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);
17 template<class K, class V>
18 struct Hash_table_entry
27 Hash_table_entry (K s, V v)
35 unsigned int hash (String);
36 unsigned int hash (int);
39 struct Dict_initialiser
46 A hash table of prime size.
48 We use quadratic probing.
50 template<class K, class V>
51 class Fixed_size_hash_table
54 Array<Hash_table_entry<K,V> > dict_arr_;
56 Fixed_size_hash_table (int size_idx)
59 int sz = prime_list(size_idx_);
60 dict_arr_.set_size (sz);
63 /// find #s#, or find first empty entry corresponding to #s#
66 int sz =dict_arr_.size ();
67 int i = hash (s) % sz;
70 if (dict_arr_[i].free_b_)
73 if (dict_arr_[i].key_ == s)
83 /// remove #s# from the hash table.
86 assert (false); // Untested routine.
87 int sz =dict_arr_.size ();
88 int i = hash (s) % sz;
91 while (j <= sz/2 && dict_arr_[i].key_ != s)
93 assert (!dict_arr_[i].free_b_);
101 int nexti = (i + j*j) % sz;
103 while (j <= sz/2 && !dict_arr_[i].free_b_)
105 dict_arr_[i] = dict_arr_[nexti];
108 nexti = (nexti + j*j)%sz;
116 Hash table with sliding sizes.
118 template<class K, class V>
121 Fixed_size_hash_table<K,V> * fixed_p_;
123 /// set size to next prime, and copy contents
126 Fixed_size_hash_table<K,V> *f = new Fixed_size_hash_table<K,V> (fixed_p_->size_idx_ +1);
127 for (int i=0; i < fixed_p_->dict_arr_.size(); i++)
129 if (fixed_p_->dict_arr_[i].free_b_)
132 K nm (fixed_p_->dict_arr_[i].key_);
133 int nl = f->lookup (nm);
135 f->dict_arr_[nl] = Hash_table_entry<K,V> (nm, fixed_p_->dict_arr_[i].value_);
143 fixed_p_ = new Fixed_size_hash_table<K,V> (0);
149 void operator = (Hash_table<K,V> const &src)
155 fixed_p_ = new Fixed_size_hash_table<K,V> (*src.fixed_p_);
157 Hash_table (Hash_table<K,V> const &src)
159 fixed_p_ = new Fixed_size_hash_table<K,V> (*src.fixed_p_);
164 int i= fixed_p_->size_idx_;
166 fixed_p_ = new Fixed_size_hash_table<K,V> (i);
168 bool elem_b (K s) const
170 int l = fixed_p_->lookup (s);
172 return (l >= 0 && !fixed_p_->dict_arr_[l].free_b_) ;
176 Find and return element. If #s# is not in the table, create an entry in the table, and init
181 while ((l= fixed_p_->lookup (s)) <0)
187 fixed_p_->dict_arr_[l].free_b_ = false;
188 fixed_p_->dict_arr_[l].key_ = s;
189 return fixed_p_->dict_arr_[l].value_;
193 return const_elem (s);
195 V const_elem (K k) const
199 retval = ((Hash_table<K,V>*)this)->elem (k);
207 V operator [] (K k) const
209 return const_elem (k);
214 return fixed_p_->remove (s);
216 friend class Hash_table_iter<K,V>;
220 class Dictionary : public Hash_table<String, V>
225 Dictionary (Dict_initialiser<V> *p)
227 for (Dict_initialiser<V> *q = p; q->key_; q++)
228 elem (q->key_) = q->value_;
232 friend class Dictionary_iter<V>;
236 #endif // DICTIONARY_HH