michael@0: michael@0: michael@0: michael@0: michael@0: michael@0: michael@0: michael@0: Detailed Design Template michael@0: michael@0: michael@0: michael@0:

Gecko Layout Detailed Design Document

michael@0: michael@0:

Space Manager Detailed Design

michael@0: michael@0:

Overview

michael@0:

michael@0: The Space Manager and related classes and structures are an important of michael@0: the Gecko Layout system, specifically Block Layout. See the High Level michael@0: Design document for an overview of the Space Manager, and as an introduction michael@0: to the classes, structures and algorithms container in this, the Detailed michael@0: Design Document. michael@0:

michael@0: michael@0: michael@0: michael@0:

michael@0:

nsSpaceManager

michael@0:

michael@0: The Space Manager is the central class is a group of classes that manage michael@0: the occupied and available space that exists in horizontal bands across michael@0: a canvas. The primary goal of the Space Manager is to provide information michael@0: about those bands of space to support the CSS notion of floated elements. michael@0:

michael@0: michael@0:

michael@0: There are three important parts to the Space Manager API: the parts that michael@0: deal with the coordinate space of the Space Manager, the parts that deal with michael@0: the regions managed by the Space Manager, and the parts that manage float michael@0: impact intervals. michael@0:

michael@0: michael@0:

michael@0: The class nsSpaceManager is declared in the file michael@0: nsSpaceManger.h michael@0: . The class is only used in the layout module and cannot be exported michael@0: outside of that module (nor does it need to be). It is not a general michael@0: purpose class, and is not intended to be subclasses michael@0: . michael@0:

michael@0: michael@0:

michael@0: Here is the class declaration, taken from the source file as of 01.08.02 michael@0:

michael@0: michael@0: michael@0: michael@0:

