#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