release: 1.0.17

[lilypond.git] / flower / include / dictionary.hh

diff --git a/flower/include/dictionary.hh b/flower/include/dictionary.hh
index b25fc84b49ac106368bb0d94eb288b66a4df993c..55f0e4fedd932edba9f1c4f320319860311b362f 100644 (file)
--- a/flower/include/dictionary.hh
+++ b/flower/include/dictionary.hh
@@ -11,28 +11,185 @@
 #define DICTIONARY_HH
 
 #include "string.hh"
-#include "assoc.hh"
+#include "array.hh"
+
+unsigned long prime_list (int idx);
+template<class V>
+struct Dict_entry
+{
+  String name_;
+  V value_;
+  bool free_b_;
+
+  Dict_entry() {
+    free_b_ = true;
+  }
+  Dict_entry (String s, V v)
+    {
+      name_ = s;
+      value_ = v;
+      free_b_ = false;
+    }
+};
+
+unsigned int hash (String);
 
 /**
-  UGH:  write a String_hash template, 
+   A hash table of prime size.
 
-  SEE:
-  
-       #include <search.h>
+   We use quadratic probing.  
+ */
+template<class V>
+class Fixed_size_dictionary
+{
+public:
+  Array<Dict_entry<V> > dict_arr_; 
+  int size_idx_;
+  Fixed_size_dictionary (int size_idx)
+    {
+      size_idx_ = size_idx;
+      int sz = prime_list(size_idx_);
+      dict_arr_.set_size (sz);
+    }
+
+  /// find #s#, or find first empty entry corresponding to #s#
+  int lookup  (String s)
+    {
+      int sz =dict_arr_.size ();
+      int i = hash (s) % sz;
+      int j = 0;
+      while (j <= sz/2) {
+       if (dict_arr_[i].free_b_)
+         return i;
+           
+       if (dict_arr_[i].name_ == s)
+         return i;
 
-       ENTRY *hsearch(ENTRY item, ACTION action);
+       j++;
+       i = (i + j*j) % sz;
+      }
 
-       int     hcreate (unsigned nel);
+      return -1;
+    }
 
-       void    hdestroy (void);
+  /// remove #s# from the hash table.  
+  V remove (String s)
+    {
+      assert (false);          // Untested routine.
+      int sz =dict_arr_.size ();
+      int i = hash (s) % sz;
+      int j = 0;
+      V retval;
+      while (j <= sz/2 && dict_arr_[i].name_ != s)
+       {
+         assert (!dict_arr_[i].free_b_);
+           
+       
+         j ++;
+         i = (i + j*j) % sz;
+       }
 
-  (should be frobnified to allow multiple hashes)
+      j++;
+      int nexti = (i + j*j) % sz;
+
+      while (j <= sz/2 && !dict_arr_[i].free_b_)
+       {
+         dict_arr_[i] = dict_arr_[nexti];
+         j++;
+         i = nexti;
+         nexti = (nexti + j*j)%sz;
+       }
+      
+    finish:
+      return retval;
+    }
+};
+
+/**
+   Hash table with sliding sizes. 
  */
-template<class T>
-class Dictionary : public Assoc<String, T>
+template<class V>
+class Dictionary
 {
+  Fixed_size_dictionary<V> * fixed_p_;
+
+  /// set size to next prime, and copy contents
+  void enlarge ()
+    {
+      Fixed_size_dictionary<V> *f = new Fixed_size_dictionary<V> (fixed_p_->size_idx_ +1);
+      for (int i=0; i < fixed_p_->dict_arr_.size(); i++)
+       {
+         if (fixed_p_->dict_arr_[i].free_b_)
+           continue;
+
+         String nm (fixed_p_->dict_arr_[i].name_);
+         int nl = f->lookup (nm);
+         
+         f->dict_arr_[nl] = Dict_entry<V> (nm, fixed_p_->dict_arr_[i].value_);
+       }
+      delete fixed_p_;
+      fixed_p_ = f;
+    }
 public:
-  
+  Dictionary ()
+    {
+      fixed_p_ = new Fixed_size_dictionary<V> (0);
+    }
+  ~Dictionary ()
+    {
+      delete fixed_p_;
+    }
+  void operator = (Dictionary<V> const &src)
+    {
+      if (&src == this)
+       return;
+      
+      delete fixed_p_;
+      fixed_p_ = new Fixed_size_dictionary<V> (*src.fixed_p_);
+    }
+  Dictionary (Dictionary<V> const &src)
+    {
+      fixed_p_ = new Fixed_size_dictionary<V> (*src.fixed_p_);
+    }
+  bool elem_b (String s) const
+    {
+      int l =  fixed_p_->lookup (s);
+
+      return (l >= 0 && !fixed_p_->dict_arr_[l].free_b_) ;
+    }
+
+  /**
+     Find and return element.  If #s# is not in the table, create an entry in the table, and init
+   */
+  V& elem (String s)
+    {
+      int l;
+      while ((l= fixed_p_->lookup (s)) <0)
+       {
+         enlarge ();
+       }
+
+      
+       fixed_p_->dict_arr_[l].free_b_ = false;
+       fixed_p_->dict_arr_[l].name_ = s;
+       return fixed_p_->dict_arr_[l].value_;
+    }
+  V& operator [] (String k)
+    {
+      return elem (k);
+    }
+
+  V operator [] (String k) const
+    {
+      return elem (k);
+    }
+
+  V remove (String s)
+    {
+      return fixed_p_->remove (s);      
+    }
+  friend class Dictionary_iter<V>;
 };
 
+
 #endif // DICTIONARY_HH