Replace space manager with a more limited float manager. (Bug 191448) r+sr=roc
authorL. David Baron <dbaron@dbaron.org>
Sun, 04 Jan 2009 19:39:54 -0500
changeset 23306 496e0cb5c943e630c473dbce949d6437e05c62ac
parent 23305 b19f0a7a3c4c11484d38110b6bbf7dcb6449b2e4
child 23307 aa32889429dba54d7f0b6dbc87e7bfc081fb666b
push idunknown
push userunknown
push dateunknown
bugs191448
milestone1.9.2a1pre
Replace space manager with a more limited float manager. (Bug 191448) r+sr=roc
layout/build/nsLayoutStatics.cpp
layout/generic/Makefile.in
layout/generic/nsBlockBandData.cpp
layout/generic/nsBlockBandData.h
layout/generic/nsBlockDebugFlags.h
layout/generic/nsBlockFrame.cpp
layout/generic/nsBlockReflowContext.cpp
layout/generic/nsBlockReflowState.cpp
layout/generic/nsBlockReflowState.h
layout/generic/nsFloatManager.cpp
layout/generic/nsFloatManager.h
layout/generic/nsLineBox.cpp
layout/generic/nsLineBox.h
layout/generic/nsLineLayout.cpp
layout/generic/nsSpaceManager.cpp
layout/generic/nsSpaceManager.h
layout/svg/base/src/nsSVGForeignObjectFrame.cpp
layout/xul/base/src/nsBoxFrame.cpp
--- a/layout/build/nsLayoutStatics.cpp
+++ b/layout/build/nsLayoutStatics.cpp
@@ -62,17 +62,17 @@
 #include "nsStyledElement.h"
 #include "nsGlobalWindow.h"
 #include "nsGkAtoms.h"
 #include "nsImageFrame.h"
 #include "nsLayoutStylesheetCache.h"
 #include "nsNodeInfo.h"
 #include "nsRange.h"
 #include "nsRepeatService.h"
-#include "nsSpaceManager.h"
+#include "nsFloatManager.h"
 #include "nsSprocketLayout.h"
 #include "nsStackLayout.h"
 #include "nsStyleSet.h"
 #include "nsTextControlFrame.h"
 #include "nsXBLWindowKeyHandler.h"
 #include "txMozillaXSLTProcessor.h"
 #include "nsDOMStorage.h"
 #include "nsCellMap.h"
--- a/layout/generic/Makefile.in
+++ b/layout/generic/Makefile.in
@@ -108,24 +108,24 @@ EXPORTS		+= \
 		nsBidiFrames.h      \
 		$(NULL)
 endif
 
 
 CPPSRCS		= \
 		nsAbsoluteContainingBlock.cpp \
 		nsBRFrame.cpp \
-		nsBlockBandData.cpp \
 		nsBlockFrame.cpp \
 		nsBlockReflowContext.cpp \
 		nsBlockReflowState.cpp \
 		nsBulletFrame.cpp \
 		nsColumnSetFrame.cpp \
 		nsContainerFrame.cpp \
 		nsFirstLetterFrame.cpp \
+		nsFloatManager.cpp \
 		nsFrame.cpp \
 		nsFrameFrame.cpp \
 		nsFrameList.cpp \
 		nsFrameSetFrame.cpp \
 		nsFrameUtil.cpp \
 		nsGfxScrollFrame.cpp \
 		nsHTMLCanvasFrame.cpp \
 		nsHTMLContainerFrame.cpp \
@@ -139,17 +139,16 @@ CPPSRCS		= \
 		nsLineBox.cpp \
 		nsLineLayout.cpp \
 		nsObjectFrame.cpp \
 		nsPageContentFrame.cpp \
 		nsPageFrame.cpp \
 		nsPlaceholderFrame.cpp \
 		nsSelection.cpp \
 		nsSimplePageSequence.cpp \
-		nsSpaceManager.cpp \
 		nsSpacerFrame.cpp \
 		nsSplittableFrame.cpp \
 		nsTextFrameThebes.cpp \
 		nsTextFrameUtils.cpp \
 		nsTextRunTransformations.cpp \
 		nsViewportFrame.cpp \
 		$(NULL)
 
deleted file mode 100644
--- a/layout/generic/nsBlockBandData.cpp
+++ /dev/null
@@ -1,270 +0,0 @@
-/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
-/* ***** BEGIN LICENSE BLOCK *****
- * Version: MPL 1.1/GPL 2.0/LGPL 2.1
- *
- * The contents of this file are subject to the Mozilla Public License Version
- * 1.1 (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- * http://www.mozilla.org/MPL/
- *
- * Software distributed under the License is distributed on an "AS IS" basis,
- * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
- * for the specific language governing rights and limitations under the
- * License.
- *
- * The Original Code is Mozilla Communicator client code.
- *
- * The Initial Developer of the Original Code is
- * Netscape Communications Corporation.
- * Portions created by the Initial Developer are Copyright (C) 1998
- * the Initial Developer. All Rights Reserved.
- *
- * Contributor(s):
- *
- * Alternatively, the contents of this file may be used under the terms of
- * either of the GNU General Public License Version 2 or later (the "GPL"),
- * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
- * in which case the provisions of the GPL or the LGPL are applicable instead
- * of those above. If you wish to allow use of your version of this file only
- * under the terms of either the GPL or the LGPL, and not to allow others to
- * use your version of this file under the terms of the MPL, indicate your
- * decision by deleting the provisions above and replace them with the notice
- * and other provisions required by the GPL or the LGPL. If you do not delete
- * the provisions above, a recipient may use your version of this file under
- * the terms of any one of the MPL, the GPL or the LGPL.
- *
- * ***** END LICENSE BLOCK ***** */
-
-/* code for management of floats that implements float manager interfaces */
-
-#include "nsCOMPtr.h"
-#include "nsBlockBandData.h"
-#include "nsIFrame.h"
-#include "nsHTMLReflowState.h"
-#include "nsPresContext.h"
-#include "nsIPresShell.h"
-
-nsBlockBandData::nsBlockBandData()
-  : mSpaceManager(nsnull),
-    mSpaceManagerX(0),
-    mSpaceManagerY(0),
-    mSpace(0, 0)
-{
-  mSize = NS_BLOCK_BAND_DATA_TRAPS;
-  mTrapezoids = mData;
-}
-
-nsBlockBandData::~nsBlockBandData()
-{
-  if (mTrapezoids != mData) {
-    delete [] mTrapezoids;
-  }
-}
-
-nsresult
-nsBlockBandData::Init(nsSpaceManager* aSpaceManager,
-                      const nsSize& aSpace)
-{
-  NS_PRECONDITION(aSpaceManager, "null pointer");
-
-  mSpaceManager = aSpaceManager;
-  aSpaceManager->GetTranslation(mSpaceManagerX, mSpaceManagerY);
-
-  mSpace = aSpace;
-  mLeftFloats = 0;
-  mRightFloats = 0;
-  return NS_OK;
-}
-
-// Get the available reflow space for the current y coordinate. The
-// available space is relative to our coordinate system (0,0) is our
-// upper left corner.
-nsresult
-nsBlockBandData::GetAvailableSpace(nscoord aY, PRBool aRelaxHeightConstraint,
-                                   nsRect& aResult)
-{
-  // Get the raw band data for the given Y coordinate
-  nsresult rv = GetBandData(aY, aRelaxHeightConstraint);
-  if (NS_FAILED(rv)) { return rv; }
-
-  // Compute the bounding rect of the available space, i.e. space
-  // between any left and right floats.
-  ComputeAvailSpaceRect();
-  aResult = mAvailSpace;
-#ifdef REALLY_NOISY_COMPUTEAVAILSPACERECT
-  printf("nsBBD %p GetAvailableSpace(%d) returning (%d, %d, %d, %d)\n",
-          this, aY, aResult.x, aResult.y, aResult.width, aResult.height);
-#endif
-  return NS_OK;
-}
-
-// the code below should never loop more than a very few times.
-// this is a safety valve to see if we've gone off the deep end
-#define ERROR_TOO_MANY_ITERATIONS 1000
-
-/* nsBlockBandData methods should never call mSpaceManager->GetBandData directly.
- * They should always call nsBlockBandData::GetBandData() instead.
- */
-nsresult
-nsBlockBandData::GetBandData(nscoord aY, PRBool aRelaxHeightConstraint)
-{
-  NS_ASSERTION(mSpaceManager, "bad state, no float manager");
-  PRInt32 iterations =0;
-  nsSize space = mSpace;
-  if (aRelaxHeightConstraint) {
-    space.height = NS_UNCONSTRAINEDSIZE;
-  }
-  nsresult rv = mSpaceManager->GetBandData(aY, space, *this);
-  while (NS_FAILED(rv)) {
-    iterations++;
-    if (iterations>ERROR_TOO_MANY_ITERATIONS)
-    {
-      NS_ASSERTION(PR_FALSE, "too many iterations in nsBlockBandData::GetBandData");
-      return NS_ERROR_FAILURE;
-    }
-    // We need more space for our bands
-    NS_ASSERTION(mTrapezoids, "bad state, no mTrapezoids");
-    if (mTrapezoids && (mTrapezoids != mData)) {
-      delete [] mTrapezoids;
-    }
-    PRInt32 newSize = mSize * 2;
-    if (newSize<mCount) {
-      newSize = mCount;
-    }
-    mTrapezoids = new nsBandTrapezoid[newSize];
-    NS_POSTCONDITION(mTrapezoids, "failure allocating mTrapezoids");
-    if (!mTrapezoids) {
-      return NS_ERROR_OUT_OF_MEMORY;
-    }
-    mSize = newSize;
-    rv = mSpaceManager->GetBandData(aY, space, *this);
-  }
-  NS_POSTCONDITION(mCount<=mSize, "bad state, count > size");
-  return NS_OK;
-}
-
-
-
-/**
- * Computes the bounding rect of the available space, i.e. space
- * between any left and right floats. Uses the current trapezoid
- * data, see nsISpaceManager::GetBandData(). Also updates member
- * data "availSpace".
- */
-void
-nsBlockBandData::ComputeAvailSpaceRect()
-{
-#ifdef REALLY_NOISY_COMPUTEAVAILSPACERECT
-  printf("nsBlockBandData::ComputeAvailSpaceRect %p with count %d\n", this, mCount);
-#endif
-  if (0 == mCount) {
-    mAvailSpace.x = 0;
-    mAvailSpace.y = 0;
-    mAvailSpace.width = 0;
-    mAvailSpace.height = 0;
-    mLeftFloats = 0;
-    mRightFloats = 0;
-    return;
-  }
-
-  nsBandTrapezoid* trapezoid = mTrapezoids;
-  // The trapezoid to the left of the first right-floated trapezoid.
-  nsBandTrapezoid* rightTrapezoid = nsnull;
-
-  PRInt32 leftFloats = 0;
-  PRInt32 rightFloats = 0;
-  if (mCount > 1) {
-    // If there's more than one trapezoid that means there are floats
-    PRInt32 i;
-
-    // Examine each trapezoid in the band, counting up the number of
-    // left and right floats. Use the right-most float to
-    // determine where the right edge of the available space is.
-    NS_PRECONDITION(mCount<=mSize, "bad state, count > size");
-    for (i = 0; i < mCount; i++) {
-      trapezoid = &mTrapezoids[i];
-      if (trapezoid->mFrames) {
-#ifdef REALLY_NOISY_COMPUTEAVAILSPACERECT
-        printf("band %p checking !Avail trap %p with frame %p\n", this, trapezoid, trapezoid->mFrames);
-#endif
-        const nsSmallVoidArray* frames = trapezoid->mFrames;
-        const PRInt32 numFrames = frames->Count();
-        NS_ASSERTION(numFrames > 0, "bad trapezoid frame list");
-        for (PRInt32 j = 0; j < numFrames; j++) {
-          nsIFrame* f = static_cast<nsIFrame*>(frames->ElementAt(j));
-          const nsStyleDisplay* display = f->GetStyleDisplay();
-          if (NS_STYLE_FLOAT_LEFT == display->mFloats) {
-            leftFloats++;
-          }
-          else if (NS_STYLE_FLOAT_RIGHT == display->mFloats) {
-            rightFloats++;
-            if ((nsnull == rightTrapezoid) && (i > 0)) {
-              rightTrapezoid = &mTrapezoids[i - 1];
-            }
-          }
-        }
-      }
-    }
-  }
-  else if (mTrapezoids[0].mFrames) {
-    // We have a float using up all the available space
-    leftFloats = 1;
-  }
-#ifdef REALLY_NOISY_COMPUTEAVAILSPACERECT
-  printf("band %p has floats %d, %d\n", this, leftFloats, rightFloats);
-#endif
-  mLeftFloats = leftFloats;
-  mRightFloats = rightFloats;
-
-  // We look for available space in the last trapezoid before the
-  // first right float, or in the last trapezoid if there is no right
-  // float or no trapezoid before the first right float.
-  if (nsnull != rightTrapezoid) {
-    trapezoid = rightTrapezoid;
-  }
-  trapezoid->GetRect(mAvailSpace);
-
-  // When there is no available space, we still need a proper X
-  // coordinate to place objects that end up here anyway.
-  const nsSmallVoidArray* frames = trapezoid->mFrames;
-  if (frames) {
-    // It's not clear what coordinate to use when there is no
-    // available space and the space is multiply occupied...So: If
-    // any of the floats that are a part of the trapezoid are left
-    // floats then we move over to the right edge of the
-    // unavaliable space.
-    const PRInt32 numFrames = frames->Count();
-    NS_ASSERTION(numFrames > 0, "bad trapezoid frame list");
-    for (PRInt32 j = 0; j < numFrames; j++) {
-      nsIFrame* f = static_cast<nsIFrame*>(frames->ElementAt(j));
-      const nsStyleDisplay* display = f->GetStyleDisplay();
-      if (NS_STYLE_FLOAT_LEFT == display->mFloats) {
-        mAvailSpace.x = mAvailSpace.XMost();
-        break;
-      }
-    }
-    mAvailSpace.width = 0;
-  }
-
-  // Fixup width
-  if (NS_UNCONSTRAINEDSIZE == mSpace.width) {
-    mAvailSpace.width = NS_UNCONSTRAINEDSIZE;
-  }
-#ifdef REALLY_NOISY_COMPUTEAVAILSPACERECT
-  printf("  ComputeAvailSpaceRect settting state mAvailSpace (%d,%d,%d,%d)\n", 
-         mAvailSpace.x, mAvailSpace.y, mAvailSpace.width, mAvailSpace.height);
-#endif
-
-}
-
-#ifdef DEBUG
-void nsBlockBandData::List()
-{
-  printf("nsBlockBandData %p sm=%p, sm coord = (%d,%d), mSpace = (%d,%d)\n",
-          this, mSpaceManager, mSpaceManagerX, mSpaceManagerY,
-          mSpace.width, mSpace.height);
-  printf("  availSpace=(%d, %d, %d, %d), floats l=%d r=%d\n",
-          mAvailSpace.x, mAvailSpace.y, mAvailSpace.width, mAvailSpace.height,
-          mLeftFloats, mRightFloats);
-}
-#endif
deleted file mode 100644
--- a/layout/generic/nsBlockBandData.h
+++ /dev/null
@@ -1,126 +0,0 @@
-/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
-/* ***** BEGIN LICENSE BLOCK *****
- * Version: MPL 1.1/GPL 2.0/LGPL 2.1
- *
- * The contents of this file are subject to the Mozilla Public License Version
- * 1.1 (the "License"); you may not use this file except in compliance with
- * the License. You may obtain a copy of the License at
- * http://www.mozilla.org/MPL/
- *
- * Software distributed under the License is distributed on an "AS IS" basis,
- * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
- * for the specific language governing rights and limitations under the
- * License.
- *
- * The Original Code is Mozilla Communicator client code.
- *
- * The Initial Developer of the Original Code is
- * Netscape Communications Corporation.
- * Portions created by the Initial Developer are Copyright (C) 1998
- * the Initial Developer. All Rights Reserved.
- *
- * Contributor(s):
- *
- * Alternatively, the contents of this file may be used under the terms of
- * either of the GNU General Public License Version 2 or later (the "GPL"),
- * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
- * in which case the provisions of the GPL or the LGPL are applicable instead
- * of those above. If you wish to allow use of your version of this file only
- * under the terms of either the GPL or the LGPL, and not to allow others to
- * use your version of this file under the terms of the MPL, indicate your
- * decision by deleting the provisions above and replace them with the notice
- * and other provisions required by the GPL or the LGPL. If you do not delete
- * the provisions above, a recipient may use your version of this file under
- * the terms of any one of the MPL, the GPL or the LGPL.
- *
- * ***** END LICENSE BLOCK ***** */
-
-/* code for management of floats that implements float manager interfaces */
-
-#ifndef nsBlockBandData_h___
-#define nsBlockBandData_h___
-
-#include "nsSpaceManager.h"
-
-class nsPresContext;
-
-// Number of builtin nsBandTrapezoid's
-#define NS_BLOCK_BAND_DATA_TRAPS 6
-
-/**
- * Class used to manage processing of the space-manager band data.
- * Provides HTML/CSS specific behavior to the raw data.
- */
-class nsBlockBandData : public nsBandData {
-public:
-  nsBlockBandData();
-  ~nsBlockBandData();
-
-  // Initialize. This must be called before any of the other methods.
-  nsresult Init(nsSpaceManager* aSpaceManager, const nsSize& aSpace);
-
-  // Get some available space. Note that aY is relative to the current
-  // float manager translation.
-  nsresult GetAvailableSpace(nscoord aY, PRBool aRelaxHeightConstraint,
-                             nsRect& aResult);
-
-  // Get the raw trapezoid count for this band.
-  PRInt32 GetTrapezoidCount() const {
-    return mCount;
-  }
-
-  const nsBandTrapezoid* GetTrapezoid(PRInt32 aIndex) const {
-    return &mTrapezoids[aIndex];
-  }
-
-  // Get the number of floats that are impacting the current
-  // band. Note that this value is relative to the current translation
-  // in the float manager which means that some floats may be hidden
-  // by the translation and therefore won't be in the count.
-  PRInt32 GetFloatCount() const {
-    return mLeftFloats + mRightFloats;
-  }
-  PRInt32 GetLeftFloatCount() const {
-    return mLeftFloats;
-  }
-  PRInt32 GetRightFloatCount() const {
-    return mRightFloats;
-  }
-
-#ifdef DEBUG
-  void List();
-#endif
-
-protected:
-
-  /** utility method to calculate the band data at aY.
-    * nsBlockBandData methods should never call 
-    * mSpaceManager->GetBandData directly.
-    * They should always call this method instead so data members
-    * mTrapezoid, mCount, and mSize all get managed properly.
-    */
-  nsresult GetBandData(nscoord aY, PRBool aRelaxHeightConstraint);
-
-  // The spacemanager we are getting space from
-  nsSpaceManager* mSpaceManager;
-  nscoord mSpaceManagerX, mSpaceManagerY;
-
-  // Limit to the available space (set by Init)
-  nsSize mSpace;
-
-  // Trapezoids used during band processing
-  nsBandTrapezoid mData[NS_BLOCK_BAND_DATA_TRAPS];
-
-  // Bounding rect of available space between any left and right floats
-  nsRect mAvailSpace;
-
-  // Number of left/right floats in the current band. Note that this
-  // number may be less than the total number of floats present in
-  // the band, if our translation in the float manager "hides" some
-  // floats.
-  PRInt32 mLeftFloats, mRightFloats;
-
-  void ComputeAvailSpaceRect();
-};
-
-#endif /* nsBlockBandData_h___ */
--- a/layout/generic/nsBlockDebugFlags.h
+++ b/layout/generic/nsBlockDebugFlags.h
@@ -46,13 +46,13 @@
 #undef NOISY_FLOAT                // enables debug output for float reflow (the in/out metrics for the floated block)
 #undef NOISY_FLOAT_CLEARING
 #undef NOISY_FINAL_SIZE           // enables debug output for desired width/height computation, once all children have been reflowed
 #undef NOISY_REMOVE_FRAME
 #undef NOISY_COMBINED_AREA        // enables debug output for combined area computation
 #undef NOISY_VERTICAL_MARGINS
 #undef NOISY_REFLOW_REASON        // gives a little info about why each reflow was requested
 #undef REFLOW_STATUS_COVERAGE     // I think this is most useful for printing, to see which frames return "incomplete"
