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