## Public API Reference

- Main Page
- Modules
- Namespaces
- Classes
- Files
- Related Pages

- File List
- File Members

# csgeom/subrec.h

Go to the documentation of this file.

    00001 /*
    00002     Copyright (C) 2001-2005 by Jorrit Tyberghein
    00003                   2003-2005 by Frank Richter
    00004
    00005     This library is free software; you can redistribute it and/or
    00006     modify it under the terms of the GNU Library General Public
    00007     License as published by the Free Software Foundation; either
    00008     version 2 of the License, or (at your option) any later version.
    00009
    00010     This library is distributed in the hope that it will be useful,
    00011     but WITHOUT ANY WARRANTY; without even the implied warranty of
    00012     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    00013     Library General Public License for more details.
    00014
    00015     You should have received a copy of the GNU Library General Public
    00016     License along with this library; if not, write to the Free
    00017     Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
    00018 */
    00019
    00020 #ifndef __CS_SUBREC_H__
    00021 #define __CS_SUBREC_H__
    00022
    00030 #include "csextern.h"
    00031
    00032 #include "csgeom/csrect.h"
    00033
    00034 #include "csutil/array.h"
    00035 #include "csutil/blockallocator.h"
    00036
    00042 class CS_CRYSTALSPACE_EXPORT csSubRectangles
    00043 {
    00044 public:
    00048   class SubRect
    00049   {
    00050   protected:
    00051     friend class csSubRectangles;
    00052     typedef csBlockAllocator<SubRect> SubRectAlloc;
    00053     friend class csBlockAllocator<SubRect>; // SubRectAlloc
    00054
    00055     enum SplitType
    00056     {
    00057       SPLIT_UNSPLIT,
    00058       SPLIT_H,
    00059       SPLIT_V
    00060     };
    00061     enum AllocPos
    00062     {
    00063       ALLOC_INVALID = -1,
    00064       ALLOC_RIGHT,
    00065       ALLOC_BELOW,
    00066       ALLOC_NEW
    00067     };
    00068     struct AllocInfo
    00069     {
    00070       SubRect* node;
    00071       int d;
    00072       AllocPos allocPos;
    00073       bool res;
    00074
    00075       AllocInfo() : node(0), d(0x7fffffff), allocPos(ALLOC_INVALID),
    00076         res(false) {};
    00077     };
    00078     friend struct AllocInfo; // Give MSVC6 access to ALLOC_INVALID.
    00079
    00080     csRect rect;
    00081     csRect allocedRect;
    00082     int splitPos;
    00083     SplitType splitType;
    00084
    00085     csSubRectangles* superrect;
    00086     SubRect* parent;
    00087     SubRect* children[2];
    00088
    00089     SubRect ();
    00090
    00092     void TestAlloc (int w, int h, AllocInfo& ai);
    00094     SubRect* Alloc (int w, int h, const AllocInfo& ai, csRect& r);
    00096     void Reclaim ();
    00098     void TestCollapse ();
    00099
    00102     void DecideBestSplit (const csRect& rect, int splitX, int splitY,
    00103       SubRect::SplitType& splitType);
    00104   };
    00105   friend class SubRect; // Give MSVC6 access to enclosing protected scope.
    00106
    00107 protected:
    00109   csRect region;
    00111   SubRect* root;
    00112
    00113   SubRect::SubRectAlloc alloc;
    00114   inline SubRect* AllocSubrect ()
    00115   { return alloc.Alloc(); }
    00116   void FreeSubrect (SubRect* sr);
    00117
    00119   csArray<SubRect*> leaves;
    00120   inline void AddLeaf (SubRect* sr)
    00121   {
    00122     leaves.InsertSorted (sr);
    00123   }
    00124   void RemoveLeaf (SubRect* sr)
    00125   {
    00126     size_t index = leaves.FindSortedKey (
    00127       csArrayCmp<SubRect*, SubRect*> (sr));
    00128     leaves.DeleteIndex (index);
    00129   }
    00130
    00131   void Grow (SubRect* sr, int ow, int oh, int nw, int nh);
    00132 public:
    00134   csSubRectangles (const csRect& region);
    00135
    00137   ~csSubRectangles ();
    00138
    00140   const csRect& GetRectangle () const { return region; }
    00141
    00145   void Clear ();
    00146
    00150   SubRect* Alloc (int w, int h, csRect& rect);
    00151
    00156   void Reclaim (SubRect* subrect);
    00157
    00162   bool Grow (int newWidth, int newHeight);
    00163
    00167   void Dump ();
    00168 };
    00169
    00170 typedef csSubRectangles::SubRect csSubRect;
    00171
    00174 #endif // __CS_SUBREC_H__
    00175