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