1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/work/klao/iter_map.h	Sat Apr 17 01:57:48 2004 +0000
     1.3 @@ -0,0 +1,121 @@
     1.4 +// -*- c++ -*- //
     1.5 +
     1.6 +#ifndef HUGO_ITER_MAP
     1.7 +#define HUGO_ITER_MAP
     1.8 +
     1.9 +#include <vector>
    1.10 +#include <algorithm>
    1.11 +// for uint8_t
    1.12 +#include <stdint.h>
    1.13 +// for memset
    1.14 +#include <cstring>
    1.15 +
    1.16 +
    1.17 +namespace hugo {
    1.18 +
    1.19 +
    1.20 +  /// \todo Decide whether we need all the range checkings!!!
    1.21 +
    1.22 +  template<typename KeyIntMap, uint8_t N>
    1.23 +  class IterableMap {
    1.24 +  public:
    1.25 +
    1.26 +    typedef typename KeyIntMap::KeyType KeyType;
    1.27 +    typedef uint8_t ValueType;
    1.28 +
    1.29 +    typedef typename std::vector<KeyType>::const_iterator iterator;
    1.30 +
    1.31 +  protected:
    1.32 +    KeyIntMap &base;
    1.33 +    std::vector<KeyType> data;
    1.34 +    size_t bounds[N];
    1.35 +
    1.36 +    uint8_t find(size_t a) const {
    1.37 +      uint8_t n=0;
    1.38 +      for(; n<N && bounds[n]<=a; ++n);
    1.39 +      return n;
    1.40 +    }
    1.41 +
    1.42 +    void half_swap(size_t &a, size_t b) {
    1.43 +      if(a != b) {
    1.44 +	base.set(data[b],a);
    1.45 +	data[a] = data[b];
    1.46 +	a = b;
    1.47 +      }
    1.48 +    }
    1.49 +
    1.50 +    size_t move(size_t a, uint8_t m, uint8_t n) {
    1.51 +      if(m != n) {
    1.52 +	size_t orig_a = a;
    1.53 +	KeyType orig_key = data[a];
    1.54 +	while(m > n) {
    1.55 +	  --m;
    1.56 +	  half_swap(a, bounds[m]++);
    1.57 +	}
    1.58 +	while(m < n) {
    1.59 +	  half_swap(a, --bounds[m]);
    1.60 +	  ++m;
    1.61 +	}
    1.62 +	if(a != orig_a) {
    1.63 +	  base.set(orig_key, a);
    1.64 +	  data[a]=orig_key;
    1.65 +	}
    1.66 +      }
    1.67 +      return a;
    1.68 +    }
    1.69 +
    1.70 +  public:
    1.71 +    
    1.72 +    IterableMap(KeyIntMap &_base) : base(_base) {
    1.73 +      memset(bounds, 0, sizeof(bounds));
    1.74 +      //    for(int i=0; i<N; ++i) { bounds[i]=0; }
    1.75 +    }
    1.76 +
    1.77 +    uint8_t operator[](const KeyType& k) const {
    1.78 +      return find(base[k]);
    1.79 +    }
    1.80 +
    1.81 +    void set(const KeyType& k, uint8_t n) {
    1.82 +      size_t a = base[k];
    1.83 +      if(a < bounds[N-1]) {
    1.84 +	base.set(k, move(a, find(a), n));
    1.85 +      }
    1.86 +    }
    1.87 +
    1.88 +    void insert(const KeyType& k, uint8_t n) {
    1.89 +      if(n<N) {
    1.90 +	data.push_back(k);
    1.91 +	base.set(k, move(bounds[N-1]++, N-1, n));
    1.92 +      }
    1.93 +    }
    1.94 +
    1.95 +    iterator begin(uint8_t n) const {
    1.96 +      if(n < N)
    1.97 +	return data.begin() + (n ? bounds[n-1] : 0);
    1.98 +      else
    1.99 +	return data.end();
   1.100 +    }
   1.101 +
   1.102 +    iterator end(uint8_t n) const {
   1.103 +      if(n < N)
   1.104 +	return data.begin() + bounds[n];
   1.105 +      else
   1.106 +	return data.end();
   1.107 +    }
   1.108 +
   1.109 +    size_t size(uint8_t n) const {
   1.110 +      if(n < N)
   1.111 +	return bounds[n] - (n ? bounds[n-1] : 0);
   1.112 +      else
   1.113 +	return 0;
   1.114 +    }
   1.115 +    
   1.116 +    size_t size() const {
   1.117 +      // assert(bounds[N-1] == data.size());
   1.118 +      return bounds[N-1];
   1.119 +    }
   1.120 +
   1.121 +  };
   1.122 +
   1.123 +}
   1.124 +#endif