"Fossies" - the Fresh Open Source Software Archive

Member "firefox-69.0.1/layout/doc/DD-SpaceManager.html" (17 Sep 2019, 27144 Bytes) of package /linux/www/firefox-69.0.1.source.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) HTML source code syntax highlighting (style: standard) with prefixed line numbers. Alternatively you can here view or download the uninterpreted source code file.

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