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