flower/assoc.hh

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