flower/assoc.hh

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