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 00187 bool IsEmpty() const { return root->IsReclaimed(); } 00188 00192 virtual SubRect* Alloc (int w, int h, csRect& rect); 00193 00198 void Reclaim (SubRect* subrect); 00199 00204 virtual bool Grow (int newWidth, int newHeight); 00205 00213 virtual bool Shrink (int newWidth, int newHeight); 00214 00218 csRect GetMinimumRectangle () const 00219 { return GetMinimumRectangle (root); } 00220 00225 virtual bool PlaceInto (const SubRectangles* rectangles, 00226 SubRect* subRect, 00227 csHash<SubRect*, csConstPtrKey<SubRect> >* newRectangles = 0); 00228 00234 void Dump (iObjectRegistry* object_reg, const char* tag = 0); 00235 00241 void Dump (const char* tag = 0); 00242 }; 00243 00257 class CS_CRYSTALSPACE_EXPORT SubRectanglesCompact : public SubRectangles 00258 { 00259 const csRect maxArea; 00260 bool growPO2; 00261 00262 inline int NewSize (int amount, int inc) 00263 { return growPO2 ? csFindNearestPowerOf2 (amount + inc) : amount + inc; } 00264 public: 00265 SubRectanglesCompact (const csRect& maxArea); 00266 SubRectanglesCompact (const SubRectanglesCompact& other); 00267 00268 void Clear (); 00269 SubRect* Alloc (int w, int h, csRect& rect); 00270 00272 const csRect& GetMaximumRectangle () const { return maxArea; } 00273 00279 void SetGrowPO2 (bool growPO2) { this->growPO2 = growPO2; } 00281 bool GetGrowPO2 () const { return growPO2; } 00282 00284 SubRect* AllocNoGrow (int w, int h, csRect& rect) 00285 { 00286 return SubRectangles::Alloc (w, h, rect); 00287 } 00288 }; 00289 00290 } // namespace CS 00291 00292 typedef CS_DEPRECATED_TYPE_MSG("csSubRectangles renamed to CS::SubRectangles") 00293 CS::SubRectangles csSubRectangles; 00294 typedef CS_DEPRECATED_TYPE_MSG("csSubRect renamed to CS::SubRectangles::SubRect") 00295 CS::SubRectangles::SubRect csSubRect; 00296 00299 #endif // __CS_SUBREC_H__ 00300
Generated for Crystal Space 2.0 by doxygen 1.6.1