another performance improvement for the simplex solver
[org.ibex.core.git] / src / org / ibex / Box.java
index 1301639..2ada11f 100644 (file)
@@ -14,7 +14,7 @@ package org.ibex;
 import java.util.*;
 import org.ibex.js.*;
 import org.ibex.util.*;
-import org.xwt.translators.*;
+import org.ibex.translators.*;
 
 /**
  *  <p>
@@ -152,6 +152,8 @@ public final class Box extends JSScope implements Scheduler.Task {
     private short col = 0;
     public LENGTH x = 0;
     public LENGTH y = 0;
+    public LENGTH ax = 0;   // FEATURE: roll these into x/y; requires lots of changes
+    public LENGTH ay = 0;   // FEATURE: roll these into x/y; requires lots of changes; perhaps y()?
     public LENGTH width = 0;
     public LENGTH height = 0;
     private LENGTH contentwidth = 0;      // == max(minwidth, textwidth, sum(child.contentwidth))
@@ -166,6 +168,7 @@ public final class Box extends JSScope implements Scheduler.Task {
 
     // Instance Methods /////////////////////////////////////////////////////////////////////
 
+    public final int fontSize() { return font == null ? DEFAULT_FONT.pointsize : font.pointsize; }
 
     /** invoked when a resource needed to render ourselves finishes loading */
     public void perform() throws JSExn {
@@ -174,9 +177,10 @@ public final class Box extends JSScope implements Scheduler.Task {
         // as external events have occured, check the state of box
         if (texture != null) {
             if (texture.isLoaded) { minwidth = min(texture.width, maxwidth); minheight = min(texture.height, maxheight); }
-            else { JS res = texture.stream; texture = null; throw new JSExn("image not found: "+res); }
+            else { JS res = texture.stream; texture = null; throw new JSExn("image not found: "+res.unclone()); }
+        } else {
+            Log.warn(Box.class, "perform() called with null texture");
         }
-
         MARK_REPACK;
         MARK_REFLOW;
         MARK_RESIZE;
@@ -210,11 +214,6 @@ public final class Box extends JSScope implements Scheduler.Task {
 
     // static stuff so we don't have to keep reallocating
     private static int[] numRowsInCol = new int[65535];
-    private static LENGTH[] colWidth = new LENGTH[65535];
-    private static LENGTH[] colMaxWidth = new LENGTH[65535];
-    private static LENGTH[] rowHeight = new LENGTH[65535];
-    private static LENGTH[] rowMaxHeight = new LENGTH[65535];
-    static { for(int i=0; i<rowMaxHeight.length; i++) { rowMaxHeight[i] = MAX_LENGTH; colMaxWidth[i] = MAX_LENGTH; } }
 
     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(); }
@@ -241,13 +240,21 @@ public final class Box extends JSScope implements Scheduler.Task {
             for(int i=0; i<cols; i++) numRowsInCol[i] = 0;
         }
         //#end
+        constrain();
+    }
 
-        //#repeat contentwidth/contentheight colWidth/rowHeight colspan/rowspan col/row cols/rows minwidth/minheight \
-        //        textwidth/textheight maxwidth/maxheight
+    void constrain() {
+        //#repeat contentwidth/contentheight colspan/rowspan col/row cols/rows minwidth/minheight \
+        //        textwidth/textheight maxwidth/maxheight cols/rows
+        // FIXME: inefficient
         contentwidth = 0;
-        for(Box child = firstPackedChild(); child != null; child = child.nextPackedSibling())
-            colWidth[child.col] = max(colWidth[child.col], child.contentwidth / child.colspan);
-        for(int i=0; i<cols; i++) { contentwidth += colWidth[i]; colWidth[i] = 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               
     }
@@ -286,68 +293,92 @@ public final class Box extends JSScope implements Scheduler.Task {
         }
     }
 
-    void resize_children() {
-
-        //#repeat col/row colspan/rowspan contentwidth/contentheight x/y width/height colMaxWidth/rowMaxHeight colWidth/rowHeight \
-        //        HSHRINK/VSHRINK maxwidth/maxheight cols/rows minwidth/minheight colWidth/rowHeight x_slack/y_slack
-        // PHASE 1: compute column min/max sizes
-        int x_slack = width;
-        for(int i=0; i<cols; i++) x_slack -= colWidth[i];
-        for(Box child = firstPackedChild(); child != null; child = child.nextPackedSibling())
-            for(int i=child.col; i < child.col + child.colspan; i++) {
-                x_slack += colWidth[i];
-                colWidth[i] = max(colWidth[i], child.contentwidth / child.colspan);
-                x_slack -= colWidth[i];
-                colMaxWidth[i] = min(colMaxWidth[i], child.test(HSHRINK) ? child.contentwidth : child.maxwidth) / child.colspan;
+    private static float[] coeff = null;
+    private static LinearProgramming.Simplex lp_h = new LinearProgramming.Simplex(50, 50, 300);
+    private static LinearProgramming.Simplex lp_v = new LinearProgramming.Simplex(50, 50, 300);
+
+    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 \
+        //        maxwidth/maxheight cols/rows minwidth/minheight lp_h/lp_v lp_h/lp_v
+        do {
+            int nc = numkids * 2 + cols * 3 + 1 + 2;
+            if (coeff == null || nc+1>coeff.length) coeff = new float[nc+1];
+            lp_h.init(nc, nc);
+
+            // objective function
+            for(int i=0; i<coeff.length; i++) coeff[i] = (float)0.0;
+            coeff[cols*2+numkids] = (float)-100000.0;                             // priority 1: sum of columns equals parent
+            for(int i=cols*2; i<cols*2+numkids; i++) coeff[i] = (float)-1000.0;   // priority 2: honor maxwidths
+            for(int i=cols; i<cols*2; i++) coeff[i] = (float)(-1.0);              // priority 3: equalize columns
+            lp_h.setObjective(coeff, true);
+
+            // 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;
+            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;
+            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;
+                lp_h.add_constraint(coeff, LinearProgramming.GE, (float)child.contentwidth);
+                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 j=0; j<coeff.length; j++) coeff[j] = (float)0.0;
+                childnum++;
             }
-        
-        // PHASE 2: hand out slack
-        for(int startslack = 0; x_slack > 0 && cols > 0 && startslack != x_slack;) {
-            int increment = max(1, x_slack / cols);
-            startslack = x_slack;
-            for(short col=0; col < cols; col++) {
-                // FIXME: double check this
-                int diff = min(min(colMaxWidth[col], colWidth[col] + increment) - colWidth[col], x_slack);
-                x_slack -= diff;
-                colWidth[col] += diff;
+
+            // priority 3: equalize columns
+            for(int i=0 ; i<cols; i++) {
+                lp_h.set_lowbo(i+1, (float)0.0);
+                lp_h.bound_difference(i, cols+i, ((float)width)/((float)cols), LinearProgramming.LE, coeff);
+                lp_h.bound_sum(       i, cols+i, ((float)width)/((float)cols), LinearProgramming.GE, coeff);
             }
-        }   
-        //#end
 
-        // Phase 3: assign childrens' actual sizes
+            lp_h.solve();
+        } while(false);
+        //#end
+        
         for(Box child = getChild(0); child != null; child = child.nextSibling()) {
             if (!child.test(VISIBLE)) continue;
             int child_width, child_height, child_x, child_y;
             if (!child.test(PACKED)) {
-                child_x = child.x;
-                child_y = child.y;
-                child_width = child.test(HSHRINK) ? child.contentwidth : min(child.maxwidth, width - child_x);
-                child_height = child.test(VSHRINK) ? child.contentheight : min(child.maxheight, height - child_y);
+                child_width = child.test(HSHRINK) ? child.contentwidth : min(child.maxwidth, width - Math.abs(child.ax));
+                child_height = child.test(VSHRINK) ? child.contentheight : min(child.maxheight, height - Math.abs(child.ay));
                 child_width = max(child.minwidth, child_width);
                 child_height = max(child.minheight, child_height);
+                int gap_x = width - child_width;
+                int gap_y = height - child_height;
+                child_x = child.ax + (child.test(ALIGN_RIGHT) ? gap_x : !child.test(ALIGN_LEFT) ? gap_x / 2 : 0);
+                child_y = child.ay + (child.test(ALIGN_BOTTOM) ? gap_y : !child.test(ALIGN_TOP) ? gap_y / 2 : 0);
             } else {
-                int unbounded;
+                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 \
-                //        colWidth/rowHeight child_width/child_height ALIGN_RIGHT/ALIGN_BOTTOM ALIGN_LEFT/ALIGN_TOP
-                unbounded = 0;
-                for(int i = child.col; i < child.col + child.colspan; i++) unbounded += colWidth[i];
-                child_width = min(unbounded, child.test(HSHRINK) ? child.contentwidth : child.maxwidth);
-                child_x = test(ALIGN_RIGHT) ? x_slack : test(ALIGN_LEFT) ? 0 : x_slack / 2;
-                for(int i=0; i < child.col; i++) child_x += colWidth[i];
-                if (child_width > unbounded) child_x -= (child_width - unbounded) / 2;
+                //        child_width/child_height ALIGN_RIGHT/ALIGN_BOTTOM ALIGN_LEFT/ALIGN_TOP lp_h/lp_v
+                child_width = 0;
+                child_x = 0;
+                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]);
+                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);
+                child_width = min(child_width, child.test(HSHRINK) ? child.contentwidth : child.maxwidth);
                 //#end
             }
             child.resize(child_x, child_y, child_width, child_height);
         }
 
