sot/source/sdstor/stgavl.hxx

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