1 ##
2 ## This file implements an in-memory balanced binary tree. This code
3 ## was originally brought in to implement an efficient priority queue
4 ## for the Dijkstra's shortest path algorithm in crewroute.c.
5 ##
6 ## This file contains code imported into READI from another project.
7 ## The text of the original header comment follows:
8 ##
9 ##
10 ## A package of routines for handling balanced binary trees.
11 ## Copyright (c) 1990 by D. Richard Hipp
12 ##
13
14 my code public-structure {
15 typedef struct Tree Tree;
16 /* A complete binary tree is defined by an instance of the following
17 ** structure
18 */
19 struct Tree {
20 int (*xCompare)(const void*, const void*); /* Comparison function */
21 void *(*xCopy)(const void*); /* Key copy function, or NULL */
22 void (*xFree)(void*); /* Key delete function */
23 struct TreeElem *top; /* The top-most node of the tree */
24 };
25
26 /* Each node in the binary tree is represented by a single instance
27 ** of the following structure
28 */
29 typedef struct TreeElem TreeElem;
30 struct TreeElem {
31 void *data; /* Pointer to the user's data */
32 void *key; /* The key associated with this element */
33 TreeElem *left; /* Left daughter */
34 TreeElem *right; /* Right daughter */
35 int weight; /* Weight of this node */
36 };
37 }
38
39 my c_function {void TreeInit(Tree *tree, int (*xCompare)(const void*, const void*),void *(*xCopy)(const void*),void (*xFree)(void*))} {
40 /* Turn bulk memory into a Tree structure
41 Tree *tree, Tree object to initialize
42 int (*xCompare)(const void*, const void*), Comparison function
43 void *(*xCopy)(const void*), Key copy function or NULL
44 void (*xFree)(void*) Key delete function or NULL
45 */
46 tree->xCompare = xCompare;
47 tree->xCopy = xCopy;
48 tree->xFree = xFree;
49 tree->top = 0;
50 }
51
52 my c_function {int TreeCount(Tree *pTree)} {
53 /* Return the number of elements in the tree. */
54 if( pTree && pTree->top ){
55 return pTree->top->weight;
56 }else{
57 return 0;
58 }
59 }
60
61 my c_function {static void TreeClearNode(TreeElem *p, void (*xFree)(void*))} {
62 /* Delete a single node of the binary tree and all of its children */
63 if( p==0 ) return;
64 if( p->left ) TreeClearNode(p->left, xFree);
65 if( p->right ) TreeClearNode(p->right, xFree);
66 if( xFree ){
67 xFree(p->key);
68 }
69 Tcl_Free((char *)p);
70 }
71
72 my c_function {void TreeClear(Tree *tree)} {
73 /* Remove all nodes from a tree */
74 if( tree->top ){
75 TreeClearNode(tree->top, tree->xFree);
76 }
77 tree->top = 0;
78 }
79
80 my c_function {void *TreeFind(Tree *tree, const void *key)} {
81 /* Find the element of the tree (if any) whose key matches "key".
82 ** Return a pointer to the data for that element. If no match
83 ** is found, return NULL.
84 */
85 TreeElem *p;
86
87 p = tree->top;
88 while( p ){
89 int c = tree->xCompare(p->key, key);
90 if( c==0 ){
91 return p->data;
92 }else if( c<0 ){
93 p = p->right;
94 }else{
95 p = p->left;
96 }
97 }
98 return 0;
99 }
100
101 my c_function {int TreeRank(Tree *tree, const void *key)} {
102 /* If the node with key "key" is the left-most element of the tree,
103 ** return 0. If it is the second to the left, return 1. And so
104 ** forth.
105 **
106 ** If there is no node in the tree with the key "key", then return
107 ** the number that would have been returned if such a node were
108 ** inserted.
109 */
110 TreeElem *p;
111 int rank = 0;
112
113 p = tree->top;
114 while( p ){
115 int c = tree->xCompare(p->key, key);
116 if( c==0 ){
117 rank += p->left ? p->left->weight: 0;
118 break;
119 }else if( c<0 ){
120 rank += (p->left ? p->left->weight: 0) + 1;
121 p = p->right;
122 }else{
123 p = p->left;
124 }
125 }
126 return rank;
127 }
128
129 my c_function {static TreeElem *TreeFindNthElem(Tree *tree, int n)} {
130 /* Return a pointer to the N-th element of a tree. (The left-most
131 ** element is number 0, the next is number 1 and so forth.)
132 */
133 TreeElem *p;
134
135 p = tree->top;
136 while( p ){
137 int c = p->left ? p->left->weight : 0;
138 if( n==c ){
139 return p;
140 }else if( n>c ){
141 n -= c+1;
142 p = p->right;
143 }else{
144 p = p->left;
145 }
146 }
147 return 0;
148 }
149
150 my c_function {void *TreeData(Tree *tree, int n)} {
151 /* Return the data associated with the N-th element of the tree. Return
152 ** NULL if there is no N-th element.
153 */
154 TreeElem *p = TreeFindNthElem(tree,n);
155 return p ? p->data : 0;
156 }
157
158 my c_function {const void *TreeKey(Tree *tree, int n)} {
159 /* Return the key associated with the N-th element of the tree. Return
160 ** NULL if there is no N-th element.
161 */
162 TreeElem *p = TreeFindNthElem(tree,n);
163 if( p ){
164 return p->key;
165 }else{
166 return 0;
167 }
168 }
169
170 my c_function {static void TreeBalance(TreeElem **ppElem)} {
171 /*
172 ** Definitions:
173 ** WEIGHT
174 ** The weight of a node is the total number of children for the node
175 ** plus 1. Leaf nodes have a weight of 1. The root node has a weight
176 ** which equals the number of nodes in the tree.
177 **
178 ** BALANCE
179 ** A node is balanced if the weight of the one child is not more than
180 ** twice the weight of the other child.
181 */
182
183 /* The following routine rebalances the tree rooted at *ppElem after
184 ** the insertion or deletion of a single ancestor.
185 */
186 TreeElem *n; /* Pointer to self */
187 int l,r; /* Weight of left and right daughters */
188 int a,b; /* Weights of various nodes */
189
190 if( ppElem==0 || (n=*ppElem)==0 ) return;
191 l = n->left ? n->left->weight: 0;
192 r = n->right ? n->right->weight: 0;
193 if( l>r*2 ){ /* Too heavy on the left side */
194 TreeElem *nl; /* Pointer to left daughter */
195 TreeElem *nr; /* Pointer to right daughter */
196 int ll, lr; /* Weight of left daughter's left and right daughter */
197 nl = n->left;
198 ll = nl->left ? nl->left->weight: 0;
199 lr = nl->right ? nl->right->weight: 0;
200 if( ll>lr || nl->right==0 ){
201 /*
202 ** Convert from: n to: nl
203 ** / \ / \
204 ** nl c a n
205 ** / \ / \
206 ** a b b c
207 */
208 n->left = nl->right;
209 nl->right = n;
210 n->weight = a = r + lr + 1;
211 nl->weight = a + ll + 1;
212 *ppElem = nl;
213 }else{
214 /*
215 ** Convert from: n to: nr
216 ** / \ / \
217 ** nl d nl n
218 ** / \ / \ / \
219 ** a nr a b c d
220 ** / \
221 ** b c
222 */
223 int lrl, lrr; /* Weight of Great-granddaughter nodes */
224 nr = nl->right;
225 lrl = nr->left ? nr->left->weight: 0;
226 lrr = nr->right ? nr->right->weight: 0;
227 nl->right = nr->left;
228 nr->left = nl;
229 n->left = nr->right;
230 nr->right = n;
231 n->weight = a = lrr + r + 1;
232 nl->weight = b = ll + lrl + 1;
233 nr->weight = a + b + 1;
234 *ppElem = nr;
235 }
236 }else if( r>l*2 ){/* Too deep on the right side */
237 TreeElem *nl; /* Pointer to left daughter */
238 TreeElem *nr; /* Pointer to right daughter */
239 int rl, rr; /* Weight of right daughter's left and right daughter */
240 nr = n->right;
241 rl = nr->left ? nr->left->weight: 0;
242 rr = nr->right ? nr->right->weight: 0;
243 if( rr>rl || nr->left==0 ){
244 /*
245 ** Convert from: n to: nr
246 ** / \ / \
247 ** a nr n c
248 ** / \ / \
249 ** b c a b
250 */
251 n->right = nr->left;
252 nr->left = n;
253 n->weight = a = l + rl + 1;
254 nr->weight = a + rr + 1;
255 *ppElem = nr;
256 }else{
257 /*
258 ** Convert from: n to: nl
259 ** / \ / \
260 ** a nr n nr
261 ** / \ / \ / \
262 ** nl d a b c d
263 ** / \
264 ** b c
265 */
266 int rll,rlr; /* Weights of great-granddaughter nodes */
267 nl = nr->left;
268 rll = nl->left ? nl->left->weight: 0;
269 rlr = nl->right ? nl->right->weight: 0;
270 nr->left = nl->right;
271 nl->right = nr;
272 n->right = nl->left;
273 nl->left = n;
274 n->weight = a = l + rll + 1;
275 nr->weight = b = rr + rlr + 1;
276 nl->weight = a + b + 1;
277 *ppElem = nl;
278 }
279 }else{ /* Node is already balanced. Just recompute its weight. */
280 n->weight = l + r + 1;
281 }
282 }
283
284 my c_function {static void *TreeInsertElement(Tree *pTree, void *key, void *data)} {
285 /*
286 Tree *pTree, The root of the tree
287 void *key, Insert data at this key
288 void *data Data to be inserted
289 */
290 /* This routine either changes the data on an existing node in the tree,
291 ** or inserts a new node. "key" identifies the node. If the data on
292 ** an existing node is changed, then the function returns the old data.
293 ** If a new node is created, NULL is returned.
294 */
295 TreeElem *n;
296 void *old = 0;
297 TreeElem **h[100]; /* Sufficient for a tree with up to 4.0E+17 nodes */
298 int level = 0;
299
300
301 h[0] = &pTree->top;
302 level = 1;
303 n = pTree->top;
304 while( n ){
305 int c;
306 c = pTree->xCompare(key, n->key);
307 if( c<0 ){
308 h[level++] = &(n->left);
309 n = n->left;
310 }else if( c>0 ){
311 h[level++] = &(n->right);
312 n = n->right;
313 }else{
314 old = n->data;
315 n->data = data; /* Replace data in an existing node */
316 break;
317 }
318 }
319 if( n==0 ){ /* Insert a leaf node */
320 level--;
321 n = *h[level] = (TreeElem *)Tcl_Alloc( sizeof(TreeElem) );
322 if( n==0 ){
323 return data;
324 }
325 n->data = data;
326 if( pTree->xCopy ){
327 n->key = pTree->xCopy(key);
328 }else{
329 n->key = key;
330 }
331 n->left = n->right = 0;
332 while( level>=0 ) TreeBalance(h[level--]);
333 }
334 return old;
335 }
336
337 my c_function {static TreeElem *TreeDeleteNthElem(TreeElem **ppTop, int N)} {
338 /* Unlink the N-th node of the tree and return a pointer to that
339 ** node. (The left-most node is 0, the next node to the right is
340 ** 1 and so forth.)
341 */
342 TreeElem *p; /* For walking the tree */
343 int level = 0; /* Depth of the blancing stack */
344 TreeElem **h[100]; /* Balance stack. 100 is sufficient for balancing
345 ** a tree with up to 4.0E+17 nodes */
346
347 h[0] = ppTop;
348 level = 1;
349 p = *ppTop;
350 while( p ){
351 int w;
352 w = (p->left ? p->left->weight: 0);
353 if( N>w ){
354 h[level++] = &(p->right);
355 p = p->right;
356 N -= w+1;
357 }else if( N<w ){
358 h[level++] = &(p->left);
359 p = p->left;
360 }else{
361 break;
362 }
363 }
364 if( p ){
365 level--;
366 if( p->left==0 ){
367 *h[level] = p->right;
368 level--;
369 }else if( p->right==0 ){
370 *h[level] = p->left;
371 level--;
372 }else{
373 TreeElem *x;
374 x = TreeDeleteNthElem(&(p->right),0);
375 x->right = p->right;
376 x->left = p->left;
377 *h[level] = x;
378 }
379 while( level>=0 ) TreeBalance(h[level--]);
380 }
381 return p;
382 }
383
384 my c_function {static TreeElem *TreeDeleteElem(Tree *tree, const void *key)} {
385 /* Unlink the node of the tree corresponding to key and return a pointer
386 ** to that node.
387 */
388 TreeElem *p; /* For walking the tree */
389 int level = 0; /* Depth of the blancing stack */
390 TreeElem **h[100]; /* Balance stack. 100 is sufficient for balancing
391 ** a tree with up to 4.0E+17 nodes */
392
393 h[0] = &tree->top;
394 level = 1;
395 p = tree->top;
396 while( p ){
397 int w;
398 w = tree->xCompare(p->key, key);
399 if( w<0 ){
400 h[level++] = &(p->right);
401 p = p->right;
402 }else if( w>0 ){
403 h[level++] = &(p->left);
404 p = p->left;
405 }else{
406 break;
407 }
408 }
409 if( p ){
410 level--;
411 if( p->left==0 ){
412 *h[level] = p->right;
413 level--;
414 }else if( p->right==0 ){
415 *h[level] = p->left;
416 level--;
417 }else{
418 TreeElem *x;
419 x = TreeDeleteNthElem(&(p->right),0);
420 x->right = p->right;
421 x->left = p->left;
422 *h[level] = x;
423 }
424 while( level>=0 ) TreeBalance(h[level--]);
425 }
426 return p;
427 }
428
429 my c_function {void *TreeInsert(Tree *tree, void *key, void *data)} {
430 /* Insert new data into a node of the tree. The node is identified
431 ** by "key".
432 **
433 ** If the new data is NULL, then node is deleted.
434 **
435 ** If the node aready exists, the new data overwrites the old and
436 ** the old data is returned. If the node doesn't already exist, then
437 ** a new node is created and the function returns NULL.
438 */
439
440 void *old;
441 if( data==0 ){
442 TreeElem *elem = TreeDeleteElem(tree, key);
443 if( elem ){
444 if( tree->xFree ){
445 tree->xFree(elem->key);
446 }
447 old = elem->data;
448 Tcl_Free((char *)elem);
449 }else{
450 old = 0;
451 }
452 }else{
453 old = TreeInsertElement(tree,key,data);
454 }
455 return old;
456 }
457
458 my c_function {void *TreeChangeNth(Tree *tree, int n, void *data)} {
459 /* Change the data on the n-th node of the tree. The old data
460 ** is returned.
461 **
462 ** If data==NULL, then the n-th node of the tree is deleted. (The
463 ** data associated with that node is still returned.)
464 **
465 ** If the value N is out-of-bounds, then no new node is created.
466 ** Instead, the "data" parameter is returned.
467 */
468 void *old;
469 if( data==0 ){
470 TreeElem *elem = TreeDeleteNthElem(&tree->top,n);
471 if( elem ){
472 if( tree->xFree ){
473 tree->xFree(elem->key);
474 }
475 old = elem->data;
476 Tcl_Free((char *)elem);
477 }else{
478 old = 0;
479 }
480 }else{
481 TreeElem *elem = TreeFindNthElem(tree,n);
482 if( elem ){
483 old = elem->data;
484 elem->data = data;
485 }else{
486 old = data;
487 }
488 }
489 return old;
490 }
