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