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 0 : StgAvlNode::StgAvlNode()
24 : {
25 0 : pLeft = pRight = NULL;
26 0 : nBalance = nId = 0;
27 0 : }
28 :
29 0 : StgAvlNode::~StgAvlNode()
30 : {
31 0 : delete pLeft;
32 0 : delete pRight;
33 0 : }
34 :
35 0 : StgAvlNode* StgAvlNode::Find( StgAvlNode* pFind )
36 : {
37 0 : if ( pFind )
38 : {
39 0 : StgAvlNode* p = this;
40 0 : while( p )
41 : {
42 0 : short nRes = p->Compare( pFind );
43 0 : if( !nRes )
44 0 : return p;
45 0 : else p = ( nRes < 0 ) ? p->pLeft : p->pRight;
46 : }
47 : }
48 0 : return NULL;
49 : }
50 :
51 : // find point to add node to AVL tree and returns
52 : // +/0/- for >/=/< previous
53 :
54 0 : short StgAvlNode::Locate
55 : ( StgAvlNode* pFind,
56 : StgAvlNode** pPivot, StgAvlNode **pParent, StgAvlNode** pPrev )
57 : {
58 0 : short nRes = 0;
59 0 : StgAvlNode* pCur = this;
60 :
61 : OSL_ENSURE( pPivot && pParent && pPrev, "The pointers may not be NULL!" );
62 0 : *pParent = *pPrev = NULL;
63 0 : *pPivot = this;
64 :
65 : // search tree for insertion point
66 0 : if ( pFind )
67 : {
68 0 : while( pCur != NULL )
69 : {
70 : // check for pPivot
71 0 : if( pCur->nBalance != 0 )
72 0 : *pPivot = pCur, *pParent = *pPrev;
73 : // save pPrev location and see what direction to go
74 0 : *pPrev = pCur;
75 0 : nRes = pCur->Compare( pFind );
76 0 : if( nRes == 0 )
77 0 : break;
78 0 : else pCur = ( nRes < 0 ) ? pCur->pLeft : pCur->pRight;
79 : }
80 : }
81 :
82 0 : return( nRes );
83 : }
84 :
85 : // adjust balance factors in AVL tree from pivot down.
86 : // Returns delta balance.
87 :
88 0 : short StgAvlNode::Adjust( StgAvlNode** pHeavy, StgAvlNode* pNew )
89 : {
90 0 : StgAvlNode* pCur = this;
91 : short nDelta;
92 : // no traversing
93 : OSL_ENSURE( pHeavy && pNew, "The pointers is not allowed to be NULL!" );
94 0 : if( pCur == pNew || !pNew )
95 0 : return nBalance;
96 :
97 0 : short nRes = Compare( pNew );
98 0 : if( nRes > 0 )
99 : {
100 0 : *pHeavy = pCur = pRight;
101 0 : nDelta = -1;
102 : }
103 : else
104 : {
105 0 : *pHeavy = pCur = pLeft;
106 0 : nDelta = 1;
107 : }
108 0 : nBalance = 0;
109 0 : while( pCur != pNew )
110 : {
111 0 : nRes = pCur->Compare( pNew );
112 0 : if( nRes > 0 )
113 : {
114 : // height of right increases by 1
115 0 : pCur->nBalance = -1;
116 0 : pCur = pCur->pRight;
117 : }
118 : else
119 : {
120 : // height of left increases by 1
121 0 : pCur->nBalance = 1;
122 0 : pCur = pCur->pLeft;
123 : }
124 : }
125 0 : nBalance = nBalance + nDelta;
126 0 : 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 0 : StgAvlNode* StgAvlNode::Rem( StgAvlNode** p, StgAvlNode* pDel, bool bPtrs )
218 : {
219 0 : if( p && *p && pDel )
220 : {
221 0 : StgAvlNode* pCur = *p;
222 0 : short nRes = bPtrs ? short( pCur == pDel ) : short(pCur->Compare( pDel ));
223 0 : if( !nRes )
224 : {
225 : // Element found: remove
226 0 : if( !pCur->pRight )
227 : {
228 0 : *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 0 : return pCur;
257 : }
258 : else
259 : {
260 0 : if( nRes < 0 )
261 0 : return Rem( &pCur->pLeft, pDel, bPtrs );
262 : else
263 0 : return Rem( &pCur->pRight, pDel, bPtrs );
264 : }
265 : }
266 0 : return NULL;
267 : }
268 :
269 : // Enumerate the tree for later iteration
270 :
271 0 : void StgAvlNode::StgEnum( short& n )
272 : {
273 0 : if( pLeft )
274 0 : pLeft->StgEnum( n );
275 0 : nId = n++;
276 0 : if( pRight )
277 0 : pRight->StgEnum( n );
278 0 : }
279 :
280 : // Add node to AVL tree.
281 : // Return false if the element already exists.
282 :
283 0 : bool StgAvlNode::Insert( StgAvlNode** pRoot, StgAvlNode* pIns )
284 : {
285 : StgAvlNode* pPivot, *pHeavy, *pNewRoot, *pParent, *pPrev;
286 0 : if ( !pRoot )
287 0 : return false;
288 :
289 : // special case - empty tree
290 0 : if( *pRoot == NULL )
291 : {
292 0 : *pRoot = pIns;
293 0 : return true;
294 : }
295 : // find insertion point and return if already present
296 0 : short nRes = (*pRoot)->Locate( pIns, &pPivot, &pParent, &pPrev );
297 0 : if( !nRes )
298 0 : return false;
299 : OSL_ENSURE( pPivot && pPrev, "The pointers may not be NULL!" );
300 :
301 : // add new node
302 0 : if( nRes < 0 )
303 0 : pPrev->pLeft = pIns;
304 : else
305 0 : pPrev->pRight = pIns;
306 : // rebalance tree
307 0 : short nDelta = pPivot->Adjust( &pHeavy, pIns );
308 0 : 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 0 : return true;
331 : }
332 :
333 : // Remove node from tree. Returns true is found and removed.
334 : // Actually delete if bDel
335 :
336 0 : bool StgAvlNode::Remove( StgAvlNode** pRoot, StgAvlNode* pDel, bool bDel )
337 : {
338 0 : if ( !pRoot )
339 0 : return false;
340 :
341 : // special case - empty tree
342 0 : if( *pRoot == NULL )
343 0 : return false;
344 : // delete the element
345 0 : pDel = Rem( pRoot, pDel, false );
346 0 : if( pDel )
347 : {
348 0 : if( bDel )
349 0 : 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 0 : 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 0 : StgAvlIterator::StgAvlIterator( StgAvlNode* p )
388 : {
389 0 : pRoot = p;
390 0 : nCount = 0;
391 0 : nCur = 0;
392 0 : if( p )
393 0 : p->StgEnum( nCount );
394 0 : }
395 :
396 0 : StgAvlNode* StgAvlIterator::Find( short n )
397 : {
398 0 : StgAvlNode* p = pRoot;
399 0 : while( p )
400 : {
401 0 : if( n == p->nId )
402 0 : break;
403 0 : else p = ( n < p->nId ) ? p->pLeft : p->pRight;
404 : }
405 0 : return p;
406 : }
407 :
408 0 : StgAvlNode* StgAvlIterator::First()
409 : {
410 0 : nCur = -1;
411 0 : return Next();
412 : }
413 :
414 0 : StgAvlNode* StgAvlIterator::Next()
415 : {
416 0 : return Find( ++nCur );
417 : }
418 :
419 : /* vim:set shiftwidth=4 softtabstop=4 expandtab: */
|
