source: lemon-0.x/src/work/klao/iter_map.h @ 672:6c7bd0edd1d7

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

#ifndef HUGO_ITER_MAP
#define HUGO_ITER_MAP

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

#include <hugo/invalid.h>

namespace hugo {

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