1 // -*- c++ -*- // |
|
2 |
|
3 #ifndef LEMON_ITER_MAP |
|
4 #define LEMON_ITER_MAP |
|
5 |
|
6 #include <vector> |
|
7 #include <algorithm> |
|
8 // for uint8_t |
|
9 #include <stdint.h> |
|
10 // for memset |
|
11 #include <cstring> |
|
12 |
|
13 #include <lemon/invalid.h> |
|
14 |
|
15 namespace lemon { |
|
16 |
|
17 /// \brief A map with "small integers" as value set which can enumarate it |
|
18 /// value classes |
|
19 |
|
20 /// \todo Decide whether we need all the range checkings!!! |
|
21 |
|
22 /// \todo Implement dynamic map behaviour. Is it necessary? Yes it is. |
|
23 |
|
24 template<typename KeyIntMap, uint8_t N, typename Val = uint8_t> |
|
25 class IterableMap { |
|
26 public: |
|
27 |
|
28 typedef typename KeyIntMap::Key Key; |
|
29 typedef Val Value; |
|
30 |
|
31 typedef typename std::vector<Key>::const_iterator iterator; |
|
32 |
|
33 protected: |
|
34 KeyIntMap &base; |
|
35 std::vector<Key> data; |
|
36 size_t bounds[N]; |
|
37 Val def_val; |
|
38 |
|
39 Val find(size_t a) const { |
|
40 for(uint8_t n=0; n<N; ++n) { |
|
41 if(bounds[n] > a) |
|
42 return n; |
|
43 } |
|
44 return def_val; |
|
45 } |
|
46 |
|
47 void half_swap(size_t &a, size_t b) { |
|
48 if(a != b) { |
|
49 base.set(data[b],a); |
|
50 data[a] = data[b]; |
|
51 a = b; |
|
52 } |
|
53 } |
|
54 |
|
55 size_t move(size_t a, uint8_t m, uint8_t n) { |
|
56 if(m != n) { |
|
57 size_t orig_a = a; |
|
58 Key orig_key = data[a]; |
|
59 while(m > n) { |
|
60 --m; |
|
61 half_swap(a, bounds[m]++); |
|
62 } |
|
63 // FIXME: range check ide? |
|
64 while(m < n) { |
|
65 half_swap(a, --bounds[m]); |
|
66 ++m; |
|
67 } |
|
68 if(a != orig_a) { |
|
69 base.set(orig_key, a); |
|
70 data[a]=orig_key; |
|
71 } |
|
72 } |
|
73 return a; |
|
74 } |
|
75 |
|
76 public: |
|
77 |
|
78 IterableMap(KeyIntMap &_base, Val d = N+1) : base(_base), def_val(d) { |
|
79 memset(bounds, 0, sizeof(bounds)); |
|
80 // for(int i=0; i<N; ++i) { bounds[i]=0; } |
|
81 } |
|
82 |
|
83 Val operator[](const Key& k) const { |
|
84 return find(base[k]); |
|
85 } |
|
86 |
|
87 void set(const Key& k, Val n) { |
|
88 // FIXME: range check? |
|
89 size_t a = base[k]; |
|
90 if(a < bounds[N-1]) { |
|
91 move(a, find(a), n); |
|
92 } |
|
93 else { |
|
94 insert(k, n); |
|
95 } |
|
96 } |
|
97 |
|
98 void insert(const Key& k, Val n) { |
|
99 data.push_back(k); |
|
100 base.set(k, move(bounds[N-1]++, N-1, n)); |
|
101 } |
|
102 |
|
103 /// This func is not very usable, but necessary to implement |
|
104 /// dynamic map behaviour. |
|
105 void remove(const Key& k) { |
|
106 size_t a = base[k]; |
|
107 if(a < bounds[N-1]) { |
|
108 move(a, find(a), N); |
|
109 data.pop_back(); |
|
110 base.set(k, -1); |
|
111 } |
|
112 } |
|
113 |
|
114 iterator begin(Val n) const { |
|
115 return data.begin() + (n ? bounds[n-1] : 0); |
|
116 } |
|
117 |
|
118 iterator end(Val n) const { |
|
119 return data.begin() + bounds[n]; |
|
120 } |
|
121 |
|
122 size_t size(Val n) const { |
|
123 return bounds[n] - (n ? bounds[n-1] : 0); |
|
124 } |
|
125 |
|
126 size_t size() const { |
|
127 // assert(bounds[N-1] == data.size()); |
|
128 return bounds[N-1]; |
|
129 } |
|
130 |
|
131 |
|
132 /// For use as an iterator... |
|
133 Key& first(Key &k, Val n) { |
|
134 size_t i = (n ? bounds[n-1] : 0); |
|
135 if( i < bounds[n] ) { |
|
136 k = data[i]; |
|
137 } |
|
138 else { |
|
139 k = INVALID; |
|
140 } |
|
141 return k; |
|
142 } |
|
143 |
|
144 /// For use as an iterator... |
|
145 Key& next(Key &k) { |
|
146 size_t i = base[k]; |
|
147 uint8_t n = find(i); |
|
148 ++i; |
|
149 if( i < bounds[n] ) { |
|
150 k = data[i]; |
|
151 } |
|
152 else { |
|
153 k = INVALID; |
|
154 } |
|
155 return k; |
|
156 } |
|
157 |
|
158 }; |
|
159 |
|
160 |
|
161 |
|
162 |
|
163 template<typename KeyIntMap> |
|
164 class IterableBoolMap : public IterableMap<KeyIntMap, 2, bool> { |
|
165 typedef IterableMap<KeyIntMap, 2, bool> Parent; |
|
166 |
|
167 public: |
|
168 IterableBoolMap(KeyIntMap &_base, bool d = false) : Parent(_base, d) {} |
|
169 }; |
|
170 |
|
171 } |
|
172 #endif |
|