layout/doc/DD-SpaceManager.html

   1 <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
   2 <html>
   3 <head>
   4
   5   <meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
   6   <title>Detailed Design Template</title>
   7 </head>
   8   <body>
   9
  10 <h1><font color="#cc0000">Gecko Layout Detailed Design Document</font></h1>
  11
  12 <h1>Space Manager Detailed Design</h1>
  13
  14 <h2>Overview</h2>
  15 <p>
  16   The Space Manager and related classes and structures are an important of
  17  the Gecko Layout system, specifically Block Layout. &nbsp;See the High Level
  18  Design document for an overview of the Space Manager, and as an introduction
  19  to the classes, structures and algorithms container in this, the Detailed
  20  Design Document.
  21 </p>
  22
  23
  24
  25 <hr width="100%" size="2">
  26 <h2>nsSpaceManager</h2>
  27 <p>
  28    The Space Manager is the central class is a group of classes that manage
  29  the occupied and available space that exists in horizontal bands across
  30 a  canvas. &nbsp;The primary goal of the Space Manager is to provide information
  31  about those bands of space to support the CSS notion of floated elements.
  32 </p>
  33
  34 <p>
  35   There are three important parts to the Space Manager API: the parts that
  36 deal with the coordinate space of the Space Manager, the parts that deal with
  37 the regions managed by the Space Manager, and the parts that manage float
  38 impact intervals.
  39 </p>
  40
  41 <p>
  42   The class nsSpaceManager is declared in the file <a href="http://lxr.mozilla.org/seamonkey/source/layout/base/src/nsSpaceManager.h">
  43   nsSpaceManger.h</a>
  44   . &nbsp;The class is only used in the layout module and cannot be exported
  45  outside of that module (nor does it need to be). &nbsp;It is not a general
  46  purpose class, and is not intended to be subclasses<font color="#cc0000">
  47  .</font>
  48 </p>
  49
  50 <p>
  51   Here is the class declaration, taken from the source file as of 01.08.02
  52 </p>
  53
  54
  55
  56 <pre>/**
  57  * Class for dealing with bands of available space. The space manager
  58  * defines a coordinate space with an origin at (0, 0) that grows down
  59  * and to the right.
  60  */
  61 class nsSpaceManager {
  62 public:
  63   nsSpaceManager(nsIPresShell* aPresShell, nsIFrame* aFrame);
  64   ~nsSpaceManager();
  65
  66   void* operator new(size_t aSize);
  67   void operator delete(void* aPtr, size_t aSize);
  68
  69   static void Shutdown();
  70
  71   /*
  72    * Get the frame that's associated with the space manager. This frame
  73    * created the space manager, and the world coordinate space is
  74    * relative to this frame.
  75    *
  76    * You can use QueryInterface() on this frame to get any additional
  77    * interfaces.
  78    */
  79   nsIFrame* GetFrame() const { return mFrame; }
  80
  81   /**
  82    * Translate the current origin by the specified (dx, dy). This
  83    * creates a new local coordinate space relative to the current
  84    * coordinate space.
  85    */
  86   void Translate(nscoord aDx, nscoord aDy) { mX += aDx; mY += aDy; }
  87
  88   /**
  89    * Returns the current translation from local coordinate space to
  90    * world coordinate space. This represents the accumulated calls to
  91    * Translate().
  92    */
  93   void GetTranslation(nscoord&amp; aX, nscoord&amp; aY) const { aX = mX; aY = mY; }
  94
  95   /**
  96    * Returns the y-most of the bottommost band or 0 if there are no bands.
  97    *
  98    * @return  PR_TRUE if there are bands and PR_FALSE if there are no bands
  99    */
 100   PRBool YMost(nscoord&amp; aYMost) const;
 101
 102   /**
 103    * Returns a band starting at the specified y-offset. The band data
 104    * indicates which parts of the band are available, and which parts
 105    * are unavailable
 106    *
 107    * The band data that is returned is in the coordinate space of the
 108    * local coordinate system.
 109    *
 110    * The local coordinate space origin, the y-offset, and the max size
 111    * describe a rectangle that's used to clip the underlying band of
 112    * available space, i.e.
 113    * {0, aYOffset, aMaxSize.width, aMaxSize.height} in the local
 114    * coordinate space
 115    *
 116    * @param   aYOffset the y-offset of where the band begins. The coordinate is
 117    *            relative to the upper-left corner of the local coordinate space
 118    * @param   aMaxSize the size to use to constrain the band data
 119    * @param   aBandData [in,out] used to return the list of trapezoids that
 120    *            describe the available space and the unavailable space
 121    * @return  NS_OK if successful and NS_ERROR_FAILURE if the band data is not
 122    *            not large enough. The 'count' member of the band data struct
 123    *            indicates how large the array of trapezoids needs to be
 124    */
 125   nsresult GetBandData(nscoord       aYOffset,
 126                        const nsSize&amp; aMaxSize,
 127                        nsBandData&amp;   aBandData) const;
 128
 129   /**
 130    * Add a rectangular region of unavailable space. The space is
 131    * relative to the local coordinate system.
 132    *
 133    * The region is tagged with a frame
 134    *
 135    * @param   aFrame the frame used to identify the region. Must not be NULL
 136    * @param   aUnavailableSpace the bounding rect of the unavailable space
 137    * @return  NS_OK if successful
 138    *          NS_ERROR_FAILURE if there is already a region tagged with aFrame
 139    */
 140   nsresult AddRectRegion(nsIFrame*     aFrame,
 141                          const nsRect&amp; aUnavailableSpace);
 142
 143   /**
 144    * Resize the rectangular region associated with aFrame by the specified
 145    * deltas. The height change always applies to the bottom edge or the existing
 146    * rect. You specify whether the width change applies to the left or right edge
 147    *
 148    * Returns NS_OK if successful, NS_ERROR_INVALID_ARG if there is no region
 149    * tagged with aFrame
 150    */
 151   enum AffectedEdge {LeftEdge, RightEdge};
 152   nsresult ResizeRectRegion(nsIFrame*    aFrame,
 153                             nscoord      aDeltaWidth,
 154                             nscoord      aDeltaHeight,
 155                             AffectedEdge aEdge = RightEdge);
 156
 157   /**
 158    * Offset the region associated with aFrame by the specified amount.
 159    *
 160    * Returns NS_OK if successful, NS_ERROR_INVALID_ARG if there is no region
 161    * tagged with aFrame
 162    */
 163   nsresult OffsetRegion(nsIFrame* aFrame, nscoord dx, nscoord dy);
 164
 165   /**
 166    * Remove the region associated with aFrane.
 167    *
 168    * Returns NS_OK if successful and NS_ERROR_INVALID_ARG if there is no region
 169    * tagged with aFrame
 170    */
 171   nsresult RemoveRegion(nsIFrame* aFrame);
 172
 173   /**
 174    * Clears the list of regions representing the unavailable space.
 175    */
 176   void ClearRegions();
 177
 178   /**
 179    * Methods for dealing with the propagation of float damage during
 180    * reflow.
 181    */
 182   PRBool HasFloatDamage()
 183   {
 184     return !mFloatDamage.IsEmpty();
 185   }
 186
 187   void IncludeInDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
 188   {
 189     mFloatDamage.IncludeInterval(aIntervalBegin + mY, aIntervalEnd + mY);
 190   }
 191
 192   PRBool IntersectsDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
 193   {
 194     return mFloatDamage.Intersects(aIntervalBegin + mY, aIntervalEnd + mY);
 195   }
 196
 197 #ifdef DEBUG
 198   /**
 199    * Dump the state of the spacemanager out to a file
 200    */
 201   nsresult List(FILE* out);
 202
 203   void SizeOf(nsISizeOfHandler* aHandler, PRUint32* aResult) const;
 204 #endif
 205
 206 private:
 207   // Structure that maintains information about the region associated
 208   // with a particular frame
 209   struct FrameInfo {
 210     nsIFrame* const mFrame;
 211     nsRect          mRect;       // rectangular region
 212     FrameInfo*      mNext;
 213
 214     FrameInfo(nsIFrame* aFrame, const nsRect&amp; aRect);
 215 #ifdef NS_BUILD_REFCNT_LOGGING
 216     ~FrameInfo();
 217 #endif
 218   };
 219
 220   // Doubly linked list of band rects
 221   struct BandRect : PRCListStr {
 222     nscoord   mLeft, mTop;
 223     nscoord   mRight, mBottom;
 224     PRIntn    mNumFrames;    // number of frames occupying this rect
 225     union {
 226       nsIFrame*    mFrame;   // single frame occupying the space
 227       nsVoidArray* mFrames;  // list of frames occupying the space
 228     };
 229
 230     BandRect(nscoord aLeft, nscoord aTop,
 231              nscoord aRight, nscoord aBottom,
 232              nsIFrame*);
 233     BandRect(nscoord aLeft, nscoord aTop,
 234              nscoord aRight, nscoord aBottom,
 235              nsVoidArray*);
 236     ~BandRect();
 237
 238     // List operations
 239     BandRect* Next() const {return (BandRect*)PR_NEXT_LINK(this);}
 240     BandRect* Prev() const {return (BandRect*)PR_PREV_LINK(this);}
 241     void      InsertBefore(BandRect* aBandRect) {PR_INSERT_BEFORE(aBandRect, this);}
 242     void      InsertAfter(BandRect* aBandRect) {PR_INSERT_AFTER(aBandRect, this);}
 243     void      Remove() {PR_REMOVE_LINK(this);}
 244
 245     // Split the band rect into two vertically, with this band rect becoming
 246     // the top part, and a new band rect being allocated and returned for the
 247     // bottom part
 248     //
 249     // Does not insert the new band rect into the linked list
 250     BandRect* SplitVertically(nscoord aBottom);
 251
 252     // Split the band rect into two horizontally, with this band rect becoming
 253     // the left part, and a new band rect being allocated and returned for the
 254     // right part
 255     //
 256     // Does not insert the new band rect into the linked list
 257     BandRect* SplitHorizontally(nscoord aRight);
 258
 259     // Accessor functions
 260     PRBool  IsOccupiedBy(const nsIFrame*) const;
 261     void    AddFrame(const nsIFrame*);
 262     void    RemoveFrame(const nsIFrame*);
 263     PRBool  HasSameFrameList(const BandRect* aBandRect) const;
 264     PRInt32 Length() const;
 265   };
 266
 267   // Circular linked list of band rects
 268   struct BandList : BandRect {
 269     BandList();
 270
 271     // Accessors
 272     PRBool    IsEmpty() const {return PR_CLIST_IS_EMPTY((PRCListStr*)this);}
 273     BandRect* Head() const {return (BandRect*)PR_LIST_HEAD(this);}
 274     BandRect* Tail() const {return (BandRect*)PR_LIST_TAIL(this);}
 275
 276     // Operations
 277     void      Append(BandRect* aBandRect) {PR_APPEND_LINK(aBandRect, this);}
 278
 279     // Remove and delete all the band rects in the list
 280     void      Clear();
 281   };
 282
 283
 284   FrameInfo* GetFrameInfoFor(nsIFrame* aFrame);
 285   FrameInfo* CreateFrameInfo(nsIFrame* aFrame, const nsRect&amp; aRect);
 286   void       DestroyFrameInfo(FrameInfo*);
 287
 288   void       ClearFrameInfo();
 289   void       ClearBandRects();
 290
 291   BandRect*  GetNextBand(const BandRect* aBandRect) const;
 292   void       DivideBand(BandRect* aBand, nscoord aBottom);
 293   PRBool     CanJoinBands(BandRect* aBand, BandRect* aPrevBand);
 294   PRBool     JoinBands(BandRect* aBand, BandRect* aPrevBand);
 295   void       AddRectToBand(BandRect* aBand, BandRect* aBandRect);
 296   void       InsertBandRect(BandRect* aBandRect);
 297
 298   nsresult   GetBandAvailableSpace(const BandRect* aBand,
 299                                    nscoord         aY,
 300                                    const nsSize&amp;   aMaxSize,
 301                                    nsBandData&amp;     aAvailableSpace) const;
 302
 303   nsIFrame* const mFrame;     // frame associated with the space manager
 304   nscoord         mX, mY;     // translation from local to global coordinate space
 305   BandList        mBandList;  // header/sentinel for circular linked list of band rects
 306   FrameInfo*      mFrameInfoMap;
 307   nsIntervalSet   mFloatDamage;
 308
 309   static PRInt32 sCachedSpaceManagerCount;
 310   static void* sCachedSpaceManagers[NS_SPACE_MANAGER_CACHE_SIZE];
 311
 312   nsSpaceManager(const nsSpaceManager&amp;);  // no implementation
 313   void operator=(const nsSpaceManager&amp;);  // no implementation
 314 };
 315
 316 </pre>
 317
 318 <h3>Public API</h3>
 319
 320 <h4>Life Cycle:</h4>
 321 <p>
 322   The Constructor requires a Presentation Shell, used for arena allocations
 323  mostly, and a frame that this Space Manager is rooted on. &nbsp;The coordinate
 324  space of this Space Manager is relative to the frame passed in to the constructor.
 325 </p>
 326
 327 <pre>  nsSpaceManager(nsIPresShell* aPresShell, nsIFrame* aFrame);
 328   ~nsSpaceManager();
 329 </pre>
 330 <p>
 331   Operators 'new' and 'delete' are overridden to support a recycler. &nbsp;Space
 332  Manager instances come and go pretty frequently, and this recycler prevents
 333  excessive heap allocations and the performance penalties associated with
 334 it. The #define NS_SPACE_MANAGER_CACHE_SIZE is used to control the number
 335 of Space Manager instances that can be present in the recycler, currently
 336 4. &nbsp;If more than NS_SPACE_MANAGER_CACHE_SIZE are allocated at a time,
 337 then standard allocation is used.
 338 </p>
 339
 340 <pre>
 341   void* operator new(size_t aSize);
 342   void operator delete(void* aPtr, size_t aSize);
 343
 344 </pre>
 345 <p>
 346  A Static method is used to shutdown the Space Manager recycling. &nbsp;This
 347 method deletes all of the Space Mangers inthe recycler,and prevents further
 348 recycling. &nbsp;It is meant to be called only when the layout module is being
 349 terminated.
 350 </p>
 351
 352 <pre>  static void Shutdown();
 353
 354 </pre>
 355
 356 <h4>Origin / Coordinate Space Translation</h4>
 357
 358 <pre>  /**
 359    * Translate the current origin by the specified (dx, dy). This
 360    * creates a new local coordinate space relative to the current
 361    * coordinate space.
 362    */
 363   void Translate(nscoord aDx, nscoord aDy) { mX += aDx; mY += aDy; }
 364
 365   /**
 366    * Returns the current translation from local coordinate space to
 367    * world coordinate space. This represents the accumulated calls to
 368    * Translate().
 369    */
 370   void GetTranslation(nscoord&amp; aX, nscoord&amp; aY) const { aX = mX; aY = mY; }
 371
 372   /**
 373    * Returns the y-most of the bottommost band or 0 if there are no bands.
 374    *
 375    * @return  PR_TRUE if there are bands and PR_FALSE if there are no bands
 376    */
 377   PRBool YMost(nscoord&amp; aYMost) const;
 378 </pre>
 379
 380 <h4>Region Management</h4>
 381
 382 <pre>  /**
 383    * Returns a band starting at the specified y-offset. The band data
 384    * indicates which parts of the band are available, and which parts
 385    * are unavailable
 386    *
 387    * The band data that is returned is in the coordinate space of the
 388    * local coordinate system.
 389    *
 390    * The local coordinate space origin, the y-offset, and the max size
 391    * describe a rectangle that's used to clip the underlying band of
 392    * available space, i.e.
 393    * {0, aYOffset, aMaxSize.width, aMaxSize.height} in the local
 394    * coordinate space
 395    *
 396    * @param   aYOffset the y-offset of where the band begins. The coordinate is
 397    *            relative to the upper-left corner of the local coordinate space
 398    * @param   aMaxSize the size to use to constrain the band data
 399    * @param   aBandData [in,out] used to return the list of trapezoids that
 400    *            describe the available space and the unavailable space
 401    * @return  NS_OK if successful and NS_ERROR_FAILURE if the band data is not
 402    *            not large enough. The 'count' member of the band data struct
 403    *            indicates how large the array of trapezoids needs to be
 404    */
 405   nsresult GetBandData(nscoord       aYOffset,
 406                        const nsSize&amp; aMaxSize,
 407                        nsBandData&amp;   aBandData) const;
 408
 409   /**
 410    * Add a rectangular region of unavailable space. The space is
 411    * relative to the local coordinate system.
 412    *
 413    * The region is tagged with a frame
 414    *
 415    * @param   aFrame the frame used to identify the region. Must not be NULL
 416    * @param   aUnavailableSpace the bounding rect of the unavailable space
 417    * @return  NS_OK if successful
 418    *          NS_ERROR_FAILURE if there is already a region tagged with aFrame
 419    */
 420   nsresult AddRectRegion(nsIFrame*     aFrame,
 421                          const nsRect&amp; aUnavailableSpace);
 422
 423   /**
 424    * Resize the rectangular region associated with aFrame by the specified
 425    * deltas. The height change always applies to the bottom edge or the existing
 426    * rect. You specify whether the width change applies to the left or right edge
 427    *
 428    * Returns NS_OK if successful, NS_ERROR_INVALID_ARG if there is no region
 429    * tagged with aFrame
 430    */
 431   enum AffectedEdge {LeftEdge, RightEdge};
 432   nsresult ResizeRectRegion(nsIFrame*    aFrame,
 433                             nscoord      aDeltaWidth,
 434                             nscoord      aDeltaHeight,
 435                             AffectedEdge aEdge = RightEdge);
 436
 437   /**
 438    * Offset the region associated with aFrame by the specified amount.
 439    *
 440    * Returns NS_OK if successful, NS_ERROR_INVALID_ARG if there is no region
 441    * tagged with aFrame
 442    */
 443   nsresult OffsetRegion(nsIFrame* aFrame, nscoord dx, nscoord dy);
 444
 445   /**
 446    * Remove the region associated with aFrane.
 447    *
 448    * Returns NS_OK if successful and NS_ERROR_INVALID_ARG if there is no region
 449    * tagged with aFrame
 450    */
 451   nsresult RemoveRegion(nsIFrame* aFrame);
 452
 453   /**
 454    * Clears the list of regions representing the unavailable space.
 455    */
 456   void ClearRegions();
 457 </pre>
 458
 459 <h4>Float Impact</h4>
 460
 461 <pre>  /**
 462    * Methods for dealing with the propagation of float damage during
 463    * reflow.
 464    */
 465   PRBool HasFloatDamage()
 466   {
 467     return !mFloatDamage.IsEmpty();
 468   }
 469
 470   void IncludeInDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
 471   {
 472     mFloatDamage.IncludeInterval(aIntervalBegin + mY, aIntervalEnd + mY);
 473   }
 474
 475   PRBool IntersectsDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
 476   {
 477     return mFloatDamage.Intersects(aIntervalBegin + mY, aIntervalEnd + mY);
 478   }
 479 </pre>
 480
 481 <h4>Debug Only Methods</h4>
 482
 483 <pre>  /**
 484    * Dump the state of the spacemanager out to a file
 485    */
 486   nsresult List(FILE* out);
 487
 488   void SizeOf(nsISizeOfHandler* aHandler, PRUint32* aResult) const;
 489
 490 </pre>
 491
 492 <h4>Unused / Obsolete Methods</h4>
 493
 494 <pre>  /*
 495    * Get the frame that's associated with the space manager. This frame
 496    * created the space manager, and the world coordinate space is
 497    * relative to this frame.
 498    *
 499    * You can use QueryInterface() on this frame to get any additional
 500    * interfaces.
 501    */
 502    nsIFrame* GetFrame() const { return mFrame; }
 503
 504 </pre>
 505
 506 <h3>Implementation Notes</h3>
 507
 508 <h4></h4>
 509
 510 <h4>Algorithm 1: GetBandData</h4>
 511 <p>
 512 GetBandData is used to provide information to clients about what space if
 513 available and unavailable in a band of space. &nbsp;The client provides a
 514 vertical offset, the yOffset, that corresponds to the band that is of interest.
 515 &nbsp;This will be the y offset of the frame that is being reflowed. &nbsp;The
 516 caller also provides a collection of BandData objects (an array) and the
 517 number of items that the collection can handle. &nbsp;If the collection is
 518 too small, then an error is returned and the count is updated to indicate
 519 the size required.
 520 </p>
 521
 522 <p>
 523 The algorithm to provide the band data is as follows:
 524 </p>
 525 <ul>
 526   <li>Get a &nbsp;vertical offset in world coordinates (instead of frame-relative
 527 coordinates) by adding the y-origin of the SpaceManager to the y offset passed
 528 in</li>
 529   <li>If the (adjusted) y value passed in is greater than the greatest band
 530 being managed, then all space is available so a single trapezoid is returned,
 531 marked as available and sized to the maximum size value (passed in).</li>
 532   <li>If the (adjusted) y offset intersects a band, then gather the band
 533 data:</li>
 534   <ul>
 535     <li>walk the internal bandData list from head to tail</li>
 536     <li>for each band data entry, see if the top of the band is greater than
 537 the (adjusted) y offset requested</li>
 538     <li>if it is, then band is below the offset requested, so the area between
 539 the band and the y offset is available - create a trapezoid with that region
 540 and return it.</li>
 541     <li>if the (adjusted) y offset is between the band top and bottom, then
 542 get the available space for the band by calling GetBandAvailableSpace</li>
 543     <li>otherwise, move to the next band</li>
 544   </ul>
 545 </ul>
 546 <h5>GetBandAvailableSpace:</h5>
 547 This method is called from GetBandData only. It walks all of the bands in
 548 the space manager and determines which bands intersect with the band passed
 549 in, and if within those bands there are regions that are available or occupied.
 550
 551 <ul>
 552   <li>First, walk all of the bands until a band that is to the right of the
 553 desired offset is located</li>
 554   <li>Starting at that band, &nbsp;walk the remaining bands:</li>
 555   <ul>
 556     <li>if the current band is to the right of the requested band, then there
 557 is available space.&nbsp;</li>
 558     <ul>
 559       <li>if there is more room in the bandData collection, then add a trapezoid
 560 to the bandData collection such that it is marked as available and has a
 561 rect that represents the space between the reference band tna dht band being
 562 examined</li>
 563       <li>if there is no more room in the BandData collection, estimate the
 564 number of entries requires as the current count + twice the number of bands
 565 below the reference band, plus two. &nbsp;Return an error code so the caller
 566 can reallocate the collection and try again.</li>
 567     </ul>
 568     <li>check the size of the collection again, if there is no room left
 569 then estimate the number of items requires as the current count + twice the
 570 number of bands below the band in question plus one.&nbsp;</li>
 571     <li>create a new trapezoid in the band collection that has a region corresponding
 572 to the reference band rect, marked as occupied by either a single or multiple
 573 frames.</li>
 574     <li>move to the next band</li>
 575   </ul>
 576   <li>after walking all of the band data, se if we have reached the right
 577 edge of the band.&nbsp;</li>
 578   <ul>
 579     <li>If not, then check for space in the band collection</li>
 580     <ul>
 581       <li>if there is no room left, then set the count to the current count
 582 plus 1 and return an error.</li>
 583       <li>otherwise, create another entry in the band collection, marked
 584 as available, and with a rect corresponding to the area remainin in the band
 585 (eg. from the right edge of the last band rect to the right edge of the band).</li>
 586     </ul>
 587   </ul>
 588 </ul>
 589
 590 <h4>Algorithm 2: AddRectRegion</h4>
 591 Clients call into this method to notify the Space Manager that a new frame
 592 is occupying some space.
 593
 594 <ul>
 595   <li>First, try to get frame info for the frame. If it is found, return
 596 an error since the frame is already associated with a region in the Space
 597 Manager.</li>
 598   <li>Next, create a rect from the occupied space passed in by the caller,
 599 transforming it first to world-coordinates by adding the Space Manager's
 600 offset to the occupied space rect passed in.</li>
 601   <li>Create a new Frame Info instance for the frame and rect, returning
 602 an error if allocation fails.</li>
 603   <li>Check if the occupied space rect (adjusted) is empty, if so, return
 604 an error &nbsp;(<font color="#cc0000">NOTE: this could be done earlier, or
 605 prevented by the caller</font>)</li>
 606   <li>Allocate a new BandRect instance with the rect and frame as constructor
 607 arguments, and insert it into the collection via InsertBandRect</li>
 608 </ul>
 609 <h5>InsertBandRect:</h5>
 610 Internal method to insert a band rect into the BandList in the correct location.
 611 There are several cases it has to handle, as specified in the source file
 612 comments:
 613
 614 <pre>// When comparing a rect to a band there are seven cases to consider.
 615 // 'R' is the rect and 'B' is the band.
 616 //
 617 //      Case 1              Case 2              Case 3              Case 4
 618 //      ------              ------              ------              ------
 619 // +-----+             +-----+                      +-----+             +-----+
 620 // |  R  |             |  R  |  +-----+    +-----+  |     |             |     |
 621 // +-----+             +-----+  |     |    |  R  |  |  B  |             |  B  |
 622 //          +-----+             |  B  |    +-----+  |     |    +-----+  |     |
 623 //          |     |             |     |             +-----+    |  R  |  +-----+
 624 //          |  B  |             +-----+                        +-----+
 625 //          |     |
 626 //          +-----+
 627 //
 628 //
 629 //
 630 //      Case 5              Case 6              Case 7
 631 //      ------              ------              ------
 632 //          +-----+    +-----+  +-----+    +-----+
 633 //          |     |    |  R  |  |  B  |    |     |  +-----+
 634 //          |  B  |    +-----+  +-----+    |  R  |  |  B  |
 635 //          |     |                        |     |  +-----+
 636 //          +-----+                        +-----+
 637 // +-----+
 638 // |  R  |
 639 // +-----+
 640 //
 641 </pre>
 642 <ul>
 643   <li>First, check for the easiest case, where there are no existing band
 644 rects, or the band rect passed in is below the bottommost rect. In this case,
 645 just append the band rect and return.</li>
 646   <li>Starting at the head of the list of bandRects, check for intersection
 647 with the rect passed in:</li>
 648   <ul>
 649     <li>case #1: the rect is totally above the current band rect, so insert
 650 a new band rect before the current bandRect</li>
 651     <li>cases #2 and #7: the rect is partially above the band rect, so it
 652 is divided into two bandRects, one entirely above the band, and one containing
 653 the remainder of the rect. &nbsp;Insert the part that is totally above the
 654 bandRect before the current bandRect, as in case #1 above, and adjust the
 655 other band rect to exclude the part already added.</li>
 656     <li>case #5: the rect is totally below the current bandRect, so just
 657 skip to the next band</li>
 658     <li>case #3 and #4: rect is at least partially intersection with the
 659 bandRect, so divide the current band into two parts, where the top part is
 660 above the current rect. &nbsp;Move to the new band just created, which is
 661 the next band.</li>
 662     <li>case #6: the rect shares the bottom and height with the bandRect,
 663 so just add the rect to the band.</li>
 664     <li>case #4 and #7: create a new rect for the part that overlaps the
 665 bandRect, and add it to the current bandRect (similar to case #6) and then
 666 move on to the next band, removing that part from the rect passed in. &nbsp;If
 667 no more bands, append the rect passed in to the end of the bandRect list.</li>
 668   </ul>
 669 </ul>
 670 <i>This algorithm is pretty confusing - basically what needs to happen is
 671 that rects and bands need to be divided up so that complicated cases like
 672 #2, #4, and #7, are reduced to simpler cases where the rects is totally above,
 673 below, or between a band rect. &nbsp;From the current implementation, it
 674 might be worth verifying that the final result of the inserts is a correctly
 675 ordered liest of bandRects (debug mode only).</i>
 676
 677
 678 <h4>Algorithm 3: RemoveRegion</h4>
 679  When a float is removed, the Space Manager is notified by a call to RemoveRegion,
 680 passing in the frame that is being removed.
 681
 682 <ul>
 683   <li>Get the FrameInfo for the frame passed in. If not found, an error is
 684 returned.</li>
 685   <li>If the rect for the frame is not empty, then visit each band in the
 686 bandList:</li>
 687   <ul>
 688     <li>for each rect in the band:
 689
 690     </li>
 691   </ul>
 692   <ul>
 693     <ul>
 694       <li>if the bandRect is occupied by the frame, either remove the frame
 695 from the bandRect (if there are other frames sharing it) and remember that
 696 it was shared</li>
 697       <li>otherwise simply remove the bandRect (no other frames share it).</li>
 698       <li>if the bandRect was shared, then try to coalesce adjacent bandRects</li>
 699       <ul>
 700         <li>if the previous bandRect is directly next to the current bandRect,
 701 and they have the same frame list, then make the current bandRect cover the
 702 previous bandRect's full region (adjust the left edge to be that of the previous
 703 bandRect) and remove the previous bandRect.</li>
 704       </ul>
 705     </ul>
 706   </ul>
 707   <ul>
 708     <li>if the current band or prior band had a rect occupied byu the frame,
 709 then try to join the two bands via JoinBands</li>
 710   </ul>
 711   <li>Finally, destroy the frameInfo for the frame.
 712
 713   </li>
 714 </ul>
 715
 716 <br>
 717
 718 <hr width="100%" size="2">
 719 <h2>Cross-Component Algorithms</h2>
 720
 721 <br>
 722
 723
 724
 725 <hr width="100%" size="2">
 726 <h2>Tech Notes</h2>
 727 <ul>
 728   <li>
 729
 730   </li>
 731
 732 </ul>
 733
 734
 735
 736
 737
 738 </body>
 739 </html>