2 dictionary.hh -- declare Dictionary
4 source file of the Flower Library
6 (c) 1997--1998 Han-Wen Nienhuys <hanwen@cs.uu.nl>
16 unsigned long prime_list (int idx);
27 Dict_entry (String s, V v)
35 unsigned int hash (String);
38 A hash table of prime size.
40 We use quadratic probing.
43 class Fixed_size_dictionary
46 Array<Dict_entry<V> > dict_arr_;
48 Fixed_size_dictionary (int size_idx)
51 int sz = prime_list(size_idx_);
52 dict_arr_.set_size (sz);
55 /// find #s#, or find first empty entry corresponding to #s#
58 int sz =dict_arr_.size ();
59 int i = hash (s) % sz;
62 if (dict_arr_[i].free_b_)
65 if (dict_arr_[i].name_ == s)
75 /// remove #s# from the hash table.
78 assert (false); // Untested routine.
79 int sz =dict_arr_.size ();
80 int i = hash (s) % sz;
83 while (j <= sz/2 && dict_arr_[i].name_ != s)
85 assert (!dict_arr_[i].free_b_);
93 int nexti = (i + j*j) % sz;
95 while (j <= sz/2 && !dict_arr_[i].free_b_)
97 dict_arr_[i] = dict_arr_[nexti];
100 nexti = (nexti + j*j)%sz;
109 Hash table with sliding sizes.
114 Fixed_size_dictionary<V> * fixed_p_;
116 /// set size to next prime, and copy contents
119 Fixed_size_dictionary<V> *f = new Fixed_size_dictionary<V> (fixed_p_->size_idx_ +1);
120 for (int i=0; i < fixed_p_->dict_arr_.size(); i++)
122 if (fixed_p_->dict_arr_[i].free_b_)
125 String nm (fixed_p_->dict_arr_[i].name_);
126 int nl = f->lookup (nm);
128 f->dict_arr_[nl] = Dict_entry<V> (nm, fixed_p_->dict_arr_[i].value_);
136 fixed_p_ = new Fixed_size_dictionary<V> (0);
142 void operator = (Dictionary<V> const &src)
148 fixed_p_ = new Fixed_size_dictionary<V> (*src.fixed_p_);
150 Dictionary (Dictionary<V> const &src)
152 fixed_p_ = new Fixed_size_dictionary<V> (*src.fixed_p_);
154 bool elem_b (String s) const
156 int l = fixed_p_->lookup (s);
158 return (l >= 0 && !fixed_p_->dict_arr_[l].free_b_) ;
162 Find and return element. If #s# is not in the table, create an entry in the table, and init
167 while ((l= fixed_p_->lookup (s)) <0)
173 fixed_p_->dict_arr_[l].free_b_ = false;
174 fixed_p_->dict_arr_[l].name_ = s;
175 return fixed_p_->dict_arr_[l].value_;
177 V& operator [] (String k)
182 V operator [] (String k) const
189 return fixed_p_->remove (s);
191 friend class Dictionary_iter<V>;
195 #endif // DICTIONARY_HH