Limited search for floats (not yet used, not even tested).

3 files changed, 98 insertions, 39 deletions

diff --git a/dw/outofflowmgr.cc b/dw/outofflowmgr.cc
index 5668d76c..d775501c 100644
--- a/dw/outofflowmgr.cc
+++ b/dw/outofflowmgr.cc
@@ -132,19 +132,59 @@ int OutOfFlowMgr::Float::CompareSideSpanningIndex::compare(Object *o1,
 }
 
 
-int OutOfFlowMgr::SortedFloatsVector::find (Textblock *textblock, int y)
+int OutOfFlowMgr::SortedFloatsVector::find (Textblock *textblock, int y,
+                                            Textblock *lastGB, int lastExtIndex)
 {
+   int last;
+
+   if (lastGB) {
+      TypedPointer<Textblock> key (lastGB);
+      TBInfo *tbInfo = oofm->tbInfosByTextblock->get (&key);
+      if (tbInfo) {
+         SortedFloatsVector *gbList =
+            side == LEFT ? tbInfo->leftFloatsGB : tbInfo->rightFloatsGB;
+         // Could be faster with binary search, but the GB (not CB!) lists
+         // should be rather small.
+         Float *lastFloat = NULL;
+         for (int i = 0; i < gbList->size(); i++) {
+            Float *vloat = gbList->get(i);
+            if (vloat->externalIndex <= lastExtIndex)
+               lastFloat = vloat;
+         }
+
+         if (lastFloat)
+            last = lastFloat->index;
+         else {
+            if (tbInfo->index > 0) {
+               TBInfo *prev = oofm->tbInfos->get (tbInfo->index - 1);
+               SortedFloatsVector *prevList =
+                  side == LEFT ? prev->leftFloatsGB : prev->rightFloatsGB;
+               // Each GB list contains at least one elemenent,
+               // otherwise it would not have been created; so the
+               // following is save.
+               Float *lastFloat = prevList->get (prevList->size() - 1);
+               last = lastFloat->index;
+            } else
+               last = -1;
+         }
+      } else
+         last = size () - 1;
+   } else
+      last = size() - 1;
+
    Float key (oofm, NULL, NULL, 0);
    key.generatingBlock = textblock;
    key.yReal = y;
 
-   return bsearch (&key, false);
+   return bsearch (&key, false, 0, last);
 }
 
 int OutOfFlowMgr::SortedFloatsVector::findFirst (Textblock *textblock,
-                                                 int y, int h)
+                                                 int y, int h,
+                                                 Textblock *lastGB,
+                                                 int lastExtIndex)
 {
-   int i = find (textblock, y);
+   int i = find (textblock, y, lastGB, lastExtIndex);
    if (i > 0 && get(i - 1)->covers (textblock, y, h))
       return i - 1;
    else if (i < size() && get(i)->covers (textblock, y, h))
@@ -164,8 +204,8 @@ int OutOfFlowMgr::SortedFloatsVector::findLastBeforeSideSpanningIndex
 
 OutOfFlowMgr::TBInfo::TBInfo (OutOfFlowMgr *oofm)
 {
-   leftFloatsGB = new SortedFloatsVector (oofm);
-   rightFloatsGB = new SortedFloatsVector (oofm);
+   leftFloatsGB = new SortedFloatsVector (oofm, LEFT);
+   rightFloatsGB = new SortedFloatsVector (oofm, RIGHT);
 }
 
 OutOfFlowMgr::TBInfo::~TBInfo ()
@@ -180,15 +220,15 @@ OutOfFlowMgr::OutOfFlowMgr (Textblock *containingBlock)
 
    this->containingBlock = containingBlock;
 
-   leftFloatsCB = new SortedFloatsVector (this);
-   rightFloatsCB = new SortedFloatsVector (this);
+   leftFloatsCB = new SortedFloatsVector (this, LEFT);
+   rightFloatsCB = new SortedFloatsVector (this, RIGHT);
 
    leftFloatsAll = new Vector<Float> (1, true);
    rightFloatsAll = new Vector<Float> (1, true);
 
    floatsByWidget = new HashTable <TypedPointer <Widget>, Float> (true, false);
 
-   tbInfos = new List <TBInfo> (false);
+   tbInfos = new Vector<TBInfo> (1, false);
    tbInfosByTextblock =
       new HashTable <TypedPointer <Textblock>, TBInfo> (true, true);
 
@@ -961,7 +1001,7 @@ OutOfFlowMgr::TBInfo *OutOfFlowMgr::registerCaller (Textblock *textblock)
       tbInfo->wasAllocated = false;
       tbInfo->index = tbInfos->size();
 
-      tbInfos->append (tbInfo);
+      tbInfos->put (tbInfo);
       tbInfosByTextblock->put (new TypedPointer<Textblock> (textblock), tbInfo);
    }
 
@@ -977,9 +1017,10 @@ OutOfFlowMgr::TBInfo *OutOfFlowMgr::registerCaller (Textblock *textblock)
  * but is 0 if there is no float, so a caller should also consider
  * other borders.
  */
