23 |
23 |
24 template<typename KeyIntMap, uint8_t N, typename Val = uint8_t> |
24 template<typename KeyIntMap, uint8_t N, typename Val = uint8_t> |
25 class IterableMap { |
25 class IterableMap { |
26 public: |
26 public: |
27 |
27 |
28 typedef typename KeyIntMap::KeyType KeyType; |
28 typedef typename KeyIntMap::Key Key; |
29 typedef Val ValueType; |
29 typedef Val Value; |
30 |
30 |
31 typedef typename std::vector<KeyType>::const_iterator iterator; |
31 typedef typename std::vector<Key>::const_iterator iterator; |
32 |
32 |
33 protected: |
33 protected: |
34 KeyIntMap &base; |
34 KeyIntMap &base; |
35 std::vector<KeyType> data; |
35 std::vector<Key> data; |
36 size_t bounds[N]; |
36 size_t bounds[N]; |
37 Val def_val; |
37 Val def_val; |
38 |
38 |
39 Val find(size_t a) const { |
39 Val find(size_t a) const { |
40 for(uint8_t n=0; n<N; ++n) { |
40 for(uint8_t n=0; n<N; ++n) { |
53 } |
53 } |
54 |
54 |
55 size_t move(size_t a, uint8_t m, uint8_t n) { |
55 size_t move(size_t a, uint8_t m, uint8_t n) { |
56 if(m != n) { |
56 if(m != n) { |
57 size_t orig_a = a; |
57 size_t orig_a = a; |
58 KeyType orig_key = data[a]; |
58 Key orig_key = data[a]; |
59 while(m > n) { |
59 while(m > n) { |
60 --m; |
60 --m; |
61 half_swap(a, bounds[m]++); |
61 half_swap(a, bounds[m]++); |
62 } |
62 } |
63 // FIXME: range check ide? |
63 // FIXME: range check ide? |
78 IterableMap(KeyIntMap &_base, Val d = N+1) : base(_base), def_val(d) { |
78 IterableMap(KeyIntMap &_base, Val d = N+1) : base(_base), def_val(d) { |
79 memset(bounds, 0, sizeof(bounds)); |
79 memset(bounds, 0, sizeof(bounds)); |
80 // for(int i=0; i<N; ++i) { bounds[i]=0; } |
80 // for(int i=0; i<N; ++i) { bounds[i]=0; } |
81 } |
81 } |
82 |
82 |
83 Val operator[](const KeyType& k) const { |
83 Val operator[](const Key& k) const { |
84 return find(base[k]); |
84 return find(base[k]); |
85 } |
85 } |
86 |
86 |
87 void set(const KeyType& k, Val n) { |
87 void set(const Key& k, Val n) { |
88 // FIXME: range check? |
88 // FIXME: range check? |
89 size_t a = base[k]; |
89 size_t a = base[k]; |
90 if(a < bounds[N-1]) { |
90 if(a < bounds[N-1]) { |
91 move(a, find(a), n); |
91 move(a, find(a), n); |
92 } |
92 } |
93 else { |
93 else { |
94 insert(k, n); |
94 insert(k, n); |
95 } |
95 } |
96 } |
96 } |
97 |
97 |
98 void insert(const KeyType& k, Val n) { |
98 void insert(const Key& k, Val n) { |
99 data.push_back(k); |
99 data.push_back(k); |
100 base.set(k, move(bounds[N-1]++, N-1, n)); |
100 base.set(k, move(bounds[N-1]++, N-1, n)); |
101 } |
101 } |
102 |
102 |
103 /// This func is not very usable, but necessary to implement |
103 /// This func is not very usable, but necessary to implement |
104 /// dynamic map behaviour. |
104 /// dynamic map behaviour. |
105 void remove(const KeyType& k) { |
105 void remove(const Key& k) { |
106 size_t a = base[k]; |
106 size_t a = base[k]; |
107 if(a < bounds[N-1]) { |
107 if(a < bounds[N-1]) { |
108 move(a, find(a), N); |
108 move(a, find(a), N); |
109 data.pop_back(); |
109 data.pop_back(); |
110 base.set(k, -1); |
110 base.set(k, -1); |