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 ---