custom simplex solver (post-experimental)

darcs-hash:20040411185431-5007d-b06d2158c4a2d967715fe77dc1ca3261685306b9.gz

diff --git a/Makefile b/Makefile
index 7fcbf5e..8a452d6 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -23,6 +23,7 @@ dist-clean:
        rm -rf .jikes .configure* .install* build .compile .build*
        find upstream -name config.cache -exec rm {} \;
        test -e upstream/nestedvm && make -C upstream/nestedvm clean
+       rm .install_nestedvm
 
 libwing_Linux := -Lupstream/install/i686-pc-linux-gnu/lib/
 libwing_Linux +=   upstream/install/i686-pc-linux-gnu/lib/libWINGs.a
@@ -147,7 +148,8 @@ build/class/org/ibex/translators/MIPSApps.class: build/mips/mipsapps.mips .insta
        mkdir -p build/java/org/ibex/translators
        @echo -e "\n\033[1mtranslating        .mips -> .class:  $<\033[0m"
        java -cp upstream/nestedvm/build:upstream/nestedvm/upstream/build/bcel-5.1/bcel-5.1.jar \
-               org.xwt.mips.Compiler org.ibex.translators.MIPSApps $< -o onepage,pagesize=8m -outfile $@
+               org.xwt.mips.Compiler org.ibex.translators.MIPSApps $< -outfile $@
+#-o onepage,pagesize=8m
 
 compile: .compile
 .compile: .download_nestedvm .download_bcel-5.1 $(java_sources) $(java_classes); touch $@

diff --git a/src/org/ibex/Box.java b/src/org/ibex/Box.java
index 9dcb020..6d74e69 100644 (file)
--- a/src/org/ibex/Box.java
+++ b/src/org/ibex/Box.java
@@ -292,84 +292,72 @@ public final class Box extends JSScope implements Scheduler.Task {
     }
     //#end
 
