Public API Reference

csgeom/subrec.h

Go to the documentation of this file.

/*
    Copyright (C) 2001-2005 by Jorrit Tyberghein
                  2003-2005 by Frank Richter

    This library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Library General Public
    License as published by the Free Software Foundation; either
    version 2 of the License, or (at your option) any later version.

    This library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Library General Public License for more details.

    You should have received a copy of the GNU Library General Public
    License along with this library; if not, write to the Free
    Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/

#ifndef __CS_SUBREC_H__
#define __CS_SUBREC_H__

#include "csextern.h"

#include "csgeom/csrect.h"

#include "csutil/array.h"
#include "csutil/blockallocator.h"

class CS_CRYSTALSPACE_EXPORT csSubRectangles
{
public:
  class SubRect
  {
  protected:
    friend class csSubRectangles;
    typedef csBlockAllocator<SubRect> SubRectAlloc;
    friend class csBlockAllocator<SubRect>; // SubRectAlloc

    enum SplitType
    {
      SPLIT_UNSPLIT,
      SPLIT_H,
      SPLIT_V
    };
    enum AllocPos
    {
      ALLOC_INVALID = -1,
      ALLOC_RIGHT,
      ALLOC_BELOW,
      ALLOC_NEW
    };
    struct AllocInfo
    {
      SubRect* node;
      int d;
      AllocPos allocPos;
      bool res;
      
      AllocInfo() : node(0), d(0x7fffffff), allocPos(ALLOC_INVALID), 
        res(false) {};
    };
    friend struct AllocInfo; // Give MSVC6 access to ALLOC_INVALID.

    csRect rect;
    csRect allocedRect;
    int splitPos;
    SplitType splitType;

    csSubRectangles* superrect;
    SubRect* parent;
    SubRect* children[2];

    SubRect ();
    SubRect& operator= (const SubRect& other);

    void TestAlloc (int w, int h, AllocInfo& ai);
    SubRect* Alloc (int w, int h, const AllocInfo& ai, csRect& r);
    void Reclaim ();
    void TestCollapse ();

    void DecideBestSplit (const csRect& rect, int splitX, int splitY,
      SubRect::SplitType& splitType);
  };
  friend class SubRect; // Give MSVC6 access to enclosing protected scope.
protected:
  csRect region;
  SubRect* root;

  SubRect::SubRectAlloc alloc;
  inline SubRect* AllocSubrect ()
  { return alloc.Alloc(); }
  void FreeSubrect (SubRect* sr);

  csArray<SubRect*> leaves;
  inline void AddLeaf (SubRect* sr)
  {
    leaves.InsertSorted (sr);
  }
  void RemoveLeaf (SubRect* sr)
  {
    size_t index = leaves.FindSortedKey (
      csArrayCmp<SubRect*, SubRect*> (sr));
    leaves.DeleteIndex (index);
  }
  
  void Grow (SubRect* sr, int ow, int oh, int nw, int nh);
public:
  csSubRectangles (const csRect& region);
  csSubRectangles (const csSubRectangles& other);

  ~csSubRectangles ();

  const csRect& GetRectangle () const { return region; }

  void Clear ();

  SubRect* Alloc (int w, int h, csRect& rect);

  void Reclaim (SubRect* subrect);

  bool Grow (int newWidth, int newHeight);

  void Dump ();
};

typedef csSubRectangles::SubRect csSubRect;

#endif // __CS_SUBREC_H__

---