1 /*
2 * AVL-trees for CLISP
3 * Bruno Haible 1993-2001, 2004, 2017
4 * Sam Steingold 2007
5 * German comments translated into English: Stefan Kain 2002
6 */
7 /*
8 Goal: Keep a set of elements sorted, where every now and then an
9 element is added or an element changes its sorting key.
10 */
11 /* ========================================================================
12 Specification:
13
14 Settings that have to be provided from the outside:
15 Identifier AVLID :
16 Identifier that identifies the incarnation of this package
17 Type AVL_ELEMENT :
18 Type of the elements that are entered into an AVL-tree.
19 Function AVL_EQUAL:
20 local bool AVL_EQUAL (AVL_ELEMENT element1, AVL_ELEMENT element2);
21 determines if two elements are considered equal.
22 It is not allowed to store two equal elements in an AVL-tree.
23 (I.e.m no element may be stored twice.)
24 Type AVL_KEY :
25 Type of the key, which is used to sort the AVL-tree.
26 Function AVL_KEYOF:
27 local AVL_KEY AVL_KEYOF (AVL_ELEMENT element);
28 returns the sorting-key of an element, that is located in a AVL-tree.
29 Type AVL_SIGNED_INT :
30 Signed integer type, wide enough for AVL_COMPARE-values.
31 (Usually `sintL'. `signean' is too short.)
32 Function AVL_COMPARE:
33 local AVL_SIGNED_INT AVL_COMPARE (AVL_KEY key1, AVL_KEY key2);
34 returns >0 if key1>key2, <0 if key1<key2, 0 if key1=key2.
35 NB: AVL_EQUAL(element1,element2) should imply
36 AVL_COMPARE(KEY_OF(element1),KEY_OF(element2)) = 0 ,
37 otherwise avl_member and avl_delete do not work!
38 Then include avl.c.
39 Then, your own struct-type NODE can be defined:
40 typedef struct NODE { ...; NODEDATA nodedata; ...; } NODE;
41 #define HAVE_NODE // just in order to indicate, that NODE was defined
42 Then include avl.c again.
43 If some of the macros NO_AVL_MEMBER, NO_AVL_INSERT[1], NO_AVL_DELETE[1],
44 NO_AVL_LEAST, NO_AVL_MOVE, NO_AVL_SORT are defined, some of the
45 corresponding functions will not be defined.
46 =========================================================================== */
47
48 #ifndef __AVL_D_
49 #define __AVL_D_
50
51 /* declarations: */
52
53 #ifndef ALLOC
54 #ifndef NO_AVL_INSERT
55 #define ALLOC(eltype,number) ((eltype*) malloc((uintL)sizeof(eltype) * (uintL)(number)))
56 #endif
57 #ifndef NO_AVL_DELETE
58 #define FREE(item) free(item)
59 #endif
60 #endif
61
62 #ifndef AVL
63 /* A kind of "AVL-Package" for identifiers of types and functions: */
64 #define AVL(incarnation,identifier) CONCAT4(avl_,incarnation,_,identifier)
65 #endif
66
67 #define NODE AVL(AVLID,node)
68 #define ELEMENT AVL_ELEMENT
69 #define EQUAL AVL_EQUAL
70 #define KEY AVL_KEY
71 #define KEYOF AVL_KEYOF
72 #define HEIGHT uintBWL
73 #define MAXHEIGHT 41
74 #define SIGNED_INT AVL_SIGNED_INT
75 #define COMPARE AVL_COMPARE
76
77 #define NODEDATA \
78 struct { \
79 struct NODE * left; /* left subtree */ \
80 struct NODE * right; /* right subtree */ \
81 HEIGHT height; /* 1+max(heightof(left),heightof(right)) */ \
82 ELEMENT value; /* element at the top of this tree */ \
83 }
84
85 #else
86
87 /* ------------------------------------------------------------------------ */
88 /* implementation: */
89
90 #ifndef HAVE_NODE
91 typedef struct NODE { NODEDATA nodedata; } NODE;
92 #endif
93
94 /* An AVL-tree is either empty or a NODE.
95 The empty tree has the height 0, a NODE has as height the maximum of the
96 heights of the two subtrees + 1. */
97 #define EMPTY ((NODE *) 0)
98 #define heightof(tree) ((tree)==EMPTY ? 0 : (tree)->nodedata.height)
99
100 /* Invariants of each AVL-tree:
101 1. the height of each NODE is correctly calculated as:
102 node.height = 1+max(heightof(node.left),heightof(node.right))
103 2. The heights of the subtrees of each NODE differ at most by 1:
104 | heightof(node.left) - heightof(node.right) | <= 1
105 3. For each NODE applies:
106 forall x in node.left : COMPARE(KEYOF(x.value),KEYOF(node.value)) <= 0,
107 forall x in node.right : COMPARE(KEYOF(x.value),KEYOF(node.value)) >= 0.
108 A AVL-tree of height h has at least F_(h+2) [Fibonacci-number] and
109 at most 2^h - 1 elements. So, h<=41 (because a tree of height h>=42 would
110 have at least F_44 elements, and because of sizeof(NODE) * F_44 > 2^32, this
111 does not fit into a 32-Bit-address space.)
112 That is why a uintB is big enough for holding HEIGHT. */
113
114 /* Determines if an element with a given key is in the tree. */
115 #ifndef NO_AVL_MEMBER0
AVL(AVLID,member0)116 local NODE* AVL(AVLID,member0) (KEY key, NODE * tree) {
117 while (1) {
118 if (tree == EMPTY)
119 return (NODE*)NULL;
120 var SIGNED_INT sign = COMPARE(key,KEYOF(tree->nodedata.value));
121 if (sign == 0) /* found? */
122 return tree;
123 if (sign < 0)
124 /* key < KEYOF(tree->nodedata.value) --> search in the left subtree: */
125 tree = tree->nodedata.left;
126 else
127 /* key > KEYOF(tree->nodedata.value) --> search in the right subtree: */
128 tree = tree->nodedata.right;
129 }
130 }
131 #endif
132
133 /* Determines, if a certain element is in the tree.
134 Requires that there are no two elements with the same key in the tree. */
135 #ifndef NO_AVL_MEMBER
AVL(AVLID,member)136 local NODE* AVL(AVLID,member) (ELEMENT element, NODE * tree) {
137 var KEY key = KEYOF(element);
138 while (1) {
139 if (tree == EMPTY)
140 return (NODE*)NULL;
141 var SIGNED_INT sign = COMPARE(key,KEYOF(tree->nodedata.value));
142 if (sign == 0) {
143 if (EQUAL(element,tree->nodedata.value)) /* found? */
144 return tree;
145 else
146 return (NODE*)NULL;
147 }
148 if (sign < 0)
149 /* key < KEYOF(tree->nodedata.value) --> search in the left subtree: */
150 tree = tree->nodedata.left;
151 else
152 /* key > KEYOF(tree->nodedata.value) --> search in the right subtree: */
153 tree = tree->nodedata.right;
154 }
155 }
156 #endif
157
158 /* Rebalances again: On insertion resp. deletion of an element
159 in a tree, the sequence nodes[0],...,nodes[k-1] of subtrees
160 (with nodes[i+1] = nodes[i] -> (left or right) for all i)
161 has to be rebalanced. As the root of a subtree might change
162 thereby, all nodes[i] may not be NODE*, but NODE** . */
AVL(AVLID,rebalance)163 local void AVL(AVLID,rebalance) (NODE** * nodeplaces_ptr, uintC count) {
164 dotimesC(count,count, {
165 var NODE** nodeplace = *--nodeplaces_ptr;
166 var NODE* node = *nodeplace; /* next subtree to be balanced */
167 var NODE* nodeleft = node->nodedata.left;
168 var NODE* noderight = node->nodedata.right;
169 var HEIGHT heightleft = heightof(nodeleft);
170 var HEIGHT heightright = heightof(noderight);
171 if (heightright + 1 < heightleft) {
172 /* subtree is heavier on the left side, rotate from left to right:
173
174 *
175 / \
176 n+2 n
177 */
178 var NODE* nodeleftleft = nodeleft->nodedata.left;
179 var NODE* nodeleftright = nodeleft->nodedata.right;
180 var HEIGHT heightleftright = heightof(nodeleftright);
181 if (heightof(nodeleftleft) >= heightleftright) {
182 /*
183 * n+2|n+3
184 / \ / \
185 n+2 n --> / n+1|n+2
186 / \ | / \
187 n+1 n|n+1 n+1 n|n+1 n
188 */
189 node->nodedata.left = nodeleftright; nodeleft->nodedata.right = node;
190 nodeleft->nodedata.height = 1 +
191 (node->nodedata.height = 1 + heightleftright);
192 *nodeplace = nodeleft;
193 } else {
194 /*
195 * n+2
196 / \ / \
197 n+2 n --> n+1 n+1
198 / \ / \ / \
199 n n+1 n L R n
200 / \
201 L R
202
203 */
204 nodeleft->nodedata.right = nodeleftright->nodedata.left;
205 node->nodedata.left = nodeleftright->nodedata.right;
206 nodeleftright->nodedata.left = nodeleft;
207 nodeleftright->nodedata.right = node;
208 nodeleft->nodedata.height = node->nodedata.height = heightleftright;
209 nodeleftright->nodedata.height = heightleft;
210 *nodeplace = nodeleftright;
211 }
212 } else if (heightleft + 1 < heightright) {
213 /* subtree is heavier on the right side, rotate from right to left:
214 (Analogous to above procedure, only swapped 'left' <--> 'right' .) */
215 var NODE* noderightright = noderight->nodedata.right;
216 var NODE* noderightleft = noderight->nodedata.left;
217 var HEIGHT heightrightleft = heightof(noderightleft);
218 if (heightof(noderightright) >= heightrightleft) {
219 node->nodedata.right = noderightleft; noderight->nodedata.left = node;
220 noderight->nodedata.height = 1 +
221 (node->nodedata.height = 1 + heightrightleft);
222 *nodeplace = noderight;
223 } else {
224 noderight->nodedata.left = noderightleft->nodedata.right;
225 node->nodedata.right = noderightleft->nodedata.left;
226 noderightleft->nodedata.right = noderight;
227 noderightleft->nodedata.left = node;
228 noderight->nodedata.height = node->nodedata.height = heightrightleft;
229 noderightleft->nodedata.height = heightright;
230 *nodeplace = noderightleft;
231 }
232 } else {
233 var HEIGHT height = /* new total height */
234 (heightleft<heightright ? heightright : heightleft) + 1;
235 /* total height of this subtree remains unchanged ->
236 the subtrees that contain this one are already balanced. */
237 if (height == node->nodedata.height)
238 break;
239 node->nodedata.height = height;
240 }
241 });
242 }
243
244 /* Inserts an element into the AVL-tree and returns the new AVL-tree. */
245 #ifndef NO_AVL_INSERT
AVL(AVLID,insert)246 local NODE* AVL(AVLID,insert) (ELEMENT value, NODE* tree) {
247 var KEY key = KEYOF(value);
248 var NODE** nodeplace = &tree;
249 var NODE** stack[MAXHEIGHT]; /* a little private-stack */
250 var uintC stack_count = 0; /* number of elements on the stack */
251 var NODE** * stack_ptr = &stack[0]; /* always = &stack[stack_count] */
252 while (1) {
253 var NODE* node = *nodeplace;
254 if (node == EMPTY)
255 break;
256 *stack_ptr++ = nodeplace; stack_count++;
257 if (COMPARE(key,KEYOF(node->nodedata.value)) < 0)
258 /* key < KEYOF(node->nodedata.value) --> insert in the left subtree: */
259 nodeplace = &node->nodedata.left;
260 else
261 /* key >= KEYOF(node->nodedata.value) --> insert in the right subtree: */
262 nodeplace = &node->nodedata.right;
263 }
264 var NODE* new_node = ALLOC(NODE,1);
265 new_node->nodedata.left = EMPTY;
266 new_node->nodedata.right = EMPTY;
267 new_node->nodedata.height = 1;
268 new_node->nodedata.value = value;
269 *nodeplace = new_node;
270 AVL(AVLID,rebalance)(stack_ptr,stack_count);
271 return tree;
272 }
273 #endif
274 /* Ditto, but without calling ALLOC: */
275 #ifndef NO_AVL_INSERT1
AVL(AVLID,insert1)276 local NODE* AVL(AVLID,insert1) (NODE* new_node, NODE* tree) {
277 var KEY key = KEYOF(new_node->nodedata.value);
278 var NODE** nodeplace = &tree;
279 var NODE** stack[MAXHEIGHT]; /* a little private-stack */
280 var uintC stack_count = 0; /* number of elements on the stack */
281 var NODE** * stack_ptr = &stack[0]; /* always = &stack[stack_count] */
282 while (1) {
283 var NODE* node = *nodeplace;
284 if (node == EMPTY)
285 break;
286 *stack_ptr++ = nodeplace; stack_count++;
287 if (COMPARE(key,KEYOF(node->nodedata.value)) < 0)
288 /* key < KEYOF(node->nodedata.value) --> insert in the left subtree: */
289 nodeplace = &node->nodedata.left;
290 else
291 /* key >= KEYOF(node->nodedata.value) --> insert in the right subtree: */
292 nodeplace = &node->nodedata.right;
293 }
294 new_node->nodedata.left = EMPTY;
295 new_node->nodedata.right = EMPTY;
296 new_node->nodedata.height = 1;
297 *nodeplace = new_node;
298 AVL(AVLID,rebalance)(stack_ptr,stack_count);
299 return tree;
300 }
301 #endif
302
303 /* Removes an element from the AVL-tree and returns a new AVL-tree.
304 Requires, that there are no two elements with the same key in the tree. */
305 #ifndef NO_AVL_DELETE
AVL(AVLID,delete)306 local NODE* AVL(AVLID,delete) (ELEMENT value, NODE* tree) {
307 var KEY key = KEYOF(value);
308 var NODE** nodeplace = &tree;
309 var NODE** stack[MAXHEIGHT]; /* a little private-stack */
310 var uintC stack_count = 0; /* number of elements on the stack */
311 var NODE** * stack_ptr = &stack[0]; /* always = &stack[stack_count] */
312 var NODE* node_to_delete;
313 while (1) {
314 var NODE* node = *nodeplace;
315 if (node == EMPTY)
316 goto done; /* element not found */
317 *stack_ptr++ = nodeplace; stack_count++;
318 var SIGNED_INT sign = COMPARE(key,KEYOF(node->nodedata.value));
319 if (sign == 0) {
320 if (EQUAL(value,node->nodedata.value)) { /* found? */
321 node_to_delete = node; break;
322 } else
323 goto done;
324 }
325 if (sign < 0)
326 /* key < KEYOF(node->nodedata.value) --> remove in left subtree: */
327 nodeplace = &node->nodedata.left;
328 else
329 /* key > KEYOF(node->nodedata.value) --> remove in right subtree: */
330 nodeplace = &node->nodedata.right;
331 }
332 var NODE** nodeplace_to_delete = nodeplace;
333 /* node_to_delete = *nodeplace_to_delete has to be removed. */
334 if (node_to_delete->nodedata.left == EMPTY) {
335 /* node_to_delete is replaced by node_to_delete->nodedata.right. */
336 *nodeplace_to_delete = node_to_delete->nodedata.right;
337 stack_ptr--; stack_count--; /* still no rebalance at *nodeplace_to_delete! */
338 } else {
339 /* node_to_delete is replaced by the element
340 of node_to_delete->nodedata.left that is situated rightmost. */
341 var NODE** * stack_ptr_to_delete = stack_ptr;
342 var NODE** nodeplace = &node_to_delete->nodedata.left;
343 var NODE* node;
344 while (1) {
345 node = *nodeplace;
346 if (node->nodedata.right == EMPTY)
347 break;
348 *stack_ptr++ = nodeplace; stack_count++;
349 nodeplace = &node->nodedata.right;
350 }
351 *nodeplace = node->nodedata.left;
352 /* node takes the position of node_to_delete: */
353 node->nodedata.left = node_to_delete->nodedata.left;
354 node->nodedata.right = node_to_delete->nodedata.right;
355 node->nodedata.height = node_to_delete->nodedata.height;
356 *nodeplace_to_delete = node; /* instead of node_to_delete */
357 /* the rebalance-stack (path from the root downwards) does not
358 contain node_to_delete anymore, but node: */
359 *stack_ptr_to_delete = &node->nodedata.left; /* instead of &node_to_delete->nodedata.left */
360 }
361 FREE(node_to_delete);
362 AVL(AVLID,rebalance)(stack_ptr,stack_count);
363 done:
364 return tree;
365 }
366 #endif
367
368 /* Removes an element from the AVL-tree and returns a new AVL-tree.
369 Without calling FREE. */
370 #ifndef NO_AVL_DELETE1
371 /* Determines, where the element node_to_delete (with Key key) is situated
372 in the tree. Stores the path at stack_ptr, and returns the new stack_ptr. */
AVL(AVLID,delete1find)373 local NODE** * AVL(AVLID,delete1find) (NODE* node_to_delete, KEY key,
374 NODE* tree, NODE** * stack_ptr) {
375 while (1) {
376 if (tree == EMPTY)
377 return (NODE***)NULL;
378 var SIGNED_INT sign = COMPARE(key,KEYOF(tree->nodedata.value));
379 if (sign == 0) {
380 /* key = KEYOF(tree->nodedata.value) --> search in both subtrees: */
381 if (tree == node_to_delete)
382 return stack_ptr;
383 *stack_ptr = &tree->nodedata.left;
384 { var NODE*** part = AVL(AVLID,delete1find)(node_to_delete,key,tree->nodedata.left,stack_ptr+1);
385 if (part)
386 return part;
387 }
388 *stack_ptr = &tree->nodedata.right;
389 { var NODE*** part = AVL(AVLID,delete1find)(node_to_delete,key,tree->nodedata.right,stack_ptr+1);
390 if (part)
391 return part;
392 }
393 return (NODE***)NULL;
394 }
395 if (sign < 0) {
396 /* key < KEYOF(tree->nodedata.value) --> search in the left subtree: */
397 *stack_ptr++ = &tree->nodedata.left; tree = tree->nodedata.left;
398 } else {
399 /* key > KEYOF(tree->nodedata.value) --> search in the right subtree */
400 *stack_ptr++ = &tree->nodedata.right; tree = tree->nodedata.right;
401 }
402 }
403 }
AVL(AVLID,delete1)404 local NODE* AVL(AVLID,delete1) (NODE* node_to_delete, NODE* tree) {
405 var KEY key = KEYOF(node_to_delete->nodedata.value);
406 var NODE** nodeplace = &tree;
407 var NODE** stack[MAXHEIGHT]; /* a little private-stack */
408 var uintC stack_count = 0; /* number of elements on the stack */
409 var NODE** * stack_ptr = &stack[0]; /* always = &stack[stack_count] */
410 while (1) {
411 var NODE* node = *nodeplace;
412 if (node == EMPTY)
413 goto done; /* element not found */
414 *stack_ptr++ = nodeplace; stack_count++;
415 var SIGNED_INT sign = COMPARE(key,KEYOF(node->nodedata.value));
416 if (sign == 0) {
417 var NODE** * new_stack_ptr =
418 AVL(AVLID,delete1find)(node_to_delete,key,node,stack_ptr);
419 if (new_stack_ptr) { /* or found somewhere in the tree at node? */
420 stack_count += (new_stack_ptr - stack_ptr);
421 stack_ptr = new_stack_ptr;
422 nodeplace = stack_ptr[-1];
423 break;
424 } else
425 goto done; /* not found */
426 }
427 if (sign < 0)
428 /* key < KEYOF(node->nodedata.value) --> remove in left subtree: */
429 nodeplace = &node->nodedata.left;
430 else
431 /* key > KEYOF(node->nodedata.value) --> remove in right subtree: */
432 nodeplace = &node->nodedata.right;
433 }
434 {
435 /* stack_ptr = &stack[stack_count], nodeplace = stack_ptr[-1], */
436 var NODE** nodeplace_to_delete = nodeplace;
437 /* node_to_delete = *nodeplace_to_delete has to be removed. */
438 if (node_to_delete->nodedata.left == EMPTY) {
439 /* node_to_delete is replaced by node_to_delete->nodedata.right. */
440 *nodeplace_to_delete = node_to_delete->nodedata.right;
441 stack_ptr--; stack_count--; /* still no rebalance at *nodeplace_to_delete! */
442 } else {
443 /* node_to_delete is replaced by the element
444 of node_to_delete->nodedata.left that is situated rightmost. */
445 var NODE** * stack_ptr_to_delete = stack_ptr;
446 var NODE** nodeplace = &node_to_delete->nodedata.left;
447 var NODE* node;
448 while (1) {
449 node = *nodeplace;
450 if (node->nodedata.right == EMPTY)
451 break;
452 *stack_ptr++ = nodeplace; stack_count++;
453 nodeplace = &node->nodedata.right;
454 }
455 *nodeplace = node->nodedata.left;
456 /* node takes the position of node_to_delete: */
457 node->nodedata.left = node_to_delete->nodedata.left;
458 node->nodedata.right = node_to_delete->nodedata.right;
459 node->nodedata.height = node_to_delete->nodedata.height;
460 *nodeplace_to_delete = node; /* instead of node_to_delete */
461 /* the rebalance-stack (path from the root downwards) does not
462 contain node_to_delete anymore, but node: */
463 *stack_ptr_to_delete = &node->nodedata.left; /* instead of &node_to_delete->nodedata.left */
464 }
465 }
466 AVL(AVLID,rebalance)(stack_ptr,stack_count);
467 done:
468 return tree;
469 }
470 #endif
471
472 /* Macros for traversing through an AVL-tree:
473 AVL_map(tree,node,statement);
474 A tree is traversed, binding a node at a time and executing the statement.
475 order of traversal:
476 AVL_map : in order L N R
477 N AVL_map_reverse : in reversed order R N L
478 / \ AVL_map_preorder : in prefix-order N L R
479 L R AVL_map_postorder : in postfix-order L R N */
480
481 typedef struct { NODE* node; bool rightp; } AVL(AVLID,mapstackitem);
482 typedef AVL(AVLID,mapstackitem) AVL(AVLID,mapstack)[MAXHEIGHT];
483 #define AVL_map(tree,nodevar,statement) \
484 { var NODE* nodevar = (tree); \
485 var AVL(AVLID,mapstack) stack; /* a little private-stack */ \
486 var uintC stack_count = 0; /* number of elements on the stack */ \
487 var AVL(AVLID,mapstackitem) * stack_ptr = &stack[0]; /* always = &stack[stack_count] */ \
488 GENTAG(down): /* descend recursively */ \
489 if (nodevar == EMPTY) goto GENTAG(up); \
490 stack_ptr->node = nodevar; \
491 stack_ptr->rightp = false; nodevar = nodevar->nodedata.left; \
492 stack_ptr++; stack_count++; \
493 goto GENTAG(down); \
494 GENTAG(up): /* climb up again */ \
495 if (stack_count == 0) goto GENTAG(end); \
496 stack_count--; stack_ptr--; \
497 if (stack_ptr->rightp) goto GENTAG(up); \
498 nodevar = stack_ptr->node; \
499 statement; \
500 stack_ptr->rightp = true; nodevar = nodevar->nodedata.right; \
501 stack_ptr++; stack_count++; \
502 goto GENTAG(down); \
503 GENTAG(end): ; /* finished */ \
504 }
505 #define AVL_map_reverse(tree,nodevar,statement) \
506 { var NODE* nodevar = (tree); \
507 var AVL(AVLID,mapstack) stack; /* a little private-stack */ \
508 var uintC stack_count = 0; /* number of elements on the stack */ \
509 var AVL(AVLID,mapstackitem) * stack_ptr = &stack[0]; /* always = &stack[stack_count] */ \
510 GENTAG(down): /* descend recursively */ \
511 if (nodevar == EMPTY) goto GENTAG(up); \
512 stack_ptr->node = nodevar; \
513 stack_ptr->rightp = true; nodevar = nodevar->nodedata.right; \
514 stack_ptr++; stack_count++; \
515 goto GENTAG(down); \
516 GENTAG(up): /* climb up again */ \
517 if (stack_count == 0) goto GENTAG(end); \
518 stack_count--; stack_ptr--; \
519 if (!(stack_ptr->rightp)) goto GENTAG(up); \
520 nodevar = stack_ptr->node; \
521 statement; \
522 stack_ptr->rightp = false; nodevar = nodevar->nodedata.left; \
523 stack_ptr++; stack_count++; \
524 goto GENTAG(down); \
525 GENTAG(end): ; /* finished */ \
526 }
527 #define AVL_map_preorder(tree,nodevar,statement) \
528 { var NODE* nodevar = (tree); \
529 var AVL(AVLID,mapstack) stack; /* a little private-stack */ \
530 var uintC stack_count = 0; /* number of elements on the stack */ \
531 var AVL(AVLID,mapstackitem) * stack_ptr = &stack[0]; /* always = &stack[stack_count] */ \
532 GENTAG(down): /* descend recursively */ \
533 if (nodevar == EMPTY) goto GENTAG(up); \
534 statement; \
535 stack_ptr->node = nodevar; \
536 stack_ptr->rightp = false; nodevar = nodevar->nodedata.left; \
537 stack_ptr++; stack_count++; \
538 goto GENTAG(down); \
539 GENTAG(up): /* climb up again */ \
540 if (stack_count == 0) goto GENTAG(end); \
541 stack_count--; stack_ptr--; \
542 if (stack_ptr->rightp) goto GENTAG(up); \
543 nodevar = stack_ptr->node; \
544 stack_ptr->rightp = true; nodevar = nodevar->nodedata.right; \
545 stack_ptr++; stack_count++; \
546 goto GENTAG(down); \
547 GENTAG(end): ; /* finished */ \
548 }
549 #define AVL_map_postorder(tree,nodevar,statement) \
550 { var NODE* nodevar = (tree); \
551 var AVL(AVLID,mapstack) stack; /* a little private-stack */ \
552 var uintC stack_count = 0; /* number of elements on the stack */ \
553 var AVL(AVLID,mapstackitem) * stack_ptr = &stack[0]; /* always = &stack[stack_count] */ \
554 GENTAG(down): /* descend recursively */ \
555 if (nodevar == EMPTY) goto GENTAG(up); \
556 stack_ptr->node = nodevar; \
557 stack_ptr->rightp = false; nodevar = nodevar->nodedata.left; \
558 stack_ptr++; stack_count++; \
559 goto GENTAG(down); \
560 GENTAG(up): /* climb up again */ \
561 if (stack_count == 0) goto GENTAG(end); \
562 stack_count--; stack_ptr--; \
563 nodevar = stack_ptr->node; \
564 if (stack_ptr->rightp) { statement; goto GENTAG(up); } \
565 stack_ptr->rightp = true; nodevar = nodevar->nodedata.right; \
566 stack_ptr++; stack_count++; \
567 goto GENTAG(down); \
568 GENTAG(end): ; /* finished */ \
569 }
570
571 /* example of application of AVL(AVLID,least) and AVL(AVLID,move):
572 { var NODE* tree = ...;
573 var KEY limit = ...;
574 // search in tree after the smallest Key >= limit:
575 var AVL(AVLID,stack) stack;
576 var NODE* bestfit = AVL(AVLID,least)(limit,&tree,&stack);
577 if (bestfit == EMPTY) { error(); }
578 // Now COMPARE(KEYOF(bestfit->nodedata.value),limit) >= 0.
579 ...; KEYOF(bestfit->nodedata.value) -= limit; ...;
580 // reposition the found and modified element in the AVL-tree:
581 AVL(AVLID,move)(&stack);
582 } */
583
584 typedef struct { uintC count; NODE** path[MAXHEIGHT]; } AVL(AVLID,stack);
585
586 /* returns the element from a AVL-tree, whose key is the smallest possible, but
587 still >= than a given limit. (EMPTY, if all elements are < limit.)
588 Thereto as a preparation for the deletion, the path from the root downwards
589 to that element (inclusive, i.e. result = stack->path[stack->count-1] ). */
590 #ifndef NO_AVL_LEAST
AVL(AVLID,least)591 local NODE* AVL(AVLID,least) (KEY limit, NODE** tree_ptr,
592 AVL(AVLID,stack) * stack) {
593 var NODE* mark = EMPTY;
594 var uintC markdepth = 0;
595 var NODE** nodeplace = tree_ptr;
596 var uintC nodedepth = 0;
597 /* mark = current subtree, node = last considered element within.
598 markdepth = stack depth up to mark, nodedepth = stack depth up to node.
599 markdepth <= nodedepth. */
600 while (1) {
601 stack->path[nodedepth++] = nodeplace;
602 var NODE* node = *nodeplace;
603 /* all elements with Key >= Limit are either in the subtree
604 below the node or to the right of mark (including mark). */
605 if (node==EMPTY)
606 break;
607 if (COMPARE(KEYOF(node->nodedata.value),limit) < 0) {
608 /* all elements below the node, that are >= limit, must already be
609 situated underneath of node->nodedata.right. */
610 nodeplace = &node->nodedata.right;
611 } else {
612 /* Limit <= node <= mark.
613 hence, only consider the subtree underneath of node: */
614 mark = node; markdepth = nodedepth;
615 nodeplace = &node->nodedata.left;
616 }
617 }
618 /* all element >= Limit are situated to the right of mark
619 (including mark). */
620 stack->count = markdepth; return mark;
621 }
622 #endif
623
624 /* Repositions an element within a AVL-tree, after its key has changed. */
625 #ifndef NO_AVL_MOVE
AVL(AVLID,move)626 local void AVL(AVLID,move) (AVL(AVLID,stack) * stack) {
627 var uintC stack_count = stack->count; /* number of elements on the stack */
628 var NODE** * stack_ptr = &stack->path[stack_count]; /* always = &stack->path[stack_count] */
629 /* first step, cf. AVL(AVLID,delete) : */
630 var NODE** nodeplace_to_delete = stack_ptr[-1];
631 var NODE* node_to_delete = *nodeplace_to_delete; /* element to be removed */
632 /* node_to_delete = *nodeplace_to_delete is to be removed. */
633 if (node_to_delete->nodedata.left == EMPTY) {
634 /* node_to_delete is replaced by node_to_delete->nodedata.right. */
635 *nodeplace_to_delete = node_to_delete->nodedata.right;
636 stack_ptr--; stack_count--; /* no rebalance at *nodeplace_to_delete! */
637 } else {
638 /* node_to_delete is replaced by the rightmost
639 element of node_to_delete->nodedata.left. */
640 var NODE** * stack_ptr_to_delete = stack_ptr;
641 var NODE** nodeplace = &node_to_delete->nodedata.left;
642 var NODE* node;
643 while (1) {
644 node = *nodeplace;
645 if (node->nodedata.right == EMPTY)
646 break;
647 *stack_ptr++ = nodeplace; stack_count++;
648 nodeplace = &node->nodedata.right;
649 }
650 *nodeplace = node->nodedata.left;
651 /* node is positioned at node_to_delete: */
652 node->nodedata.left = node_to_delete->nodedata.left;
653 node->nodedata.right = node_to_delete->nodedata.right;
654 node->nodedata.height = node_to_delete->nodedata.height;
655 *nodeplace_to_delete = node; /* instead of node_to_delete */
656 /* the rebalance-stack (path from the root downwards) does not
657 contain node_to_delete anymore, but node: */
658 *stack_ptr_to_delete = &node->nodedata.left; /* instead of &node_to_delete->nodedata.left */
659 }
660 AVL(AVLID,rebalance)(stack_ptr,stack_count);
661 /* second step, cf. AVL(AVLID,insert) : */
662 var KEY key = KEYOF(node_to_delete->nodedata.value);
663 var NODE** nodeplace = stack->path[0]; /* = &tree */
664 stack_count = 0; stack_ptr = &stack->path[0];
665 while (1) {
666 var NODE* node = *nodeplace;
667 if (node == EMPTY)
668 break;
669 *stack_ptr++ = nodeplace; stack_count++;
670 if (COMPARE(key,KEYOF(node->nodedata.value)) < 0)
671 /* key < KEYOF(node->nodedata.value) --> insert in the left subtree: */
672 nodeplace = &node->nodedata.left;
673 else
674 /* key >= KEYOF(node->nodedata.value) --> insert in the right subtree: */
675 nodeplace = &node->nodedata.right;
676 }
677 node_to_delete->nodedata.left = EMPTY;
678 node_to_delete->nodedata.right = EMPTY;
679 node_to_delete->nodedata.height = 1;
680 *nodeplace = node_to_delete;
681 AVL(AVLID,rebalance)(stack_ptr,stack_count);
682 }
683 #endif
684
685 /* Sorts the AVL-tree, after the keys have changed and
686 returns the new AVL-tree. */
687 #ifndef NO_AVL_SORT
AVL(AVLID,sort)688 local NODE* AVL(AVLID,sort) (NODE* tree) {
689 var NODE* new_tree = EMPTY;
690 AVL_map_postorder(tree,node, new_tree = AVL(AVLID,insert1)(node,new_tree); );
691 return new_tree;
692 }
693 #endif
694
695 #ifdef DEBUG_AVL
696 /* prints an AVL-tree. */
AVL(AVLID,out)697 local void AVL(AVLID,out) (NODE* tree) {
698 if (tree!=EMPTY) {
699 print("(");
700 if (!(tree->nodedata.left==EMPTY)) {
701 AVL(AVLID,out)(tree->nodedata.left); print("<");
702 }
703 printf("%lx",tree);
704 if (!(tree->nodedata.right==EMPTY)) {
705 print(">"); AVL(AVLID,out)(tree->nodedata.right);
706 }
707 print(")");
708 }
709 }
710 #endif
711
712 #ifdef DEBUG_AVL
713 /* check the invariants of an AVL-tree: */
714 local void AVL(AVLID,check) (NODE* tree);
715 local void AVL(AVLID,checkleft) (NODE* tree, KEY key);
716 local void AVL(AVLID,checkright) (NODE* tree, KEY key);
AVL(AVLID,check)717 local void AVL(AVLID,check) (NODE* tree) {
718 /* check rules 1 and 2: */
719 AVL_map_postorder(tree,node, {
720 var HEIGHT h = node->nodedata.height;
721 var HEIGHT hl = heightof(node->nodedata.left);
722 var HEIGHT hr = heightof(node->nodedata.right);
723 if (!( ((h == hl+1) && (hr <= hl) && (hl <= hr+1))
724 || ((h == hr+1) && (hl <= hr) && (hr <= hl+1))))
725 abort();
726 });
727 /* check rule 3: */
728 AVL_map(tree,node, {
729 AVL(AVLID,checkleft)(node->nodedata.left,KEYOF(node->nodedata.value));
730 AVL(AVLID,checkright)(node->nodedata.right,KEYOF(node->nodedata.value));
731 });
732 }
733 /* check, if all elements of tree have a value <= key : */
AVL(AVLID,checkleft)734 local void AVL(AVLID,checkleft) (NODE* tree, KEY key) {
735 AVL_map(tree,node,
736 if (!( COMPARE(KEYOF(node->nodedata.value),key) <= 0)) abort(););
737 }
738 /* check, if all elements of tree have a value >= key : */
AVL(AVLID,checkright)739 local void AVL(AVLID,checkright) (NODE* tree, KEY key) {
740 AVL_map(tree,node,
741 if (!( COMPARE(KEYOF(node->nodedata.value),key) >= 0)) abort(););
742 }
743 #endif
744
745 #undef heightof
746
747 #endif
748