sot/source/sdstor/stgavl.cxx

   1 /*************************************************************************
   2  *
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * Copyright 2008 by Sun Microsystems, Inc.
   6  *
   7  * OpenOffice.org - a multi-platform office productivity suite
   8  *
   9  * $RCSfile: stgavl.cxx,v $
  10  * $Revision: 1.6 $
  11  *
  12  * This file is part of OpenOffice.org.
  13  *
  14  * OpenOffice.org is free software: you can redistribute it and/or modify
  15  * it under the terms of the GNU Lesser General Public License version 3
  16  * only, as published by the Free Software Foundation.
  17  *
  18  * OpenOffice.org is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  21  * GNU Lesser General Public License version 3 for more details
  22  * (a copy is included in the LICENSE file that accompanied this code).
  23  *
  24  * You should have received a copy of the GNU Lesser General Public License
  25  * version 3 along with OpenOffice.org.  If not, see
  26  * <http://www.openoffice.org/license.html>
  27  * for a copy of the LGPLv3 License.
  28  *
  29  ************************************************************************/
  30
  31 // MARKER(update_precomp.py): autogen include statement, do not remove
  32 #include "precompiled_sot.hxx"
  33
  34
  35 #include "stgavl.hxx"
  36
  37 StgAvlNode::StgAvlNode()
  38 {
  39     pLeft = pRight = NULL;
  40     nBalance = nId = 0;
  41 }
  42
  43 StgAvlNode::~StgAvlNode()
  44 {
  45     delete pLeft;
  46     delete pRight;
  47 }
  48
  49 StgAvlNode* StgAvlNode::Find( StgAvlNode* pFind )
  50 {
  51     StgAvlNode* p = this;
  52     while( p )
  53     {
  54         short nRes = p->Compare( pFind );
  55         if( !nRes )
  56             return p;
  57         else p = ( nRes < 0 ) ? p->pLeft : p->pRight;
  58     }
  59     return NULL;
  60 }
  61
  62 // find point to add node to AVL tree and returns
  63 // +/0/- for >/=/< previous
  64
  65 short StgAvlNode::Locate
  66     ( StgAvlNode* pFind,
  67       StgAvlNode** pPivot, StgAvlNode **pParent, StgAvlNode** pPrev )
  68 {
  69     short nRes = 0;
  70     StgAvlNode* pCur = this;
  71     *pParent = *pPrev = NULL;
  72     *pPivot = this;
  73
  74     // search tree for insertion point
  75
  76     while( pCur != NULL )
  77     {
  78         // check for pPivot
  79         if( pCur->nBalance != 0 )
  80             *pPivot = pCur, *pParent = *pPrev;
  81         // save pPrev location and see what direction to go
  82         *pPrev = pCur;
  83         nRes = pCur->Compare( pFind );
  84         if( nRes == 0 )
  85             break;
  86         else pCur = ( nRes < 0 ) ? pCur->pLeft : pCur->pRight;
  87     }
  88     return( nRes );
  89 }
  90
  91 // adjust balance factors in AVL tree from pivot down.
  92 // Returns delta balance.
  93
  94 short StgAvlNode::Adjust( StgAvlNode** pHeavy, StgAvlNode* pNew )
  95 {
  96     StgAvlNode* pCur = this;
  97     short nDelta;
  98     // no traversing
  99     if( pCur == pNew )
 100         return nBalance;
 101     short nRes = Compare( pNew );
 102     if( nRes > 0 )
 103     {
 104         *pHeavy = pCur = pRight;
 105         nDelta = -1;
 106     }
 107     else
 108     {
 109         *pHeavy = pCur = pLeft;
 110         nDelta = 1;
 111     }
 112     nBalance = 0;
 113     while( pCur != pNew )
 114     {
 115         nRes = pCur->Compare( pNew );
 116         if( nRes > 0 )
 117         {
 118             // height of right increases by 1
 119             pCur->nBalance = -1;
 120             pCur = pCur->pRight;
 121         }
 122         else
 123         {
 124             // height of left increases by 1
 125             pCur->nBalance = 1;
 126             pCur = pCur->pLeft;
 127         }
 128     }
 129     nBalance = nBalance + nDelta;
 130     return nDelta;
 131 }
 132
 133 // perform LL rotation and return new root
 134
 135 StgAvlNode* StgAvlNode::RotLL()
 136 {
 137     StgAvlNode *pHeavy = pLeft;
 138     pLeft = pHeavy->pRight;
 139     pHeavy->pRight = this;
 140     pHeavy->nBalance = nBalance = 0;
 141     return pHeavy;
 142 }
 143
 144 // perform LR rotation and return new root
 145
 146 StgAvlNode* StgAvlNode::RotLR()
 147 {
 148
 149     StgAvlNode* pHeavy = pLeft;
 150     StgAvlNode* pNewRoot = pHeavy->pRight;
 151
 152     pHeavy->pRight = pNewRoot->pLeft;
 153     pLeft = pNewRoot->pRight;
 154     pNewRoot->pLeft = pHeavy;
 155     pNewRoot->pRight = this;
 156
 157     switch( pNewRoot->nBalance )
 158     {
 159         case 1:     // LR( b )
 160             nBalance = -1;
 161             pHeavy->nBalance = 0;
 162             break;
 163         case -1:    // LR( c )
 164             pHeavy->nBalance = 1;
 165             nBalance = 0;
 166             break;
 167         case 0:     // LR( a )
 168             nBalance = 0;
 169             pHeavy->nBalance = 0;
 170             break;
 171     }
 172     pNewRoot->nBalance = 0;
 173     return pNewRoot;
 174 }
 175
 176 // perform RR rotation and return new root
 177
 178 StgAvlNode* StgAvlNode::RotRR()
 179 {
 180     StgAvlNode* pHeavy = pRight;
 181     pRight = pHeavy->pLeft;
 182     pHeavy->pLeft = this;
 183     nBalance = pHeavy->nBalance = 0;
 184     return pHeavy;
 185 }
 186
 187 // perform the RL rotation and return the new root
 188
 189 StgAvlNode* StgAvlNode::RotRL()
 190 {
 191     StgAvlNode* pHeavy = pRight;
 192     StgAvlNode* pNewRoot = pHeavy->pLeft;
 193     pHeavy->pLeft = pNewRoot->pRight;
 194     pRight = pNewRoot->pLeft;
 195     pNewRoot->pRight = pHeavy;
 196     pNewRoot->pLeft = this;
 197     switch( pNewRoot->nBalance )
 198     {
 199         case -1:    // RL( b )
 200             nBalance = 1;
 201             pHeavy->nBalance = 0;
 202             break;
 203         case 1:     // RL( c )
 204             pHeavy->nBalance = -1;
 205             nBalance = 0;
 206             break;
 207         case 0:     // RL( a )
 208             nBalance = 0;
 209             pHeavy->nBalance = 0;
 210             break;
 211     }
 212     pNewRoot->nBalance = 0;
 213     return pNewRoot;
 214 }
 215
 216 // Remove a tree element. Return the removed element or NULL.
 217
 218 StgAvlNode* StgAvlNode::Rem( StgAvlNode** p, StgAvlNode* pDel, BOOL bPtrs )
 219 {
 220     if( *p )
 221     {
 222         StgAvlNode* pCur = *p;
 223         short nRes = bPtrs ? short( pCur == pDel ) : short(pCur->Compare( pDel ));
 224         if( !nRes )
 225         {
 226             // Element found: remove
 227             if( !pCur->pRight )
 228             {
 229                 *p = pCur->pLeft; pCur->pLeft = NULL;
 230             }
 231             else if( !pCur->pLeft )
 232             {
 233                 *p = pCur->pRight; pCur->pRight = NULL;
 234             }
 235             else
 236             {
 237                 // The damn element has two leaves. Get the
 238                 // rightmost element of the left subtree (which
 239                 // is lexically before this element) and replace
 240                 // this element with the element found.
 241                 StgAvlNode* last = pCur;
 242                 StgAvlNode* l;
 243                 for( l = pCur->pLeft;
 244                      l->pRight; last = l, l = l->pRight ) {}
 245                 // remove the element from chain
 246                 if( l == last->pRight )
 247                     last->pRight = l->pLeft;
 248                 else
 249                     last->pLeft = l->pLeft;
 250                 // perform the replacement
 251                 l->pLeft = pCur->pLeft;
 252                 l->pRight = pCur->pRight;
 253                 *p = l;
 254                 // delete the element
 255                 pCur->pLeft = pCur->pRight = NULL;
 256             }
 257             return pCur;
 258         }
 259         else
 260         {
 261             if( nRes < 0 )
 262                 return Rem( &pCur->pLeft, pDel, bPtrs );
 263             else
 264                 return Rem( &pCur->pRight, pDel, bPtrs );
 265         }
 266     }
 267     return NULL;
 268 }
 269
 270 // Enumerate the tree for later iteration
 271
 272 void StgAvlNode::StgEnum( short& n )
 273 {
 274     if( this )
 275     {
 276         if( pLeft )
 277             pLeft->StgEnum( n );
 278         nId = n++;
 279         if( pRight )
 280             pRight->StgEnum( n );
 281     }
 282 }
 283
 284 // Add node to AVL tree.
 285 // Return FALSE if the element already exists.
 286
 287 BOOL StgAvlNode::Insert( StgAvlNode** pRoot, StgAvlNode* pIns )
 288 {
 289     StgAvlNode* pPivot, *pHeavy, *pNewRoot, *pParent, *pPrev;
 290     // special case - empty tree
 291     if( *pRoot == NULL )
 292     {
 293         *pRoot = pIns;
 294         return TRUE;
 295     }
 296     // find insertion point and return if already present
 297     short nRes = (*pRoot)->Locate( pIns, &pPivot, &pParent, &pPrev );
 298     if( !nRes )
 299         return FALSE;
 300     // add new node
 301     if( nRes < 0 )
 302         pPrev->pLeft = pIns;
 303     else
 304         pPrev->pRight = pIns;
 305     // rebalance tree
 306     short nDelta = pPivot->Adjust( &pHeavy, pIns );
 307     if( pPivot->nBalance >= 2 || pPivot->nBalance <= -2 )
 308     {
 309         pHeavy = ( nDelta < 0 ) ? pPivot->pRight : pPivot->pLeft;
 310         // left imbalance
 311         if( nDelta > 0 )
 312             if( pHeavy->nBalance == 1 )
 313                 pNewRoot = pPivot->RotLL();
 314             else
 315                 pNewRoot = pPivot->RotLR();
 316         // right imbalance
 317         else if( pHeavy->nBalance == -1 )
 318             pNewRoot = pPivot->RotRR();
 319         else
 320             pNewRoot = pPivot->RotRL();
 321         // relink balanced subtree
 322         if( pParent == NULL )
 323             *pRoot = pNewRoot;
 324         else if( pPivot == pParent->pLeft )
 325             pParent->pLeft = pNewRoot;
 326         else if( pPivot == pParent->pRight )
 327             pParent->pRight = pNewRoot;
 328     }
 329     return TRUE;
 330 }
 331
 332 // Remove node from tree. Returns TRUE is found and removed.
 333 // Actually delete if bDel
 334
 335 BOOL StgAvlNode::Remove( StgAvlNode** pRoot, StgAvlNode* pDel, BOOL bDel )
 336 {
 337     // special case - empty tree
 338     if( *pRoot == NULL )
 339         return FALSE;
 340     // delete the element
 341     pDel = Rem( pRoot, pDel, FALSE );
 342     if( pDel )
 343     {
 344         if( bDel )
 345             delete pDel;
 346         // Rebalance the tree the hard way
 347         // OS 22.09.95: Auf MD's Wunsch auskommentiert wg. Absturz
 348 /*              StgAvlNode* pNew = NULL;
 349         while( *pRoot )
 350         {
 351             StgAvlNode* p = Rem( pRoot, *pRoot, FALSE );
 352             Insert( &pNew, p );
 353         }
 354         *pRoot = pNew;*/
 355         return TRUE;
 356     }
 357     else
 358         return FALSE;
 359 }
 360
 361 // Move node to a different tree. Returns TRUE is found and moved. This routine
 362 // may be called when the key has changed.
 363
 364 BOOL StgAvlNode::Move
 365     ( StgAvlNode** pRoot1, StgAvlNode** pRoot2, StgAvlNode* pMove )
 366 {
 367     // special case - empty tree
 368     if( *pRoot1 == NULL )
 369         return FALSE;
 370     pMove = Rem( pRoot1, pMove, FALSE );
 371     if( pMove )
 372         return Insert( pRoot2, pMove );
 373     else
 374         return FALSE;
 375 }
 376
 377 ////////////////////////// class AvlIterator /////////////////////////
 378
 379 // The iterator walks through a tree one entry by one.
 380
 381 StgAvlIterator::StgAvlIterator( StgAvlNode* p )
 382 {
 383     pRoot = p;
 384     nCount = 0;
 385     if( p )
 386         p->StgEnum( nCount );
 387 }
 388
 389 StgAvlNode* StgAvlIterator::Find( short n )
 390 {
 391     StgAvlNode* p = pRoot;
 392     while( p )
 393     {
 394         if( n == p->nId )
 395             break;
 396         else p = ( n < p->nId ) ? p->pLeft : p->pRight;
 397     }
 398     return p;
 399 }
 400
 401 StgAvlNode* StgAvlIterator::First()
 402 {
 403     nCur = -1;
 404     return Next();
 405 }
 406
 407 StgAvlNode* StgAvlIterator::Last()
 408 {
 409     nCur = nCount;
 410     return Prev();
 411 }
 412
 413 StgAvlNode* StgAvlIterator::Next()
 414 {
 415     return Find( ++nCur );
 416 }
 417
 418 StgAvlNode* StgAvlIterator::Prev()
 419 {
 420     return Find( --nCur );
 421 }
 422