/**
michael@0:  * Class for dealing with bands of available space. The space manager
michael@0:  * defines a coordinate space with an origin at (0, 0) that grows down
michael@0:  * and to the right.
michael@0:  */
michael@0: class nsSpaceManager {
michael@0: public:
michael@0:   nsSpaceManager(nsIPresShell* aPresShell, nsIFrame* aFrame);
michael@0:   ~nsSpaceManager();
michael@0: 
michael@0:   void* operator new(size_t aSize);
michael@0:   void operator delete(void* aPtr, size_t aSize);
michael@0: 
michael@0:   static void Shutdown();
michael@0: 
michael@0:   /*
michael@0:    * Get the frame that's associated with the space manager. This frame
michael@0:    * created the space manager, and the world coordinate space is
michael@0:    * relative to this frame.
michael@0:    *
michael@0:    * You can use QueryInterface() on this frame to get any additional
michael@0:    * interfaces.
michael@0:    */
michael@0:   nsIFrame* GetFrame() const { return mFrame; }
michael@0: 
michael@0:   /**
michael@0:    * Translate the current origin by the specified (dx, dy). This
michael@0:    * creates a new local coordinate space relative to the current
michael@0:    * coordinate space.
michael@0:    */
michael@0:   void Translate(nscoord aDx, nscoord aDy) { mX += aDx; mY += aDy; }
michael@0: 
michael@0:   /**
michael@0:    * Returns the current translation from local coordinate space to
michael@0:    * world coordinate space. This represents the accumulated calls to
michael@0:    * Translate().
michael@0:    */
michael@0:   void GetTranslation(nscoord& aX, nscoord& aY) const { aX = mX; aY = mY; }
michael@0: 
michael@0:   /**
michael@0:    * Returns the y-most of the bottommost band or 0 if there are no bands.
michael@0:    *
michael@0:    * @return  PR_TRUE if there are bands and PR_FALSE if there are no bands
michael@0:    */
michael@0:   PRBool YMost(nscoord& aYMost) const;
michael@0: 
michael@0:   /**
michael@0:    * Returns a band starting at the specified y-offset. The band data
michael@0:    * indicates which parts of the band are available, and which parts
michael@0:    * are unavailable
michael@0:    *
michael@0:    * The band data that is returned is in the coordinate space of the
michael@0:    * local coordinate system.
michael@0:    *
michael@0:    * The local coordinate space origin, the y-offset, and the max size
michael@0:    * describe a rectangle that's used to clip the underlying band of
michael@0:    * available space, i.e.
michael@0:    * {0, aYOffset, aMaxSize.width, aMaxSize.height} in the local
michael@0:    * coordinate space
michael@0:    *
michael@0:    * @param   aYOffset the y-offset of where the band begins. The coordinate is
michael@0:    *            relative to the upper-left corner of the local coordinate space
michael@0:    * @param   aMaxSize the size to use to constrain the band data
michael@0:    * @param   aBandData [in,out] used to return the list of trapezoids that
michael@0:    *            describe the available space and the unavailable space
michael@0:    * @return  NS_OK if successful and NS_ERROR_FAILURE if the band data is not
michael@0:    *            not large enough. The 'count' member of the band data struct
michael@0:    *            indicates how large the array of trapezoids needs to be
michael@0:    */
michael@0:   nsresult GetBandData(nscoord       aYOffset,
michael@0:                        const nsSize& aMaxSize,
michael@0:                        nsBandData&   aBandData) const;
michael@0: 
michael@0:   /**
michael@0:    * Add a rectangular region of unavailable space. The space is
michael@0:    * relative to the local coordinate system.
michael@0:    *
michael@0:    * The region is tagged with a frame
michael@0:    *
michael@0:    * @param   aFrame the frame used to identify the region. Must not be NULL
michael@0:    * @param   aUnavailableSpace the bounding rect of the unavailable space
michael@0:    * @return  NS_OK if successful
michael@0:    *          NS_ERROR_FAILURE if there is already a region tagged with aFrame
michael@0:    */
michael@0:   nsresult AddRectRegion(nsIFrame*     aFrame,
michael@0:                          const nsRect& aUnavailableSpace);
michael@0: 
michael@0:   /**
michael@0:    * Resize the rectangular region associated with aFrame by the specified
michael@0:    * deltas. The height change always applies to the bottom edge or the existing
michael@0:    * rect. You specify whether the width change applies to the left or right edge
michael@0:    *
michael@0:    * Returns NS_OK if successful, NS_ERROR_INVALID_ARG if there is no region
michael@0:    * tagged with aFrame
michael@0:    */
michael@0:   enum AffectedEdge {LeftEdge, RightEdge};
michael@0:   nsresult ResizeRectRegion(nsIFrame*    aFrame,
michael@0:                             nscoord      aDeltaWidth,
michael@0:                             nscoord      aDeltaHeight,
michael@0:                             AffectedEdge aEdge = RightEdge);
michael@0: 
michael@0:   /**
michael@0:    * Offset the region associated with aFrame by the specified amount.
michael@0:    *
michael@0:    * Returns NS_OK if successful, NS_ERROR_INVALID_ARG if there is no region
michael@0:    * tagged with aFrame
michael@0:    */
michael@0:   nsresult OffsetRegion(nsIFrame* aFrame, nscoord dx, nscoord dy);
michael@0: 
michael@0:   /**
michael@0:    * Remove the region associated with aFrane.
michael@0:    *
michael@0:    * Returns NS_OK if successful and NS_ERROR_INVALID_ARG if there is no region
michael@0:    * tagged with aFrame
michael@0:    */
michael@0:   nsresult RemoveRegion(nsIFrame* aFrame);
michael@0: 
michael@0:   /**
michael@0:    * Clears the list of regions representing the unavailable space.
michael@0:    */
michael@0:   void ClearRegions();
michael@0: 
michael@0:   /**
michael@0:    * Methods for dealing with the propagation of float damage during
michael@0:    * reflow.
michael@0:    */
michael@0:   PRBool HasFloatDamage()
michael@0:   {
michael@0:     return !mFloatDamage.IsEmpty();
michael@0:   }
michael@0: 
michael@0:   void IncludeInDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
michael@0:   {
michael@0:     mFloatDamage.IncludeInterval(aIntervalBegin + mY, aIntervalEnd + mY);
michael@0:   }
michael@0: 
michael@0:   PRBool IntersectsDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
michael@0:   {
michael@0:     return mFloatDamage.Intersects(aIntervalBegin + mY, aIntervalEnd + mY);
michael@0:   }
michael@0: 
michael@0: #ifdef DEBUG
michael@0:   /**
michael@0:    * Dump the state of the spacemanager out to a file
michael@0:    */
michael@0:   nsresult List(FILE* out);
michael@0: 
michael@0:   void SizeOf(nsISizeOfHandler* aHandler, uint32_t* aResult) const;
michael@0: #endif
michael@0: 
michael@0: private:
michael@0:   // Structure that maintains information about the region associated
michael@0:   // with a particular frame
michael@0:   struct FrameInfo {
michael@0:     nsIFrame* const mFrame;
michael@0:     nsRect          mRect;       // rectangular region
michael@0:     FrameInfo*      mNext;
michael@0: 
michael@0:     FrameInfo(nsIFrame* aFrame, const nsRect& aRect);
michael@0: #ifdef NS_BUILD_REFCNT_LOGGING
michael@0:     ~FrameInfo();
michael@0: #endif
michael@0:   };
michael@0: 
michael@0:   // Doubly linked list of band rects
michael@0:   struct BandRect : PRCListStr {
michael@0:     nscoord   mLeft, mTop;
michael@0:     nscoord   mRight, mBottom;
michael@0:     int32_t   mNumFrames;    // number of frames occupying this rect
michael@0:     union {
michael@0:       nsIFrame*    mFrame;   // single frame occupying the space
michael@0:       nsVoidArray* mFrames;  // list of frames occupying the space
michael@0:     };
michael@0: 
michael@0:     BandRect(nscoord aLeft, nscoord aTop,
michael@0:              nscoord aRight, nscoord aBottom,
michael@0:              nsIFrame*);
michael@0:     BandRect(nscoord aLeft, nscoord aTop,
michael@0:              nscoord aRight, nscoord aBottom,
michael@0:              nsVoidArray*);
michael@0:     ~BandRect();
michael@0: 
michael@0:     // List operations
michael@0:     BandRect* Next() const {return (BandRect*)PR_NEXT_LINK(this);}
michael@0:     BandRect* Prev() const {return (BandRect*)PR_PREV_LINK(this);}
michael@0:     void      InsertBefore(BandRect* aBandRect) {PR_INSERT_BEFORE(aBandRect, this);}
michael@0:     void      InsertAfter(BandRect* aBandRect) {PR_INSERT_AFTER(aBandRect, this);}
michael@0:     void      Remove() {PR_REMOVE_LINK(this);}
michael@0: 
michael@0:     // Split the band rect into two vertically, with this band rect becoming
michael@0:     // the top part, and a new band rect being allocated and returned for the
michael@0:     // bottom part
michael@0:     //
michael@0:     // Does not insert the new band rect into the linked list
michael@0:     BandRect* SplitVertically(nscoord aBottom);
michael@0: 
michael@0:     // Split the band rect into two horizontally, with this band rect becoming
michael@0:     // the left part, and a new band rect being allocated and returned for the
michael@0:     // right part
michael@0:     //
michael@0:     // Does not insert the new band rect into the linked list
michael@0:     BandRect* SplitHorizontally(nscoord aRight);
michael@0: 
michael@0:     // Accessor functions
michael@0:     PRBool  IsOccupiedBy(const nsIFrame*) const;
michael@0:     void    AddFrame(const nsIFrame*);
michael@0:     void    RemoveFrame(const nsIFrame*);
michael@0:     PRBool  HasSameFrameList(const BandRect* aBandRect) const;
michael@0:     int32_t Length() const;
michael@0:   };
michael@0: 
michael@0:   // Circular linked list of band rects
michael@0:   struct BandList : BandRect {
michael@0:     BandList();
michael@0: 
michael@0:     // Accessors
michael@0:     PRBool    IsEmpty() const {return PR_CLIST_IS_EMPTY((PRCListStr*)this);}
michael@0:     BandRect* Head() const {return (BandRect*)PR_LIST_HEAD(this);}
michael@0:     BandRect* Tail() const {return (BandRect*)PR_LIST_TAIL(this);}
michael@0: 
michael@0:     // Operations
michael@0:     void      Append(BandRect* aBandRect) {PR_APPEND_LINK(aBandRect, this);}
michael@0: 
michael@0:     // Remove and delete all the band rects in the list
michael@0:     void      Clear();
michael@0:   };
michael@0: 
michael@0: 
michael@0:   FrameInfo* GetFrameInfoFor(nsIFrame* aFrame);
michael@0:   FrameInfo* CreateFrameInfo(nsIFrame* aFrame, const nsRect& aRect);
michael@0:   void       DestroyFrameInfo(FrameInfo*);
michael@0: 
michael@0:   void       ClearFrameInfo();
michael@0:   void       ClearBandRects();
michael@0: 
michael@0:   BandRect*  GetNextBand(const BandRect* aBandRect) const;
michael@0:   void       DivideBand(BandRect* aBand, nscoord aBottom);
michael@0:   PRBool     CanJoinBands(BandRect* aBand, BandRect* aPrevBand);
michael@0:   PRBool     JoinBands(BandRect* aBand, BandRect* aPrevBand);
michael@0:   void       AddRectToBand(BandRect* aBand, BandRect* aBandRect);
michael@0:   void       InsertBandRect(BandRect* aBandRect);
michael@0: 
michael@0:   nsresult   GetBandAvailableSpace(const BandRect* aBand,
michael@0:                                    nscoord         aY,
michael@0:                                    const nsSize&   aMaxSize,
michael@0:                                    nsBandData&     aAvailableSpace) const;
michael@0: 
michael@0:   nsIFrame* const mFrame;     // frame associated with the space manager
michael@0:   nscoord         mX, mY;     // translation from local to global coordinate space
michael@0:   BandList        mBandList;  // header/sentinel for circular linked list of band rects
michael@0:   FrameInfo*      mFrameInfoMap;
michael@0:   nsIntervalSet   mFloatDamage;
michael@0: 
michael@0:   static int32_t sCachedSpaceManagerCount;
michael@0:   static void* sCachedSpaceManagers[NS_SPACE_MANAGER_CACHE_SIZE];
michael@0: 
michael@0:   nsSpaceManager(const nsSpaceManager&);  // no implementation
michael@0:   void operator=(const nsSpaceManager&);  // no implementation
michael@0: };
michael@0: 
michael@0:

