flower/assoc.hh

   1 #ifndef ASSOC_HH
   2 #define ASSOC_HH
   3
   4 #include "varray.hh"
   5 #include <assert.h>
   6
   7 /**
   8   A helper for Assoc
   9  */
  10 template<class K, class V>
  11 struct Assoc_ent_ {
  12     bool free;
  13     K key;
  14     V val;
  15 };
  16
  17
  18 /** mindblowingly stupid Associative array implementation.
  19   Hungarian: map
  20  */
  21 template<class K, class V>
  22 struct Assoc {
  23     Array< Assoc_ent_<K,V> > arr;
  24
  25     /* ************** */
  26
  27     int find(K key) const {
  28         for (int i = 0; i < arr.size(); i++) {
  29             if (!arr[i].free && key == arr[i].key)
  30                 return i;
  31         }
  32         return -1;
  33     }
  34     int find_creat(K key) {
  35         int free = -1;
  36         for (int i = 0; i < arr.size(); i++) {
  37             if (key == arr[i].key) {
  38                 return i;
  39             } else if (arr[i].free ) {
  40                 free = i;
  41             }
  42         }
  43         if (free >= 0){
  44             arr[free].free = false;
  45             arr[free].key = key;
  46             return free;
  47         }
  48
  49         Assoc_ent_<K,V> ae;
  50         ae.free = false;
  51         ae.key = key;
  52         arr.push(ae);
  53         return arr.size() -1;
  54     }
  55 public:
  56     bool elt_query(K key) const {
  57         return find(key) >= 0;
  58     }
  59     void del(K key) {
  60         assert(elt_query(key));
  61         int i= find(key);
  62         arr[i].free = true;
  63     }
  64     void
  65     add(K key, V val) {
  66         int i = find_creat(key);
  67         arr[i].val = val;
  68     }
  69     V& operator[](K key) {
  70         return arr[find_creat(key)].val;
  71     }
  72     const V& operator[](K key) const {
  73         assert(elt_query(key));
  74         return arr[find(key)].val;
  75     }
  76 };
  77
  78 #endif