sot/source/sdstor/stgavl.cxx

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