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;
108 Hash table with sliding sizes.
113 Fixed_size_dictionary<V> * fixed_p_;
115 /// set size to next prime, and copy contents
118 Fixed_size_dictionary<V> *f = new Fixed_size_dictionary<V> (fixed_p_->size_idx_ +1);
119 for (int i=0; i < fixed_p_->dict_arr_.size(); i++)
121 if (fixed_p_->dict_arr_[i].free_b_)
124 String nm (fixed_p_->dict_arr_[i].name_);
125 int nl = f->lookup (nm);
127 f->dict_arr_[nl] = Dict_entry<V> (nm, fixed_p_->dict_arr_[i].value_);
135 fixed_p_ = new Fixed_size_dictionary<V> (0);
141 void operator = (Dictionary<V> const &src)
147 fixed_p_ = new Fixed_size_dictionary<V> (*src.fixed_p_);
149 Dictionary (Dictionary<V> const &src)
151 fixed_p_ = new Fixed_size_dictionary<V> (*src.fixed_p_);
153 bool elem_b (String s) const
155 int l = fixed_p_->lookup (s);
157 return (l >= 0 && !fixed_p_->dict_arr_[l].free_b_) ;
161 Find and return element. If #s# is not in the table, create an entry in the table, and init
166 while ((l= fixed_p_->lookup (s)) <0)
172 fixed_p_->dict_arr_[l].free_b_ = false;
173 fixed_p_->dict_arr_[l].name_ = s;
174 return fixed_p_->dict_arr_[l].value_;
176 V& operator [] (String k)
181 V operator [] (String k) const
186 retval ((Dictionary<V> *) this)->elem (k);
191 return fixed_p_->remove (s);
193 friend class Dictionary_iter<V>;
197 #endif // DICTIONARY_HH