stgavl.cxx (046d9d1f) | stgavl.cxx (297a844a) |
---|---|
1/************************************************************** 2 * 3 * Licensed to the Apache Software Foundation (ASF) under one 4 * or more contributor license agreements. See the NOTICE file 5 * distributed with this work for additional information 6 * regarding copyright ownership. The ASF licenses this file 7 * to you under the Apache License, Version 2.0 (the 8 * "License"); you may not use this file except in compliance --- 10 unchanged lines hidden (view full) --- 19 * 20 *************************************************************/ 21 22 23 24// MARKER(update_precomp.py): autogen include statement, do not remove 25#include "precompiled_sot.hxx" 26 | 1/************************************************************** 2 * 3 * Licensed to the Apache Software Foundation (ASF) under one 4 * or more contributor license agreements. See the NOTICE file 5 * distributed with this work for additional information 6 * regarding copyright ownership. The ASF licenses this file 7 * to you under the Apache License, Version 2.0 (the 8 * "License"); you may not use this file except in compliance --- 10 unchanged lines hidden (view full) --- 19 * 20 *************************************************************/ 21 22 23 24// MARKER(update_precomp.py): autogen include statement, do not remove 25#include "precompiled_sot.hxx" 26 |
27 | 27#include <osl/diagnose.h> |
28#include "stgavl.hxx" 29 30StgAvlNode::StgAvlNode() 31{ 32 pLeft = pRight = NULL; 33 nBalance = nId = 0; 34} 35 36StgAvlNode::~StgAvlNode() 37{ 38 delete pLeft; 39 delete pRight; 40} 41 42StgAvlNode* StgAvlNode::Find( StgAvlNode* pFind ) 43{ | 28#include "stgavl.hxx" 29 30StgAvlNode::StgAvlNode() 31{ 32 pLeft = pRight = NULL; 33 nBalance = nId = 0; 34} 35 36StgAvlNode::~StgAvlNode() 37{ 38 delete pLeft; 39 delete pRight; 40} 41 42StgAvlNode* StgAvlNode::Find( StgAvlNode* pFind ) 43{ |
44 StgAvlNode* p = this; 45 while( p ) | 44 if ( pFind ) |
46 { | 45 { |
47 short nRes = p->Compare( pFind ); 48 if( !nRes ) 49 return p; 50 else p = ( nRes < 0 ) ? p->pLeft : p->pRight; | 46 StgAvlNode* p = this; 47 while( p ) 48 { 49 short nRes = p->Compare( pFind ); 50 if( !nRes ) 51 return p; 52 else p = ( nRes < 0 ) ? p->pLeft : p->pRight; 53 } |
51 } 52 return NULL; 53} 54 55// find point to add node to AVL tree and returns 56// +/0/- for >/=/< previous 57 58short StgAvlNode::Locate 59 ( StgAvlNode* pFind, 60 StgAvlNode** pPivot, StgAvlNode **pParent, StgAvlNode** pPrev ) 61{ 62 short nRes = 0; 63 StgAvlNode* pCur = this; | 54 } 55 return NULL; 56} 57 58// find point to add node to AVL tree and returns 59// +/0/- for >/=/< previous 60 61short StgAvlNode::Locate 62 ( StgAvlNode* pFind, 63 StgAvlNode** pPivot, StgAvlNode **pParent, StgAvlNode** pPrev ) 64{ 65 short nRes = 0; 66 StgAvlNode* pCur = this; |
67 68 OSL_ENSURE( pPivot && pParent && pPrev, "The pointers may not be NULL!" ); |
|
64 *pParent = *pPrev = NULL; 65 *pPivot = this; 66 67 // search tree for insertion point | 69 *pParent = *pPrev = NULL; 70 *pPivot = this; 71 72 // search tree for insertion point |
68 69 while( pCur != NULL ) | 73 if ( pFind ) |
70 { | 74 { |
71 // check for pPivot 72 if( pCur->nBalance != 0 ) 73 *pPivot = pCur, *pParent = *pPrev; 74 // save pPrev location and see what direction to go 75 *pPrev = pCur; 76 nRes = pCur->Compare( pFind ); 77 if( nRes == 0 ) 78 break; 79 else pCur = ( nRes < 0 ) ? pCur->pLeft : pCur->pRight; | 75 while( pCur != NULL ) 76 { 77 // check for pPivot 78 if( pCur->nBalance != 0 ) 79 *pPivot = pCur, *pParent = *pPrev; 80 // save pPrev location and see what direction to go 81 *pPrev = pCur; 82 nRes = pCur->Compare( pFind ); 83 if( nRes == 0 ) 84 break; 85 else pCur = ( nRes < 0 ) ? pCur->pLeft : pCur->pRight; 86 } |
80 } | 87 } |
88 |
|
81 return( nRes ); 82} 83 84// adjust balance factors in AVL tree from pivot down. 85// Returns delta balance. 86 87short StgAvlNode::Adjust( StgAvlNode** pHeavy, StgAvlNode* pNew ) 88{ 89 StgAvlNode* pCur = this; 90 short nDelta; 91 // no traversing | 89 return( nRes ); 90} 91 92// adjust balance factors in AVL tree from pivot down. 93// Returns delta balance. 94 95short StgAvlNode::Adjust( StgAvlNode** pHeavy, StgAvlNode* pNew ) 96{ 97 StgAvlNode* pCur = this; 98 short nDelta; 99 // no traversing |
92 if( pCur == pNew ) | 100 OSL_ENSURE( pHeavy && pNew, "The pointers is not allowed to be NULL!" ); 101 if( pCur == pNew || !pNew ) |
93 return nBalance; | 102 return nBalance; |
103 |
|
94 short nRes = Compare( pNew ); 95 if( nRes > 0 ) 96 { 97 *pHeavy = pCur = pRight; 98 nDelta = -1; 99 } 100 else 101 { --- 20 unchanged lines hidden (view full) --- 122 nBalance = nBalance + nDelta; 123 return nDelta; 124} 125 126// perform LL rotation and return new root 127 128StgAvlNode* StgAvlNode::RotLL() 129{ | 104 short nRes = Compare( pNew ); 105 if( nRes > 0 ) 106 { 107 *pHeavy = pCur = pRight; 108 nDelta = -1; 109 } 110 else 111 { --- 20 unchanged lines hidden (view full) --- 132 nBalance = nBalance + nDelta; 133 return nDelta; 134} 135 136// perform LL rotation and return new root 137 138StgAvlNode* StgAvlNode::RotLL() 139{ |
140 OSL_ENSURE( pLeft, "The pointer is not allowed to be NULL!" ); |
|
130 StgAvlNode *pHeavy = pLeft; 131 pLeft = pHeavy->pRight; 132 pHeavy->pRight = this; 133 pHeavy->nBalance = nBalance = 0; 134 return pHeavy; 135} 136 137// perform LR rotation and return new root 138 139StgAvlNode* StgAvlNode::RotLR() 140{ | 141 StgAvlNode *pHeavy = pLeft; 142 pLeft = pHeavy->pRight; 143 pHeavy->pRight = this; 144 pHeavy->nBalance = nBalance = 0; 145 return pHeavy; 146} 147 148// perform LR rotation and return new root 149 150StgAvlNode* StgAvlNode::RotLR() 151{ |
141 | 152 OSL_ENSURE( pLeft && pLeft->pRight, "The pointer is not allowed to be NULL!" ); |
142 StgAvlNode* pHeavy = pLeft; 143 StgAvlNode* pNewRoot = pHeavy->pRight; 144 145 pHeavy->pRight = pNewRoot->pLeft; 146 pLeft = pNewRoot->pRight; 147 pNewRoot->pLeft = pHeavy; 148 pNewRoot->pRight = this; 149 --- 15 unchanged lines hidden (view full) --- 165 pNewRoot->nBalance = 0; 166 return pNewRoot; 167} 168 169// perform RR rotation and return new root 170 171StgAvlNode* StgAvlNode::RotRR() 172{ | 153 StgAvlNode* pHeavy = pLeft; 154 StgAvlNode* pNewRoot = pHeavy->pRight; 155 156 pHeavy->pRight = pNewRoot->pLeft; 157 pLeft = pNewRoot->pRight; 158 pNewRoot->pLeft = pHeavy; 159 pNewRoot->pRight = this; 160 --- 15 unchanged lines hidden (view full) --- 176 pNewRoot->nBalance = 0; 177 return pNewRoot; 178} 179 180// perform RR rotation and return new root 181 182StgAvlNode* StgAvlNode::RotRR() 183{ |
184 OSL_ENSURE( pRight, "The pointer is not allowed to be NULL!" ); |
|
173 StgAvlNode* pHeavy = pRight; 174 pRight = pHeavy->pLeft; 175 pHeavy->pLeft = this; 176 nBalance = pHeavy->nBalance = 0; 177 return pHeavy; 178} 179 180// perform the RL rotation and return the new root 181 182StgAvlNode* StgAvlNode::RotRL() 183{ | 185 StgAvlNode* pHeavy = pRight; 186 pRight = pHeavy->pLeft; 187 pHeavy->pLeft = this; 188 nBalance = pHeavy->nBalance = 0; 189 return pHeavy; 190} 191 192// perform the RL rotation and return the new root 193 194StgAvlNode* StgAvlNode::RotRL() 195{ |
196 OSL_ENSURE( pRight && pRight->pLeft, "The pointer is not allowed to be NULL!" ); |
|
184 StgAvlNode* pHeavy = pRight; 185 StgAvlNode* pNewRoot = pHeavy->pLeft; 186 pHeavy->pLeft = pNewRoot->pRight; 187 pRight = pNewRoot->pLeft; 188 pNewRoot->pRight = pHeavy; 189 pNewRoot->pLeft = this; 190 switch( pNewRoot->nBalance ) 191 { --- 13 unchanged lines hidden (view full) --- 205 pNewRoot->nBalance = 0; 206 return pNewRoot; 207} 208 209// Remove a tree element. Return the removed element or NULL. 210 211StgAvlNode* StgAvlNode::Rem( StgAvlNode** p, StgAvlNode* pDel, sal_Bool bPtrs ) 212{ | 197 StgAvlNode* pHeavy = pRight; 198 StgAvlNode* pNewRoot = pHeavy->pLeft; 199 pHeavy->pLeft = pNewRoot->pRight; 200 pRight = pNewRoot->pLeft; 201 pNewRoot->pRight = pHeavy; 202 pNewRoot->pLeft = this; 203 switch( pNewRoot->nBalance ) 204 { --- 13 unchanged lines hidden (view full) --- 218 pNewRoot->nBalance = 0; 219 return pNewRoot; 220} 221 222// Remove a tree element. Return the removed element or NULL. 223 224StgAvlNode* StgAvlNode::Rem( StgAvlNode** p, StgAvlNode* pDel, sal_Bool bPtrs ) 225{ |
213 if( *p ) | 226 if( p && *p && pDel ) |
214 { 215 StgAvlNode* pCur = *p; 216 short nRes = bPtrs ? short( pCur == pDel ) : short(pCur->Compare( pDel )); 217 if( !nRes ) 218 { 219 // Element found: remove 220 if( !pCur->pRight ) 221 { --- 37 unchanged lines hidden (view full) --- 259 } 260 return NULL; 261} 262 263// Enumerate the tree for later iteration 264 265void StgAvlNode::StgEnum( short& n ) 266{ | 227 { 228 StgAvlNode* pCur = *p; 229 short nRes = bPtrs ? short( pCur == pDel ) : short(pCur->Compare( pDel )); 230 if( !nRes ) 231 { 232 // Element found: remove 233 if( !pCur->pRight ) 234 { --- 37 unchanged lines hidden (view full) --- 272 } 273 return NULL; 274} 275 276// Enumerate the tree for later iteration 277 278void StgAvlNode::StgEnum( short& n ) 279{ |
267 if( this ) 268 { 269 if( pLeft ) 270 pLeft->StgEnum( n ); 271 nId = n++; 272 if( pRight ) 273 pRight->StgEnum( n ); 274 } | 280 if( pLeft ) 281 pLeft->StgEnum( n ); 282 nId = n++; 283 if( pRight ) 284 pRight->StgEnum( n ); |
275} 276 277// Add node to AVL tree. 278// Return sal_False if the element already exists. 279 280sal_Bool StgAvlNode::Insert( StgAvlNode** pRoot, StgAvlNode* pIns ) 281{ 282 StgAvlNode* pPivot, *pHeavy, *pNewRoot, *pParent, *pPrev; | 285} 286 287// Add node to AVL tree. 288// Return sal_False if the element already exists. 289 290sal_Bool StgAvlNode::Insert( StgAvlNode** pRoot, StgAvlNode* pIns ) 291{ 292 StgAvlNode* pPivot, *pHeavy, *pNewRoot, *pParent, *pPrev; |
293 if ( !pRoot ) 294 return sal_False; 295 |
|
283 // special case - empty tree 284 if( *pRoot == NULL ) 285 { 286 *pRoot = pIns; 287 return sal_True; 288 } 289 // find insertion point and return if already present 290 short nRes = (*pRoot)->Locate( pIns, &pPivot, &pParent, &pPrev ); 291 if( !nRes ) 292 return sal_False; | 296 // special case - empty tree 297 if( *pRoot == NULL ) 298 { 299 *pRoot = pIns; 300 return sal_True; 301 } 302 // find insertion point and return if already present 303 short nRes = (*pRoot)->Locate( pIns, &pPivot, &pParent, &pPrev ); 304 if( !nRes ) 305 return sal_False; |
306 OSL_ENSURE( pPivot && pPrev, "The pointers may not be NULL!" ); 307 |
|
293 // add new node 294 if( nRes < 0 ) 295 pPrev->pLeft = pIns; 296 else 297 pPrev->pRight = pIns; 298 // rebalance tree 299 short nDelta = pPivot->Adjust( &pHeavy, pIns ); 300 if( pPivot->nBalance >= 2 || pPivot->nBalance <= -2 ) --- 21 unchanged lines hidden (view full) --- 322 return sal_True; 323} 324 325// Remove node from tree. Returns sal_True is found and removed. 326// Actually delete if bDel 327 328sal_Bool StgAvlNode::Remove( StgAvlNode** pRoot, StgAvlNode* pDel, sal_Bool bDel ) 329{ | 308 // add new node 309 if( nRes < 0 ) 310 pPrev->pLeft = pIns; 311 else 312 pPrev->pRight = pIns; 313 // rebalance tree 314 short nDelta = pPivot->Adjust( &pHeavy, pIns ); 315 if( pPivot->nBalance >= 2 || pPivot->nBalance <= -2 ) --- 21 unchanged lines hidden (view full) --- 337 return sal_True; 338} 339 340// Remove node from tree. Returns sal_True is found and removed. 341// Actually delete if bDel 342 343sal_Bool StgAvlNode::Remove( StgAvlNode** pRoot, StgAvlNode* pDel, sal_Bool bDel ) 344{ |
345 if ( !pRoot ) 346 return sal_False; 347 |
|
330 // special case - empty tree 331 if( *pRoot == NULL ) 332 return sal_False; 333 // delete the element 334 pDel = Rem( pRoot, pDel, sal_False ); 335 if( pDel ) 336 { 337 if( bDel ) --- 14 unchanged lines hidden (view full) --- 352} 353 354// Move node to a different tree. Returns sal_True is found and moved. This routine 355// may be called when the key has changed. 356 357sal_Bool StgAvlNode::Move 358 ( StgAvlNode** pRoot1, StgAvlNode** pRoot2, StgAvlNode* pMove ) 359{ | 348 // special case - empty tree 349 if( *pRoot == NULL ) 350 return sal_False; 351 // delete the element 352 pDel = Rem( pRoot, pDel, sal_False ); 353 if( pDel ) 354 { 355 if( bDel ) --- 14 unchanged lines hidden (view full) --- 370} 371 372// Move node to a different tree. Returns sal_True is found and moved. This routine 373// may be called when the key has changed. 374 375sal_Bool StgAvlNode::Move 376 ( StgAvlNode** pRoot1, StgAvlNode** pRoot2, StgAvlNode* pMove ) 377{ |
378 if ( !pRoot1 ) 379 return sal_False; 380 |
|
360 // special case - empty tree 361 if( *pRoot1 == NULL ) 362 return sal_False; 363 pMove = Rem( pRoot1, pMove, sal_False ); 364 if( pMove ) 365 return Insert( pRoot2, pMove ); 366 else 367 return sal_False; --- 48 unchanged lines hidden --- | 381 // special case - empty tree 382 if( *pRoot1 == NULL ) 383 return sal_False; 384 pMove = Rem( pRoot1, pMove, sal_False ); 385 if( pMove ) 386 return Insert( pRoot2, pMove ); 387 else 388 return sal_False; --- 48 unchanged lines hidden --- |