// 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() {
//#repeat contentwidth/contentheight colspan/rowspan col/row cols/rows minwidth/minheight \
- // textwidth/textheight maxwidth/maxheight cols/rows
+ // textwidth/textheight maxwidth/maxheight cols/rows rowspan/colspan row/col rows/cols
// FIXME: inefficient
contentwidth = 0;
for(int i=0; i<rows; i++) {
}
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);
+ 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];
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;
+ 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; */
+
+ // FIXME: numboxes^2, and damn ugly to boot
+ for(Box c = firstPackedChild(); c != null; c = c.nextPackedSibling()) {
+ 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);
+ }
+ }
+ 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;
+ 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);
- 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);
+
+ // 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, 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
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;
- 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]);
+ if (cols == 1) {
+ child_x = 0;
+ child_width = width;
+ /*
+ } else if (easy_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]));
+ }
+ }
+ }
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);
fillcolor = newfillcolor;
} else if(value instanceof JS) {
texture = Picture.load((JS)value, this);
+ if (texture != null && texture.isLoaded) perform();
} else {
throw new JSExn("fill must be null, a String, or a stream, not a " + value.getClass());
}