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

#ifndef HUGO_ITER_MAP
#define HUGO_ITER_MAP

#include <vector>
#include <algorithm>
// for uint8_t
#include <stdint.h>
// for memset
#include <cstring>


namespace hugo {


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

  template<typename KeyIntMap, uint8_t N>
  class IterableMap {
  public:

    typedef typename KeyIntMap::KeyType KeyType;
    typedef uint8_t ValueType;

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

  protected:
    KeyIntMap &base;
    std::vector<KeyType> data;
    size_t bounds[N];

    uint8_t find(size_t a) const {
      uint8_t n=0;
      for(; n<N && bounds[n]<=a; ++n);
      return n;
    }

    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]++);
	}
	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) : base(_base) {
      memset(bounds, 0, sizeof(bounds));
      //    for(int i=0; i<N; ++i) { bounds[i]=0; }
    }

    uint8_t operator[](const KeyType& k) const {
      return find(base[k]);
    }

    void set(const KeyType& k, uint8_t n) {
      size_t a = base[k];
      if(a < bounds[N-1]) {
	base.set(k, move(a, find(a), n));
      }
    }

    void insert(const KeyType& k, uint8_t n) {
      if(n<N) {
	data.push_back(k);
	base.set(k, move(bounds[N-1]++, N-1, n));
      }
    }

    iterator begin(uint8_t n) const {
      if(n < N)
	return data.begin() + (n ? bounds[n-1] : 0);
      else
	return data.end();
    }

    iterator end(uint8_t n) const {
      if(n < N)
	return data.begin() + bounds[n];
      else
	return data.end();
    }

    size_t size(uint8_t n) const {
      if(n < N)
	return bounds[n] - (n ? bounds[n-1] : 0);
      else
	return 0;
    }
    
    size_t size() const {
      // assert(bounds[N-1] == data.size());
      return bounds[N-1];
    }

  };

}
#endif