1 /*
2 This is dictionary.cpp
3
4 Coxeter version 3.0 Copyright (C) 2002 Fokko du Cloux
5 See file main.cpp for full copyright notice
6 */
7
8 /****************************************************************************
9
10 This module contains an implementation of dictionaries. For us, a dictionary
11 is a search structure (in practice, a tree) recognizing strings. The
12 operations which are allowed are inserting and deleting a string, and
13 searching for a given string. The return value is a pointer; this allows us
14 to have a unique typesize.
15
16 ****************************************************************************/
17
18 /****************************************************************************
19
20 Chapter I -- The Dictionary class.
21
22 ****************************************************************************/
23
24 namespace dictionary {
25
Dictionary()26 template <class T> Dictionary<T>::Dictionary()
27
28 /*
29 Default constructor for the Dictionary class. A dictionary is always
30 created with a root cell, corresponding to the empty string "".
31 */
32
33 {
34 d_root = new DictCell<T>(0,0,true,false);
35 }
36
~Dictionary()37 template <class T> Dictionary<T>::~Dictionary()
38
39 /*
40 Destructor for the Dictionary class. The destructor has to run through
41 the cells, and destroy each of them.
42 */
43
44 {
45 delete d_root;
46 }
47
findCell(const String & str) const48 template <class T> DictCell<T>* Dictionary<T>::findCell(const String& str)
49 const
50
51 /*
52 Searches for a value in the dictionary. Returns NULL in case of failure.
53
54 NOTE : in fact, recognizes if str is a *prefix* of a word in the dictionary.
55 It is up to the client to decide what to do about incomplete words (return
56 a special value, for instance.) It is not possible to restrict to leaves
57 because in practice embedded dictionary words will be common.
58 */
59
60 {
61 DictCell<T> *cell = d_root;
62
63 for (Ulong j = 0; str[j]; ++j)
64 {
65 if (cell->left == 0) /* leaf reached */
66 return 0;
67 cell = cell->left;
68 char c = str[j];
69 while ((cell->right) && (c > cell->letter))
70 cell = cell->right;
71 if (c != cell->letter)
72 return 0;
73 }
74
75 return cell;
76 }
77
find(const String & str) const78 template <class T> T* Dictionary<T>::find(const String& str) const
79
80 {
81 DictCell<T>* dc = findCell(str);
82
83 if (dc)
84 return dc->value();
85 else
86 return 0;
87 }
88
insert(const String & str,T * const value)89 template <class T> void Dictionary<T>::insert(const String& str,
90 T* const value)
91
92 /*
93 Inserts a new word in the dictionary. The root of the tree always
94 corresponds to the empty string "" (which may or may not be considered
95 to be in the dictionary.) The nodes are classified in three types :
96 dictionary words, unique prefixes (i.e., strings which are prefixes
97 to a unique dictionary word) and non-unique prefixes.
98 */
99
100 {
101 DictCell<T>* cell = findCell(str);
102
103 if (cell && cell->fullname) { /* word was already in the dictionary */
104 cell->ptr = value;
105 return;
106 }
107
108 /* from now on we are sure that the word is not already in the
109 dictionary */
110
111 cell = d_root;
112
113 for (Ulong j = 0; str[j]; ++j)
114 {
115 if (cell->left == 0) { /* leaf reached */
116 if (str[j+1]) /* add non-leaf */
117 cell->left = new DictCell<T>(str[j],0,false,true);
118 else /* add leaf */
119 cell->left = new DictCell<T>(str[j],value,true,false);
120 cell = cell->left;
121 continue;
122 }
123
124 /* if we reach this point we are at a non-leaf */
125
126 if (str[j] < cell->left->letter) { /* insert at
127 beginning */
128 if (str[j+1]) /* add non-leaf */
129 cell->left = new DictCell<T>(str[j],0,false,true,0,cell->left);
130 else /* add leaf */
131 cell->left = new DictCell<T>(str[j],value,true,false,0,cell->left);
132 cell = cell->left;
133 continue;
134 }
135 cell = cell->left;
136 while (cell->right && (cell->right->letter <= str[j]))
137 cell = cell->right;
138 if (cell->letter < str[j]) { /* add new cell */
139 if (str[j+1]) /* add non-leaf */
140 cell->right = new DictCell<T>(str[j],0,false,true,0,cell->right);
141 else /* add leaf */
142 cell->right = new DictCell<T>(str[j],value,true,false,0,cell->right);
143 cell = cell->right;
144 continue;
145 }
146
147 /* if we reach this point cell->letter = str[j] */
148
149 cell->uniquePrefix = false;
150 if (str[j+1] == 0) { /* word is complete */
151 cell->fullname = true;
152 cell->ptr = value;
153 }
154 }
155 }
156
remove(const String & str)157 template <class T> void Dictionary<T>::remove(const String& str)
158
159 /*
160 Not implemented.
161 */
162
163 {}
164
165 };
166
167
168 /****************************************************************************
169
170 Chapter II -- The DictCell class.
171
172 ****************************************************************************/
173
174 namespace dictionary {
175
~DictCell()176 template <class T> DictCell<T>::~DictCell()
177
178 /*
179 This destructor will recursively remove the dictionary. It is assumed
180 that the dictionary owns its data.
181 */
182
183 {
184 delete left;
185 delete right;
186 delete ptr;
187 }
188
189 /*
190 template <class T> void DictCell<T>::operator delete(void* ptr, size_t size)
191
192 {
193 arena().free(ptr,size);
194 }
195 */
196
197 };
198
199 /****** Auxiliary functions ************************************************/
200
201 namespace dictionary {
202
203 template <class T>
printExtensions(FILE * file,DictCell<T> * cell,String & name,bool & first,const char * sep)204 void printExtensions(FILE* file, DictCell<T>* cell, String& name,
205 bool &first, const char* sep)
206
207 /*
208 This function prints all the possible extensions of the prefix corresponding
209 to str on stdout. It is an auxiliary to the interactive treatment of
210 ambiguities. It is assumed that name contains the name of the parent of the
211 string.
212 */
213
214 {
215 if (cell == 0)
216 return;
217 append(name,cell->letter);
218 if (cell->fullname) { /* print */
219 if (first) /* first time a name is found */
220 first = false;
221 else
222 fprintf(file,"%s",sep);
223 fprintf(file,"%s",name.ptr());
224 }
225 printExtensions(file,cell->left,name,first,sep);
226 erase(name,1);
227 printExtensions(file,cell->right,name,first,sep);
228 }
229
230 };
231