COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/klao/iter_map.h @ 362:6c2e8a1f380a

Last change on this file since 362:6c2e8a1f380a was 362:6c2e8a1f380a, checked in by Mihaly Barasz, 17 years ago

IterableMap?: no range checking, no warning :)

File size: 2.4 KB
Line 
1// -*- c++ -*- //
2
3#ifndef HUGO_ITER_MAP
4#define HUGO_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
14namespace hugo {
15
16
17  /// \todo Decide whether we need all the range checkings!!!
18
19  template<typename KeyIntMap, uint8_t N, typename Val = uint8_t>
20  class IterableMap {
21  public:
22
23    typedef typename KeyIntMap::KeyType KeyType;
24    typedef Val ValueType;
25
26    typedef typename std::vector<KeyType>::const_iterator iterator;
27
28  protected:
29    KeyIntMap &base;
30    std::vector<KeyType> data;
31    size_t bounds[N];
32    Val def_val;
33
34    Val find(size_t a) const {
35      for(uint8_t n=0; n<N; ++n) {
36        if(bounds[n] > a)
37          return n;
38      }
39      return def_val;
40    }
41
42    void half_swap(size_t &a, size_t b) {
43      if(a != b) {
44        base.set(data[b],a);
45        data[a] = data[b];
46        a = b;
47      }
48    }
49
50    size_t move(size_t a, uint8_t m, uint8_t n) {
51      if(m != n) {
52        size_t orig_a = a;
53        KeyType orig_key = data[a];
54        while(m > n) {
55          --m;
56          half_swap(a, bounds[m]++);
57        }
58        // FIXME: range check ide?
59        while(m < n) {
60          half_swap(a, --bounds[m]);
61          ++m;
62        }
63        if(a != orig_a) {
64          base.set(orig_key, a);
65          data[a]=orig_key;
66        }
67      }
68      return a;
69    }
70
71  public:
72   
73    IterableMap(KeyIntMap &_base, Val d = N+1) : base(_base), def_val(d) {
74      memset(bounds, 0, sizeof(bounds));
75      //    for(int i=0; i<N; ++i) { bounds[i]=0; }
76    }
77
78    Val operator[](const KeyType& k) const {
79      return find(base[k]);
80    }
81
82    void set(const KeyType& k, Val n) {
83      // FIXME: range check?
84      size_t a = base[k];
85      if(a < bounds[N-1]) {
86        base.set(k, move(a, find(a), n));
87      }
88      else {
89        insert(k, n);
90      }
91    }
92
93    void insert(const KeyType& k, Val n) {
94      data.push_back(k);
95      base.set(k, move(bounds[N-1]++, N-1, n));
96    }
97
98    iterator begin(Val n) const {
99      return data.begin() + (n ? bounds[n-1] : 0);
100    }
101
102    iterator end(Val n) const {
103      return data.begin() + bounds[n];
104    }
105
106    size_t size(Val n) const {
107      return bounds[n] - (n ? bounds[n-1] : 0);
108    }
109   
110    size_t size() const {
111      // assert(bounds[N-1] == data.size());
112      return bounds[N-1];
113    }
114
115  };
116
117
118
119
120  template<typename KeyIntMap>
121  class IterableBoolMap : public IterableMap<KeyIntMap, 2, bool> {
122    typedef IterableMap<KeyIntMap, 2, bool> Parent;
123
124  public:
125    IterableBoolMap(KeyIntMap &_base, bool d = false) : Parent(_base, d) {}
126  };
127
128}
129#endif
Note: See TracBrowser for help on using the repository browser.