-#undef NOISY_FLOATMANAGER         // enables debug output for float manager use, useful for analysing reflow of floats and positioned elements
+#undef NOISY_FLOATMANAGER         // enables debug output for float manager use, useful for analysing reflow of floats
 #undef NOISY_BLOCK_INVALIDATE     // enables debug output for all calls to invalidate
 #undef REALLY_NOISY_REFLOW        // some extra debug info
 
 #endif // nsBlockDebugFlags_h__
--- a/layout/generic/nsBlockFrame.cpp
+++ b/layout/generic/nsBlockFrame.cpp
@@ -45,17 +45,16 @@
  * rendering object for CSS display:block, inline-block, and list-item
  * boxes, also used for various anonymous boxes
  */
 
 #include "nsCOMPtr.h"
 #include "nsBlockFrame.h"
 #include "nsBlockReflowContext.h"
 #include "nsBlockReflowState.h"
-#include "nsBlockBandData.h"
 #include "nsBulletFrame.h"
 #include "nsLineBox.h"
 #include "nsInlineFrame.h"
 #include "nsLineLayout.h"
 #include "nsPlaceholderFrame.h"
 #include "nsStyleConsts.h"
 #include "nsFrameManager.h"
 #include "nsPresContext.h"
@@ -65,17 +64,17 @@
 #include "nsIFontMetrics.h"
 #include "nsHTMLParts.h"
 #include "nsGkAtoms.h"
 #include "nsIDOMEvent.h"
 #include "nsGenericHTMLElement.h"
 #include "prprf.h"
 #include "nsStyleChangeList.h"
 #include "nsFrameSelection.h"
-#include "nsSpaceManager.h"
+#include "nsFloatManager.h"
 #include "nsIntervalSet.h"
 #include "prenv.h"
 #include "plstr.h"
 #include "nsGUIEvent.h"
 #include "nsLayoutErrors.h"
 #include "nsAutoPtr.h"
 #include "nsIServiceManager.h"
 #include "nsIScrollableFrame.h"
--- a/layout/generic/nsBlockReflowContext.cpp
+++ b/layout/generic/nsBlockReflowContext.cpp
@@ -36,17 +36,17 @@
  * the terms of any one of the MPL, the GPL or the LGPL.
  *
  * ***** END LICENSE BLOCK ***** */
 
 /* class that a parent frame uses to reflow a block frame */
 
 #include "nsBlockReflowContext.h"
 #include "nsLineLayout.h"
-#include "nsSpaceManager.h"
+#include "nsFloatManager.h"
 #include "nsIFontMetrics.h"
 #include "nsPresContext.h"
 #include "nsFrameManager.h"
 #include "nsIContent.h"
 #include "nsStyleContext.h"
 #include "nsHTMLContainerFrame.h"
 #include "nsBlockFrame.h"
 #include "nsLineBox.h"
