major repack speedup

darcs-hash:20040407105749-5007d-0a73c62baafe772efd99461cc0f0d7edde733045.gz

diff --git a/src/org/ibex/Box.java b/src/org/ibex/Box.java
index 13c02ee..bb57d5a 100644 (file)
--- a/src/org/ibex/Box.java
+++ b/src/org/ibex/Box.java
@@ -215,29 +215,49 @@ public final class Box extends JSScope implements Scheduler.Task {
     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(); }
 
     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];
+    private static Box[] frontier = new Box[65535];
+    private static int[] frontier_content = 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();
 
     /** pack the boxes into rows and columns; also computes contentwidth */
     void repack() {
         for(Box child = getChild(0); child != null; child = child.nextSibling()) child.repack();

+        contentwidth = 0;
+        contentheight = 0;

         if (treeSize() == 0) { constrain(); return; }
         if (treeSize() == 0) { constrain(); return; }

-        //#repeat COLS/ROWS rows/cols cols/rows col/row row/col colspan/rowspan rowspan/colspan 
+        //#repeat COLS/ROWS rows/cols cols/rows col/row row/col colspan/rowspan rowspan/colspan contentheight/contentwidth contentwidth/contentheight

         if (test(FIXED) == COLS) {
             int childnum = 0;
             Box lastpacked = null;
             int maxfront = 0;
         if (test(FIXED) == COLS) {
             int childnum = 0;
             Box lastpacked = null;
             int maxfront = 0;

+            int maxrow = 0;
+            int rowwidth = 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++) {
             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 (col + colspan > cols) {
+                        row++;
+                        for(; i>0; i--) row = max(row, frontier[i].row + frontier[i].rowspan);
+                        col = 0;
+                        rowwidth = 0;
+                        continue;
+                    }
+                    Box front = frontier[i];       // FIXME: O(nlgn)
+                    if (front.row + front.rowspan <= row) {
+                        frontier[i] = frontier[maxfront-1];
+                        frontier_content[i] = frontier_content[maxfront-1];
+                        maxfront--;
+                        frontier[maxfront] = null;
+                        frontier_content[maxfront] = 0;
+                        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;
                     if ((front.col <= col && front.col + front.colspan > col) ||
                         (front.col < (col+colspan) && front.col + front.colspan >= (col+colspan))) {
                         col = front.col + front.colspan;

+                        rowwidth += front.contentwidth; // FIXME: suspect

                         i = -1;
                         continue;
                     }
                         i = -1;
                         continue;
                     }

@@ -245,28 +265,33 @@ public final class Box extends JSScope implements Scheduler.Task {
                 }
                 child.col = (short)col;
                 child.row = (short)row;
                 }
                 child.col = (short)col;
                 child.row = (short)row;

+                maxrow = max(maxrow, child.row + child.rowspan);
+                contentwidth = max(contentwidth, rowwidth);
+                rowwidth = 0;

                 lastpacked = child;
                 lastpacked = child;

-                frontier[maxfront++] = childnum;
+                for(int i=0; i<maxfront; i++) {
+                    frontier_content[maxfront] =
+                        max(frontier_content[maxfront], frontier_content[i] + child.contentheight);
+                    contentheight = 
+                        max(contentheight, frontier_content[i] + child.contentheight);
+                }
+                frontier[maxfront++] = child;

             }
             }

-            rows = (short)(lastpacked.row + lastpacked.rowspan);
+            rows = (short)maxrow;
+            for(int i=0; i<maxfront; i++) frontier[i] = null;
+            for(int i=0; i<maxfront; i++) frontier_content[i] = 0;

         }
         //#end
         }
         //#end