+    private static float[] sizes = new float[65535];
+    private static float[] sizes_v = new float[65535];
     void solve(boolean findMinimum) {
         int numkids = 0; for(Box c = firstPackedChild(); c != null; c = c.nextPackedSibling()) numkids++;
         //#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 \
-        //        computeRegions/computeRegions_v
-        if (numkids > 0) do {
-            computeRegions();
-            int nc = numregions * 3 + numkids * 2 + 3;
-            if (coeff == null || nc+1>coeff.length) coeff = new float[nc+1];
-            lp_h.init(nc);
-
-            for(int i=0; i<coeff.length; i++) coeff[i] = (float)0.0;
-            if (!findMinimum) {
-                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
+        //        computeRegions/computeRegions_v targetColumnSize/targetRowSize sizes/sizes_v
+        if (numkids == 0) {
+            if (findMinimum) contentwidth = 0;
+            else targetColumnSize = 0;
+        } else if (cols == 1) {
+            if (findMinimum) {
+                contentwidth = 0;
+                for(Box c = firstPackedChild(); c != null; c = c.nextPackedSibling())
+                    contentwidth = max(contentwidth, c.contentwidth);
             } else {
-                coeff[numregions*2+numkids] = (float)1.0;
+                targetColumnSize = width;
             }
-            lp_h.setObjective(coeff, false);
-
-            // 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;
-            if (!findMinimum) lp_h.add_constraint(coeff, Simplex.EQ, (float)width);
-            else              lp_h.add_constraint(coeff, Simplex.LE, (float)0);
-
-            int childnum = 0;
-            for(Box child = firstPackedChild(); child != null; child = child.nextPackedSibling()) {
-
-                // 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, Simplex.GE, (float)child.contentwidth);
-                if (!findMinimum) {
-                    // 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] = (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, Simplex.LE, (float)child_maxwidth);
+        } else if (cols > 1) do {
+            computeRegions();
+            int target = findMinimum ? 0 : Math.max(width, contentwidth);
+            // priority 0: (inviolable) honor minwidths
+            // priority 1: sum of columns no greater than parent
+            // priority 2: honor maxwidths
+            // priority 3: equalize columns
+            float targetColumnSize = target == 0 ? 0 : this.targetColumnSize;
+            float last_columnsize = 0;
+            float last_total = 0;
+            float total;
+            boolean first = true;
+            while(true) {
+                total = (float)0.0;
+                for(int r=0; r<numregions; r++) total += (sizes[r] = (float)(targetColumnSize * (regions[r+1]-regions[r])));
+                int minregion = 0;
+                for(Box child = firstPackedChild(); child != null; child = child.nextPackedSibling())
+                    for(int r=(child.col==0?0:minregion); r<numregions; r++) {
+                        if (regions[r+1] < child.col) continue;
+                        if (regions[r] >= min(child.col+child.colspan,cols)) { minregion = r; break; }
+                        total -= sizes[r];
+                        if (sizes[r] <= (float)(targetColumnSize*(regions[r+1]-regions[r])))
+                            if ((child.colspan * targetColumnSize) > (child.maxwidth + (float)0.5))
+                                sizes[r] = (float)Math.min(sizes[r], (regions[r+1]-regions[r])*(child.maxwidth/child.colspan));
+                        if ((child.colspan * targetColumnSize) < (child.contentwidth - (float)0.5))
+                            sizes[r] = (float)Math.max(sizes[r], (regions[r+1]-regions[r])*(child.contentwidth/child.colspan));
+                        total += sizes[r];
                     }
+                float save = targetColumnSize;
+                if (Math.abs(total - target) <= (float)1.0) break;
+                if (!first) {
+                    if (Math.abs(total - last_total) <= (float)1.0) break;
+                } else {
+                    last_columnsize = ((total - target) / (float)cols) + targetColumnSize;
                 }
-                childnum++;
-            }
-
-            if (!findMinimum) {
-                // priority 3: equalize columns
-                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, Simplex.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, Simplex.GE, avg * weight);
-                }
-            }
-
-            try { switch(lp_h.solve()) {
-                case Simplex.UNBOUNDED: Log.warn(this, "simplex claims unboundedness; this should never happen"); break;
-                case Simplex.INFEASIBLE: Log.debug(this, "simplex claims infeasibility; this should never happen"); break;
-                case Simplex.MILP_FAIL: Log.warn(this, "simplex claims MILP_FAIL; this should never happen"); break;
-                case Simplex.RUNNING: Log.warn(this, "simplex still RUNNING; this should never happen"); break;
-                case Simplex.FAILURE: Log.warn(this, "simplex 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;
+                if (total < target)      targetColumnSize += Math.abs((last_columnsize - targetColumnSize) / (float)1.1);
+                else if (total > target) targetColumnSize -= Math.abs((last_columnsize - targetColumnSize) / (float)1.1);
+                last_columnsize = save;
+                last_total = total;
+                first = false;
             }
-
-            if (findMinimum) contentwidth = Math.round(lp_h.solution[lp_h.rows + (2*numregions + numkids + 1)]);
+            if (findMinimum) contentwidth = Math.round(total);
+            else this.targetColumnSize = targetColumnSize;
         } while(false);
         //#end
     }
+    private float targetColumnSize = (float)0.0;
+    private float targetRowSize = (float)0.0;
 
     void place() {
         solve(false);
@@ -390,18 +378,16 @@ public final class Box extends JSScope implements Scheduler.Task {
                 //#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 \
-                //        numregions/numregions_v regions/regions_v
-                child_width = 0;
+                //        numregions/numregions_v regions/regions_v targetColumnSize/targetRowSize sizes/sizes_v
                 child_x = 0;
                 if (cols == 1) {
-                    child_x = 0;
                     child_width = width;
                 } else {
-                    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]));
+                    child_width = 0;
+                    for(int r=0; r<numregions; r++) {
+                        if (regions[r] < child.col) child_x += Math.round(sizes[r]);
+                        else if (regions[r] < child.col+child.colspan) child_width += Math.round(sizes[r]);
+                    }
                 }
                 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);