klao@347: // -*- c++ -*- // klao@347: klao@347: #ifndef HUGO_ITER_MAP klao@347: #define HUGO_ITER_MAP klao@347: klao@347: #include <vector> klao@347: #include <algorithm> klao@347: // for uint8_t klao@347: #include <stdint.h> klao@347: // for memset klao@347: #include <cstring> klao@347: marci@555: #include <hugo/invalid.h> klao@347: klao@347: namespace hugo { klao@347: klao@367: /// \brief A map with "small integers" as value set which can enumarate it klao@367: /// value classes klao@347: klao@347: /// \todo Decide whether we need all the range checkings!!! klao@347: klao@367: /// \todo Implement dynamic map behaviour. Is it necessary? Yes it is. klao@367: klao@361: template<typename KeyIntMap, uint8_t N, typename Val = uint8_t> klao@347: class IterableMap { klao@347: public: klao@347: klao@347: typedef typename KeyIntMap::KeyType KeyType; klao@361: typedef Val ValueType; klao@347: klao@347: typedef typename std::vector<KeyType>::const_iterator iterator; klao@347: klao@347: protected: klao@347: KeyIntMap &base; klao@347: std::vector<KeyType> data; klao@347: size_t bounds[N]; klao@361: Val def_val; klao@347: klao@361: Val find(size_t a) const { klao@361: for(uint8_t n=0; n<N; ++n) { klao@361: if(bounds[n] > a) klao@361: return n; klao@361: } klao@361: return def_val; klao@347: } klao@347: klao@347: void half_swap(size_t &a, size_t b) { klao@347: if(a != b) { klao@347: base.set(data[b],a); klao@347: data[a] = data[b]; klao@347: a = b; klao@347: } klao@347: } klao@347: klao@347: size_t move(size_t a, uint8_t m, uint8_t n) { klao@347: if(m != n) { klao@347: size_t orig_a = a; klao@347: KeyType orig_key = data[a]; klao@347: while(m > n) { klao@347: --m; klao@347: half_swap(a, bounds[m]++); klao@347: } klao@362: // FIXME: range check ide? klao@347: while(m < n) { klao@347: half_swap(a, --bounds[m]); klao@347: ++m; klao@347: } klao@347: if(a != orig_a) { klao@347: base.set(orig_key, a); klao@347: data[a]=orig_key; klao@347: } klao@347: } klao@347: return a; klao@347: } klao@347: klao@347: public: klao@347: klao@361: IterableMap(KeyIntMap &_base, Val d = N+1) : base(_base), def_val(d) { klao@347: memset(bounds, 0, sizeof(bounds)); klao@347: // for(int i=0; i<N; ++i) { bounds[i]=0; } klao@347: } klao@347: klao@361: Val operator[](const KeyType& k) const { klao@347: return find(base[k]); klao@347: } klao@347: klao@361: void set(const KeyType& k, Val n) { klao@362: // FIXME: range check? klao@347: size_t a = base[k]; klao@362: if(a < bounds[N-1]) { klao@367: move(a, find(a), n); klao@347: } klao@362: else { klao@362: insert(k, n); klao@362: } klao@347: } klao@347: klao@361: void insert(const KeyType& k, Val n) { klao@362: data.push_back(k); klao@362: base.set(k, move(bounds[N-1]++, N-1, n)); klao@347: } klao@347: klao@367: /// This func is not very usable, but necessary to implement klao@367: /// dynamic map behaviour. klao@367: void remove(const KeyType& k) { klao@367: size_t a = base[k]; klao@367: if(a < bounds[N-1]) { klao@367: move(a, find(a), N); klao@367: data.pop_back(); klao@367: base.set(k, -1); klao@367: } klao@367: } klao@367: klao@361: iterator begin(Val n) const { klao@362: return data.begin() + (n ? bounds[n-1] : 0); klao@347: } klao@347: klao@361: iterator end(Val n) const { klao@362: return data.begin() + bounds[n]; klao@347: } klao@347: klao@361: size_t size(Val n) const { klao@362: return bounds[n] - (n ? bounds[n-1] : 0); klao@347: } klao@347: klao@347: size_t size() const { klao@347: // assert(bounds[N-1] == data.size()); klao@347: return bounds[N-1]; klao@347: } klao@347: klao@365: klao@365: /// For use as an iterator... klao@365: KeyType& first(KeyType &k, Val n) { klao@365: size_t i = (n ? bounds[n-1] : 0); klao@365: if( i < bounds[n] ) { klao@365: k = data[i]; klao@365: } klao@365: else { klao@365: k = INVALID; klao@365: } klao@365: return k; klao@365: } klao@365: klao@365: /// For use as an iterator... klao@365: KeyType& next(KeyType &k) { klao@365: size_t i = base[k]; klao@365: uint8_t n = find(i); klao@365: ++i; klao@365: if( i < bounds[n] ) { klao@365: k = data[i]; klao@365: } klao@365: else { klao@365: k = INVALID; klao@365: } klao@365: return k; klao@365: } klao@365: klao@347: }; klao@347: klao@361: klao@361: klao@361: klao@361: template<typename KeyIntMap> klao@361: class IterableBoolMap : public IterableMap<KeyIntMap, 2, bool> { klao@361: typedef IterableMap<KeyIntMap, 2, bool> Parent; klao@361: klao@361: public: klao@361: IterableBoolMap(KeyIntMap &_base, bool d = false) : Parent(_base, d) {} klao@361: }; klao@361: klao@347: } klao@347: #endif