1 /************************************************************************* 2 * 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * Copyright 2000, 2010 Oracle and/or its affiliates. 6 * 7 * OpenOffice.org - a multi-platform office productivity suite 8 * 9 * This file is part of OpenOffice.org. 10 * 11 * OpenOffice.org is free software: you can redistribute it and/or modify 12 * it under the terms of the GNU Lesser General Public License version 3 13 * only, as published by the Free Software Foundation. 14 * 15 * OpenOffice.org is distributed in the hope that it will be useful, 16 * but WITHOUT ANY WARRANTY; without even the implied warranty of 17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 * GNU Lesser General Public License version 3 for more details 19 * (a copy is included in the LICENSE file that accompanied this code). 20 * 21 * You should have received a copy of the GNU Lesser General Public License 22 * version 3 along with OpenOffice.org. If not, see 23 * <http://www.openoffice.org/license.html> 24 * for a copy of the LGPLv3 License. 25 * 26 ************************************************************************/ 27 28 #ifndef _STGAVL_HXX 29 #define _STGAVL_HXX 30 31 #ifndef _TOOLS_SOLAR_H 32 #include <tools/solar.h> 33 #endif 34 35 // This class must be overloaded to define real, living nodes. 36 // Especially, the compare function must be implemented. 37 38 class StgAvlNode 39 { 40 friend class StgAvlIterator; 41 private: 42 short Locate( StgAvlNode*, StgAvlNode**, StgAvlNode**, StgAvlNode** ); 43 short Adjust( StgAvlNode**, StgAvlNode* ); 44 StgAvlNode* RotLL(); 45 StgAvlNode* RotLR(); 46 StgAvlNode* RotRR(); 47 StgAvlNode* RotRL(); 48 void StgEnum( short& ); 49 static StgAvlNode* Rem( StgAvlNode**, StgAvlNode*, sal_Bool ); 50 protected: 51 short nId; // iterator ID 52 short nBalance; // indicates tree balance 53 StgAvlNode* pLeft, *pRight; // leaves 54 StgAvlNode(); 55 public: 56 virtual ~StgAvlNode(); 57 StgAvlNode* Find( StgAvlNode* ); 58 static sal_Bool Insert( StgAvlNode**, StgAvlNode* ); 59 static sal_Bool Remove( StgAvlNode**, StgAvlNode*, sal_Bool bDel = sal_True ); 60 static sal_Bool Move( StgAvlNode**, StgAvlNode**, StgAvlNode* ); 61 virtual short Compare( const StgAvlNode* ) const = 0; 62 }; 63 64 // The iterator class provides single stepping through an AVL tree. 65 66 class StgAvlIterator { 67 StgAvlNode* pRoot; // root entry (parent) 68 short nCount; // tree size 69 short nCur; // current element 70 StgAvlNode* Find( short ); 71 public: 72 StgAvlIterator( StgAvlNode* ); 73 StgAvlNode* First(); 74 StgAvlNode* Last(); 75 StgAvlNode* Next(); 76 StgAvlNode* Prev(); 77 }; 78 79 #endif 80