-        // cleanup
-        for(int i=0; i<cols; i++) { colWidth[i] = 0; colMaxWidth[i] = MAX_LENGTH; }
-        for(int i=0; i<rows; i++) { rowHeight[i] = 0; rowMaxHeight[i] = MAX_LENGTH; }
-
         for(Box child = getChild(0); child != null; child = child.nextSibling())
-            if (test(VISIBLE))
-                child.resize_children();
+            if (child.test(VISIBLE) && child.treeSize() > 0)
+                child.place_children();
     }
 
 
@@ -361,10 +392,9 @@ public final class Box extends JSScope implements Scheduler.Task {
         int globaly = parenty + (parent == null ? 0 : y);
 
         // intersect the x,y,w,h rendering window with ourselves; quit if it's empty
-
         if (test(CLIP)) {
-            cx1 = max(cx1, parent == null ? 0 : globalx);
-            cy1 = max(cy1, parent == null ? 0 : globaly);
+            cx1 = max(cx1, globalx);
+            cy1 = max(cy1, globaly);
             cx2 = min(cx2, globalx + width);
             cy2 = min(cy2, globaly + height);
             if (cx2 <= cx1 || cy2 <= cy1) return;
@@ -378,10 +408,15 @@ public final class Box extends JSScope implements Scheduler.Task {
             for(int x = globalx; x < cx2; x += texture.width)
                 for(int y = globaly; y < cy2; y += texture.height)
                     buf.drawPicture(texture, x, y, cx1, cy1, cx2, cy2);
-
-        if (text != null && !text.equals("") && font != null)
-            if (font.rasterizeGlyphs(text, buf, strokecolor, globalx, globaly, cx1, cy1, cx2, cy2, null) == -1)
-                font.rasterizeGlyphs(text, buf, strokecolor, globalx, globaly, cx1, cy1, cx2, cy2, this);
+        if (text != null && !text.equals("") && font != null) {
+            int gap_x = width - font.textwidth(text);
+            int gap_y = height - font.textheight(text);
+            int text_x = globalx + (test(ALIGN_RIGHT) ? gap_x : !test(ALIGN_LEFT) ? gap_x/2 : 0);
+            int text_y = globaly + (test(ALIGN_BOTTOM) ? gap_y : !test(ALIGN_TOP) ? gap_y/2 : 0);
+            if (font.rasterizeGlyphs(text, buf, strokecolor, text_x, text_y, cx1, cy1, cx2, cy2, null) == -1)
+                font.rasterizeGlyphs(text, buf, strokecolor, text_x, text_y, cx1, cy1, cx2, cy2, this);
+        }
 
         for(Box b = getChild(0); b != null; b = b.nextSibling())
             b.render(globalx, globaly, cx1, cy1, cx2, cy2, buf, null);
@@ -396,13 +431,28 @@ public final class Box extends JSScope implements Scheduler.Task {
     public int localToGlobalY(int y) { return parent == null ? y : parent.globalToLocalY(y + this.y); }
     
     public Object callMethod(Object method, Object a0, Object a1, Object a2, Object[] rest, int nargs) throws JSExn {
-        if (nargs != 1 || !"indexof".equals(method)) return super.callMethod(method, a0, a1, a2, rest, nargs);
-        Box b = (Box)a0;
-        if (b.parent != this)
-            return (redirect == null || redirect == this) ?
-                N(-1) :
-                redirect.callMethod(method, a0, a1, a2, rest, nargs);
-        return N(b.getIndexInParent());
+        switch (nargs) {
+            case 1: {
+                //#switch(method)
+                case "indexof":
+                    Box b = (Box)a0;
+                    if (b.parent != this)
+                        return (redirect == null || redirect == this) ?
+                            N(-1) :
+                            redirect.callMethod(method, a0, a1, a2, rest, nargs);
+                    return N(b.getIndexInParent());
+
+                case "distanceto":
+                    Box b = (Box)a0;
+                    JS ret = new JS();
+                    ret.put("x", N(b.localToGlobalX(0) - localToGlobalX(0)));
+                    ret.put("y", N(b.localToGlobalY(0) - localToGlobalY(0)));
+                    return ret;
+
+                //#end
+            }
+        }
+        return super.callMethod(method, a0, a1, a2, rest, nargs);
     }
 
     public Enumeration keys() { throw new Error("you cannot apply for..in to a " + this.getClass().getName()); }
@@ -426,6 +476,7 @@ public final class Box extends JSScope implements Scheduler.Task {
         //#switch(name)
         case "surface": return parent == null ? null : parent.getAndTriggerTraps("surface");
         case "indexof": return METHOD;
+        case "distanceto": return METHOD;
         case "text": return text;
         case "path": throw new JSExn("cannot read from the path property");
         case "fill": return colorToString(fillcolor);
@@ -535,15 +586,36 @@ public final class Box extends JSScope implements Scheduler.Task {
         case "Minimized": if (parent == null && getSurface() != null) getSurface().minimized = toBoolean(value);  // FEATURE
         case "Maximized": if (parent == null && getSurface() != null) getSurface().maximized = toBoolean(value);  // FEATURE
         case "Close": if (parent == null && getSurface() != null) getSurface().dispose(true);
-        case "redirect": if (redirect == this) redirect = (Box)value; else Log.info(this, "redirect can only be set once");
+        case "redirect":
+            if (value == null) { redirect = null; return; }
+            for(Box cur = (Box)value; cur != null; cur = cur.parent)
+                if (cur == redirect) {
+                    redirect = (Box)value;
+                    return;
+                }
+            JS.error("redirect can only be set to a descendant of its current value");
         case "font":
             if(!(value instanceof Stream)) throw new JSExn("You can only put streams to the font property");
             font = value == null ? null : Font.getFont((Stream)value, font == null ? 10 : font.pointsize);
             MARK_RESIZE;
             dirty();
         case "fontsize": font = Font.getFont(font == null ? null : font.stream, toInt(value)); MARK_RESIZE; dirty();
-        case "x": if (parent==null && Surface.fromBox(this)!=null) { CHECKSET_INT(x); } else { if (test(PACKED) && parent != null) return; dirty(); CHECKSET_INT(x); dirty(); MARK_RESIZE; dirty(); }
-        case "y": if (parent==null && Surface.fromBox(this)!=null) { CHECKSET_INT(y); } else { if (test(PACKED) && parent != null) return; dirty(); CHECKSET_INT(y); dirty(); MARK_RESIZE; dirty(); }
+        case "x": if (parent==null && Surface.fromBox(this)!=null) {
+            CHECKSET_INT(x);
+        } else {
+            if (test(PACKED) && parent != null) return;
+            dirty(); CHECKSET_INT(ax);
+            dirty(); MARK_RESIZE;
+            dirty();
+        }
+        case "y": if (parent==null && Surface.fromBox(this)!=null) {
+            CHECKSET_INT(y);
+        } else {
+            if (test(PACKED) && parent != null) return;
+            dirty(); CHECKSET_INT(ay);
+            dirty(); MARK_RESIZE;
+            dirty();
+        }
         case "titlebar":
             if (getSurface() != null && value != null) getSurface().setTitleBarText(JS.toString(value));
             super.put(name,value);
@@ -563,8 +635,11 @@ public final class Box extends JSScope implements Scheduler.Task {
         case "KeyPressed":    if (!test(STOP_UPWARD_PROPAGATION) && parent != null) parent.putAndTriggerTraps(name, value);
         case "KeyReleased":   if (!test(STOP_UPWARD_PROPAGATION) && parent != null) parent.putAndTriggerTraps(name, value);
         case "Move":          if (!test(STOP_UPWARD_PROPAGATION) && parent != null) parent.putAndTriggerTraps(name, value);
-        case "Enter":         if (!test(STOP_UPWARD_PROPAGATION) && parent != null) parent.putAndTriggerTraps(name, value);
-        case "Leave":         if (!test(STOP_UPWARD_PROPAGATION) && parent != null) parent.putAndTriggerTraps(name, value);
+
+        case "HScroll":       if (!test(STOP_UPWARD_PROPAGATION) && parent != null)
+            parent.putAndTriggerTraps(name, N(((Number)value).floatValue() * ((float)parent.fontSize()) / ((float)fontSize())));
+        case "VScroll":       if (!test(STOP_UPWARD_PROPAGATION) && parent != null)
+            parent.putAndTriggerTraps(name, N(((Number)value).floatValue() * ((float)parent.fontSize()) / ((float)fontSize())));
 
         case "_Move":         propagateDownward(name, value, false);
         case "_Press1":       propagateDownward(name, value, false);
@@ -581,11 +656,15 @@ public final class Box extends JSScope implements Scheduler.Task {
         case "_DoubleClick3": propagateDownward(name, value, false);
         case "_KeyPressed":   propagateDownward(name, value, false);
         case "_KeyReleased":  propagateDownward(name, value, false);
+        case "_HScroll":      propagateDownward(name, value, false);
+        case "_VScroll":      propagateDownward(name, value, false);
 
         case "PosChange":     return;
         case "SizeChange":    return;
         case "childadded":    return;
         case "childremoved":  return;
+        case "Enter":         return;
+        case "Leave":         return;
 
         case "thisbox":       if (value == null) removeSelf();
 
@@ -629,10 +708,11 @@ public final class Box extends JSScope implements Scheduler.Task {
         set(CURSOR);
         boxToCursor.put(this, value);
         Surface surface = getSurface();
-        String tempcursor = surface.cursor;
-        // FIXME
-        //Move(surface.mousex, surface.mousey, surface.mousex, surface.mousey);
-        if (surface.cursor != tempcursor) surface.syncCursor();
+        if (surface != null) {
+            String tempcursor = surface.cursor;
+            propagateDownward(null, null, false);
+            if (surface.cursor != tempcursor) surface.syncCursor();
+        }
     }
 
     private void setFill(Object value) throws JSExn {
@@ -666,29 +746,42 @@ public final class Box extends JSScope implements Scheduler.Task {
         int y = globalToLocalY(getSurface()._mousey);
         boolean wasinside = test(MOUSEINSIDE);
         boolean isinside = test(VISIBLE) && inside(x, y) && !obscured;
-        if (!wasinside && isinside) { set(MOUSEINSIDE);   putAndTriggerTrapsAndCatchExceptions("Enter", T); }
-        if (wasinside && !isinside) { clear(MOUSEINSIDE); putAndTriggerTrapsAndCatchExceptions("Leave", T); }
+        if (!wasinside && isinside) {
+            set(MOUSEINSIDE);
+            putAndTriggerTrapsAndCatchExceptions("Enter", T);
+        }
+        if (isinside && test(CURSOR)) getSurface().cursor = (String)boxToCursor.get(this);
+        if (wasinside && !isinside) {
+            clear(MOUSEINSIDE);
+            putAndTriggerTrapsAndCatchExceptions("Leave", T);
+        }
 
         boolean found = false;
         if (wasinside || isinside)
             for(Box child = getChild(treeSize() - 1); child != null; child = child.prevSibling()) {
                 boolean save_stop = child.test(STOP_UPWARD_PROPAGATION);
+                Object value2 = value;
+                if (name.equals("_HScroll") || name.equals("_VScroll"))
+                    value2 = N(((Number)value).floatValue() * ((float)child.fontSize()) / (float)fontSize());
                 if (obscured || !child.inside(x - child.x, y - child.y)) {
-                    child.propagateDownward(name, value, true);
+                    child.propagateDownward(name, value2, true);
                 } else try {
                     found = true;
                     child.clear(STOP_UPWARD_PROPAGATION);
-                    child.putAndTriggerTrapsAndCatchExceptions(name, value);
+                    if (name != null) child.putAndTriggerTrapsAndCatchExceptions(name, value2);
+                    else child.propagateDownward(name, value2, obscured);
                 } finally {
                     if (save_stop) child.set(STOP_UPWARD_PROPAGATION); else child.clear(STOP_UPWARD_PROPAGATION);
                 }
                 if (child.inside(x - child.x, y - child.y))
-                    if (name.equals("_Move")) obscured = true;
+                    if (name != null && name.equals("_Move")) obscured = true;
                     else break;
             }
 
         if (!obscured && !found)
-            if (!name.equals("_Move") || wasinside) putAndTriggerTrapsAndCatchExceptions(name.substring(1), value);
+            if ("_Move".equals(name) || wasinside)
+                if (name != null)
+                    putAndTriggerTrapsAndCatchExceptions(name.substring(1), value);
     }
 
     private static int stringToColor(String s) {