xref: /trunk/main/sot/source/sdstor/stgavl.hxx (revision bbfc4cc7)
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 #ifndef _STGAVL_HXX
25 #define _STGAVL_HXX
26 
27 #ifndef _TOOLS_SOLAR_H
28 #include <tools/solar.h>
29 #endif
30 
31 // This class must be overloaded to define real, living nodes.
32 // Especially, the compare function must be implemented.
33 
34 class StgAvlNode
35 {
36 	friend class StgAvlIterator;
37 private:
38 	short Locate( StgAvlNode*, StgAvlNode**, StgAvlNode**, StgAvlNode** );
39 	short Adjust( StgAvlNode**, StgAvlNode* );
40 	StgAvlNode* RotLL();
41 	StgAvlNode* RotLR();
42 	StgAvlNode* RotRR();
43 	StgAvlNode* RotRL();
44 	void   StgEnum( short& );
45 	static StgAvlNode* Rem( StgAvlNode**, StgAvlNode*, sal_Bool );
46 protected:
47 	short nId;						  	// iterator ID
48 	short nBalance;						// indicates tree balance
49 	StgAvlNode* pLeft, *pRight; 		// leaves
50 	StgAvlNode();
51 public:
52 	virtual ~StgAvlNode();
53 	StgAvlNode* Find( StgAvlNode* );
54 	static sal_Bool Insert( StgAvlNode**, StgAvlNode* );
55 	static sal_Bool Remove( StgAvlNode**, StgAvlNode*, sal_Bool bDel = sal_True );
56 	static sal_Bool Move( StgAvlNode**, StgAvlNode**, StgAvlNode* );
57 	virtual short Compare( const StgAvlNode* ) const = 0;
58 };
59 
60 // The iterator class provides single stepping through an AVL tree.
61 
62 class StgAvlIterator {
63 	StgAvlNode* pRoot;					// root entry (parent)
64 	short 	    nCount;					// tree size
65 	short		nCur;					// current element
66 	StgAvlNode* Find( short );
67 public:
68 	StgAvlIterator( StgAvlNode* );
69 	StgAvlNode* First();
70 	StgAvlNode* Last();
71 	StgAvlNode* Next();
72 	StgAvlNode* Prev();
73 };
74 
75 #endif
76