close Warning: Can't use blame annotator: 
No changeset 422 in the repository

source: liacs/da/opdr2a/trie.cc@ 422

Last change on this file since 422 was 2, checked in by Rick van der Zwet, 15 years ago

Initial import of data of old repository ('data') worth keeping (e.g. tracking
means of URL access statistics)
File size: 8.6 KB
RevLine 
1/* Author : Rick van der Zwet
2 * S-number : 0433373
3 * Version : $Id: trie.cc 322 2007-11-22 14:09:00Z rick $
4 * Copyright : FreeBSD Licence
5 */
6
7#include "trie.h"
8
9#ifndef TRIE_CC
10#define TRIE_CC
11
12template <class InfoTp>
13TrieNode<InfoTp>::TrieNode()
14{
15 Value = '\0';
16 One = NULL;
17 Zero = NULL;
18 Parent = NULL;
19}
20
21
22
23template <class InfoTp>
24TrieNode<InfoTp>::~TrieNode()
25{
26 delete One;
27 delete Zero;
28}
29
30
31
32template <class InfoTp>
33Trie<InfoTp>::Trie ()
34{
35 Root = new TrieNode<InfoTp> ();
36 //Set window to root
37 GoRoot ();
38}
39
40
41
42template <class InfoTp>
43Trie<InfoTp>::~Trie ()
44{
45 delete Root;
46}
47
48
49
50template <class InfoTp>
51bool Trie<InfoTp>::AtLeaf ()
52{
53 if (Window->One == NULL and Window->Zero == NULL)
54 {
55 return(true);
56 }
57
58 // Got some extra nodes down below
59 return(false);
60}
61
62
63
64template <class InfoTp>
65void Trie<InfoTp>::GoChild (char K)
66{
67 // Call ExistsChild to check if node exists and deliver an pointer
68 // to the node in NodeFound
69 if ( ExistsChild(K) )
70 {
71 Window = NodeFound;
72 }
73}
74
75
76
77template <class InfoTp>
78void Trie<InfoTp>::GoRoot ()
79{
80 //set the current window on the Root pointer
81 Window = Root;
82}
83
84
85
86template <class InfoTp>
87bool Trie<InfoTp>::ExistsChild (char K)
88{
89 // worker with different knob, to make it able to get back
90 TrieNode<InfoTp> * Worker = Window;
91
92 int i;
93 for (i = 7; i >= 0; i--)
94 {
95 // bit i is 1 or not?
96 if (K & 1<<i)
97 {
98 // If node not exists, bail out
99 if (Worker->One == NULL)
100 {
101 return false;
102 }
103 else
104 {
105 Worker = Worker->One;
106 }
107 }
108 else
109 {
110 // If node not exists, bail out
111 if (Worker->Zero == NULL)
112 {
113 return false;
114 }
115 else
116 {
117 Worker = Worker->Zero;
118 }
119 }
120 }
121
122 // Store found window in NodeFound
123 NodeFound = Worker;
124 return true;
125}
126
127
128
129template <class InfoTp>
130char Trie<InfoTp>::FirstChild ()
131{
132 // worker with different knob, to make it able to get back
133 TrieNode<InfoTp> * Worker = Window;
134 // walk 8 bits, i indication of the bit currently are
135 int i;
136 // return value
137 char retval = 0;
138 for (i = 7; i >= 0; i--)
139 {
140 // go as many Zero if possible else go right if possible else return \0
141 if (Worker->Zero != NULL)
142 {
143 Worker = Worker->Zero;
144 }
145 else if (Worker->One != NULL)
146 {
147 //set bit i to 1
148 retval |= 1<<i;
149 Worker = Worker->One;
150 }
151 else
152 {
153 retval = '\0';
154 break;
155 }
156 }
157 return(retval);
158}
159
160
161
162/* This does not seems be very logical in the first place, but try to
163 * draw a picture and then follow the paths, just remind 2 things
164 * -no One 'turns' are allowed, cause those are higher order childs
165 * -the story ends if you hit the startnode from the right
166 * XXX: Only works well with one level depth, not multilevel depth
167 */
168template <class InfoTp>
169char Trie<InfoTp>::NextChild (char K)
170{
171 // store startnode
172 TrieNode<InfoTp> * Worker;
173 // tmp (loop) counter
174 int i;
175 // return value, not changed if not found
176 int retval = '\0';
177
178 // goto child node if it exists at least
179 if (ExistsChild(K)) {
180 Worker = NodeFound;
181
182 // depth counter
183 i = 0;
184 while ( true )
185 {
186 // ends if in startnode and came from right or
187 // in startnode en no left turn possible
188 if (Worker->Parent == Window)
189 {
190 if (Worker->Parent->One == Worker or
191 Worker->Parent->One == NULL)
192 {
193 return(retval);
194 }
195 }
196
197 //if from left and right available, go for it
198 if (Worker->Parent->Zero == Worker and
199 Worker->Parent->One != NULL)
200 {
201 Worker = Worker->Parent->One;
202
203 //walk to child leaf
204 while (i > 0)
205 {
206 //decrement counter, cause we are going inward again
207 i--;
208 // if left available take it, else right
209 if (Worker->Zero != NULL)
210 {
211 Worker = Worker->Zero;
212 }
213 else
214 {
215 Worker = Worker->One;
216 }
217 }
218
219 //calculate value NextChild
220 retval = 0;
221 for (i = 0; i <= 7; i++)
222 {
223 if (Worker->Parent->One == Worker)
224 {
225 retval |= 1<<i;
226 }
227 Worker = Worker->Parent;
228 }
229
230 //should never happen
231 if (Worker != Window)
232 {
233 perror("BUG: NextChild find value error");
234 exit(1);
235 }
236 return(retval);
237 }
238
239 //set new value Worker
240 Worker = Worker->Parent;
241 //raise counter
242 i++;
243 }
244 // end none found
245 return(retval);
246 }
247 // no valid leaf
248 return(retval);
249}
250
251
252
253template <class InfoTp>
254void Trie<InfoTp>::AddChild (char K)
255{
256 //get worker pointer
257 TrieNode<InfoTp> * Worker = Window;
258
259 int i;
260 for (i = 7; i >= 0; i--)
261 {
262 //bit i is 1 or not?
263 if (K & 1<<i)
264 {
265 // check is node exists, else create new one
266 if (Worker->One == NULL)
267 {
268 Worker->One = new TrieNode<InfoTp>();
269 }
270 Worker->One->Parent = Worker;
271 Worker = Worker->One;
272 }
273 else {
274 // check is node exists, else create new one
275 if (Worker->Zero == NULL)
276 {
277 Worker->Zero = new TrieNode<InfoTp>();
278 }
279 Worker->Zero->Parent = Worker;
280 Worker = Worker->Zero;
281 }
282 }
283}
284
285
286
287template <class InfoTp>
288void Trie<InfoTp>::RemoveChild (char K)
289{
290 TrieNode<InfoTp> * Worker;
291 int i; //loop counter
292 //check whether this knob exists
293 if ( ExistsChild(K) )
294 {
295 Worker = NodeFound;
296 //and is leaf
297 if (Worker->One == NULL and Worker->Zero == NULL)
298 {
299 //delete obsolete knob and null refering pointer
300 // walk 7 steps up and delete node if both pointers are zero
301 // first step is special cause the other could be a leaf as
302 // well
303
304
305 //goto parent
306 Worker = Worker->Parent;
307 //deleted leaf specified at NodeFound
308 if (Worker->One == NodeFound)
309 {
310 delete Worker->One;
311 Worker->One = NULL;
312 }
313 else
314 {
315 delete Worker->Zero;
316 Worker->Zero = NULL;
317 }
318
319 for (i = 0; i <= 6; i++)
320 {
321 // go one up
322 Worker = Worker->Parent;
323
324 //XXX: Only need to check the node we came from, instead
325 //of both
326
327 // Check wether we could delete arch 1
328 if (Worker->One != NULL)
329 {
330 //delete subnode if both pointers are NULL
331 if (Worker->One->One == NULL and
332 Worker->One->Zero == NULL)
333 {
334 delete Worker->One;
335 Worker->One = NULL;
336 }
337 }
338
339 // Check wether we could delete arch 0
340 if (Worker->Zero != NULL)
341 {
342 //delete subnode if both pointers are NULL
343 if (Worker->Zero->One == NULL and
344 Worker->Zero->Zero == NULL)
345 {
346 delete Worker->Zero;
347 Worker->Zero = NULL;
348 }
349 }
350 }
351
352 //Should never happen
353 if (Window != Worker)
354 {
355 perror("BUG: Pointer delete error");
356 exit(1);
357 }
358 }
359 }
360}
361
362
363
364template <class InfoTp>
365void Trie<InfoTp>::PutInfo (InfoTp I)
366{
367 Window->Value = I;
368}
369
370
371
372template <class InfoTp>
373InfoTp Trie<InfoTp>::GetInfo ()
374{
375 return(Window->Value);
376}
377
378
379
380template <class InfoTp>
381void Trie<InfoTp>::GotoNode(TrieNode<InfoTp> *Nd)
382{
383 Window = Nd;
384}
385
386
387
388template <class InfoTp>
389TrieNode<InfoTp> *Trie<InfoTp>::GetNode()
390{
391 return(Window);
392}
393
394#endif
Note: See TracBrowser for help on using the repository browser.