COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/klao/iter_map.h @ 366:be6fe0ea99b5

Last change on this file since 366:be6fe0ea99b5 was 365:9ca84022df34, checked in by Mihaly Barasz, 21 years ago

Masikfele iteralas, Node-hoz alkalmazkodva...

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