+        constrain();

     }
 
     void constrain() {
     }
 
     void constrain() {

-        //#repeat contentwidth/contentheight colspan/rowspan col/row cols/rows minwidth/minheight \
-        //        textwidth/textheight maxwidth/maxheight cols/rows rowspan/colspan row/col rows/cols
-        // FIXME: inefficient
-        contentwidth = 0;
-        for(int i=0; i<rows; i++) {
-            int rowcontentwidth = 0;
-            for(Box child = firstPackedChild(); child != null; child = child.nextPackedSibling())
-                if (child.row <= i && (child.row + child.rowspan > i))
-                    rowcontentwidth += child.contentwidth;
-            contentwidth = max(contentwidth, rowcontentwidth);
-        }
-        contentwidth = bound(minwidth, max(font == null || text == null ? 0 : font.textwidth(text), contentwidth), maxwidth);
-        //#end               
+        //#repeat contentwidth/contentheight contentheight/contentwidth minwidth/minheight row/col col/row \
+        //        textwidth/textheight maxwidth/maxheight cols/rows rows/cols colspan/rowspan rowspan/colspan
+        contentwidth = bound(minwidth,
+                             max(contentwidth, font == null || text == null ? 0 : font.textwidth(text)),
+                             maxwidth);
+        //#end

     }
     
     void resize(LENGTH x, LENGTH y, LENGTH width, LENGTH height) {
     }
     
     void resize(LENGTH x, LENGTH y, LENGTH width, LENGTH height) {

@@ -306,17 +331,15 @@ 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);
     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);

