File:	/home/sbrandt/cactus/Cactus/src/util/SKBinTree.c
1	: /*@@
2	:   @file      SKBinTree.c
3	:   @date      Mon Oct  5 11:00:01 1998
4	:   @author    Tom Goodale
5	:   @desc
6	:              Routines to deal with binary trees keyed by strings.
7	:              The tree is a threaded tree, i.e. it can also be
8	:              traversed, inorder, like a linked list.
9	:   @enddesc
10	:   @version   $Id: SKBinTree.c 3382 2003-08-22 11:21:37Z tradke $
11	: @@*/
12	:
13	:#include <stdio.h>
14	:#include <stdlib.h>
15	:#include <string.h>
16	:#include <ctype.h>
17	:
18	:#include "SKBinTree.h"
19	:#include "util_String.h"
20	:#include "cctk_Flesh.h"
21	:
22	:
23	:static const char *rcsid = "$Header$";
24	:
25	:CCTK_FILEVERSION(util_SKBinTree_c);
26	:
27	: /*@@
28	:   @routine    SKTreeStoreData
29	:   @date       Mon Oct  5 11:04:55 1998
30	:   @author     Tom Goodale
31	:   @desc
32	:   Stores data in string-keyed binary tree.
33	:   @enddesc
34	:@@*/
35	:t_sktree *SKTreeStoreData(t_sktree *root, t_sktree *subtree,
36	:                          const char *key, void *data)
37	:{
38	:  int order;
39	:  t_sktree *newsubtree;
40	:
41	:  if(!subtree)
42	:  {
43	:    /* Create a new element. */
44	:    newsubtree = (t_sktree *)malloc(sizeof(t_sktree));
45	:    if(newsubtree)
46	:    {
47	:      newsubtree->left=NULL;
48	:      newsubtree->right=NULL;
49	:      newsubtree->next=NULL;
50	:      newsubtree->last=NULL;
51	:
52	:      newsubtree->data = data;
53	:
54	:      newsubtree->key= (char *)malloc(sizeof(char)*(strlen(key)+1));
55	:      strcpy(newsubtree->key, key);
56	:      if(root)
57	:      {
58	:        if((order = Util_StrCmpi(key, root->key)) < 0)
59	:        {
60	:          root->left = newsubtree;
61	:          newsubtree->next = root;
62	:          newsubtree->last = root->last;
63	:          if(newsubtree->last)
64	:          {
65	:            newsubtree->last->next = newsubtree;
66	:          }
67	:
68	:          /*          printf("Added %s, NEXT: %s\n", newsubtree->key, root->key); */
69	:        }
70	:        else
71	:        {
72	:          root->right = newsubtree;
73	:          newsubtree->next = root->next;
74	:          newsubtree->last = root;
75	:          root->next = newsubtree;
76	:
77	:          /*printf("Added %s, NEXT: %s\n", newsubtree->key, newsubtree->next ? newsubtree->next->key : "(none)");*/
78	:          /*printf("Modified %s NEXT\n", root->key);*/
79	:        }
80	:
81	:      }
82	:    }
83	:  }
84	:  else
85	:  {
86	:    /* Go down left or right branch. */
87	:    if((order = Util_StrCmpi(key, subtree->key)) < 0)
88	:    {
89	:      newsubtree = SKTreeStoreData(subtree, subtree->left, key, data);
90	:    }
91	:    else if(order > 0)
92	:    {
93	:      newsubtree = SKTreeStoreData(subtree, subtree->right, key, data);
94	:    }
95	:    else
96	:    {
97	:      /* Duplicate key. */
98	:      newsubtree = NULL;
99	:    }
100	:
101	:  }
102	:
103	:  /* Return either the new node, or NULL if either a duplicate value or
104	:   * memory failure.
105	:   */
106	:
107	:  return newsubtree;
108	:
109	:}
110	:
111	: /*@@
112	:   @routine    SKTreeTraverseInorder
113	:   @date       Mon Oct  5 11:05:54 1998
114	:   @author     Tom Goodale
115	:   @desc
116	:   Traverse a tree 'inorder'
117	:   @enddesc
118	:@@*/
119	:int SKTreeTraverseInorder(t_sktree *root, int (*process)(const char *, void *, void *), void *info)
120	:{
121	:  int terminate;
122	:
123	:  terminate = 0;
124	:
125	:  if(root)
126	:  {
127	:    terminate = SKTreeTraverseInorder(root->left, process, info);
128	:    if(!terminate) terminate = process(root->key,root->data,info);
129	:    if(!terminate) terminate = SKTreeTraverseInorder(root->right, process, info);
130	:  }
131	:
132	:  return terminate;
133	:}
134	:
135	: /*@@
136	:   @routine    SKTreeTraversePreorder
137	:   @date       Mon Oct  5 11:05:54 1998
138	:   @author     Tom Goodale
139	:   @desc
140	:   Traverse a tree 'preorder'
141	:   @enddesc
142	:@@*/
143	:int SKTreeTraversePreorder(t_sktree *root, int (*process)(const char *,void *, void *), void *info)
144	:{
145	:  int terminate;
146	:
147	:  terminate = 0;
148	:
149	:  if(root)
150	:  {
151	:    terminate = process(root->key,root->data, info);
152	:    if(!terminate) terminate = SKTreeTraversePreorder(root->left, process, info);
153	:    if(!terminate) terminate = SKTreeTraversePreorder(root->right, process,info);
154	:  }
155	:
156	:  return terminate;
157	:}
158	:
159	: /*@@
160	:   @routine    SKTreeTraversePostorder
161	:   @date       Mon Oct  5 11:05:54 1998
162	:   @author     Tom Goodale
163	:   @desc
164	:   Traverse a tree 'postorder'
165	:   @enddesc
166	:@@*/
167	:int SKTreeTraversePostorder(t_sktree *root, int (*process)(const char *, void *, void *), void *info)
168	:{
169	:  int terminate;
170	:
171	:  terminate = 0;
172	:
173	:  if(root)
174	:  {
175	:    terminate = SKTreeTraversePostorder(root->left, process, info);
176	:    if(!terminate) terminate = SKTreeTraversePostorder(root->right, process, info);
177	:    if(!terminate) terminate = process(root->key,root->data, info);
178	:  }
179	:
180	:  return terminate;
181	:}
182	:
183	: /*@@
184	:   @routine    SKTreePrintNodes
185	:   @date       Mon Oct  5 11:06:52 1998
186	:   @author     Tom Goodale
187	:   @desc
188	:   Allows a binary tree to be printed out.
189	:   @enddesc
190	:@@*/
191	:void SKTreePrintNodes(t_sktree *root, int depth, void (*print_node)(const char *,void *, int))
192	:{
193	:  if(root)
194	:  {
195	:    SKTreePrintNodes(root->left, depth+1,print_node);
196	:    print_node(root->key,root->data,depth);
197	:    SKTreePrintNodes(root->right, depth+1, print_node);
198	:  }
199	:}
200	:
201	:void SKTreeDebugNodes(t_sktree *root, int depth)
202	:{
203	:  if(root)
204	:  {
205	:    SKTreeDebugNodes(root->left, depth+1);
206	:
207	:    printf("KEY:   %s\n", root->key);
208	:    printf("LEFT:  %s\n", root->left  ? root->left->key  : "(none)");
209	:    printf("RIGHT: %s\n", root->right ? root->right->key : "(none)");
210	:    printf("NEXT:  %s\n", root->next  ? root->next->key  : "(none)");
211	:
212	:    SKTreeDebugNodes(root->right, depth+1);
213	:  }
214	:}
215	:
216	:
217	: /*@@
218	:   @routine    SKTreeFindNode
219	:   @date       Mon Jul  5 10:09:30 1999
220	:   @author     Tom Goodale
221	:   @desc
222	:   Finds a given node in the tree.
223	:   @enddesc
224	:@@*/
225	:t_sktree *SKTreeFindNode(t_sktree *root, const char *key)
226	:{
227	:  int order;
228	:
229	:  t_sktree *node;
230	:
231	:  if(root)
232	:  {
233	:    /* Go down left or right branch. */
234	:    if((order = Util_StrCmpi(key, root->key)) < 0)
235	:    {
236	:      node = SKTreeFindNode(root->left, key);
237	:    }
238	:    else if(order > 0)
239	:    {
240	:      node = SKTreeFindNode(root->right, key);
241	:    }
242	:    else
243	:    {
244	:      /* Found it. */
245	:      node = root;
246	:    }
247	:  }
248	:  else
249	:  {
250	:    node = NULL;
251	:  }
252	:
253	:  return node;
254	:}
255	:
256	: /*@@
257	:   @routine    SKTreeFindFirst
258	:   @date       Mon Jul  5 10:09:57 1999
259	:   @author     Tom Goodale
260	:   @desc
261	:   Finds the first node in the tree (the leftmost one).
262	:   @enddesc
263	:@@*/
264	:t_sktree *SKTreeFindFirst(t_sktree *root)
265	:{
266	:  for(; root->left ; root = root->left);
267	:
268	:  return root;
269	:}