1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/layout/doc/DD-SpaceManager.html Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,743 @@
1.4 +<!-- This Source Code Form is subject to the terms of the Mozilla Public
1.5 + - License, v. 2.0. If a copy of the MPL was not distributed with this
1.6 + - file, You can obtain one at http://mozilla.org/MPL/2.0/. -->
1.7 +
1.8 +<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
1.9 +<html>
1.10 +<head>
1.11 +
1.12 + <meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
1.13 + <title>Detailed Design Template</title>
1.14 +</head>
1.15 + <body>
1.16 +
1.17 +<h1><font color="#cc0000">Gecko Layout Detailed Design Document</font></h1>
1.18 +
1.19 +<h1>Space Manager Detailed Design</h1>
1.20 +
1.21 +<h2>Overview</h2>
1.22 +<p>
1.23 + The Space Manager and related classes and structures are an important of
1.24 + the Gecko Layout system, specifically Block Layout. See the High Level
1.25 + Design document for an overview of the Space Manager, and as an introduction
1.26 + to the classes, structures and algorithms container in this, the Detailed
1.27 + Design Document.
1.28 +</p>
1.29 +
1.30 +
1.31 +
1.32 +<hr width="100%" size="2">
1.33 +<h2>nsSpaceManager</h2>
1.34 +<p>
1.35 + The Space Manager is the central class is a group of classes that manage
1.36 + the occupied and available space that exists in horizontal bands across
1.37 +a canvas. The primary goal of the Space Manager is to provide information
1.38 + about those bands of space to support the CSS notion of floated elements.
1.39 +</p>
1.40 +
1.41 +<p>
1.42 + There are three important parts to the Space Manager API: the parts that
1.43 +deal with the coordinate space of the Space Manager, the parts that deal with
1.44 +the regions managed by the Space Manager, and the parts that manage float
1.45 +impact intervals.
1.46 +</p>
1.47 +
1.48 +<p>
1.49 + The class nsSpaceManager is declared in the file <a href="http://lxr.mozilla.org/seamonkey/source/layout/base/src/nsSpaceManager.h">
1.50 + nsSpaceManger.h</a>
1.51 + . The class is only used in the layout module and cannot be exported
1.52 + outside of that module (nor does it need to be). It is not a general
1.53 + purpose class, and is not intended to be subclasses<font color="#cc0000">
1.54 + .</font>
1.55 +</p>
1.56 +
1.57 +<p>
1.58 + Here is the class declaration, taken from the source file as of 01.08.02
1.59 +</p>
1.60 +
1.61 +
1.62 +
1.63 +<pre>/**
1.64 + * Class for dealing with bands of available space. The space manager
1.65 + * defines a coordinate space with an origin at (0, 0) that grows down
1.66 + * and to the right.
1.67 + */
1.68 +class nsSpaceManager {
1.69 +public:
1.70 + nsSpaceManager(nsIPresShell* aPresShell, nsIFrame* aFrame);
1.71 + ~nsSpaceManager();
1.72 +
1.73 + void* operator new(size_t aSize);
1.74 + void operator delete(void* aPtr, size_t aSize);
1.75 +
1.76 + static void Shutdown();
1.77 +
1.78 + /*
1.79 + * Get the frame that's associated with the space manager. This frame
1.80 + * created the space manager, and the world coordinate space is
1.81 + * relative to this frame.
1.82 + *
1.83 + * You can use QueryInterface() on this frame to get any additional
1.84 + * interfaces.
1.85 + */
1.86 + nsIFrame* GetFrame() const { return mFrame; }
1.87 +
1.88 + /**
1.89 + * Translate the current origin by the specified (dx, dy). This
1.90 + * creates a new local coordinate space relative to the current
1.91 + * coordinate space.
1.92 + */
1.93 + void Translate(nscoord aDx, nscoord aDy) { mX += aDx; mY += aDy; }
1.94 +
1.95 + /**
1.96 + * Returns the current translation from local coordinate space to
1.97 + * world coordinate space. This represents the accumulated calls to
1.98 + * Translate().
1.99 + */
1.100 + void GetTranslation(nscoord& aX, nscoord& aY) const { aX = mX; aY = mY; }
1.101 +
1.102 + /**
1.103 + * Returns the y-most of the bottommost band or 0 if there are no bands.
1.104 + *
1.105 + * @return PR_TRUE if there are bands and PR_FALSE if there are no bands
1.106 + */
1.107 + PRBool YMost(nscoord& aYMost) const;
1.108 +
1.109 + /**
1.110 + * Returns a band starting at the specified y-offset. The band data
1.111 + * indicates which parts of the band are available, and which parts
1.112 + * are unavailable
1.113 + *
1.114 + * The band data that is returned is in the coordinate space of the
1.115 + * local coordinate system.
1.116 + *
1.117 + * The local coordinate space origin, the y-offset, and the max size
1.118 + * describe a rectangle that's used to clip the underlying band of
1.119 + * available space, i.e.
1.120 + * {0, aYOffset, aMaxSize.width, aMaxSize.height} in the local
1.121 + * coordinate space
1.122 + *
1.123 + * @param aYOffset the y-offset of where the band begins. The coordinate is
1.124 + * relative to the upper-left corner of the local coordinate space
1.125 + * @param aMaxSize the size to use to constrain the band data
1.126 + * @param aBandData [in,out] used to return the list of trapezoids that
1.127 + * describe the available space and the unavailable space
1.128 + * @return NS_OK if successful and NS_ERROR_FAILURE if the band data is not
1.129 + * not large enough. The 'count' member of the band data struct
1.130 + * indicates how large the array of trapezoids needs to be
1.131 + */
1.132 + nsresult GetBandData(nscoord aYOffset,
1.133 + const nsSize& aMaxSize,
1.134 + nsBandData& aBandData) const;
1.135 +
1.136 + /**
1.137 + * Add a rectangular region of unavailable space. The space is
1.138 + * relative to the local coordinate system.
1.139 + *
1.140 + * The region is tagged with a frame
1.141 + *
1.142 + * @param aFrame the frame used to identify the region. Must not be NULL
1.143 + * @param aUnavailableSpace the bounding rect of the unavailable space
1.144 + * @return NS_OK if successful
1.145 + * NS_ERROR_FAILURE if there is already a region tagged with aFrame
1.146 + */
1.147 + nsresult AddRectRegion(nsIFrame* aFrame,
1.148 + const nsRect& aUnavailableSpace);
1.149 +
1.150 + /**
1.151 + * Resize the rectangular region associated with aFrame by the specified
1.152 + * deltas. The height change always applies to the bottom edge or the existing
1.153 + * rect. You specify whether the width change applies to the left or right edge
1.154 + *
1.155 + * Returns NS_OK if successful, NS_ERROR_INVALID_ARG if there is no region
1.156 + * tagged with aFrame
1.157 + */
1.158 + enum AffectedEdge {LeftEdge, RightEdge};
1.159 + nsresult ResizeRectRegion(nsIFrame* aFrame,
1.160 + nscoord aDeltaWidth,
1.161 + nscoord aDeltaHeight,
1.162 + AffectedEdge aEdge = RightEdge);
1.163 +
1.164 + /**
1.165 + * Offset the region associated with aFrame by the specified amount.
1.166 + *
1.167 + * Returns NS_OK if successful, NS_ERROR_INVALID_ARG if there is no region
1.168 + * tagged with aFrame
1.169 + */
1.170 + nsresult OffsetRegion(nsIFrame* aFrame, nscoord dx, nscoord dy);
1.171 +
1.172 + /**
1.173 + * Remove the region associated with aFrane.
1.174 + *
1.175 + * Returns NS_OK if successful and NS_ERROR_INVALID_ARG if there is no region
1.176 + * tagged with aFrame
1.177 + */
1.178 + nsresult RemoveRegion(nsIFrame* aFrame);
1.179 +
1.180 + /**
1.181 + * Clears the list of regions representing the unavailable space.
1.182 + */
1.183 + void ClearRegions();
1.184 +
1.185 + /**
1.186 + * Methods for dealing with the propagation of float damage during
1.187 + * reflow.
1.188 + */
1.189 + PRBool HasFloatDamage()
1.190 + {
1.191 + return !mFloatDamage.IsEmpty();
1.192 + }
1.193 +
1.194 + void IncludeInDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
1.195 + {
1.196 + mFloatDamage.IncludeInterval(aIntervalBegin + mY, aIntervalEnd + mY);
1.197 + }
1.198 +
1.199 + PRBool IntersectsDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
1.200 + {
1.201 + return mFloatDamage.Intersects(aIntervalBegin + mY, aIntervalEnd + mY);
1.202 + }
1.203 +
1.204 +#ifdef DEBUG
1.205 + /**
1.206 + * Dump the state of the spacemanager out to a file
1.207 + */
1.208 + nsresult List(FILE* out);
1.209 +
1.210 + void SizeOf(nsISizeOfHandler* aHandler, uint32_t* aResult) const;
1.211 +#endif
1.212 +
1.213 +private:
1.214 + // Structure that maintains information about the region associated
1.215 + // with a particular frame
1.216 + struct FrameInfo {
1.217 + nsIFrame* const mFrame;
1.218 + nsRect mRect; // rectangular region
1.219 + FrameInfo* mNext;
1.220 +
1.221 + FrameInfo(nsIFrame* aFrame, const nsRect& aRect);
1.222 +#ifdef NS_BUILD_REFCNT_LOGGING
1.223 + ~FrameInfo();
1.224 +#endif
1.225 + };
1.226 +
1.227 + // Doubly linked list of band rects
1.228 + struct BandRect : PRCListStr {
1.229 + nscoord mLeft, mTop;
1.230 + nscoord mRight, mBottom;
1.231 + int32_t mNumFrames; // number of frames occupying this rect
1.232 + union {
1.233 + nsIFrame* mFrame; // single frame occupying the space
1.234 + nsVoidArray* mFrames; // list of frames occupying the space
1.235 + };
1.236 +
1.237 + BandRect(nscoord aLeft, nscoord aTop,
1.238 + nscoord aRight, nscoord aBottom,
1.239 + nsIFrame*);
1.240 + BandRect(nscoord aLeft, nscoord aTop,
1.241 + nscoord aRight, nscoord aBottom,
1.242 + nsVoidArray*);
1.243 + ~BandRect();
1.244 +
1.245 + // List operations
1.246 + BandRect* Next() const {return (BandRect*)PR_NEXT_LINK(this);}
1.247 + BandRect* Prev() const {return (BandRect*)PR_PREV_LINK(this);}
1.248 + void InsertBefore(BandRect* aBandRect) {PR_INSERT_BEFORE(aBandRect, this);}
1.249 + void InsertAfter(BandRect* aBandRect) {PR_INSERT_AFTER(aBandRect, this);}
1.250 + void Remove() {PR_REMOVE_LINK(this);}
1.251 +
1.252 + // Split the band rect into two vertically, with this band rect becoming
1.253 + // the top part, and a new band rect being allocated and returned for the
1.254 + // bottom part
1.255 + //
1.256 + // Does not insert the new band rect into the linked list
1.257 + BandRect* SplitVertically(nscoord aBottom);
1.258 +
1.259 + // Split the band rect into two horizontally, with this band rect becoming
1.260 + // the left part, and a new band rect being allocated and returned for the
1.261 + // right part
1.262 + //
1.263 + // Does not insert the new band rect into the linked list
1.264 + BandRect* SplitHorizontally(nscoord aRight);
1.265 +
1.266 + // Accessor functions
1.267 + PRBool IsOccupiedBy(const nsIFrame*) const;
1.268 + void AddFrame(const nsIFrame*);
1.269 + void RemoveFrame(const nsIFrame*);
1.270 + PRBool HasSameFrameList(const BandRect* aBandRect) const;
1.271 + int32_t Length() const;
1.272 + };
1.273 +
1.274 + // Circular linked list of band rects
1.275 + struct BandList : BandRect {
1.276 + BandList();
1.277 +
1.278 + // Accessors
1.279 + PRBool IsEmpty() const {return PR_CLIST_IS_EMPTY((PRCListStr*)this);}
1.280 + BandRect* Head() const {return (BandRect*)PR_LIST_HEAD(this);}
1.281 + BandRect* Tail() const {return (BandRect*)PR_LIST_TAIL(this);}
1.282 +
1.283 + // Operations
1.284 + void Append(BandRect* aBandRect) {PR_APPEND_LINK(aBandRect, this);}
1.285 +
1.286 + // Remove and delete all the band rects in the list
1.287 + void Clear();
1.288 + };
1.289 +
1.290 +
1.291 + FrameInfo* GetFrameInfoFor(nsIFrame* aFrame);
1.292 + FrameInfo* CreateFrameInfo(nsIFrame* aFrame, const nsRect& aRect);
1.293 + void DestroyFrameInfo(FrameInfo*);
1.294 +
1.295 + void ClearFrameInfo();
1.296 + void ClearBandRects();
1.297 +
1.298 + BandRect* GetNextBand(const BandRect* aBandRect) const;
1.299 + void DivideBand(BandRect* aBand, nscoord aBottom);
1.300 + PRBool CanJoinBands(BandRect* aBand, BandRect* aPrevBand);
1.301 + PRBool JoinBands(BandRect* aBand, BandRect* aPrevBand);
1.302 + void AddRectToBand(BandRect* aBand, BandRect* aBandRect);
1.303 + void InsertBandRect(BandRect* aBandRect);
1.304 +
1.305 + nsresult GetBandAvailableSpace(const BandRect* aBand,
1.306 + nscoord aY,
1.307 + const nsSize& aMaxSize,
1.308 + nsBandData& aAvailableSpace) const;
1.309 +
1.310 + nsIFrame* const mFrame; // frame associated with the space manager
1.311 + nscoord mX, mY; // translation from local to global coordinate space
1.312 + BandList mBandList; // header/sentinel for circular linked list of band rects
1.313 + FrameInfo* mFrameInfoMap;
1.314 + nsIntervalSet mFloatDamage;
1.315 +
1.316 + static int32_t sCachedSpaceManagerCount;
1.317 + static void* sCachedSpaceManagers[NS_SPACE_MANAGER_CACHE_SIZE];
1.318 +
1.319 + nsSpaceManager(const nsSpaceManager&); // no implementation
1.320 + void operator=(const nsSpaceManager&); // no implementation
1.321 +};
1.322 +
1.323 +</pre>
1.324 +
1.325 +<h3>Public API</h3>
1.326 +
1.327 +<h4>Life Cycle:</h4>
1.328 +<p>
1.329 + The Constructor requires a Presentation Shell, used for arena allocations
1.330 + mostly, and a frame that this Space Manager is rooted on. The coordinate
1.331 + space of this Space Manager is relative to the frame passed in to the constructor.
1.332 +</p>
1.333 +
1.334 +<pre> nsSpaceManager(nsIPresShell* aPresShell, nsIFrame* aFrame);
1.335 + ~nsSpaceManager();
1.336 +</pre>
1.337 +<p>
1.338 + Operators 'new' and 'delete' are overridden to support a recycler. Space
1.339 + Manager instances come and go pretty frequently, and this recycler prevents
1.340 + excessive heap allocations and the performance penalties associated with
1.341 +it. The #define NS_SPACE_MANAGER_CACHE_SIZE is used to control the number
1.342 +of Space Manager instances that can be present in the recycler, currently
1.343 +4. If more than NS_SPACE_MANAGER_CACHE_SIZE are allocated at a time,
1.344 +then standard allocation is used.
1.345 +</p>
1.346 +
1.347 +<pre>
1.348 + void* operator new(size_t aSize);
1.349 + void operator delete(void* aPtr, size_t aSize);
1.350 +
1.351 +</pre>
1.352 +<p>
1.353 + A Static method is used to shutdown the Space Manager recycling. This
1.354 +method deletes all of the Space Mangers inthe recycler,and prevents further
1.355 +recycling. It is meant to be called only when the layout module is being
1.356 +terminated.
1.357 +</p>
1.358 +
1.359 +<pre> static void Shutdown();
1.360 +
1.361 +</pre>
1.362 +
1.363 +<h4>Origin / Coordinate Space Translation</h4>
1.364 +
1.365 +<pre> /**
1.366 + * Translate the current origin by the specified (dx, dy). This
1.367 + * creates a new local coordinate space relative to the current
1.368 + * coordinate space.
1.369 + */
1.370 + void Translate(nscoord aDx, nscoord aDy) { mX += aDx; mY += aDy; }
1.371 +
1.372 + /**
1.373 + * Returns the current translation from local coordinate space to
1.374 + * world coordinate space. This represents the accumulated calls to
1.375 + * Translate().
1.376 + */
1.377 + void GetTranslation(nscoord& aX, nscoord& aY) const { aX = mX; aY = mY; }
1.378 +
1.379 + /**
1.380 + * Returns the y-most of the bottommost band or 0 if there are no bands.
1.381 + *
1.382 + * @return PR_TRUE if there are bands and PR_FALSE if there are no bands
1.383 + */
1.384 + PRBool YMost(nscoord& aYMost) const;
1.385 +</pre>
1.386 +
1.387 +<h4>Region Management</h4>
1.388 +
1.389 +<pre> /**
1.390 + * Returns a band starting at the specified y-offset. The band data
1.391 + * indicates which parts of the band are available, and which parts
1.392 + * are unavailable
1.393 + *
1.394 + * The band data that is returned is in the coordinate space of the
1.395 + * local coordinate system.
1.396 + *
1.397 + * The local coordinate space origin, the y-offset, and the max size
1.398 + * describe a rectangle that's used to clip the underlying band of
1.399 + * available space, i.e.
1.400 + * {0, aYOffset, aMaxSize.width, aMaxSize.height} in the local
1.401 + * coordinate space
1.402 + *
1.403 + * @param aYOffset the y-offset of where the band begins. The coordinate is
1.404 + * relative to the upper-left corner of the local coordinate space
1.405 + * @param aMaxSize the size to use to constrain the band data
1.406 + * @param aBandData [in,out] used to return the list of trapezoids that
1.407 + * describe the available space and the unavailable space
1.408 + * @return NS_OK if successful and NS_ERROR_FAILURE if the band data is not
1.409 + * not large enough. The 'count' member of the band data struct
1.410 + * indicates how large the array of trapezoids needs to be
1.411 + */
1.412 + nsresult GetBandData(nscoord aYOffset,
1.413 + const nsSize& aMaxSize,
1.414 + nsBandData& aBandData) const;
1.415 +
1.416 + /**
1.417 + * Add a rectangular region of unavailable space. The space is
1.418 + * relative to the local coordinate system.
1.419 + *
1.420 + * The region is tagged with a frame
1.421 + *
1.422 + * @param aFrame the frame used to identify the region. Must not be NULL
1.423 + * @param aUnavailableSpace the bounding rect of the unavailable space
1.424 + * @return NS_OK if successful
1.425 + * NS_ERROR_FAILURE if there is already a region tagged with aFrame
1.426 + */
1.427 + nsresult AddRectRegion(nsIFrame* aFrame,
1.428 + const nsRect& aUnavailableSpace);
1.429 +
1.430 + /**
1.431 + * Resize the rectangular region associated with aFrame by the specified
1.432 + * deltas. The height change always applies to the bottom edge or the existing
1.433 + * rect. You specify whether the width change applies to the left or right edge
1.434 + *
1.435 + * Returns NS_OK if successful, NS_ERROR_INVALID_ARG if there is no region
1.436 + * tagged with aFrame
1.437 + */
1.438 + enum AffectedEdge {LeftEdge, RightEdge};
1.439 + nsresult ResizeRectRegion(nsIFrame* aFrame,
1.440 + nscoord aDeltaWidth,
1.441 + nscoord aDeltaHeight,
1.442 + AffectedEdge aEdge = RightEdge);
1.443 +
1.444 + /**
1.445 + * Offset the region associated with aFrame by the specified amount.
1.446 + *
1.447 + * Returns NS_OK if successful, NS_ERROR_INVALID_ARG if there is no region
1.448 + * tagged with aFrame
1.449 + */
1.450 + nsresult OffsetRegion(nsIFrame* aFrame, nscoord dx, nscoord dy);
1.451 +
1.452 + /**
1.453 + * Remove the region associated with aFrane.
1.454 + *
1.455 + * Returns NS_OK if successful and NS_ERROR_INVALID_ARG if there is no region
1.456 + * tagged with aFrame
1.457 + */
1.458 + nsresult RemoveRegion(nsIFrame* aFrame);
1.459 +
1.460 + /**
1.461 + * Clears the list of regions representing the unavailable space.
1.462 + */
1.463 + void ClearRegions();
1.464 +</pre>
1.465 +
1.466 +<h4>Float Impact</h4>
1.467 +
1.468 +<pre> /**
1.469 + * Methods for dealing with the propagation of float damage during
1.470 + * reflow.
1.471 + */
1.472 + PRBool HasFloatDamage()
1.473 + {
1.474 + return !mFloatDamage.IsEmpty();
1.475 + }
1.476 +
1.477 + void IncludeInDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
1.478 + {
1.479 + mFloatDamage.IncludeInterval(aIntervalBegin + mY, aIntervalEnd + mY);
1.480 + }
1.481 +
1.482 + PRBool IntersectsDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
1.483 + {
1.484 + return mFloatDamage.Intersects(aIntervalBegin + mY, aIntervalEnd + mY);
1.485 + }
1.486 +</pre>
1.487 +
1.488 +<h4>Debug Only Methods</h4>
1.489 +
1.490 +<pre> /**
1.491 + * Dump the state of the spacemanager out to a file
1.492 + */
1.493 + nsresult List(FILE* out);
1.494 +
1.495 + void SizeOf(nsISizeOfHandler* aHandler, uint32_t* aResult) const;
1.496 +
1.497 +</pre>
1.498 +
1.499 +<h4>Unused / Obsolete Methods</h4>
1.500 +
1.501 +<pre> /*
1.502 + * Get the frame that's associated with the space manager. This frame
1.503 + * created the space manager, and the world coordinate space is
1.504 + * relative to this frame.
1.505 + *
1.506 + * You can use QueryInterface() on this frame to get any additional
1.507 + * interfaces.
1.508 + */
1.509 + nsIFrame* GetFrame() const { return mFrame; }
1.510 +
1.511 +</pre>
1.512 +
1.513 +<h3>Implementation Notes</h3>
1.514 +
1.515 +<h4></h4>
1.516 +
1.517 +<h4>Algorithm 1: GetBandData</h4>
1.518 +<p>
1.519 +GetBandData is used to provide information to clients about what space if
1.520 +available and unavailable in a band of space. The client provides a
1.521 +vertical offset, the yOffset, that corresponds to the band that is of interest.
1.522 + This will be the y offset of the frame that is being reflowed. The
1.523 +caller also provides a collection of BandData objects (an array) and the
1.524 +number of items that the collection can handle. If the collection is
1.525 +too small, then an error is returned and the count is updated to indicate
1.526 +the size required.
1.527 +</p>
1.528 +
1.529 +<p>
1.530 +The algorithm to provide the band data is as follows:
1.531 +</p>
1.532 +<ul>
1.533 + <li>Get a vertical offset in world coordinates (instead of frame-relative
1.534 +coordinates) by adding the y-origin of the SpaceManager to the y offset passed
1.535 +in</li>
1.536 + <li>If the (adjusted) y value passed in is greater than the greatest band
1.537 +being managed, then all space is available so a single trapezoid is returned,
1.538 +marked as available and sized to the maximum size value (passed in).</li>
1.539 + <li>If the (adjusted) y offset intersects a band, then gather the band
1.540 +data:</li>
1.541 + <ul>
1.542 + <li>walk the internal bandData list from head to tail</li>
1.543 + <li>for each band data entry, see if the top of the band is greater than
1.544 +the (adjusted) y offset requested</li>
1.545 + <li>if it is, then band is below the offset requested, so the area between
1.546 +the band and the y offset is available - create a trapezoid with that region
1.547 +and return it.</li>
1.548 + <li>if the (adjusted) y offset is between the band top and bottom, then
1.549 +get the available space for the band by calling GetBandAvailableSpace</li>
1.550 + <li>otherwise, move to the next band</li>
1.551 + </ul>
1.552 +</ul>
1.553 +<h5>GetBandAvailableSpace:</h5>
1.554 +This method is called from GetBandData only. It walks all of the bands in
1.555 +the space manager and determines which bands intersect with the band passed
1.556 +in, and if within those bands there are regions that are available or occupied.
1.557 +
1.558 +<ul>
1.559 + <li>First, walk all of the bands until a band that is to the right of the
1.560 +desired offset is located</li>
1.561 + <li>Starting at that band, walk the remaining bands:</li>
1.562 + <ul>
1.563 + <li>if the current band is to the right of the requested band, then there
1.564 +is available space. </li>
1.565 + <ul>
1.566 + <li>if there is more room in the bandData collection, then add a trapezoid
1.567 +to the bandData collection such that it is marked as available and has a
1.568 +rect that represents the space between the reference band tna dht band being
1.569 +examined</li>
1.570 + <li>if there is no more room in the BandData collection, estimate the
1.571 +number of entries requires as the current count + twice the number of bands
1.572 +below the reference band, plus two. Return an error code so the caller
1.573 +can reallocate the collection and try again.</li>
1.574 + </ul>
1.575 + <li>check the size of the collection again, if there is no room left
1.576 +then estimate the number of items requires as the current count + twice the
1.577 +number of bands below the band in question plus one. </li>
1.578 + <li>create a new trapezoid in the band collection that has a region corresponding
1.579 +to the reference band rect, marked as occupied by either a single or multiple
1.580 +frames.</li>
1.581 + <li>move to the next band</li>
1.582 + </ul>
1.583 + <li>after walking all of the band data, se if we have reached the right
1.584 +edge of the band. </li>
1.585 + <ul>
1.586 + <li>If not, then check for space in the band collection</li>
1.587 + <ul>
1.588 + <li>if there is no room left, then set the count to the current count
1.589 +plus 1 and return an error.</li>
1.590 + <li>otherwise, create another entry in the band collection, marked
1.591 +as available, and with a rect corresponding to the area remainin in the band
1.592 +(eg. from the right edge of the last band rect to the right edge of the band).</li>
1.593 + </ul>
1.594 + </ul>
1.595 +</ul>
1.596 +
1.597 +<h4>Algorithm 2: AddRectRegion</h4>
1.598 +Clients call into this method to notify the Space Manager that a new frame
1.599 +is occupying some space.
1.600 +
1.601 +<ul>
1.602 + <li>First, try to get frame info for the frame. If it is found, return
1.603 +an error since the frame is already associated with a region in the Space
1.604 +Manager.</li>
1.605 + <li>Next, create a rect from the occupied space passed in by the caller,
1.606 +transforming it first to world-coordinates by adding the Space Manager's
1.607 +offset to the occupied space rect passed in.</li>
1.608 + <li>Create a new Frame Info instance for the frame and rect, returning
1.609 +an error if allocation fails.</li>
1.610 + <li>Check if the occupied space rect (adjusted) is empty, if so, return
1.611 +an error (<font color="#cc0000">NOTE: this could be done earlier, or
1.612 +prevented by the caller</font>)</li>
1.613 + <li>Allocate a new BandRect instance with the rect and frame as constructor
1.614 +arguments, and insert it into the collection via InsertBandRect</li>
1.615 +</ul>
1.616 +<h5>InsertBandRect:</h5>
1.617 +Internal method to insert a band rect into the BandList in the correct location.
1.618 +There are several cases it has to handle, as specified in the source file
1.619 +comments:
1.620 +
1.621 +<pre>// When comparing a rect to a band there are seven cases to consider.
1.622 +// 'R' is the rect and 'B' is the band.
1.623 +//
1.624 +// Case 1 Case 2 Case 3 Case 4
1.625 +// ------ ------ ------ ------
1.626 +// +-----+ +-----+ +-----+ +-----+
1.627 +// | R | | R | +-----+ +-----+ | | | |
1.628 +// +-----+ +-----+ | | | R | | B | | B |
1.629 +// +-----+ | B | +-----+ | | +-----+ | |
1.630 +// | | | | +-----+ | R | +-----+
1.631 +// | B | +-----+ +-----+
1.632 +// | |
1.633 +// +-----+
1.634 +//
1.635 +//
1.636 +//
1.637 +// Case 5 Case 6 Case 7
1.638 +// ------ ------ ------
1.639 +// +-----+ +-----+ +-----+ +-----+
1.640 +// | | | R | | B | | | +-----+
1.641 +// | B | +-----+ +-----+ | R | | B |
1.642 +// | | | | +-----+
1.643 +// +-----+ +-----+
1.644 +// +-----+
1.645 +// | R |
1.646 +// +-----+
1.647 +//
1.648 +</pre>
1.649 +<ul>
1.650 + <li>First, check for the easiest case, where there are no existing band
1.651 +rects, or the band rect passed in is below the bottommost rect. In this case,
1.652 +just append the band rect and return.</li>
1.653 + <li>Starting at the head of the list of bandRects, check for intersection
1.654 +with the rect passed in:</li>
1.655 + <ul>
1.656 + <li>case #1: the rect is totally above the current band rect, so insert
1.657 +a new band rect before the current bandRect</li>
1.658 + <li>cases #2 and #7: the rect is partially above the band rect, so it
1.659 +is divided into two bandRects, one entirely above the band, and one containing
1.660 +the remainder of the rect. Insert the part that is totally above the
1.661 +bandRect before the current bandRect, as in case #1 above, and adjust the
1.662 +other band rect to exclude the part already added.</li>
1.663 + <li>case #5: the rect is totally below the current bandRect, so just
1.664 +skip to the next band</li>
1.665 + <li>case #3 and #4: rect is at least partially intersection with the
1.666 +bandRect, so divide the current band into two parts, where the top part is
1.667 +above the current rect. Move to the new band just created, which is
1.668 +the next band.</li>
1.669 + <li>case #6: the rect shares the bottom and height with the bandRect,
1.670 +so just add the rect to the band.</li>
1.671 + <li>case #4 and #7: create a new rect for the part that overlaps the
1.672 +bandRect, and add it to the current bandRect (similar to case #6) and then
1.673 +move on to the next band, removing that part from the rect passed in. If
1.674 +no more bands, append the rect passed in to the end of the bandRect list.</li>
1.675 + </ul>
1.676 +</ul>
1.677 +<i>This algorithm is pretty confusing - basically what needs to happen is
1.678 +that rects and bands need to be divided up so that complicated cases like
1.679 +#2, #4, and #7, are reduced to simpler cases where the rects is totally above,
1.680 +below, or between a band rect. From the current implementation, it
1.681 +might be worth verifying that the final result of the inserts is a correctly
1.682 +ordered liest of bandRects (debug mode only).</i>
1.683 +
1.684 +
1.685 +<h4>Algorithm 3: RemoveRegion</h4>
1.686 + When a float is removed, the Space Manager is notified by a call to RemoveRegion,
1.687 +passing in the frame that is being removed.
1.688 +
1.689 +<ul>
1.690 + <li>Get the FrameInfo for the frame passed in. If not found, an error is
1.691 +returned.</li>
1.692 + <li>If the rect for the frame is not empty, then visit each band in the
1.693 +bandList:</li>
1.694 + <ul>
1.695 + <li>for each rect in the band:
1.696 +
1.697 + </li>
1.698 + </ul>
1.699 + <ul>
1.700 + <ul>
1.701 + <li>if the bandRect is occupied by the frame, either remove the frame
1.702 +from the bandRect (if there are other frames sharing it) and remember that
1.703 +it was shared</li>
1.704 + <li>otherwise simply remove the bandRect (no other frames share it).</li>
1.705 + <li>if the bandRect was shared, then try to coalesce adjacent bandRects</li>
1.706 + <ul>
1.707 + <li>if the previous bandRect is directly next to the current bandRect,
1.708 +and they have the same frame list, then make the current bandRect cover the
1.709 +previous bandRect's full region (adjust the left edge to be that of the previous
1.710 +bandRect) and remove the previous bandRect.</li>
1.711 + </ul>
1.712 + </ul>
1.713 + </ul>
1.714 + <ul>
1.715 + <li>if the current band or prior band had a rect occupied byu the frame,
1.716 +then try to join the two bands via JoinBands</li>
1.717 + </ul>
1.718 + <li>Finally, destroy the frameInfo for the frame.
1.719 +
1.720 + </li>
1.721 +</ul>
1.722 +
1.723 +<br>
1.724 +
1.725 +<hr width="100%" size="2">
1.726 +<h2>Cross-Component Algorithms</h2>
1.727 +
1.728 +<br>
1.729 +
1.730 +
1.731 +
1.732 +<hr width="100%" size="2">
1.733 +<h2>Tech Notes</h2>
1.734 +<ul>
1.735 + <li>
1.736 +
1.737 + </li>
1.738 +
1.739 +</ul>
1.740 +
1.741 +
1.742 +
1.743 +
1.744 +
1.745 +</body>
1.746 +</html>