-    int[] regions = new int[65535];
-    int[] regions_v = new int[65535];
+    private static int[] regions = new int[65535];
+    private static int[] regions_v = new int[65535];

 
     void place_children() {
         int numkids = 0; for(Box c = firstPackedChild(); c != null; c = c.nextPackedSibling()) numkids++;
         int numregions = 0, numregions_v = 0;
         //#repeat col/row colspan/rowspan contentwidth/contentheight width/height HSHRINK/VSHRINK numregions/numregions_v \
         //        maxwidth/maxheight cols/rows minwidth/minheight lp_h/lp lp_h/lp easy_width/easy_height regions/regions_v
 
     void place_children() {
         int numkids = 0; for(Box c = firstPackedChild(); c != null; c = c.nextPackedSibling()) numkids++;
         int numregions = 0, numregions_v = 0;
         //#repeat col/row colspan/rowspan contentwidth/contentheight width/height HSHRINK/VSHRINK numregions/numregions_v \
         //        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; */
-
+        if (numkids > 0 && cols > 1) do {

             // FIXME: numboxes^2, and damn ugly to boot
             for(Box c = firstPackedChild(); c != null; c = c.nextPackedSibling()) {
                 int target = c.col;
             // FIXME: numboxes^2, and damn ugly to boot
             for(Box c = firstPackedChild(); c != null; c = c.nextPackedSibling()) {
                 int target = c.col;

@@ -334,6 +357,7 @@ public final class Box extends JSScope implements Scheduler.Task {
             if (regions[numregions-1] == cols) numregions--;
             else regions[numregions] = cols;
 
             if (regions[numregions-1] == cols) numregions--;
             else regions[numregions] = cols;
 

+            /* boolean easy_width = contentwidth >= width; */

             /*
             for(Box c = firstPackedChild(); easy_width && c != null; c = c.nextPackedSibling()) {
                 if (c.contentwidth == c.maxwidth) continue;
             /*
             for(Box c = firstPackedChild(); easy_width && c != null; c = c.nextPackedSibling()) {
                 if (c.contentwidth == c.maxwidth) continue;

@@ -405,11 +429,30 @@ public final class Box extends JSScope implements Scheduler.Task {
                 lp_h.add_constraint(coeff, LinearProgramming.GE, avg * weight);
             }
 
                 lp_h.add_constraint(coeff, LinearProgramming.GE, avg * weight);
             }
 

-            int result = lp_h.solve();
-            if (result == LinearProgramming.UNBOUNDED)
-                Log.warn(this, "simplex solver claims unboundedness; this should never happen");
-            if (result != LinearProgramming.OPTIMAL)
-                Log.warn(this, "simplex solver claims infeasibility; this should never happen");
+            try {
+                int result = lp_h.solve();
+                switch(result) {
+                    case LinearProgramming.UNBOUNDED:
+                        Log.warn(this, "simplex solver claims unboundedness; this should never happen");
+                        break;
+                    case LinearProgramming.INFEASIBLE:
+                        Log.debug(this, "simplex solver claims infeasibility; this should never happen");
+                        break;
+                    case LinearProgramming.MILP_FAIL:
+                        Log.warn(this, "simplex solver claims MILP_FAIL; this should never happen");
+                        break;
+                    case LinearProgramming.RUNNING:
+                        Log.warn(this, "simplex solver still RUNNING; this should never happen");
+                        break;
+                    case LinearProgramming.FAILURE:
+                        Log.warn(this, "simplex solver claims FAILURE; this should never happen");
+                        break;
+                }
+            } catch (Error e) {
+                Log.warn(this, "got an Error in simplex solver; not sure why this happens");
+                return;
+            }
+

         } while(false);
         //#end
         
         } while(false);
         //#end
         

@@ -448,9 +491,9 @@ public final class Box extends JSScope implements Scheduler.Task {
                         }
                     }
                 }
                         }
                     }
                 }

-                diff = (child_width - min(child_width, child.test(HSHRINK) ? child.contentwidth : child.maxwidth));
+                diff = (child_width - (child.test(HSHRINK) ? child.contentwidth : min(child_width, child.maxwidth)));

                 child_x += (child.test(ALIGN_RIGHT) ? diff : child.test(ALIGN_LEFT) ? 0 : diff / 2);
                 child_x += (child.test(ALIGN_RIGHT) ? diff : child.test(ALIGN_LEFT) ? 0 : diff / 2);

-                child_width = min(child_width, child.test(HSHRINK) ? child.contentwidth : child.maxwidth);
+                child_width -= diff;

                 //#end
             }
             child.resize(child_x, child_y, child_width, child_height);
                 //#end
             }
             child.resize(child_x, child_y, child_width, child_height);

@@ -645,8 +688,8 @@ public final class Box extends JSScope implements Scheduler.Task {
         case "minheight": CHECKSET_INT(minheight); MARK_RESIZE;
                          if (parent == null && getSurface() != null)
                              getSurface().setMinimumSize(minwidth, minheight, minwidth != maxwidth || minheight != maxheight);
         case "minheight": CHECKSET_INT(minheight); MARK_RESIZE;
                          if (parent == null && getSurface() != null)
                              getSurface().setMinimumSize(minwidth, minheight, minwidth != maxwidth || minheight != maxheight);

-        case "colspan": CHECKSET_SHORT(colspan); MARK_REPACK_parent;
-        case "rowspan": CHECKSET_SHORT(rowspan); MARK_REPACK_parent;
+        case "colspan": if (toInt(value) <= 0) return; CHECKSET_SHORT(colspan); MARK_REPACK_parent;
+        case "rowspan": if (toInt(value) <= 0) return; CHECKSET_SHORT(rowspan); MARK_REPACK_parent;

         case "rows": CHECKSET_SHORT(rows); if (rows==0){set(FIXED, COLS);if(cols==0)cols=1;} else set(FIXED, ROWS); MARK_REPACK;
         case "cols": CHECKSET_SHORT(cols); if (cols==0){set(FIXED, ROWS);if(rows==0)rows=1;} else set(FIXED, COLS); MARK_REPACK;
         case "clip": CHECKSET_FLAG(CLIP); if (parent == null) dirty(); else parent.dirty();
         case "rows": CHECKSET_SHORT(rows); if (rows==0){set(FIXED, COLS);if(cols==0)cols=1;} else set(FIXED, ROWS); MARK_REPACK;
         case "cols": CHECKSET_SHORT(cols); if (cols==0){set(FIXED, ROWS);if(rows==0)rows=1;} else set(FIXED, COLS); MARK_REPACK;
         case "clip": CHECKSET_FLAG(CLIP); if (parent == null) dirty(); else parent.dirty();