1 /* -*- c -*- */
2
3 /*
4 * avl.c
5 *
6 * chpp
7 *
8 * Copyright (C) 1997-1998 Mark Probst
9 *
10 * This program is free software; you can redistribute it and/or
11 * modify it under the terms of the GNU General Public License
12 * as published by the Free Software Foundation; either version 2
13 * of the License, or (at your option) any later version.
14 *
15 * This program is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
19 *
20 * You should have received a copy of the GNU General Public License
21 * along with this program; if not, write to the Free Software
22 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
23 */
24
25 #include <stdlib.h>
26
27 #include "memory.h"
28
29 #include "avl.h"
30
31 int
avlCompare(avlTree * pcolCollect,void * key,unsigned int rank,avlNode * pavlnNode)32 avlCompare (avlTree *pcolCollect, void* key, unsigned int rank,
33 avlNode *pavlnNode)
34 {
35 if (pcolCollect->isSorted)
36 return pcolCollect->compare(key, pavlnNode->key);
37 if (rank < pavlnNode->rank)
38 return -1;
39 if (rank == pavlnNode->rank)
40 return 0;
41 return 1;
42 }
43
44 int
avlBalance(avlNode * pavlnS,int iA,avlNode ** phead)45 avlBalance (avlNode *pavlnS, int iA, avlNode **phead)
46 {
47 avlNode *pavlnR,
48 *pavlnP,
49 *pavlnT;
50
51 *phead = 0;
52 pavlnT = pavlnS->up;
53 pavlnR = AVL_LINK(iA, pavlnS); /* R = LINK(a,S) */
54 if (pavlnR->balance == 0 || pavlnR->balance == iA) /* single rotation */
55 {
56 pavlnR->up = pavlnT; /* UP(R) = T */
57 pavlnS->up = pavlnR; /* UP(S) = R */
58 if (pavlnT)
59 {
60 if (pavlnT->left == pavlnS)
61 pavlnT->left = pavlnR; /* LEFT(T) = R */
62 else
63 pavlnT->right = pavlnR; /* RIGHT(T) = R */
64 }
65 else
66 *phead = pavlnR;
67 if (AVL_LINK(-iA, pavlnR))
68 AVL_LINK(-iA, pavlnR)->up = pavlnS; /* UP(LINK(-a,R)) = S */
69 pavlnP = pavlnR;
70 AVL_LINK_SET(iA, pavlnS, AVL_LINK(-iA, pavlnR));
71 AVL_LINK_SET(-iA, pavlnR, pavlnS);
72 if (iA == 1)
73 pavlnR->rank += pavlnS->rank;
74 else
75 pavlnS->rank -= pavlnR->rank;
76 if (pavlnR->balance == iA)
77 {
78 pavlnS->balance = pavlnR->balance = 0;
79 return iA;
80 }
81 pavlnR->balance = -iA;
82 return 0;
83 }
84
85 /* double rotation */
86 pavlnP = AVL_LINK(-iA, pavlnR);
87 pavlnP->up = pavlnT; /* UP(P) = T */
88 pavlnS->up = pavlnR->up = pavlnP; /* UP(S) = UP(R) = P */
89 if (pavlnT)
90 {
91 if (pavlnT->left == pavlnS)
92 pavlnT->left = pavlnP; /* LEFT(T) = R */
93 else
94 pavlnT->right = pavlnP; /* RIGHT(T) = R */
95 }
96 else
97 *phead = pavlnP;
98 if (AVL_LINK(iA, pavlnP))
99 AVL_LINK(iA, pavlnP)->up = pavlnR; /* UP(LINK(a,P)) = R */
100 if (AVL_LINK(-iA, pavlnP))
101 AVL_LINK(-iA, pavlnP)->up = pavlnS; /* UP(LINK(-a,P)) = S */
102 AVL_LINK_SET(-iA, pavlnR, AVL_LINK(iA, pavlnP));
103 AVL_LINK_SET(iA, pavlnP, pavlnR);
104 AVL_LINK_SET(iA, pavlnS, AVL_LINK(-iA, pavlnP));
105 AVL_LINK_SET(-iA, pavlnP, pavlnS);
106 if (pavlnP->balance == iA)
107 {
108 pavlnS->balance = -iA;
109 pavlnR->balance = 0;
110 }
111 else
112 if (pavlnP->balance == -iA)
113 {
114 pavlnS->balance = 0;
115 pavlnR->balance = iA;
116 }
117 else
118 pavlnS->balance = pavlnR->balance = 0;
119 pavlnP->balance = 0;
120 if (iA == 1)
121 {
122 pavlnR->rank -= pavlnP->rank;
123 pavlnP->rank += pavlnS->rank;
124 }
125 else
126 {
127 pavlnP->rank += pavlnR->rank;
128 pavlnS->rank -= pavlnP->rank;
129 }
130 return -iA;
131 }
132
133 avlTree*
avlNew(void)134 avlNew (void)
135 {
136 avlTree *pcolReturnVar;
137
138 pcolReturnVar = memXAlloc(sizeof(avlTree));
139 pcolReturnVar->head = 0;
140 pcolReturnVar->numElements = 0;
141 pcolReturnVar->isSorted = 0;
142 return pcolReturnVar;
143 }
144
145 avlTree*
avlNewSorted(int (* compare)(void *,void *))146 avlNewSorted (int (*compare) (void*,void*))
147 {
148 avlTree *pcolReturnVar;
149
150 pcolReturnVar = memXAlloc(sizeof(avlTree));
151 pcolReturnVar->head = 0;
152 pcolReturnVar->numElements = 0;
153 pcolReturnVar->isSorted = 1;
154 pcolReturnVar->compare = compare;
155 return pcolReturnVar;
156 }
157
158 void
avlInsert(avlTree * pcolCollect,void * key,unsigned int uiPos)159 avlInsert (avlTree *pcolCollect, void* key, unsigned int uiPos)
160 {
161 avlNode *pavlnNode,
162 *pavlnS,
163 *pavlnP,
164 *pavlnR;
165 unsigned int uiU,
166 uiM;
167 int iA,
168 iResult;
169 int done = 0;
170
171 pcolCollect->numElements++;
172 pavlnNode = memXAlloc(sizeof(avlNode));
173 pavlnNode->key = key;
174 pavlnNode->left = 0;
175 pavlnNode->right = 0;
176 pavlnNode->balance = 0;
177 pavlnNode->rank = 1;
178 if (pcolCollect->head == 0)
179 {
180 pavlnNode->up = 0;
181 pcolCollect->head = pavlnNode;
182 }
183 else
184 {
185 uiU = uiM = uiPos;
186 pavlnS = pavlnP = pcolCollect->head;
187 do
188 {
189 if (avlCompare(pcolCollect, key, uiM, pavlnP) < 0)
190 { /* move left */
191 pavlnP->rank++;
192 pavlnR = pavlnP->left;
193 if (pavlnR == 0)
194 {
195 pavlnP->left = pavlnNode;
196 pavlnNode->up = pavlnP;
197 done = 1;
198 }
199 else
200 if (pavlnR->balance != 0)
201 {
202 pavlnS = pavlnR;
203 uiU = uiM;
204 }
205 pavlnP = pavlnR;
206 }
207 else
208 { /* move right */
209 uiM -= pavlnP->rank;
210 pavlnR = pavlnP->right;
211 if (pavlnR == 0)
212 {
213 pavlnP->right = pavlnNode;
214 pavlnNode->up = pavlnP;
215 done = 1;
216 }
217 else
218 if (pavlnR->balance != 0)
219 {
220 pavlnS = pavlnR;
221 uiU = uiM;
222 }
223 pavlnP = pavlnR;
224 }
225 } while (!done);
226 uiM = uiU;
227 if (avlCompare(pcolCollect, key, uiM, pavlnS) < 0)
228 pavlnR = pavlnP = pavlnS->left;
229 else
230 {
231 pavlnR = pavlnP = pavlnS->right;
232 uiM -= pavlnS->rank;
233 }
234 while (pavlnP != pavlnNode)
235 {
236 iResult = avlCompare(pcolCollect, key, uiM, pavlnP);
237 if (iResult < 0)
238 {
239 pavlnP->balance = -1;
240 pavlnP = pavlnP->left;
241 }
242 else
243 {
244 pavlnP->balance = 1;
245 uiM -= pavlnP->rank;
246 pavlnP = pavlnP->right;
247 }
248 }
249 /* balancing act */
250 if (avlCompare(pcolCollect, key, uiU, pavlnS) < 0)
251 iA = -1;
252 else
253 iA = 1;
254 if (pavlnS->balance == 0)
255 {
256 pavlnS->balance = iA;
257 return;
258 }
259 if (pavlnS->balance == -iA)
260 {
261 pavlnS->balance = 0;
262 return;
263 }
264 /* we need to rebalance our tree */
265 avlBalance(pavlnS, iA, &pavlnR);
266 if (pavlnR)
267 pcolCollect->head = pavlnR;
268 }
269 }
270
271 void
avlPut(avlTree * pcolCollect,void * key)272 avlPut (avlTree *pcolCollect, void* key)
273 {
274 avlInsert(pcolCollect, key, pcolCollect->numElements + 1);
275 }
276
277 avlNode*
avlFirst(avlTree * pcolCollect,unsigned int uiPos)278 avlFirst (avlTree *pcolCollect, unsigned int uiPos)
279 {
280
281 avlNode *pavlnNode;
282
283 if (pcolCollect->head == 0)
284 return 0;
285 pavlnNode = pcolCollect->head;
286 while (uiPos != pavlnNode->rank)
287 {
288 if (uiPos < pavlnNode->rank)
289 pavlnNode = pavlnNode->left;
290 else
291 {
292 uiPos -= pavlnNode->rank;
293 pavlnNode = pavlnNode->right;
294 }
295 }
296 return pavlnNode;
297 }
298
299 avlNode*
avlSearch(avlTree * pcolCollect,void * key)300 avlSearch (avlTree *pcolCollect, void* key)
301 {
302
303 avlNode *pavlnNode,
304 *pavlnLast = 0;
305 int iResult;
306
307 if (!pcolCollect->isSorted)
308 return 0;
309 if (pcolCollect->head == 0)
310 return 0;
311 pavlnNode = pcolCollect->head;
312 iResult = pcolCollect->compare(key, pavlnNode->key);
313 while (pavlnNode)
314 {
315 if (iResult == 0)
316 pavlnLast = pavlnNode;
317 if (iResult <= 0)
318 pavlnNode = pavlnNode->left;
319 else
320 pavlnNode = pavlnNode->right;
321 if (pavlnNode)
322 iResult = pcolCollect->compare(key, pavlnNode->key);
323 }
324 return pavlnLast;
325 }
326
327 unsigned int
avlGetPos(avlTree * pcolCollect,void * key)328 avlGetPos (avlTree *pcolCollect, void* key)
329 {
330
331 avlNode *pavlnNode;
332 unsigned int uiReturnVar = 1,
333 uiLastPos = 0;
334 int iResult;
335
336 if (!pcolCollect->isSorted)
337 return 0;
338 if (pcolCollect->head == 0)
339 return 0;
340 pavlnNode = pcolCollect->head;
341 iResult = pcolCollect->compare(key, pavlnNode->key);
342 while (pavlnNode)
343 {
344 if (iResult == 0)
345 uiLastPos = uiReturnVar;
346 if (iResult <= 0)
347 pavlnNode = pavlnNode->left;
348 else
349 {
350 uiReturnVar += pavlnNode->rank;
351 pavlnNode = pavlnNode->right;
352 }
353 if (pavlnNode)
354 iResult = pcolCollect->compare(key, pavlnNode->key);
355 }
356 return uiLastPos;
357 }
358
359 avlNode*
avlNext(avlNode * pavlnNode)360 avlNext (avlNode *pavlnNode)
361 {
362 if (pavlnNode->right)
363 {
364 pavlnNode = pavlnNode->right;
365 while (pavlnNode->left)
366 pavlnNode = pavlnNode->left;
367 return pavlnNode;
368 }
369 do
370 {
371 if (pavlnNode->up)
372 {
373 if (pavlnNode->up->left == pavlnNode)
374 return pavlnNode->up;
375 else
376 pavlnNode = pavlnNode->up;
377 }
378 else
379 return 0;
380 } while (1);
381 }
382
383 avlNode*
avlPrevious(avlNode * pavlnNode)384 avlPrevious (avlNode *pavlnNode)
385 {
386 if (pavlnNode->left)
387 {
388 pavlnNode = pavlnNode->left;
389 while (pavlnNode->right)
390 pavlnNode = pavlnNode->right;
391 return pavlnNode;
392 }
393 do
394 {
395 if (pavlnNode->up)
396 {
397 if (pavlnNode->up->right == pavlnNode)
398 return pavlnNode->up;
399 else
400 pavlnNode = pavlnNode->up;
401 }
402 else
403 return 0;
404 } while (1);
405 }
406
407 void
avlDeleteNode(avlTree * pcolCollect,avlNode * pavlnNode,int iA)408 avlDeleteNode (avlTree *pcolCollect,
409 avlNode *pavlnNode, int iA)
410 {
411 int balancing = 1;
412 avlNode *pavlnTemp;
413
414 if (!pavlnNode->up) /* deleting the root */
415 {
416 pcolCollect->head = AVL_LINK(iA, pavlnNode);
417 if (pcolCollect->head)
418 pcolCollect->head->up = 0;
419 memFree(pavlnNode);
420 return;
421 }
422 pavlnTemp = pavlnNode;
423 if (pavlnNode->up->left == pavlnNode)
424 {
425 pavlnNode->up->left = AVL_LINK(iA, pavlnNode);
426 iA = -1;
427 }
428 else
429 {
430 pavlnNode->up->right = AVL_LINK(iA, pavlnNode);
431 iA = 1;
432 }
433 pavlnNode = pavlnNode->up;
434 if (AVL_LINK(iA, pavlnNode))
435 AVL_LINK(iA, pavlnNode)->up = pavlnNode;
436 memFree(pavlnTemp);
437 do
438 {
439 if (iA == -1)
440 pavlnNode->rank--; /* adjust rank */
441 if (balancing)
442 { /* adjust balance */
443 if (pavlnNode->balance == 0)
444 {
445 pavlnNode->balance = -iA;
446 balancing = 0;
447 }
448 else
449 if (pavlnNode->balance == iA)
450 pavlnNode->balance = 0;
451 else
452 {
453 /* rebalancing is necessary */
454 if (!avlBalance(pavlnNode, -iA, &pavlnTemp))
455 balancing = 0;
456 if (pavlnTemp)
457 pcolCollect->head = pavlnTemp;
458 pavlnNode = pavlnNode->up;
459 }
460 }
461 if (pavlnNode->up) /* go up one level */
462 {
463 if (pavlnNode->up->left == pavlnNode)
464 iA = -1;
465 else
466 iA = 1;
467 pavlnNode = pavlnNode->up;
468 }
469 else
470 pavlnNode = 0;
471 } while (pavlnNode);
472 }
473
474 void*
avlDelete(avlTree * pcolCollect,unsigned int uiPos)475 avlDelete (avlTree *pcolCollect, unsigned int uiPos)
476 {
477 avlNode *pavlnNode,
478 *pavlnNext;
479 void *key,
480 *ulReturnVar;
481
482 pcolCollect->numElements--;
483 pavlnNode = avlFirst(pcolCollect, uiPos);
484 ulReturnVar = pavlnNode->key;
485 pavlnNext = pavlnNode->right;
486 if (pavlnNext)
487 {
488 for (; pavlnNext->left; pavlnNext = pavlnNext->left)
489 ;
490 key = pavlnNext->key;
491 avlDeleteNode(pcolCollect, pavlnNext, 1);
492 pavlnNode->key = key;
493 }
494 else
495 avlDeleteNode(pcolCollect, pavlnNode, -1);
496 return ulReturnVar;
497 }
498
499 void*
avlKey(avlNode * pavlnNode)500 avlKey (avlNode *pavlnNode)
501 {
502 return pavlnNode->key;
503 }
504
505 void*
avlGet(avlTree * pcolCollect,unsigned int uiPos)506 avlGet (avlTree *pcolCollect, unsigned int uiPos)
507 {
508 return avlFirst(pcolCollect, uiPos)->key;
509 }
510
511 unsigned int
avlNumElements(avlTree * pcolCollect)512 avlNumElements (avlTree *pcolCollect)
513 {
514 return pcolCollect->numElements;
515 }
516
517 int
avlIsEmpty(avlTree * pcolCollect)518 avlIsEmpty (avlTree *pcolCollect)
519 {
520 return avlNumElements(pcolCollect) == 0;
521 }
522
523 int
avlBalanced(avlNode * pavlnNode,unsigned int * puiHeight,unsigned int * pnumElements)524 avlBalanced (avlNode *pavlnNode, unsigned int *puiHeight,
525 unsigned int *pnumElements)
526 {
527 unsigned int uiHeightL,
528 uiHeightR,
529 numElementsR;
530
531 if (!pavlnNode)
532 {
533 *puiHeight = 0;
534 *pnumElements = 0;
535 return 1;
536 }
537 if (pavlnNode->left)
538 {
539 if (pavlnNode->left->up != pavlnNode)
540 return 0;
541 if (!avlBalanced(pavlnNode->left, &uiHeightL, pnumElements))
542 return 0;
543 if (pavlnNode->rank != *pnumElements + 1)
544 return 0;
545 }
546 else
547 {
548 if (pavlnNode->rank != 1)
549 return 0;
550 uiHeightL = 0;
551 *pnumElements = 0;
552 }
553 if (pavlnNode->right)
554 {
555 if (pavlnNode->right->up != pavlnNode)
556 return 0;
557 if (!avlBalanced(pavlnNode->right, &uiHeightR, &numElementsR))
558 return 0;
559 }
560 else
561 {
562 numElementsR = 0;
563 uiHeightR = 0;
564 }
565 if ((int)uiHeightR - (int)uiHeightL != pavlnNode->balance)
566 return 0;
567 if (uiHeightR > uiHeightL)
568 *puiHeight = uiHeightR + 1;
569 else
570 *puiHeight = uiHeightL + 1;
571 *pnumElements += numElementsR + 1;
572 return 1;
573 }
574
575 #ifdef _AVL_TEST
576
577 #include <ctype.h>
578 #include <string.h>
579 #include <stdio.h>
580
581 int
compare_strings(void * ulString1,void * ulString2)582 compare_strings (void* ulString1, void* ulString2)
583 {
584 return strcmp((const char*)ulString1, (const char*)ulString2);
585 }
586
587 void
main(void)588 main (void)
589 {
590
591 avlTree *pcolCollect;
592 avlNode *pavlnCounter;
593 unsigned int uiHeight,
594 uiCounter,
595 uiIndex,
596 numElements;
597 FILE *pfileFile;
598 char acBuffer[128],
599 *pcString;
600
601 pcolCollect = avlNewSorted(compare_strings);
602 /* pcolCollect = avlNew();*/
603 pfileFile = fopen("collect.c", "r");
604 uiCounter = 0;
605 do
606 {
607 if (fgets(acBuffer, 128, pfileFile))
608 {
609 for (uiIndex = 0; isspace(acBuffer[uiIndex]); uiIndex++)
610 ;
611 pcString = malloc(strlen(acBuffer + uiIndex) + 1);
612 strcpy(pcString, acBuffer + uiIndex);
613 avlPut(pcolCollect, (void*)pcString);
614 /* uiCounter++;
615 if (!avlBalanced(pcolCollect->head, &uiHeight, &numElements))
616 {
617 printf("Error: Tree no longer balanced after %uth insertion\n", uiCounter);
618 _getch();
619 return;
620 }*/
621 }
622 else
623 break;
624 } while (1);
625 fclose(pfileFile);
626
627 for (uiCounter = 0; uiCounter < 11; uiCounter++)
628 {
629 avlDelete(pcolCollect, 13);
630 if (!avlBalanced(pcolCollect->head, &uiHeight, &numElements))
631 {
632 printf("Error: Tree no longer balanced!\n");
633 return;
634 }
635 printf("Height: %u\n", uiHeight);
636 }
637
638 pavlnCounter = avlFirst(pcolCollect, 1);
639 uiCounter = 0;
640 for (; pavlnCounter; pavlnCounter = avlNext(pavlnCounter))
641 {
642 if (!pavlnCounter)
643 break;
644 /* if (uiCounter++ == 24)
645 break; */
646 printf("%s", (char*)avlKey(pavlnCounter));
647 }
648
649 avlFree(pcolCollect);
650 }
651
652 #endif
653