|
1 // -*- c++ -*- // |
|
2 |
|
3 #ifndef HUGO_ITER_MAP |
|
4 #define HUGO_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 |
|
14 namespace hugo { |
|
15 |
|
16 |
|
17 /// \todo Decide whether we need all the range checkings!!! |
|
18 |
|
19 template<typename KeyIntMap, uint8_t N> |
|
20 class IterableMap { |
|
21 public: |
|
22 |
|
23 typedef typename KeyIntMap::KeyType KeyType; |
|
24 typedef uint8_t ValueType; |
|
25 |
|
26 typedef typename std::vector<KeyType>::const_iterator iterator; |
|
27 |
|
28 protected: |
|
29 KeyIntMap &base; |
|
30 std::vector<KeyType> data; |
|
31 size_t bounds[N]; |
|
32 |
|
33 uint8_t find(size_t a) const { |
|
34 uint8_t n=0; |
|
35 for(; n<N && bounds[n]<=a; ++n); |
|
36 return n; |
|
37 } |
|
38 |
|
39 void half_swap(size_t &a, size_t b) { |
|
40 if(a != b) { |
|
41 base.set(data[b],a); |
|
42 data[a] = data[b]; |
|
43 a = b; |
|
44 } |
|
45 } |
|
46 |
|
47 size_t move(size_t a, uint8_t m, uint8_t n) { |
|
48 if(m != n) { |
|
49 size_t orig_a = a; |
|
50 KeyType orig_key = data[a]; |
|
51 while(m > n) { |
|
52 --m; |
|
53 half_swap(a, bounds[m]++); |
|
54 } |
|
55 while(m < n) { |
|
56 half_swap(a, --bounds[m]); |
|
57 ++m; |
|
58 } |
|
59 if(a != orig_a) { |
|
60 base.set(orig_key, a); |
|
61 data[a]=orig_key; |
|
62 } |
|
63 } |
|
64 return a; |
|
65 } |
|
66 |
|
67 public: |
|
68 |
|
69 IterableMap(KeyIntMap &_base) : base(_base) { |
|
70 memset(bounds, 0, sizeof(bounds)); |
|
71 // for(int i=0; i<N; ++i) { bounds[i]=0; } |
|
72 } |
|
73 |
|
74 uint8_t operator[](const KeyType& k) const { |
|
75 return find(base[k]); |
|
76 } |
|
77 |
|
78 void set(const KeyType& k, uint8_t n) { |
|
79 size_t a = base[k]; |
|
80 if(a < bounds[N-1]) { |
|
81 base.set(k, move(a, find(a), n)); |
|
82 } |
|
83 } |
|
84 |
|
85 void insert(const KeyType& k, uint8_t n) { |
|
86 if(n<N) { |
|
87 data.push_back(k); |
|
88 base.set(k, move(bounds[N-1]++, N-1, n)); |
|
89 } |
|
90 } |
|
91 |
|
92 iterator begin(uint8_t n) const { |
|
93 if(n < N) |
|
94 return data.begin() + (n ? bounds[n-1] : 0); |
|
95 else |
|
96 return data.end(); |
|
97 } |
|
98 |
|
99 iterator end(uint8_t n) const { |
|
100 if(n < N) |
|
101 return data.begin() + bounds[n]; |
|
102 else |
|
103 return data.end(); |
|
104 } |
|
105 |
|
106 size_t size(uint8_t n) const { |
|
107 if(n < N) |
|
108 return bounds[n] - (n ? bounds[n-1] : 0); |
|
109 else |
|
110 return 0; |
|
111 } |
|
112 |
|
113 size_t size() const { |
|
114 // assert(bounds[N-1] == data.size()); |
|
115 return bounds[N-1]; |
|
116 } |
|
117 |
|
118 }; |
|
119 |
|
120 } |
|
121 #endif |