// -*- c++ -*- //

 #ifndef LEMON_ITER_MAP

 #define LEMON_ITER_MAP

 #include <vector>

 #include <algorithm>

 // for uint8_t

 #include <stdint.h>

 // for memset

 #include <cstring>

 #include <lemon/invalid.h>

 namespace lemon {

   /// \brief A map with "small integers" as value set which can enumarate it

   /// value classes

   /// \todo Decide whether we need all the range checkings!!!

   /// \todo Implement dynamic map behaviour. Is it necessary? Yes it is.

   template<typename KeyIntMap, uint8_t N, typename Val = uint8_t>

   class IterableMap {

   public:

     typedef typename KeyIntMap::KeyType KeyType;

     typedef Val ValueType;

     typedef typename std::vector<KeyType>::const_iterator iterator;

   protected:

     KeyIntMap &base;

     std::vector<KeyType> data;

     size_t bounds[N];

     Val def_val;

     Val find(size_t a) const {

       for(uint8_t n=0; n<N; ++n) {

 	if(bounds[n] > a)

 	  return n;

       }

       return def_val;

     }

     void half_swap(size_t &a, size_t b) {

       if(a != b) {

 	base.set(data[b],a);

 	data[a] = data[b];

 	a = b;

       }

     }

     size_t move(size_t a, uint8_t m, uint8_t n) {

       if(m != n) {

 	size_t orig_a = a;

 	KeyType orig_key = data[a];

 	while(m > n) {

 	  --m;

 	  half_swap(a, bounds[m]++);

 	}

 	// FIXME: range check ide?

 	while(m < n) {

 	  half_swap(a, --bounds[m]);

 	  ++m;

 	}

 	if(a != orig_a) {

 	  base.set(orig_key, a);

 	  data[a]=orig_key;

 	}

       }

       return a;

     }

   public:

     IterableMap(KeyIntMap &_base, Val d = N+1) : base(_base), def_val(d) {

       memset(bounds, 0, sizeof(bounds));

       //    for(int i=0; i<N; ++i) { bounds[i]=0; }

     }

     Val operator[](const KeyType& k) const {

       return find(base[k]);

     }

     void set(const KeyType& k, Val n) {

       // FIXME: range check?

       size_t a = base[k];

       if(a < bounds[N-1]) {

 	move(a, find(a), n);

       }

       else {

 	insert(k, n);

       }

     }

     void insert(const KeyType& k, Val n) {

       data.push_back(k);

       base.set(k, move(bounds[N-1]++, N-1, n));

     }

     /// This func is not very usable, but necessary to implement 

     /// dynamic map behaviour.

     void remove(const KeyType& k) {

       size_t a = base[k];

       if(a < bounds[N-1]) {

 	move(a, find(a), N);

 	data.pop_back();

 	base.set(k, -1);

       }

     }

     iterator begin(Val n) const {

       return data.begin() + (n ? bounds[n-1] : 0);

     }

     iterator end(Val n) const {

       return data.begin() + bounds[n];

     }

     size_t size(Val n) const {

       return bounds[n] - (n ? bounds[n-1] : 0);

     }

     size_t size() const {

       // assert(bounds[N-1] == data.size());

       return bounds[N-1];

     }

     /// For use as an iterator...

     KeyType& first(KeyType &k, Val n) {

       size_t i = (n ? bounds[n-1] : 0);

       if( i < bounds[n] ) {

 	k = data[i];

       }

       else {

 	k = INVALID;

       }

       return k;

     }

     /// For use as an iterator...

     KeyType& next(KeyType &k) {

       size_t i = base[k];

       uint8_t n = find(i);

       ++i;

       if( i < bounds[n] ) {

 	k = data[i];

       }

       else {

 	k = INVALID;

       }

       return k;

     }

   };

   template<typename KeyIntMap>

   class IterableBoolMap : public IterableMap<KeyIntMap, 2, bool> {

     typedef IterableMap<KeyIntMap, 2, bool> Parent;

   public:

     IterableBoolMap(KeyIntMap &_base, bool d = false) : Parent(_base, d) {}

   };

 }

 #endif