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