1*bbfc4cc7SAndrew Rist /************************************************************** 2cdf0e10cSrcweir * 3*bbfc4cc7SAndrew Rist * Licensed to the Apache Software Foundation (ASF) under one 4*bbfc4cc7SAndrew Rist * or more contributor license agreements. See the NOTICE file 5*bbfc4cc7SAndrew Rist * distributed with this work for additional information 6*bbfc4cc7SAndrew Rist * regarding copyright ownership. The ASF licenses this file 7*bbfc4cc7SAndrew Rist * to you under the Apache License, Version 2.0 (the 8*bbfc4cc7SAndrew Rist * "License"); you may not use this file except in compliance 9*bbfc4cc7SAndrew Rist * with the License. You may obtain a copy of the License at 10*bbfc4cc7SAndrew Rist * 11*bbfc4cc7SAndrew Rist * http://www.apache.org/licenses/LICENSE-2.0 12*bbfc4cc7SAndrew Rist * 13*bbfc4cc7SAndrew Rist * Unless required by applicable law or agreed to in writing, 14*bbfc4cc7SAndrew Rist * software distributed under the License is distributed on an 15*bbfc4cc7SAndrew Rist * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 16*bbfc4cc7SAndrew Rist * KIND, either express or implied. See the License for the 17*bbfc4cc7SAndrew Rist * specific language governing permissions and limitations 18*bbfc4cc7SAndrew Rist * under the License. 19*bbfc4cc7SAndrew Rist * 20*bbfc4cc7SAndrew Rist *************************************************************/ 21*bbfc4cc7SAndrew Rist 22*bbfc4cc7SAndrew Rist 23cdf0e10cSrcweir 24cdf0e10cSrcweir #ifndef _STGAVL_HXX 25cdf0e10cSrcweir #define _STGAVL_HXX 26cdf0e10cSrcweir 27cdf0e10cSrcweir #ifndef _TOOLS_SOLAR_H 28cdf0e10cSrcweir #include <tools/solar.h> 29cdf0e10cSrcweir #endif 30cdf0e10cSrcweir 31cdf0e10cSrcweir // This class must be overloaded to define real, living nodes. 32cdf0e10cSrcweir // Especially, the compare function must be implemented. 33cdf0e10cSrcweir 34cdf0e10cSrcweir class StgAvlNode 35cdf0e10cSrcweir { 36cdf0e10cSrcweir friend class StgAvlIterator; 37cdf0e10cSrcweir private: 38cdf0e10cSrcweir short Locate( StgAvlNode*, StgAvlNode**, StgAvlNode**, StgAvlNode** ); 39cdf0e10cSrcweir short Adjust( StgAvlNode**, StgAvlNode* ); 40cdf0e10cSrcweir StgAvlNode* RotLL(); 41cdf0e10cSrcweir StgAvlNode* RotLR(); 42cdf0e10cSrcweir StgAvlNode* RotRR(); 43cdf0e10cSrcweir StgAvlNode* RotRL(); 44cdf0e10cSrcweir void StgEnum( short& ); 45cdf0e10cSrcweir static StgAvlNode* Rem( StgAvlNode**, StgAvlNode*, sal_Bool ); 46cdf0e10cSrcweir protected: 47cdf0e10cSrcweir short nId; // iterator ID 48cdf0e10cSrcweir short nBalance; // indicates tree balance 49cdf0e10cSrcweir StgAvlNode* pLeft, *pRight; // leaves 50cdf0e10cSrcweir StgAvlNode(); 51cdf0e10cSrcweir public: 52cdf0e10cSrcweir virtual ~StgAvlNode(); 53cdf0e10cSrcweir StgAvlNode* Find( StgAvlNode* ); 54cdf0e10cSrcweir static sal_Bool Insert( StgAvlNode**, StgAvlNode* ); 55cdf0e10cSrcweir static sal_Bool Remove( StgAvlNode**, StgAvlNode*, sal_Bool bDel = sal_True ); 56cdf0e10cSrcweir static sal_Bool Move( StgAvlNode**, StgAvlNode**, StgAvlNode* ); 57cdf0e10cSrcweir virtual short Compare( const StgAvlNode* ) const = 0; 58cdf0e10cSrcweir }; 59cdf0e10cSrcweir 60cdf0e10cSrcweir // The iterator class provides single stepping through an AVL tree. 61cdf0e10cSrcweir 62cdf0e10cSrcweir class StgAvlIterator { 63cdf0e10cSrcweir StgAvlNode* pRoot; // root entry (parent) 64cdf0e10cSrcweir short nCount; // tree size 65cdf0e10cSrcweir short nCur; // current element 66cdf0e10cSrcweir StgAvlNode* Find( short ); 67cdf0e10cSrcweir public: 68cdf0e10cSrcweir StgAvlIterator( StgAvlNode* ); 69cdf0e10cSrcweir StgAvlNode* First(); 70cdf0e10cSrcweir StgAvlNode* Last(); 71cdf0e10cSrcweir StgAvlNode* Next(); 72cdf0e10cSrcweir StgAvlNode* Prev(); 73cdf0e10cSrcweir }; 74cdf0e10cSrcweir 75cdf0e10cSrcweir #endif 76