COIN-OR::LEMON - Graph Library

source: lemon-0.x/src/work/klao/iter_map.h @ 358:caf183989ec4

Last change on this file since 358:caf183989ec4 was 347:e4ab32225f1c, checked in by Mihaly Barasz, 17 years ago

A generic map with value type [0, N) where N is a small integer.
Can enumerate keys with a given value.

File size: 2.1 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>
20  class IterableMap {
21  public:
22
23    typedef typename KeyIntMap::KeyType KeyType;
24    typedef uint8_t 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
33    uint8_t find(size_t a) const {
34      uint8_t n=0;
35      for(; n<N && bounds[n]<=a; ++n);
36      return n;
37    }
38
39    void half_swap(size_t &a, size_t b) {
40      if(a != b) {
41        base.set(data[b],a);
42        data[a] = data[b];
43        a = b;
44      }
45    }
46
47    size_t move(size_t a, uint8_t m, uint8_t n) {
48      if(m != n) {
49        size_t orig_a = a;
50        KeyType orig_key = data[a];
51        while(m > n) {
52          --m;
53          half_swap(a, bounds[m]++);
54        }
55        while(m < n) {
56          half_swap(a, --bounds[m]);
57          ++m;
58        }
59        if(a != orig_a) {
60          base.set(orig_key, a);
61          data[a]=orig_key;
62        }
63      }
64      return a;
65    }
66
67  public:
68   
69    IterableMap(KeyIntMap &_base) : base(_base) {
70      memset(bounds, 0, sizeof(bounds));
71      //    for(int i=0; i<N; ++i) { bounds[i]=0; }
72    }
73
74    uint8_t operator[](const KeyType& k) const {
75      return find(base[k]);
76    }
77
78    void set(const KeyType& k, uint8_t n) {
79      size_t a = base[k];
80      if(a < bounds[N-1]) {
81        base.set(k, move(a, find(a), n));
82      }
83    }
84
85    void insert(const KeyType& k, uint8_t n) {
86      if(n<N) {
87        data.push_back(k);
88        base.set(k, move(bounds[N-1]++, N-1, n));
89      }
90    }
91
92    iterator begin(uint8_t n) const {
93      if(n < N)
94        return data.begin() + (n ? bounds[n-1] : 0);
95      else
96        return data.end();
97    }
98
99    iterator end(uint8_t n) const {
100      if(n < N)
101        return data.begin() + bounds[n];
102      else
103        return data.end();
104    }
105
106    size_t size(uint8_t n) const {
107      if(n < N)
108        return bounds[n] - (n ? bounds[n-1] : 0);
109      else
110        return 0;
111    }
112   
113    size_t size() const {
114      // assert(bounds[N-1] == data.size());
115      return bounds[N-1];
116    }
117
118  };
119
120}
121#endif
Note: See TracBrowser for help on using the repository browser.