src/work/klao/iter_map.h
author deba
Wed, 08 Sep 2004 12:06:45 +0000 (2004-09-08)
changeset 822 88226d9fe821
parent 367 825647d4eca7
child 921 818510fa3d99
permissions -rw-r--r--
The MapFactories have been removed from the code because
if we use macros then they increases only the complexity.

The pair iterators of the maps are separeted from the maps.

Some macros and comments has been changed.
     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 <hugo/invalid.h>
    14 
    15 namespace hugo {
    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