michael@0: michael@0:

Public API

michael@0: michael@0:

Life Cycle:

michael@0:

michael@0: The Constructor requires a Presentation Shell, used for arena allocations michael@0: mostly, and a frame that this Space Manager is rooted on. The coordinate michael@0: space of this Space Manager is relative to the frame passed in to the constructor. michael@0:

michael@0: michael@0:

  nsSpaceManager(nsIPresShell* aPresShell, nsIFrame* aFrame);
michael@0:   ~nsSpaceManager();
michael@0:

michael@0:

michael@0: Operators 'new' and 'delete' are overridden to support a recycler. Space michael@0: Manager instances come and go pretty frequently, and this recycler prevents michael@0: excessive heap allocations and the performance penalties associated with michael@0: it. The #define NS_SPACE_MANAGER_CACHE_SIZE is used to control the number michael@0: of Space Manager instances that can be present in the recycler, currently michael@0: 4. If more than NS_SPACE_MANAGER_CACHE_SIZE are allocated at a time, michael@0: then standard allocation is used. michael@0:

michael@0: michael@0:

michael@0:   void* operator new(size_t aSize);
michael@0:   void operator delete(void* aPtr, size_t aSize);
michael@0: 
michael@0:

michael@0:

michael@0: A Static method is used to shutdown the Space Manager recycling. This michael@0: method deletes all of the Space Mangers inthe recycler,and prevents further michael@0: recycling. It is meant to be called only when the layout module is being michael@0: terminated. michael@0:

