From 07849159e3abf2aa6cb788538716b8d9f2717499 Mon Sep 17 00:00:00 2001 From: adam Date: Wed, 7 Apr 2004 10:57:49 +0000 Subject: [PATCH] major repack speedup darcs-hash:20040407105749-5007d-0a73c62baafe772efd99461cc0f0d7edde733045.gz --- src/org/ibex/Box.java | 111 ++++++++++++++++++++++++++++++++++--------------- 1 file changed, 77 insertions(+), 34 deletions(-) diff --git a/src/org/ibex/Box.java b/src/org/ibex/Box.java index 13c02ee..bb57d5a 100644 --- 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(); } - 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(); + contentwidth = 0; + contentheight = 0; 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; + 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 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; + rowwidth += front.contentwidth; // FIXME: suspect i = -1; continue; } @@ -245,28 +265,33 @@ public final class Box extends JSScope implements Scheduler.Task { } child.col = (short)col; child.row = (short)row; + maxrow = max(maxrow, child.row + child.rowspan); + contentwidth = max(contentwidth, rowwidth); + rowwidth = 0; lastpacked = child; - frontier[maxfront++] = childnum; + for(int i=0; i 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) { @@ -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); - 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 - 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; @@ -334,6 +357,7 @@ public final class Box extends JSScope implements Scheduler.Task { 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; @@ -405,11 +429,30 @@ public final class Box extends JSScope implements Scheduler.Task { 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 @@ -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_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); @@ -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 "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(); -- 1.7.10.4