simplex optimization: make place_children() run in O(numkids) rather than O(numcols^2)

darcs-hash:20040407065511-5007d-b5fa5c1fb1ec90357a2a191486f0c86836f4df19.gz

diff --git a/src/org/ibex/Box.java b/src/org/ibex/Box.java
index 59d4ca7..f680f20 100644 (file)
--- a/src/org/ibex/Box.java
+++ b/src/org/ibex/Box.java
@@ -295,61 +295,104 @@ 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_v = 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];
 
     void place_children() {
         int numkids = 0; for(Box c = firstPackedChild(); c != null; c = c.nextPackedSibling()) numkids++;
-        //#repeat col/row colspan/rowspan contentwidth/contentheight width/height HSHRINK/VSHRINK \
-        //        maxwidth/maxheight cols/rows minwidth/minheight lp_h/lp_v lp_h/lp_v
-       if (cols > 1) {
-            int nc = numkids * 2 + cols * 3 + 1 + 2;
+        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; */
+            for(Box c = firstPackedChild(); c != null; c = c.nextPackedSibling()) {
+                breakpoints[c.col] = true;
+                breakpoints[min(cols, c.col+c.colspan)] = true;
+            }
+            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;
+            /*
+            for(Box c = firstPackedChild(); easy_width && c != null; c = c.nextPackedSibling()) {
+                if (c.contentwidth == c.maxwidth) continue;
+                if (c.maxwidth == Integer.MAX_VALUE) continue;
+                easy_width = false;
+            }
+            if (easy_width) for(int i=0; i<cols; i++) {
+                easy_width = false;
+                boolean good = true;
+                for(Box c = firstPackedChild(); good && c != null; c = c.nextPackedSibling())
+                    if (c.col <= i && c.col + c.colspan > i && c.maxwidth < Integer.MAX_VALUE)
+                        good = false;
+                if (good) { easy_width = true; break; }
+            }
+            if (easy_width) break;
+            */
+            int nc = numregions * 2 + numkids + 1;
             if (coeff == null || nc+1>coeff.length) coeff = new float[nc+1];
             lp_h.init(nc);
 
-            // objective function
             for(int i=0; i<coeff.length; i++) coeff[i] = (float)0.0;
-            coeff[cols*2+numkids] = (float)10000.0;                              // priority 1: sum of columns equals parent
-            for(int i=cols*2; i<cols*2+numkids; i++) coeff[i] = (float)100.0;    // priority 2: honor maxwidths
-            for(int i=cols; i<cols*2; i++) coeff[i] = (float)(1.0);              // priority 3: equalize columns
+            coeff[numregions*2+numkids] = (float)10000.0;               // priority 1: sum of columns no greater than parent
+            for(int i=numregions*2; i<numregions*2+numkids; i++) coeff[i] = (float)100.0;  // priority 2: honor maxwidths
+            for(int i=numregions; i<numregions*2; i++) coeff[i] = (float)(0.1);            // priority 3: equalize columns
             lp_h.setObjective(coeff, false);
+            
+            for(int i=0; i<numregions; i++) lp_h.set_lowbo(i+1, (float)0.0); // invariant: columns cannot have negative size
 
-            // priority 1: sum of columns at least as big as parent
-            for(int i=0; i<coeff.length; i++) coeff[i] = (i<cols) ? (float)1.0 : (float)0.0;
+            // invariant: columns must be at least as large as parent
+            for(int i=0; i<coeff.length; i++) coeff[i] = (i<numregions) ? (float)(regions[i+1] - regions[i]) : (float)0.0;
             lp_h.add_constraint(coeff, LinearProgramming.GE, (float)width);
-            for(int i=0; i<coeff.length; i++) coeff[i] = (i<cols) ? (float)1.0 : (float)0.0;
-            coeff[cols*2+numkids] = (float)1.0;
+
+            // priority 1: sum of columns as close to parent's width as possible
+            for(int i=0; i<coeff.length; i++) coeff[i] = (i<numregions) ? (float)(regions[i+1] - regions[i]) : (float)0.0;
+            coeff[numregions*2+numkids] = (float)-1.0;
             lp_h.add_constraint(coeff, LinearProgramming.EQ, (float)width);
 
-            // priority 2: honor maxwidths
             int childnum = 0;
             for(Box child = firstPackedChild(); child != null; child = child.nextPackedSibling()) {
-                for(int i=0; i<coeff.length; i++)
-                    coeff[i] = (i>=child.col && i<min(child.colspan+child.col, cols)) ? (float)1.0 : (float)0.0;
+
+                // invariant: honor minwidths
+                for(int i=0; i<coeff.length; i++) coeff[i] = (float)0.0;
+                for(int r=0; r<numregions; r++)
+                    if (regions[r] >= child.col && regions[r+1] <= min(child.col+child.colspan,cols))
+                        coeff[r] = (float)(regions[r+1] - regions[r]);
                 lp_h.add_constraint(coeff, LinearProgramming.GE, (float)child.contentwidth);
+
+                // priority 2: honor maxwidths
                 int child_maxwidth = child.test(HSHRINK) ? min(child.maxwidth, child.contentwidth) : child.maxwidth;
                 if (child_maxwidth < Integer.MAX_VALUE) {
-                    for(int i=0; i<coeff.length; i++)
-                        coeff[i] = (i>=child.col && i<min(child.colspan+child.col, cols)) ? (float)1.0 : (float)0.0;
-                    coeff[cols*2+childnum] = (float)-1.0;
-                    lp_h.add_constraint(coeff, LinearProgramming.EQ, (float)child_maxwidth);
+                    for(int i=0; i<coeff.length; i++) coeff[i] = (float)0.0;
+                    for(int r=0; r<numregions; r++)
+                        if (regions[r] >= child.col && regions[r+1] <= min(child.col+child.colspan,cols))
+                            coeff[r] = (float)(regions[r+1] - regions[r]);
+                    coeff[numregions*2+childnum] = (float)-1.0;
+                    lp_h.add_constraint(coeff, LinearProgramming.LE, (float)child_maxwidth);
                 }
-                for(int j=0; j<coeff.length; j++) coeff[j] = (float)0.0;
+
                 childnum++;
             }
 
             // priority 3: equalize columns
-            for(int i=0 ; i<cols; i++) lp_h.set_lowbo(i+1, (float)0.0);
-            for(int i=0 ; i<cols; i++) {
-                for(int j=0 ; j<i; j++) {
-                    for(int k=0; k<coeff.length; k++) coeff[k] = (float)(k==i?1.0:k==j?-1.0:k==(cols+1)?-1.0:0.0);
-                    lp_h.add_constraint(coeff, LinearProgramming.LE, 0);
-                    for(int k=0; k<coeff.length; k++) coeff[k] = (float)(k==i?1.0:k==j?-1.0:k==(cols+1)?1.0:0.0);
-                    lp_h.add_constraint(coeff, LinearProgramming.GE, 0);
-                }
+            float avg = ((float)width)/((float)numregions);
+            for(int r=0; r<numregions; r++) {
+                float weight = (float)(regions[r+1] - regions[r]);
+                for(int k=0; k<coeff.length; k++) coeff[k] = (float)(k==r?weight:k==(numregions+r)?-1.0:0.0);
+                lp_h.add_constraint(coeff, LinearProgramming.LE, avg * weight);
+                for(int k=0; k<coeff.length; k++) coeff[k] = (float)(k==r?weight:k==(numregions+r)?1.0:0.0);
+                lp_h.add_constraint(coeff, LinearProgramming.GE, avg * weight);
             }
-            for(int i=0; i<coeff.length; i++) coeff[i] = (float)0.0;
-            lp_h.solve();
-        }
+
+            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");
+        } while(false);
         //#end
         
         for(Box child = getChild(0); child != null; child = child.nextSibling()) {
@@ -368,17 +411,24 @@ public final class Box extends JSScope implements Scheduler.Task {
                 int diff;
                 //#repeat col/row colspan/rowspan contentwidth/contentheight width/height colMaxWidth/rowMaxHeight \
                 //        child_x/child_y x/y HSHRINK/VSHRINK maxwidth/maxheight cols/rows minwidth/minheight x_slack/y_slack \
-                //        child_width/child_height ALIGN_RIGHT/ALIGN_BOTTOM ALIGN_LEFT/ALIGN_TOP lp_h/lp_v
+                //        child_width/child_height ALIGN_RIGHT/ALIGN_BOTTOM ALIGN_LEFT/ALIGN_TOP lp_h/lp easy_width/easy_height \
+                //        numregions/numregions_v regions/regions_v
                 child_width = 0;
                 child_x = 0;
                 if (cols == 1) {
                     child_x = 0;
                     child_width = width;
+                    /*
+                } else if (easy_width) {
+                    */
                 } else {
-                    for(int i=0; i < child.col; i++)
-                        child_x += Math.round(lp_h.solution[lp_h.rows+i+1]);
-                    for(int i = child.col; i<child.col + child.colspan; i++)
-                        child_width += Math.round(lp_h.solution[lp_h.rows+i+1]);
+                    for(int r=0; r<numregions; r++) {
+                        if (regions[r] >= child.col && regions[r+1] <= min(child.col+child.colspan,cols)) {
+                            child_width += Math.round(lp_h.solution[lp_h.rows+r+1] * (regions[r+1] - regions[r]));
+                        } else if (regions[r+1] <= child.col) {
+                            child_x += Math.round(lp_h.solution[lp_h.rows+r+1] * (regions[r+1] - regions[r]));
+                        }
+                    }
                 }
                 diff = (child_width - min(child_width, child.test(HSHRINK) ? child.contentwidth : child.maxwidth));
                 child_x += (child.test(ALIGN_RIGHT) ? diff : child.test(ALIGN_LEFT) ? 0 : diff / 2);