michael@0: michael@0:

  static void Shutdown();
michael@0: 
michael@0:

michael@0: michael@0:

Origin / Coordinate Space Translation

michael@0: michael@0:

  /**
michael@0:    * Translate the current origin by the specified (dx, dy). This
michael@0:    * creates a new local coordinate space relative to the current
michael@0:    * coordinate space.
michael@0:    */
michael@0:   void Translate(nscoord aDx, nscoord aDy) { mX += aDx; mY += aDy; }
michael@0: 
michael@0:   /**
michael@0:    * Returns the current translation from local coordinate space to
michael@0:    * world coordinate space. This represents the accumulated calls to
michael@0:    * Translate().
michael@0:    */
michael@0:   void GetTranslation(nscoord& aX, nscoord& aY) const { aX = mX; aY = mY; }
michael@0: 
michael@0:   /**
michael@0:    * Returns the y-most of the bottommost band or 0 if there are no bands.
michael@0:    *
michael@0:    * @return  PR_TRUE if there are bands and PR_FALSE if there are no bands
michael@0:    */
michael@0:   PRBool YMost(nscoord& aYMost) const;
michael@0:

michael@0: michael@0:

Region Management

michael@0: michael@0:

  /**
michael@0:    * Returns a band starting at the specified y-offset. The band data
michael@0:    * indicates which parts of the band are available, and which parts
michael@0:    * are unavailable
michael@0:    *
michael@0:    * The band data that is returned is in the coordinate space of the
michael@0:    * local coordinate system.
michael@0:    *
michael@0:    * The local coordinate space origin, the y-offset, and the max size
michael@0:    * describe a rectangle that's used to clip the underlying band of
michael@0:    * available space, i.e.
michael@0:    * {0, aYOffset, aMaxSize.width, aMaxSize.height} in the local
michael@0:    * coordinate space
michael@0:    *
michael@0:    * @param   aYOffset the y-offset of where the band begins. The coordinate is
michael@0:    *            relative to the upper-left corner of the local coordinate space
michael@0:    * @param   aMaxSize the size to use to constrain the band data
michael@0:    * @param   aBandData [in,out] used to return the list of trapezoids that
michael@0:    *            describe the available space and the unavailable space
michael@0:    * @return  NS_OK if successful and NS_ERROR_FAILURE if the band data is not
michael@0:    *            not large enough. The 'count' member of the band data struct
michael@0:    *            indicates how large the array of trapezoids needs to be
michael@0:    */
michael@0:   nsresult GetBandData(nscoord       aYOffset,
michael@0:                        const nsSize& aMaxSize,
michael@0:                        nsBandData&   aBandData) const;
michael@0: 
michael@0:   /**
michael@0:    * Add a rectangular region of unavailable space. The space is
michael@0:    * relative to the local coordinate system.
michael@0:    *
michael@0:    * The region is tagged with a frame
michael@0:    *
michael@0:    * @param   aFrame the frame used to identify the region. Must not be NULL
michael@0:    * @param   aUnavailableSpace the bounding rect of the unavailable space
michael@0:    * @return  NS_OK if successful
michael@0:    *          NS_ERROR_FAILURE if there is already a region tagged with aFrame
michael@0:    */
michael@0:   nsresult AddRectRegion(nsIFrame*     aFrame,
michael@0:                          const nsRect& aUnavailableSpace);
michael@0: 
michael@0:   /**
michael@0:    * Resize the rectangular region associated with aFrame by the specified
michael@0:    * deltas. The height change always applies to the bottom edge or the existing
michael@0:    * rect. You specify whether the width change applies to the left or right edge
michael@0:    *
michael@0:    * Returns NS_OK if successful, NS_ERROR_INVALID_ARG if there is no region
michael@0:    * tagged with aFrame
michael@0:    */
michael@0:   enum AffectedEdge {LeftEdge, RightEdge};
michael@0:   nsresult ResizeRectRegion(nsIFrame*    aFrame,
michael@0:                             nscoord      aDeltaWidth,
michael@0:                             nscoord      aDeltaHeight,
michael@0:                             AffectedEdge aEdge = RightEdge);
michael@0: 
michael@0:   /**
michael@0:    * Offset the region associated with aFrame by the specified amount.
michael@0:    *
michael@0:    * Returns NS_OK if successful, NS_ERROR_INVALID_ARG if there is no region
michael@0:    * tagged with aFrame
michael@0:    */
michael@0:   nsresult OffsetRegion(nsIFrame* aFrame, nscoord dx, nscoord dy);
michael@0: 
michael@0:   /**
michael@0:    * Remove the region associated with aFrane.
michael@0:    *
michael@0:    * Returns NS_OK if successful and NS_ERROR_INVALID_ARG if there is no region
michael@0:    * tagged with aFrame
michael@0:    */
michael@0:   nsresult RemoveRegion(nsIFrame* aFrame);
michael@0: 
michael@0:   /**
michael@0:    * Clears the list of regions representing the unavailable space.
michael@0:    */
michael@0:   void ClearRegions();
michael@0:

