1046d9d1fSAndrew Rist /**************************************************************
2cdf0e10cSrcweir *
3046d9d1fSAndrew Rist * Licensed to the Apache Software Foundation (ASF) under one
4046d9d1fSAndrew Rist * or more contributor license agreements. See the NOTICE file
5046d9d1fSAndrew Rist * distributed with this work for additional information
6046d9d1fSAndrew Rist * regarding copyright ownership. The ASF licenses this file
7046d9d1fSAndrew Rist * to you under the Apache License, Version 2.0 (the
8046d9d1fSAndrew Rist * "License"); you may not use this file except in compliance
9046d9d1fSAndrew Rist * with the License. You may obtain a copy of the License at
10046d9d1fSAndrew Rist *
11046d9d1fSAndrew Rist * http://www.apache.org/licenses/LICENSE-2.0
12046d9d1fSAndrew Rist *
13046d9d1fSAndrew Rist * Unless required by applicable law or agreed to in writing,
14046d9d1fSAndrew Rist * software distributed under the License is distributed on an
15046d9d1fSAndrew Rist * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
16046d9d1fSAndrew Rist * KIND, either express or implied. See the License for the
17046d9d1fSAndrew Rist * specific language governing permissions and limitations
18046d9d1fSAndrew Rist * under the License.
19046d9d1fSAndrew Rist *
20046d9d1fSAndrew Rist *************************************************************/
21046d9d1fSAndrew Rist
22046d9d1fSAndrew Rist
23cdf0e10cSrcweir
24cdf0e10cSrcweir // MARKER(update_precomp.py): autogen include statement, do not remove
25cdf0e10cSrcweir #include "precompiled_sot.hxx"
26cdf0e10cSrcweir
27*297a844aSArmin Le Grand #include <osl/diagnose.h>
28cdf0e10cSrcweir #include "stgavl.hxx"
29cdf0e10cSrcweir
StgAvlNode()30cdf0e10cSrcweir StgAvlNode::StgAvlNode()
31cdf0e10cSrcweir {
32cdf0e10cSrcweir pLeft = pRight = NULL;
33cdf0e10cSrcweir nBalance = nId = 0;
34cdf0e10cSrcweir }
35cdf0e10cSrcweir
~StgAvlNode()36cdf0e10cSrcweir StgAvlNode::~StgAvlNode()
37cdf0e10cSrcweir {
38cdf0e10cSrcweir delete pLeft;
39cdf0e10cSrcweir delete pRight;
40cdf0e10cSrcweir }
41cdf0e10cSrcweir
Find(StgAvlNode * pFind)42cdf0e10cSrcweir StgAvlNode* StgAvlNode::Find( StgAvlNode* pFind )
43cdf0e10cSrcweir {
44*297a844aSArmin Le Grand if ( pFind )
45cdf0e10cSrcweir {
46*297a844aSArmin Le Grand StgAvlNode* p = this;
47*297a844aSArmin Le Grand while( p )
48*297a844aSArmin Le Grand {
49*297a844aSArmin Le Grand short nRes = p->Compare( pFind );
50*297a844aSArmin Le Grand if( !nRes )
51*297a844aSArmin Le Grand return p;
52*297a844aSArmin Le Grand else p = ( nRes < 0 ) ? p->pLeft : p->pRight;
53*297a844aSArmin Le Grand }
54cdf0e10cSrcweir }
55cdf0e10cSrcweir return NULL;
56cdf0e10cSrcweir }
57cdf0e10cSrcweir
58cdf0e10cSrcweir // find point to add node to AVL tree and returns
59cdf0e10cSrcweir // +/0/- for >/=/< previous
60cdf0e10cSrcweir
Locate(StgAvlNode * pFind,StgAvlNode ** pPivot,StgAvlNode ** pParent,StgAvlNode ** pPrev)61cdf0e10cSrcweir short StgAvlNode::Locate
62cdf0e10cSrcweir ( StgAvlNode* pFind,
63cdf0e10cSrcweir StgAvlNode** pPivot, StgAvlNode **pParent, StgAvlNode** pPrev )
64cdf0e10cSrcweir {
65cdf0e10cSrcweir short nRes = 0;
66cdf0e10cSrcweir StgAvlNode* pCur = this;
67*297a844aSArmin Le Grand
68*297a844aSArmin Le Grand OSL_ENSURE( pPivot && pParent && pPrev, "The pointers may not be NULL!" );
69cdf0e10cSrcweir *pParent = *pPrev = NULL;
70cdf0e10cSrcweir *pPivot = this;
71cdf0e10cSrcweir
72cdf0e10cSrcweir // search tree for insertion point
73*297a844aSArmin Le Grand if ( pFind )
74cdf0e10cSrcweir {
75*297a844aSArmin Le Grand while( pCur != NULL )
76*297a844aSArmin Le Grand {
77*297a844aSArmin Le Grand // check for pPivot
78*297a844aSArmin Le Grand if( pCur->nBalance != 0 )
79*297a844aSArmin Le Grand *pPivot = pCur, *pParent = *pPrev;
80*297a844aSArmin Le Grand // save pPrev location and see what direction to go
81*297a844aSArmin Le Grand *pPrev = pCur;
82*297a844aSArmin Le Grand nRes = pCur->Compare( pFind );
83*297a844aSArmin Le Grand if( nRes == 0 )
84*297a844aSArmin Le Grand break;
85*297a844aSArmin Le Grand else pCur = ( nRes < 0 ) ? pCur->pLeft : pCur->pRight;
86*297a844aSArmin Le Grand }
87cdf0e10cSrcweir }
88*297a844aSArmin Le Grand
89cdf0e10cSrcweir return( nRes );
90cdf0e10cSrcweir }
91cdf0e10cSrcweir
92cdf0e10cSrcweir // adjust balance factors in AVL tree from pivot down.
93cdf0e10cSrcweir // Returns delta balance.
94cdf0e10cSrcweir
Adjust(StgAvlNode ** pHeavy,StgAvlNode * pNew)95cdf0e10cSrcweir short StgAvlNode::Adjust( StgAvlNode** pHeavy, StgAvlNode* pNew )
96cdf0e10cSrcweir {
97cdf0e10cSrcweir StgAvlNode* pCur = this;
98cdf0e10cSrcweir short nDelta;
99cdf0e10cSrcweir // no traversing
100*297a844aSArmin Le Grand OSL_ENSURE( pHeavy && pNew, "The pointers is not allowed to be NULL!" );
101*297a844aSArmin Le Grand if( pCur == pNew || !pNew )
102cdf0e10cSrcweir return nBalance;
103*297a844aSArmin Le Grand
104cdf0e10cSrcweir short nRes = Compare( pNew );
105cdf0e10cSrcweir if( nRes > 0 )
106cdf0e10cSrcweir {
107cdf0e10cSrcweir *pHeavy = pCur = pRight;
108cdf0e10cSrcweir nDelta = -1;
109cdf0e10cSrcweir }
110cdf0e10cSrcweir else
111cdf0e10cSrcweir {
112cdf0e10cSrcweir *pHeavy = pCur = pLeft;
113cdf0e10cSrcweir nDelta = 1;
114cdf0e10cSrcweir }
115cdf0e10cSrcweir nBalance = 0;
116cdf0e10cSrcweir while( pCur != pNew )
117cdf0e10cSrcweir {
118cdf0e10cSrcweir nRes = pCur->Compare( pNew );
119cdf0e10cSrcweir if( nRes > 0 )
120cdf0e10cSrcweir {
121cdf0e10cSrcweir // height of right increases by 1
122cdf0e10cSrcweir pCur->nBalance = -1;
123cdf0e10cSrcweir pCur = pCur->pRight;
124cdf0e10cSrcweir }
125cdf0e10cSrcweir else
126cdf0e10cSrcweir {
127cdf0e10cSrcweir // height of left increases by 1
128cdf0e10cSrcweir pCur->nBalance = 1;
129cdf0e10cSrcweir pCur = pCur->pLeft;
130cdf0e10cSrcweir }
131cdf0e10cSrcweir }
132cdf0e10cSrcweir nBalance = nBalance + nDelta;
133cdf0e10cSrcweir return nDelta;
134cdf0e10cSrcweir }
135cdf0e10cSrcweir
136cdf0e10cSrcweir // perform LL rotation and return new root
137cdf0e10cSrcweir
RotLL()138cdf0e10cSrcweir StgAvlNode* StgAvlNode::RotLL()
139cdf0e10cSrcweir {
140*297a844aSArmin Le Grand OSL_ENSURE( pLeft, "The pointer is not allowed to be NULL!" );
141cdf0e10cSrcweir StgAvlNode *pHeavy = pLeft;
142cdf0e10cSrcweir pLeft = pHeavy->pRight;
143cdf0e10cSrcweir pHeavy->pRight = this;
144cdf0e10cSrcweir pHeavy->nBalance = nBalance = 0;
145cdf0e10cSrcweir return pHeavy;
146cdf0e10cSrcweir }
147cdf0e10cSrcweir
148cdf0e10cSrcweir // perform LR rotation and return new root
149cdf0e10cSrcweir
RotLR()150cdf0e10cSrcweir StgAvlNode* StgAvlNode::RotLR()
151cdf0e10cSrcweir {
152*297a844aSArmin Le Grand OSL_ENSURE( pLeft && pLeft->pRight, "The pointer is not allowed to be NULL!" );
153cdf0e10cSrcweir StgAvlNode* pHeavy = pLeft;
154cdf0e10cSrcweir StgAvlNode* pNewRoot = pHeavy->pRight;
155cdf0e10cSrcweir
156cdf0e10cSrcweir pHeavy->pRight = pNewRoot->pLeft;
157cdf0e10cSrcweir pLeft = pNewRoot->pRight;
158cdf0e10cSrcweir pNewRoot->pLeft = pHeavy;
159cdf0e10cSrcweir pNewRoot->pRight = this;
160cdf0e10cSrcweir
161cdf0e10cSrcweir switch( pNewRoot->nBalance )
162cdf0e10cSrcweir {
163cdf0e10cSrcweir case 1: // LR( b )
164cdf0e10cSrcweir nBalance = -1;
165cdf0e10cSrcweir pHeavy->nBalance = 0;
166cdf0e10cSrcweir break;
167cdf0e10cSrcweir case -1: // LR( c )
168cdf0e10cSrcweir pHeavy->nBalance = 1;
169cdf0e10cSrcweir nBalance = 0;
170cdf0e10cSrcweir break;
171cdf0e10cSrcweir case 0: // LR( a )
172cdf0e10cSrcweir nBalance = 0;
173cdf0e10cSrcweir pHeavy->nBalance = 0;
174cdf0e10cSrcweir break;
175cdf0e10cSrcweir }
176cdf0e10cSrcweir pNewRoot->nBalance = 0;
177cdf0e10cSrcweir return pNewRoot;
178cdf0e10cSrcweir }
179cdf0e10cSrcweir
180cdf0e10cSrcweir // perform RR rotation and return new root
181cdf0e10cSrcweir
RotRR()182cdf0e10cSrcweir StgAvlNode* StgAvlNode::RotRR()
183cdf0e10cSrcweir {
184*297a844aSArmin Le Grand OSL_ENSURE( pRight, "The pointer is not allowed to be NULL!" );
185cdf0e10cSrcweir StgAvlNode* pHeavy = pRight;
186cdf0e10cSrcweir pRight = pHeavy->pLeft;
187cdf0e10cSrcweir pHeavy->pLeft = this;
188cdf0e10cSrcweir nBalance = pHeavy->nBalance = 0;
189cdf0e10cSrcweir return pHeavy;
190cdf0e10cSrcweir }
191cdf0e10cSrcweir
192cdf0e10cSrcweir // perform the RL rotation and return the new root
193cdf0e10cSrcweir
RotRL()194cdf0e10cSrcweir StgAvlNode* StgAvlNode::RotRL()
195cdf0e10cSrcweir {
196*297a844aSArmin Le Grand OSL_ENSURE( pRight && pRight->pLeft, "The pointer is not allowed to be NULL!" );
197cdf0e10cSrcweir StgAvlNode* pHeavy = pRight;
198cdf0e10cSrcweir StgAvlNode* pNewRoot = pHeavy->pLeft;
199cdf0e10cSrcweir pHeavy->pLeft = pNewRoot->pRight;
200cdf0e10cSrcweir pRight = pNewRoot->pLeft;
201cdf0e10cSrcweir pNewRoot->pRight = pHeavy;
202cdf0e10cSrcweir pNewRoot->pLeft = this;
203cdf0e10cSrcweir switch( pNewRoot->nBalance )
204cdf0e10cSrcweir {
205cdf0e10cSrcweir case -1: // RL( b )
206cdf0e10cSrcweir nBalance = 1;
207cdf0e10cSrcweir pHeavy->nBalance = 0;
208cdf0e10cSrcweir break;
209cdf0e10cSrcweir case 1: // RL( c )
210cdf0e10cSrcweir pHeavy->nBalance = -1;
211cdf0e10cSrcweir nBalance = 0;
212cdf0e10cSrcweir break;
213cdf0e10cSrcweir case 0: // RL( a )
214cdf0e10cSrcweir nBalance = 0;
215cdf0e10cSrcweir pHeavy->nBalance = 0;
216cdf0e10cSrcweir break;
217cdf0e10cSrcweir }
218cdf0e10cSrcweir pNewRoot->nBalance = 0;
219cdf0e10cSrcweir return pNewRoot;
220cdf0e10cSrcweir }
221cdf0e10cSrcweir
222cdf0e10cSrcweir // Remove a tree element. Return the removed element or NULL.
223cdf0e10cSrcweir
Rem(StgAvlNode ** p,StgAvlNode * pDel,sal_Bool bPtrs)224cdf0e10cSrcweir StgAvlNode* StgAvlNode::Rem( StgAvlNode** p, StgAvlNode* pDel, sal_Bool bPtrs )
225cdf0e10cSrcweir {
226*297a844aSArmin Le Grand if( p && *p && pDel )
227cdf0e10cSrcweir {
228cdf0e10cSrcweir StgAvlNode* pCur = *p;
229cdf0e10cSrcweir short nRes = bPtrs ? short( pCur == pDel ) : short(pCur->Compare( pDel ));
230cdf0e10cSrcweir if( !nRes )
231cdf0e10cSrcweir {
232cdf0e10cSrcweir // Element found: remove
233cdf0e10cSrcweir if( !pCur->pRight )
234cdf0e10cSrcweir {
235cdf0e10cSrcweir *p = pCur->pLeft; pCur->pLeft = NULL;
236cdf0e10cSrcweir }
237cdf0e10cSrcweir else if( !pCur->pLeft )
238cdf0e10cSrcweir {
239cdf0e10cSrcweir *p = pCur->pRight; pCur->pRight = NULL;
240cdf0e10cSrcweir }
241cdf0e10cSrcweir else
242cdf0e10cSrcweir {
243cdf0e10cSrcweir // The damn element has two leaves. Get the
244cdf0e10cSrcweir // rightmost element of the left subtree (which
245cdf0e10cSrcweir // is lexically before this element) and replace
246cdf0e10cSrcweir // this element with the element found.
247cdf0e10cSrcweir StgAvlNode* last = pCur;
248cdf0e10cSrcweir StgAvlNode* l;
249cdf0e10cSrcweir for( l = pCur->pLeft;
250cdf0e10cSrcweir l->pRight; last = l, l = l->pRight ) {}
251cdf0e10cSrcweir // remove the element from chain
252cdf0e10cSrcweir if( l == last->pRight )
253cdf0e10cSrcweir last->pRight = l->pLeft;
254cdf0e10cSrcweir else
255cdf0e10cSrcweir last->pLeft = l->pLeft;
256cdf0e10cSrcweir // perform the replacement
257cdf0e10cSrcweir l->pLeft = pCur->pLeft;
258cdf0e10cSrcweir l->pRight = pCur->pRight;
259cdf0e10cSrcweir *p = l;
260cdf0e10cSrcweir // delete the element
261cdf0e10cSrcweir pCur->pLeft = pCur->pRight = NULL;
262cdf0e10cSrcweir }
263cdf0e10cSrcweir return pCur;
264cdf0e10cSrcweir }
265cdf0e10cSrcweir else
266cdf0e10cSrcweir {
267cdf0e10cSrcweir if( nRes < 0 )
268cdf0e10cSrcweir return Rem( &pCur->pLeft, pDel, bPtrs );
269cdf0e10cSrcweir else
270cdf0e10cSrcweir return Rem( &pCur->pRight, pDel, bPtrs );
271cdf0e10cSrcweir }
272cdf0e10cSrcweir }
273cdf0e10cSrcweir return NULL;
274cdf0e10cSrcweir }
275cdf0e10cSrcweir
276cdf0e10cSrcweir // Enumerate the tree for later iteration
277cdf0e10cSrcweir
StgEnum(short & n)278cdf0e10cSrcweir void StgAvlNode::StgEnum( short& n )
279cdf0e10cSrcweir {
280*297a844aSArmin Le Grand if( pLeft )
281*297a844aSArmin Le Grand pLeft->StgEnum( n );
282*297a844aSArmin Le Grand nId = n++;
283*297a844aSArmin Le Grand if( pRight )
284*297a844aSArmin Le Grand pRight->StgEnum( n );
285cdf0e10cSrcweir }
286cdf0e10cSrcweir
287cdf0e10cSrcweir // Add node to AVL tree.
288cdf0e10cSrcweir // Return sal_False if the element already exists.
289cdf0e10cSrcweir
Insert(StgAvlNode ** pRoot,StgAvlNode * pIns)290cdf0e10cSrcweir sal_Bool StgAvlNode::Insert( StgAvlNode** pRoot, StgAvlNode* pIns )
291cdf0e10cSrcweir {
292cdf0e10cSrcweir StgAvlNode* pPivot, *pHeavy, *pNewRoot, *pParent, *pPrev;
293*297a844aSArmin Le Grand if ( !pRoot )
294*297a844aSArmin Le Grand return sal_False;
295*297a844aSArmin Le Grand
296cdf0e10cSrcweir // special case - empty tree
297cdf0e10cSrcweir if( *pRoot == NULL )
298cdf0e10cSrcweir {
299cdf0e10cSrcweir *pRoot = pIns;
300cdf0e10cSrcweir return sal_True;
301cdf0e10cSrcweir }
302cdf0e10cSrcweir // find insertion point and return if already present
303cdf0e10cSrcweir short nRes = (*pRoot)->Locate( pIns, &pPivot, &pParent, &pPrev );
304cdf0e10cSrcweir if( !nRes )
305cdf0e10cSrcweir return sal_False;
306*297a844aSArmin Le Grand OSL_ENSURE( pPivot && pPrev, "The pointers may not be NULL!" );
307*297a844aSArmin Le Grand
308cdf0e10cSrcweir // add new node
309cdf0e10cSrcweir if( nRes < 0 )
310cdf0e10cSrcweir pPrev->pLeft = pIns;
311cdf0e10cSrcweir else
312cdf0e10cSrcweir pPrev->pRight = pIns;
313cdf0e10cSrcweir // rebalance tree
314cdf0e10cSrcweir short nDelta = pPivot->Adjust( &pHeavy, pIns );
315cdf0e10cSrcweir if( pPivot->nBalance >= 2 || pPivot->nBalance <= -2 )
316cdf0e10cSrcweir {
317cdf0e10cSrcweir pHeavy = ( nDelta < 0 ) ? pPivot->pRight : pPivot->pLeft;
318cdf0e10cSrcweir // left imbalance
319cdf0e10cSrcweir if( nDelta > 0 )
320cdf0e10cSrcweir if( pHeavy->nBalance == 1 )
321cdf0e10cSrcweir pNewRoot = pPivot->RotLL();
322cdf0e10cSrcweir else
323cdf0e10cSrcweir pNewRoot = pPivot->RotLR();
324cdf0e10cSrcweir // right imbalance
325cdf0e10cSrcweir else if( pHeavy->nBalance == -1 )
326cdf0e10cSrcweir pNewRoot = pPivot->RotRR();
327cdf0e10cSrcweir else
328cdf0e10cSrcweir pNewRoot = pPivot->RotRL();
329cdf0e10cSrcweir // relink balanced subtree
330cdf0e10cSrcweir if( pParent == NULL )
331cdf0e10cSrcweir *pRoot = pNewRoot;
332cdf0e10cSrcweir else if( pPivot == pParent->pLeft )
333cdf0e10cSrcweir pParent->pLeft = pNewRoot;
334cdf0e10cSrcweir else if( pPivot == pParent->pRight )
335cdf0e10cSrcweir pParent->pRight = pNewRoot;
336cdf0e10cSrcweir }
337cdf0e10cSrcweir return sal_True;
338cdf0e10cSrcweir }
339cdf0e10cSrcweir
340cdf0e10cSrcweir // Remove node from tree. Returns sal_True is found and removed.
341cdf0e10cSrcweir // Actually delete if bDel
342cdf0e10cSrcweir
Remove(StgAvlNode ** pRoot,StgAvlNode * pDel,sal_Bool bDel)343cdf0e10cSrcweir sal_Bool StgAvlNode::Remove( StgAvlNode** pRoot, StgAvlNode* pDel, sal_Bool bDel )
344cdf0e10cSrcweir {
345*297a844aSArmin Le Grand if ( !pRoot )
346*297a844aSArmin Le Grand return sal_False;
347*297a844aSArmin Le Grand
348cdf0e10cSrcweir // special case - empty tree
349cdf0e10cSrcweir if( *pRoot == NULL )
350cdf0e10cSrcweir return sal_False;
351cdf0e10cSrcweir // delete the element
352cdf0e10cSrcweir pDel = Rem( pRoot, pDel, sal_False );
353cdf0e10cSrcweir if( pDel )
354cdf0e10cSrcweir {
355cdf0e10cSrcweir if( bDel )
356cdf0e10cSrcweir delete pDel;
357cdf0e10cSrcweir // Rebalance the tree the hard way
358cdf0e10cSrcweir // OS 22.09.95: Auf MD's Wunsch auskommentiert wg. Absturz
359cdf0e10cSrcweir /* StgAvlNode* pNew = NULL;
360cdf0e10cSrcweir while( *pRoot )
361cdf0e10cSrcweir {
362cdf0e10cSrcweir StgAvlNode* p = Rem( pRoot, *pRoot, sal_False );
363cdf0e10cSrcweir Insert( &pNew, p );
364cdf0e10cSrcweir }
365cdf0e10cSrcweir *pRoot = pNew;*/
366cdf0e10cSrcweir return sal_True;
367cdf0e10cSrcweir }
368cdf0e10cSrcweir else
369cdf0e10cSrcweir return sal_False;
370cdf0e10cSrcweir }
371cdf0e10cSrcweir
372cdf0e10cSrcweir // Move node to a different tree. Returns sal_True is found and moved. This routine
373cdf0e10cSrcweir // may be called when the key has changed.
374cdf0e10cSrcweir
Move(StgAvlNode ** pRoot1,StgAvlNode ** pRoot2,StgAvlNode * pMove)375cdf0e10cSrcweir sal_Bool StgAvlNode::Move
376cdf0e10cSrcweir ( StgAvlNode** pRoot1, StgAvlNode** pRoot2, StgAvlNode* pMove )
377cdf0e10cSrcweir {
378*297a844aSArmin Le Grand if ( !pRoot1 )
379*297a844aSArmin Le Grand return sal_False;
380*297a844aSArmin Le Grand
381cdf0e10cSrcweir // special case - empty tree
382cdf0e10cSrcweir if( *pRoot1 == NULL )
383cdf0e10cSrcweir return sal_False;
384cdf0e10cSrcweir pMove = Rem( pRoot1, pMove, sal_False );
385cdf0e10cSrcweir if( pMove )
386cdf0e10cSrcweir return Insert( pRoot2, pMove );
387cdf0e10cSrcweir else
388cdf0e10cSrcweir return sal_False;
389cdf0e10cSrcweir }
390cdf0e10cSrcweir
391cdf0e10cSrcweir ////////////////////////// class AvlIterator /////////////////////////
392cdf0e10cSrcweir
393cdf0e10cSrcweir // The iterator walks through a tree one entry by one.
394cdf0e10cSrcweir
StgAvlIterator(StgAvlNode * p)395cdf0e10cSrcweir StgAvlIterator::StgAvlIterator( StgAvlNode* p )
396cdf0e10cSrcweir {
397cdf0e10cSrcweir pRoot = p;
398cdf0e10cSrcweir nCount = 0;
399cdf0e10cSrcweir if( p )
400cdf0e10cSrcweir p->StgEnum( nCount );
401cdf0e10cSrcweir }
402cdf0e10cSrcweir
Find(short n)403cdf0e10cSrcweir StgAvlNode* StgAvlIterator::Find( short n )
404cdf0e10cSrcweir {
405cdf0e10cSrcweir StgAvlNode* p = pRoot;
406cdf0e10cSrcweir while( p )
407cdf0e10cSrcweir {
408cdf0e10cSrcweir if( n == p->nId )
409cdf0e10cSrcweir break;
410cdf0e10cSrcweir else p = ( n < p->nId ) ? p->pLeft : p->pRight;
411cdf0e10cSrcweir }
412cdf0e10cSrcweir return p;
413cdf0e10cSrcweir }
414cdf0e10cSrcweir
First()415cdf0e10cSrcweir StgAvlNode* StgAvlIterator::First()
416cdf0e10cSrcweir {
417cdf0e10cSrcweir nCur = -1;
418cdf0e10cSrcweir return Next();
419cdf0e10cSrcweir }
420cdf0e10cSrcweir
Last()421cdf0e10cSrcweir StgAvlNode* StgAvlIterator::Last()
422cdf0e10cSrcweir {
423cdf0e10cSrcweir nCur = nCount;
424cdf0e10cSrcweir return Prev();
425cdf0e10cSrcweir }
426cdf0e10cSrcweir
Next()427cdf0e10cSrcweir StgAvlNode* StgAvlIterator::Next()
428cdf0e10cSrcweir {
429cdf0e10cSrcweir return Find( ++nCur );
430cdf0e10cSrcweir }
431cdf0e10cSrcweir
Prev()432cdf0e10cSrcweir StgAvlNode* StgAvlIterator::Prev()
433cdf0e10cSrcweir {
434cdf0e10cSrcweir return Find( --nCur );
435cdf0e10cSrcweir }
436cdf0e10cSrcweir
437