COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/klao/iter_map.h @ 361:ab0899df30d2

Last change on this file since 361:ab0899df30d2 was 361:ab0899df30d2, checked in by Mihaly Barasz, 17 years ago

IterableMap? with template ValueType?. IterableBoolMap? as a specialization.
Range checking warnings...

File size: 2.5 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        while(m < n) {
59          half_swap(a, --bounds[m]);
60          ++m;
61        }
62        if(a != orig_a) {
63          base.set(orig_key, a);
64          data[a]=orig_key;
65        }
66      }
67      return a;
68    }
69
70  public:
71   
72    IterableMap(KeyIntMap &_base, Val d = N+1) : base(_base), def_val(d) {
73      memset(bounds, 0, sizeof(bounds));
74      //    for(int i=0; i<N; ++i) { bounds[i]=0; }
75    }
76
77    Val operator[](const KeyType& k) const {
78      return find(base[k]);
79    }
80
81    void set(const KeyType& k, Val n) {
82      // FIXME: n < N ???
83      size_t a = base[k];
84      if(a < bounds[N-1] && n < N) {
85        base.set(k, move(a, find(a), n));
86      }
87    }
88
89    void insert(const KeyType& k, Val n) {
90      if(n < N) {
91        data.push_back(k);
92        base.set(k, move(bounds[N-1]++, N-1, n));
93      }
94    }
95
96    iterator begin(Val n) const {
97      if(n < N)
98        return data.begin() + (n ? bounds[n-1] : 0);
99      else
100        return data.end();
101    }
102
103    iterator end(Val n) const {
104      if(n < N)
105        return data.begin() + bounds[n];
106      else
107        return data.end();
108    }
109
110    size_t size(Val n) const {
111      if(n < N)
112        return bounds[n] - (n ? bounds[n-1] : 0);
113      else
114        return 0;
115    }
116   
117    size_t size() const {
118      // assert(bounds[N-1] == data.size());
119      return bounds[N-1];
120    }
121
122  };
123
124
125
126
127  template<typename KeyIntMap>
128  class IterableBoolMap : public IterableMap<KeyIntMap, 2, bool> {
129    typedef IterableMap<KeyIntMap, 2, bool> Parent;
130
131  public:
132    IterableBoolMap(KeyIntMap &_base, bool d = false) : Parent(_base, d) {}
133  };
134
135}
136#endif
Note: See TracBrowser for help on using the repository browser.