summaryrefslogtreecommitdiffstats
path: root/layout/doc/DD-SpaceManager.html
diff options
context:
space:
mode:
Diffstat (limited to 'layout/doc/DD-SpaceManager.html')
-rw-r--r--layout/doc/DD-SpaceManager.html743
1 files changed, 743 insertions, 0 deletions
diff --git a/layout/doc/DD-SpaceManager.html b/layout/doc/DD-SpaceManager.html
new file mode 100644
index 000000000..39cd16597
--- /dev/null
+++ b/layout/doc/DD-SpaceManager.html
@@ -0,0 +1,743 @@
+<!-- This Source Code Form is subject to the terms of the Mozilla Public
+ - License, v. 2.0. If a copy of the MPL was not distributed with this
+ - file, You can obtain one at http://mozilla.org/MPL/2.0/. -->
+
+<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
+<html>
+<head>
+
+ <meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
+ <title>Detailed Design Template</title>
+</head>
+ <body>
+
+<h1><font color="#cc0000">Gecko Layout Detailed Design Document</font></h1>
+
+<h1>Space Manager Detailed Design</h1>
+
+<h2>Overview</h2>
+<p>
+ The Space Manager and related classes and structures are an important of
+ the Gecko Layout system, specifically Block Layout. &nbsp;See the High Level
+ Design document for an overview of the Space Manager, and as an introduction
+ to the classes, structures and algorithms container in this, the Detailed
+ Design Document.
+</p>
+
+
+
+<hr width="100%" size="2">
+<h2>nsSpaceManager</h2>
+<p>
+ The Space Manager is the central class is a group of classes that manage
+ the occupied and available space that exists in horizontal bands across
+a canvas. &nbsp;The primary goal of the Space Manager is to provide information
+ about those bands of space to support the CSS notion of floated elements.
+</p>
+
+<p>
+ There are three important parts to the Space Manager API: the parts that
+deal with the coordinate space of the Space Manager, the parts that deal with
+the regions managed by the Space Manager, and the parts that manage float
+impact intervals.
+</p>
+
+<p>
+ The class nsSpaceManager is declared in the file <a href="http://lxr.mozilla.org/seamonkey/source/layout/base/src/nsSpaceManager.h">
+ nsSpaceManger.h</a>
+ . &nbsp;The class is only used in the layout module and cannot be exported
+ outside of that module (nor does it need to be). &nbsp;It is not a general
+ purpose class, and is not intended to be subclasses<font color="#cc0000">
+ .</font>
+</p>
+
+<p>
+ Here is the class declaration, taken from the source file as of 01.08.02
+</p>
+
+
+
+<pre>/**
+ * Class for dealing with bands of available space. The space manager
+ * defines a coordinate space with an origin at (0, 0) that grows down
+ * and to the right.
+ */
+class nsSpaceManager {
+public:
+ nsSpaceManager(nsIPresShell* aPresShell, nsIFrame* aFrame);
+ ~nsSpaceManager();
+
+ void* operator new(size_t aSize);
+ void operator delete(void* aPtr, size_t aSize);
+
+ static void Shutdown();
+
+ /*
+ * Get the frame that's associated with the space manager. This frame
+ * created the space manager, and the world coordinate space is
+ * relative to this frame.
+ *
+ * You can use QueryInterface() on this frame to get any additional
+ * interfaces.
+ */
+ nsIFrame* GetFrame() const { return mFrame; }
+
+ /**
+ * Translate the current origin by the specified (dx, dy). This
+ * creates a new local coordinate space relative to the current
+ * coordinate space.
+ */
+ void Translate(nscoord aDx, nscoord aDy) { mX += aDx; mY += aDy; }
+
+ /**
+ * Returns the current translation from local coordinate space to
+ * world coordinate space. This represents the accumulated calls to
+ * Translate().
+ */
+ void GetTranslation(nscoord&amp; aX, nscoord&amp; aY) const { aX = mX; aY = mY; }
+
+ /**
+ * Returns the y-most of the bottommost band or 0 if there are no bands.
+ *
+ * @return PR_TRUE if there are bands and PR_FALSE if there are no bands
+ */
+ PRBool YMost(nscoord&amp; aYMost) const;
+
+ /**
+ * Returns a band starting at the specified y-offset. The band data
+ * indicates which parts of the band are available, and which parts
+ * are unavailable
+ *
+ * The band data that is returned is in the coordinate space of the
+ * local coordinate system.
+ *
+ * The local coordinate space origin, the y-offset, and the max size
+ * describe a rectangle that's used to clip the underlying band of
+ * available space, i.e.
+ * {0, aYOffset, aMaxSize.width, aMaxSize.height} in the local
+ * coordinate space
+ *
+ * @param aYOffset the y-offset of where the band begins. The coordinate is
+ * relative to the upper-left corner of the local coordinate space
+ * @param aMaxSize the size to use to constrain the band data
+ * @param aBandData [in,out] used to return the list of trapezoids that
+ * describe the available space and the unavailable space
+ * @return NS_OK if successful and NS_ERROR_FAILURE if the band data is not
+ * not large enough. The 'count' member of the band data struct
+ * indicates how large the array of trapezoids needs to be
+ */
+ nsresult GetBandData(nscoord aYOffset,
+ const nsSize&amp; aMaxSize,
+ nsBandData&amp; aBandData) const;
+
+ /**
+ * Add a rectangular region of unavailable space. The space is
+ * relative to the local coordinate system.
+ *
+ * The region is tagged with a frame
+ *
+ * @param aFrame the frame used to identify the region. Must not be NULL
+ * @param aUnavailableSpace the bounding rect of the unavailable space
+ * @return NS_OK if successful
+ * NS_ERROR_FAILURE if there is already a region tagged with aFrame
+ */
+ nsresult AddRectRegion(nsIFrame* aFrame,
+ const nsRect&amp; aUnavailableSpace);
+
+ /**
+ * Resize the rectangular region associated with aFrame by the specified
+ * deltas. The height change always applies to the bottom edge or the existing
+ * rect. You specify whether the width change applies to the left or right edge
+ *
+ * Returns NS_OK if successful, NS_ERROR_INVALID_ARG if there is no region
+ * tagged with aFrame
+ */
+ enum AffectedEdge {LeftEdge, RightEdge};
+ nsresult ResizeRectRegion(nsIFrame* aFrame,
+ nscoord aDeltaWidth,
+ nscoord aDeltaHeight,
+ AffectedEdge aEdge = RightEdge);
+
+ /**
+ * Offset the region associated with aFrame by the specified amount.
+ *
+ * Returns NS_OK if successful, NS_ERROR_INVALID_ARG if there is no region
+ * tagged with aFrame
+ */
+ nsresult OffsetRegion(nsIFrame* aFrame, nscoord dx, nscoord dy);
+
+ /**
+ * Remove the region associated with aFrane.
+ *
+ * Returns NS_OK if successful and NS_ERROR_INVALID_ARG if there is no region
+ * tagged with aFrame
+ */
+ nsresult RemoveRegion(nsIFrame* aFrame);
+
+ /**
+ * Clears the list of regions representing the unavailable space.
+ */
+ void ClearRegions();
+
+ /**
+ * Methods for dealing with the propagation of float damage during
+ * reflow.
+ */
+ PRBool HasFloatDamage()
+ {
+ return !mFloatDamage.IsEmpty();
+ }
+
+ void IncludeInDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
+ {
+ mFloatDamage.IncludeInterval(aIntervalBegin + mY, aIntervalEnd + mY);
+ }
+
+ PRBool IntersectsDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
+ {
+ return mFloatDamage.Intersects(aIntervalBegin + mY, aIntervalEnd + mY);
+ }
+
+#ifdef DEBUG
+ /**
+ * Dump the state of the spacemanager out to a file
+ */
+ nsresult List(FILE* out);
+
+ void SizeOf(nsISizeOfHandler* aHandler, uint32_t* aResult) const;
+#endif
+
+private:
+ // Structure that maintains information about the region associated
+ // with a particular frame
+ struct FrameInfo {
+ nsIFrame* const mFrame;
+ nsRect mRect; // rectangular region
+ FrameInfo* mNext;
+
+ FrameInfo(nsIFrame* aFrame, const nsRect&amp; aRect);
+#ifdef NS_BUILD_REFCNT_LOGGING
+ ~FrameInfo();
+#endif
+ };
+
+ // Doubly linked list of band rects
+ struct BandRect : PRCListStr {
+ nscoord mLeft, mTop;
+ nscoord mRight, mBottom;
+ int32_t mNumFrames; // number of frames occupying this rect
+ union {
+ nsIFrame* mFrame; // single frame occupying the space
+ nsVoidArray* mFrames; // list of frames occupying the space
+ };
+
+ BandRect(nscoord aLeft, nscoord aTop,
+ nscoord aRight, nscoord aBottom,
+ nsIFrame*);
+ BandRect(nscoord aLeft, nscoord aTop,
+ nscoord aRight, nscoord aBottom,
+ nsVoidArray*);
+ ~BandRect();
+
+ // List operations
+ BandRect* Next() const {return (BandRect*)PR_NEXT_LINK(this);}
+ BandRect* Prev() const {return (BandRect*)PR_PREV_LINK(this);}
+ void InsertBefore(BandRect* aBandRect) {PR_INSERT_BEFORE(aBandRect, this);}
+ void InsertAfter(BandRect* aBandRect) {PR_INSERT_AFTER(aBandRect, this);}
+ void Remove() {PR_REMOVE_LINK(this);}
+
+ // Split the band rect into two vertically, with this band rect becoming
+ // the top part, and a new band rect being allocated and returned for the
+ // bottom part
+ //
+ // Does not insert the new band rect into the linked list
+ BandRect* SplitVertically(nscoord aBottom);
+
+ // Split the band rect into two horizontally, with this band rect becoming
+ // the left part, and a new band rect being allocated and returned for the
+ // right part
+ //
+ // Does not insert the new band rect into the linked list
+ BandRect* SplitHorizontally(nscoord aRight);
+
+ // Accessor functions
+ PRBool IsOccupiedBy(const nsIFrame*) const;
+ void AddFrame(const nsIFrame*);
+ void RemoveFrame(const nsIFrame*);
+ PRBool HasSameFrameList(const BandRect* aBandRect) const;
+ int32_t Length() const;
+ };
+
+ // Circular linked list of band rects
+ struct BandList : BandRect {
+ BandList();
+
+ // Accessors
+ PRBool IsEmpty() const {return PR_CLIST_IS_EMPTY((PRCListStr*)this);}
+ BandRect* Head() const {return (BandRect*)PR_LIST_HEAD(this);}
+ BandRect* Tail() const {return (BandRect*)PR_LIST_TAIL(this);}
+
+ // Operations
+ void Append(BandRect* aBandRect) {PR_APPEND_LINK(aBandRect, this);}
+
+ // Remove and delete all the band rects in the list
+ void Clear();
+ };
+
+
+ FrameInfo* GetFrameInfoFor(nsIFrame* aFrame);
+ FrameInfo* CreateFrameInfo(nsIFrame* aFrame, const nsRect&amp; aRect);
+ void DestroyFrameInfo(FrameInfo*);
+
+ void ClearFrameInfo();
+ void ClearBandRects();
+
+ BandRect* GetNextBand(const BandRect* aBandRect) const;
+ void DivideBand(BandRect* aBand, nscoord aBottom);
+ PRBool CanJoinBands(BandRect* aBand, BandRect* aPrevBand);
+ PRBool JoinBands(BandRect* aBand, BandRect* aPrevBand);
+ void AddRectToBand(BandRect* aBand, BandRect* aBandRect);
+ void InsertBandRect(BandRect* aBandRect);
+
+ nsresult GetBandAvailableSpace(const BandRect* aBand,
+ nscoord aY,
+ const nsSize&amp; aMaxSize,
+ nsBandData&amp; aAvailableSpace) const;
+
+ nsIFrame* const mFrame; // frame associated with the space manager
+ nscoord mX, mY; // translation from local to global coordinate space
+ BandList mBandList; // header/sentinel for circular linked list of band rects
+ FrameInfo* mFrameInfoMap;
+ nsIntervalSet mFloatDamage;
+
+ static int32_t sCachedSpaceManagerCount;
+ static void* sCachedSpaceManagers[NS_SPACE_MANAGER_CACHE_SIZE];
+
+ nsSpaceManager(const nsSpaceManager&amp;); // no implementation
+ void operator=(const nsSpaceManager&amp;); // no implementation
+};
+
+</pre>
+
+<h3>Public API</h3>
+
+<h4>Life Cycle:</h4>
+<p>
+ The Constructor requires a Presentation Shell, used for arena allocations
+ mostly, and a frame that this Space Manager is rooted on. &nbsp;The coordinate
+ space of this Space Manager is relative to the frame passed in to the constructor.
+</p>
+
+<pre> nsSpaceManager(nsIPresShell* aPresShell, nsIFrame* aFrame);
+ ~nsSpaceManager();
+</pre>
+<p>
+ Operators 'new' and 'delete' are overridden to support a recycler. &nbsp;Space
+ Manager instances come and go pretty frequently, and this recycler prevents
+ excessive heap allocations and the performance penalties associated with
+it. The #define NS_SPACE_MANAGER_CACHE_SIZE is used to control the number
+of Space Manager instances that can be present in the recycler, currently
+4. &nbsp;If more than NS_SPACE_MANAGER_CACHE_SIZE are allocated at a time,
+then standard allocation is used.
+</p>
+
+<pre>
+ void* operator new(size_t aSize);
+ void operator delete(void* aPtr, size_t aSize);
+
+</pre>
+<p>
+ A Static method is used to shutdown the Space Manager recycling. &nbsp;This
+method deletes all of the Space Mangers inthe recycler,and prevents further
+recycling. &nbsp;It is meant to be called only when the layout module is being
+terminated.
+</p>
+
+<pre> static void Shutdown();
+
+</pre>
+
+<h4>Origin / Coordinate Space Translation</h4>
+
+<pre> /**
+ * Translate the current origin by the specified (dx, dy). This
+ * creates a new local coordinate space relative to the current
+ * coordinate space.
+ */
+ void Translate(nscoord aDx, nscoord aDy) { mX += aDx; mY += aDy; }
+
+ /**
+ * Returns the current translation from local coordinate space to
+ * world coordinate space. This represents the accumulated calls to
+ * Translate().
+ */
+ void GetTranslation(nscoord&amp; aX, nscoord&amp; aY) const { aX = mX; aY = mY; }
+
+ /**
+ * Returns the y-most of the bottommost band or 0 if there are no bands.
+ *
+ * @return PR_TRUE if there are bands and PR_FALSE if there are no bands
+ */
+ PRBool YMost(nscoord&amp; aYMost) const;
+</pre>
+
+<h4>Region Management</h4>
+
+<pre> /**
+ * Returns a band starting at the specified y-offset. The band data
+ * indicates which parts of the band are available, and which parts
+ * are unavailable
+ *
+ * The band data that is returned is in the coordinate space of the
+ * local coordinate system.
+ *
+ * The local coordinate space origin, the y-offset, and the max size
+ * describe a rectangle that's used to clip the underlying band of
+ * available space, i.e.
+ * {0, aYOffset, aMaxSize.width, aMaxSize.height} in the local
+ * coordinate space
+ *
+ * @param aYOffset the y-offset of where the band begins. The coordinate is
+ * relative to the upper-left corner of the local coordinate space
+ * @param aMaxSize the size to use to constrain the band data
+ * @param aBandData [in,out] used to return the list of trapezoids that
+ * describe the available space and the unavailable space
+ * @return NS_OK if successful and NS_ERROR_FAILURE if the band data is not
+ * not large enough. The 'count' member of the band data struct
+ * indicates how large the array of trapezoids needs to be
+ */
+ nsresult GetBandData(nscoord aYOffset,
+ const nsSize&amp; aMaxSize,
+ nsBandData&amp; aBandData) const;
+
+ /**
+ * Add a rectangular region of unavailable space. The space is
+ * relative to the local coordinate system.
+ *
+ * The region is tagged with a frame
+ *
+ * @param aFrame the frame used to identify the region. Must not be NULL
+ * @param aUnavailableSpace the bounding rect of the unavailable space
+ * @return NS_OK if successful
+ * NS_ERROR_FAILURE if there is already a region tagged with aFrame
+ */
+ nsresult AddRectRegion(nsIFrame* aFrame,
+ const nsRect&amp; aUnavailableSpace);
+
+ /**
+ * Resize the rectangular region associated with aFrame by the specified
+ * deltas. The height change always applies to the bottom edge or the existing
+ * rect. You specify whether the width change applies to the left or right edge
+ *
+ * Returns NS_OK if successful, NS_ERROR_INVALID_ARG if there is no region
+ * tagged with aFrame
+ */
+ enum AffectedEdge {LeftEdge, RightEdge};
+ nsresult ResizeRectRegion(nsIFrame* aFrame,
+ nscoord aDeltaWidth,
+ nscoord aDeltaHeight,
+ AffectedEdge aEdge = RightEdge);
+
+ /**
+ * Offset the region associated with aFrame by the specified amount.
+ *
+ * Returns NS_OK if successful, NS_ERROR_INVALID_ARG if there is no region
+ * tagged with aFrame
+ */
+ nsresult OffsetRegion(nsIFrame* aFrame, nscoord dx, nscoord dy);
+
+ /**
+ * Remove the region associated with aFrane.
+ *
+ * Returns NS_OK if successful and NS_ERROR_INVALID_ARG if there is no region
+ * tagged with aFrame
+ */
+ nsresult RemoveRegion(nsIFrame* aFrame);
+
+ /**
+ * Clears the list of regions representing the unavailable space.
+ */
+ void ClearRegions();
+</pre>
+
+<h4>Float Impact</h4>
+
+<pre> /**
+ * Methods for dealing with the propagation of float damage during
+ * reflow.
+ */
+ PRBool HasFloatDamage()
+ {
+ return !mFloatDamage.IsEmpty();
+ }
+
+ void IncludeInDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
+ {
+ mFloatDamage.IncludeInterval(aIntervalBegin + mY, aIntervalEnd + mY);
+ }
+
+ PRBool IntersectsDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
+ {
+ return mFloatDamage.Intersects(aIntervalBegin + mY, aIntervalEnd + mY);
+ }
+</pre>
+
+<h4>Debug Only Methods</h4>
+
+<pre> /**
+ * Dump the state of the spacemanager out to a file
+ */
+ nsresult List(FILE* out);
+
+ void SizeOf(nsISizeOfHandler* aHandler, uint32_t* aResult) const;
+
+</pre>
+
+<h4>Unused / Obsolete Methods</h4>
+
+<pre> /*
+ * Get the frame that's associated with the space manager. This frame
+ * created the space manager, and the world coordinate space is
+ * relative to this frame.
+ *
+ * You can use QueryInterface() on this frame to get any additional
+ * interfaces.
+ */
+ nsIFrame* GetFrame() const { return mFrame; }
+
+</pre>
+
+<h3>Implementation Notes</h3>
+
+<h4></h4>
+
+<h4>Algorithm 1: GetBandData</h4>
+<p>
+GetBandData is used to provide information to clients about what space if
+available and unavailable in a band of space. &nbsp;The client provides a
+vertical offset, the yOffset, that corresponds to the band that is of interest.
+&nbsp;This will be the y offset of the frame that is being reflowed. &nbsp;The
+caller also provides a collection of BandData objects (an array) and the
+number of items that the collection can handle. &nbsp;If the collection is
+too small, then an error is returned and the count is updated to indicate
+the size required.
+</p>
+
+<p>
+The algorithm to provide the band data is as follows:
+</p>
+<ul>
+ <li>Get a &nbsp;vertical offset in world coordinates (instead of frame-relative
+coordinates) by adding the y-origin of the SpaceManager to the y offset passed
+in</li>
+ <li>If the (adjusted) y value passed in is greater than the greatest band
+being managed, then all space is available so a single trapezoid is returned,
+marked as available and sized to the maximum size value (passed in).</li>
+ <li>If the (adjusted) y offset intersects a band, then gather the band
+data:</li>
+ <ul>
+ <li>walk the internal bandData list from head to tail</li>
+ <li>for each band data entry, see if the top of the band is greater than
+the (adjusted) y offset requested</li>
+ <li>if it is, then band is below the offset requested, so the area between
+the band and the y offset is available - create a trapezoid with that region
+and return it.</li>
+ <li>if the (adjusted) y offset is between the band top and bottom, then
+get the available space for the band by calling GetBandAvailableSpace</li>
+ <li>otherwise, move to the next band</li>
+ </ul>
+</ul>
+<h5>GetBandAvailableSpace:</h5>
+This method is called from GetBandData only. It walks all of the bands in
+the space manager and determines which bands intersect with the band passed
+in, and if within those bands there are regions that are available or occupied.
+
+<ul>
+ <li>First, walk all of the bands until a band that is to the right of the
+desired offset is located</li>
+ <li>Starting at that band, &nbsp;walk the remaining bands:</li>
+ <ul>
+ <li>if the current band is to the right of the requested band, then there
+is available space.&nbsp;</li>
+ <ul>
+ <li>if there is more room in the bandData collection, then add a trapezoid
+to the bandData collection such that it is marked as available and has a
+rect that represents the space between the reference band tna dht band being
+examined</li>
+ <li>if there is no more room in the BandData collection, estimate the
+number of entries requires as the current count + twice the number of bands
+below the reference band, plus two. &nbsp;Return an error code so the caller
+can reallocate the collection and try again.</li>
+ </ul>
+ <li>check the size of the collection again, if there is no room left
+then estimate the number of items requires as the current count + twice the
+number of bands below the band in question plus one.&nbsp;</li>
+ <li>create a new trapezoid in the band collection that has a region corresponding
+to the reference band rect, marked as occupied by either a single or multiple
+frames.</li>
+ <li>move to the next band</li>
+ </ul>
+ <li>after walking all of the band data, se if we have reached the right
+edge of the band.&nbsp;</li>
+ <ul>
+ <li>If not, then check for space in the band collection</li>
+ <ul>
+ <li>if there is no room left, then set the count to the current count
+plus 1 and return an error.</li>
+ <li>otherwise, create another entry in the band collection, marked
+as available, and with a rect corresponding to the area remainin in the band
+(eg. from the right edge of the last band rect to the right edge of the band).</li>
+ </ul>
+ </ul>
+</ul>
+
+<h4>Algorithm 2: AddRectRegion</h4>
+Clients call into this method to notify the Space Manager that a new frame
+is occupying some space.
+
+<ul>
+ <li>First, try to get frame info for the frame. If it is found, return
+an error since the frame is already associated with a region in the Space
+Manager.</li>
+ <li>Next, create a rect from the occupied space passed in by the caller,
+transforming it first to world-coordinates by adding the Space Manager's
+offset to the occupied space rect passed in.</li>
+ <li>Create a new Frame Info instance for the frame and rect, returning
+an error if allocation fails.</li>
+ <li>Check if the occupied space rect (adjusted) is empty, if so, return
+an error &nbsp;(<font color="#cc0000">NOTE: this could be done earlier, or
+prevented by the caller</font>)</li>
+ <li>Allocate a new BandRect instance with the rect and frame as constructor
+arguments, and insert it into the collection via InsertBandRect</li>
+</ul>
+<h5>InsertBandRect:</h5>
+Internal method to insert a band rect into the BandList in the correct location.
+There are several cases it has to handle, as specified in the source file
+comments:
+
+<pre>// When comparing a rect to a band there are seven cases to consider.
+// 'R' is the rect and 'B' is the band.
+//
+// Case 1 Case 2 Case 3 Case 4
+// ------ ------ ------ ------
+// +-----+ +-----+ +-----+ +-----+
+// | R | | R | +-----+ +-----+ | | | |
+// +-----+ +-----+ | | | R | | B | | B |
+// +-----+ | B | +-----+ | | +-----+ | |
+// | | | | +-----+ | R | +-----+
+// | B | +-----+ +-----+
+// | |
+// +-----+
+//
+//
+//
+// Case 5 Case 6 Case 7
+// ------ ------ ------
+// +-----+ +-----+ +-----+ +-----+
+// | | | R | | B | | | +-----+
+// | B | +-----+ +-----+ | R | | B |
+// | | | | +-----+
+// +-----+ +-----+
+// +-----+
+// | R |
+// +-----+
+//
+</pre>
+<ul>
+ <li>First, check for the easiest case, where there are no existing band
+rects, or the band rect passed in is below the bottommost rect. In this case,
+just append the band rect and return.</li>
+ <li>Starting at the head of the list of bandRects, check for intersection
+with the rect passed in:</li>
+ <ul>
+ <li>case #1: the rect is totally above the current band rect, so insert
+a new band rect before the current bandRect</li>
+ <li>cases #2 and #7: the rect is partially above the band rect, so it
+is divided into two bandRects, one entirely above the band, and one containing
+the remainder of the rect. &nbsp;Insert the part that is totally above the
+bandRect before the current bandRect, as in case #1 above, and adjust the
+other band rect to exclude the part already added.</li>
+ <li>case #5: the rect is totally below the current bandRect, so just
+skip to the next band</li>
+ <li>case #3 and #4: rect is at least partially intersection with the
+bandRect, so divide the current band into two parts, where the top part is
+above the current rect. &nbsp;Move to the new band just created, which is
+the next band.</li>
+ <li>case #6: the rect shares the bottom and height with the bandRect,
+so just add the rect to the band.</li>
+ <li>case #4 and #7: create a new rect for the part that overlaps the
+bandRect, and add it to the current bandRect (similar to case #6) and then
+move on to the next band, removing that part from the rect passed in. &nbsp;If
+no more bands, append the rect passed in to the end of the bandRect list.</li>
+ </ul>
+</ul>
+<i>This algorithm is pretty confusing - basically what needs to happen is
+that rects and bands need to be divided up so that complicated cases like
+#2, #4, and #7, are reduced to simpler cases where the rects is totally above,
+below, or between a band rect. &nbsp;From the current implementation, it
+might be worth verifying that the final result of the inserts is a correctly
+ordered liest of bandRects (debug mode only).</i>
+
+
+<h4>Algorithm 3: RemoveRegion</h4>
+ When a float is removed, the Space Manager is notified by a call to RemoveRegion,
+passing in the frame that is being removed.
+
+<ul>
+ <li>Get the FrameInfo for the frame passed in. If not found, an error is
+returned.</li>
+ <li>If the rect for the frame is not empty, then visit each band in the
+bandList:</li>
+ <ul>
+ <li>for each rect in the band:
+
+ </li>
+ </ul>
+ <ul>
+ <ul>
+ <li>if the bandRect is occupied by the frame, either remove the frame
+from the bandRect (if there are other frames sharing it) and remember that
+it was shared</li>
+ <li>otherwise simply remove the bandRect (no other frames share it).</li>
+ <li>if the bandRect was shared, then try to coalesce adjacent bandRects</li>
+ <ul>
+ <li>if the previous bandRect is directly next to the current bandRect,
+and they have the same frame list, then make the current bandRect cover the
+previous bandRect's full region (adjust the left edge to be that of the previous
+bandRect) and remove the previous bandRect.</li>
+ </ul>
+ </ul>
+ </ul>
+ <ul>
+ <li>if the current band or prior band had a rect occupied byu the frame,
+then try to join the two bands via JoinBands</li>
+ </ul>
+ <li>Finally, destroy the frameInfo for the frame.
+
+ </li>
+</ul>
+
+<br>
+
+<hr width="100%" size="2">
+<h2>Cross-Component Algorithms</h2>
+
+<br>
+
+
+
+<hr width="100%" size="2">
+<h2>Tech Notes</h2>
+<ul>
+ <li>
+
+ </li>
+
+</ul>
+
+
+
+
+
+</body>
+</html>