From: adam <adam@megacz.com>
Date: Wed, 7 Apr 2004 07:53:46 +0000 (+0000)
Subject: achieved true O(numboxes) and independence from numcols
X-Git-Tag: RC4~36
X-Git-Url: http://git.megacz.com/?p=org.ibex.core.git;a=commitdiff_plain;h=80f694a9d56be6df76bb61d5409a4ab0bae6be86

achieved true O(numboxes) and independence from numcols

darcs-hash:20040407075346-5007d-f0cd824cd9db4b0b8066c6c6ea567a3c1c182764.gz
---

diff --git a/src/org/ibex/Box.java b/src/org/ibex/Box.java
index f680f20..13c02ee 100644
--- a/src/org/ibex/Box.java
+++ b/src/org/ibex/Box.java
@@ -212,35 +212,45 @@ public final class Box extends JSScope implements Scheduler.Task {
 
     // Reflow ////////////////////////////////////////////////////////////////////////////////////////
 
-    // static stuff so we don't have to keep reallocating
-    private static int[] numRowsInCol = new int[65535];
-
     Box nextPackedSibling() { Box b = nextSibling(); return b == null || (b.test(PACKED | VISIBLE)) ? b : b.nextPackedSibling(); }
     Box firstPackedChild() { Box b = getChild(0); return b == null || (b.test(PACKED | VISIBLE)) ? b : b.nextPackedSibling(); }
 
+    private static int[] frontier = new int[65535];
+
     /** pack the boxes into rows and columns; also computes contentwidth */
     void repack() {
         for(Box child = getChild(0); child != null; child = child.nextSibling()) child.repack();
-
+        if (treeSize() == 0) { constrain(); return; }
         //#repeat COLS/ROWS rows/cols cols/rows col/row row/col colspan/rowspan rowspan/colspan 
         if (test(FIXED) == COLS) {
-            short r = 0;
-            for(Box child = firstPackedChild(); child != null; r++) {
-                for(short c=0, numclear=0; child != null && c < cols; c++) {
-                    if (numRowsInCol[c] > r) { numclear = 0; continue; }
-                    if (c != 0 && c + min(cols, child.colspan) - numclear > cols) break;
-                    if (++numclear < min(cols, child.colspan)) continue;
-                    for(int i=c - numclear + 1; i <= c; i++) numRowsInCol[i] += child.rowspan;
-                    child.col = (short)(c - numclear + 1); child.row = r;
-                    rows = (short)max(rows, child.row + child.rowspan);
-                    child = child.nextPackedSibling();
-                    numclear = 0;
+            int childnum = 0;
+            Box lastpacked = null;
+            int maxfront = 0;
+            for(Box child = getChild(0); child != null; child = child.nextSibling(), childnum++) {
+                if (!(child.test(PACKED) && child.test(VISIBLE))) continue;
+                int col = lastpacked == null ? 0 : (lastpacked.col + lastpacked.colspan);
+                int row = lastpacked == null ? 0 : lastpacked.row;
+                int colspan = min(cols, child.colspan);
+                for(int i=0; i<maxfront; i++) {
+                    if (col + colspan > cols) { row++; col = 0; i = -1; continue; }
+                    Box front = getChild(frontier[i]);       // FIXME: O(nlgn)
+                    if (front.row + front.rowspan <= row) { frontier[i] = frontier[maxfront-1]; maxfront--; i--; continue; }
+                    if ((front.col <= col && front.col + front.colspan > col) ||
+                        (front.col < (col+colspan) && front.col + front.colspan >= (col+colspan))) {
+                        col = front.col + front.colspan;
+                        i = -1;
+                        continue;
+                    }
+                    break;
                 }
+                child.col = (short)col;
+                child.row = (short)row;
+                lastpacked = child;
+                frontier[maxfront++] = childnum;
             }
-            for(int i=0; i<cols; i++) numRowsInCol[i] = 0;
+            rows = (short)(lastpacked.row + lastpacked.rowspan);
         }
         //#end
-        constrain();
     }
 
     void constrain() {
@@ -296,7 +306,6 @@ public final class Box extends JSScope implements Scheduler.Task {
     private static float[] coeff = null;
     private static LinearProgramming.Simplex lp_h = new LinearProgramming.Simplex(100, 100, 300);
     private static LinearProgramming.Simplex lp = new LinearProgramming.Simplex(100, 100, 300);
-    boolean[] breakpoints = new boolean[65535];
     int[] regions = new int[65535];
     int[] regions_v = new int[65535];
 
@@ -307,15 +316,24 @@ public final class Box extends JSScope implements Scheduler.Task {
         //        maxwidth/maxheight cols/rows minwidth/minheight lp_h/lp lp_h/lp easy_width/easy_height regions/regions_v
         if (cols > 1) do {
             /* boolean easy_width = contentwidth >= width; */
+
+            // FIXME: numboxes^2, and damn ugly to boot
             for(Box c = firstPackedChild(); c != null; c = c.nextPackedSibling()) {
-                breakpoints[c.col] = true;
-                breakpoints[min(cols, c.col+c.colspan)] = true;
+                int target = c.col;
+                for(boolean stop = false;;) {
+                    for(int i=0; i<=numregions; i++) {
+                        if (i == numregions) { regions[numregions++] = target; break; }
+                        if (target == regions[i]) break;
+                        if (target < regions[i]) { int tmp = target; target = regions[i]; regions[i] = tmp; }
+                    }
+                    if (stop) break;
+                    stop = true;
+                    target = min(cols, c.col+c.colspan);
+                }
             }
-            numregions = 0;
-            // FIXME: depends on cols
-            for(int i=0; i<cols; i++) if (breakpoints[i]) regions[numregions++] = i;
-            regions[numregions] = cols;
-            for(int i=0; i<numkids; i++) breakpoints[i] = false;
+            if (regions[numregions-1] == cols) numregions--;
+            else regions[numregions] = cols;
+
             /*
             for(Box c = firstPackedChild(); easy_width && c != null; c = c.nextPackedSibling()) {
                 if (c.contentwidth == c.maxwidth) continue;