michael@0: michael@0:

Float Impact

michael@0: michael@0:

  /**
michael@0:    * Methods for dealing with the propagation of float damage during
michael@0:    * reflow.
michael@0:    */
michael@0:   PRBool HasFloatDamage()
michael@0:   {
michael@0:     return !mFloatDamage.IsEmpty();
michael@0:   }
michael@0: 
michael@0:   void IncludeInDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
michael@0:   {
michael@0:     mFloatDamage.IncludeInterval(aIntervalBegin + mY, aIntervalEnd + mY);
michael@0:   }
michael@0: 
michael@0:   PRBool IntersectsDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
michael@0:   {
michael@0:     return mFloatDamage.Intersects(aIntervalBegin + mY, aIntervalEnd + mY);
michael@0:   }
michael@0:

michael@0: michael@0:

Debug Only Methods

michael@0: michael@0:

  /**
michael@0:    * Dump the state of the spacemanager out to a file
michael@0:    */
michael@0:   nsresult List(FILE* out);
michael@0: 
michael@0:   void SizeOf(nsISizeOfHandler* aHandler, uint32_t* aResult) const;
michael@0: 
michael@0:

michael@0: michael@0:

Unused / Obsolete Methods

michael@0: michael@0:

  /*
michael@0:    * Get the frame that's associated with the space manager. This frame
michael@0:    * created the space manager, and the world coordinate space is
michael@0:    * relative to this frame.
michael@0:    *
michael@0:    * You can use QueryInterface() on this frame to get any additional
michael@0:    * interfaces.
michael@0:    */
michael@0:    nsIFrame* GetFrame() const { return mFrame; }
michael@0: 
michael@0:

