1 #ifndef ARRAY_MAP_H |
1 #ifndef ARRAY_MAP_H |
2 #define ARRAY_MAP_H |
2 #define ARRAY_MAP_H |
3 |
3 |
4 #include <memory> |
4 #include <memory> |
5 |
5 |
6 #include "map_base.h" |
|
7 |
6 |
8 #include <iostream> |
7 #include <iostream> |
9 using namespace std; |
8 using namespace std; |
10 |
9 |
11 namespace hugo { |
10 namespace hugo { |
12 |
11 |
13 template <typename G, typename K, typename KIt> |
12 template <typename MapRegistry> class ArrayMapFactory { |
14 class ArrayMapFactory { |
13 |
|
14 public: |
|
15 |
|
16 typedef typename MapRegistry::Graph Graph; |
|
17 typedef typename MapRegistry::Key Key; |
|
18 typedef typename MapRegistry::KeyIt KeyIt; |
|
19 |
|
20 typedef typename MapRegistry::MapBase MapBase; |
|
21 |
|
22 template <typename V, typename A = std::allocator<V> > |
|
23 class Map : public MapBase { |
|
24 |
|
25 public: |
|
26 |
|
27 typedef V Value; |
|
28 typedef A Allocator; |
|
29 |
|
30 |
|
31 Map() : values(0), capacity(0) {} |
|
32 |
|
33 Map(Graph& g, MapRegistry& r) : MapBase(g, r) { |
|
34 int max_id = -1; |
|
35 for (KeyIt it(*graph); graph->valid(it); graph->next(it)) { |
|
36 int id = graph->id(it); |
|
37 if (id > max_id) { |
|
38 max_id = id; |
|
39 } |
|
40 } |
|
41 if (max_id == -1) { |
|
42 capacity = 0; |
|
43 values = 0; |
|
44 return; |
|
45 } |
|
46 capacity = 1; |
|
47 while (capacity <= max_id) { |
|
48 capacity <<= 1; |
|
49 } |
|
50 values = allocator.allocate(capacity); |
|
51 for (KeyIt it(*graph); graph->valid(it); graph->next(it)) { |
|
52 int id = graph->id(it); |
|
53 allocator.construct(&(values[id]), Value()); |
|
54 } |
|
55 } |
|
56 |
|
57 Map(const Map& copy) : MapBase(*copy.graph, *copy.registry) { |
|
58 capacity = copy.capacity; |
|
59 values = allocator.allocate(capacity); |
|
60 for (KeyIt it(*graph); graph->valid(it); graph->next(it)) { |
|
61 int id = graph->id(it); |
|
62 allocator.construct(&(values[id]), copy.values[id]); |
|
63 } |
|
64 } |
|
65 |
|
66 virtual ~Map() { |
|
67 destroy(); |
|
68 allocator.deallocate(values, capacity); |
|
69 } |
15 |
70 |
16 |
71 |
17 public: |
72 Value& operator[](const Key& key) { |
|
73 int id = graph->id(key); |
|
74 return values[id]; |
|
75 } |
18 |
76 |
19 typedef G Graph; |
77 const Value& operator[](const Key& key) const { |
20 typedef K Key; |
78 int id = graph->id(key); |
21 typedef KIt KeyIt; |
79 return values[id]; |
|
80 } |
|
81 |
|
82 const Value& get(const Key& key) const { |
|
83 int id = graph->id(key); |
|
84 return values[id]; |
|
85 } |
22 |
86 |
23 template <typename V, typename A = allocator<V> > |
87 void set(const Key& key, const Value& val) { |
24 class Map : public MapBase<G, K, KIt> { |
88 int id = graph->id(key); |
25 public: |
89 values[id] = val; |
26 typedef V Value; |
90 } |
27 typedef typename _Alloc_traits<V, A>::_Alloc_type _Alloc_type; |
91 |
28 |
92 void add(const Key& key) { |
|
93 int id = graph->id(key); |
|
94 if (id >= capacity) { |
|
95 int new_capacity = (capacity == 0 ? 1 : capacity); |
|
96 while (new_capacity <= id) { |
|
97 new_capacity <<= 1; |
|
98 } |
|
99 Value* new_values = allocator.allocate(new_capacity);; |
|
100 for (KeyIt it(*graph); graph->valid(it); graph->next(it)) { |
|
101 int jd = graph->id(it); |
|
102 if (id != jd) { |
|
103 allocator.construct(&(new_values[jd]), values[jd]); |
|
104 allocator.destroy(&(values[jd])); |
|
105 } |
|
106 } |
|
107 if (capacity != 0) allocator.deallocate(values, capacity); |
|
108 values = new_values; |
|
109 capacity = new_capacity; |
|
110 } |
|
111 allocator.construct(&(values[id]), Value()); |
|
112 } |
|
113 |
|
114 void erase(const Key& key) { |
|
115 int id = graph->id(key); |
|
116 allocator.destroy(&(values[id])); |
|
117 } |
29 |
118 |
30 Map() : values(0), capacity(0) {} |
119 private: |
31 |
120 int capacity; |
32 Map(Graph& g, MapRegistry<G, K, KIt>& r) |
121 Value* values; |
33 : MapBase<G, K, KIt>(g, r) { |
122 Allocator allocator; |
34 int max_id = -1; |
123 }; |
35 for (KeyIt it(*graph); graph->valid(it); graph->next(it)) { |
124 }; |
36 int id = graph->id(it); |
|
37 if (id > max_id) { |
|
38 max_id = id; |
|
39 } |
|
40 } |
|
41 if (max_id == -1) { |
|
42 capacity = 0; |
|
43 values = 0; |
|
44 return; |
|
45 } |
|
46 int capacity = 1; |
|
47 while (capacity <= max_id) { |
|
48 capacity <<= 1; |
|
49 } |
|
50 Value* values = reinterpret_cast<Value*>(new char[capacity*sizeof(Value)]); |
|
51 for (KeyIt it(*graph); graph->valid(it); graph->next(it)) { |
|
52 int id = graph->id(it); |
|
53 new(&(values[id])) Value(); |
|
54 } |
|
55 cerr << capacity << endl; |
|
56 } |
|
57 |
|
58 virtual ~Map() { |
|
59 destroy(); |
|
60 delete[] reinterpret_cast<char*>(values); |
|
61 values = 0; |
|
62 capacity = 0; |
|
63 } |
|
64 |
|
65 |
|
66 Value& operator[](const K& key) { |
|
67 int id = graph->id(key); |
|
68 return values[id]; |
|
69 } |
|
70 |
|
71 const Value& operator[](const K& key) const { |
|
72 int id = graph->id(key); |
|
73 return values[id]; |
|
74 } |
|
75 |
|
76 const Value& get(const K& key) const { |
|
77 int id = graph->id(key); |
|
78 return values[id]; |
|
79 } |
|
80 |
|
81 void set(const K& key, const Value& val) { |
|
82 int id = graph->id(key); |
|
83 values[id] = val; |
|
84 } |
|
85 |
|
86 void add(const K& key) { |
|
87 cerr << capacity << endl; |
|
88 int id = graph->id(key); |
|
89 if (id >= capacity) { |
|
90 int new_capacity = (capacity == 0 ? 1 : capacity); |
|
91 while (new_capacity <= id) { |
|
92 new_capacity <<= 1; |
|
93 } |
|
94 Value* new_values = reinterpret_cast<Value*>(new char[new_capacity*sizeof(Value)]);; |
|
95 for (KeyIt it(*graph); graph->valid(it); graph->next(it)) { |
|
96 int jd = graph->id(it); |
|
97 if (id != jd) { |
|
98 new(&(new_values[jd])) Value(values[jd]); |
|
99 } |
|
100 } |
|
101 if (capacity != 0) delete[] reinterpret_cast<char *>(values); |
|
102 values = new_values; |
|
103 capacity = new_capacity; |
|
104 } |
|
105 cerr << id << ' ' << capacity << endl; |
|
106 new(&(values[id])) Value(); |
|
107 } |
|
108 |
|
109 void erase(const K& key) { |
|
110 int id = graph->id(key); |
|
111 values[id].~Value(); |
|
112 } |
|
113 |
|
114 private: |
|
115 int capacity; |
|
116 Value* values; |
|
117 |
|
118 }; |
|
119 |
|
120 }; |
|
121 } |
125 } |
122 |
126 |
123 #endif |
127 #endif |