00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
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>;
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;
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;
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 }
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