00001
00009 #include <stdlib.h>
00010 #include "treemap.h"
00011
00019 static TreeNode leftRotate(TreeNode tree)
00020 {
00021 TreeNode aux;
00022
00023 if(tree&&tree->right)
00024 {
00025 aux=tree->right;
00026 tree->right=aux->left;
00027 aux->left=tree;
00028
00029 aux->super=tree->super;
00030 tree->super=aux;
00031 if(tree->right) tree->right->super=tree;
00032 return aux;
00033 }
00034 else return tree;
00035 }
00036
00037
00038
00046 static TreeNode rightRotate(TreeNode tree)
00047 {
00048 TreeNode aux;
00049
00050 if(tree&&tree->left)
00051 {
00052 aux=tree->left;
00053 tree->left=aux->right;
00054 aux->right=tree;
00055
00056 aux->super=tree->super;
00057 tree->super=aux;
00058 if(tree->left) tree->left->super=tree;
00059 return aux;
00060 }
00061 else return tree;
00062 }
00063
00064
00065
00076 static TreeNode leftBalance(TreeNode tree)
00077 {
00078 if(tree&&tree->left)
00079 {
00080 if(tree->left->bf==L)
00081 {
00082 tree=rightRotate(tree);
00083 tree->bf=E;
00084 tree->right->bf=E;
00085 }
00086 else
00087 {
00088 tree->left=leftRotate(tree->left);
00089 tree=rightRotate(tree);
00090 switch(tree->bf)
00091 {
00092 case L : tree->left->bf=E;
00093 tree->right->bf=R;
00094 break;
00095 case E : tree->left->bf=E;
00096 tree->right->bf=E;
00097 break;
00098 case R : tree->left->bf=L;
00099 tree->right->bf=E;
00100 break;
00101 }
00102 tree->bf=E;
00103 }
00104 }
00105 else
00106 {
00107 tree=rightRotate(tree);
00108 tree->right->bf=E;
00109 tree->left->bf=E;
00110 }
00111 return tree;
00112 }
00113
00114
00115
00126 static TreeNode rightBalance(TreeNode tree)
00127 {
00128 if(tree&&tree->right)
00129 {
00130 if(tree->right->bf==R)
00131 {
00132 tree=leftRotate(tree);
00133 tree->bf=E;
00134 tree->left->bf=E;
00135 }
00136 else
00137 {
00138 tree->right=rightRotate(tree->right);
00139 tree=leftRotate(tree);
00140 switch(tree->bf)
00141 {
00142 case L : tree->left->bf=E;
00143 tree->right->bf=R;
00144 break;
00145 case E : tree->left->bf=E;
00146 tree->right->bf=E;
00147 break;
00148 case R : tree->left->bf=L;
00149 tree->right->bf=E;
00150 break;
00151 }
00152 tree->bf=E;
00153 }
00154 }
00155 else
00156 {
00157 tree=rightRotate(tree);
00158 tree->left->bf=E;
00159 tree->right->bf=E;
00160 }
00161 return tree;
00162 }
00163
00164
00165
00177 static TreeNode rLeftBalance(TreeNode tree,int* h)
00178 {
00179 if(tree&&tree->left)
00180 {
00181 switch(tree->left->bf)
00182 {
00183 case L : tree=rightRotate(tree);
00184 tree->bf=E;
00185 tree->right->bf=E;
00186 break;
00187 case E : tree=rightRotate(tree);
00188 tree->bf=R;
00189 tree->bf=L;
00190 *h=2;
00191 break;
00192 case R : tree->left=leftRotate(tree->left);
00193 tree=rightRotate(tree);
00194 switch(tree->bf)
00195 {
00196 case L : tree->left->bf=E;
00197 tree->right->bf=E;
00198 break;
00199 case E : tree->left->bf=E;
00200 tree->right->bf=E;
00201 break;
00202 case R : tree->left->bf=L;
00203 tree->right->bf=E;
00204 break;
00205 }
00206 tree->bf=E;
00207 break;
00208 }
00209 }
00210 return tree;
00211 }
00212
00213
00214
00226 static TreeNode rRightBalance(TreeNode tree,int* h)
00227 {
00228 if(tree&&tree->right)
00229 {
00230 switch(tree->right->bf)
00231 {
00232 case L : tree->right=rightRotate(tree->right);
00233 tree=leftRotate(tree);
00234 switch(tree->bf)
00235 {
00236 case L : tree->left->bf=E;
00237 tree->right->bf=R;
00238 break;
00239 case E : tree->left->bf=E;
00240 tree->right->bf=E;
00241 break;
00242 case R : tree->left->bf=L;
00243 tree->right->bf=E;
00244 break;
00245 }
00246 tree->bf=E;
00247 break;
00248 case E : tree=leftRotate(tree);
00249 tree->bf=L;
00250 tree->left->bf=R;
00251 *h=2;
00252 break;
00253 case R : tree=leftRotate(tree);
00254 tree->bf=E;
00255 tree->left->bf=E;
00256 break;
00257 }
00258 }
00259 return tree;
00260 }
00261
00262
00263
00271 static TreeNode upperLeft(TreeNode tree)
00272 {
00273 while(tree->right)
00274 tree=tree->right;
00275
00276 return tree;
00277 }
00278
00279
00280
00281 TreeMap newTree(int(*keyComp)(void*,void*))
00282 {
00283 if(!keyComp) return NULL;
00284 else
00285 {
00286 TreeMap tree=(TreeMap)malloc(sizeof(STreeMap));
00287 if(!tree) return NULL;
00288 else
00289 {
00290 tree->keyComp=*keyComp;
00291 tree->size=0;
00292 tree->root=NULL;
00293 return tree;
00294 }
00295 }
00296 }
00297
00298
00299
00300 int treeSetKComp(TreeMap tree,int(*keyComp)(void*,void*))
00301 {
00302 if(!keyComp) return 1;
00303 else
00304 {
00305 tree->keyComp=*keyComp;
00306 return 0;
00307 }
00308 }
00309
00310
00311
00317 static void treeDelAux(TreeNode tree)
00318 {
00319 if(tree)
00320 {
00321 treeDelAux(tree->left);
00322 treeDelAux(tree->right);
00323 free(tree);
00324 }
00325 }
00326
00327
00328
00329 void treeDelete(TreeMap tree)
00330 {
00331 treeDelAux(tree->root);
00332 free(tree);
00333 }
00334
00335
00336
00351 static TreeNode treeInsAux(TreeNode tree,void* key,void* val,int replace,int* h,
00352 int(*comp)(void*,void*))
00353 {
00354 int sig;
00355
00356 if(!tree)
00357 {
00358 TreeNode new;
00359 new=(TreeNode)malloc(sizeof(STreeNode));
00360
00361 if(new)
00362 {
00363 new->key=key;
00364 new->value=val;
00365 new->bf=E;
00366 new->super=NULL;
00367 new->left=NULL;
00368 new->right=NULL;
00369
00370 *h=0;
00371 return new;
00372 }
00373 else
00374 {
00375 *h=2;
00376 return NULL;
00377 }
00378 }
00379 else
00380 {
00381 sig=comp(key,tree->key);
00382
00383 if(sig<0)
00384 {
00385 tree->left=treeInsAux(tree->left,key,val,replace,h,comp);
00386 if(!(*h))
00387 {
00388 tree->left->super=tree;
00389 switch(tree->bf)
00390 {
00391 case L : tree=leftBalance(tree);
00392 tree->bf=E;
00393 *h=-1;
00394 break;
00395 case E : tree->bf=L;
00396 break;
00397 case R : tree->bf=E;
00398 *h=-1;
00399 break;
00400 }
00401 }
00402 }
00403 else if(sig>0)
00404 {
00405 tree->right=treeInsAux(tree->right,key,val,replace,h,comp);
00406
00407 if(!(*h))
00408 {
00409 tree->right->super=tree;
00410 switch(tree->bf)
00411 {
00412 case L : tree->bf=E;
00413 *h=-1;
00414 break;
00415 case E : tree->bf=R;
00416 break;
00417 case R : tree=rightBalance(tree);
00418 tree->bf=E;
00419 *h=-1;
00420 break;
00421 }
00422 }
00423 }
00424 else
00425 {
00426 if(replace) tree->value=val;
00427 *h=1;
00428 }
00429 return tree;
00430 }
00431 }
00432
00433
00434
00435 int treeInsert(TreeMap tree,void* key,void* val,int replace)
00436 {
00437 int h;
00438 tree->root=treeInsAux(tree->root,key,val,replace,&h,tree->keyComp);
00439
00440 if(h<1)
00441 {
00442 tree->size++;
00443 return 0;
00444 }
00445 else return h;
00446 }
00447
00448
00449
00464 static TreeNode treeRemAux(TreeNode tree,void* key,void** value,
00465 void(*del)(void*),int* h,int(*comp)(void*,void*))
00466 {
00467 int sig;
00468 TreeNode aux;
00469
00470 if(!tree)
00471 {
00472 if(value) *value=NULL;
00473 *h=1;
00474 return NULL;
00475 }
00476 else
00477 {
00478 sig=comp(key,tree->key);
00479
00480 if(sig<0)
00481 {
00482 tree->left=treeRemAux(tree->left,key,value,del,h,comp);
00483 if(!(*h))
00484 {
00485 switch(tree->bf)
00486 {
00487 case L : tree->bf=E;
00488 break;
00489 case E : tree->bf=R;
00490 *h=2;
00491 break;
00492 case R : tree=rRightBalance(tree,h);
00493 break;
00494 }
00495 }
00496 return tree;
00497 }
00498 else if(sig>0)
00499 {
00500 tree->right=treeRemAux(tree->right,key,value,del,h,comp);
00501 if(!(*h))
00502 {
00503 switch(tree->bf)
00504 {
00505 case L : tree=rLeftBalance(tree,h);
00506 break;
00507 case E : tree->bf=L;
00508 *h=2;
00509 break;
00510 case R : tree->bf=E;
00511 break;
00512 }
00513 }
00514 return tree;
00515 }
00516 else
00517 {
00518 if(!tree->right)
00519 {
00520 aux=tree->left;
00521 if(aux) aux->super=tree->super;
00522
00523 if(del) del(tree->key);
00524 if(value) *value=tree->value;
00525
00526 free(tree);
00527 *h=0;
00528 return aux;
00529 }
00530 else if(!tree->left)
00531 {
00532 aux=tree->right;
00533 if(aux) aux->super=tree->super;
00534
00535 if(del) del(tree->key);
00536 if(value) *value=tree->value;
00537
00538 free(tree);
00539 *h=0;
00540 return aux;
00541 }
00542 else
00543 {
00544 if(del) del(tree->key);
00545 if(value) *value=tree->value;
00546
00547 aux=upperLeft(tree->left);
00548
00549 tree->key=aux->key;
00550 tree->value=aux->value;
00551 aux->value=NULL;
00552
00553 tree->left=treeRemAux(tree->left,aux->key,NULL,NULL,h,comp);
00554
00555 if(!(*h))
00556 {
00557 switch(tree->bf)
00558 {
00559 case L : tree->bf=E;
00560 break;
00561 case E : tree->bf=R;
00562 *h=2;
00563 break;
00564 case R : tree=rRightBalance(tree,h);
00565 break;
00566 }
00567 }
00568 return tree;
00569 }
00570 }
00571 }
00572 }
00573
00574
00575
00576 int treeRemove(TreeMap tree,void* key,void** value,void(*del)(void*))
00577 {
00578 int h;
00579 tree->root=treeRemAux(tree->root,key,value,del,&h,tree->keyComp);
00580
00581 if(h==1) return 1;
00582 else
00583 {
00584 tree->size--;
00585 return 0;
00586 }
00587 }
00588
00589
00590
00591 int treeGet(TreeMap tree,void* key,void** value)
00592 {
00593 TreeNode aux;
00594 int r;
00595
00596 for(r=-1,aux=tree->root;
00597 aux&&(r=(*tree->keyComp)(key,aux->key));
00598 aux=r<0?aux->left:aux->right);
00599
00600 if(r)
00601 {
00602 *value=NULL;
00603 return 1;
00604 }
00605 else
00606 {
00607 *value=aux->value;
00608 return 0;
00609 }
00610 }
00611
00612
00613
00623 int treeIsAVLAux(TreeNode tree)
00624 {
00625 int left,right;
00626
00627 if(!tree) return 0;
00628 else
00629 {
00630 left=treeIsAVLAux(tree->left);
00631 right=treeIsAVLAux(tree->right);
00632
00633 if(left<0||right<0) return -1;
00634 else if(left>right) return left-right>1?-1:++left;
00635 else return right-left>1?-1:++right;
00636 }
00637 }
00638
00639
00640
00641 int treeIsAVL(TreeMap tree)
00642 {
00643 return(treeIsAVLAux(tree->root)==-1?0:1);
00644 }
00645
00646
00647
00655 static int treeHightAux(TreeNode tree)
00656 {
00657 int hLeft,hRight;
00658
00659 if(!tree) return 0;
00660 else
00661 {
00662 hLeft=treeHightAux(tree->left);
00663 hRight=treeHightAux(tree->right);
00664
00665 return(hLeft>hRight ? ++hLeft:++hRight);
00666 }
00667 }
00668
00669
00670
00671 int treeHeight(TreeMap tree)
00672 {
00673 if(!tree->size) return 0;
00674 else return treeHightAux(tree->root);
00675 }
00676
00677
00678
00679 int treeSize(TreeMap tree)
00680 {
00681 return(tree->size);
00682 }
00683
00684
00691 static void treeInOAux(TreeNode tree,void(*fun)(void*,void*))
00692 {
00693 if(tree)
00694 {
00695 treeInOAux(tree->left,fun);
00696 fun(tree->key,tree->value);
00697 treeInOAux(tree->right,fun);
00698 }
00699 }
00700
00701
00702
00703 int treeInOrder(TreeMap tree,void(*fun)(void*,void*))
00704 {
00705 if(!tree->size) return 1;
00706 else
00707 {
00708 treeInOAux(tree->root,fun);
00709 return 0;
00710 }
00711 }
00712
00713
00714
00721 static void treePrOAux(TreeNode tree,void(*fun)(void*,void*))
00722 {
00723 if(tree)
00724 {
00725 fun(tree->key,tree->value);
00726 treePrOAux(tree->left,fun);
00727 treePrOAux(tree->right,fun);
00728 }
00729 }
00730
00731
00732
00733 int treePreOrder(TreeMap tree,void(*fun)(void*,void*))
00734 {
00735 if(!tree->size) return 1;
00736 else
00737 {
00738 treePrOAux(tree->root,fun);
00739 return 0;
00740 }
00741 }
00742
00743
00744
00751 static void treePsOAux(TreeNode tree,void(*fun)(void*,void*))
00752 {
00753 if(tree)
00754 {
00755 treePsOAux(tree->left,fun);
00756 treePsOAux(tree->right,fun);
00757 fun(tree->key,tree->value);
00758 }
00759 }
00760
00761
00762
00763 int treePosOrder(TreeMap tree,void(*fun)(void*,void*))
00764 {
00765 if(!tree->size) return 1;
00766 else
00767 {
00768 treePsOAux(tree->root,fun);
00769 return 0;
00770 }
00771 }
00772
00773
00774
00784 static int treeKAux(TreeNode tree,Iterator it)
00785 {
00786 int r=0;
00787 if(tree)
00788 {
00789 r=treeKAux(tree->left,it);
00790 r=r||itAdd(it,tree->key);
00791 r=r||treeKAux(tree->right,it);
00792 }
00793
00794 return r;
00795 }
00796
00797
00798
00799 Iterator treeKeys(TreeMap tree)
00800 {
00801 Iterator it=newIt(tree->size);
00802 if(!it) return NULL;
00803 else if(treeKAux(tree->root,it))
00804 {
00805 itDelete(it);
00806 return NULL;
00807 }
00808 else return it;
00809 }
00810
00811
00812
00823 static int treeVAux(TreeNode tree,Iterator it)
00824 {
00825 int r=0;
00826 if(tree)
00827 {
00828 r=treeVAux(tree->left,it);
00829 r=r||itAdd(it,tree->value);
00830 r=r||treeVAux(tree->right,it);
00831 }
00832
00833 return r;
00834 }
00835
00836
00837
00838 Iterator treeValues(TreeMap tree)
00839 {
00840 Iterator it=newIt(tree->size);
00841 if(treeVAux(tree->root,it))
00842 {
00843 itDelete(it);
00844 return NULL;
00845 }
00846 else return it;
00847 }