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
9 * with the License. You may obtain a copy of the License at
10 *
11 * http://www.apache.org/licenses/LICENSE-2.0
12 *
13 * Unless required by applicable law or agreed to in writing,
14 * software distributed under the License is distributed on an
15 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16 * KIND, either express or implied. See the License for the
17 * specific language governing permissions and limitations
18 * under the License.
19 *
20 *************************************************************/
21
22
23
24 // MARKER(update_precomp.py): autogen include statement, do not remove
25 #include "precompiled_sot.hxx"
26
27 #include <osl/diagnose.h>
28 #include "stgavl.hxx"
29
StgAvlNode()30 StgAvlNode::StgAvlNode()
31 {
32 pLeft = pRight = NULL;
33 nBalance = nId = 0;
34 }
35
~StgAvlNode()36 StgAvlNode::~StgAvlNode()
37 {
38 delete pLeft;
39 delete pRight;
40 }
41
Find(StgAvlNode * pFind)42 StgAvlNode* StgAvlNode::Find( StgAvlNode* pFind )
43 {
44 if ( pFind )
45 {
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 }
54 }
55 return NULL;
56 }
57
58 // find point to add node to AVL tree and returns
59 // +/0/- for >/=/< previous
60
Locate(StgAvlNode * pFind,StgAvlNode ** pPivot,StgAvlNode ** pParent,StgAvlNode ** pPrev)61 short 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!" );
69 *pParent = *pPrev = NULL;
70 *pPivot = this;
71
72 // search tree for insertion point
73 if ( pFind )
74 {
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 }
87 }
88
89 return( nRes );
90 }
91
92 // adjust balance factors in AVL tree from pivot down.
93 // Returns delta balance.
94
Adjust(StgAvlNode ** pHeavy,StgAvlNode * pNew)95 short StgAvlNode::Adjust( StgAvlNode** pHeavy, StgAvlNode* pNew )
96 {
97 StgAvlNode* pCur = this;
98 short nDelta;
99 // no traversing
100 OSL_ENSURE( pHeavy && pNew, "The pointers is not allowed to be NULL!" );
101 if( pCur == pNew || !pNew )
102 return nBalance;
103
104 short nRes = Compare( pNew );
105 if( nRes > 0 )
106 {
107 *pHeavy = pCur = pRight;
108 nDelta = -1;
109 }
110 else
111 {
112 *pHeavy = pCur = pLeft;
113 nDelta = 1;
114 }
115 nBalance = 0;
116 while( pCur != pNew )
117 {
118 nRes = pCur->Compare( pNew );
119 if( nRes > 0 )
120 {
121 // height of right increases by 1
122 pCur->nBalance = -1;
123 pCur = pCur->pRight;
124 }
125 else
126 {
127 // height of left increases by 1
128 pCur->nBalance = 1;
129 pCur = pCur->pLeft;
130 }
131 }
132 nBalance = nBalance + nDelta;
133 return nDelta;
134 }
135
136 // perform LL rotation and return new root
137
RotLL()138 StgAvlNode* StgAvlNode::RotLL()
139 {
140 OSL_ENSURE( pLeft, "The pointer is not allowed to be NULL!" );
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
RotLR()150 StgAvlNode* StgAvlNode::RotLR()
151 {
152 OSL_ENSURE( pLeft && pLeft->pRight, "The pointer is not allowed to be NULL!" );
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
161 switch( pNewRoot->nBalance )
162 {
163 case 1: // LR( b )
164 nBalance = -1;
165 pHeavy->nBalance = 0;
166 break;
167 case -1: // LR( c )
168 pHeavy->nBalance = 1;
169 nBalance = 0;
170 break;
171 case 0: // LR( a )
172 nBalance = 0;
173 pHeavy->nBalance = 0;
174 break;
175 }
176 pNewRoot->nBalance = 0;
177 return pNewRoot;
178 }
179
180 // perform RR rotation and return new root
181
RotRR()182 StgAvlNode* StgAvlNode::RotRR()
183 {
184 OSL_ENSURE( pRight, "The pointer is not allowed to be NULL!" );
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
RotRL()194 StgAvlNode* StgAvlNode::RotRL()
195 {
196 OSL_ENSURE( pRight && pRight->pLeft, "The pointer is not allowed to be NULL!" );
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 {
205 case -1: // RL( b )
206 nBalance = 1;
207 pHeavy->nBalance = 0;
208 break;
209 case 1: // RL( c )
210 pHeavy->nBalance = -1;
211 nBalance = 0;
212 break;
213 case 0: // RL( a )
214 nBalance = 0;
215 pHeavy->nBalance = 0;
216 break;
217 }
218 pNewRoot->nBalance = 0;
219 return pNewRoot;
220 }
221
222 // Remove a tree element. Return the removed element or NULL.
223
Rem(StgAvlNode ** p,StgAvlNode * pDel,sal_Bool bPtrs)224 StgAvlNode* StgAvlNode::Rem( StgAvlNode** p, StgAvlNode* pDel, sal_Bool bPtrs )
225 {
226 if( p && *p && pDel )
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 {
235 *p = pCur->pLeft; pCur->pLeft = NULL;
236 }
237 else if( !pCur->pLeft )
238 {
239 *p = pCur->pRight; pCur->pRight = NULL;
240 }
241 else
242 {
243 // The damn element has two leaves. Get the
244 // rightmost element of the left subtree (which
245 // is lexically before this element) and replace
246 // this element with the element found.
247 StgAvlNode* last = pCur;
248 StgAvlNode* l;
249 for( l = pCur->pLeft;
250 l->pRight; last = l, l = l->pRight ) {}
251 // remove the element from chain
252 if( l == last->pRight )
253 last->pRight = l->pLeft;
254 else
255 last->pLeft = l->pLeft;
256 // perform the replacement
257 l->pLeft = pCur->pLeft;
258 l->pRight = pCur->pRight;
259 *p = l;
260 // delete the element
261 pCur->pLeft = pCur->pRight = NULL;
262 }
263 return pCur;
264 }
265 else
266 {
267 if( nRes < 0 )
268 return Rem( &pCur->pLeft, pDel, bPtrs );
269 else
270 return Rem( &pCur->pRight, pDel, bPtrs );
271 }
272 }
273 return NULL;
274 }
275
276 // Enumerate the tree for later iteration
277
StgEnum(short & n)278 void StgAvlNode::StgEnum( short& n )
279 {
280 if( pLeft )
281 pLeft->StgEnum( n );
282 nId = n++;
283 if( pRight )
284 pRight->StgEnum( n );
285 }
286
287 // Add node to AVL tree.
288 // Return sal_False if the element already exists.
289
Insert(StgAvlNode ** pRoot,StgAvlNode * pIns)290 sal_Bool StgAvlNode::Insert( StgAvlNode** pRoot, StgAvlNode* pIns )
291 {
292 StgAvlNode* pPivot, *pHeavy, *pNewRoot, *pParent, *pPrev;
293 if ( !pRoot )
294 return sal_False;
295
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
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 )
316 {
317 pHeavy = ( nDelta < 0 ) ? pPivot->pRight : pPivot->pLeft;
318 // left imbalance
319 if( nDelta > 0 )
320 if( pHeavy->nBalance == 1 )
321 pNewRoot = pPivot->RotLL();
322 else
323 pNewRoot = pPivot->RotLR();
324 // right imbalance
325 else if( pHeavy->nBalance == -1 )
326 pNewRoot = pPivot->RotRR();
327 else
328 pNewRoot = pPivot->RotRL();
329 // relink balanced subtree
330 if( pParent == NULL )
331 *pRoot = pNewRoot;
332 else if( pPivot == pParent->pLeft )
333 pParent->pLeft = pNewRoot;
334 else if( pPivot == pParent->pRight )
335 pParent->pRight = pNewRoot;
336 }
337 return sal_True;
338 }
339
340 // Remove node from tree. Returns sal_True is found and removed.
341 // Actually delete if bDel
342
Remove(StgAvlNode ** pRoot,StgAvlNode * pDel,sal_Bool bDel)343 sal_Bool StgAvlNode::Remove( StgAvlNode** pRoot, StgAvlNode* pDel, sal_Bool bDel )
344 {
345 if ( !pRoot )
346 return sal_False;
347
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 )
356 delete pDel;
357 // Rebalance the tree the hard way
358 // OS 22.09.95: Auf MD's Wunsch auskommentiert wg. Absturz
359 /* StgAvlNode* pNew = NULL;
360 while( *pRoot )
361 {
362 StgAvlNode* p = Rem( pRoot, *pRoot, sal_False );
363 Insert( &pNew, p );
364 }
365 *pRoot = pNew;*/
366 return sal_True;
367 }
368 else
369 return sal_False;
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
Move(StgAvlNode ** pRoot1,StgAvlNode ** pRoot2,StgAvlNode * pMove)375 sal_Bool StgAvlNode::Move
376 ( StgAvlNode** pRoot1, StgAvlNode** pRoot2, StgAvlNode* pMove )
377 {
378 if ( !pRoot1 )
379 return sal_False;
380
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;
389 }
390
391 ////////////////////////// class AvlIterator /////////////////////////
392
393 // The iterator walks through a tree one entry by one.
394
StgAvlIterator(StgAvlNode * p)395 StgAvlIterator::StgAvlIterator( StgAvlNode* p )
396 {
397 pRoot = p;
398 nCount = 0;
399 if( p )
400 p->StgEnum( nCount );
401 }
402
Find(short n)403 StgAvlNode* StgAvlIterator::Find( short n )
404 {
405 StgAvlNode* p = pRoot;
406 while( p )
407 {
408 if( n == p->nId )
409 break;
410 else p = ( n < p->nId ) ? p->pLeft : p->pRight;
411 }
412 return p;
413 }
414
First()415 StgAvlNode* StgAvlIterator::First()
416 {
417 nCur = -1;
418 return Next();
419 }
420
Last()421 StgAvlNode* StgAvlIterator::Last()
422 {
423 nCur = nCount;
424 return Prev();
425 }
426
Next()427 StgAvlNode* StgAvlIterator::Next()
428 {
429 return Find( ++nCur );
430 }
431
Prev()432 StgAvlNode* StgAvlIterator::Prev()
433 {
434 return Find( --nCur );
435 }
436
437