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 : #include <assert.h>
23 :
24 23584 : StgAvlNode::StgAvlNode()
25 : {
26 23584 : pLeft = pRight = NULL;
27 23584 : nBalance = nId = 0;
28 23584 : }
29 :
30 23584 : StgAvlNode::~StgAvlNode()
31 : {
32 23584 : delete pLeft;
33 23584 : delete pRight;
34 23584 : }
35 :
36 15126 : StgAvlNode* StgAvlNode::Find( StgAvlNode* pFind )
37 : {
38 15126 : if ( pFind )
39 : {
40 15126 : StgAvlNode* p = this;
41 106105 : while( p )
42 : {
43 84975 : short nRes = p->Compare( pFind );
44 84975 : if( !nRes )
45 9122 : return p;
46 75853 : else p = ( nRes < 0 ) ? p->pLeft : p->pRight;
47 : }
48 : }
49 6004 : return NULL;
50 : }
51 :
52 : // find point to add node to AVL tree and returns
53 : // +/0/- for >/=/< previous
54 :
55 6570 : short StgAvlNode::Locate
56 : ( StgAvlNode* pFind,
57 : StgAvlNode** pPivot, StgAvlNode **pParent, StgAvlNode** pPrev )
58 : {
59 6570 : short nRes = 0;
60 6570 : StgAvlNode* pCur = this;
61 :
62 : OSL_ENSURE( pPivot && pParent && pPrev, "The pointers may not be NULL!" );
63 6570 : *pParent = *pPrev = NULL;
64 6570 : *pPivot = this;
65 :
66 : // search tree for insertion point
67 6570 : if ( pFind )
68 : {
69 39074 : while( pCur != NULL )
70 : {
71 : // check for pPivot
72 25934 : if( pCur->nBalance != 0 )
73 20778 : *pPivot = pCur, *pParent = *pPrev;
74 : // save pPrev location and see what direction to go
75 25934 : *pPrev = pCur;
76 25934 : nRes = pCur->Compare( pFind );
77 25934 : if( nRes == 0 )
78 0 : break;
79 25934 : else pCur = ( nRes < 0 ) ? pCur->pLeft : pCur->pRight;
80 : }
81 : }
82 :
83 6570 : return nRes;
84 : }
85 :
86 : // adjust balance factors in AVL tree from pivot down.
87 : // Returns delta balance.
88 :
89 6570 : short StgAvlNode::Adjust( StgAvlNode** pHeavy, StgAvlNode* pNew )
90 : {
91 6570 : StgAvlNode* pCur = this;
92 : short nDelta;
93 : // no traversing
94 : OSL_ENSURE( pHeavy && pNew, "The pointers is not allowed to be NULL!" );
95 6570 : if( pCur == pNew || !pNew )
96 0 : return nBalance;
97 :
98 6570 : short nRes = Compare( pNew );
99 6570 : if( nRes > 0 )
100 : {
101 4985 : *pHeavy = pCur = pRight;
102 4985 : nDelta = -1;
103 : }
104 : else
105 : {
106 1585 : *pHeavy = pCur = pLeft;
107 1585 : nDelta = 1;
108 : }
109 6570 : nBalance = 0;
110 17227 : while( pCur != pNew )
111 : {
112 4087 : nRes = pCur->Compare( pNew );
113 4087 : if( nRes > 0 )
114 : {
115 : // height of right increases by 1
116 3050 : pCur->nBalance = -1;
117 3050 : pCur = pCur->pRight;
118 : }
119 : else
120 : {
121 : // height of left increases by 1
122 1037 : pCur->nBalance = 1;
123 1037 : pCur = pCur->pLeft;
124 : }
125 : }
126 6570 : nBalance = nBalance + nDelta;
127 6570 : return nDelta;
128 : }
129 :
130 : // perform LL rotation and return new root
131 :
132 0 : StgAvlNode* StgAvlNode::RotLL()
133 : {
134 : assert(pLeft && "The pointer is not allowed to be NULL!");
135 0 : StgAvlNode *pHeavy = pLeft;
136 0 : pLeft = pHeavy->pRight;
137 0 : pHeavy->pRight = this;
138 0 : pHeavy->nBalance = nBalance = 0;
139 0 : return pHeavy;
140 : }
141 :
142 : // perform LR rotation and return new root
143 :
144 0 : StgAvlNode* StgAvlNode::RotLR()
145 : {
146 : assert(pLeft && pLeft->pRight && "The pointer is not allowed to be NULL!");
147 0 : StgAvlNode* pHeavy = pLeft;
148 0 : StgAvlNode* pNewRoot = pHeavy->pRight;
149 :
150 0 : pHeavy->pRight = pNewRoot->pLeft;
151 0 : pLeft = pNewRoot->pRight;
152 0 : pNewRoot->pLeft = pHeavy;
153 0 : pNewRoot->pRight = this;
154 :
155 0 : switch( pNewRoot->nBalance )
156 : {
157 : case 1: // LR( b )
158 0 : nBalance = -1;
159 0 : pHeavy->nBalance = 0;
160 0 : break;
161 : case -1: // LR( c )
162 0 : pHeavy->nBalance = 1;
163 0 : nBalance = 0;
164 0 : break;
165 : case 0: // LR( a )
166 0 : nBalance = 0;
167 0 : pHeavy->nBalance = 0;
168 0 : break;
169 : }
170 0 : pNewRoot->nBalance = 0;
171 0 : return pNewRoot;
172 : }
173 :
174 : // perform RR rotation and return new root
175 0 : StgAvlNode* StgAvlNode::RotRR()
176 : {
177 : assert(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 0 : StgAvlNode* StgAvlNode::RotRL()
187 : {
188 : assert(pRight && pRight->pLeft && "The pointer is not allowed to be NULL!");
189 0 : StgAvlNode* pHeavy = pRight;
190 0 : StgAvlNode* pNewRoot = pHeavy->pLeft;
191 0 : pHeavy->pLeft = pNewRoot->pRight;
192 0 : pRight = pNewRoot->pLeft;
193 0 : pNewRoot->pRight = pHeavy;
194 0 : pNewRoot->pLeft = this;
195 0 : switch( pNewRoot->nBalance )
196 : {
197 : case -1: // RL( b )
198 0 : nBalance = 1;
199 0 : pHeavy->nBalance = 0;
200 0 : break;
201 : case 1: // RL( c )
202 0 : pHeavy->nBalance = -1;
203 0 : nBalance = 0;
204 0 : break;
205 : case 0: // RL( a )
206 0 : nBalance = 0;
207 0 : pHeavy->nBalance = 0;
208 0 : break;
209 : }
210 0 : pNewRoot->nBalance = 0;
211 0 : return pNewRoot;
212 : }
213 :
214 : // Remove a tree element. Return the removed element or NULL.
215 :
216 112 : StgAvlNode* StgAvlNode::Rem( StgAvlNode** p, StgAvlNode* pDel, bool bPtrs )
217 : {
218 112 : if( p && *p && pDel )
219 : {
220 112 : StgAvlNode* pCur = *p;
221 112 : short nRes = bPtrs ? short( pCur == pDel ) : short(pCur->Compare( pDel ));
222 112 : if( !nRes )
223 : {
224 : // Element found: remove
225 28 : if( !pCur->pRight )
226 : {
227 28 : *p = pCur->pLeft; pCur->pLeft = NULL;
228 : }
229 0 : else if( !pCur->pLeft )
230 : {
231 0 : *p = pCur->pRight; pCur->pRight = NULL;
232 : }
233 : else
234 : {
235 : // The damn element has two leaves. Get the
236 : // rightmost element of the left subtree (which
237 : // is lexically before this element) and replace
238 : // this element with the element found.
239 0 : StgAvlNode* last = pCur;
240 : StgAvlNode* l;
241 0 : for( l = pCur->pLeft;
242 : l->pRight; last = l, l = l->pRight ) {}
243 : // remove the element from chain
244 0 : if( l == last->pRight )
245 0 : last->pRight = l->pLeft;
246 : else
247 0 : last->pLeft = l->pLeft;
248 : // perform the replacement
249 0 : l->pLeft = pCur->pLeft;
250 0 : l->pRight = pCur->pRight;
251 0 : *p = l;
252 : // delete the element
253 0 : pCur->pLeft = pCur->pRight = NULL;
254 : }
255 28 : return pCur;
256 : }
257 : else
258 : {
259 84 : if( nRes < 0 )
260 56 : return Rem( &pCur->pLeft, pDel, bPtrs );
261 : else
262 28 : return Rem( &pCur->pRight, pDel, bPtrs );
263 : }
264 : }
265 0 : return NULL;
266 : }
267 :
268 : // Enumerate the tree for later iteration
269 :
270 19990 : void StgAvlNode::StgEnum( short& n )
271 : {
272 19990 : if( pLeft )
273 3279 : pLeft->StgEnum( n );
274 19990 : nId = n++;
275 19990 : if( pRight )
276 13976 : pRight->StgEnum( n );
277 19990 : }
278 :
279 : // Add node to AVL tree.
280 : // Return false if the element already exists.
281 :
282 8239 : bool StgAvlNode::Insert( StgAvlNode** pRoot, StgAvlNode* pIns )
283 : {
284 : StgAvlNode* pPivot, *pHeavy, *pNewRoot, *pParent, *pPrev;
285 8239 : if ( !pRoot )
286 0 : return false;
287 :
288 : // special case - empty tree
289 8239 : if( *pRoot == NULL )
290 : {
291 1669 : *pRoot = pIns;
292 1669 : return true;
293 : }
294 : // find insertion point and return if already present
295 6570 : short nRes = (*pRoot)->Locate( pIns, &pPivot, &pParent, &pPrev );
296 6570 : if( !nRes )
297 0 : return false;
298 :
299 : assert(pPivot && pPrev && "The pointers may not be NULL!");
300 :
301 : // add new node
302 6570 : if( nRes < 0 )
303 1816 : pPrev->pLeft = pIns;
304 : else
305 4754 : pPrev->pRight = pIns;
306 : // rebalance tree
307 6570 : short nDelta = pPivot->Adjust( &pHeavy, pIns );
308 6570 : 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 6570 : return true;
331 : }
332 :
333 : // Remove node from tree. Returns true is found and removed.
334 : // Actually delete if bDel
335 :
336 28 : bool StgAvlNode::Remove( StgAvlNode** pRoot, StgAvlNode* pDel, bool bDel )
337 : {
338 28 : if ( !pRoot )
339 0 : return false;
340 :
341 : // special case - empty tree
342 28 : if( *pRoot == NULL )
343 0 : return false;
344 : // delete the element
345 28 : pDel = Rem( pRoot, pDel, false );
346 28 : if( pDel )
347 : {
348 28 : if( bDel )
349 28 : 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 28 : return true;
360 : }
361 : else
362 0 : 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 0 : bool StgAvlNode::Move( StgAvlNode** pRoot1, StgAvlNode** pRoot2, StgAvlNode* pMove )
369 : {
370 0 : if ( !pRoot1 )
371 0 : return false;
372 :
373 : // special case - empty tree
374 0 : if( *pRoot1 == NULL )
375 0 : return false;
376 0 : pMove = Rem( pRoot1, pMove, false );
377 0 : if( pMove )
378 0 : return Insert( pRoot2, pMove );
379 : else
380 0 : return false;
381 : }
382 :
383 : ////////////////////////// class AvlIterator
384 :
385 : // The iterator walks through a tree one entry by one.
386 :
387 3094 : StgAvlIterator::StgAvlIterator( StgAvlNode* p )
388 : {
389 3094 : pRoot = p;
390 3094 : nCount = 0;
391 3094 : nCur = 0;
392 3094 : if( p )
393 2735 : p->StgEnum( nCount );
394 3094 : }
395 :
396 23084 : StgAvlNode* StgAvlIterator::Find( short n )
397 : {
398 23084 : StgAvlNode* p = pRoot;
399 144502 : while( p )
400 : {
401 118324 : if( n == p->nId )
402 19990 : break;
403 98334 : else p = ( n < p->nId ) ? p->pLeft : p->pRight;
404 : }
405 23084 : return p;
406 : }
407 :
408 3094 : StgAvlNode* StgAvlIterator::First()
409 : {
410 3094 : nCur = -1;
411 3094 : return Next();
412 : }
413 :
414 23084 : StgAvlNode* StgAvlIterator::Next()
415 : {
416 23084 : return Find( ++nCur );
417 : }
418 :
419 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