-int OutOfFlowMgr::getLeftBorder (Textblock *textblock, int y, int h)
+int OutOfFlowMgr::getLeftBorder (Textblock *textblock, int y, int h,
+                                 Textblock *lastGB, int lastExtIndex)
 {
-   int b = getBorder (textblock, LEFT, y, h);
+   int b = getBorder (textblock, LEFT, y, h, lastGB, lastExtIndex);
    //printf ("getLeftBorder (%p, %d, %d) => %d\n", textblock, y, h, b);
    return b;
 }
@@ -990,14 +1031,16 @@ int OutOfFlowMgr::getLeftBorder (Textblock *textblock, int y, int h)
  *
  * See also getLeftBorder(int, int);
  */
-int OutOfFlowMgr::getRightBorder (Textblock *textblock, int y, int h)
+int OutOfFlowMgr::getRightBorder (Textblock *textblock, int y, int h,
+                                  Textblock *lastGB, int lastExtIndex)
 {
-   int b = getBorder (textblock, RIGHT, y, h);
+   int b = getBorder (textblock, RIGHT, y, h, lastGB, lastExtIndex);
    //printf ("getRightBorder (%p, %d, %d) => %d\n", textblock, y, h, b);
    return b;
 }
 
-int OutOfFlowMgr::getBorder (Textblock *textblock, Side side, int y, int h)
+int OutOfFlowMgr::getBorder (Textblock *textblock, Side side, int y, int h,
+                             Textblock *lastGB, int lastExtIndex)
 {
    //printf ("[%p] GET_BORDER (%p (allocated: %s), %s, %d, %d) ...\n",
    //        containingBlock, textblock,
@@ -1005,7 +1048,7 @@ int OutOfFlowMgr::getBorder (Textblock *textblock, Side side, int y, int h)
    //        side == LEFT ? "LEFT" : "RIGHT", y, h);
 
    SortedFloatsVector *list = getFloatsListForTextblock (textblock, side);
-   int first = list->findFirst (textblock, y, h);
+   int first = list->findFirst (textblock, y, h, lastGB, lastExtIndex);
 
    //printf ("[%p] GET_BORDER (...): %d floats, first is %d\n",
    //        containingBlock, list->size(), first);
@@ -1026,6 +1069,7 @@ int OutOfFlowMgr::getBorder (Textblock *textblock, Side side, int y, int h)
       // which the widest has to be choosen.
       int border = 0;
       bool covers = true;
+      // TODO Also check against lastGB and lastExtIndex
       for (int i = first; covers && i < list->size(); i++) {
          Float *vloat = list->get(i);
          covers = vloat->covers (textblock, y, h);
@@ -1058,20 +1102,23 @@ OutOfFlowMgr::SortedFloatsVector *OutOfFlowMgr::getFloatsListForTextblock
 }
 
 
-bool OutOfFlowMgr::hasFloatLeft (Textblock *textblock, int y, int h)
+bool OutOfFlowMgr::hasFloatLeft (Textblock *textblock, int y, int h,
+                                 Textblock *lastGB, int lastExtIndex)
 {
-   return hasFloat (textblock, LEFT, y, h);
+   return hasFloat (textblock, LEFT, y, h, lastGB, lastExtIndex);
 }
 
-bool OutOfFlowMgr::hasFloatRight (Textblock *textblock, int y, int h)
+bool OutOfFlowMgr::hasFloatRight (Textblock *textblock, int y, int h,
+                                  Textblock *lastGB, int lastExtIndex)
 {
-   return hasFloat (textblock, RIGHT, y, h);
+   return hasFloat (textblock, RIGHT, y, h, lastGB, lastExtIndex);
 }
 
-bool OutOfFlowMgr::hasFloat (Textblock *textblock, Side side, int y, int h)
+bool OutOfFlowMgr::hasFloat (Textblock *textblock, Side side, int y, int h,
+                             Textblock *lastGB, int lastExtIndex)
 {
-   return getFloatsListForTextblock(textblock,
-                                    side)->findFirst (textblock, y, h) != -1;
+   SortedFloatsVector *list = getFloatsListForTextblock(textblock, side);
+   return list->findFirst (textblock, y, h, lastGB, lastExtIndex) != -1;
 }
 
 void OutOfFlowMgr::ensureFloatSize (Float *vloat)
diff --git a/dw/outofflowmgr.hh b/dw/outofflowmgr.hh
index bee5c6ab..18ac801d 100644
--- a/dw/outofflowmgr.hh
+++ b/dw/outofflowmgr.hh
@@ -81,14 +81,17 @@ private:
    {
    private:
       OutOfFlowMgr *oofm;
+      Side side;
           
    public:
-      inline SortedFloatsVector (OutOfFlowMgr *oofm) :
+      inline SortedFloatsVector (OutOfFlowMgr *oofm, Side side) :
          lout::container::typed::Vector<Float> (1, false)
-      { this->oofm = oofm; }
+      { this->oofm = oofm; this->side = side; }
 
-      int find (Textblock *textblock, int y);
-      int findFirst (Textblock *textblock, int y, int h);
+      int find (Textblock *textblock, int y, Textblock *lastGB,
+                int lastExtIndex);
+      int findFirst (Textblock *textblock, int y, int h, Textblock *lastGB,
+                     int lastExtIndex);
       int findLastBeforeSideSpanningIndex (int sideSpanningIndex);
       inline void put (Float *vloat)
       { lout::container::typed::Vector<Float>::put (vloat);
@@ -132,7 +135,7 @@ private:
    lout::container::typed::HashTable<lout::object::TypedPointer
                                      <dw::core::Widget>, Float> *floatsByWidget;
 
-   lout::container::typed::List<TBInfo> *tbInfos;
+   lout::container::typed::Vector<TBInfo> *tbInfos;
    lout::container::typed::HashTable<lout::object::TypedPointer <Textblock>,
                                      TBInfo> *tbInfosByTextblock;
 
@@ -183,10 +186,12 @@ private:
    void accumExtremes (SortedFloatsVector *list, int *oofMinWidth,
                        int *oofMaxWidth);
    TBInfo *registerCaller (Textblock *textblock);
-   int getBorder (Textblock *textblock, Side side, int y, int h);
+   int getBorder (Textblock *textblock, Side side, int y, int h,
+                  Textblock *lastGB, int lastExtIndex);
    SortedFloatsVector *getFloatsListForTextblock (Textblock *textblock,
                                                   Side side);
-   bool hasFloat (Textblock *textblock, Side side, int y, int h);
+   bool hasFloat (Textblock *textblock, Side side, int y, int h,
+                  Textblock *lastGB, int lastExtIndex);
 
    void ensureFloatSize (Float *vloat);
    int getBorderDiff (Textblock *textblock, Float *vloat, Side side);
@@ -231,11 +236,15 @@ public:
    void getExtremes (int cbMinWidth, int cbMaxWidth, int *oofMinWidth,
                      int *oofMaxWidth);
 
-   int getLeftBorder (Textblock *textblock, int y, int h);
-   int getRightBorder (Textblock *textblock, int y, int h);
+   int getLeftBorder (Textblock *textblock, int y, int h, Textblock *lastGB,
+                      int lastExtIndex);
+   int getRightBorder (Textblock *textblock, int y, int h, Textblock *lastGB,
+                       int lastExtIndex);
 
-   bool hasFloatLeft (Textblock *textblock, int y, int h);
-   bool hasFloatRight (Textblock *textblock, int y, int h);
+   bool hasFloatLeft (Textblock *textblock, int y, int h, Textblock *lastGB,
+                      int lastExtIndex);
+   bool hasFloatRight (Textblock *textblock, int y, int h, Textblock *lastGB,
+                       int lastExtIndex);
 
    inline static bool isRefOutOfFlow (int ref)
    { return ref != -1 && (ref & 1) != 0; }
diff --git a/dw/textblock_linebreaking.cc b/dw/textblock_linebreaking.cc
index af23b5a4..4a5922b4 100644
--- a/dw/textblock_linebreaking.cc
+++ b/dw/textblock_linebreaking.cc
@@ -400,7 +400,8 @@ Textblock::Line *Textblock::addLine (int firstWord, int lastWord,
    if (containingBlock->outOfFlowMgr && mustBorderBeRegarded (line)) {
       int y = line->top + getStyle()->boxOffsetY();
       int h = line->boxAscent + line->boxDescent;
-      leftBorder = containingBlock->outOfFlowMgr->getLeftBorder (this, y, h);
+      leftBorder =
+         containingBlock->outOfFlowMgr->getLeftBorder (this, y, h, NULL, 0);
    } else
       leftBorder = 0;
 
@@ -535,8 +536,8 @@ void Textblock::wordWrap (int wordIndex, bool wrapAll)
          // disputable. (More on this later.)
 
          thereWillBeMoreSpace =
-            containingBlock->outOfFlowMgr->hasFloatLeft (this, y, h) ||
-            containingBlock->outOfFlowMgr->hasFloatRight (this, y, h);
+            containingBlock->outOfFlowMgr->hasFloatLeft (this, y, h, NULL, 0) ||
+            containingBlock->outOfFlowMgr->hasFloatRight (this, y, h, NULL, 0);
 
          PRINTF ("   thereWillBeMoreSpace = %s (y = %d, h = %d)\n",
                  thereWillBeMoreSpace ? "true" : "false", y, h);
@@ -1141,8 +1142,10 @@ int Textblock::calcAvailWidth (int lineIndex)
    if (containingBlock->outOfFlowMgr && mustBorderBeRegarded (lineIndex)) {
       int y = topOfPossiblyMissingLine (lineIndex);
       int h = heightOfPossiblyMissingLine (lineIndex);
-      leftBorder = containingBlock->outOfFlowMgr->getLeftBorder (this, y, h);
-      rightBorder = containingBlock->outOfFlowMgr->getRightBorder (this, y, h);
+      leftBorder =
+         containingBlock->outOfFlowMgr->getLeftBorder (this, y, h, NULL, 0);
+      rightBorder =
+         containingBlock->outOfFlowMgr->getRightBorder (this, y, h, NULL, 0);
    } else
       leftBorder = rightBorder = 0;