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