Branch data Line data Source code
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 : 17727 : StgAvlNode::StgAvlNode()
24 : : {
25 : 17727 : pLeft = pRight = NULL;
26 : 17727 : nBalance = nId = 0;
27 : 17727 : }
28 : :
29 : 17617 : StgAvlNode::~StgAvlNode()
30 : : {
31 [ + + ]: 17617 : delete pLeft;
32 [ + + ]: 17617 : delete pRight;
33 [ - + ]: 17617 : }
34 : :
35 : 11350 : StgAvlNode* StgAvlNode::Find( StgAvlNode* pFind )
36 : : {
37 [ + - ]: 11350 : if ( pFind )
38 : : {
39 : 11350 : StgAvlNode* p = this;
40 [ + + ]: 93653 : while( p )
41 : : {
42 : 89575 : short nRes = p->Compare( pFind );
43 [ + + ]: 89575 : if( !nRes )
44 : 7272 : return p;
45 [ + + ]: 82303 : else p = ( nRes < 0 ) ? p->pLeft : p->pRight;
46 : : }
47 : : }
48 : 11350 : return NULL;
49 : : }
50 : :
51 : : // find point to add node to AVL tree and returns
52 : : // +/0/- for >/=/< previous
53 : :
54 : 4896 : short StgAvlNode::Locate
55 : : ( StgAvlNode* pFind,
56 : : StgAvlNode** pPivot, StgAvlNode **pParent, StgAvlNode** pPrev )
57 : : {
58 : 4896 : short nRes = 0;
59 : 4896 : StgAvlNode* pCur = this;
60 : :
61 : : OSL_ENSURE( pPivot && pParent && pPrev, "The pointers may not be NULL!" );
62 : 4896 : *pParent = *pPrev = NULL;
63 : 4896 : *pPivot = this;
64 : :
65 : : // search tree for insertion point
66 [ + - ]: 4896 : if ( pFind )
67 : : {
68 [ + + ]: 30806 : while( pCur != NULL )
69 : : {
70 : : // check for pPivot
71 [ + + ]: 25910 : if( pCur->nBalance != 0 )
72 : 22184 : *pPivot = pCur, *pParent = *pPrev;
73 : : // save pPrev location and see what direction to go
74 : 25910 : *pPrev = pCur;
75 : 25910 : nRes = pCur->Compare( pFind );
76 [ - + ]: 25910 : if( nRes == 0 )
77 : 0 : break;
78 [ + + ]: 25910 : else pCur = ( nRes < 0 ) ? pCur->pLeft : pCur->pRight;
79 : : }
80 : : }
81 : :
82 : 4896 : return( nRes );
83 : : }
84 : :
85 : : // adjust balance factors in AVL tree from pivot down.
86 : : // Returns delta balance.
87 : :
88 : 4896 : short StgAvlNode::Adjust( StgAvlNode** pHeavy, StgAvlNode* pNew )
89 : : {
90 : 4896 : StgAvlNode* pCur = this;
91 : : short nDelta;
92 : : // no traversing
93 : : OSL_ENSURE( pHeavy && pNew, "The pointers is not allowed to be NULL!" );
94 [ + - ][ - + ]: 4896 : if( pCur == pNew || !pNew )
95 : 0 : return nBalance;
96 : :
97 : 4896 : short nRes = Compare( pNew );
98 [ + + ]: 4896 : if( nRes > 0 )
99 : : {
100 : 3591 : *pHeavy = pCur = pRight;
101 : 3591 : nDelta = -1;
102 : : }
103 : : else
104 : : {
105 : 1305 : *pHeavy = pCur = pLeft;
106 : 1305 : nDelta = 1;
107 : : }
108 : 4896 : nBalance = 0;
109 [ + + ]: 7781 : while( pCur != pNew )
110 : : {
111 : 2885 : nRes = pCur->Compare( pNew );
112 [ + + ]: 2885 : if( nRes > 0 )
113 : : {
114 : : // height of right increases by 1
115 : 1972 : pCur->nBalance = -1;
116 : 1972 : pCur = pCur->pRight;
117 : : }
118 : : else
119 : : {
120 : : // height of left increases by 1
121 : 913 : pCur->nBalance = 1;
122 : 913 : pCur = pCur->pLeft;
123 : : }
124 : : }
125 : 4896 : nBalance = nBalance + nDelta;
126 : 4896 : return nDelta;
127 : : }
128 : :
129 : : // perform LL rotation and return new root
130 : :
131 : 0 : StgAvlNode* StgAvlNode::RotLL()
132 : : {
133 : : OSL_ENSURE( pLeft, "The pointer is not allowed to be NULL!" );
134 : 0 : StgAvlNode *pHeavy = pLeft;
135 : 0 : pLeft = pHeavy->pRight;
136 : 0 : pHeavy->pRight = this;
137 : 0 : pHeavy->nBalance = nBalance = 0;
138 : 0 : return pHeavy;
139 : : }
140 : :
141 : : // perform LR rotation and return new root
142 : :
143 : 0 : StgAvlNode* StgAvlNode::RotLR()
144 : : {
145 : : OSL_ENSURE( pLeft && pLeft->pRight, "The pointer is not allowed to be NULL!" );
146 : 0 : StgAvlNode* pHeavy = pLeft;
147 : 0 : StgAvlNode* pNewRoot = pHeavy->pRight;
148 : :
149 : 0 : pHeavy->pRight = pNewRoot->pLeft;
150 : 0 : pLeft = pNewRoot->pRight;
151 : 0 : pNewRoot->pLeft = pHeavy;
152 : 0 : pNewRoot->pRight = this;
153 : :
154 [ # # # # ]: 0 : switch( pNewRoot->nBalance )
155 : : {
156 : : case 1: // LR( b )
157 : 0 : nBalance = -1;
158 : 0 : pHeavy->nBalance = 0;
159 : 0 : break;
160 : : case -1: // LR( c )
161 : 0 : pHeavy->nBalance = 1;
162 : 0 : nBalance = 0;
163 : 0 : break;
164 : : case 0: // LR( a )
165 : 0 : nBalance = 0;
166 : 0 : pHeavy->nBalance = 0;
167 : 0 : break;
168 : : }
169 : 0 : pNewRoot->nBalance = 0;
170 : 0 : return pNewRoot;
171 : : }
172 : :
173 : : // perform RR rotation and return new root
174 : :
175 : 0 : StgAvlNode* StgAvlNode::RotRR()
176 : : {
177 : : OSL_ENSURE( pRight, "The pointer is not allowed to be NULL!" );
178 : 0 : StgAvlNode* pHeavy = pRight;
179 : 0 : pRight = pHeavy->pLeft;
180 : 0 : pHeavy->pLeft = this;
181 : 0 : nBalance = pHeavy->nBalance = 0;
182 : 0 : return pHeavy;
183 : : }
184 : :
185 : : // perform the RL rotation and return the new root
186 : :
187 : 0 : StgAvlNode* StgAvlNode::RotRL()
188 : : {
189 : : OSL_ENSURE( pRight && pRight->pLeft, "The pointer is not allowed to be NULL!" );
190 : 0 : StgAvlNode* pHeavy = pRight;
191 : 0 : StgAvlNode* pNewRoot = pHeavy->pLeft;
192 : 0 : pHeavy->pLeft = pNewRoot->pRight;
193 : 0 : pRight = pNewRoot->pLeft;
194 : 0 : pNewRoot->pRight = pHeavy;
195 : 0 : pNewRoot->pLeft = this;
196 [ # # # # ]: 0 : switch( pNewRoot->nBalance )
197 : : {
198 : : case -1: // RL( b )
199 : 0 : nBalance = 1;
200 : 0 : pHeavy->nBalance = 0;
201 : 0 : break;
202 : : case 1: // RL( c )
203 : 0 : pHeavy->nBalance = -1;
204 : 0 : nBalance = 0;
205 : 0 : break;
206 : : case 0: // RL( a )
207 : 0 : nBalance = 0;
208 : 0 : pHeavy->nBalance = 0;
209 : 0 : break;
210 : : }
211 : 0 : pNewRoot->nBalance = 0;
212 : 0 : return pNewRoot;
213 : : }
214 : :
215 : : // Remove a tree element. Return the removed element or NULL.
216 : :
217 : 60 : StgAvlNode* StgAvlNode::Rem( StgAvlNode** p, StgAvlNode* pDel, sal_Bool bPtrs )
218 : : {
219 [ + - ][ + - ]: 60 : if( p && *p && pDel )
[ + - ]
220 : : {
221 : 60 : StgAvlNode* pCur = *p;
222 [ - + ]: 60 : short nRes = bPtrs ? short( pCur == pDel ) : short(pCur->Compare( pDel ));
223 [ + + ]: 60 : if( !nRes )
224 : : {
225 : : // Element found: remove
226 [ + - ]: 15 : if( !pCur->pRight )
227 : : {
228 : 15 : *p = pCur->pLeft; pCur->pLeft = NULL;
229 : : }
230 [ # # ]: 0 : else if( !pCur->pLeft )
231 : : {
232 : 0 : *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 : 0 : StgAvlNode* last = pCur;
241 : : StgAvlNode* l;
242 [ # # ]: 0 : for( l = pCur->pLeft;
243 : : l->pRight; last = l, l = l->pRight ) {}
244 : : // remove the element from chain
245 [ # # ]: 0 : if( l == last->pRight )
246 : 0 : last->pRight = l->pLeft;
247 : : else
248 : 0 : last->pLeft = l->pLeft;
249 : : // perform the replacement
250 : 0 : l->pLeft = pCur->pLeft;
251 : 0 : l->pRight = pCur->pRight;
252 : 0 : *p = l;
253 : : // delete the element
254 : 0 : pCur->pLeft = pCur->pRight = NULL;
255 : : }
256 : 15 : return pCur;
257 : : }
258 : : else
259 : : {
260 [ + + ]: 45 : if( nRes < 0 )
261 : 30 : return Rem( &pCur->pLeft, pDel, bPtrs );
262 : : else
263 : 15 : return Rem( &pCur->pRight, pDel, bPtrs );
264 : : }
265 : : }
266 : 60 : return NULL;
267 : : }
268 : :
269 : : // Enumerate the tree for later iteration
270 : :
271 : 15369 : void StgAvlNode::StgEnum( short& n )
272 : : {
273 [ + + ]: 15369 : if( pLeft )
274 : 2572 : pLeft->StgEnum( n );
275 : 15369 : nId = n++;
276 [ + + ]: 15369 : if( pRight )
277 : 10891 : pRight->StgEnum( n );
278 : 15369 : }
279 : :
280 : : // Add node to AVL tree.
281 : : // Return sal_False if the element already exists.
282 : :
283 : 6234 : sal_Bool StgAvlNode::Insert( StgAvlNode** pRoot, StgAvlNode* pIns )
284 : : {
285 : : StgAvlNode* pPivot, *pHeavy, *pNewRoot, *pParent, *pPrev;
286 [ - + ]: 6234 : if ( !pRoot )
287 : 0 : return sal_False;
288 : :
289 : : // special case - empty tree
290 [ + + ]: 6234 : if( *pRoot == NULL )
291 : : {
292 : 1338 : *pRoot = pIns;
293 : 1338 : return sal_True;
294 : : }
295 : : // find insertion point and return if already present
296 [ + - ]: 4896 : short nRes = (*pRoot)->Locate( pIns, &pPivot, &pParent, &pPrev );
297 [ - + ]: 4896 : if( !nRes )
298 : 0 : return sal_False;
299 : : OSL_ENSURE( pPivot && pPrev, "The pointers may not be NULL!" );
300 : :
301 : : // add new node
302 [ + + ]: 4896 : if( nRes < 0 )
303 : 1563 : pPrev->pLeft = pIns;
304 : : else
305 : 3333 : pPrev->pRight = pIns;
306 : : // rebalance tree
307 [ + - ]: 4896 : short nDelta = pPivot->Adjust( &pHeavy, pIns );
308 [ + - ][ - + ]: 4896 : if( pPivot->nBalance >= 2 || pPivot->nBalance <= -2 )
309 : : {
310 [ # # ]: 0 : pHeavy = ( nDelta < 0 ) ? pPivot->pRight : pPivot->pLeft;
311 : : // left imbalance
312 [ # # ]: 0 : if( nDelta > 0 )
313 [ # # ]: 0 : if( pHeavy->nBalance == 1 )
314 : 0 : pNewRoot = pPivot->RotLL();
315 : : else
316 : 0 : pNewRoot = pPivot->RotLR();
317 : : // right imbalance
318 [ # # ]: 0 : else if( pHeavy->nBalance == -1 )
319 : 0 : pNewRoot = pPivot->RotRR();
320 : : else
321 : 0 : pNewRoot = pPivot->RotRL();
322 : : // relink balanced subtree
323 [ # # ]: 0 : if( pParent == NULL )
324 : 0 : *pRoot = pNewRoot;
325 [ # # ]: 0 : else if( pPivot == pParent->pLeft )
326 : 0 : pParent->pLeft = pNewRoot;
327 [ # # ]: 0 : else if( pPivot == pParent->pRight )
328 : 0 : pParent->pRight = pNewRoot;
329 : : }
330 : 6234 : return sal_True;
331 : : }
332 : :
333 : : // Remove node from tree. Returns sal_True is found and removed.
334 : : // Actually delete if bDel
335 : :
336 : 15 : sal_Bool StgAvlNode::Remove( StgAvlNode** pRoot, StgAvlNode* pDel, sal_Bool bDel )
337 : : {
338 [ - + ]: 15 : if ( !pRoot )
339 : 0 : return sal_False;
340 : :
341 : : // special case - empty tree
342 [ - + ]: 15 : if( *pRoot == NULL )
343 : 0 : return sal_False;
344 : : // delete the element
345 : 15 : pDel = Rem( pRoot, pDel, sal_False );
346 [ + - ]: 15 : if( pDel )
347 : : {
348 [ + - ]: 15 : if( bDel )
349 [ + - ]: 15 : 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, sal_False );
356 : : Insert( &pNew, p );
357 : : }
358 : : *pRoot = pNew;*/
359 : 15 : return sal_True;
360 : : }
361 : : else
362 : 15 : return sal_False;
363 : : }
364 : :
365 : : // Move node to a different tree. Returns sal_True is found and moved. This routine
366 : : // may be called when the key has changed.
367 : :
368 : 0 : sal_Bool StgAvlNode::Move
369 : : ( StgAvlNode** pRoot1, StgAvlNode** pRoot2, StgAvlNode* pMove )
370 : : {
371 [ # # ]: 0 : if ( !pRoot1 )
372 : 0 : return sal_False;
373 : :
374 : : // special case - empty tree
375 [ # # ]: 0 : if( *pRoot1 == NULL )
376 : 0 : return sal_False;
377 : 0 : pMove = Rem( pRoot1, pMove, sal_False );
378 [ # # ]: 0 : if( pMove )
379 : 0 : return Insert( pRoot2, pMove );
380 : : else
381 : 0 : return sal_False;
382 : : }
383 : :
384 : : ////////////////////////// class AvlIterator /////////////////////////
385 : :
386 : : // The iterator walks through a tree one entry by one.
387 : :
388 : 2086 : StgAvlIterator::StgAvlIterator( StgAvlNode* p )
389 : : {
390 : 2086 : pRoot = p;
391 : 2086 : nCount = 0;
392 : 2086 : nCur = 0;
393 [ + + ]: 2086 : if( p )
394 : 1906 : p->StgEnum( nCount );
395 : 2086 : }
396 : :
397 : 17455 : StgAvlNode* StgAvlIterator::Find( short n )
398 : : {
399 : 17455 : StgAvlNode* p = pRoot;
400 [ + + ]: 130939 : while( p )
401 : : {
402 [ + + ]: 128853 : if( n == p->nId )
403 : 15369 : break;
404 [ + + ]: 113484 : else p = ( n < p->nId ) ? p->pLeft : p->pRight;
405 : : }
406 : 17455 : return p;
407 : : }
408 : :
409 : 2086 : StgAvlNode* StgAvlIterator::First()
410 : : {
411 : 2086 : nCur = -1;
412 : 2086 : return Next();
413 : : }
414 : :
415 : 17455 : StgAvlNode* StgAvlIterator::Next()
416 : : {
417 : 17455 : return Find( ++nCur );
418 : : }
419 : :
420 : : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
