flower/include/assoc.hh

   1 #ifndef ASSOC_HH
   2 #define ASSOC_HH
   3
   4 #include "array.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   TODO: a decent hash for strings.
  22  */
  23 template<class K, class V>
  24 struct Assoc {
  25   Array< Assoc_ent_<K,V> > arr;
  26
  27   /* ************** */
  28
  29   int find (K key) const {
  30     for (int i = 0; i < arr.size(); i++) {
  31       if (!arr[i].free && key == arr[i].key)
  32         return i;
  33     }
  34     return -1;
  35   }
  36   int find_creat (K key) {
  37     int free = -1;
  38     for (int i = 0; i < arr.size(); i++) {
  39       if (!arr[i].free && key == arr[i].key) {
  40         return i;
  41       } else if (arr[i].free) {
  42         free = i;
  43       }
  44     }
  45     if (free >= 0){
  46       arr[free].free = false;
  47       arr[free].key = key;
  48       return free;
  49     }
  50
  51     Assoc_ent_<K,V> ae;
  52     ae.free = false;
  53     ae.key = key;
  54     arr.push (ae);
  55     return arr.size() -1;
  56   }
  57 public:
  58   bool elt_b (K key) const {
  59     return find (key) >= 0;
  60   }
  61   void del (K key) {
  62     assert (elt_b (key));
  63     int i= find (key);
  64     arr[i].free = true;
  65   }
  66   void add (K key, V val) {
  67     int i = find_creat (key);
  68     arr[i].val = val;
  69   }
  70   V& elem (K key) {
  71     return arr[find_creat (key)].val;
  72   }
  73   V& operator[](K key) {
  74     return elem (key);
  75   }
  76   V const & operator[](K key) const {
  77     return elem (key);
  78   }
  79   V const & elem (K key) const {
  80     assert (elt_b (key));
  81     return arr[find (key)].val;
  82   }
  83   void clear ()
  84   {
  85     for (int i=0 ;  i < arr.size (); i++)
  86       arr[i].free = true;
  87   }
  88 };
  89
  90 #endif