CrystalSpace

Public API Reference

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 
00037 namespace CS
00038 {
00039 
00040 class SubRectanglesCompact;
00041 
00048 class CS_CRYSTALSPACE_EXPORT SubRectangles : public CS::Memory::CustomAllocated
00049 {
00050 public:
00054   class SubRect
00055   {
00056   private:
00057     csRect rect;
00058     csRect allocedRect;
00059   protected:
00060     friend class SubRectangles;
00061     friend class SubRectanglesCompact;
00062     typedef csBlockAllocator<SubRect> SubRectAlloc;
00063     friend class csBlockAllocator<SubRect>; // SubRectAlloc
00064 
00065     enum SplitType
00066     {
00067       SPLIT_UNSPLIT,
00068       SPLIT_H,
00069       SPLIT_V
00070     };
00071     enum AllocPos
00072     {
00073       ALLOC_INVALID = -1,
00074       ALLOC_RIGHT,
00075       ALLOC_BELOW,
00076       ALLOC_NEW
00077     };
00078     struct AllocInfo
00079     {
00080       SubRect* node;
00081       int d;
00082       AllocPos allocPos;
00083       bool res;
00084       
00085       AllocInfo() : node(0), d(0x7fffffff), allocPos(ALLOC_INVALID), 
00086         res(false) {};
00087     };
00088     friend struct AllocInfo; // Give MSVC6 access to ALLOC_INVALID.
00089 
00090     int splitPos;
00091     SplitType splitType;
00092 
00093     SubRectangles* superrect;
00094     SubRect* parent;
00095     SubRect* children[2];
00096 
00097     SubRect ();
00098     SubRect& operator= (const SubRect& other);
00099 
00101     const csRect& GetRect() const { return rect; }
00103     const csRect& GetAllocedRect() const { return allocedRect; }
00105     void MakeEmpty ()
00106     { allocedRect.Set (0, 0, -1, -1); }
00108     bool IsEmpty () const
00109     { return (allocedRect.xmax < 0) || (allocedRect.ymax < 0); }
00110 
00112     void TestAlloc (int w, int h, AllocInfo& ai);
00114     SubRect* Alloc (int w, int h, const AllocInfo& ai, csRect& r);
00116     void Reclaim ();
00117     bool IsReclaimed() const
00118     { return IsEmpty() && (splitType == SPLIT_UNSPLIT); }
00120     void TestCollapse ();
00121 
00124     void DecideBestSplit (const csRect& rect, int splitX, int splitY,
00125       SubRect::SplitType& splitType);
00126   };
00127   friend class SubRect; // Give MSVC6 access to enclosing protected scope.
00128 protected:
00130   csRect region;
00132   SubRect* root;
00133 
00134   SubRect::SubRectAlloc alloc;
00135   inline SubRect* AllocSubrect ()
00136   { 
00137     SubRect* sr = alloc.Alloc(); 
00138     sr->superrect = this;
00139     return sr;
00140   }
00141   void FreeSubrect (SubRect* sr);
00142 
00144   csArray<SubRect*> leaves;
00145   static int SubRectCompare (SubRect* const& sr1, SubRect* const& sr2);
00146   inline void AddLeaf (SubRect* sr)
00147   {
00148     leaves.InsertSorted (sr, SubRectCompare);
00149   }
00150   void RemoveLeaf (SubRect* sr)
00151   {
00152     size_t index = leaves.FindSortedKey (
00153       csArrayCmp<SubRect*, SubRect*> (sr, SubRectCompare));
00154     leaves.DeleteIndex (index);
00155   }
00156 
00158   void Split (SubRect* subRect, SubRect::SplitType split, int splitPos);
00159   
00160   void Grow (SubRect* sr, int ow, int oh, int nw, int nh,
00161     int touch);
00162   bool Shrink (SubRect* sr, int ow, int oh, int nw, int nh);
00163   csRect GetMinimumRectangle (SubRect* sr) const;
00164   void DupeWithOffset (const SubRect* from, SubRect* to, 
00165     int x, int y, csHash<SubRect*, csConstPtrKey<SubRect> >* map,
00166     const csRect& outerAllocated, const csRect& outerRect);
00167 public:
00169   SubRectangles (const csRect& region);
00170   SubRectangles (const SubRectangles& other);
00171 
00173   virtual ~SubRectangles ();
00174 
00176   const csRect& GetRectangle () const { return region; }
00177 
00181   virtual void Clear ();
00182 
00186   virtual SubRect* Alloc (int w, int h, csRect& rect);
00187 
00192   void Reclaim (SubRect* subrect);
00193 
00198   virtual bool Grow (int newWidth, int newHeight);
00199 
00207   virtual bool Shrink (int newWidth, int newHeight);
00208 
00212   csRect GetMinimumRectangle () const
00213   { return GetMinimumRectangle (root); }
00214 
00219   virtual bool PlaceInto (const SubRectangles* rectangles, 
00220     SubRect* subRect, 
00221     csHash<SubRect*, csConstPtrKey<SubRect> >* newRectangles = 0);
00222 
00228   void Dump (iObjectRegistry* object_reg, const char* tag = 0);
00229 
00235   void Dump (const char* tag = 0);
00236 };
00237 
00251 class CS_CRYSTALSPACE_EXPORT SubRectanglesCompact : public SubRectangles
00252 {
00253   const csRect maxArea;
00254   bool growPO2;
00255 
00256   inline int NewSize (int amount, int inc)
00257   { return growPO2 ? csFindNearestPowerOf2 (amount + inc) : amount + inc; }
00258 public:
00259   SubRectanglesCompact (const csRect& maxArea);
00260   SubRectanglesCompact (const SubRectanglesCompact& other);
00261 
00262   void Clear ();
00263   SubRect* Alloc (int w, int h, csRect& rect);
00264 
00266   const csRect& GetMaximumRectangle () const { return maxArea; }
00267 
00273   void SetGrowPO2 (bool growPO2) { this->growPO2 = growPO2; }
00275   bool GetGrowPO2 () const { return growPO2; }
00276 
00278   SubRect* AllocNoGrow (int w, int h, csRect& rect)
00279   {
00280     return SubRectangles::Alloc (w, h, rect);
00281   }
00282 };
00283 
00284 } // namespace CS
00285 
00286 typedef CS_DEPRECATED_TYPE_MSG("csSubRectangles renamed to CS::SubRectangles")
00287   CS::SubRectangles csSubRectangles;
00288 typedef CS_DEPRECATED_TYPE_MSG("csSubRect renamed to CS::SubRectangles::SubRect")
00289   CS::SubRectangles::SubRect csSubRect;
00290 
00293 #endif // __CS_SUBREC_H__
00294 

Generated for Crystal Space 1.2.1 by doxygen 1.5.3