source: trunk/src/helpers/tree.c@ 22

Last change on this file since 22 was 21, checked in by umoeller, 25 years ago

Final changes for 0.9.7, i hope...
  • Property svn:eol-style set to CRLF
  • Property svn:keywords set to Author Date Id Revision
File size: 27.5 KB
Line 
1
2/*
3 *@@sourcefile tree.c:
4 * contains helper functions for maintaining 'Red-Black' balanced
5 * binary trees.
6 * See explanations below.
7 *
8 * This file is all new with V0.9.5 (2000-09-29) [umoeller].
9 *
10 * Usage: All C programs; not OS/2-specific.
11 *
12 * Function prefixes (new with V0.81):
13 * -- tree* tree helper functions
14 *
15 * This has been taken from the Standard Function Library (SFL)
16 * by iMatix Corporation and changed to user the "id" member for
17 * tree sorting/comparison. This implementation is released
18 * under the GPL.
19 *
20 * <B>Using binary trees</B>
21 *
22 * You can use any structure as elements in a tree, provided
23 * that the first member in the structure is a TREE structure
24 * (i.e. it has the left, right, parent, id, and colour members).
25 * The tree functions don't care what follows.
26 *
27 * So the implementation here is slightly different from the
28 * linked lists in linklist.c, because the LISTNODE structs
29 * only have pointers to the data. By contrast, the TREE structs
30 * are expected to contain the data themselves. See treeInsertID()
31 * for a sample.
32 *
33 * Each TREE node does not only contain data, but also an
34 * "id" field. The order of nodes in the tree is determined
35 * by calling a node comparison function provided by the caller
36 * (which you must write). This takes two "id" values and must
37 * return:
38 *
39 + 0: id1 == id2
40 + -1: id1 < id2
41 + +1: id1 > id2
42 *
43 * Initialize the root of the tree with treeInit(). Then
44 * add nodes to the tree with treeInsertID() and remove nodes
45 * with treeDelete().
46 *
47 * You can test whether a tree is empty by comparing its
48 * root with TREE_NULL.
49 *
50 * Compared to linked lists (as implemented by linklist.c),
51 * trees allow for much faster searching.
52 *
53 * Assuming a linked list contains N items, then searching the
54 * list for an item will take an average of N/2 comparisons
55 * and even N comparisons if the item cannot be found (unless
56 * you keep the list sorted, but linklist.c doesn't do this).
57 *
58 * According to "Algorithms in C", a search in a balanced
59 * "red-black" binary tree takes about lg N comparisons on
60 * average, and insertions take less than one rotation on
61 * average.
62 *
63 * Example: You need to build a list of files, and you
64 * will search the list frequently according to the file
65 * handles. This would make the handle an ideal "id" field.
66 *
67 * Differences compared to linklist.c:
68 *
69 * -- Trees are considerably slower when inserting and removing
70 * nodes because the tree has to be rebalanced every time
71 * a node changes. By contrast, trees are much faster finding
72 * nodes because the tree is always sorted.
73 *
74 * -- You must always supply a comparison function to allow the
75 * tree functions to sort the tree.
76 *
77 * -- As opposed to a LISTNODE, the TREE structure (which
78 * represents a tree node) does not contain a data pointer,
79 * as said above.
80 *
81 *@@added V0.9.5 (2000-09-29) [umoeller]
82 *@@header "helpers\tree.h"
83 */
84
85/*
86 * Written: 97/11/18 Jonathan Schultz <jonathan@imatix.com>
87 * Revised: 98/12/08 Jonathan Schultz <jonathan@imatix.com>
88 *
89 * Copyright (C) 1991-99 iMatix Corporation.
90 * Copyright (C) 2000 Ulrich M”ller.
91 * This file is part of the "XWorkplace helpers" source package.
92 * This is free software; you can redistribute it and/or modify
93 * it under the terms of the GNU General Public License as published
94 * by the Free Software Foundation, in version 2 as it comes in the
95 * "COPYING" file of the XWorkplace main distribution.
96 * This program is distributed in the hope that it will be useful,
97 * but WITHOUT ANY WARRANTY; without even the implied warranty of
98 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
99 * GNU General Public License for more details.
100 */
101
102/*
103 *@@category: Helpers\C helpers\Red-black balanced binary trees
104 * See tree.c.
105 */
106
107#include "setup.h"
108#include "helpers\tree.h"
109
110// Constants
111TREE TREE_EMPTY = {TREE_NULL, TREE_NULL, NULL, BLACK};
112
113// Internal function prototypes
114static void insert_fixup(TREE **root, TREE *tree);
115static void rotate_left(TREE **root, TREE *tree);
116static void rotate_right(TREE **root, TREE *tree);
117static void delete_fixup(TREE **root, TREE *tree);
118
119/*
120 *@@ treeInit:
121 * initializes an empty tree. The data on the
122 * tree will be invalid, and no memory will be
123 * freed.
124 *
125 * Usage:
126 + TREE *TreeRoot;
127 + treeInit(&TreeRoot);
128 */
129
130void treeInit(TREE **root)
131{
132 *root = TREE_NULL;
133}
134
135/*
136 *@@ treeInsertID:
137 * inserts a node into an existing tree.
138 *
139 * Note: A tree node MUST contain a TREE structure
140 * at the beginning for the tree functions to work.
141 * So to create a tree node with usable data, do this:
142 *
143 + typedef _MYTREENODE
144 + {
145 + // TREE must be at beginning
146 + TREE Tree;
147 + // now use whatever you want
148 + CHAR szMyExtraData[100];
149 + } MYTREENODE, *PMYTREENODE;
150 *
151 * When calling the tree functions, manually cast your
152 * MYTREENODE pointers to (TREE*).
153 *
154 * This function initialises the node pointers and colour
155 * in the TREE structure to correct values, so the caller
156 * does not have to worry about those.
157 *
158 * However you must initialize the TREE.id member correctly
159 * so that your comparison function can compare on that
160 * to find the correct place in the tree to insert the node.
161 *
162 * Usage:
163 + TREE *TreeRoot;
164 + treeInit(&TreeRoot);
165 +
166 + PMYTREENODE pTreeItem = malloc(sizeof(MYTREENODE));
167 + pTreeItem->Tree.id = 1;
168 +
169 + treeInsertID(&TreeRoot,
170 + (TREE*)pTreeItem,
171 + fnCompare, // your comparison function
172 + FALSE);
173 *
174 * Returns:
175 *
176 * -- TREE_OK: OK, item inserted.
177 *
178 * -- TREE_DUPLICATE: if (fAllowDuplicates == FALSE), this is
179 * returned if a tree item with the specified ID already
180 * exists.
181 */
182
183int treeInsertID(TREE **root, // in: root of tree
184 TREE *tree, // in: new tree node
185 FNTREE_COMPARE_IDS *comp, // in: comparison function
186 BOOL fAllowDuplicates) // in: whether duplicates with the same ID are allowed
187{
188 TREE
189 *current,
190 *parent;
191 int
192 last_comp = 0;
193
194 // find where node belongs
195 current = *root;
196 parent = NULL;
197 while (current != TREE_NULL)
198 {
199 parent = current;
200 last_comp = comp(tree->id, current->id);
201 switch (last_comp)
202 {
203 case -1: current = current->left; break;
204 case 1: current = current->right; break;
205 default: if (fAllowDuplicates)
206 current = current->left;
207 else
208 return TREE_DUPLICATE;
209
210 }
211 }
212
213 // setup new node
214 ((TREE *) tree)->parent = parent;
215 ((TREE *) tree)->left = TREE_NULL;
216 ((TREE *) tree)->right = TREE_NULL;
217 ((TREE *) tree)->colour = RED;
218
219 // insert node in tree
220 if (parent)
221 switch (last_comp)
222 {
223 case 1: parent->right = tree; break;
224 default: parent->left = tree;
225 }
226 else
227 *root = tree;
228
229 insert_fixup(root, tree);
230 return(TREE_OK);
231}
232
233/*
234 *@@ treeInsertNode:
235 * similar to treeInsertID, but this uses
236 * a comparision function which compares
237 * nodes.
238 */
239
240int treeInsertNode(TREE **root, // in: root of tree
241 TREE *tree, // in: new tree node
242 FNTREE_COMPARE_NODES *comp, // in: comparison function
243 BOOL fAllowDuplicates) // in: whether duplicates with the same ID are allowed
244{
245 TREE
246 *current,
247 *parent;
248 int
249 last_comp = 0;
250
251 // find where node belongs
252 current = *root;
253 parent = NULL;
254 while (current != TREE_NULL)
255 {
256 parent = current;
257 last_comp = comp(tree, current);
258 switch (last_comp)
259 {
260 case -1: current = current->left; break;
261 case 1: current = current->right; break;
262 default: if (fAllowDuplicates)
263 current = current->left;
264 else
265 return TREE_DUPLICATE;
266
267 }
268 }
269
270 // setup new node
271 ((TREE *) tree)->parent = parent;
272 ((TREE *) tree)->left = TREE_NULL;
273 ((TREE *) tree)->right = TREE_NULL;
274 ((TREE *) tree)->colour = RED;
275
276 // insert node in tree
277 if (parent)
278 switch (last_comp)
279 {
280 case 1: parent->right = tree; break;
281 default: parent->left = tree;
282 }
283 else
284 *root = tree;
285
286 insert_fixup(root, tree);
287 return(TREE_OK);
288}
289
290/*
291 * insert_fixup:
292 * maintains the Red-Black tree balance after a node has been inserted.
293 *
294 * Private function.
295 */
296
297static void insert_fixup(TREE **root,
298 TREE *tree)
299{
300 TREE *uncle;
301
302 // check red-black properties
303 while ((tree != *root)
304 && (tree->parent->colour == RED))
305 {
306 // we have a violation
307 if (tree->parent == tree->parent->parent->left)
308 {
309 uncle = tree->parent->parent->right;
310 if (uncle->colour == RED)
311 {
312 // uncle is RED
313 tree ->parent->colour = BLACK;
314 uncle->colour = BLACK;
315 tree ->parent->parent->colour = RED;
316
317 tree = tree->parent->parent;
318 }
319 else
320 {
321 // uncle is BLACK
322 if (tree == tree->parent->right)
323 {
324 // make tree a left child
325 tree = tree->parent;
326 rotate_left (root, tree);
327 }
328
329 // recolor and rotate
330 tree->parent->colour = BLACK;
331 tree->parent->parent->colour = RED;
332 rotate_right (root, tree->parent->parent);
333 }
334 }
335 else
336 {
337 // mirror image of above code
338 uncle = tree->parent->parent->left;
339 if (uncle->colour == RED)
340 {
341 // uncle is RED
342 tree ->parent->colour = BLACK;
343 uncle->colour = BLACK;
344 tree ->parent->parent->colour = RED;
345
346 tree = tree->parent->parent;
347 }
348 else
349 {
350 // uncle is BLACK
351 if (tree == tree->parent->left)
352 {
353 tree = tree->parent;
354 rotate_right (root, tree);
355 }
356 tree->parent->colour = BLACK;
357 tree->parent->parent->colour = RED;
358 rotate_left (root, tree->parent->parent);
359 }
360 }
361 }
362 (*root)->colour = BLACK;
363}
364
365/*
366 * rotate_left:
367 * rotates tree to left.
368 *
369 * Private function.
370 */
371
372static void rotate_left(TREE **root,
373 TREE *tree)
374{
375 TREE *other = tree->right;
376
377 // establish tree->right link
378 tree->right = other->left;
379 if (other->left != TREE_NULL)
380 other->left->parent = tree;
381
382 // establish other->parent link
383 if (other != TREE_NULL)
384 other->parent = tree->parent;
385
386 if (tree->parent)
387 {
388 if (tree == tree->parent->left)
389 tree->parent->left = other;
390 else
391 tree->parent->right = other;
392 }
393 else
394 *root = other;
395
396 // link tree and other
397 other->left = tree;
398 if (tree != TREE_NULL)
399 tree->parent = other;
400}
401
402/*
403 * rotate_right:
404 * rotates tree to right.
405 *
406 * Private function.
407 */
408
409static void rotate_right(TREE **root,
410 TREE *tree)
411{
412 TREE *other;
413
414 other = tree->left;
415
416 // establish tree->left link
417 tree->left = other->right;
418 if (other->right != TREE_NULL)
419 other->right->parent = tree;
420
421 // establish other->parent link
422 if (other != TREE_NULL)
423 other->parent = tree->parent;
424
425 if (tree->parent)
426 {
427 if (tree == tree->parent->right)
428 tree->parent->right = other;
429 else
430 tree->parent->left = other;
431 }
432 else
433 *root = other;
434
435 // link tree and other
436 other->right = tree;
437 if (tree != TREE_NULL)
438 tree->parent = other;
439}
440
441/*
442 *@@ treeDelete:
443 * deletes a node from a tree. Does not deallocate any memory.
444 *
445 * Returns:
446 *
447 * -- TREE_OK: node deleted.
448 * -- TREE_INVALID_NODE: tree node not found.
449 */
450
451int treeDelete(TREE **root, // in: root of tree
452 TREE *tree) // in: tree node to delete
453{
454 int irc = TREE_OK;
455
456 TREE
457 *youngest, *descendent;
458 TREE_COLOUR
459 colour;
460
461 if ( (!tree)
462 || (tree == TREE_NULL)
463 )
464 return TREE_INVALID_NODE;
465
466 if ( (((TREE *) tree)->left == TREE_NULL)
467 || (((TREE *) tree)->right == TREE_NULL)
468 )
469 // descendent has a TREE_NULL node as a child
470 descendent = tree;
471 else
472 {
473 // find tree successor with a TREE_NULL node as a child
474 descendent = ((TREE *) tree)->right;
475 while (descendent->left != TREE_NULL)
476 descendent = descendent->left;
477 }
478
479 // youngest is descendent's only child, if there is one, else TREE_NULL
480 if (descendent->left != TREE_NULL)
481 youngest = descendent->left;
482 else
483 youngest = descendent->right;
484
485 // remove descendent from the parent chain
486 if (youngest != TREE_NULL)
487 youngest->parent = descendent->parent;
488 if (descendent->parent)
489 {
490 if (descendent == descendent->parent->left)
491 descendent->parent->left = youngest;
492 else
493 descendent->parent->right = youngest;
494 }
495 else
496 *root = youngest;
497
498 colour = descendent->colour;
499
500 if (descendent != (TREE *) tree)
501 {
502 // Conceptually what we are doing here is moving the data from
503 // descendent to tree. In fact we do this by linking descendent
504 // into the structure in the place of tree.
505 descendent->left = ((TREE *) tree)->left;
506 descendent->right = ((TREE *) tree)->right;
507 descendent->parent = ((TREE *) tree)->parent;
508 descendent->colour = ((TREE *) tree)->colour;
509
510 if (descendent->parent)
511 {
512 if (tree == descendent->parent->left)
513 descendent->parent->left = descendent;
514 else
515 descendent->parent->right = descendent;
516 }
517 else
518 *root = descendent;
519
520 if (descendent->left != TREE_NULL)
521 descendent->left->parent = descendent;
522
523 if (descendent->right != TREE_NULL)
524 descendent->right->parent = descendent;
525 }
526
527 if ( (youngest != TREE_NULL)
528 && (colour == BLACK))
529 delete_fixup (root, youngest);
530
531 return (irc);
532}
533
534/*
535 *@@ delete_fixup:
536 * maintains Red-Black tree balance after deleting a node.
537 *
538 * Private function.
539 */
540
541static void delete_fixup(TREE **root,
542 TREE *tree)
543{
544 TREE
545 *sibling;
546
547 while (tree != *root && tree->colour == BLACK)
548 {
549 if (tree == tree->parent->left)
550 {
551 sibling = tree->parent->right;
552 if (sibling->colour == RED)
553 {
554 sibling->colour = BLACK;
555 tree->parent->colour = RED;
556 rotate_left (root, tree->parent);
557 sibling = tree->parent->right;
558 }
559 if ((sibling->left->colour == BLACK)
560 && (sibling->right->colour == BLACK))
561 {
562 sibling->colour = RED;
563 tree = tree->parent;
564 }
565 else
566 {
567 if (sibling->right->colour == BLACK)
568 {
569 sibling->left->colour = BLACK;
570 sibling->colour = RED;
571 rotate_right (root, sibling);
572 sibling = tree->parent->right;
573 }
574 sibling->colour = tree->parent->colour;
575 tree->parent->colour = BLACK;
576 sibling->right->colour = BLACK;
577 rotate_left (root, tree->parent);
578 tree = *root;
579 }
580 }
581 else
582 {
583 sibling = tree->parent->left;
584 if (sibling->colour == RED)
585 {
586 sibling->colour = BLACK;
587 tree->parent->colour = RED;
588 rotate_right (root, tree->parent);
589 sibling = tree->parent->left;
590 }
591 if ((sibling->right->colour == BLACK)
592 && (sibling->left->colour == BLACK))
593 {
594 sibling->colour = RED;
595 tree = tree->parent;
596 }
597 else
598 {
599 if (sibling->left->colour == BLACK)
600 {
601 sibling->right->colour = BLACK;
602 sibling->colour = RED;
603 rotate_left (root, sibling);
604 sibling = tree->parent->left;
605 }
606 sibling->colour = tree->parent->colour;
607 tree->parent->colour = BLACK;
608 sibling->left->colour = BLACK;
609 rotate_right (root, tree->parent);
610 tree = *root;
611 }
612 }
613 }
614 tree->colour = BLACK;
615}
616
617/*
618 *@@ treeFindEQID:
619 * finds a node with ID exactly matching that provided.
620 * To find a tree node, your comparison function must
621 * compare the tree node IDs.
622 */
623
624void* treeFindEQID(TREE **root,
625 unsigned long id,
626 FNTREE_COMPARE_IDS *comp)
627{
628 TREE
629 *current = *root,
630 *found;
631
632 found = NULL;
633 while (current != TREE_NULL)
634 switch (comp(current->id, id))
635 {
636 case -1: current = current->right; break;
637 case 1: current = current->left; break;
638 default: found = current; // In case of duplicates,
639 current = current->left; // get the first one.
640 }
641
642 return found;
643}
644
645/*
646 *@@ treeFindGEID:
647 * finds a node with ID greater than or equal to provided.
648 * To find a tree node, your comparison function must
649 * compare the tree node IDs.
650 */
651
652void* treeFindGEID(TREE **root,
653 unsigned long idFind,
654 FNTREE_COMPARE_IDS *comp)
655{
656 TREE
657 *current = *root,
658 *found;
659
660 found = NULL;
661 while (current != TREE_NULL)
662 switch (comp(current->id, idFind))
663 {
664 case -1: current = current->right; break;
665 default: found = current;
666 current = current->left;
667 }
668
669 return found;
670}
671
672/*
673 *@@ treeFindEQNode:
674 * finds a node with ID exactly matching that provided.
675 * To find a tree node, your comparison function must
676 * compare the tree nodes.
677 */
678
679void* treeFindEQNode(TREE **root,
680 TREE *nodeFind,
681 FNTREE_COMPARE_NODES *comp)
682{
683 TREE
684 *current = *root,
685 *found;
686
687 found = NULL;
688 while (current != TREE_NULL)
689 switch (comp(current, nodeFind))
690 {
691 case -1: current = current->right; break;
692 case 1: current = current->left; break;
693 default: found = current; // In case of duplicates,
694 current = current->left; // get the first one.
695 }
696
697 return found;
698}
699
700/*
701 *@@ treeFindGENode:
702 * finds a node with ID greater than or equal to provided.
703 * To find a tree node, your comparison function must
704 * compare the tree nodes.
705 */
706
707void* treeFindGENode(TREE **root,
708 TREE *nodeFind,
709 FNTREE_COMPARE_NODES *comp)
710{
711 TREE
712 *current = *root,
713 *found;
714
715 found = NULL;
716 while (current != TREE_NULL)
717 switch (comp(current, nodeFind))
718 {
719 case -1: current = current->right; break;
720 default: found = current;
721 current = current->left;
722 }
723
724 return found;
725}
726
727/*
728 *@@ treeFindLTNode:
729 * finds a node with Node less than provided.
730 * To find a tree node, your comparison function must
731 * compare the tree nodes.
732 */
733
734void* treeFindLTNode(TREE **root,
735 TREE *nodeFind,
736 FNTREE_COMPARE_NODES *comp)
737{
738 TREE
739 *current = *root,
740 *found;
741
742 found = NULL;
743 while (current != TREE_NULL)
744 switch (comp(current, nodeFind))
745 {
746 case -1: found = current;
747 current = current->right; break;
748 default: current = current->left;
749 }
750
751 return found;
752}
753
754/*
755 *@@ treeFindLENode:
756 * finds a node with Node less than or equal to provided.
757 * To find a tree node, your comparison function must
758 * compare the tree nodes.
759 */
760
761void* treeFindLENode(TREE **root,
762 TREE *nodeFind,
763 FNTREE_COMPARE_NODES *comp)
764{
765 TREE
766 *current = *root,
767 *found;
768
769 found = NULL;
770 while (current != TREE_NULL)
771 switch (comp(current, nodeFind))
772 {
773 case 1 : current = current->left; break;
774 default: found = current;
775 current = current->right;
776 }
777
778 return found;
779}
780
781/*
782 *@@ treeFindGTNode:
783 * finds a node with Node greater than provided.
784 * To find a tree node, your comparison function must
785 * compare the tree nodes.
786 */
787
788void* treeFindGTNode(TREE **root,
789 TREE *nodeFind,
790 FNTREE_COMPARE_NODES *comp)
791{
792 TREE
793 *current = *root,
794 *found;
795
796 found = NULL;
797 while (current != TREE_NULL)
798 switch (comp(current, nodeFind))
799 {
800 case 1 : found = current;
801 current = current->left; break;
802 default: current = current->right;
803 }
804
805 return found;
806}
807
808/*
809 *@@ treeFindEQID:
810 * finds a node with data exactly matching that provided.
811 * To find a tree node, your comparison function must
812 * compare a tree member with external data.
813 *
814 * This is useful for finding a tree item from a string ID.
815 *
816 * Make sure to use treeInsertNode and compare according
817 * to a string member, and then write a second compare
818 * function for this function which compares the string
819 * member to an external string.
820 */
821
822void* treeFindEQData(TREE **root,
823 void *pData,
824 FNTREE_COMPARE_DATA *comp)
825{
826 TREE *current = *root,
827 *found = NULL;
828
829 while (current != TREE_NULL)
830 switch (comp(current, pData))
831 {
832 case -1: current = current->right; break;
833 case 1: current = current->left; break;
834 default: found = current; // In case of duplicates,
835 current = current->left; // get the first one.
836 }
837
838 return found;
839}
840
841/*
842 *@@ treeTraverse:
843 * traverses the specified tree, calling a processing function
844 * for each tree node.
845 *
846 * The processing function ("process") must be declared as
847 * follows:
848 *
849 + void fnProcess(TREE *t, // current tree node
850 + void *pUser); // user data
851 *
852 * and will receive the "pUser" parameter, which you can use
853 * as a data pointer to some structure for whatever you like.
854 *
855 * "method" specifies in which order the nodes are traversed.
856 * This can be:
857 *
858 * -- 1: current node first, then left node, then right node.
859 * -- 2: left node first, then right node, then current node.
860 * -- other: left node first, then current node, then right node.
861 */
862
863void treeTraverse(TREE *tree, // in: root of tree
864 TREE_PROCESS *process, // in: callback for each node
865 void *pUser, // in: user param for callback
866 int method) // in: traversal mode
867{
868 if ((!tree)
869 || (tree == TREE_NULL))
870 return;
871
872 if (method == 1)
873 {
874 process(tree, pUser);
875 treeTraverse (((TREE *) tree)->left, process, pUser, method);
876 treeTraverse (((TREE *) tree)->right, process, pUser, method);
877 }
878 else if (method == 2)
879 {
880 treeTraverse (((TREE *) tree)->left, process, pUser, method);
881 treeTraverse (((TREE *) tree)->right, process, pUser, method);
882 process(tree, pUser);
883 }
884 else
885 {
886 treeTraverse (((TREE *) tree)->left, process, pUser, method);
887 process(tree, pUser);
888 treeTraverse (((TREE *) tree)->right, process, pUser, method);
889 }
890}
891
892/*
893 *@@ treeFirst:
894 * finds and returns the first node in a (sub-)tree.
895 */
896
897void* treeFirst(TREE *tree)
898{
899 TREE
900 *current;
901
902 if ((!tree)
903 || (tree == TREE_NULL))
904 return NULL;
905
906 current = tree;
907 while (current->left != TREE_NULL)
908 current = current->left;
909
910 return current;
911}
912
913/*
914 *@@ treeLast:
915 * finds and returns the last node in a (sub-)tree.
916 */
917
918void* treeLast(TREE *tree)
919{
920 TREE
921 *current;
922
923 if ((!tree)
924 || (tree == TREE_NULL))
925 return NULL;
926
927 current = tree;
928 while (current->right != TREE_NULL)
929 current = current->right;
930
931 return current;
932}
933
934/*
935 *@@ treeNext:
936 * finds and returns the next node in a tree.
937 */
938
939void* treeNext(TREE *tree)
940{
941 TREE
942 *current,
943 *child;
944
945 if ((!tree)
946 || (tree == TREE_NULL))
947 return NULL;
948
949 current = tree;
950 if (current->right != TREE_NULL)
951 return treeFirst (current->right);
952 else
953 {
954 current = tree;
955 child = TREE_NULL;
956 while ((current->parent)
957 && (current->right == child))
958 {
959 child = current;
960 current = current->parent;
961 }
962 if (current->right != child)
963 return current;
964 else
965 return NULL;
966 }
967}
968
969/*
970 *@@ treePrev:
971 * finds and returns the previous node in a tree.
972 */
973
974void* treePrev(TREE *tree)
975{
976 TREE
977 *current,
978 *child;
979
980 if ((!tree)
981 || (tree == TREE_NULL))
982 return NULL;
983
984 current = tree;
985 if (current->left != TREE_NULL)
986 return treeLast (current->left);
987 else
988 {
989 current = tree;
990 child = TREE_NULL;
991 while ((current->parent)
992 && (current->left == child))
993 {
994 child = current;
995 current = current->parent;
996 }
997 if (current->left != child)
998 return current;
999 else
1000 return NULL;
1001 }
1002}
1003
1004
Note: See TracBrowser for help on using the repository browser.