Main Page   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members  

guma_sorting.cpp

Go to the documentation of this file.
00001 /* LIBGUL - Geometry Utility Library
00002  * Copyright (C) 1998-1999 Norbert Irmer
00003  *
00004  * This library is free software; you can redistribute it and/or
00005  * modify it under the terms of the GNU Library General Public
00006  * License as published by the Free Software Foundation; either
00007  * version 2 of the License, or (at your option) any later version.
00008  *
00009  * This library is distributed in the hope that it will be useful,
00010  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012  * Library General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU Library General Public
00015  * License along with this library; if not, write to the
00016  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
00017  * Boston, MA 02111-1307, USA.
00018  */
00019  
00020 #include "stdafx.h"
00021 
00022 #include <stdio.h>
00023 #include <stdlib.h>
00024 #include <iostream>
00025 #include <math.h>
00026 #include "gul_types.h"
00027 #include "guma_sorting.h"
00028 
00029 
00030 namespace guma {
00031 
00032 using gul::Ptr;
00033 using std::cout;
00034 
00035 /*----------------------------------------------------------
00036   Heapsort (see "Numerical Recipes in C", or Knuth) 
00037 -----------------------------------------------------------*/
00038 GULAPI void HeapSort( size_t nelem, size_t elsize, void *elptr,
00039                int (*usrfunc)( void *, void *, void *), void *usrdata )                
00040 {
00041   char *ra, *rra;
00042   size_t n = nelem, l, ir, i, j;
00043 
00044   rra = (char *)alloca( elsize );
00045   if( rra == NULL ) return;
00046 
00047   ra = (char *)elptr;
00048 
00049   if( n < 2 ) return;
00050   l = (n >> 1) + 1;
00051   ir = n;
00052   
00053   for(;;)
00054   {
00055     if( l > 1 )
00056     {
00057       memcpy( rra, &ra[(l-2)*elsize], elsize );
00058       l--;    
00059     }
00060     else
00061     {
00062       memcpy( rra, &ra[(ir-1)*elsize], elsize );
00063       memcpy( &ra[(ir-1)*elsize], ra, elsize );
00064       if( --ir == 1 )
00065       {
00066         memcpy( ra, rra, elsize );
00067         break;
00068       }
00069     }
00070     i = l;
00071     j = l+l;
00072 
00073     while( j <= ir )
00074     {
00075       if( (j < ir) &&
00076           (usrfunc( &ra[(j-1)*elsize], &ra[j*elsize], usrdata ) < 0) )
00077         j++;
00078        
00079       if( usrfunc(rra, &ra[(j-1)*elsize], usrdata) < 0 )
00080       {
00081         memcpy( &ra[(i-1)*elsize], &ra[(j-1)*elsize], elsize );
00082         i = j;
00083         j <<= 1;
00084       }
00085       else
00086         j = ir + 1;
00087     }
00088     memcpy( &ra[(i-1)*elsize], rra, elsize );
00089   }
00090   return;
00091 }
00092 
00093 GULAPI void PtrHeapSort( size_t nelem, void **elptr,
00094                 int (*usrfunc)( void *, void *, void *), void *usrdata )                
00095 {
00096   void **ra, *rra;
00097   size_t n = nelem, l, ir, i, j;
00098 
00099   ra = elptr;
00100 
00101   if( n < 2 ) return;
00102   l = (n >> 1) + 1;
00103   ir = n;
00104   
00105   for(;;)
00106   {
00107     if( l > 1 )
00108     {
00109       rra = ra[l-2];
00110       l--;    
00111     }
00112     else
00113     {
00114       rra = ra[ir-1];
00115       ra[ir-1] = ra[0];
00116       
00117       if( --ir == 1 )
00118       {
00119         ra[0] = rra;
00120         break;
00121       }
00122     }
00123     i = l;
00124     j = l+l;
00125 
00126     while( j <= ir )
00127     {
00128       if( (j < ir) &&
00129           (usrfunc( ra[j-1], ra[j], usrdata ) < 0) )
00130         j++;
00131   
00132       if( usrfunc( rra, ra[j-1], usrdata) < 0 )
00133       {
00134         ra[i-1] = ra[j-1];
00135         i = j;
00136         j <<= 1;
00137       }
00138       else
00139         j = ir + 1;
00140     }
00141 
00142     ra[i-1] = rra;
00143   }
00144 }
00145 
00146 // instantiation of the heapsort template for often used types 
00147 GULAPI void heapsort( int nA, Ptr<void *>& A ) { _heapsort( nA, A ); }
00148 GULAPI void heapsort( int nA, Ptr<int>& A ) { _heapsort( nA, A ); }
00149 
00150 // these are often used, so they are instantiated in the library
00151 GULAPI int BinarySearch( int x, int nA, const gul::Ptr<int>& A )
00152 { return _BinarySearch( x, nA, A); }
00153 GULAPI int BinarySearch( void *x, int nA, const gul::Ptr<void *>& A )
00154 { return _BinarySearch( x, nA, A); }
00155 
00156 /***************************************************************
00157 
00158   BALANCED BINARY TREE (see Knuth: "Sorting and Searching")
00159 
00160 ***************************************************************/
00161 
00162 /*-------------------------------------------------------------
00163   Creates an empty balanced binary tree
00164 ------------------------------------------------------------*/
00165 
00166 GULAPI void InitBBT( BBTNode *head )
00167 {
00168   head->F.b = 1;
00169   head->F.l = 0;
00170  
00171   (*((int *)(&head->left))) = 0;  /* height = 0 */
00172   head->right = NULL;
00173 }
00174 
00175 
00176 /*----------------------------------------------------------------------
00177   Search for an element in a balanced binary tree. If the element was found,
00178   the address of its node is returned, otherwise the position (address of node
00179   and side) in the tree is returned, under which the element would be
00180   inserted.  
00181 ------------------------------------------------------------------------*/
00182 
00183 GULAPI int SearchElementInBBT( BBTNode *head, void *key,
00184                                int compare( void *, void * ),
00185                                BBTNode **element )
00186 {
00187   int result;
00188   BBTNode *P,*el;
00189   
00190   el = head;
00191   result = 1;
00192   P = head->right;
00193 
00194   while( P != NULL )      /* Knoten suchen */
00195   {               
00196     el = P;
00197     result = compare( key, P->key );
00198 
00199     if( result < 0 )
00200     {     
00201       P = P->left;
00202     }
00203     else if( result > 0 )
00204     {
00205       P = P->right;      
00206     }
00207     else
00208       break;
00209   }
00210 
00211   *element = el;
00212   return(result);
00213 }  
00214 
00215 /* ---------------------------------------------------------------
00216   Find the successor of a given element in a balanced binary tree
00217 ----------------------------------------------------------------- */
00218 
00219 GULAPI BBTNode *SearchSuccessorInBBT( BBTNode *element, BBTNode *head )
00220 {
00221   BBTNode *N = element, *L, *P;
00222   
00223   if( N->right )
00224   {
00225     N = N->right;
00226     for(;;)
00227     {
00228       L = N->left;
00229       if( L == NULL ) return N;
00230       N = L;
00231     } 
00232   }
00233   else
00234   {
00235     for(;;)
00236     {
00237       if( N == head ) return NULL;
00238       P = N->parent;
00239       if( N->F.l == -1 ) return P;
00240       N = P;
00241     }
00242   }
00243 }
00244 
00245 /* ---------------------------------------------------------------
00246   Find the predecessor of a given element in a balanced binary tree
00247 ----------------------------------------------------------------- */
00248 
00249 GULAPI BBTNode *SearchPredecessorInBBT( BBTNode *element, BBTNode *head )
00250 {
00251   BBTNode *N = element, *R, *P;
00252   
00253   if( N->left )
00254   {
00255     N = N->left;
00256     for(;;)
00257     {
00258       R = N->right;
00259       if( R == NULL ) return N;
00260       N = R;
00261     } 
00262   }
00263   else
00264   {
00265     for(;;)
00266     {
00267       P = N->parent;
00268       if( P == head ) return NULL;
00269       if( N->F.l == +1 ) return P;
00270       N = P;
00271     }
00272   }
00273 }
00274 
00275 /*------------------------------------------------------------------------
00276   Inserts a node 'element' into a balanced binary tree, given by 'head'.
00277   The node is inserted under the node 'where' on the side 'side'.
00278   (side == -1 => left,  side == 1 => right )
00279 ------------------------------------------------------------------------*/
00280 
00281 GULAPI void InsertElementIntoBBT( BBTNode *element, 
00282                                   BBTNode *where, int side, BBTNode *head  )
00283 {
00284   BBTNode *Q, *Pk, *Pk_1, *A, *B, *X;
00285   int ak, ak_1;
00286 
00287   Q = element;                    /* neuen Knoten initialisieren */
00288   Q->left = Q->right = NULL;    
00289   Q->F.b = 0;
00290 
00291   Pk = where;
00292   ak = side;
00293 
00294   if( ak == -1 )
00295   {
00296     Pk->left = Q;
00297     if( Pk->left != NULL )
00298     {
00299       Pk->left->parent = Pk;
00300       Pk->left->F.l = -1;
00301     }
00302   }  
00303   else
00304   {
00305     Pk->right = Q;  
00306     if( Pk->right != NULL )
00307     {
00308       Pk->right->parent = Pk;
00309       Pk->right->F.l = 1;
00310     }
00311   }  
00312   
00313   while( (Pk->F.b == 0) && (Pk != head) )  /* Balance Faktoren aktualisieren */
00314   {
00315     Pk->F.b = ak;
00316     ak = Pk->F.l;                 /* k-- */
00317     Pk = Pk->parent;
00318   }
00319 
00320   if( Pk == head )
00321   {
00322     (*((int *)(&head->left)))++;  /* Baumhoehe im Headerknoten erhoehen */
00323     return;                      /*** fertig ***/
00324   }
00325 
00326   if( ak == -1 ) /*** eventuell Rebalancieren, Ausfuehrung fuer (ak == -1) ***/
00327   {
00328     A = Pk;
00329     Pk_1 = Pk->parent;
00330     ak_1 = Pk->F.l;
00331     
00332     if( A->F.b == 1 )             /* (A->B == -ak)   */    
00333     {
00334       A->F.b = 0;
00335       return;                    /*** fertig ***/
00336     }
00337     else                          /* A->B == ak      */
00338     {
00339       B = Pk->left;               /* B = LINK(A,ak)  */
00340 
00341       if( B->F.b == -1 )          /* (B->B == ak) => Single Rotation */
00342       {
00343         A->left = B->right;       /* LINK(A,ak) = LINK(B,-ak) */     
00344         if( A->left != NULL )
00345         {
00346           A->left->parent = A;
00347           A->left->F.l = -1;
00348         }
00349             
00350         B->right = A;             /* LINK(B,-ak) = A  */
00351         if( B->right != NULL )
00352         {
00353           B->right->parent = B;
00354           B->right->F.l = 1;
00355         }
00356             
00357         A->F.b = B->F.b = 0;
00358 
00359         ak = ak_1;                          /* k-- */
00360         Pk = Pk_1;
00361           
00362         if( ak == -1 )                      /* Wurzel Teilbaum = B */
00363         {
00364           Pk->left = B;
00365           if( Pk->left != NULL )
00366           {
00367             Pk->left->parent = Pk;
00368             Pk->left->F.l = -1;
00369           }
00370         }  
00371         else
00372         {
00373           Pk->right = B;  
00374           if( Pk->right != NULL )
00375           {
00376             Pk->right->parent = Pk;
00377             Pk->right->F.l = 1;
00378           }
00379         }
00380 
00381         return;   /*** fertig ***/
00382       }
00383       else                        /* (B->B == -ak) => Double Rotation */
00384       {
00385         X = B->right;             /* X = LINK(B,-ak)                  */
00386 
00387         A->left = X->right;       /* LINK(A,ak) = LINK(X,-ak)         */
00388         if( A->left != NULL )
00389         {
00390           A->left->parent = A;
00391           A->left->F.l = -1;
00392         }
00393             
00394         B->right = X->left;       /* LINK(B,-ak) = LINK(X,ak)         */
00395         if( B->right != NULL )
00396         {
00397           B->right->parent = B;
00398           B->right->F.l = 1;
00399         }
00400             
00401         X->left = B;              /* LINK(X,ak) = B                   */
00402         if( X->left != NULL )
00403         {
00404           X->left->parent = X;
00405           X->left->F.l = -1;
00406         }
00407             
00408         X->right = A;             /* LINK(X,-ak) = A                  */
00409         if( X->right != NULL )
00410         {
00411           X->right->parent = X;
00412           X->right->F.l = 1;
00413         }
00414     
00415         if( X->F.b == 1 )         /* (X.B == -ak)                     */
00416         {
00417           B->F.b = -1;            /* B->B = ak                        */
00418           A->F.b = 0;             /* A->B = 0                         */
00419         }  
00420         else if( X->F.b == -1 )   /* (X.B == ak )                     */
00421         {
00422           B->F.b = 0;             /* B->B = 0                         */
00423           A->F.b = 1;             /* A->B = -ak                       */
00424         }
00425         else           /* (X.B == 0), (Anm: ist der Fall, wenn X == Q)*/ 
00426         {
00427           B->F.b = 0;             /* B->B = 0                         */
00428           A->F.b = 0;             /* A->B = 0                         */
00429         }
00430         X->F.b = 0;               /* X->B = 0                         */
00431 
00432         ak = ak_1;                          /* k-- */
00433         Pk = Pk_1;
00434           
00435         if( ak == -1 )                      /* Wurzel Teilbaum = X */
00436         {
00437           Pk->left = X;
00438           if( Pk->left != NULL )
00439           {
00440             Pk->left->parent = Pk;
00441             Pk->left->F.l = -1;
00442           }
00443         }  
00444         else
00445         {
00446           Pk->right = X;  
00447           if( Pk->right != NULL )
00448           {
00449             Pk->right->parent = Pk;
00450             Pk->right->F.l = 1;
00451           }
00452         }
00453 
00454         return;   /*** fertig ***/
00455       }
00456     }
00457   }
00458 
00459 
00460   else         /*** Ausfuehrung fuer (ak == 1) ***/
00461   {
00462     A = Pk;
00463     Pk_1 = Pk->parent;
00464     ak_1 = Pk->F.l;
00465     
00466     if( A->F.b == -1 )            /* (A->B == -ak)   */    
00467     {
00468       A->F.b = 0;
00469       return;                    /*** fertig ***/
00470     }
00471     else                          /* A->B == ak      */
00472     {
00473       B = Pk->right;              /* B = LINK(A,ak)  */
00474 
00475       if( B->F.b == 1 )           /* (B->B == ak) => Single Rotation */
00476       {
00477         A->right = B->left;       /* LINK(A,ak) = LINK(B,-ak) */     
00478         if( A->right != NULL )
00479         {
00480           A->right->parent = A;
00481           A->right->F.l = 1;
00482         }
00483         
00484         B->left = A;              /* LINK(B,-ak) = A  */
00485         if( B->left != NULL )
00486         {
00487           B->left->parent = B;
00488           B->left->F.l = -1;
00489         }
00490         
00491         A->F.b = B->F.b = 0;
00492 
00493         ak = ak_1;                       /* k-- */
00494         Pk = Pk_1;
00495           
00496         if( ak == -1 )                      /* Wurzel Teilbaum = B */
00497         {
00498           Pk->left = B;
00499           if( Pk->left != NULL )
00500           {
00501             Pk->left->parent = Pk;
00502             Pk->left->F.l = -1;
00503           }
00504         }  
00505         else
00506         {
00507           Pk->right = B;  
00508           if( Pk->right != NULL )
00509           {
00510             Pk->right->parent = Pk;
00511             Pk->right->F.l = 1;
00512           }
00513         }
00514 
00515         return;   /*** fertig ***/
00516       }
00517       else                        /* (B->B == -ak) => Double Rotation */
00518       {
00519         X = B->left;              /* X = LINK(B,-ak)                  */
00520 
00521         A->right = X->left;       /* LINK(A,ak) = LINK(X,-ak)         */
00522         if( A->right != NULL )
00523         {
00524           A->right->parent = A;
00525           A->right->F.l = 1;
00526         }
00527 
00528         B->left = X->right;       /* LINK(B,-ak) = LINK(X,ak)         */
00529         if( B->left != NULL )
00530         {
00531           B->left->parent = B;
00532           B->left->F.l = -1;
00533         }
00534     
00535         X->right = B;             /* LINK(X,ak) = B                   */
00536         if( X->right != NULL )
00537         {
00538           X->right->parent = X;
00539           X->right->F.l = 1;
00540         }
00541             
00542         X->left = A;              /* LINK(X,-ak) = A                  */
00543         if( X->left != NULL )
00544         {
00545           X->left->parent = X;
00546           X->left->F.l = -1;
00547         }
00548         
00549         if( X->F.b == -1 )        /* (X.B == -ak)                     */
00550         {
00551           B->F.b = 1;             /* B->B = ak                        */
00552           A->F.b = 0;             /* A->B = 0                         */
00553         }  
00554         else if( X->F.b == 1 )    /* (X.B == ak )                     */
00555         {
00556           B->F.b = 0;             /* B->B = 0                         */
00557           A->F.b = -1;            /* A->B = -ak                       */
00558         }
00559         else           /* (X.B == 0), (Anm: ist der Fall, wenn X == Q)*/ 
00560         {
00561           B->F.b = 0;             /* B->B = 0                         */
00562           A->F.b = 0;             /* A->B = 0                         */
00563         }
00564         X->F.b = 0;               /* X->B = 0                         */
00565 
00566         ak = ak_1;                          /* k-- */
00567         Pk = Pk_1;
00568           
00569         if( ak == -1 )                      /* Wurzel Teilbaum = X */
00570         {
00571           Pk->left = X;
00572           if( Pk->left != NULL )
00573           {
00574             Pk->left->parent = Pk;
00575             Pk->left->F.l = -1;
00576           }
00577         }  
00578         else
00579         {
00580           Pk->right = X;  
00581           if( Pk->right != NULL )
00582           {
00583             Pk->right->parent = Pk;
00584             Pk->right->F.l = 1;
00585           }
00586         }
00587 
00588         return;   /*** fertig ***/
00589       }
00590     }
00591   }
00592 }
00593 
00594 
00595 
00596 /*------------------------------------------------------------------------
00597   Removes a node 'element' from a balanced binary tree 'head'.
00598   The tree will get rebalanced, if necessary.  
00599 ------------------------------------------------------------------------*/
00600 
00601 GULAPI void DeleteElementFromBBT( BBTNode *element, BBTNode *head )
00602 {
00603   BBTNode *P,*Q,*Pk,*Pk_1,*A,*B,*X;
00604   int ak, ak_1, ak_ini;
00605   
00606   P = head->right;
00607   if( P == NULL ) return;
00608     
00609   P = Q = element;
00610 
00611   if( P->right == NULL )    /* Knoten suchen, bei dem rechter oder */
00612   {                         /* linker Ast = NULL:                  */
00613     Pk = P;
00614     ak = 1;
00615     Pk_1 = Pk->parent;
00616     ak_1 = ak_ini = Pk->F.l;
00617   }
00618   else if( P->left == NULL )
00619   {
00620     Pk = P;
00621     ak = -1;
00622     Pk_1 = Pk->parent;
00623     ak_1 = ak_ini = Pk->F.l;
00624   }
00625   else
00626   {
00627     P = P->right;                    /* nach rechts gehen */    
00628 
00629     if( P->left == NULL )
00630     {
00631       Pk = Q;
00632 
00633       if( Q->F.l == 1 )     
00634       {
00635         Q->parent->right = P;
00636         P->F.l = 1;
00637       }
00638       else
00639       {
00640         Q->parent->left = P;
00641         P->F.l = -1; 
00642       }       
00643       P->parent = Q->parent;
00644       P->F.b = Q->F.b;
00645 
00646       ak = 1;
00647       Pk_1 = P;
00648       ak_1 = -1;    
00649       ak_ini = 1;
00650     }
00651     else
00652     {
00653       do            /* suchen bis Nachfolger in symmetrischer */
00654       {             /* Ordnung gefunden                       */
00655         Pk = P;
00656         P = P->left;
00657       }
00658       while( P != NULL );
00659 
00660       ak = -1;
00661       Pk_1 = Pk->parent;
00662       ak_1 = ak_ini = Pk->F.l;
00663     }
00664   }            
00665 
00666 /* --- Knoten loeschen: -------------------------------------------- */
00667 
00668   if( ak_1 == -1 )                                /* wenn Pk linker Sohn */
00669   {
00670     Pk_1->left = (ak == -1 ? Pk->right : Pk->left);
00671     if( Pk_1->left != NULL )
00672     {
00673       Pk_1->left->parent = Pk_1;
00674       Pk_1->left->F.l = -1;
00675     }
00676   }    
00677   else
00678   {
00679     Pk_1->right = (ak == -1 ? Pk->right : Pk->left);
00680     if( Pk_1->right != NULL )
00681     {
00682       Pk_1->right->parent = Pk_1;
00683       Pk_1->right->F.l = 1;
00684     }
00685   }  
00686 
00687   if( Pk != Q )
00688   {
00689     Pk->left = Q->left;                /* Pk uebernimmt nun die Rolle von Q */
00690     if( Pk->left != NULL )
00691       Pk->left->parent = Pk;
00692     Pk->right = Q->right;
00693     if( Pk->right != NULL )
00694       Pk->right->parent = Pk;
00695 
00696     Pk->F.b = Q->F.b;
00697   
00698     Pk->parent = Q->parent;
00699     Pk->F.l = Q->F.l;
00700     if( Pk->F.l == -1 )
00701       Pk->parent->left = Pk;
00702     else
00703       Pk->parent->right = Pk;
00704   } 
00705                                      /* Q kann jetzt freigeben werden */
00706 
00707 /* --- Balance-Faktoren updaten ------------------------------------- */  
00708 
00709   ak = ak_ini;
00710   Pk = Pk_1;
00711 
00712   while( 1 )
00713   {
00714     if( Pk == head )                       /* Listenkopf */
00715     {
00716       (*((int *)&head->left))--;           /* Hoehe des Baums um 1 erniedrigen */
00717       break;                 /*** fertig ***/
00718     }
00719     else if( Pk->F.b == ak )
00720     {
00721       Pk->F.b = 0;
00722 
00723       ak = Pk->F.l;                       /* k-- */
00724       Pk = Pk->parent;
00725     }
00726     else if( Pk->F.b == 0 )
00727     {
00728       Pk->F.b = -ak;
00729       break;                  /*** fertig ***/
00730     }
00731     else                                 /* rebalancieren erforderlich, */
00732     {                                    /* da (Pk->B == -ak) */
00733       if( ak == -1 )          /*** Ausfuehrung fuer (ak == -1) ***/
00734       {
00735         A = Pk;
00736         ak_1 = Pk->F.l;
00737         Pk_1 = Pk->parent; 
00738 
00739         B = A->right;                     /* B = Zweig auf der anderen Seite */
00740       
00741         if( B->F.b == 1 )                 /* B->B == -ak => Single Rotation */
00742         {
00743           A->right = B->left;             /* LINK(A,-ak) = LINK(B,ak) */
00744           if( A->right != NULL )
00745           {
00746             A->right->parent = A;
00747             A->right->F.l = 1;
00748           }
00749 
00750           B->left = A;                    /* LINK(B,ak) = A */
00751           if( B->left != NULL )
00752           {
00753             B->left->parent = B;
00754             B->left->F.l = -1;
00755           }
00756 
00757           A->F.b = B->F.b = 0;
00758           
00759           ak = ak_1;                       /* k-- */
00760           Pk = Pk_1;
00761           
00762           if( ak == -1 )
00763           {
00764             Pk->left = B;
00765             if( Pk->left != NULL )
00766             {
00767               Pk->left->parent = Pk;
00768               Pk->left->F.l = -1;
00769             }
00770           }  
00771           else
00772           {
00773             Pk->right = B;  
00774             if( Pk->right != NULL )
00775             {
00776               Pk->right->parent = Pk;
00777               Pk->right->F.l = 1;
00778             }
00779           }
00780         }
00781         else if( B->F.b == -1 )           /* (B->B == ak) => Double Rotation */
00782         {
00783           X = B->left;                    /* X = LINK(B,ak) */
00784  
00785           A->right = X->left;             /* LINK(A,-ak) = LINK(X,ak) */
00786           if( A->right != NULL )
00787           {
00788             A->right->parent = A;
00789             A->right->F.l = 1;
00790           }
00791 
00792           B->left = X->right;             /* LINK(B,ak) = LINK(X,-ak) */
00793           if( B->left != NULL )
00794           {
00795             B->left->parent = B;
00796             B->left->F.l = -1;
00797           }
00798           
00799           X->left = A;                    /* LINK(X,ak) = A           */
00800           if( X->left != NULL )
00801           {
00802             X->left->parent = X;
00803             X->left->F.l = -1;
00804           }
00805 
00806           X->right = B;                   /* LINK(X,-ak) = B          */
00807           if( X->right != NULL )
00808           {
00809             X->right->parent = X;
00810             X->right->F.l = 1;
00811           }
00812           
00813           if( X->F.b == -1 )              /* (X->B == ak)             */
00814           {
00815             A->F.b = 0;                   /* A->B = 0                 */
00816             B->F.b = 1;                   /* B->B = -ak               */
00817           }
00818           else if( X->F.b == 1 )          /* (X->B == -ak)            */
00819           {
00820             A->F.b = -1;                  /* A->B = ak                */
00821             B->F.b = 0;                   /* B->B = 0                 */
00822           }
00823           else                            /* B->B = 0                 */
00824           {
00825             A->F.b = 0;
00826             B->F.b = 0;
00827           }
00828           X->F.b = 0; 
00829 
00830           ak = ak_1;                       /* k-- */
00831           Pk = Pk_1;
00832 
00833           if( ak == -1 )
00834           {
00835             Pk->left = X;
00836             if( Pk->left != NULL )
00837             {
00838               Pk->left->parent = Pk;
00839               Pk->left->F.l = -1;
00840             }
00841           }  
00842           else
00843           {
00844             Pk->right = X;  
00845             if( Pk->right != NULL )
00846             {
00847               Pk->right->parent = Pk;
00848               Pk->right->F.l = 1;
00849             }
00850           }
00851         }
00852         else                               /* (B->B == 0) => Single Rotation */
00853         {
00854           A->right = B->left;              /* LINK(A,-ak) = LINK(B,ak)     */
00855           if( A->right != NULL )
00856           {
00857             A->right->parent = A;
00858             A->right->F.l = 1;
00859           }
00860           
00861           B->left = A;                     /* LINK(B,ak) = A               */
00862           if( B->left != NULL )
00863           {
00864             B->left->parent = B;
00865             B->left->F.l = -1;
00866           }
00867 
00868           B->F.b = -1;                     /* B->B = ak                    */
00869 
00870           ak = ak_1;                    /* k-- */
00871           Pk = Pk_1;
00872 
00873           if( ak == -1 )
00874           {
00875             Pk->left = B;
00876             if( Pk->left != NULL )
00877             {
00878               Pk->left->parent = Pk;
00879               Pk->left->F.l = -1;
00880             }
00881           }  
00882           else
00883           {
00884             Pk->right = B;  
00885             if( Pk->right != NULL )
00886             {
00887               Pk->right->parent = Pk;
00888               Pk->right->F.l = 1;
00889             }
00890           }
00891 
00892           break;              /*** fertig ***/
00893         }
00894 
00895 
00896       }
00897       else                    /*** dasselbe nochmal fuer (ak == +1) ***/
00898       {
00899         A = Pk;
00900         ak_1 = Pk->F.l;
00901         Pk_1 = Pk->parent;
00902         
00903         B = A->left;                      /* B = Zweig auf der anderen Seite */
00904       
00905         if( B->F.b == -1 )                /* (B->B == -ak) => Single Rotation */
00906         {
00907           A->left = B->right;             /* LINK(A,-ak) = LINK(B,ak) */
00908           if( A->left != NULL )
00909           {
00910             A->left->parent = A;
00911             A->left->F.l = -1;
00912           }
00913                 
00914           B->right = A;
00915           if( B->right != NULL )
00916           {
00917             B->right->parent = B;
00918             B->right->F.l = 1;
00919           }
00920           
00921           A->F.b = B->F.b = 0;
00922           
00923           ak = ak_1;                       /* k-- */
00924           Pk = Pk_1;
00925         
00926           if( ak == -1 )
00927           {
00928             Pk->left = B;
00929             if( Pk->left != NULL )
00930             {
00931               Pk->left->parent = Pk;
00932               Pk->left->F.l = -1;
00933             }
00934           }  
00935           else
00936           {
00937             Pk->right = B;  
00938             if( Pk->right != NULL )
00939             {
00940               Pk->right->parent = Pk;
00941               Pk->right->F.l = 1;
00942             }
00943           }
00944         }
00945         else if( B->F.b == 1 )            /* (B->B == ak) => Double Rotation */
00946         {
00947           X = B->right;                   /* X = LINK(B,ak) */
00948  
00949           A->left = X->right;             /* LINK(A,-ak) = LINK(X,ak) */
00950           if( A->left != NULL )
00951           {
00952             A->left->parent = A;
00953             A->left->F.l = -1;
00954           }
00955           
00956           B->right = X->left;             /* LINK(B,ak) = LINK(X,-ak) */
00957           if( B->right != NULL )
00958           {
00959             B->right->parent = B;
00960             B->right->F.l = 1;
00961           }
00962 
00963           X->right = A;                   /* LINK(X,ak) = A           */
00964           if( X->right != NULL )
00965           {
00966             X->right->parent = X;
00967             X->right->F.l = 1;
00968           }
00969 
00970           X->left = B;                    /* LINK(X,-ak) = B          */
00971           if( X->left != NULL )
00972           {
00973             X->left->parent = X;
00974             X->left->F.l = -1;
00975           }
00976 
00977           if( X->F.b == 1 )               /* (X->B == ak)             */
00978           {
00979             A->F.b = 0;                   /* A->B = 0                 */
00980             B->F.b = -1;                  /* B->B = -ak               */
00981           }
00982           else if( X->F.b == -1 )         /* (X->B == -ak)            */
00983           {
00984             A->F.b = 1;                   /* A->B = ak                */
00985             B->F.b = 0;                   /* B->B = 0                 */
00986           }
00987           else                            /* B->B = 0                 */
00988           {
00989             A->F.b = 0;
00990             B->F.b = 0;
00991           }  
00992           X->F.b = 0;
00993 
00994           ak = ak_1;                       /* k-- */
00995           Pk = Pk_1;
00996         
00997           if( ak == -1 )
00998           {
00999             Pk->left = X;
01000             if( Pk->left != NULL )
01001             {
01002               Pk->left->parent = Pk;
01003               Pk->left->F.l = -1;
01004             }
01005           }  
01006           else
01007           {
01008             Pk->right = X;  
01009             if( Pk->right != NULL )
01010             {
01011               Pk->right->parent = Pk;
01012               Pk->right->F.l = 1;
01013             }
01014           }
01015         }
01016         else                               /* (B->B == 0) => Single Rotation */
01017         {
01018           A->left = B->right;              /* LINK(A,-ak) = LINK(B,ak)     */
01019           if( A->left != NULL )
01020           {
01021             A->left->parent = A;
01022             A->left->F.l = -1;
01023           }
01024 
01025           B->right = A;                    /* LINK(B,ak) = A               */
01026           if( B->right != NULL )
01027           {
01028             B->right->parent = B;
01029             B->right->F.l = 1;
01030           }
01031           
01032           B->F.b = 1;                      /* B->B = ak                    */
01033 
01034           ak = ak_1;                    /* k-- */
01035           Pk = Pk_1;
01036         
01037           if( ak == -1 )
01038           {
01039             Pk->left = B;
01040             if( Pk->left != NULL )
01041             {
01042               Pk->left->parent = Pk;
01043               Pk->left->F.l = -1;
01044             }
01045           }  
01046           else
01047           {
01048             Pk->right = B;  
01049             if( Pk->right != NULL )
01050             {
01051               Pk->right->parent = Pk;
01052               Pk->right->F.l = 1;
01053             }
01054           }
01055 
01056           break;              /*** fertig ***/
01057         }
01058       }
01059     }    /*** Ende "while"-Schleife ***/
01060   }
01061     
01062   return;
01063 }                                   
01064                  
01065 /*------------------------------------------------------------------------
01066   Dump BBT Tree (for debugging)
01067 ------------------------------------------------------------------------*/  
01068 
01069 GULAPI void DumpBBTTree( BBTNode *node, int level,  
01070                          void dumpkey_func( void * ) )
01071 {
01072   int i;
01073 
01074   if( node == NULL )
01075     return;
01076     
01077   if( node->left != NULL )
01078     DumpBBTTree( node->left, level+4, dumpkey_func );
01079 
01080   for( i = 0; i < level; i++ )
01081   {
01082     cout << " ";
01083   }
01084 
01085   if( node->key != NULL )
01086     dumpkey_func( node->key );
01087     cout << "\n";
01088 
01089   if( node->right != NULL )
01090     DumpBBTTree( node->right, level+4, dumpkey_func );
01091 }
01092 
01093 /*------------------------------------------------------------------------
01094   Dump BBT Tree (for debugging)
01095 ------------------------------------------------------------------------*/  
01096 
01097 GULAPI void DumpBBTNode( BBTNode *node, int level )
01098 {
01099   int i;
01100 
01101   if( node == NULL )
01102     return;
01103     
01104   if( node->left != NULL )
01105     DumpBBTNode( node->left, level+4 );
01106 
01107   for( i = 0; i < level; i++ )
01108   {
01109     cout << " ";
01110   }
01111   cout << (void *)node << ":[b:" << node->F.b << ", l:" << node->F.l <<
01112        "] (l=" << (void *)node->left << ", r=" <<
01113        (void *)node->right << ", p=" << (void *)node->parent << ")\n";
01114 
01115   if( node->right != NULL )
01116     DumpBBTNode( node->right, level+4 );
01117 }
01118 
01119 
01120 }
01121 
01122 
01123 
01124 
01125 
01126 
01127 
01128 
01129 
01130 

Generated on Mon Jan 21 04:17:35 2002 for GUL 0.6 - Geometry Utility Library by doxygen1.2.13.1 written by Dimitri van Heesch, © 1997-2001