1.1 --- a/src/work/klao/iter_map.h Sun Apr 17 18:57:22 2005 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,172 +0,0 @@
1.4 -// -*- c++ -*- //
1.5 -
1.6 -#ifndef LEMON_ITER_MAP
1.7 -#define LEMON_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 -#include <lemon/invalid.h>
1.17 -
1.18 -namespace lemon {
1.19 -
1.20 - /// \brief A map with "small integers" as value set which can enumarate it
1.21 - /// value classes
1.22 -
1.23 - /// \todo Decide whether we need all the range checkings!!!
1.24 -
1.25 - /// \todo Implement dynamic map behaviour. Is it necessary? Yes it is.
1.26 -
1.27 - template<typename KeyIntMap, uint8_t N, typename Val = uint8_t>
1.28 - class IterableMap {
1.29 - public:
1.30 -
1.31 - typedef typename KeyIntMap::Key Key;
1.32 - typedef Val Value;
1.33 -
1.34 - typedef typename std::vector<Key>::const_iterator iterator;
1.35 -
1.36 - protected:
1.37 - KeyIntMap &base;
1.38 - std::vector<Key> data;
1.39 - size_t bounds[N];
1.40 - Val def_val;
1.41 -
1.42 - Val find(size_t a) const {
1.43 - for(uint8_t n=0; n<N; ++n) {
1.44 - if(bounds[n] > a)
1.45 - return n;
1.46 - }
1.47 - return def_val;
1.48 - }
1.49 -
1.50 - void half_swap(size_t &a, size_t b) {
1.51 - if(a != b) {
1.52 - base.set(data[b],a);
1.53 - data[a] = data[b];
1.54 - a = b;
1.55 - }
1.56 - }
1.57 -
1.58 - size_t move(size_t a, uint8_t m, uint8_t n) {
1.59 - if(m != n) {
1.60 - size_t orig_a = a;
1.61 - Key orig_key = data[a];
1.62 - while(m > n) {
1.63 - --m;
1.64 - half_swap(a, bounds[m]++);
1.65 - }
1.66 - // FIXME: range check ide?
1.67 - while(m < n) {
1.68 - half_swap(a, --bounds[m]);
1.69 - ++m;
1.70 - }
1.71 - if(a != orig_a) {
1.72 - base.set(orig_key, a);
1.73 - data[a]=orig_key;
1.74 - }
1.75 - }
1.76 - return a;
1.77 - }
1.78 -
1.79 - public:
1.80 -
1.81 - IterableMap(KeyIntMap &_base, Val d = N+1) : base(_base), def_val(d) {
1.82 - memset(bounds, 0, sizeof(bounds));
1.83 - // for(int i=0; i<N; ++i) { bounds[i]=0; }
1.84 - }
1.85 -
1.86 - Val operator[](const Key& k) const {
1.87 - return find(base[k]);
1.88 - }
1.89 -
1.90 - void set(const Key& k, Val n) {
1.91 - // FIXME: range check?
1.92 - size_t a = base[k];
1.93 - if(a < bounds[N-1]) {
1.94 - move(a, find(a), n);
1.95 - }
1.96 - else {
1.97 - insert(k, n);
1.98 - }
1.99 - }
1.100 -
1.101 - void insert(const Key& k, Val n) {
1.102 - data.push_back(k);
1.103 - base.set(k, move(bounds[N-1]++, N-1, n));
1.104 - }
1.105 -
1.106 - /// This func is not very usable, but necessary to implement
1.107 - /// dynamic map behaviour.
1.108 - void remove(const Key& k) {
1.109 - size_t a = base[k];
1.110 - if(a < bounds[N-1]) {
1.111 - move(a, find(a), N);
1.112 - data.pop_back();
1.113 - base.set(k, -1);
1.114 - }
1.115 - }
1.116 -
1.117 - iterator begin(Val n) const {
1.118 - return data.begin() + (n ? bounds[n-1] : 0);
1.119 - }
1.120 -
1.121 - iterator end(Val n) const {
1.122 - return data.begin() + bounds[n];
1.123 - }
1.124 -
1.125 - size_t size(Val n) const {
1.126 - return bounds[n] - (n ? bounds[n-1] : 0);
1.127 - }
1.128 -
1.129 - size_t size() const {
1.130 - // assert(bounds[N-1] == data.size());
1.131 - return bounds[N-1];
1.132 - }
1.133 -
1.134 -
1.135 - /// For use as an iterator...
1.136 - Key& first(Key &k, Val n) {
1.137 - size_t i = (n ? bounds[n-1] : 0);
1.138 - if( i < bounds[n] ) {
1.139 - k = data[i];
1.140 - }
1.141 - else {
1.142 - k = INVALID;
1.143 - }
1.144 - return k;
1.145 - }
1.146 -
1.147 - /// For use as an iterator...
1.148 - Key& next(Key &k) {
1.149 - size_t i = base[k];
1.150 - uint8_t n = find(i);
1.151 - ++i;
1.152 - if( i < bounds[n] ) {
1.153 - k = data[i];
1.154 - }
1.155 - else {
1.156 - k = INVALID;
1.157 - }
1.158 - return k;
1.159 - }
1.160 -
1.161 - };
1.162 -
1.163 -
1.164 -
1.165 -
1.166 - template<typename KeyIntMap>
1.167 - class IterableBoolMap : public IterableMap<KeyIntMap, 2, bool> {
1.168 - typedef IterableMap<KeyIntMap, 2, bool> Parent;
1.169 -
1.170 - public:
1.171 - IterableBoolMap(KeyIntMap &_base, bool d = false) : Parent(_base, d) {}
1.172 - };
1.173 -
1.174 -}
1.175 -#endif