// -*- 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