michael@0: michael@0:

Implementation Notes

michael@0: michael@0:

Algorithm 1: GetBandData

michael@0:

michael@0: GetBandData is used to provide information to clients about what space if michael@0: available and unavailable in a band of space. The client provides a michael@0: vertical offset, the yOffset, that corresponds to the band that is of interest. michael@0: This will be the y offset of the frame that is being reflowed. The michael@0: caller also provides a collection of BandData objects (an array) and the michael@0: number of items that the collection can handle. If the collection is michael@0: too small, then an error is returned and the count is updated to indicate michael@0: the size required. michael@0:

michael@0: michael@0:

michael@0: The algorithm to provide the band data is as follows: michael@0:

michael@0:

Get a vertical offset in world coordinates (instead of frame-relative michael@0: coordinates) by adding the y-origin of the SpaceManager to the y offset passed michael@0: in
If the (adjusted) y value passed in is greater than the greatest band michael@0: being managed, then all space is available so a single trapezoid is returned, michael@0: marked as available and sized to the maximum size value (passed in).
If the (adjusted) y offset intersects a band, then gather the band michael@0: data:

walk the internal bandData list from head to tail
for each band data entry, see if the top of the band is greater than michael@0: the (adjusted) y offset requested
if it is, then band is below the offset requested, so the area between michael@0: the band and the y offset is available - create a trapezoid with that region michael@0: and return it.
if the (adjusted) y offset is between the band top and bottom, then michael@0: get the available space for the band by calling GetBandAvailableSpace
otherwise, move to the next band

