![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to HTBTree.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Public] / libwww / Library / src|
Return to HTBTree.c CVS log | Up to [Public] / libwww / Library / src |
1.1 timbl 1: /* Binary Tree for sorting things
2: ** ==============================
3: ** Author: Arthur Secret
4: */
5:
6:
7: #include "HTUtils.h"
8: #include "HTBTree.h"
9: #include <stdlib.h>
10: #include <string.h>
11:
12: #define MAX(a,b) ((a)>(b)?(a):(b))
13:
14:
15:
16:
17:
18: PUBLIC HTBTree * HTBTree_new ARGS1(HTComparer, comp)
19: /*********************************************************
20: ** This function returns an HTBTree with memory allocated
21: ** for it when given a mean to compare things
22: */
23: {
24: HTBTree * tree = (HTBTree *)malloc(sizeof(HTBTree));
25: if (tree==NULL) outofmem(__FILE__, "HTBTree_new");
26:
27: tree->compare = comp;
28: tree->top = NULL;
29:
30: return tree;
31: }
32:
33:
34:
35:
36:
37: PUBLIC void HTBTree_free ARGS1(HTBTree*, tree)
38: /**************************************************************
39: ** This void will free the memory allocated for the whole tree
40: */
41: {
42: HTBTElement * wagazou;
43:
44: wagazou = HTBTree_next(tree,NULL);
45: while (wagazou != NULL)
46: {
47: free (wagazou);
48: wagazou = HTBTree_next(tree,wagazou);
49: }
50: free(tree);
51: }
52:
53:
54:
55:
56:
57: PUBLIC void HTBTree_add ARGS2(
58: HTBTree*, tree,
59: void*, object)
60: /**********************************************************************
61: ** This void is the core of HTBTree.c . It will
62: ** 1/ add a new element to the tree at the right place
63: ** so that the tree remains sorted
64: ** 2/ balance the tree to be as fast as possible when reading it
65: */
66: {
67: HTBTElement * leopard;
68: HTBTElement * leopard_son;
69: HTBTElement * leopard_father;
70: HTBTElement * leo_brother;
71: BOOL bouboule,bouboule2,first_correction;
72: int depth,depth2;
73: /* leopard is a pointer to the structure that is the father of the new
74: ** object "object".
75: ** leopard_son is a pointer to the structure that contains or will contain
76: ** the new object "object".
77: ** leopard_father and leo_brother are pointers that are used to modify the
78: ** depths of upper elements, when needed.
79: **
80: ** bouboule indicates by a value NO when the future father of "object" is
81: ** found.
82: ** bouboule2 indicates by a value NO when, in case of a difference of depths
83: ** < 2, the top of the tree is encountered and forbids any further try to
84: ** balance the tree.
85: ** first_correction is a boolean used to avoid infinite loops in cases
86: ** such as:
87: **
88: ** 3 3
89: ** 4 4
90: ** 5 5
91: **
92: ** 3 is used here to show that it need not be the top of the tree.
93: */
94:
95: /*
96: ** 1/ Adding of the element to the binary tree
97: */
98:
99: if (tree->top == NULL)
100: {
101: tree->top = (HTBTElement *)malloc(sizeof(HTBTElement));
102: if (tree->top == NULL) outofmem(__FILE__, "HTBTree_add");
103: tree->top->up = NULL;
104: tree->top->object = object;
105: tree->top->left = NULL;
106: tree->top->left_depth = 0;
107: tree->top->right = NULL;
108: tree->top->right_depth = 0;
109: }
110: else
111: {
112: bouboule = YES;
113: leopard = tree->top;
114: leopard_son = NULL;
115: leopard_father = NULL;
116: leo_brother = NULL;
117: while (bouboule)
118: {
119: if (tree->compare(object,leopard->object)<0)
120: {
121: if (leopard->left != NULL) leopard = leopard->left;
122: else
123: {
124: bouboule = NO;
125: leopard->left = (HTBTElement *)malloc(sizeof(HTBTElement));
126: if (leopard->left==NULL) outofmem(__FILE__, "HTBTree_add");
127: leopard_son = leopard->left;
128: leopard_son->up = leopard;
129: leopard_son->object = object;
130: leopard_son->left = NULL;
131: leopard_son->left_depth = 0;
132: leopard_son->right = NULL;
133: leopard_son->right_depth = 0;
134: }
135: }
136: if (tree->compare(object,leopard->object)>0)
137: {
138: if (leopard->right != NULL) leopard = leopard->right;
139: else
140: {
141: bouboule = NO;
142: leopard->right = (HTBTElement *)malloc(sizeof(HTBTElement));
143: if (leopard->right==NULL) outofmem(__FILE__, "HTBTree_add");
144: leopard_son = leopard->right;
145: leopard_son->up = leopard;
146: leopard_son->object = object;
147: leopard_son->left = NULL;
148: leopard_son->left_depth = 0;
149: leopard_son->right = NULL;
150: leopard_son->right_depth = 0;
151: }
152: }
153: }
154: /*
155: ** Changing of all depths that need to be changed
156: */
157: leopard_father = leopard;
158: leo_brother = leopard_son;
159: do
160: {
161: if (leopard_father->left == leo_brother)
162: {
163: depth = leopard_father->left_depth;
164: leopard_father->left_depth = 1
165: + MAX(leo_brother->right_depth,leo_brother->left_depth);
166: depth2 = leopard_father->left_depth;
167: }
168: else
169: {
170: depth = leopard_father->right_depth;
171: leopard_father->right_depth = 1
172: + MAX(leo_brother->right_depth,leo_brother->left_depth);
173: depth2 = leopard_father->right_depth;
174: }
175: leo_brother = leopard_father;
176: leopard_father = leopard_father->up;
177: } while ((depth != depth2) && (leopard_father != NULL));
178:
179:
180: /*
181: ** 2/ Balancing the binary tree, if necessary
182: */
183: bouboule2 = YES;
184: first_correction = YES;
185: while ((bouboule2) && (first_correction))
186: {
187: if ((abs(leopard->left_depth - leopard->right_depth)) < 2)
188: {
189: if (leopard->up != NULL) leopard = leopard->up;
190: else bouboule2 = NO;
191: }
192: else
193: { /* We start the process of balancing */
194:
195: first_correction = NO;
196: /*
197: ** first_correction is a boolean used to avoid infinite
198: ** loops in cases such as:
199: **
200: ** 3 3
201: ** 4 4
202: ** 5 5
203: **
204: ** 3 is used to show that it need not be the top of the tree
205: */
206:
207:
208: if (leopard->left_depth > leopard->right_depth)
209: {
210: leopard_son = leopard->left;
211: leopard->left_depth = leopard_son->right_depth;
212: leopard_son->right_depth = 1
213: + MAX(leopard->right_depth,leopard->left_depth);
214: if (leopard->up != NULL)
215: {
216: leopard_father = leopard->up;
217: leo_brother = leopard_son;
218: do
219: {
220: if (leopard_father->left == leo_brother->up)
221: {
222: depth = leopard_father->left_depth;
223: leopard_father->left_depth = 1
224: + MAX(leo_brother->left_depth,
225: leo_brother->right_depth);
226: depth2 = leopard_father->left_depth;
227: }
228: else
229: {
230: depth = leopard_father->right_depth;
231: leopard_father->right_depth = 1
232: + MAX(leo_brother->left_depth,
233: leo_brother->right_depth);
234: depth2 = leopard_father->right_depth;
235: }
236: leo_brother = leopard_father;
237: leopard_father = leopard_father->up;
238: } while ((depth != depth2) && (leopard_father != NULL));
239: leopard_father = leopard->up;
240: if (leopard_father->left == leopard)
241: {
242: /*
243: ** 3 3
244: ** 4 5
245: ** When tree 5 6 becomes 7 4
246: ** 7 8 8 6
247: **
248: ** 3 is used to show that it may not be the top of the
249: ** tree.
250: */
251: leopard_father->left = leopard_son;
252: leopard->left = leopard_son->right;
253: leopard_son->right = leopard;
254: }
255: if (leopard_father->right == leopard)
256: {
257: /*
258: ** 3 3
259: ** 4 5
260: ** When tree 5 6 becomes 7 4
261: ** 7 8 8 6
262: **
263: ** 3 is used to show that it may not be the top of the
264: ** tree
265: */
266: leopard_father->right = leopard_son;
267: leopard->left = leopard_son->right;
268: leopard_son->right = leopard;
269: }
270: leopard_son->up = leopard_father;
271: }
272: else
273: {
274: /*
275: **
276: ** 1 2
277: ** When tree 2 3 becomes 4 1
278: ** 4 5 5 3
279: **
280: ** 1 is used to show that it is the top of the tree
281: */
282: leopard_son->up = NULL;
283: leopard->left = leopard_son->right;
284: leopard_son->right = leopard;
285: }
286: leopard->up = leopard_son;
287: if (leopard->left != NULL)
288: leopard->left->up = leopard;
289: }
290: else
291: {
292: leopard_son = leopard->right;
293: leopard->right_depth = leopard_son->left_depth;
294: leopard_son->left_depth = 1 +
295: MAX(leopard->right_depth,leopard->left_depth);
296: if (leopard->up != NULL)
297: {
298: leopard_father = leopard->up;
299: leo_brother = leopard_son;
300: do
301: {
302: if (leopard_father->left == leopard)
303: {
304: depth = leopard_father->left_depth;
305: leopard_father->left_depth = 1
306: + MAX(leopard_son->left_depth,
307: leopard_son->right_depth);
308: depth2 = leopard_father->left_depth;
309: }
310: else
311: {
312: depth = leopard_father->right_depth;
313: leopard_father->right_depth = 1
314: + MAX(leopard_son->left_depth,
315: leopard_son->right_depth);
316: depth2 = leopard_father->right_depth;
317: }
318: leopard_father = leopard_father->up;
319: leo_brother = leopard_father;
320: } while ((depth != depth2) && (leopard_father != NULL));;
321: leopard_father = leopard->up;
322: if (leopard_father->left == leopard)
323: {
324: /*
325: ** 3 3
326: ** 4 6
327: ** When tree 5 6 becomes 4 8
328: ** 7 8 5 7
329: **
330: ** 3 is used to show that it may not be the top of the
331: ** tree.
332: */
333: leopard_father->left = leopard_son;
334: leopard->right = leopard_son->left;
335: leopard_son->left = leopard;
336: }
337: if (leopard_father->right == leopard)
338: {
339: /*
340: ** 3 3
341: ** 4 6
342: ** When tree 5 6 becomes 4 8
343: ** 7 8 5 7
344: **
345: ** 3 is used to show that it may not be the top of the
346: ** tree
347: */
348: leopard_father->right = leopard_son;
349: leopard->right = leopard_son->left;
350: leopard_son->left = leopard;
351: }
352: leopard_son->up = leopard_father;
353: }
354: else
355: {
356: /*
357: **
358: ** 1 3
359: ** When tree 2 3 becomes 1 5
360: ** 4 5 2 4
361: **
362: ** 1 is used to show that it is the top of the tree.
363: */
364: leopard_son->up = NULL;
365: leopard->right = leopard_son->left;
366: leopard_son->left = leopard;
367: }
368: leopard->up = leopard_son;
369: leopard->right->up = leopard;
370: }
371: }
372: }
373: while (leopard->up != NULL)
374: {
375: leopard = leopard->up;
376: }
377: tree->top = leopard;
378: }
379: }
380:
381:
382:
383: PUBLIC HTBTElement * HTBTree_next ARGS2(
384: HTBTree*, tree,
385: HTBTElement*, ele)
386: /**************************************************************************
387: ** this function returns a pointer to the leftmost element if ele is NULL,
388: ** and to the next object to the right otherways.
389: ** If no elements left, returns a pointer to NULL.
390: */
391: {
392: HTBTElement * leopard;
393: HTBTElement * leopard_father;
394:
395: if (ele == NULL)
396: {
397: leopard = tree->top;
398: if (leopard != NULL)
399: while (leopard->left != NULL)
400: leopard = leopard->left;
401: }
402: else
403: {
404: leopard = ele;
405: if (leopard->right != NULL)
406: {
407: leopard = leopard->right;
408: while (leopard->left != NULL)
409: leopard = leopard->left;
410: }
411: else
412: {
413: leopard_father = leopard->up;
414: while (leopard_father->right == leopard)
415: {
416: leopard = leopard_father;
417: leopard_father = leopard->up;
418: }
419: leopard = leopard_father;
420: }
421: }
422: return leopard;
423: }
424:
425:
426: #ifdef TEST
427: main ()
428: /******************************************************
429: ** This is just a test to show how to handle HTBTree.c
430: */
431: {
432: HTBTree * tree;
433: HTBTElement * wagazou;
434:
435: tree = HTBTree_new(strcasecmp);
436: HTBTree_add(tree,"zoo");
437: HTBTree_add(tree,"carot");
438: HTBTree_add(tree,"elephant\t");
439: HTBTree_add(tree,"coat");
440: HTBTree_add(tree,"snake");
441: HTBTree_add(tree,"Peter");
442: HTBTree_add(tree,"Harrison");
443: HTBTree_add(tree,"WWW");
444: wagazou = HTBTree_next(tree,NULL);
445: while (wagazou != NULL)
446: {
447: printf("The next element is %s\n",wagazou->object);
448: wagazou = HTBTree_next(tree,wagazou);
449: }
450: HTBTree_free (tree);
451: }
452:
453:
454: #endif