--- a/layout/generic/nsBlockReflowState.cpp
+++ b/layout/generic/nsBlockReflowState.cpp
@@ -129,17 +129,16 @@ nsBlockReflowState::nsBlockReflowState(c
   else {
     // When we are not in a paginated situation then we always use
     // an constrained height.
     SetFlag(BRS_UNCONSTRAINEDHEIGHT, PR_TRUE);
     mContentArea.height = mBottomEdge = NS_UNCONSTRAINEDSIZE;
   }
 
   mY = borderPadding.top;
-  mBand.Init(mFloatManager, mContentArea);
 
   mPrevChild = nsnull;
   mCurrentLine = aFrame->end_lines();
 
   mMinLineHeight = nsHTMLReflowState::CalcLineHeight(aReflowState.frame);
 
   // Calculate mOutsideBulletX
   GetAvailableSpace();
@@ -252,18 +251,17 @@ nsBlockReflowState::ComputeReplacedBlock
 // GetAvailableSpace has already been called.
 void
 nsBlockReflowState::ComputeBlockAvailSpace(nsIFrame* aFrame,
                                            const nsStyleDisplay* aDisplay,
                                            PRBool aBlockAvoidsFloats,
                                            nsRect& aResult)
 {
 #ifdef REALLY_NOISY_REFLOW
-  printf("CBAS frame=%p has float count %d\n", aFrame, mBand.GetFloatCount());
-  mBand.List();
+  printf("CBAS frame=%p has floats %d\n", aFrame, mBandHasFloats);
 #endif
   aResult.y = mY;
   aResult.height = GetFlag(BRS_UNCONSTRAINEDHEIGHT)
     ? NS_UNCONSTRAINEDSIZE
     : PR_MAX(0, mReflowState.availableHeight - mY);
   // mY might be greater than mBottomEdge if the block's top margin pushes
   // it off the page/column. Negative available height can confuse other code
   // and is nonsense in principle.
@@ -281,17 +279,17 @@ nsBlockReflowState::ComputeBlockAvailSpa
   // true but nsBlockFrame::BlockCanIntersectFloats is false,
   // nsBlockFrame::WidthToClearPastFloats would need to use the
   // shrink-wrap formula, max(MIN_WIDTH, min(avail width, PREF_WIDTH))
   // rather than just using MIN_WIDTH.
   NS_ASSERTION(nsBlockFrame::BlockCanIntersectFloats(aFrame) == 
                  !aBlockAvoidsFloats,
                "unexpected replaced width");
   if (!aBlockAvoidsFloats) {
-    if (mBand.GetFloatCount()) {
+    if (mBandHasFloats) {
       // Use the float-edge property to determine how the child block
       // will interact with the float.
       const nsStyleBorder* borderStyle = aFrame->GetStyleBorder();
       switch (borderStyle->mFloatEdge) {
         default:
         case NS_STYLE_FLOAT_EDGE_CONTENT:  // content and only content does runaround of floats
           // The child block will flow around the float. Therefore
           // give it all of the available space.
@@ -342,26 +340,32 @@ nsBlockReflowState::GetAvailableSpace(ns
 #ifdef DEBUG
   // Verify that the caller setup the coordinate system properly
   nscoord wx, wy;
   mFloatManager->GetTranslation(wx, wy);
   NS_ASSERTION((wx == mFloatManagerX) && (wy == mFloatManagerY),
                "bad coord system");
 #endif
 
-  mBand.GetAvailableSpace(aY - BorderPadding().top, aRelaxHeightConstraint,
-                          mAvailSpaceRect);
+  PRBool hasFloats;
+  mAvailSpaceRect = 
+    mFloatManager->GetBand(aY - BorderPadding().top, 
+                           aRelaxHeightConstraint ? nscoord_MAX
+                                                  : mContentArea.height,
+                           mContentArea.width,
+                           &hasFloats);
+  mBandHasFloats = hasFloats;
 
 #ifdef DEBUG
   if (nsBlockFrame::gNoisyReflow) {
     nsFrame::IndentBy(stdout, nsBlockFrame::gNoiseIndent);
-    printf("GetAvailableSpace: band=%d,%d,%d,%d count=%d\n",
+    printf("GetAvailableSpace: band=%d,%d,%d,%d hasfloats=%d\n",
            mAvailSpaceRect.x, mAvailSpaceRect.y,
            mAvailSpaceRect.width, mAvailSpaceRect.height,
-           mBand.GetTrapezoidCount());
+           mBandHasFloats);
   }
 #endif
 }
 
 /*
  * Reconstruct the vertical margin before the line |aLine| in order to
  * do an incremental reflow that begins with |aLine| without reflowing
  * the line before it.  |aLine| may point to the fencepost at the end of
@@ -434,17 +438,17 @@ nsBlockReflowState::RecoverFloats(nsLine
         printf("RecoverFloats: txy=%d,%d (%d,%d) ",
                tx, ty, mFloatManagerX, mFloatManagerY);
         nsFrame::ListTag(stdout, floatFrame);
         printf(" aDeltaY=%d region={%d,%d,%d,%d}\n",
                aDeltaY, fc->mRegion.x, fc->mRegion.y,
                fc->mRegion.width, fc->mRegion.height);
       }
 #endif
-      mFloatManager->AddRectRegion(floatFrame, fc->mRegion);
+      mFloatManager->AddFloat(floatFrame, fc->mRegion);
       fc = fc->Next();
     }
   } else if (aLine->IsBlock()) {
     nsBlockFrame *kid = nsLayoutUtils::GetAsBlock(aLine->mFirstChild);
     // don't recover any state inside a block that has its own space
     // manager (we don't currently have any blocks like this, though,
     // thanks to our use of extra frames for 'overflow')
     if (kid && !nsBlockFrame::BlockNeedsFloatManager(kid)) {
@@ -517,19 +521,19 @@ nsBlockReflowState::RecoverStateFrom(nsL
   }
 }
 
 PRBool
 nsBlockReflowState::IsImpactedByFloat() const
 {
 #ifdef REALLY_NOISY_REFLOW
   printf("nsBlockReflowState::IsImpactedByFloat %p returned %d\n", 
-         this, mBand.GetFloatCount());
+         this, mBandHasFloats);
 #endif
-  return mBand.GetFloatCount() > 0;
+  return mBandHasFloats;
 }
 
 
 PRBool
 nsBlockReflowState::InitFloat(nsLineLayout&       aLineLayout,
                               nsPlaceholderFrame* aPlaceholder,
                               nscoord             aAvailableWidth,
                               nsReflowStatus&     aReflowStatus)
@@ -654,17 +658,17 @@ nsBlockReflowState::AddFloat(nsLineLayou
 
 PRBool
 nsBlockReflowState::CanPlaceFloat(const nsSize& aFloatSize,
                                   PRUint8 aFloats, PRBool aForceFit)
 {
   // If the current Y coordinate is not impacted by any floats
   // then by definition the float fits.
   PRBool result = PR_TRUE;
-  if (0 != mBand.GetFloatCount()) {
+  if (mBandHasFloats) {
     // XXX We should allow overflow by up to half a pixel here (bug 21193).
     if (mAvailSpaceRect.width < aFloatSize.width) {
       // The available width is too narrow (and its been impacted by a
       // prior float)
       result = PR_FALSE;
     }
   }
 
@@ -720,17 +724,17 @@ nsBlockReflowState::CanPlaceFloat(const 
         // there is no more available space. We lose.
         result = PR_FALSE;
         break;
       }
 
       mY += mAvailSpaceRect.height;
       GetAvailableSpace(mY, aForceFit);
 
-      if (0 != mBand.GetFloatCount()) {
+      if (mBandHasFloats) {
         if ((xa < mAvailSpaceRect.x) || (xb > mAvailSpaceRect.XMost())) {
           // The float can't go here.
           result = PR_FALSE;
           break;
         }
       }
 
       // See if there is now enough height for the float.
@@ -770,17 +774,17 @@ nsBlockReflowState::FlowAndPlaceFloat(ns
   // Grab the float's display information
   const nsStyleDisplay* floatDisplay = floatFrame->GetStyleDisplay();
 
   // The float's old region, so we can propagate damage.
   nsRect oldRegion = aFloatCache->mRegion;
 
   // Enforce CSS2 9.5.1 rule [2], i.e., make sure that a float isn't
   // ``above'' another float that preceded it in the flow.
-  mY = NS_MAX(mFloatManager->GetLowestRegionTop() + BorderPadding().top, mY);
+  mY = NS_MAX(mFloatManager->GetLowestFloatTop() + BorderPadding().top, mY);
 
   // See if the float should clear any preceding floats...
   // XXX We need to mark this float somehow so that it gets reflowed
   // when floats are inserted before it.
   if (NS_STYLE_CLEAR_NONE != floatDisplay->mBreakType) {
     // XXXldb Does this handle vertical margins correctly?
     mY = ClearFloats(mY, floatDisplay->mBreakType);
   }
@@ -939,17 +943,17 @@ nsBlockReflowState::FlowAndPlaceFloat(ns
     region.width = 0;
   }
   if (region.height < 0) {
     region.height = 0;
   }
 #ifdef DEBUG
   nsresult rv =
 #endif
-  mFloatManager->AddRectRegion(floatFrame, region);
+  mFloatManager->AddFloat(floatFrame, region);
   NS_ABORT_IF_FALSE(NS_SUCCEEDED(rv), "bad float placement");
 
   // Save away the floats region in the spacemanager, after making
   // it relative to the containing block's frame instead of relative
   // to the spacemanager translation (which is inset by the
   // border+padding).
   // XXX Maybe RecoverFloats should calc/add in the borderPadding itself?
   // It's kind of confusing to have the spacemanager translation be different
@@ -968,17 +972,17 @@ nsBlockReflowState::FlowAndPlaceFloat(ns
     nscoord bottom = NS_MAX(region.YMost(), oldRegion.YMost());
     mFloatManager->IncludeInDamage(top, bottom);
   }
 
 #ifdef NOISY_FLOATMANAGER
   nscoord tx, ty;
   mFloatManager->GetTranslation(tx, ty);
   nsFrame::ListTag(stdout, mBlock);
-  printf(": FlowAndPlaceFloat: AddRectRegion: txy=%d,%d (%d,%d) {%d,%d,%d,%d}\n",
+  printf(": FlowAndPlaceFloat: AddFloat: txy=%d,%d (%d,%d) {%d,%d,%d,%d}\n",
          tx, ty, mFloatManagerX, mFloatManagerY,
          aFloatCache->mRegion.x, aFloatCache->mRegion.y,
          aFloatCache->mRegion.width, aFloatCache->mRegion.height);
 #endif
 
   // Calculate the actual origin of the float frame's border rect
   // relative to the parent block; floatX/Y must be converted from space-manager
   // coordinates to parent coordinates, and the margin must be added in
@@ -1096,17 +1100,17 @@ nsBlockReflowState::ClearFloats(nscoord 
     newY = bp.top + mFloatManager->ClearFloats(newY - bp.top, aBreakType);
   }
 
   if (aReplacedBlock) {
     for (;;) {
       GetAvailableSpace(newY, PR_FALSE);
       nsBlockFrame::ReplacedElementWidthToClear replacedWidth =
         nsBlockFrame::WidthToClearPastFloats(*this, aReplacedBlock);
-      if (mBand.GetFloatCount() == 0 ||
+      if (!mBandHasFloats ||
           PR_MAX(mAvailSpaceRect.x, replacedWidth.marginLeft) +
             replacedWidth.borderBoxWidth +
             PR_MAX(mContentArea.width -
                      PR_MIN(mContentArea.width, mAvailSpaceRect.XMost()),
                    replacedWidth.marginRight) <=
           mContentArea.width) {
         break;
       }
@@ -1119,18 +1123,18 @@ nsBlockReflowState::ClearFloats(nscoord 
           // Stop trying to clear here; we'll just get pushed to the
           // next column or page and try again there.
           break;
         }
         NS_NOTREACHED("avail space rect with zero height!");
         newY += 1;
       }
     }
-    // Restore mBand and mAvailSpaceRect to the way they were.  This may
-    // well not be needed, and we should probably come up with
+    // Restore mBandHasFloats and mAvailSpaceRect to the way they were.
+    // This may well not be needed, and we should probably come up with
     // well-defined rules about when these members are valid so that
     // it's clearly not needed.
     GetAvailableSpace();
   }
 
 #ifdef DEBUG
   if (nsBlockFrame::gNoisyReflow) {
     nsFrame::IndentBy(stdout, nsBlockFrame::gNoiseIndent);
--- a/layout/generic/nsBlockReflowState.h
+++ b/layout/generic/nsBlockReflowState.h
@@ -38,17 +38,17 @@
  *
  * ***** END LICENSE BLOCK ***** */
 
 /* state used in reflow of block frames */
 
 #ifndef nsBlockReflowState_h__
 #define nsBlockReflowState_h__
 
-#include "nsBlockBandData.h"
+#include "nsFloatManager.h"
 #include "nsLineBox.h"
 #include "nsFrameList.h"
 #include "nsBlockFrame.h"
 
   // block reflow state flags
 #define BRS_UNCONSTRAINEDHEIGHT   0x00000001
 #define BRS_ISTOPMARGINROOT       0x00000002  // Is this frame a root for top/bottom margin collapsing?
 #define BRS_ISBOTTOMMARGINROOT    0x00000004
@@ -189,17 +189,17 @@ public:
   nsBlockFrame* mBlock;
 
   nsPresContext* mPresContext;
 
   const nsHTMLReflowState& mReflowState;
 
   nsFloatManager* mFloatManager;
 
-  // The coordinates within the spacemanager where the block is being
+  // The coordinates within the float manager where the block is being
   // placed <b>after</b> taking into account the blocks border and
   // padding. This, therefore, represents the inner "content area" (in
   // spacemanager coordinates) where child frames will be placed,
   // including child blocks and floats.
   nscoord mFloatManagerX, mFloatManagerY;
 
   // XXX get rid of this
   nsReflowStatus mReflowStatus;
@@ -267,19 +267,16 @@ public:
   nsCollapsingMargin mPrevBottomMargin;
 
   // The current next-in-flow for the block. When lines are pulled
   // from a next-in-flow, this is used to know which next-in-flow to
   // pull from. When a next-in-flow is emptied of lines, we advance
   // this to the next next-in-flow.
   nsBlockFrame* mNextInFlow;
 
-  // The current band data for the current Y coordinate
-  nsBlockBandData mBand;
-
   //----------------------------------------
 
   // Temporary line-reflow state. This state is used during the reflow
   // of a given line, but doesn't have meaning before or after.
 
   // The list of floats that are "current-line" floats. These are
   // added to the line after the line has been reflowed, to keep the
   // list fiddling from being N^2.
@@ -294,16 +291,21 @@ public:
   nscoord mMinLineHeight;
 
   PRInt32 mLineNumber;
 
   PRInt16 mFlags;
  
   PRUint8 mFloatBreakType;
 
+  // The number of floats on the sides of mAvailSpaceRect, including
+  // floats that do not reduce mAvailSpaceRect because they are in the
+  // margins.
+  PRPackedBool mBandHasFloats;
+
   void SetFlag(PRUint32 aFlag, PRBool aValue)
   {
     NS_ASSERTION(aFlag<=BRS_LASTFLAG, "bad flag");
     NS_ASSERTION(aValue==PR_FALSE || aValue==PR_TRUE, "bad value");
     if (aValue) { // set flag
       mFlags |= aFlag;
     }
     else {        // unset flag
rename from layout/generic/nsSpaceManager.cpp
rename to layout/generic/nsFloatManager.cpp
--- a/layout/generic/nsSpaceManager.cpp
+++ b/layout/generic/nsFloatManager.cpp
@@ -15,83 +15,43 @@
  * The Original Code is mozilla.org code.
  *
  * The Initial Developer of the Original Code is
  * Netscape Communications Corporation.
  * Portions created by the Initial Developer are Copyright (C) 1998
  * the Initial Developer. All Rights Reserved.
  *
  * Contributor(s):
- *   Pierre Phaneuf <pp@ludusdesign.com>
+ *   L. David Baron <dbaron@dbaron.org>, Mozilla Corporation
  *
  * Alternatively, the contents of this file may be used under the terms of
  * either of the GNU General Public License Version 2 or later (the "GPL"),
  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  * in which case the provisions of the GPL or the LGPL are applicable instead
  * of those above. If you wish to allow use of your version of this file only
  * under the terms of either the GPL or the LGPL, and not to allow others to
  * use your version of this file under the terms of the MPL, indicate your
  * decision by deleting the provisions above and replace them with the notice
  * and other provisions required by the GPL or the LGPL. If you do not delete
  * the provisions above, a recipient may use your version of this file under
  * the terms of any one of the MPL, the GPL or the LGPL.
  *
  * ***** END LICENSE BLOCK ***** */
 
-/*
- * class that manages regions of 2-D space, originally designed
- * generally but actually specific to space occupied by floats
- */
+/* class that manages rules for positioning floats */
 
-#include "nsSpaceManager.h"
-#include "nsPoint.h"
-#include "nsRect.h"
-#include "nsSize.h"
-#include <stdlib.h>
-#include "nsVoidArray.h"
-#include "nsIFrame.h"
-#include "nsString.h"
+#include "nsFloatManager.h"
 #include "nsIPresShell.h"
 #include "nsMemory.h"
 #include "nsHTMLReflowState.h"
 #include "nsHashSets.h"
-#ifdef DEBUG
-#include "nsIFrameDebug.h"
-#endif
-
-/////////////////////////////////////////////////////////////////////////////
-// BandList
+#include "nsBlockDebugFlags.h"
 
 PRInt32 nsFloatManager::sCachedFloatManagerCount = 0;
-void* nsFloatManager::sCachedFloatManagers[NS_SPACE_MANAGER_CACHE_SIZE];
-
-#define NSCOORD_MIN (-2147483647 - 1) /* minimum signed value */
-
-nsFloatManager::BandList::BandList()
-  : nsFloatManager::BandRect(NSCOORD_MIN, NSCOORD_MIN, NSCOORD_MIN, NSCOORD_MIN, (nsIFrame*)nsnull)
-{
-  PR_INIT_CLIST(this);
-}
-
-void
-nsFloatManager::BandList::Clear()
-{
-  if (!IsEmpty()) {
-    BandRect* bandRect = Head();
-  
-    while (bandRect != this) {
-      BandRect* nxt = bandRect->Next();
-  
-      delete bandRect;
-      bandRect = nxt;
-    }
-  
-    PR_INIT_CLIST(this);
-  }
-}
+void* nsFloatManager::sCachedFloatManagers[NS_FLOAT_MANAGER_CACHE_SIZE];
 
 /////////////////////////////////////////////////////////////////////////////
 
 // PresShell Arena allocate callback (for nsIntervalSet use below)
 static void*
 PSArenaAllocCB(size_t aSize, void* aClosure)
 {
   return static_cast<nsIPresShell*>(aClosure)->AllocateFrame(aSize);
@@ -103,44 +63,25 @@ PSArenaFreeCB(size_t aSize, void* aPtr, 
 {
   static_cast<nsIPresShell*>(aClosure)->FreeFrame(aSize, aPtr);
 }
 
 /////////////////////////////////////////////////////////////////////////////
 // nsFloatManager
 
 nsFloatManager::nsFloatManager(nsIPresShell* aPresShell)
-  : mLowestTop(NSCOORD_MIN),
-    mFloatDamage(PSArenaAllocCB, PSArenaFreeCB, aPresShell),
-    mHaveCachedLeftYMost(PR_TRUE),
-    mHaveCachedRightYMost(PR_TRUE),
-    mMaximalLeftYMost(nscoord_MIN),
-    mMaximalRightYMost(nscoord_MIN),
-    mCachedBandPosition(nsnull)
+  : mX(0), mY(0),
+    mFloatDamage(PSArenaAllocCB, PSArenaFreeCB, aPresShell)
 {
   MOZ_COUNT_CTOR(nsFloatManager);
-  mX = mY = 0;
-  mFrameInfoMap = nsnull;
-}
-
-void
-nsFloatManager::ClearFrameInfo()
-{
-  while (mFrameInfoMap) {
-    FrameInfo*  next = mFrameInfoMap->mNext;
-    delete mFrameInfoMap;
-    mFrameInfoMap = next;
-  }
 }
 
 nsFloatManager::~nsFloatManager()
 {
   MOZ_COUNT_DTOR(nsFloatManager);
-  mBandList.Clear();
-  ClearFrameInfo();
 }
 
 // static
 void* nsFloatManager::operator new(size_t aSize) CPP_THROW_NEW
 {
   if (sCachedFloatManagerCount > 0) {
     // We have cached unused instances of this class, return a cached
     // instance in stead of always creating a new one.
@@ -156,17 +97,17 @@ void
 nsFloatManager::operator delete(void* aPtr, size_t aSize)
 {
   if (!aPtr)
     return;
   // This float manager is no longer used, if there's still room in
   // the cache we'll cache this float manager, unless the layout
   // module was already shut down.
 
-  if (sCachedFloatManagerCount < NS_SPACE_MANAGER_CACHE_SIZE &&
+  if (sCachedFloatManagerCount < NS_FLOAT_MANAGER_CACHE_SIZE &&
       sCachedFloatManagerCount >= 0) {
     // There's still space in the cache for more instances, put this
     // instance in the cache in stead of deleting it.
 
     sCachedFloatManagers[sCachedFloatManagerCount++] = aPtr;
     return;
   }
 
@@ -189,842 +130,178 @@ void nsFloatManager::Shutdown()
     if (floatManager)
       nsMemory::Free(floatManager);
   }
 
   // Disable further caching.
   sCachedFloatManagerCount = -1;
 }
 
-PRBool
-nsFloatManager::YMost(nscoord& aYMost) const
+nsRect
+nsFloatManager::GetBand(nscoord aYOffset,
+                        nscoord aMaxHeight,
+                        nscoord aContentAreaWidth,
+                        PRBool* aHasFloats) const
 {
-  PRBool result;
+  NS_ASSERTION(aMaxHeight >= 0, "unexpected max height");
+  NS_ASSERTION(aContentAreaWidth >= 0, "unexpected content area width");
 
-  if (mBandList.IsEmpty()) {
-    aYMost = 0;
-    result = PR_FALSE;
-
-  } else {
-    BandRect* lastRect = mBandList.Tail();
-
-    aYMost = lastRect->mBottom;
-    result = PR_TRUE;
+  nscoord top = aYOffset + mY;
+  if (top < nscoord_MIN) {
+    NS_NOTREACHED("bad value");
+    top = nscoord_MIN;
   }
 
-  return result;
-}
+  // If there are no floats at all, or we're below the last one, return
+  // quickly.
+  PRUint32 floatCount = mFloats.Length();
+  if (floatCount == 0 ||
+      (mFloats[floatCount-1].mLeftYMost <= top &&
+       mFloats[floatCount-1].mRightYMost <= top)) {
+    *aHasFloats = PR_FALSE;
+    return nsRect(0, aYOffset, aContentAreaWidth, aMaxHeight);
+  }
 
-/**
- * Internal function that returns the list of available and unavailable space
- * within the band
- *
- * Note: If the clip rectangle has 0 width and is aligned exactly at
- * aBand->mLeft or aBand->mRight, we count it as intersecting the band, and we
- * return an unavailable-space trapezoid for the band.  (The alternative would
- * be to return a zero-width available-space trapezoid, which would make no
- * sense.  See bug 403129)
- *
- * @param aBand the first rect in the band
- * @param aY the y-offset in world coordinates
- * @param aMaxSize the size to use to constrain the band data
- * @param aBandData the object to populate with available and unavailable space
- */
-nsresult
-nsFloatManager::GetBandAvailableSpace(const BandRect* aBand,
-                                      nscoord         aY,
-                                      const nsSize&   aMaxSize,
-                                      nsBandData&     aBandData) const
-{
-  nscoord          topOfBand = aBand->mTop;
-  nscoord          localY = aY - mY;
-  nscoord          height = PR_MIN(aBand->mBottom - aY, aMaxSize.height);
-  nsBandTrapezoid* trapezoid = aBandData.mTrapezoids;
-  nscoord          rightEdge = mX + aMaxSize.width;
-
-  // Initialize the band data
-  aBandData.mCount = 0;
-
-  // Skip any rectangles that are to the left of the local coordinate space
-  while (aBand->mTop == topOfBand) {
-    if (aBand->mRight > mX ||
-        (aMaxSize.width == 0 && aBand->mRight == mX)) {
-      break;
+  nscoord bottom;
+  if (aMaxHeight == nscoord_MAX) {
+    bottom = nscoord_MAX;
+  } else {
+    bottom = top + aMaxHeight;
+    if (bottom < top || bottom > nscoord_MAX) {
+      NS_NOTREACHED("bad value");
+      bottom = nscoord_MAX;
     }
-
-    // Get the next rect in the band
-    aBand = aBand->Next();
+  }
+  nscoord left = mX;
+  nscoord right = aContentAreaWidth + mX;
+  if (right < left) {
+    NS_NOTREACHED("bad value");
+    right = left;
   }
 
-  // This is used to track the current x-location within the band. This is in
-  // world coordinates
-  nscoord   left = mX;
-
-  // Process the remaining rectangles that are within the clip width
-  while ((aBand->mTop == topOfBand) && 
-         (aBand->mLeft < rightEdge || 
-          (aMaxSize.width == 0 && aBand->mLeft == mX))) {
-    // Compare the left edge of the occupied space with the current left
-    // coordinate
-    if (aBand->mLeft > left) {
-      // The rect is to the right of our current left coordinate, so we've
-      // found some available space
-      if (aBandData.mCount >= aBandData.mSize) {
-        // Not enough space in the array of trapezoids
-        aBandData.mCount += 2 * aBand->Length() + 2;  // estimate the number needed
-        return NS_ERROR_FAILURE;
+  // Walk backwards through the floats until we either hit the front of
+  // the list or we're above |top|.
+  PRBool haveFloats = PR_FALSE;
+  for (PRUint32 i = mFloats.Length(); i > 0; --i) {
+    const FloatInfo &fi = mFloats[i-1];
+    if (fi.mLeftYMost <= top && fi.mRightYMost <= top) {
+      // There aren't any more floats that could intersect this band.
+      break;
+    }
+    if (fi.mRect.IsEmpty()) {
+      // For compatibility, ignore floats with empty rects, even though it
+      // disagrees with the spec.  (We might want to fix this in the
+      // future, though.)
+      continue;
+    }
+    nscoord floatTop = fi.mRect.y, floatBottom = fi.mRect.YMost();
+    if (floatTop > top) {
+      // This float is below our band.  Shrink our band's height if needed.
+      if (floatTop < bottom) {
+        bottom = floatTop;
       }
-      trapezoid->mFrames = nsnull;
-
-      // Assign the trapezoid a rectangular shape. The trapezoid must be in the
-      // local coordinate space, so convert the current left coordinate
-      *trapezoid = nsRect(left - mX, localY, aBand->mLeft - left, height);
-
-      // Move to the next output rect
-      trapezoid++;
-      aBandData.mCount++;
-    }
+    } else if (floatBottom > top) {
+      // This float is in our band.
+      haveFloats = PR_TRUE;
 
-    // The rect represents unavailable space, so add another trapezoid
-    if (aBandData.mCount >= aBandData.mSize) {
-      // Not enough space in the array of trapezoids
-      aBandData.mCount += 2 * aBand->Length() + 1;  // estimate the number needed
-      return NS_ERROR_FAILURE;
-    }
-    NS_ASSERTION(aBand->mFrames.Count() > 0, "unexpected frame count");
-    trapezoid->mFrames = &aBand->mFrames;
+      // Shrink our band's height if needed.
+      if (floatBottom < bottom) {
+        bottom = floatBottom;
+      }
 
-    nscoord x = aBand->mLeft;
-    // The first band can straddle the clip rect
-    if (x < mX) {
-      // Clip the left edge
-      x = mX;
+      // Shrink our band's width if needed.
+      if (fi.mFrame->GetStyleDisplay()->mFloats == NS_STYLE_FLOAT_LEFT) {
+        // A left float.
+        nscoord rightEdge = fi.mRect.XMost();
+        if (rightEdge > left) {
+          left = rightEdge;
+        }
+      } else {
+        // A right float.
+        nscoord leftEdge = fi.mRect.x;
+        if (leftEdge < right) {
+          right = leftEdge;
+        }
+      }
     }
-
-    // Assign the trapezoid a rectangular shape. The trapezoid must be in the
-    // local coordinate space, so convert the rects's left coordinate
-    *trapezoid = nsRect(x - mX, localY, aBand->mRight - x, height);
-
-    // Move to the next output rect
-    trapezoid++;
-    aBandData.mCount++;
-
-    // Adjust our current x-location within the band
-    left = aBand->mRight;
-
-    // Move to the next rect within the band
-    aBand = aBand->Next();
   }
 
-  // No more rects left in the band. If we haven't yet reached the right edge,
-  // then all the remaining space is available
-  if (left < rightEdge || aBandData.mCount == 0) {
-    if (aBandData.mCount >= aBandData.mSize) {
-      // Not enough space in the array of trapezoids
-      aBandData.mCount++;
-      return NS_ERROR_FAILURE;
-    }
-    trapezoid->mFrames = nsnull;
+  *aHasFloats = haveFloats;
+  nscoord height = (bottom == nscoord_MAX) ? nscoord_MAX : (bottom - top);
+  return nsRect(left - mX, top - mY, right - left, height);
+}
+
+nsresult
+nsFloatManager::AddFloat(nsIFrame* aFloatFrame, const nsRect& aMarginRect)
+{
+  NS_ASSERTION(aMarginRect.width >= 0, "negative width!");
+  NS_ASSERTION(aMarginRect.height >= 0, "negative height!");
+
+  FloatInfo info(aFloatFrame, aMarginRect + nsPoint(mX, mY));
 
-    // Assign the trapezoid a rectangular shape. The trapezoid must be in the
-    // local coordinate space, so convert the current left coordinate
-    *trapezoid = nsRect(left - mX, localY, rightEdge - left, height);
-    aBandData.mCount++;
+  // Set mLeftYMost and mRightYMost.
+  if (HasAnyFloats()) {
+    FloatInfo &tail = mFloats[mFloats.Length() - 1];
+    info.mLeftYMost = tail.mLeftYMost;
+    info.mRightYMost = tail.mRightYMost;
+  } else {
+    info.mLeftYMost = nscoord_MIN;
+    info.mRightYMost = nscoord_MIN;
   }
+  PRUint8 floatStyle = aFloatFrame->GetStyleDisplay()->mFloats;
+  NS_ASSERTION(floatStyle == NS_STYLE_FLOAT_LEFT ||
+               floatStyle == NS_STYLE_FLOAT_RIGHT, "unexpected float");
+  nscoord& sideYMost = (floatStyle == NS_STYLE_FLOAT_LEFT) ? info.mLeftYMost
+                                                           : info.mRightYMost;
+  nscoord thisYMost = info.mRect.YMost();
+  if (thisYMost > sideYMost)
+    sideYMost = thisYMost;
+
+  if (!mFloats.AppendElement(info))
+    return NS_ERROR_OUT_OF_MEMORY;
 
   return NS_OK;
 }
 
 nsresult
-nsFloatManager::GetBandData(nscoord       aYOffset,
-                            const nsSize& aMaxSize,
-                            nsBandData&   aBandData) const
-{
-  NS_PRECONDITION(aBandData.mSize >= 1, "bad band data");
-  nsresult  result = NS_OK;
-
-  // Convert the y-offset to world coordinates
-  nscoord   y = mY + aYOffset;
-
-  // If there are no unavailable rects or the offset is below the bottommost
-  // band, then all the space is available
-  nscoord yMost;
-  nscoord maxHeight = aMaxSize.height == NS_UNCONSTRAINEDSIZE ? NS_UNCONSTRAINEDSIZE 
-    : PR_MAX(0, aMaxSize.height - aYOffset);
-
-  if (!YMost(yMost) || (y >= yMost)) {
-    // All the requested space is available
-    aBandData.mCount = 1;
-    aBandData.mTrapezoids[0] = nsRect(0, aYOffset, aMaxSize.width, maxHeight);
-    aBandData.mTrapezoids[0].mFrames = nsnull;
-  } else {
-    // Find the first band that contains the y-offset or is below the y-offset
-    BandRect* band = GuessBandWithTopAbove(y);
-
-    aBandData.mCount = 0;
-    while (nsnull != band) {
-      if (band->mTop > y) {
-        // The band is below the y-offset. The area between the y-offset and
-        // the top of the band is available
-        aBandData.mCount = 1;
-        aBandData.mTrapezoids[0] =
-          nsRect(0, aYOffset, aMaxSize.width, PR_MIN(band->mTop - y, maxHeight));
-        aBandData.mTrapezoids[0].mFrames = nsnull;
-        break;
-      } else if (y < band->mBottom) {
-        // The band contains the y-offset. Return a list of available and
-        // unavailable rects within the band
-        return GetBandAvailableSpace(band, y, nsSize(aMaxSize.width, maxHeight), aBandData);
-      } else {
-        // Skip to the next band
-        band = GetNextBand(band);
-      }
-    }
-  }
-
-  NS_POSTCONDITION(aBandData.mCount > 0, "unexpected band data count");
-  return result;
-}
-
-/**
- * Skips to the start of the next band.
- *
- * @param aBandRect A rect within the band
- * @returns The start of the next band, or nsnull of this is the last band.
- */
-nsFloatManager::BandRect*
-nsFloatManager::GetNextBand(const BandRect* aBandRect) const
-{
-  nscoord topOfBand = aBandRect->mTop;
-
-  aBandRect = aBandRect->Next();
-  while (aBandRect != &mBandList) {
-    // Check whether this rect is part of the same band
-    if (aBandRect->mTop != topOfBand) {
-      // We found the start of the next band
-      return (BandRect*)aBandRect;
-    }
-
-    aBandRect = aBandRect->Next();
-  }
-
-  // No bands left
-  return nsnull;
-}
-
-/**
- * Skips to the start of the previous band.
- *
- * @param aBandRect The first rect within a band
- * @returns The start of the previous band, or nsnull of this is the first band.
- */
-nsFloatManager::BandRect*
-nsFloatManager::GetPrevBand(const BandRect* aBandRect) const
-{
-  NS_ASSERTION(aBandRect->Prev() == &mBandList ||
-               aBandRect->Prev()->mBottom <= aBandRect->mTop,
-               "aBandRect should be first rect within its band");
-
-  BandRect* prev = aBandRect->Prev();
-  nscoord topOfBand = prev->mTop;
-
-  while (prev != &mBandList) {
-    // Check whether the prev rect is part of the same band
-    if (prev->mTop != topOfBand) {
-      // We found the beginning of this band
-      return (BandRect*)aBandRect;
-    }
-
-    aBandRect = prev;
-    prev = aBandRect->Prev();
-  }
-
-  // No bands left
-  return nsnull;
-}
-
-/**
- * Divides the current band into two vertically
- *
- * @param aBandRect the first rect in the band
- * @param aBottom where to split the band. This becomes the bottom of the top
- *          part
- */
-void
-nsFloatManager::DivideBand(BandRect* aBandRect, nscoord aBottom)
-{
-  NS_PRECONDITION(aBottom < aBandRect->mBottom, "bad height");
-  nscoord   topOfBand = aBandRect->mTop;
-  BandRect* nextBand = GetNextBand(aBandRect);
-
-  if (nsnull == nextBand) {
-    nextBand = (BandRect*)&mBandList;
-  }
-
-  while (topOfBand == aBandRect->mTop) {
-    // Split the band rect into two vertically
-    BandRect* bottomBandRect = aBandRect->SplitVertically(aBottom);
-
-    // Insert the new bottom part
-    nextBand->InsertBefore(bottomBandRect);
-
-    // Move to the next rect in the band
-    aBandRect = aBandRect->Next();
-  }
-}
-
-PRBool
-nsFloatManager::CanJoinBands(BandRect* aBand, BandRect* aPrevBand)
-{
-  PRBool  result;
-  nscoord topOfBand = aBand->mTop;
-  nscoord topOfPrevBand = aPrevBand->mTop;
-
-  // The bands can be joined if:
-  // - they're adjacent
-  // - they have the same number of rects
-  // - each rect has the same left and right edge as its corresponding rect, and
-  //   the rects are occupied by the same frames
-  if (aPrevBand->mBottom == aBand->mTop) {
-    // Compare each of the rects in the two bands
-    while (PR_TRUE) {
-      if ((aBand->mLeft != aPrevBand->mLeft) || (aBand->mRight != aPrevBand->mRight)) {
-        // The rects have different edges
-        result = PR_FALSE;
-        break;
-      }
-
-      if (!aBand->HasSameFrameList(aPrevBand)) {
-        // The rects are occupied by different frames
-        result = PR_FALSE;
-        break;
-      }
-
-      // Move to the next rects within the bands
-      aBand = aBand->Next();
-      aPrevBand = aPrevBand->Next();
-
-      // Have we reached the end of either band?
-      PRBool  endOfBand = aBand->mTop != topOfBand;
-      PRBool  endOfPrevBand = aPrevBand->mTop != topOfPrevBand;
-
-      if (endOfBand || endOfPrevBand) {
-        result = endOfBand & endOfPrevBand;
-        break;  // all done
-      }
-    }
-
-  } else {
-    // The bands aren't adjacent
-    result = PR_FALSE;
-  }
-
-  return result;
-}
-
-/**
- * Tries to join the two adjacent bands. Returns PR_TRUE if successful and
- * PR_FALSE otherwise
- *
- * If the two bands are joined, the previous band is the band that's deleted
- */
-PRBool
-nsFloatManager::JoinBands(BandRect* aBand, BandRect* aPrevBand)
-{
-  if (CanJoinBands(aBand, aPrevBand)) {
-    BandRect* startOfNextBand = aBand;
-    // We're going to be removing aPrevBand, so if mCachedBandPosition points
-    // to it just advance it to startOfNextBand.
-    if (mCachedBandPosition == aPrevBand) {
-      SetCachedBandPosition(startOfNextBand);
-    }
-
-    while (aPrevBand != startOfNextBand) {
-      // Adjust the top of the band we're keeping, and then move to the next
-      // rect within the band
-      aBand->mTop = aPrevBand->mTop;
-      aBand = aBand->Next();
-
-      // Delete the rect from the previous band
-      BandRect* next = aPrevBand->Next();
-
-      NS_ASSERTION(mCachedBandPosition != aPrevBand,
-                   "Removing mCachedBandPosition BandRect?");
-      aPrevBand->Remove();
-      delete aPrevBand;
-      aPrevBand = next;
-    }
-
-    return PR_TRUE;
-  }
-
-  return PR_FALSE;
-}
-
-/**
- * Adds a new rect to a band.
- *
- * @param aBand the first rect in the band
- * @param aBandRect the band rect to add to the band
- */
-void
-nsFloatManager::AddRectToBand(BandRect* aBand, BandRect* aBandRect)
+nsFloatManager::RemoveTrailingRegions(nsIFrame* aFrameList)
 {
-  NS_PRECONDITION((aBand->mTop == aBandRect->mTop) &&
-                  (aBand->mBottom == aBandRect->mBottom), "bad band");
-  NS_PRECONDITION(1 == aBandRect->mFrames.Count(), "shared band rect");
-  nscoord topOfBand = aBand->mTop;
-
-  // Figure out where in the band horizontally to insert the rect
-  do {
-    // Compare the left edge of the new rect with the left edge of the existing
-    // rect
-    if (aBandRect->mLeft < aBand->mLeft) {
-      // The new rect's left edge is to the left of the existing rect's left edge.
-      // Could be any of these cases (N is new rect, E is existing rect):
-      //
-      //   Case 1: left-of      Case 2: overlaps     Case 3: N.contains(E)
-      //   ---------------      ----------------     ---------------------
-      //   +-----+ +-----+      +-----+              +---------+
-      //   |  N  | |  E  |      |  N  |              |    N    |
-      //   +-----+ +-----+      +-----+              +---------+
-      //                           +-----+              +---+
-      //                           |  E  |              | E |
-      //                           +-----+              +---+
-      //
-      // Do the two rectangles overlap?
-      if (aBandRect->mRight <= aBand->mLeft) {
-        // No, the new rect is completely to the left of the existing rect
-        // (case #1). Insert a new rect
-        aBand->InsertBefore(aBandRect);
-        if (mCachedBandPosition == aBand) {
-          SetCachedBandPosition(aBandRect);
-        }
-        return;
-      }
-
-      // Yes, they overlap. Compare the right edges.
-      if (aBandRect->mRight > aBand->mRight) {
-        // The new rect's right edge is to the right of the existing rect's
-        // right edge (case #3). Split the new rect
-        BandRect* r1 = aBandRect->SplitHorizontally(aBand->mLeft);
-
-        // Insert the part of the new rect that's to the left of the existing
-        // rect as a new band rect
-        aBand->InsertBefore(aBandRect);
-        if (mCachedBandPosition == aBand) {
-          SetCachedBandPosition(aBandRect);
-        }
-
-        // Continue below with the part that overlaps the existing rect
-        aBandRect = r1;
-
-      } else {
-        if (aBand->mRight > aBandRect->mRight) {
-          // The existing rect extends past the new rect (case #2). Split the
-          // existing rect
-          BandRect* r1 = aBand->SplitHorizontally(aBandRect->mRight);
-
-          // Insert the new right half of the existing rect
-          aBand->InsertAfter(r1);
-        }
-
-        // Insert the part of the new rect that's to the left of the existing
-        // rect
-        aBandRect->mRight = aBand->mLeft;
-        aBand->InsertBefore(aBandRect);
-
-        if (mCachedBandPosition == aBand) {
-          SetCachedBandPosition(aBandRect);
-        }
-
-        // Mark the existing rect as shared
-        aBand->AddFrame(aBandRect->FrameAt(0));
-        return;
-      }
-    }
-      
-    if (aBandRect->mLeft > aBand->mLeft) {
-      // The new rect's left edge is to the right of the existing rect's left
-      // edge. Could be any one of these cases:
-      //
-      //   Case 4: right-of    Case 5: overlaps     Case 6: E.Contains(N)
-      //   ---------------    ----------------     ---------------------
-      //   +-----+ +-----+    +-----+              +------------+
-      //   |  E  | |  N  |    |  E  |              |      E     |
-      //   +-----+ +-----+    +-----+              +------------+
-      //                         +-----+              +-----+
-      //                         |  N  |              |  N  |
-      //                         +-----+              +-----+
-      //
-      if (aBandRect->mLeft >= aBand->mRight) {
-        // The new rect is to the right of the existing rect (case #4), so move
-        // to the next rect in the band
-        aBand = aBand->Next();
-        continue;
-      }
-
-      // The rects overlap, so divide the existing rect into two rects: the
-      // part to the left of the new rect, and the part that overlaps
-      BandRect* r1 = aBand->SplitHorizontally(aBandRect->mLeft);
-
-      // Insert the new right half of the existing rect, and make it the current
-      // rect
-      aBand->InsertAfter(r1);
-      aBand = r1;
-    }
-
-    // At this point the left edge of the new rect is the same as the left edge
-    // of the existing rect
-    NS_ASSERTION(aBandRect->mLeft == aBand->mLeft, "unexpected rect");
-
-    // Compare which rect is wider, the new rect or the existing rect
-    if (aBand->mRight > aBandRect->mRight) {
-      // The existing rect is wider (case #6). Divide the existing rect into
-      // two rects: the part that overlaps, and the part to the right of the
-      // new rect
-      BandRect* r1 = aBand->SplitHorizontally(aBandRect->mRight);
-
-      // Insert the new right half of the existing rect
-      aBand->InsertAfter(r1);
-
-      // Mark the overlap as being shared
-      aBand->AddFrame(aBandRect->FrameAt(0));
-
-      // We no longer need aBandRect, since the area it covers is covered by
-      // the part of aBand that SplitHorizontally left in place.  Just delete
-      // it.
-      delete aBandRect;
-      return;
-
-    } else {
-      // Indicate the frames share the existing rect
-      aBand->AddFrame(aBandRect->FrameAt(0));
-
-      if (aBand->mRight == aBandRect->mRight) {
-        // The new and existing rect have the same right edge. We're all done,
-        // and the new band rect is no longer needed
-        delete aBandRect;
-        return;
-      } else {
-        // The new rect is wider than the existing rect (cases #5). Set the
-        // new rect to be the overhang, and move to the next rect within the band
-        aBandRect->mLeft = aBand->mRight;
-        aBand = aBand->Next();
-        continue;
-      }
-    }
-  } while (aBand->mTop == topOfBand);
-
-  // Insert a new rect.  This is an insertion at the _end_ of the band, so we
-  // absolutely do not want to set mCachedBandPosition to aBandRect here.
-  aBand->InsertBefore(aBandRect);
-}
-
-// When comparing a rect to a band there are seven cases to consider.
-// 'R' is the rect and 'B' is the band.
-//
-//      Case 1              Case 2              Case 3              Case 4
-//      ------              ------              ------              ------
-// +-----+             +-----+                      +-----+             +-----+
-// |  R  |             |  R  |  +-----+    +-----+  |     |             |     |
-// +-----+             +-----+  |     |    |  R  |  |  B  |             |  B  |
-//          +-----+             |  B  |    +-----+  |     |    +-----+  |     |
-//          |     |             |     |             +-----+    |  R  |  +-----+
-//          |  B  |             +-----+                        +-----+
-//          |     |
-//          +-----+
-//
-//
-//
-//      Case 5              Case 6              Case 7
-//      ------              ------              ------
-//          +-----+    +-----+  +-----+    +-----+
-//          |     |    |  R  |  |  B  |    |     |  +-----+
-//          |  B  |    +-----+  +-----+    |  R  |  |  B  |
-//          |     |                        |     |  +-----+
-//          +-----+                        +-----+
-// +-----+
-// |  R  |
-// +-----+
-//
-void
-nsFloatManager::InsertBandRect(BandRect* aBandRect)
-{
-  // If there are no existing bands or this rect is below the bottommost
-  // band, then add a new band
-  nscoord yMost;
-  if (!YMost(yMost) || (aBandRect->mTop >= yMost)) {
-    mBandList.Append(aBandRect);
-    SetCachedBandPosition(aBandRect);
-    return;
+  if (!aFrameList) {
+    return NS_OK;
   }
-
-  // Examine each band looking for a band that intersects this rect
-  // First guess a band whose top is above aBandRect->mTop.  We know
-  // aBandRect won't overlap any bands before that one.
-  BandRect* band = GuessBandWithTopAbove(aBandRect->mTop);
-
-  while (nsnull != band) {
-    // Compare the top edge of this rect with the top edge of the band
-    if (aBandRect->mTop < band->mTop) {
-      // The top edge of the rect is above the top edge of the band.
-      // Is there any overlap?
-      if (aBandRect->mBottom <= band->mTop) {
-        // Case #1. This rect is completely above the band, so insert a
-        // new band before the current band
-        band->InsertBefore(aBandRect);
-        SetCachedBandPosition(aBandRect);
-        break;  // we're all done
-      }
-
-      // Case #2 and case #7. Divide this rect, creating a new rect for
-      // the part that's above the band
-      BandRect* bandRect1 = new BandRect(aBandRect->mLeft, aBandRect->mTop,
-                                         aBandRect->mRight, band->mTop,
-                                         aBandRect->mFrames);
-
-      // Insert bandRect1 as a new band
-      band->InsertBefore(bandRect1);
-
-      // Modify this rect to exclude the part above the band
-      aBandRect->mTop = band->mTop;
-
-    } else if (aBandRect->mTop > band->mTop) {
-      // The top edge of the rect is below the top edge of the band. Is there
-      // any overlap?
-      if (aBandRect->mTop >= band->mBottom) {
-        // Case #5. This rect is below the current band. Skip to the next band
-        band = GetNextBand(band);
-        continue;
-      }
-
-      // Case #3 and case #4. Divide the current band into two bands with the
-      // top band being the part that's above the rect
-      DivideBand(band, aBandRect->mTop);
-
-      // Skip to the bottom band that we just created
-      band = GetNextBand(band);
-    }
-
-    // At this point the rect and the band should have the same y-offset
-    NS_ASSERTION(aBandRect->mTop == band->mTop, "unexpected band");
-
-    // Is the band higher than the rect?
-    if (band->mBottom > aBandRect->mBottom) {
-      // Divide the band into two bands with the top band the same height
-      // as the rect
-      DivideBand(band, aBandRect->mBottom);
-    }
-
-    if (aBandRect->mBottom == band->mBottom) {
-      // Add the rect to the band
-      SetCachedBandPosition(band);  // Do this before AddRectToBand
-      AddRectToBand(band, aBandRect);
-      break;
-
-    } else {
-      // Case #4 and case #7. The rect contains the band vertically. Divide
-      // the rect, creating a new rect for the part that overlaps the band
-      BandRect* bandRect1 = new BandRect(aBandRect->mLeft, aBandRect->mTop,
-                                         aBandRect->mRight, band->mBottom,
-                                         aBandRect->mFrames);
-
-      // Add bandRect1 to the band
-      AddRectToBand(band, bandRect1);
-
-      // Modify aBandRect to be the part below the band
-      aBandRect->mTop = band->mBottom;
-
-      // Continue with the next band
-      band = GetNextBand(band);
-      if (nsnull == band) {
-        // Append a new bottommost band
-        mBandList.Append(aBandRect);
-        SetCachedBandPosition(aBandRect);
-        break;
-      }
-    }
-  }
-}
-
-nsresult
-nsFloatManager::AddRectRegion(nsIFrame* aFrame, const nsRect& aUnavailableSpace)
-{
-  NS_PRECONDITION(nsnull != aFrame, "null frame");
-
-  // Convert the frame to world coordinates
-  nsRect  rect(aUnavailableSpace.x + mX, aUnavailableSpace.y + mY,
-               aUnavailableSpace.width, aUnavailableSpace.height);
-
-  if (rect.y > mLowestTop)
-    mLowestTop = rect.y;
-
-  // Create a frame info structure
-  FrameInfo* frameInfo = CreateFrameInfo(aFrame, rect);
-  if (nsnull == frameInfo) {
-    return NS_ERROR_OUT_OF_MEMORY;
-  }
-
-  if (aUnavailableSpace.IsEmpty())
-    return NS_OK;
-
-  // Allocate a band rect
-  BandRect* bandRect = new BandRect(rect.x, rect.y, 
-                                    PR_MIN(rect.XMost(), nscoord_MAX),
-                                    PR_MIN(rect.YMost(), nscoord_MAX),
-                                    aFrame);
-  if (nsnull == bandRect) {
-    return NS_ERROR_OUT_OF_MEMORY;
-  }
-
-  // Insert the band rect
-  InsertBandRect(bandRect);
-  return NS_OK;
-}
-
-nsresult
-nsFloatManager::RemoveTrailingRegions(nsIFrame* aFrameList) {
+  // This could be a good bit simpler if we could guarantee that the
+  // floats given were at the end of our list, so we could just search
+  // for the head of aFrameList.  (But we can't;
+  // layout/reftests/bugs/421710-1.html crashes.)
   nsVoidHashSet frameSet;
 
   frameSet.Init(1);
   for (nsIFrame* f = aFrameList; f; f = f->GetNextSibling()) {
     frameSet.Put(f);
   }
 
-  // Pop frame regions off as long as they're in the set of frames to
-  // remove
-  while (mFrameInfoMap && frameSet.Contains(mFrameInfoMap->mFrame)) {
-    RemoveRegion(mFrameInfoMap->mFrame);
+  PRUint32 newLength = mFloats.Length();
+  while (newLength > 0) {
+    if (!frameSet.Contains(mFloats[newLength - 1].mFrame)) {
+      break;
+    }
+    --newLength;
   }
+  mFloats.RemoveElementsAt(newLength, mFloats.Length() - newLength);
 
 #ifdef DEBUG
-  for (FrameInfo* frameInfo = mFrameInfoMap; frameInfo;
-       frameInfo = frameInfo->mNext) {
-    NS_ASSERTION(!frameSet.Contains(frameInfo->mFrame),
+  for (PRUint32 i = 0; i < mFloats.Length(); ++i) {
+    NS_ASSERTION(!frameSet.Contains(mFloats[i].mFrame),
                  "Frame region deletion was requested but we couldn't delete it");
   }
 #endif
 
   return NS_OK;
 }
 
-nsresult
-nsFloatManager::RemoveRegion(nsIFrame* aFrame)
-{
-  // Get the frame info associated with aFrame
-  FrameInfo*  frameInfo = GetFrameInfoFor(aFrame);
-
-  if (nsnull == frameInfo) {
-    NS_WARNING("no region associated with aFrame");
-    return NS_ERROR_INVALID_ARG;
-  }
-
-  if (!frameInfo->mRect.IsEmpty()) {
-    NS_ASSERTION(!mBandList.IsEmpty(), "no bands");
-    BandRect* band = mBandList.Head();
-    BandRect* prevBand = nsnull;
-    PRBool    prevFoundMatchingRect = PR_FALSE;
-
-    // Iterate each band looking for rects tagged with aFrame
-    while (nsnull != band) {
-      BandRect* rect = band;
-      BandRect* prevRect = nsnull;
-      nscoord   topOfBand = band->mTop;
-      PRBool    foundMatchingRect = PR_FALSE;
-      PRBool    prevIsSharedRect = PR_FALSE;
-
-      // Iterate each rect in the band
-      do {
-        PRBool  isSharedRect = PR_FALSE;
-
-        if (rect->IsOccupiedBy(aFrame)) {
-          // Remember that we found a matching rect in this band
-          foundMatchingRect = PR_TRUE;
-
-          if (rect->mFrames.Count() > 1) {
-            // The band rect is occupied by more than one frame
-            rect->mFrames.RemoveElement(aFrame);
-
-            // Remember that this rect was being shared by more than one frame
-            // including aFrame
-            isSharedRect = PR_TRUE;
-          } else {
-            // The rect isn't shared so just delete it
-            BandRect* next = rect->Next();
-            rect->Remove();
-            if (rect == band) {
-              // The rect we're deleting is the start of the band
-              if (topOfBand == next->mTop) {
-                band = next;
-              } else {
-                band = nsnull;
-              }
-              if (mCachedBandPosition == rect) {
-                SetCachedBandPosition(band);
-              }                
-            }
-            delete rect;
-            rect = next;
-
-            // We don't need to try and coalesce adjacent rects in this case
-            prevRect = nsnull;
-            prevIsSharedRect = PR_FALSE;
-            continue;
-          }
-        }
-           
-        // If we found a shared rect occupied by aFrame, then we need to try
-        // and coalesce adjacent rects
-        if (prevIsSharedRect || (isSharedRect && (nsnull != prevRect))) {
-          NS_ASSERTION(nsnull != prevRect, "no previous rect");
-          if ((prevRect->mRight == rect->mLeft) && (prevRect->HasSameFrameList(rect))) {
-            // Modify the current rect's left edge, and delete the previous rect
-            rect->mLeft = prevRect->mLeft;
-            prevRect->Remove();
-            if (prevRect == band) {
-              // the rect we're deleting is the start of the band
-              band = rect;
-              if (mCachedBandPosition == prevRect) {
-                SetCachedBandPosition(band);
-              }
-            }
-            delete prevRect;
-          }
-        }
-
-        // Get the next rect in the band
-        prevRect = rect;
-        prevIsSharedRect = isSharedRect;
-        rect = rect->Next();
-      } while (rect->mTop == topOfBand);
-
-      if (nsnull != band) {
-        // If we found a rect occupied by aFrame in this band or the previous band
-        // then try to join the two bands
-        if ((nsnull != prevBand) && (foundMatchingRect || prevFoundMatchingRect)) {
-          // Try and join this band with the previous band
-          JoinBands(band, prevBand);
-        }
-      }
-
-      // Move to the next band
-      prevFoundMatchingRect = foundMatchingRect;
-      prevBand = band;
-      band = (rect == &mBandList) ? nsnull : rect;
-      if (!mCachedBandPosition) {
-        SetCachedBandPosition(band);
-      }
-    }
-  }
-
-  DestroyFrameInfo(frameInfo);
-  return NS_OK;
-}
-
 void
 nsFloatManager::PushState(SavedState* aState)
 {
   NS_PRECONDITION(aState, "Need a place to save state");
 
   // This is a cheap push implementation, which
   // only saves the (x,y) and last frame in the mFrameInfoMap
   // which is enough info to get us back to where we should be
@@ -1039,403 +316,114 @@ nsFloatManager::PushState(SavedState* aS
   // since that could lead to bugs where damage is missed/dropped when
   // we move from position A to B (during the intermediate incremental
   // reflow mentioned above) and then from B to C during the subsequent
   // reflow. In the typical case A and C will be the same, but not always.
   // Allowing mFloatDamage to accumulate the damage incurred during both
   // reflows ensures that nothing gets missed.
   aState->mX = mX;
   aState->mY = mY;
-  aState->mLowestTop = mLowestTop;
-  aState->mHaveCachedLeftYMost = mHaveCachedLeftYMost;
-  aState->mHaveCachedRightYMost = mHaveCachedRightYMost;
-  aState->mMaximalLeftYMost = mMaximalLeftYMost;
-  aState->mMaximalRightYMost = mMaximalRightYMost;
-
-  if (mFrameInfoMap) {
-    aState->mLastFrame = mFrameInfoMap->mFrame;
-  } else {
-    aState->mLastFrame = nsnull;
-  }
+  aState->mFloatInfoCount = mFloats.Length();
 }
 
 void
 nsFloatManager::PopState(SavedState* aState)
 {
   NS_PRECONDITION(aState, "No state to restore?");
 
-  // This is a quick and dirty pop implementation, to
-  // match the current implementation of PushState(). The
-  // idea here is to remove any frames that have been added
-  // to the mFrameInfoMap since the last call to PushState().
-
-  // Say we don't have cached left- and right-YMost, so that we don't
-  // try to check for it in RemoveRegion.  We'll restore these from
-  // the state anyway.
-  mHaveCachedLeftYMost = mHaveCachedRightYMost = PR_FALSE;
-
-  // mFrameInfoMap is LIFO so keep removing what it points
-  // to until we hit mLastFrame.
-  while (mFrameInfoMap && mFrameInfoMap->mFrame != aState->mLastFrame) {
-    RemoveRegion(mFrameInfoMap->mFrame);
-  }
-
-  // If we trip this assertion it means that someone added
-  // PushState()/PopState() calls around code that actually
-  // removed mLastFrame from mFrameInfoMap, which means our
-  // state is now out of sync with what we thought it should be.
-
-  NS_ASSERTION(((aState->mLastFrame && mFrameInfoMap) ||
-               (!aState->mLastFrame && !mFrameInfoMap)),
-               "Unexpected outcome!");
-
   mX = aState->mX;
   mY = aState->mY;
-  mLowestTop = aState->mLowestTop;
-  mHaveCachedLeftYMost = aState->mHaveCachedLeftYMost;
-  mHaveCachedRightYMost = aState->mHaveCachedRightYMost;
-  mMaximalLeftYMost = aState->mMaximalLeftYMost;
-  mMaximalRightYMost = aState->mMaximalRightYMost;
+
+  NS_ASSERTION(aState->mFloatInfoCount <= mFloats.Length(),
+               "somebody misused PushState/PopState");
+  mFloats.RemoveElementsAt(aState->mFloatInfoCount,
+                           mFloats.Length() - aState->mFloatInfoCount);
 }
 
 nscoord
-nsFloatManager::GetLowestRegionTop()
+nsFloatManager::GetLowestFloatTop() const
 {
-  if (mLowestTop == NSCOORD_MIN)
-    return mLowestTop;
-  return mLowestTop - mY;
+  if (!HasAnyFloats()) {
+    return nscoord_MIN;
+  }
+  return mFloats[mFloats.Length() - 1].mRect.y - mY;
 }
 
 #ifdef DEBUG
 void
-DebugListFloatManager(nsFloatManager *aFloatManager)
+DebugListFloatManager(const nsFloatManager *aFloatManager)
 {
   aFloatManager->List(stdout);
 }
 
 nsresult
-nsFloatManager::List(FILE* out)
+nsFloatManager::List(FILE* out) const
 {
-  nsAutoString tmp;
-
-  fprintf(out, "FloatManager@%p", this);
-  fprintf(out, " xy=%d,%d <\n", mX, mY);
-  if (mBandList.IsEmpty()) {
-    fprintf(out, "  no bands\n");
-  }
-  else {
-    BandRect* band = mBandList.Head();
-    do {
-      PRInt32 const n = band->mFrames.Count();
-      fprintf(out, "  left=%d top=%d right=%d bottom=%d count=%d frames=",
-              band->mLeft, band->mTop, band->mRight, band->mBottom, n);
+  if (!HasAnyFloats())
+    return NS_OK;
 
-      for (PRInt32 i = 0; i < n; i++) {
-        nsIFrame* frame = (nsIFrame*)band->mFrames.FastElementAt(i);
-        if (frame) {
-          nsIFrameDebug*  frameDebug;
+  for (PRUint32 i = 0; i < mFloats.Length(); ++i) {
+    const FloatInfo &fi = mFloats[i];
+    printf("Float %u: frame=%p rect={%d,%d,%d,%d} ymost={l:%d, r:%d}\n",
+           i, static_cast<void*>(fi.mFrame),
+           fi.mRect.x, fi.mRect.y, fi.mRect.width, fi.mRect.height,
+           fi.mLeftYMost, fi.mRightYMost);
+  }
 
-		  if (NS_SUCCEEDED(frame->QueryInterface(NS_GET_IID(nsIFrameDebug), (void**)&frameDebug))) {
-            frameDebug->GetFrameName(tmp);
-            fputs(NS_LossyConvertUTF16toASCII(tmp).get(), out);
-            fprintf(out, "@%p ", frame);
-          }
-        }
-      }
-      fprintf(out, "\n");
-      band = band->Next();
-    } while (band != mBandList.Head());
-  }
-  fprintf(out, ">\n");
   return NS_OK;
 }
 #endif
 
-nsFloatManager::FrameInfo*
-nsFloatManager::GetFrameInfoFor(nsIFrame* aFrame)
-{
-  FrameInfo*  result = nsnull;
-
-  for (result = mFrameInfoMap; result; result = result->mNext) {
-    if (result->mFrame == aFrame) {
-      break;
-    }
-  }
-
-  return result;
-}
-
-nsFloatManager::FrameInfo*
-nsFloatManager::CreateFrameInfo(nsIFrame* aFrame, const nsRect& aRect)
+nscoord
+nsFloatManager::ClearFloats(nscoord aY, PRUint8 aBreakType) const
 {
-  FrameInfo*  frameInfo = new FrameInfo(aFrame, aRect);
-
-  if (frameInfo) {
-    // Link it into the list
-    frameInfo->mNext = mFrameInfoMap;
-    mFrameInfoMap = frameInfo;
-
-    // Optimize for the common case case when the frame being added is
-    // likely to be near the bottom.
-    nscoord ymost = aRect.YMost();
-    PRUint8 floatType = aFrame->GetStyleDisplay()->mFloats;
-    if (mHaveCachedLeftYMost && ymost > mMaximalLeftYMost &&
-        floatType == NS_STYLE_FLOAT_LEFT) {
-      mMaximalLeftYMost = ymost;
-    }
-    else if (mHaveCachedRightYMost && ymost > mMaximalRightYMost &&
-             floatType == NS_STYLE_FLOAT_RIGHT) {
-      mMaximalRightYMost = ymost;
-    }
-  }
-  return frameInfo;
-}
-
-void
-nsFloatManager::DestroyFrameInfo(FrameInfo* aFrameInfo)
-{
-  // See if it's at the head of the list
-  if (mFrameInfoMap == aFrameInfo) {
-    mFrameInfoMap = aFrameInfo->mNext;
-
-  } else {
-    FrameInfo*  prev;
-    
-    // Find the previous node in the list
-    for (prev = mFrameInfoMap; prev && (prev->mNext != aFrameInfo); prev = prev->mNext) {
-      ;
-    }
-
-    // Disconnect it from the list
-    NS_ASSERTION(prev, "element not in list");
-    if (prev) {
-      prev->mNext = aFrameInfo->mNext;
-    }
+  if (!HasAnyFloats()) {
+    return aY;
   }
 
-  // Optimize for the case when the frame being removed is likely to be near
-  // the bottom, but do nothing if we have neither cached value -- that case is
-  // likely to be hit from PopState().
-  if (mHaveCachedLeftYMost || mHaveCachedRightYMost) {
-    PRUint8 floatType = aFrameInfo->mFrame->GetStyleDisplay()->mFloats;
-    if (floatType == NS_STYLE_FLOAT_LEFT) {
-      mHaveCachedLeftYMost = PR_FALSE;
-    }
-    else {
-      NS_ASSERTION(floatType == NS_STYLE_FLOAT_RIGHT, "Unexpected float type");
-      mHaveCachedRightYMost = PR_FALSE;
-    }
-  }
-
-  delete aFrameInfo;
-}
-
-nscoord
-nsFloatManager::ClearFloats(nscoord aY, PRUint8 aBreakType)
-{
   nscoord bottom = aY + mY;
 
-  if ((!mHaveCachedLeftYMost && aBreakType != NS_STYLE_CLEAR_RIGHT) ||
-      (!mHaveCachedRightYMost && aBreakType != NS_STYLE_CLEAR_LEFT)) {
-    // Recover our maximal YMost values.  Might need both if this is a
-    // NS_STYLE_CLEAR_LEFT_AND_RIGHT
-    nscoord maximalLeftYMost = mHaveCachedLeftYMost ? mMaximalLeftYMost : nscoord_MIN;
-    nscoord maximalRightYMost = mHaveCachedRightYMost ? mMaximalRightYMost : nscoord_MIN;
-
-    // Optimize for most floats not being near the bottom
-    for (FrameInfo *frame = mFrameInfoMap; frame; frame = frame->mNext) {
-      nscoord ymost = frame->mRect.YMost();
-      if (ymost > maximalLeftYMost) {
-        if (frame->mFrame->GetStyleDisplay()->mFloats == NS_STYLE_FLOAT_LEFT) {
-          NS_ASSERTION(!mHaveCachedLeftYMost, "Shouldn't happen");
-          maximalLeftYMost = ymost;
-          // No need to compare to the right ymost
-          continue;
-        }
-      }
-
-      if (ymost > maximalRightYMost) {
-        if (frame->mFrame->GetStyleDisplay()->mFloats == NS_STYLE_FLOAT_RIGHT) {
-          NS_ASSERTION(!mHaveCachedRightYMost, "Shouldn't happen");
-          maximalRightYMost = ymost;
-        }
-      }
-    }
-
-    mMaximalLeftYMost = maximalLeftYMost;
-    mMaximalRightYMost = maximalRightYMost;
-    mHaveCachedRightYMost = mHaveCachedLeftYMost = PR_TRUE;
-  }
-  
+  const FloatInfo &tail = mFloats[mFloats.Length() - 1];
   switch (aBreakType) {
     case NS_STYLE_CLEAR_LEFT_AND_RIGHT:
-      NS_ASSERTION(mHaveCachedLeftYMost && mHaveCachedRightYMost,
-                   "Need cached values!");
-      bottom = PR_MAX(bottom, mMaximalLeftYMost);
-      bottom = PR_MAX(bottom, mMaximalRightYMost);
+      bottom = PR_MAX(bottom, tail.mLeftYMost);
+      bottom = PR_MAX(bottom, tail.mRightYMost);
       break;
     case NS_STYLE_CLEAR_LEFT:
-      NS_ASSERTION(mHaveCachedLeftYMost, "Need cached value!");
-      bottom = PR_MAX(bottom, mMaximalLeftYMost);
+      bottom = PR_MAX(bottom, tail.mLeftYMost);
       break;
     case NS_STYLE_CLEAR_RIGHT:
-      NS_ASSERTION(mHaveCachedRightYMost, "Need cached value!");
-      bottom = PR_MAX(bottom, mMaximalRightYMost);
+      bottom = PR_MAX(bottom, tail.mRightYMost);
       break;
     default:
       // Do nothing
       break;
   }
 
   bottom -= mY;
 
   return bottom;
 }
 
-nsFloatManager::BandRect*
-nsFloatManager::GuessBandWithTopAbove(nscoord aYOffset) const
-{
-  NS_ASSERTION(!mBandList.IsEmpty(), "no bands");
-  BandRect* band = nsnull;
-  if (mCachedBandPosition) {
-    band = mCachedBandPosition;
-    // Now seek backward so that we're guaranteed to be the topmost
-    // band which might contain the y-offset or be below it.
-    while (band && band->mTop > aYOffset) {
-      band = GetPrevBand(band);
-    }
-  }
+/////////////////////////////////////////////////////////////////////////////
+// FloatInfo
 
-  if (band) {
-    return band;
-  }
-  
-  return mBandList.Head();
-}
-
-/////////////////////////////////////////////////////////////////////////////
-// FrameInfo
-
-nsFloatManager::FrameInfo::FrameInfo(nsIFrame* aFrame, const nsRect& aRect)
-  : mFrame(aFrame), mRect(aRect), mNext(0)
+nsFloatManager::FloatInfo::FloatInfo(nsIFrame* aFrame, const nsRect& aRect)
+  : mFrame(aFrame), mRect(aRect)
 {
-  MOZ_COUNT_CTOR(nsFloatManager::FrameInfo);
+  MOZ_COUNT_CTOR(nsFloatManager::FloatInfo);
 }
 
 #ifdef NS_BUILD_REFCNT_LOGGING
-nsFloatManager::FrameInfo::~FrameInfo()
+nsFloatManager::FloatInfo::~FloatInfo()
 {
-  MOZ_COUNT_DTOR(nsFloatManager::FrameInfo);
+  MOZ_COUNT_DTOR(nsFloatManager::FloatInfo);
 }
 #endif
 
-/////////////////////////////////////////////////////////////////////////////
-// BandRect
-
-nsFloatManager::BandRect::BandRect(nscoord    aLeft,
-                                   nscoord    aTop,
-                                   nscoord    aRight,
-                                   nscoord    aBottom,
-                                   nsIFrame*  aFrame)
-{
-  MOZ_COUNT_CTOR(BandRect);
-  mLeft = aLeft;
-  mTop = aTop;
-  mRight = aRight;
-  mBottom = aBottom;
-  AddFrame(aFrame);
-}
-
-nsFloatManager::BandRect::BandRect(nscoord      aLeft,
-                                   nscoord      aTop,
-                                   nscoord      aRight,
-                                   nscoord      aBottom,
-                                   nsSmallVoidArray& aFrames)
-{
-  MOZ_COUNT_CTOR(BandRect);
-  mLeft = aLeft;
-  mTop = aTop;
-  mRight = aRight;
-  mBottom = aBottom;
-  mFrames = aFrames;
-}
-
-nsFloatManager::BandRect::~BandRect()
-{
-  MOZ_COUNT_DTOR(BandRect);
-}
-
-nsFloatManager::BandRect*
-nsFloatManager::BandRect::SplitVertically(nscoord aBottom)
-{
-  NS_PRECONDITION((aBottom > mTop) && (aBottom < mBottom), "bad argument");
-
-  // Create a new band rect for the bottom part
-  BandRect* bottomBandRect = new BandRect(mLeft, aBottom, mRight, mBottom, mFrames);
-                                           
-  // This band rect becomes the top part, so adjust the bottom edge
-  mBottom = aBottom;
-  return bottomBandRect;
-}
-
-nsFloatManager::BandRect*
-nsFloatManager::BandRect::SplitHorizontally(nscoord aRight)
-{
-  NS_PRECONDITION((aRight > mLeft) && (aRight < mRight), "bad argument");
-  
-  // Create a new band rect for the right part
-  BandRect* rightBandRect = new BandRect(aRight, mTop, mRight, mBottom, mFrames);
-                                           
-  // This band rect becomes the left part, so adjust the right edge
-  mRight = aRight;
-  return rightBandRect;
-}
-
-PRBool
-nsFloatManager::BandRect::HasSameFrameList(const BandRect* aBandRect) const
-{
-  const PRInt32 count = mFrames.Count();
-
-  // Check whether they're occupied by the same number of frames
-  if (count != aBandRect->mFrames.Count()) {
-    return PR_FALSE;
-  }
-  // For each frame occupying this band rect check whether it also occupies
-  // aBandRect
-  for (PRInt32 i = 0; i < count; i++) {
-    if (-1 == aBandRect->mFrames.IndexOf(mFrames.FastElementAt(i))) {
-      return PR_FALSE;
-    }
-  }
-
-  return PR_TRUE;
-}
-
-/**
- * Internal helper function that counts the number of rects in this band
- * including the current band rect
- */
-PRInt32
-nsFloatManager::BandRect::Length() const
-{
-  PRInt32   len = 1;
-  BandRect* bandRect = Next();
-
-  // Because there's a header cell we know we'll either find the next band
-  // (which has a different y-offset) or the header cell which has an invalid
-  // y-offset
-  while (bandRect->mTop == mTop) {
-    len++;
-    bandRect = bandRect->Next();
-  }
-
-  return len;
-}
-
-
 //----------------------------------------------------------------------
 
 nsAutoFloatManager::~nsAutoFloatManager()
 {
   // Restore the old float manager in the reflow state if necessary.
   if (mNew) {
 #ifdef NOISY_FLOATMANAGER
     printf("restoring old float manager %p\n", mOld);
rename from layout/generic/nsSpaceManager.h
rename to layout/generic/nsFloatManager.h
--- a/layout/generic/nsSpaceManager.h
+++ b/layout/generic/nsFloatManager.h
@@ -16,267 +16,152 @@
  * The Original Code is mozilla.org code.
  *
  * The Initial Developer of the Original Code is
  * Netscape Communications Corporation.
  * Portions created by the Initial Developer are Copyright (C) 1998
  * the Initial Developer. All Rights Reserved.
  *
  * Contributor(s):
+ *   L. David Baron <dbaron@dbaron.org>, Mozilla Corporation
  *
  * Alternatively, the contents of this file may be used under the terms of
  * either of the GNU General Public License Version 2 or later (the "GPL"),
  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  * in which case the provisions of the GPL or the LGPL are applicable instead
  * of those above. If you wish to allow use of your version of this file only
  * under the terms of either the GPL or the LGPL, and not to allow others to
  * use your version of this file under the terms of the MPL, indicate your
  * decision by deleting the provisions above and replace them with the notice
  * and other provisions required by the GPL or the LGPL. If you do not delete
  * the provisions above, a recipient may use your version of this file under
  * the terms of any one of the MPL, the GPL or the LGPL.
  *
  * ***** END LICENSE BLOCK ***** */
 
-/*
- * class that manages regions of 2-D space, originally designed
- * generally but actually specific to space occupied by floats
- */
+/* class that manages rules for positioning floats */
 
-#ifndef nsSpaceManager_h___
-#define nsSpaceManager_h___
+#ifndef nsFloatManager_h_
+#define nsFloatManager_h_
 
-#include "prclist.h"
 #include "nsIntervalSet.h"
-#include "nsISupports.h"
 #include "nsCoord.h"
 #include "nsRect.h"
-#include "nsVoidArray.h"
+#include "nsTArray.h"
 
 class nsIPresShell;
 class nsIFrame;
-struct nsSize;
 struct nsHTMLReflowState;
 class nsPresContext;
 
-#define NS_SPACE_MANAGER_CACHE_SIZE 4
-
-/**
- * Information about a particular trapezoid within a band. The space described
- * by the trapezoid is in one of three states:
- * <ul>
- * <li>available
- * <li>occupied by one frame
- * <li>occupied by more than one frame
- * </ul>
- */
-struct nsBandTrapezoid {
-  nscoord   mTopY, mBottomY;            // top and bottom y-coordinates
-  nscoord   mTopLeftX, mBottomLeftX;    // left edge x-coordinates
-  nscoord   mTopRightX, mBottomRightX;  // right edge x-coordinates
-  const nsSmallVoidArray* mFrames; // list of frames occupying the space
-
-  // Get the height of the trapezoid
-  nscoord GetHeight() const {return mBottomY - mTopY;}
-
-  // Get the bounding rect of the trapezoid
-  inline void GetRect(nsRect& aRect) const;
-
-  // Set the trapezoid from a rectangle
-  inline void operator=(const nsRect& aRect);
-
-  // Do these trapezoids have the same geometry?
-  inline PRBool EqualGeometry(const nsBandTrapezoid& aTrap) const;
-
-  nsBandTrapezoid()
-    : mTopY(0),
-      mBottomY(0),
-      mTopLeftX(0),
-      mBottomLeftX(0),
-      mTopRightX(0),
-      mBottomRightX(0),
-      mFrames(nsnull)
-  {
-  }
-};
+#define NS_FLOAT_MANAGER_CACHE_SIZE 4
 
-inline void nsBandTrapezoid::GetRect(nsRect& aRect) const
-{
-  aRect.x = PR_MIN(mTopLeftX, mBottomLeftX);
-  aRect.y = mTopY;
-  aRect.width = PR_MAX(mTopRightX, mBottomRightX);
-  if (NS_MAXSIZE != aRect.width) {
-    aRect.width -= aRect.x;
-  }
-  aRect.height = (NS_MAXSIZE == mBottomY) ? NS_MAXSIZE : mBottomY - mTopY;
-}
-
-inline void nsBandTrapezoid::operator=(const nsRect& aRect)
-{
-  mTopLeftX = mBottomLeftX = aRect.x;
-  mTopRightX = mBottomRightX = aRect.XMost();
-  mTopY = aRect.y;
-  mBottomY = aRect.YMost();
-}
-
-inline PRBool nsBandTrapezoid::EqualGeometry(const nsBandTrapezoid& aTrap) const
-{
-  return (
-    mTopLeftX == aTrap.mTopLeftX &&
-    mBottomLeftX == aTrap.mBottomLeftX &&
-    mTopRightX == aTrap.mTopRightX &&
-    mBottomRightX == aTrap.mBottomRightX &&
-    mTopY == aTrap.mTopY &&
-    mBottomY == aTrap.mBottomY
-  );
-}
-
-/**
- * Structure used for describing the space within a band.
- * @see #GetBandData()
- */
-struct nsBandData {
-  PRInt32 mCount; // [out] actual number of trapezoids in the band data
-  PRInt32 mSize; // [in] the size of the array (number of trapezoids)
-  nsBandTrapezoid* mTrapezoids; // [out] array of length 'size'
-};
-
-/**
- * Class for dealing with bands of available space. The float manager
- * defines a coordinate space (relative to the frame that created the
- * float manager) with an origin at (0, 0) that grows down and to the
- * right.
- */
 class nsFloatManager {
 public:
   nsFloatManager(nsIPresShell* aPresShell);
   ~nsFloatManager();
 
   void* operator new(size_t aSize) CPP_THROW_NEW;
   void operator delete(void* aPtr, size_t aSize);
 
   static void Shutdown();
+
   /**
    * Translate the current origin by the specified (dx, dy). This
    * creates a new local coordinate space relative to the current
    * coordinate space.
    */
   void Translate(nscoord aDx, nscoord aDy) { mX += aDx; mY += aDy; }
 
   /**
    * Returns the current translation from local coordinate space to
    * world coordinate space. This represents the accumulated calls to
    * Translate().
    */
   void GetTranslation(nscoord& aX, nscoord& aY) const { aX = mX; aY = mY; }
-  /**
-   * Returns the y-most of the bottommost band or 0 if there are no bands.
-   *
-   * @return  PR_TRUE if there are bands and PR_FALSE if there are no bands
-   */
-  PRBool YMost(nscoord& aYMost) const;
 
   /**
-   * Returns a band starting at the specified y-offset. The band data
-   * indicates which parts of the band are available, and which parts
-   * are unavailable
-   *
-   * The band data that is returned is in the coordinate space of the
-   * local coordinate system.
-   *
-   * The local coordinate space origin, the y-offset, and the max size
-   * describe a rectangle that's used to clip the underlying band of
-   * available space, i.e.
-   * {0, aYOffset, aMaxSize.width, aMaxSize.height} in the local
-   * coordinate space
+   * Get information about the band containing vertical coordinate |aY|,
+   * but up to at most |aMaxHeight| (which may be nscoord_MAX).  This
+   * will return the tallest rectangle whose top is |aY| and in which
+   * there are no changes in what floats are on the sides of that
+   * rectangle, but will limit the height of the rectangle to
+   * |aMaxHeight|.  The left and right edges of the rectangle give the
+   * area available for line boxes in that space.
    *
-   * @param   aYOffset the y-offset of where the band begins. The coordinate is
-   *            relative to the upper-left corner of the local coordinate space
-   * @param   aMaxSize the size to use to constrain the band data
-   * @param   aBandData [in,out] used to return the list of trapezoids that
-   *            describe the available space and the unavailable space
-   * @return  NS_OK if successful and NS_ERROR_FAILURE if the band data is not
-   *            not large enough. The 'count' member of the band data struct
-   *            indicates how large the array of trapezoids needs to be
+   * @param aY [in] vertical coordinate for top of available space
+   *           desired
+   * @param aMaxHeight [in] maximum height of available space desired
+   * @param aContentAreaWidth [in] the width of the content area (whose left
+   *                          edge must be zero in the current translation)
+   * @param aHasFloats [out] whether there are floats at the sides of
+   *                    the return value including those that do not
+   *                    reduce the line box width at all (because they
+   *                    are entirely in the margins)
+   * @return the resulting rectangle for line boxes.  It will not go
+   *         left of 0, nor right of aContentAreaWidth, but will be
+   *         narrower when floats are present.
+   *
+   * aY and aAvailSpace are positioned relative to the current translation
    */
-  nsresult GetBandData(nscoord       aYOffset,
-                       const nsSize& aMaxSize,
-                       nsBandData&   aBandData) const;
+  nsRect GetBand(nscoord aY, nscoord aMaxHeight, nscoord aContentAreaWidth,
+                 PRBool* aHasFloats) const;
 
   /**
-   * Add a rectangular region of unavailable space. The space is
-   * relative to the local coordinate system.
-   *
-   * The region is tagged with a frame
+   * Add a float that comes after all floats previously added.  Its top
+   * must be even with or below the top of all previous floats.
    *
-   * @param   aFrame the frame used to identify the region. Must not be NULL
-   * @param   aUnavailableSpace the bounding rect of the unavailable space
-   * @return  NS_OK if successful
-   *          NS_ERROR_FAILURE if there is already a region tagged with aFrame
+   * aMarginRect is relative to the current translation.  The caller
+   * must ensure aMarginRect.height >= 0 and aMarginRect.width >= 0.
    */
-  nsresult AddRectRegion(nsIFrame*     aFrame,
-                         const nsRect& aUnavailableSpace);
+  nsresult AddFloat(nsIFrame* aFloatFrame, const nsRect& aMarginRect);
 
   /**
    * Remove the regions associated with this floating frame and its
    * next-sibling list.  Some of the frames may never have been added;
    * we just skip those. This is not fully general; it only works as
    * long as the N frames to be removed are the last N frames to have
    * been added; if there's a frame in the middle of them that should
    * not be removed, YOU LOSE.
-   *
-   * This can only be done at the end of the life of this float manager. The only
-   * methods it is safe to call after this are XMost() and YMost().
    */
   nsresult RemoveTrailingRegions(nsIFrame* aFrameList);
 
-protected:
-  /**
-   * Remove the region associated with aFrane.
-   *
-   * doesn't work in the general case!
-   *
-   * Returns NS_OK if successful and NS_ERROR_INVALID_ARG if there is no region
-   * tagged with aFrame
-   */
-  nsresult RemoveRegion(nsIFrame* aFrame);
+private:
+  struct FloatInfo;
+public:
 
-public:
   // Structure that stores the current state of a frame manager for
   // Save/Restore purposes.
+  struct SavedState;
+  friend struct SavedState;
   struct SavedState {
   private:
-    nsIFrame *mLastFrame;
+    PRUint32 mFloatInfoCount;
     nscoord mX, mY;
-    nscoord mLowestTop;
-    nscoord mMaximalLeftYMost;
-    nscoord mMaximalRightYMost;
-    PRPackedBool mHaveCachedLeftYMost;
-    PRPackedBool mHaveCachedRightYMost;
     
     friend class nsFloatManager;
   };
 
-  PRBool HasAnyFloats() { return mFrameInfoMap != nsnull; }
+  PRBool HasAnyFloats() const { return !mFloats.IsEmpty(); }
 
   /**
    * Methods for dealing with the propagation of float damage during
    * reflow.
    */
-  PRBool HasFloatDamage()
+  PRBool HasFloatDamage() const
   {
     return !mFloatDamage.IsEmpty();
   }
 
   void IncludeInDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
   {
     mFloatDamage.IncludeInterval(aIntervalBegin + mY, aIntervalEnd + mY);
   }
 
-  PRBool IntersectsDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
+  PRBool IntersectsDamage(nscoord aIntervalBegin, nscoord aIntervalEnd) const
   {
     return mFloatDamage.Intersects(aIntervalBegin + mY, aIntervalEnd + mY);
   }
 
   /**
    * Saves the current state of the float manager into aState.
    */
   void PushState(SavedState* aState);
@@ -287,205 +172,85 @@ public:
    * These states must be managed using stack discipline. PopState can only
    * be used after PushState has been used to save the state, and it can only
    * be used once --- although it can be omitted; saved states can be ignored.
    * States must be popped in the reverse order they were pushed. 
    */
   void PopState(SavedState* aState);
 
   /**
-   * Get the top of the last region placed into the float manager, to
+   * Get the top of the last float placed into the float manager, to
    * enforce the rule that a float can't be above an earlier float.
-   * Returns the minimum nscoord value if there are no regions.
+   * Returns the minimum nscoord value if there are no floats.
+   *
+   * The result is relative to the current translation.
    */
-  nscoord GetLowestRegionTop();
+  nscoord GetLowestFloatTop() const;
 
   /**
    * Return the coordinate of the lowest float matching aBreakType in this
    * float manager. Returns aY if there are no matching floats.
+   *
+   * Both aY and the result are relative to the current translation.
    */
-  nscoord ClearFloats(nscoord aY, PRUint8 aBreakType);
+  nscoord ClearFloats(nscoord aY, PRUint8 aBreakType) const;
 
 #ifdef DEBUG
   /**
-   * Dump the state of the spacemanager out to a file
+   * Dump the state of the float manager out to a file.
    */
-  nsresult List(FILE* out);
+  nsresult List(FILE* out) const;
 #endif
 
-protected:
-  // Structure that maintains information about the region associated
-  // with a particular frame
-  struct FrameInfo {
-    nsIFrame* const mFrame;
-    nsRect          mRect;       // rectangular region
-    FrameInfo*      mNext;
+private:
 
-    FrameInfo(nsIFrame* aFrame, const nsRect& aRect);
+  struct FloatInfo {
+    nsIFrame *const mFrame;
+    nsRect mRect;
+    // The lowest bottoms of left/right floats up to and including this one.
+    nscoord mLeftYMost, mRightYMost;
+
+    FloatInfo(nsIFrame* aFrame, const nsRect& aRect);
 #ifdef NS_BUILD_REFCNT_LOGGING
-    ~FrameInfo();
+    ~FloatInfo();
 #endif
   };
 
-public:
-  // Doubly linked list of band rects
-  struct BandRect : PRCListStr {
-    nscoord   mLeft, mTop;
-    nscoord   mRight, mBottom;
-    nsSmallVoidArray mFrames;  // list of frames occupying the space
-
-    BandRect(nscoord aLeft, nscoord aTop,
-             nscoord aRight, nscoord aBottom,
-             nsIFrame* aFrame);
-    BandRect(nscoord aLeft, nscoord aTop,
-             nscoord aRight, nscoord aBottom,
-             nsSmallVoidArray& frames);
-    ~BandRect();
-
-    // List operations
-    BandRect* Next() const {return (BandRect*)PR_NEXT_LINK(this);}
-    BandRect* Prev() const {return (BandRect*)PR_PREV_LINK(this);}
-    void      InsertBefore(BandRect* aBandRect) {PR_INSERT_BEFORE(aBandRect, this);}
-    void      InsertAfter(BandRect* aBandRect) {PR_INSERT_AFTER(aBandRect, this);}
-    void      Remove() {PR_REMOVE_LINK(this);}
-
-    // Split the band rect into two vertically, with this band rect becoming
-    // the top part, and a new band rect being allocated and returned for the
-    // bottom part
-    //
-    // Does not insert the new band rect into the linked list
-    BandRect* SplitVertically(nscoord aBottom);
-
-    // Split the band rect into two horizontally, with this band rect becoming
-    // the left part, and a new band rect being allocated and returned for the
-    // right part
-    //
-    // Does not insert the new band rect into the linked list
-    BandRect* SplitHorizontally(nscoord aRight);
-
-    // Accessor functions
-    PRBool  IsOccupiedBy(const nsIFrame* aFrame) const {
-      return (mFrames.IndexOf((void*)aFrame) != -1);
-    }
-    void    AddFrame(const nsIFrame* aFrame) {
-      mFrames.AppendElement((void*)aFrame);
-    }
-    void    RemoveFrame(const nsIFrame* aFrame) {
-      mFrames.RemoveElement((void*)aFrame);
-    }
-    nsIFrame * FrameAt(PRInt32 index) {
-      return static_cast<nsIFrame*>(mFrames.FastElementAt(index));
-    }
-    PRBool  HasSameFrameList(const BandRect* aBandRect) const;
-    PRInt32 Length() const;
-  };
-
-  // Circular linked list of band rects
-  struct BandList : BandRect {
-    BandList();
-
-    // Accessors
-    PRBool    IsEmpty() const {return PR_CLIST_IS_EMPTY((PRCListStr*)this);}
-    BandRect* Head() const {return (BandRect*)PR_LIST_HEAD(this);}
-    BandRect* Tail() const {return (BandRect*)PR_LIST_TAIL(this);}
-
-    // Operations
-    void      Append(BandRect* aBandRect) {PR_APPEND_LINK(aBandRect, this);}
+  nscoord         mX, mY;     // translation from local to global coordinate space
+  nsTArray<FloatInfo> mFloats;
+  nsIntervalSet   mFloatDamage;
 
-    // Remove and delete all the band rects in the list
-    void      Clear();
-  };
-
-protected:
-  nscoord         mX, mY;     // translation from local to global coordinate space
-  BandList        mBandList;  // header/sentinel for circular linked list of band rects
-  nscoord         mLowestTop;  // the lowest *top*
-  FrameInfo*      mFrameInfoMap;
-  nsIntervalSet   mFloatDamage;
-  PRPackedBool    mHaveCachedLeftYMost; // If true, mMaximalLeftYMost is set
-  PRPackedBool    mHaveCachedRightYMost; // If true, mMaximalRightYMost is set
-  nscoord         mMaximalLeftYMost;  // The maximal YMost of our FrameInfo
-                                      // rects for left floats.  Only makes
-                                      // sense when mHaveCachedLeftYMost is
-                                      // true.
-  nscoord         mMaximalRightYMost; // The maximal YMost of our FrameInfo
-                                      // rects for right floats.  Only makes
-                                      // sense when mHaveCachedLeftYMost is
-                                      // true.
-  // We keep track of the last BandRect* we worked with so that we can
-  // make use of locality of reference in situations where people want
-  // to do a bunch of operations in a row.
-  BandRect*       mCachedBandPosition;
-
-protected:
-  FrameInfo* GetFrameInfoFor(nsIFrame* aFrame);
-  FrameInfo* CreateFrameInfo(nsIFrame* aFrame, const nsRect& aRect);
-  void       DestroyFrameInfo(FrameInfo*);
-
-  void       ClearFrameInfo();
-
-  BandRect*  GetNextBand(const BandRect* aBandRect) const;
-  BandRect*  GetPrevBand(const BandRect* aBandRect) const;
-  void       DivideBand(BandRect* aBand, nscoord aBottom);
-  PRBool     CanJoinBands(BandRect* aBand, BandRect* aPrevBand);
-  PRBool     JoinBands(BandRect* aBand, BandRect* aPrevBand);
-  void       AddRectToBand(BandRect* aBand, BandRect* aBandRect);
-  void       InsertBandRect(BandRect* aBandRect);
-
-  nsresult   GetBandAvailableSpace(const BandRect* aBand,
-                                   nscoord         aY,
-                                   const nsSize&   aMaxSize,
-                                   nsBandData&     aAvailableSpace) const;
-
-  // Return a band guaranteed to have its top at or above aYOffset or the first
-  // band if there is no band with its top above aYOffset.  This method will
-  // use mCachedBandPosition to maybe get such a band that's not too far up.
-  // This function should not be called if there are no bands.
-  // This function never returns null.
-  BandRect*  GuessBandWithTopAbove(nscoord aYOffset) const;
-
-  void SetCachedBandPosition(BandRect* aBandRect) {
-    NS_ASSERTION(!aBandRect ||
-                 aBandRect == mBandList.Head() ||
-                 aBandRect->Prev()->mBottom != aBandRect->mBottom,
-                 "aBandRect should be first rect within its band");
-    mCachedBandPosition = aBandRect;
-  }
-
-
-private:
   static PRInt32 sCachedFloatManagerCount;
-  static void* sCachedFloatManagers[NS_SPACE_MANAGER_CACHE_SIZE];
+  static void* sCachedFloatManagers[NS_FLOAT_MANAGER_CACHE_SIZE];
 
   nsFloatManager(const nsFloatManager&);  // no implementation
   void operator=(const nsFloatManager&);  // no implementation
 };
 
 /**
  * A helper class to manage maintenance of the float manager during
- * nsBlockFrame::Reflow. It automatically restores the old space
+ * nsBlockFrame::Reflow. It automatically restores the old float
  * manager in the reflow state when the object goes out of scope.
  */
 class nsAutoFloatManager {
 public:
   nsAutoFloatManager(nsHTMLReflowState& aReflowState)
     : mReflowState(aReflowState),
       mNew(nsnull),
       mOld(nsnull) {}
 
   ~nsAutoFloatManager();
 
   /**
    * Create a new float manager for the specified frame. This will
-   * `remember' the old float manager, and install the new space
+   * `remember' the old float manager, and install the new float
    * manager in the reflow state.
    */
   nsresult
   CreateFloatManager(nsPresContext *aPresContext);
 
 protected:
   nsHTMLReflowState &mReflowState;
   nsFloatManager *mNew;
   nsFloatManager *mOld;
 };
 
-#endif /* nsSpaceManager_h___ */
-
+#endif /* !defined(nsFloatManager_h_) */
--- a/layout/generic/nsLineBox.cpp
+++ b/layout/generic/nsLineBox.cpp
@@ -36,17 +36,16 @@
  * the provisions above, a recipient may use your version of this file under
  * the terms of any one of the MPL, the GPL or the LGPL.
  *
  * ***** END LICENSE BLOCK ***** */
 
 /* representation of one line within a block frame, a CSS line box */
 
 #include "nsLineBox.h"
-#include "nsSpaceManager.h"
 #include "nsLineLayout.h"
 #include "prprf.h"
 #include "nsBlockFrame.h"
 #include "nsGkAtoms.h"
 #include "nsFrameManager.h"
 #ifdef IBMBIDI
 #include "nsBidiPresUtils.h"
 #endif
--- a/layout/generic/nsLineBox.h
+++ b/layout/generic/nsLineBox.h
@@ -41,17 +41,16 @@
 /* representation of one line within a block frame, a CSS line box */
 
 #ifndef nsLineBox_h___
 #define nsLineBox_h___
 
 #include "nsPlaceholderFrame.h"
 #include "nsILineIterator.h"
 
-class nsFloatManager;
 class nsLineBox;
 class nsFloatCache;
 class nsFloatCacheList;
 class nsFloatCacheFreeList;
 
 // State cached after reflowing a float. This state is used during
 // incremental reflow when we avoid reflowing a float.
 class nsFloatCache {
--- a/layout/generic/nsLineLayout.cpp
+++ b/layout/generic/nsLineLayout.cpp
@@ -47,17 +47,17 @@
 #include "plarena.h"
 
 #include "nsCOMPtr.h"
 #include "nsLineLayout.h"
 #include "nsBlockFrame.h"
 #include "nsInlineFrame.h"
 #include "nsStyleConsts.h"
 #include "nsHTMLContainerFrame.h"
-#include "nsSpaceManager.h"
+#include "nsFloatManager.h"
 #include "nsStyleContext.h"
 #include "nsPresContext.h"
 #include "nsIFontMetrics.h"
 #include "nsIThebesFontMetrics.h"
 #include "nsIRenderingContext.h"
 #include "nsGkAtoms.h"
 #include "nsPlaceholderFrame.h"
 #include "nsIDocument.h"
--- a/layout/svg/base/src/nsSVGForeignObjectFrame.cpp
+++ b/layout/svg/base/src/nsSVGForeignObjectFrame.cpp
@@ -36,17 +36,16 @@
  *
  * ***** END LICENSE BLOCK ***** */
 
 #include "nsSVGForeignObjectFrame.h"
 
 #include "nsIDOMSVGForeignObjectElem.h"
 #include "nsIDOMSVGMatrix.h"
 #include "nsIDOMSVGSVGElement.h"
-#include "nsSpaceManager.h"
 #include "nsSVGOuterSVGFrame.h"
 #include "nsRegion.h"
 #include "nsGkAtoms.h"
 #include "nsLayoutUtils.h"
 #include "nsSVGUtils.h"
 #include "nsIURI.h"
 #include "nsSVGRect.h"
 #include "nsSVGMatrix.h"
--- a/layout/xul/base/src/nsBoxFrame.cpp
+++ b/layout/xul/base/src/nsBoxFrame.cpp
@@ -67,17 +67,16 @@
 #include "nsBoxLayoutState.h"
 #include "nsBoxFrame.h"
 #include "nsStyleContext.h"
 #include "nsPresContext.h"
 #include "nsCOMPtr.h"
 #include "nsINameSpaceManager.h"
 #include "nsGkAtoms.h"
 #include "nsIContent.h"
-#include "nsSpaceManager.h"
 #include "nsHTMLParts.h"
 #include "nsIViewManager.h"
 #include "nsIView.h"
 #include "nsIPresShell.h"
 #include "nsFrameNavigator.h"
 #include "nsCSSRendering.h"
 #include "nsIServiceManager.h"
 #include "nsIBoxLayout.h"