michael@0:

GetBandAvailableSpace:

michael@0: This method is called from GetBandData only. It walks all of the bands in michael@0: the space manager and determines which bands intersect with the band passed michael@0: in, and if within those bands there are regions that are available or occupied. michael@0: michael@0:

First, walk all of the bands until a band that is to the right of the michael@0: desired offset is located
Starting at that band, walk the remaining bands:

if the current band is to the right of the requested band, then there michael@0: is available space.

if there is more room in the bandData collection, then add a trapezoid michael@0: to the bandData collection such that it is marked as available and has a michael@0: rect that represents the space between the reference band tna dht band being michael@0: examined
if there is no more room in the BandData collection, estimate the michael@0: number of entries requires as the current count + twice the number of bands michael@0: below the reference band, plus two. Return an error code so the caller michael@0: can reallocate the collection and try again.

check the size of the collection again, if there is no room left michael@0: then estimate the number of items requires as the current count + twice the michael@0: number of bands below the band in question plus one.
create a new trapezoid in the band collection that has a region corresponding michael@0: to the reference band rect, marked as occupied by either a single or multiple michael@0: frames.
move to the next band

after walking all of the band data, se if we have reached the right michael@0: edge of the band.

If not, then check for space in the band collection

if there is no room left, then set the count to the current count michael@0: plus 1 and return an error.
otherwise, create another entry in the band collection, marked michael@0: as available, and with a rect corresponding to the area remainin in the band michael@0: (eg. from the right edge of the last band rect to the right edge of the band).

michael@0: michael@0:

Algorithm 2: AddRectRegion

michael@0: Clients call into this method to notify the Space Manager that a new frame michael@0: is occupying some space. michael@0: michael@0:

First, try to get frame info for the frame. If it is found, return michael@0: an error since the frame is already associated with a region in the Space michael@0: Manager.
Next, create a rect from the occupied space passed in by the caller, michael@0: transforming it first to world-coordinates by adding the Space Manager's michael@0: offset to the occupied space rect passed in.
Create a new Frame Info instance for the frame and rect, returning michael@0: an error if allocation fails.
Check if the occupied space rect (adjusted) is empty, if so, return michael@0: an error (NOTE: this could be done earlier, or michael@0: prevented by the caller)
Allocate a new BandRect instance with the rect and frame as constructor michael@0: arguments, and insert it into the collection via InsertBandRect

michael@0:

InsertBandRect:

michael@0: Internal method to insert a band rect into the BandList in the correct location. michael@0: There are several cases it has to handle, as specified in the source file michael@0: comments: michael@0: michael@0:

