|
1 #ifndef ARRAY_MAP_H |
|
2 #define ARRAY_MAP_H |
|
3 |
|
4 #include <memory> |
|
5 |
|
6 #include "map_base.h" |
|
7 |
|
8 #include <iostream> |
|
9 using namespace std; |
|
10 |
|
11 namespace hugo { |
|
12 |
|
13 template <typename G, typename K, typename KIt> |
|
14 class ArrayMapFactory { |
|
15 |
|
16 |
|
17 public: |
|
18 |
|
19 typedef G Graph; |
|
20 typedef K Key; |
|
21 typedef KIt KeyIt; |
|
22 |
|
23 template <typename V, typename A = allocator<V> > |
|
24 class Map : public MapBase<G, K, KIt> { |
|
25 public: |
|
26 typedef V Value; |
|
27 typedef typename _Alloc_traits<V, A>::_Alloc_type _Alloc_type; |
|
28 |
|
29 |
|
30 Map() : values(0), capacity(0) {} |
|
31 |
|
32 Map(Graph& g, MapRegistry<G, K, KIt>& r) |
|
33 : MapBase<G, K, KIt>(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 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 } |
|
122 |
|
123 #endif |