# source:lemon-0.x/src/work/klao/iter_map.h@946:c94ef40a22ce

Last change on this file since 946:c94ef40a22ce was 921:818510fa3d99, checked in by Alpar Juttner, 18 years ago

hugo -> lemon

File size: 3.3 KB
Line
1// -*- c++ -*- //
2
3#ifndef LEMON_ITER_MAP
4#define LEMON_ITER_MAP
5
6#include <vector>
7#include <algorithm>
8// for uint8_t
9#include <stdint.h>
10// for memset
11#include <cstring>
12
13#include <lemon/invalid.h>
14
15namespace lemon {
16
17  /// \brief A map with "small integers" as value set which can enumarate it
18  /// value classes
19
20  /// \todo Decide whether we need all the range checkings!!!
21
22  /// \todo Implement dynamic map behaviour. Is it necessary? Yes it is.
23
24  template<typename KeyIntMap, uint8_t N, typename Val = uint8_t>
25  class IterableMap {
26  public:
27
28    typedef typename KeyIntMap::KeyType KeyType;
29    typedef Val ValueType;
30
31    typedef typename std::vector<KeyType>::const_iterator iterator;
32
33  protected:
34    KeyIntMap &base;
35    std::vector<KeyType> data;
36    size_t bounds[N];
37    Val def_val;
38
39    Val find(size_t a) const {
40      for(uint8_t n=0; n<N; ++n) {
41        if(bounds[n] > a)
42          return n;
43      }
44      return def_val;
45    }
46
47    void half_swap(size_t &a, size_t b) {
48      if(a != b) {
49        base.set(data[b],a);
50        data[a] = data[b];
51        a = b;
52      }
53    }
54
55    size_t move(size_t a, uint8_t m, uint8_t n) {
56      if(m != n) {
57        size_t orig_a = a;
58        KeyType orig_key = data[a];
59        while(m > n) {
60          --m;
61          half_swap(a, bounds[m]++);
62        }
63        // FIXME: range check ide?
64        while(m < n) {
65          half_swap(a, --bounds[m]);
66          ++m;
67        }
68        if(a != orig_a) {
69          base.set(orig_key, a);
70          data[a]=orig_key;
71        }
72      }
73      return a;
74    }
75
76  public:
77
78    IterableMap(KeyIntMap &_base, Val d = N+1) : base(_base), def_val(d) {
79      memset(bounds, 0, sizeof(bounds));
80      //    for(int i=0; i<N; ++i) { bounds[i]=0; }
81    }
82
83    Val operator[](const KeyType& k) const {
84      return find(base[k]);
85    }
86
87    void set(const KeyType& k, Val n) {
88      // FIXME: range check?
89      size_t a = base[k];
90      if(a < bounds[N-1]) {
91        move(a, find(a), n);
92      }
93      else {
94        insert(k, n);
95      }
96    }
97
98    void insert(const KeyType& k, Val n) {
99      data.push_back(k);
100      base.set(k, move(bounds[N-1]++, N-1, n));
101    }
102
103    /// This func is not very usable, but necessary to implement
104    /// dynamic map behaviour.
105    void remove(const KeyType& k) {
106      size_t a = base[k];
107      if(a < bounds[N-1]) {
108        move(a, find(a), N);
109        data.pop_back();
110        base.set(k, -1);
111      }
112    }
113
114    iterator begin(Val n) const {
115      return data.begin() + (n ? bounds[n-1] : 0);
116    }
117
118    iterator end(Val n) const {
119      return data.begin() + bounds[n];
120    }
121
122    size_t size(Val n) const {
123      return bounds[n] - (n ? bounds[n-1] : 0);
124    }
125
126    size_t size() const {
127      // assert(bounds[N-1] == data.size());
128      return bounds[N-1];
129    }
130
131
132    /// For use as an iterator...
133    KeyType& first(KeyType &k, Val n) {
134      size_t i = (n ? bounds[n-1] : 0);
135      if( i < bounds[n] ) {
136        k = data[i];
137      }
138      else {
139        k = INVALID;
140      }
141      return k;
142    }
143
144    /// For use as an iterator...
145    KeyType& next(KeyType &k) {
146      size_t i = base[k];
147      uint8_t n = find(i);
148      ++i;
149      if( i < bounds[n] ) {
150        k = data[i];
151      }
152      else {
153        k = INVALID;
154      }
155      return k;
156    }
157
158  };
159
160
161
162
163  template<typename KeyIntMap>
164  class IterableBoolMap : public IterableMap<KeyIntMap, 2, bool> {
165    typedef IterableMap<KeyIntMap, 2, bool> Parent;
166
167  public:
168    IterableBoolMap(KeyIntMap &_base, bool d = false) : Parent(_base, d) {}
169  };
170
171}
172#endif
Note: See TracBrowser for help on using the repository browser.