]>
Commit | Line | Data |
---|---|---|
1eee94d3 GM |
1 | (* SymbolKey.mod binary tree operations for storing symbols. |
2 | ||
3 | Copyright (C) 2001-2022 Free Software Foundation, Inc. | |
4 | Contributed by Gaius Mulley <gaius.mulley@southwales.ac.uk>. | |
5 | ||
6 | This file is part of GNU Modula-2. | |
7 | ||
8 | GNU Modula-2 is free software; you can redistribute it and/or modify | |
9 | it under the terms of the GNU General Public License as published by | |
10 | the Free Software Foundation; either version 3, or (at your option) | |
11 | any later version. | |
12 | ||
13 | GNU Modula-2 is distributed in the hope that it will be useful, but | |
14 | WITHOUT ANY WARRANTY; without even the implied warranty of | |
15 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
16 | General Public License for more details. | |
17 | ||
18 | You should have received a copy of the GNU General Public License | |
19 | along with GNU Modula-2; see the file COPYING3. If not see | |
20 | <http://www.gnu.org/licenses/>. *) | |
21 | ||
22 | IMPLEMENTATION MODULE SymbolKey ; | |
23 | ||
24 | ||
25 | FROM Storage IMPORT ALLOCATE, DEALLOCATE ; | |
26 | FROM StrIO IMPORT WriteString, WriteLn ; | |
27 | FROM NumberIO IMPORT WriteCard ; | |
28 | FROM NameKey IMPORT WriteKey ; | |
29 | FROM Assertion IMPORT Assert ; | |
30 | FROM Debug IMPORT Halt ; | |
31 | ||
32 | ||
33 | TYPE | |
34 | SymbolTree = POINTER TO Node ; | |
35 | Node = RECORD | |
36 | KeyName : Name ; (* The sorted entity *) | |
37 | KeySym : WORD ; (* The value entity *) | |
38 | Left : SymbolTree ; | |
39 | Right : SymbolTree ; | |
40 | END ; | |
41 | ||
42 | ||
43 | PROCEDURE InitTree (VAR t: SymbolTree) ; | |
44 | BEGIN | |
45 | NEW(t) ; | |
46 | WITH t^ DO | |
47 | Left := NIL ; | |
48 | Right := NIL | |
49 | END | |
50 | END InitTree ; | |
51 | ||
52 | ||
53 | (* | |
54 | we used to get problems compiling KillTree below - so it was split | |
55 | into the two procedures below. | |
56 | ||
57 | ||
58 | PROCEDURE KillTree (VAR t: SymbolTree) ; | |
59 | BEGIN | |
60 | IF t#NIL | |
61 | THEN | |
62 | Kill(t) ; (* Would like to place Kill in here but the compiler *) | |
63 | (* gives a type incompatible error... so i've split *) | |
64 | (* the procedure into two. - Problem i think with *) | |
65 | (* VAR t at the top? *) | |
66 | t := NIL | |
67 | END | |
68 | END KillTree ; | |
69 | ||
70 | ||
71 | PROCEDURE Kill (t: SymbolTree) ; | |
72 | BEGIN | |
73 | IF t#NIL | |
74 | THEN | |
75 | Kill(t^.Left) ; | |
76 | Kill(t^.Right) ; | |
77 | DISPOSE(t) | |
78 | END | |
79 | END Kill ; | |
80 | *) | |
81 | ||
82 | ||
83 | PROCEDURE KillTree (VAR t: SymbolTree) ; | |
84 | BEGIN | |
85 | IF t#NIL | |
86 | THEN | |
87 | KillTree(t^.Left) ; | |
88 | KillTree(t^.Right) ; | |
89 | DISPOSE(t) ; | |
90 | t := NIL | |
91 | END | |
92 | END KillTree ; | |
93 | ||
94 | ||
95 | (* | |
96 | ContainsSymKey - return TRUE if tree, t, contains an entry for, NameKey. | |
97 | *) | |
98 | ||
99 | PROCEDURE ContainsSymKey (t: SymbolTree; NameKey: Name) : BOOLEAN ; | |
100 | VAR | |
101 | father, | |
102 | child : SymbolTree ; | |
103 | BEGIN | |
104 | FindNodeParentInTree(t, NameKey, child, father) ; | |
105 | RETURN child#NIL | |
106 | END ContainsSymKey ; | |
107 | ||
108 | ||
109 | PROCEDURE GetSymKey (t: SymbolTree; NameKey: Name) : WORD ; | |
110 | VAR | |
111 | father, | |
112 | child : SymbolTree ; | |
113 | BEGIN | |
114 | FindNodeParentInTree(t, NameKey, child, father) ; | |
115 | IF child=NIL | |
116 | THEN | |
117 | RETURN NulKey | |
118 | ELSE | |
119 | RETURN child^.KeySym | |
120 | END | |
121 | END GetSymKey ; | |
122 | ||
123 | ||
124 | PROCEDURE PutSymKey (t: SymbolTree; NameKey: Name; SymKey: WORD) ; | |
125 | VAR | |
126 | father, | |
127 | child : SymbolTree ; | |
128 | BEGIN | |
129 | FindNodeParentInTree(t, NameKey, child, father) ; | |
130 | IF child=NIL | |
131 | THEN | |
132 | (* no child found, now is NameKey less than father or greater? *) | |
133 | IF father=t | |
134 | THEN | |
135 | (* empty tree, add it to the left branch of t *) | |
136 | NEW(child) ; | |
137 | father^.Left := child | |
138 | ELSE | |
139 | IF NameKey<father^.KeyName | |
140 | THEN | |
141 | NEW(child) ; | |
142 | father^.Left := child | |
143 | ELSIF NameKey>father^.KeyName | |
144 | THEN | |
145 | NEW(child) ; | |
146 | father^.Right := child | |
147 | END | |
148 | END ; | |
149 | WITH child^ DO | |
150 | Right := NIL ; | |
151 | Left := NIL ; | |
152 | KeySym := SymKey ; | |
153 | KeyName := NameKey | |
154 | END | |
155 | ELSE | |
156 | Halt('symbol already stored', __LINE__, __FILE__) | |
157 | END | |
158 | END PutSymKey ; | |
159 | ||
160 | ||
161 | (* | |
162 | DelSymKey - deletes an entry in the binary tree. | |
163 | ||
164 | NB in order for this to work we must ensure that the InitTree sets | |
165 | both Left and Right to NIL. | |
166 | *) | |
167 | ||
168 | PROCEDURE DelSymKey (t: SymbolTree; NameKey: Name) ; | |
169 | VAR | |
170 | i, child, father: SymbolTree ; | |
171 | BEGIN | |
172 | FindNodeParentInTree(t, NameKey, child, father) ; (* find father and child of the node *) | |
173 | IF (child#NIL) AND (child^.KeyName=NameKey) | |
174 | THEN | |
175 | (* Have found the node to be deleted *) | |
176 | IF father^.Right=child | |
177 | THEN | |
178 | (* Node is child and this is greater than the father. *) | |
179 | (* Greater being on the right. *) | |
180 | (* Connect child^.Left onto the father^.Right. *) | |
181 | (* Connect child^.Right onto the end of the right *) | |
182 | (* most branch of child^.Left. *) | |
183 | IF child^.Left#NIL | |
184 | THEN | |
185 | (* Scan for Right most node of child^.Left *) | |
186 | i := child^.Left ; | |
187 | WHILE i^.Right#NIL DO | |
188 | i := i^.Right | |
189 | END ; | |
190 | i^.Right := child^.Right ; | |
191 | father^.Right := child^.Left | |
192 | ELSE | |
193 | (* No child^.Left node therefore link over child *) | |
194 | (* (as in a single linked list) to child^.Right *) | |
195 | father^.Right := child^.Right | |
196 | END ; | |
197 | DISPOSE(child) | |
198 | ELSE | |
199 | (* Assert that father^.Left=child will always be true *) | |
200 | (* Perform exactly the mirror image of the above code *) | |
201 | ||
202 | (* Connect child^.Right onto the father^.Left. *) | |
203 | (* Connect child^.Left onto the end of the Left most *) | |
204 | (* branch of child^.Right *) | |
205 | IF child^.Right#NIL | |
206 | THEN | |
207 | (* Scan for Left most node of child^.Right *) | |
208 | i := child^.Right ; | |
209 | WHILE i^.Left#NIL DO | |
210 | i := i^.Left | |
211 | END ; | |
212 | i^.Left := child^.Left ; | |
213 | father^.Left := child^.Right | |
214 | ELSE | |
215 | (* No child^.Right node therefore link over c *) | |
216 | (* (as in a single linked list) to child^.Left. *) | |
217 | father^.Left := child^.Left | |
218 | END ; | |
219 | DISPOSE(child) | |
220 | END | |
221 | ELSE | |
222 | Halt('trying to delete a symbol that is not in the tree - the compiler never expects this to occur', | |
223 | __LINE__, __FILE__) | |
224 | END | |
225 | END DelSymKey ; | |
226 | ||
227 | ||
228 | (* | |
229 | FindNodeParentInTree - find a node, child, in a binary tree, t, with name equal to n. | |
230 | if an entry is found, parent is set to the node above child. | |
231 | *) | |
232 | ||
233 | PROCEDURE FindNodeParentInTree (t: SymbolTree; n: Name; | |
234 | VAR child, parent: SymbolTree) ; | |
235 | BEGIN | |
236 | (* remember to skip the sentinal value and assign parent and child *) | |
237 | parent := t ; | |
238 | IF t=NIL | |
239 | THEN | |
240 | Halt('parameter t should never be NIL', __LINE__, __FILE__) | |
241 | END ; | |
242 | Assert (t^.Right = NIL) ; | |
243 | child := t^.Left ; | |
244 | IF child#NIL | |
245 | THEN | |
246 | REPEAT | |
247 | IF n<child^.KeyName | |
248 | THEN | |
249 | parent := child ; | |
250 | child := child^.Left | |
251 | ELSIF n>child^.KeyName | |
252 | THEN | |
253 | parent := child ; | |
254 | child := child^.Right | |
255 | END | |
256 | UNTIL (child=NIL) OR (n=child^.KeyName) | |
257 | END | |
258 | END FindNodeParentInTree ; | |
259 | ||
260 | ||
261 | (* | |
262 | IsEmptyTree - returns true if SymbolTree, t, is empty. | |
263 | *) | |
264 | ||
265 | PROCEDURE IsEmptyTree (t: SymbolTree) : BOOLEAN ; | |
266 | BEGIN | |
267 | RETURN t^.Left = NIL | |
268 | END IsEmptyTree ; | |
269 | ||
270 | ||
271 | (* | |
272 | DoesTreeContainAny - returns true if SymbolTree, t, contains any | |
273 | symbols which in turn return true when procedure, | |
274 | P, is called with a symbol as its parameter. | |
275 | The SymbolTree root is empty apart from the field, | |
276 | Left, hence we need two procedures. | |
277 | *) | |
278 | ||
279 | PROCEDURE DoesTreeContainAny (t: SymbolTree; P: IsSymbol) : BOOLEAN ; | |
280 | BEGIN | |
281 | RETURN SearchForAny (t^.Left, P) | |
282 | END DoesTreeContainAny ; | |
283 | ||
284 | ||
285 | (* | |
286 | SearchForAny - performs the search required for DoesTreeContainAny. | |
287 | The root node always contains a nul data value, | |
288 | therefore we must skip over it. | |
289 | *) | |
290 | ||
291 | PROCEDURE SearchForAny (t: SymbolTree; P: IsSymbol) : BOOLEAN ; | |
292 | BEGIN | |
293 | IF t=NIL | |
294 | THEN | |
295 | RETURN FALSE | |
296 | ELSE | |
297 | RETURN( P (t^.KeySym) OR | |
298 | SearchForAny (t^.Left, P) OR | |
299 | SearchForAny(t^.Right, P) | |
300 | ) | |
301 | END | |
302 | END SearchForAny ; | |
303 | ||
304 | ||
305 | (* | |
306 | ForeachNodeDo - for each node in SymbolTree, t, a procedure, P, | |
307 | is called with the node symbol as its parameter. | |
308 | The tree root node only contains a legal Left pointer, | |
309 | therefore we need two procedures to examine this tree. | |
310 | *) | |
311 | ||
312 | PROCEDURE ForeachNodeDo (t: SymbolTree; P: PerformOperation) ; | |
313 | BEGIN | |
314 | SearchAndDo(t^.Left, P) | |
315 | END ForeachNodeDo ; | |
316 | ||
317 | ||
318 | (* | |
319 | SearchAndDo - searches all the nodes in SymbolTree, t, and | |
320 | calls procedure, P, with a node as its parameter. | |
321 | It traverse the tree in order. | |
322 | *) | |
323 | ||
324 | PROCEDURE SearchAndDo (t: SymbolTree; P: PerformOperation) ; | |
325 | BEGIN | |
326 | IF t#NIL | |
327 | THEN | |
328 | WITH t^ DO | |
329 | SearchAndDo(Right, P) ; | |
330 | P(KeySym) ; | |
331 | SearchAndDo(Left, P) | |
332 | END | |
333 | END | |
334 | END SearchAndDo ; | |
335 | ||
336 | ||
337 | (* | |
338 | CountNodes - wrapper for NoOfNodes. | |
339 | *) | |
340 | ||
341 | PROCEDURE CountNodes (t: SymbolTree; condition: IsSymbol; count: CARDINAL) : CARDINAL ; | |
342 | BEGIN | |
343 | IF t # NIL | |
344 | THEN | |
345 | WITH t^ DO | |
346 | IF condition (KeySym) | |
347 | THEN | |
348 | INC (count) | |
349 | END ; | |
350 | count := CountNodes (Left, condition, count) ; | |
351 | count := CountNodes (Right, condition, count) | |
352 | END | |
353 | END ; | |
354 | RETURN count | |
355 | END CountNodes ; | |
356 | ||
357 | ||
358 | (* | |
359 | NoOfNodes - returns the number of nodes in the tree t. | |
360 | *) | |
361 | ||
362 | PROCEDURE NoOfNodes (t: SymbolTree; condition: IsSymbol) : CARDINAL ; | |
363 | BEGIN | |
364 | RETURN CountNodes (t^.Left, condition, 0) | |
365 | END NoOfNodes ; | |
366 | ||
367 | ||
368 | (* | |
369 | SearchConditional - wrapper for ForeachNodeConditionDo. | |
370 | *) | |
371 | ||
372 | PROCEDURE SearchConditional (t: SymbolTree; condition: IsSymbol; P: PerformOperation) ; | |
373 | BEGIN | |
374 | IF t#NIL | |
375 | THEN | |
376 | WITH t^ DO | |
377 | SearchConditional (Right, condition, P) ; | |
378 | IF (KeySym # 0) AND condition (KeySym) | |
379 | THEN | |
380 | P (KeySym) | |
381 | END ; | |
382 | SearchConditional (Left, condition, P) | |
383 | END | |
384 | END | |
385 | END SearchConditional ; | |
386 | ||
387 | ||
388 | (* | |
389 | ForeachNodeConditionDo - traverse the tree t and for any node which satisfied | |
390 | condition call P. | |
391 | *) | |
392 | ||
393 | PROCEDURE ForeachNodeConditionDo (t: SymbolTree; | |
394 | condition: IsSymbol; | |
395 | P: PerformOperation) ; | |
396 | BEGIN | |
397 | IF t#NIL | |
398 | THEN | |
399 | WITH t^ DO | |
400 | Assert (Right = NIL) ; | |
401 | SearchConditional (Left, condition, P) | |
402 | END | |
403 | END | |
404 | END ForeachNodeConditionDo ; | |
405 | ||
406 | ||
407 | END SymbolKey. |