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: 
klao@347: 
klao@347: namespace hugo {
klao@347: 
klao@347: 
klao@347:   /// \todo Decide whether we need all the range checkings!!!
klao@347: 
klao@347:   template<typename KeyIntMap, uint8_t N>
klao@347:   class IterableMap {
klao@347:   public:
klao@347: 
klao@347:     typedef typename KeyIntMap::KeyType KeyType;
klao@347:     typedef uint8_t 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@347: 
klao@347:     uint8_t find(size_t a) const {
klao@347:       uint8_t n=0;
klao@347:       for(; n<N && bounds[n]<=a; ++n);
klao@347:       return n;
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@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@347:     IterableMap(KeyIntMap &_base) : base(_base) {
klao@347:       memset(bounds, 0, sizeof(bounds));
klao@347:       //    for(int i=0; i<N; ++i) { bounds[i]=0; }
klao@347:     }
klao@347: 
klao@347:     uint8_t operator[](const KeyType& k) const {
klao@347:       return find(base[k]);
klao@347:     }
klao@347: 
klao@347:     void set(const KeyType& k, uint8_t n) {
klao@347:       size_t a = base[k];
klao@347:       if(a < bounds[N-1]) {
klao@347: 	base.set(k, move(a, find(a), n));
klao@347:       }
klao@347:     }
klao@347: 
klao@347:     void insert(const KeyType& k, uint8_t n) {
klao@347:       if(n<N) {
klao@347: 	data.push_back(k);
klao@347: 	base.set(k, move(bounds[N-1]++, N-1, n));
klao@347:       }
klao@347:     }
klao@347: 
klao@347:     iterator begin(uint8_t n) const {
klao@347:       if(n < N)
klao@347: 	return data.begin() + (n ? bounds[n-1] : 0);
klao@347:       else
klao@347: 	return data.end();
klao@347:     }
klao@347: 
klao@347:     iterator end(uint8_t n) const {
klao@347:       if(n < N)
klao@347: 	return data.begin() + bounds[n];
klao@347:       else
klao@347: 	return data.end();
klao@347:     }
klao@347: 
klao@347:     size_t size(uint8_t n) const {
klao@347:       if(n < N)
klao@347: 	return bounds[n] - (n ? bounds[n-1] : 0);
klao@347:       else
klao@347: 	return 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@347:   };
klao@347: 
klao@347: }
klao@347: #endif