// When comparing a rect to a band there are seven cases to consider.
michael@0: // 'R' is the rect and 'B' is the band.
michael@0: //
michael@0: //      Case 1              Case 2              Case 3              Case 4
michael@0: //      ------              ------              ------              ------
michael@0: // +-----+             +-----+                      +-----+             +-----+
michael@0: // |  R  |             |  R  |  +-----+    +-----+  |     |             |     |
michael@0: // +-----+             +-----+  |     |    |  R  |  |  B  |             |  B  |
michael@0: //          +-----+             |  B  |    +-----+  |     |    +-----+  |     |
michael@0: //          |     |             |     |             +-----+    |  R  |  +-----+
michael@0: //          |  B  |             +-----+                        +-----+
michael@0: //          |     |
michael@0: //          +-----+
michael@0: //
michael@0: //
michael@0: //
michael@0: //      Case 5              Case 6              Case 7
michael@0: //      ------              ------              ------
michael@0: //          +-----+    +-----+  +-----+    +-----+
michael@0: //          |     |    |  R  |  |  B  |    |     |  +-----+
michael@0: //          |  B  |    +-----+  +-----+    |  R  |  |  B  |
michael@0: //          |     |                        |     |  +-----+
michael@0: //          +-----+                        +-----+
michael@0: // +-----+
michael@0: // |  R  |
michael@0: // +-----+
michael@0: //
michael@0:

michael@0:

First, check for the easiest case, where there are no existing band michael@0: rects, or the band rect passed in is below the bottommost rect. In this case, michael@0: just append the band rect and return.
Starting at the head of the list of bandRects, check for intersection michael@0: with the rect passed in:

case #1: the rect is totally above the current band rect, so insert michael@0: a new band rect before the current bandRect
cases #2 and #7: the rect is partially above the band rect, so it michael@0: is divided into two bandRects, one entirely above the band, and one containing michael@0: the remainder of the rect. Insert the part that is totally above the michael@0: bandRect before the current bandRect, as in case #1 above, and adjust the michael@0: other band rect to exclude the part already added.
case #5: the rect is totally below the current bandRect, so just michael@0: skip to the next band
case #3 and #4: rect is at least partially intersection with the michael@0: bandRect, so divide the current band into two parts, where the top part is michael@0: above the current rect. Move to the new band just created, which is michael@0: the next band.
case #6: the rect shares the bottom and height with the bandRect, michael@0: so just add the rect to the band.
case #4 and #7: create a new rect for the part that overlaps the michael@0: bandRect, and add it to the current bandRect (similar to case #6) and then michael@0: move on to the next band, removing that part from the rect passed in. If michael@0: no more bands, append the rect passed in to the end of the bandRect list.

michael@0: This algorithm is pretty confusing - basically what needs to happen is michael@0: that rects and bands need to be divided up so that complicated cases like michael@0: #2, #4, and #7, are reduced to simpler cases where the rects is totally above, michael@0: below, or between a band rect. From the current implementation, it michael@0: might be worth verifying that the final result of the inserts is a correctly michael@0: ordered liest of bandRects (debug mode only). michael@0: michael@0: michael@0:

Algorithm 3: RemoveRegion

michael@0: When a float is removed, the Space Manager is notified by a call to RemoveRegion, michael@0: passing in the frame that is being removed. michael@0: michael@0:

Get the FrameInfo for the frame passed in. If not found, an error is michael@0: returned.
If the rect for the frame is not empty, then visit each band in the michael@0: bandList:

for each rect in the band: michael@0: michael@0:

if the bandRect is occupied by the frame, either remove the frame michael@0: from the bandRect (if there are other frames sharing it) and remember that michael@0: it was shared
otherwise simply remove the bandRect (no other frames share it).
if the bandRect was shared, then try to coalesce adjacent bandRects

if the previous bandRect is directly next to the current bandRect, michael@0: and they have the same frame list, then make the current bandRect cover the michael@0: previous bandRect's full region (adjust the left edge to be that of the previous michael@0: bandRect) and remove the previous bandRect.

if the current band or prior band had a rect occupied byu the frame, michael@0: then try to join the two bands via JoinBands

Finally, destroy the frameInfo for the frame. michael@0: michael@0:

michael@0: michael@0:
michael@0: michael@0:

michael@0:

Cross-Component Algorithms

michael@0: michael@0:
michael@0: michael@0: michael@0: michael@0:

michael@0:

Tech Notes

michael@0:

michael@0: michael@0:

michael@0: michael@0: michael@0: michael@0: michael@0: michael@0: michael@0: