* SizeChanges trigger an Surface.abort; if rendering were done in the same
* pass, rendering work done prior to the Surface.abort would be wasted.
*/
-public abstract class Box extends JSScope implements JSTrap.JSTrappable {
+public final class Box extends JSScope {
// Macros //////////////////////////////////////////////////////////////////////
Box parent = null;
Box redirect = this;
- int flags = VISIBLE | PACKED;
+ int flags = VISIBLE | PACKED | REPACK | REFLOW | RESIZE | FIXED /* ROWS */;
private String text = null;
private Font font = null;
- private Picture texture;
+ private Picture.Holder texture;
private short strokewidth = 1;
private int fillcolor = 0x00000000;
private int strokecolor = 0xFF000000;
// specified directly by user
public LENGTH minwidth = 0;
- public LENGTH maxwidth = 0;
+ public LENGTH maxwidth = MAX_LENGTH;
public LENGTH minheight = 0;
- public LENGTH maxheight = 0;
+ public LENGTH maxheight = MAX_LENGTH;
private short rows = 1;
private short cols = 0;
private short rowspan = 1;
// FEATURE: use cx2/cy2 format
/** Adds the intersection of (x,y,w,h) and the node's current actual geometry to the Surface's dirty list */
- public final void dirty() { dirty(0, 0, width, height); }
- public final void dirty(int x, int y, int w, int h) {
+ public void dirty() { dirty(0, 0, width, height); }
+ public void dirty(int x, int y, int w, int h) {
for(Box cur = this; cur != null; cur = cur.parent) {
if (!cur.test(NOCLIP)) {
w = min(x + w, cur.width) - max(x, 0);
}
}
- public void putAndTriggerJSTraps(Object key, Object value) {
- }
-
/** update MOUSEINSIDE, check for Enter/Leave/Move */
void Move(int oldmousex, int oldmousey, int mousex, int mousey) { Move(oldmousex, oldmousey, mousex, mousey, false); }
void Move(int oldmousex, int oldmousey, int mousex, int mousey, boolean forceleave) {
if (!wasinside && !isinside) return;
if (isinside && test(CURSOR)) Surface.fromBox(getRoot()).cursor = (String)boxToCursor.get(this);
- if (!wasinside && isinside && getTrap("Enter") != null) putAndTriggerJSTraps("Enter", T);
- else if (wasinside && !isinside && getTrap("Leave") != null) putAndTriggerJSTraps("Leave", T);
+ if (!wasinside && isinside && getTrap("Enter") != null) putAndTriggerTraps("Enter", T);
+ else if (wasinside && !isinside && getTrap("Leave") != null) putAndTriggerTraps("Leave", T);
else if (wasinside && isinside && (mousex != oldmousex || mousey != oldmousey) && getTrap("Move")!= null)
- putAndTriggerJSTraps("Move", T);
+ putAndTriggerTraps("Move", T);
for(Box b = getChild(numchildren - 1); b != null; b = b.prevSibling()) {
b.Move(oldmousex - b.x, oldmousey - b.y, mousex - b.x, mousey - b.y, forceleave);
if (b.inside(mousex - b.x, mousey - b.y)) forceleave = true;
// static stuff so we don't have to keep reallocating
private static int[] numRowsInCol = new int[65535];
- private LENGTH[] colWidth = new LENGTH[65535];
- private LENGTH[] colMaxWidth = new LENGTH[65535];
- private LENGTH[] rowHeight = new LENGTH[65535];
- private LENGTH[] rowMaxHeight = new LENGTH[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; } }
- final Box nextPackedSibling() { Box b = nextSibling(); return b == null || (b.test(PACKED | VISIBLE)) ? b : b.nextPackedSibling(); }
- final Box firstPackedChild() { Box b = getChild(0); return b == null || (b.test(PACKED | VISIBLE)) ? b : b.nextPackedSibling(); }
+ 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(); }
/** only for use on the root box */
void reflow(int new_width, int new_height) {
repack();
+ /*
new_width = bound(max(contentwidth, minwidth), new_width, test(HSHRINK) ? max(contentwidth, minwidth) : maxwidth);
new_height = bound(max(contentheight, minheight), new_height, test(VSHRINK) ? max(contentheight, minheight) : maxheight);
+ */
resize(x, y, new_width, new_height);
+ resize_children();
}
/** pack the boxes into rows and columns; also computes contentwidth */
//#repeat COLS/ROWS rows/cols cols/rows col/row row/col colspan/rowspan rowspan/colspan
if (test(FIXED) == COLS) {
- short r = 0; short rows = 0;
- for(Box child = firstPackedChild(); child != null; r++)
- for(short col=0, numclear=0; child != null && col < cols;) {
- if (numRowsInCol[col] > r) continue;
- if (col != 0 && col + min(cols, child.colspan) > cols) break;
+ 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) continue;
+ if (c != 0 && c + min(cols, child.colspan) - numclear > cols) break;
if (++numclear < min(cols, child.colspan)) continue;
- for(int i=col - numclear + 1; i <= col; i++) numRowsInCol[i] += child.rowspan;
- child.col = col; child.row = r;
- child = child.nextPackedSibling();
+ 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;
}
+ }
for(int i=0; i<cols; i++) numRowsInCol[i] = 0;
}
//#end
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; }
-
- contentwidth = bound(minwidth, max(font == null ? 0 : font.textwidth(text), contentwidth), maxwidth);
+ contentwidth = bound(minwidth, max(font == null || text == null ? 0 : font.textwidth(text), contentwidth), maxwidth);
//#end
}
private void resize(LENGTH x, LENGTH y, LENGTH width, LENGTH height) {
// FEATURE reimplement, but we're destroying this
- /*
if (x != this.x || y != this.y || width != this.width || height != this.height) {
- */
(parent == null ? this : parent).dirty(this.x, this.y, this.width, this.height);
boolean sizechange = (this.width != width || this.height != height) && getTrap("SizeChange") != null;
boolean poschange = (this.x != x || this.y != y) && getTrap("PosChange") != null;
this.width = width; this.height = height; this.x = x; this.y = y;
dirty();
- /*
- try { if (sizechange) putAndTriggerJSTraps("SizeChange", T); Surface.abort = true; }
+ try { if (sizechange) putAndTriggerTraps("SizeChange", T); /*Surface.abort = true;*/ }
catch (Exception e) { Log.log(this, e); }
- try { if (poschange) putAndTriggerJSTraps("PosChange", T); Surface.abort = true; }
+ try { if (poschange) putAndTriggerTraps("PosChange", T); /*Surface.abort = true;*/ }
catch (Exception e) { Log.log(this, e); }
}
- */
- if (numchildren > 0) resize_children();
}
private void resize_children() {
- int slack;
- //#repeat col/row colspan/rowspan contentwidth/contentheight x/y width/height \
- // HSHRINK/VSHRINK maxwidth/maxheight cols/rows minwidth/minheight
+ //#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
- slack = 0;
+ 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++) {
- slack += colWidth[i];
+ x_slack += colWidth[i];
colWidth[i] = max(colWidth[i], child.contentwidth / child.colspan);
- slack -= colWidth[i];
- colMaxWidth[i] = max(colMaxWidth[i], child.test(HSHRINK) ? child.contentwidth : child.maxwidth) / child.colspan;
+ x_slack -= colWidth[i];
+ colMaxWidth[i] = min(colMaxWidth[i], child.test(HSHRINK) ? child.contentwidth : child.maxwidth) / child.colspan;
}
// PHASE 2: hand out slack
- for(int startslack = 0; slack > 0 && startslack != slack;) {
- int increment = max(1, slack / cols);
- startslack = slack;
- for(short col=0; col < cols && slack > 0; col++) {
+ 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++) {
int diff = min(colMaxWidth[col], colWidth[col] + increment) - colWidth[col];
- slack -= diff;
+ x_slack -= diff;
colWidth[col] += diff;
}
}
+ //#end
- for(Box child = getChild(0); child != null; child = child.nextPackedSibling()) {
- int unbounded = 0;
- for(int i = child.col; i < child.col + child.colspan; i++) unbounded += colWidth[i];
- child.width = bound(child.contentwidth, unbounded, child.test(HSHRINK) ? child.contentwidth : child.maxwidth);
- child.x = test(ALIGN_RIGHT) ? slack : test(ALIGN_LEFT) ? slack / 2 : 0;
- for(int i=0; i < child.col; i++) child.x += colWidth[i];
- if (child.width < unbounded) child.x += (child.width - unbounded) / 2;
+ // Phase 3: assign childrens' actual sizes
+ 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 = max(child.minwidth, child_width);
+ child_height = max(child.minheight, child_height);
+ } else {
+ int unbounded;
+ //#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;
+ //#end
+ }
+ child.resize(child_x, child_y, child_width, child_height);
}
// cleanup
- for(int i=0; i<colWidth.length; i++) colWidth[i] = 0;
- for(int i=0; i<colMaxWidth.length; i++) colMaxWidth[i] = MAX_LENGTH;
- //#end
+ 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; }
- // Phase 3: assign childrens' actual sizes
for(Box child = getChild(0); child != null; child = child.nextSibling())
- if (!test(VISIBLE)) continue;
- else if (!child.test(PACKED))
- child.resize(child.x, child.y,
- child.test(HSHRINK) ? child.contentwidth : min(child.maxwidth, width - child.x),
- child.test(VSHRINK) ? child.contentheight : min(child.maxheight, height - child.y));
- else child.resize(child.x, child.y, child.width, child.height);
+ if (test(VISIBLE))
+ child.resize_children();
}
if (!test(NOCLIP)) {
cx1 = max(cx1, parent == null ? 0 : globalx);
cy1 = max(cy1, parent == null ? 0 : globaly);
- cx2 = min(cx2, parent == null ? 0 : globalx + width);
- cy2 = min(cy2, parent == null ? 0 : globaly + height);
+ cx2 = min(cx2, globalx + width);
+ cy2 = min(cy2, globaly + height);
if (cx2 <= cx1 || cy2 <= cy1) return;
}
if ((fillcolor & 0xFF000000) != 0x00000000)
- buf.fillJSTrapezoid(globalx, globalx + width, globaly, globalx, globalx + width, globaly + height, fillcolor);
+ buf.fillTrapezoid(globalx, globalx + width, globaly, globalx, globalx + width, globaly + height, fillcolor);
+
+ if (texture != null && texture.picture != null)
+ for(int x = globalx; x < cx2; x += texture.picture.getWidth())
+ for(int y = globaly; y < cy2; y += texture.picture.getHeight())
+ buf.drawPicture(texture.picture, x, y, cx1, cy1, cx2, cy2);
- if (texture != null)
- for(int x = globalx; x < cx2; x += texture.getWidth())
- for(int y = globaly; y < cy2; y += texture.getHeight())
- 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,
new Scheduler.Task() { public void perform() { Box b = Box.this; MARK_REFLOW_b; dirty(); }});
-
+
for(Box b = getChild(0); b != null; b = b.nextSibling())
b.render(globalx, globaly, cx1, cy1, cx2, cy2, buf, null);
}
public int localToGlobalX(int x) { return parent == null ? x : parent.globalToLocalX(x + this.x); }
public int localToGlobalY(int y) { return parent == null ? y : parent.globalToLocalY(y + this.y); }
- public Object call(Object method, JSArray args) throws JS.Exn {
- if (!"indexof".equals(method)) return null;
- Box b = (Box)args.elementAt(0);
- if (b.parent != this) return (redirect == null || redirect == this) ? N(-1) : redirect.call(method, args);
+ 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());
}
+ public Enumeration keys() { throw new Error("you cannot apply for..in to a " + this.getClass().getName()); }
+
/** to be filled in by the Tree implementation */
- abstract void put(int i, Object value);
public int numchildren = 0;
- abstract public int getIndexInParent();
- abstract public Box getChild(int i);
- abstract public Box nextSibling();
- abstract public Box prevSibling();
- abstract public void remove();
- abstract Box swapPosition(Box x, Box y);
-
- public Object get(Object name) { return get(name, false); }
- public Object get(Object name, boolean ignoretraps) {
+
+ protected boolean isTrappable() { return true; }
+ public Object get(Object name) {
if (name instanceof Number)
return redirect == null ? null : redirect == this ? getChild(toInt(name)) : redirect.get(name);
//#switch(name)
+ case "indexof": return METHOD;
case "text": return text;
- case "path": throw new JS.Exn("cannot read from the path property");
+ case "path": throw new JSExn("cannot read from the path property");
case "fill": return colorToString(fillcolor);
case "strokecolor": return colorToString(strokecolor);
case "textcolor": return colorToString(strokecolor);
case "vshrink": return B(test(VSHRINK));
case "x": return (parent == null || !test(VISIBLE)) ? N(0) : N(x);
case "y": return (parent == null || !test(VISIBLE)) ? N(0) : N(y);
- case "width" return N(width);
- case "height" return N(height);
+ case "width": return N(width);
+ case "height": return N(height);
case "cols": return test(FIXED) == COLS ? N(cols) : N(0);
case "rows": return test(FIXED) == ROWS ? N(rows) : N(0);
case "colspan": return N(colspan);
return null;
}
- public void put(Object name, Object value) { put(name, value, false); }
- public void put(Object name, Object value, boolean ignoretraps) {
+ public void put(Object name, Object value) {
if (name instanceof Number) { put(toInt(name), value); return; }
//#switch(name)
case "text": CHECKSET_STRING(text); MARK_RESIZE; dirty();
+ case "strokecolor": value = N(stringToColor((String)value)); CHECKSET_INT(strokecolor); MARK_RESIZE; dirty();
+ case "textcolor": value = N(stringToColor((String)value)); CHECKSET_INT(strokecolor); MARK_RESIZE; dirty();
+ case "text": CHECKSET_STRING(text); MARK_RESIZE; dirty();
case "strokewidth": CHECKSET_SHORT(strokewidth); dirty();
case "thisbox": if (value == null) remove();
case "shrink": put("hshrink", value); put("vshrink", value);
case "hshrink": CHECKSET_FLAG(HSHRINK); MARK_RESIZE;
case "vshrink": CHECKSET_FLAG(VSHRINK); MARK_RESIZE;
- case "width": CHECKSET_INT(width); MARK_RESIZE;
+ case "width": if (parent==null&&Surface.fromBox(this)!=null) { CHECKSET_INT(width); } else { put("maxwidth", value); put("minwidth", value); MARK_RESIZE; }
+ case "height": if (parent == null&&Surface.fromBox(this)!=null) { CHECKSET_INT(height); } else { put("maxheight", value); put("minheight", value); MARK_RESIZE; }
case "maxwidth": CHECKSET_INT(maxwidth); MARK_RESIZE;
case "minwidth": CHECKSET_INT(minwidth); MARK_RESIZE;
- case "height": CHECKSET_INT(height); MARK_RESIZE;
case "maxheight": CHECKSET_INT(maxheight); MARK_RESIZE;
case "minheight": CHECKSET_INT(minheight); MARK_RESIZE;
case "colspan": CHECKSET_SHORT(colspan); MARK_REPACK_parent;
case "rowspan": CHECKSET_SHORT(colspan); MARK_REPACK_parent;
- case "rows": CHECKSET_SHORT(rows); MARK_REPACK; // FEATURE: error checking
- case "cols": CHECKSET_SHORT(cols); MARK_REPACK; // FEATURE: error checking
+ 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 "noclip": CHECKSET_FLAG(NOCLIP); if (parent == null) dirty(); else parent.dirty();
case "visible": CHECKSET_FLAG(VISIBLE); dirty(); MARK_RESIZE; dirty();
case "packed": CHECKSET_FLAG(PACKED); MARK_REPACK_parent;
}
private void setFill(Object value) {
- if (value == null || !(value instanceof Res)) return;
- Picture pic = Picture.fromRes((Res)value, null);
- if (pic != null) {
- texture = pic;
- minwidth = texture.getWidth();
- minheight = texture.getHeight();
+ if (value == null) return;
+ if (value instanceof String) {
+ // FIXME check double set
+ int newfillcolor = stringToColor((String)value);
+ if (newfillcolor == fillcolor) return;
+ fillcolor = newfillcolor;
+ dirty();
+ return;
+ }
+ if (!(value instanceof Res)) return;
+ texture = Picture.fromRes((Res)value, null);
+ if (texture != null) {
+ minwidth = texture.picture.getWidth();
+ minheight = texture.picture.getHeight();
MARK_REFLOW;
dirty();
- } else Picture.fromRes((Res)value, new Callback() { public Object call(Object arg) {
- texture = (Picture)arg;
- minwidth = texture.getWidth();
- minheight = texture.getHeight();
+ return;
+ }
+ texture = Picture.fromRes((Res)value, new Scheduler.Task() { public void perform() {
+ minwidth = texture.picture.getWidth();
+ minheight = texture.picture.getHeight();
Box b = Box.this; MARK_REFLOW_b;
dirty();
- return null;
} });
}
int mousex = globalToLocalX(surface.mousex);
int mousey = globalToLocalY(surface.mousey);
for(Box c = prevSibling(); c != null; c = c.prevSibling())
- if (c.inside(mousex - c.x, mousey - c.y)) { c.putAndTriggerJSTraps(name, value); return; }
- if (parent != null) parent.putAndTriggerJSTraps(name, value);
+ if (c.inside(mousex - c.x, mousey - c.y)) { c.putAndTriggerTraps(name, value); return; }
+ if (parent != null) parent.putAndTriggerTraps(name, value);
}
private static int stringToColor(String s) {
// Trivial Helper Methods (should be inlined) /////////////////////////////////////////
- static final short min(short a, short b) { if (a<b) return a; else return b; }
- static final int min(int a, int b) { if (a<b) return a; else return b; }
- static final float min(float a, float b) { if (a<b) return a; else return b; }
+ static short min(short a, short b) { if (a<b) return a; else return b; }
+ static int min(int a, int b) { if (a<b) return a; else return b; }
+ static float min(float a, float b) { if (a<b) return a; else return b; }
- static final short max(short a, short b) { if (a>b) return a; else return b; }
- static final int max(int a, int b) { if (a>b) return a; else return b; }
- static final float max(float a, float b) { if (a>b) return a; else return b; }
+ static short max(short a, short b) { if (a>b) return a; else return b; }
+ static int max(int a, int b) { if (a>b) return a; else return b; }
+ static float max(float a, float b) { if (a>b) return a; else return b; }
- static final int min(int a, int b, int c) { if (a<=b && a<=c) return a; else if (b<=c && b<=a) return b; else return c; }
- static final int max(int a, int b, int c) { if (a>=b && a>=c) return a; else if (b>=c && b>=a) return b; else return c; }
- static final int bound(int a, int b, int c) { if (c < b) return c; if (a > b) return a; return b; }
+ static int min(int a, int b, int c) { if (a<=b && a<=c) return a; else if (b<=c && b<=a) return b; else return c; }
+ static int max(int a, int b, int c) { if (a>=b && a>=c) return a; else if (b>=c && b>=a) return b; else return c; }
+ static int bound(int a, int b, int c) { if (c < b) return c; if (a > b) return a; return b; }
final boolean inside(int x, int y) { return test(VISIBLE) && x >= 0 && y >= 0 && x < width && y < height; }
- protected final void set(int mask) { flags |= mask; }
- protected final void clear(int mask) { flags &= ~mask; }
- protected final boolean test(int mask) { return ((flags & mask) == mask); }
+ void set(int mask) { flags |= mask; }
+ void set(int mask, boolean setclear) { if (setclear) set(mask); else clear(mask); }
+ void clear(int mask) { flags &= ~mask; }
+ boolean test(int mask) { return ((flags & mask) == mask); }
protected Box left = null;
protected Box right = null;
protected Box rootChild = null;
protected Box peerTree_parent = null;
- public abstract Box peerTree_leftmost();
- public abstract Box peerTree_rightmost();
- public abstract Box insertBeforeMe(Box cell);
- public abstract Box insertAfterMe(Box cell);
- protected abstract Box fixAfterInsertion();
- protected abstract Box fixAfterDeletion();
- protected abstract Box rotateLeft();
- protected abstract Box rotateRight();
- protected abstract int numPeerChildren();
+
+
+ // Tree Handling //////////////////////////////////////////////////////////////////////
+
+
+ private static boolean REDbool = false;
+ private static boolean BLACKbool = true;
+
+ public final Box peerTree_leftmost() { for (Box p = this; ; p = p.left) if (p.left == null) return p; }
+ public final Box peerTree_rightmost() { for (Box p = this; ; p = p.right) if (p.right == null) return p; }
+ static Box peerTree_parent(Box p) { return (p == null)? null: p.peerTree_parent; }
+
+ public Box insertBeforeMe(Box cell) { left = cell; cell.peerTree_parent = this; return cell.fixAfterInsertion(); }
+ public Box insertAfterMe(Box cell) { right = cell; cell.peerTree_parent = this; return cell.fixAfterInsertion(); }
+
+ static boolean colorOf(Box p) { return (p == null) ? BLACKbool : p.test(BLACK); }
+ static void setColor(Box p, boolean c) { if (p != null) { if (c) p.set(BLACK); else p.clear(BLACK); } }
+ static Box leftOf(Box p) { return (p == null)? null: p.left; }
+ static Box rightOf(Box p) { return (p == null)? null: p.right; }
+
+ public final Box nextSibling() {
+ if (right != null)
+ return right.peerTree_leftmost();
+ else {
+ Box p = peerTree_parent;
+ Box ch = this;
+ while (p != null && ch == p.right) { ch = p; p = p.peerTree_parent; }
+ return p;
+ }
+ }
+
+ public final Box prevSibling() {
+ if (left != null)
+ return left.peerTree_rightmost();
+ else {
+ Box p = peerTree_parent;
+ Box ch = this;
+ while (p != null && ch == p.left) { ch = p; p = p.peerTree_parent; }
+ return p;
+ }
+ }
+
+ public Box removeNode() {
+ Box root = peerTree_parent.rootChild;
+
+ // handle case where we are only node
+ if (left == null && right == null && peerTree_parent == null) return null;
+
+ // if strictly internal, swap places with a successor
+ if (left != null && right != null) {
+ Box s = nextSibling();
+ // To work nicely with arbitrary subclasses of Box, we don't want to
+ // just copy successor's fields. since we don't know what
+ // they are. Instead we swap positions in the tree.
+ root = swapPosition(this, s);
+ }
+
+ // Start fixup at replacement node (normally a child).
+ // But if no children, fake it by using self
+
+ if (left == null && right == null) {
+
+ if (test(BLACK)) root = this.fixAfterDeletion();
+
+ // Unlink (Couldn't before since fixAfterDeletion needs peerTree_parent ptr)
+
+ if (peerTree_parent != null) {
+ if (this == peerTree_parent.left)
+ peerTree_parent.left = null;
+ else if (this == peerTree_parent.right)
+ peerTree_parent.right = null;
+ peerTree_parent = null;
+ }
+
+ }
+ else {
+ Box replacement = left;
+ if (replacement == null) replacement = right;
+
+ // link replacement to peerTree_parent
+ replacement.peerTree_parent = peerTree_parent;
+
+ if (peerTree_parent == null) root = replacement;
+ else if (this == peerTree_parent.left) peerTree_parent.left = replacement;
+ else peerTree_parent.right = replacement;
+
+ left = null;
+ right = null;
+ peerTree_parent = null;
+
+ // fix replacement
+ if (test(BLACK)) root = replacement.fixAfterDeletion();
+
+ }
+
+ return root;
+ }
+
+ /**
+ * Swap the linkages of two nodes in a tree.
+ * Return new root, in case it changed.
+ **/
+ Box swapPosition(Box x, Box y) {
+ Box root = peerTree_parent.rootChild;
+
+ /* Too messy. TODO: find sequence of assigments that are always OK */
+
+ Box px = x.peerTree_parent;
+ boolean xpl = px != null && x == px.left;
+ Box lx = x.left;
+ Box rx = x.right;
+
+ Box py = y.peerTree_parent;
+ boolean ypl = py != null && y == py.left;
+ Box ly = y.left;
+ Box ry = y.right;
+
+ if (x == py) {
+ y.peerTree_parent = px;
+ if (px != null) if (xpl) px.left = y; else px.right = y;
+ x.peerTree_parent = y;
+ if (ypl) {
+ y.left = x;
+ y.right = rx; if (rx != null) rx.peerTree_parent = y;
+ }
+ else {
+ y.right = x;
+ y.left = lx; if (lx != null) lx.peerTree_parent = y;
+ }
+ x.left = ly; if (ly != null) ly.peerTree_parent = x;
+ x.right = ry; if (ry != null) ry.peerTree_parent = x;
+ }
+ else if (y == px) {
+ x.peerTree_parent = py;
+ if (py != null) if (ypl) py.left = x; else py.right = x;
+ y.peerTree_parent = x;
+ if (xpl) {
+ x.left = y;
+ x.right = ry; if (ry != null) ry.peerTree_parent = x;
+ }
+ else {
+ x.right = y;
+ x.left = ly; if (ly != null) ly.peerTree_parent = x;
+ }
+ y.left = lx; if (lx != null) lx.peerTree_parent = y;
+ y.right = rx; if (rx != null) rx.peerTree_parent = y;
+ }
+ else {
+ x.peerTree_parent = py; if (py != null) if (ypl) py.left = x; else py.right = x;
+ x.left = ly; if (ly != null) ly.peerTree_parent = x;
+ x.right = ry; if (ry != null) ry.peerTree_parent = x;
+
+ y.peerTree_parent = px; if (px != null) if (xpl) px.left = y; else px.right = y;
+ y.left = lx; if (lx != null) lx.peerTree_parent = y;
+ y.right = rx; if (rx != null) rx.peerTree_parent = y;
+ }
+
+ boolean c = x.test(BLACK);
+ if (y.test(BLACK)) x.set(BLACK); else x.clear(BLACK);
+ if (c) y.set(BLACK); else y.clear(BLACK);
+
+ if (root == x) root = y;
+ else if (root == y) root = x;
+ return parent.rootChild = root;
+ }
+
+ Box rotateLeft() {
+ Box root = parent.rootChild;
+ Box r = right;
+ right = r.left;
+ if (r.left != null) r.left.peerTree_parent = this;
+ r.peerTree_parent = peerTree_parent;
+ if (peerTree_parent == null) root = r;
+ else if (peerTree_parent.left == this) peerTree_parent.left = r;
+ else peerTree_parent.right = r;
+ r.left = this;
+ peerTree_parent = r;
+ return parent.rootChild = root;
+ }
+
+ Box rotateRight() {
+ Box root = parent.rootChild;
+ Box l = left;
+ left = l.right;
+ if (l.right != null) l.right.peerTree_parent = this;
+ l.peerTree_parent = peerTree_parent;
+ if (peerTree_parent == null) root = l;
+ else if (peerTree_parent.right == this) peerTree_parent.right = l;
+ else peerTree_parent.left = l;
+ l.right = this;
+ peerTree_parent = l;
+ return parent.rootChild;
+ }
+
+ Box fixAfterInsertion() {
+ Box root = parent.rootChild;
+ clear(BLACK);
+ Box x = this;
+
+ while (x != null && x != root && !x.peerTree_parent.test(BLACK)) {
+ if (peerTree_parent(x) == leftOf(peerTree_parent(peerTree_parent(x)))) {
+ Box y = rightOf(peerTree_parent(peerTree_parent(x)));
+ if (colorOf(y) == REDbool) {
+ setColor(peerTree_parent(x), BLACKbool);
+ setColor(y, BLACKbool);
+ setColor(peerTree_parent(peerTree_parent(x)), REDbool);
+ x = peerTree_parent(peerTree_parent(x));
+ }
+ else {
+ if (x == rightOf(peerTree_parent(x))) {
+ x = peerTree_parent(x);
+ root = x.rotateLeft();
+ }
+ setColor(peerTree_parent(x), BLACKbool);
+ setColor(peerTree_parent(peerTree_parent(x)), REDbool);
+ if (peerTree_parent(peerTree_parent(x)) != null)
+ root = peerTree_parent(peerTree_parent(x)).rotateRight();
+ }
+ }
+ else {
+ Box y = leftOf(peerTree_parent(peerTree_parent(x)));
+ if (colorOf(y) == REDbool) {
+ setColor(peerTree_parent(x), BLACKbool);
+ setColor(y, BLACKbool);
+ setColor(peerTree_parent(peerTree_parent(x)), REDbool);
+ x = peerTree_parent(peerTree_parent(x));
+ }
+ else {
+ if (x == leftOf(peerTree_parent(x))) {
+ x = peerTree_parent(x);
+ root = x.rotateRight();
+ }
+ setColor(peerTree_parent(x), BLACKbool);
+ setColor(peerTree_parent(peerTree_parent(x)), REDbool);
+ if (peerTree_parent(peerTree_parent(x)) != null)
+ root = peerTree_parent(peerTree_parent(x)).rotateLeft();
+ }
+ }
+ }
+ root.set(BLACK);
+ return parent.rootChild = root;
+ }
+
+ /** From CLR **/
+ Box fixAfterDeletion() {
+ Box root = peerTree_parent.rootChild;
+ Box x = this;
+ while (x != root && colorOf(x) == BLACKbool) {
+ if (x == leftOf(peerTree_parent(x))) {
+ Box sib = rightOf(peerTree_parent(x));
+ if (colorOf(sib) == REDbool) {
+ setColor(sib, BLACKbool);
+ setColor(peerTree_parent(x), REDbool);
+ root = peerTree_parent(x).rotateLeft();
+ sib = rightOf(peerTree_parent(x));
+ }
+ if (colorOf(leftOf(sib)) == BLACKbool && colorOf(rightOf(sib)) == BLACKbool) {
+ setColor(sib, REDbool);
+ x = peerTree_parent(x);
+ }
+ else {
+ if (colorOf(rightOf(sib)) == BLACKbool) {
+ setColor(leftOf(sib), BLACKbool);
+ setColor(sib, REDbool);
+ root = sib.rotateRight();
+ sib = rightOf(peerTree_parent(x));
+ }
+ setColor(sib, colorOf(peerTree_parent(x)));
+ setColor(peerTree_parent(x), BLACKbool);
+ setColor(rightOf(sib), BLACKbool);
+ root = peerTree_parent(x).rotateLeft();
+ x = root;
+ }
+ }
+ else {
+ Box sib = leftOf(peerTree_parent(x));
+ if (colorOf(sib) == REDbool) {
+ setColor(sib, BLACKbool);
+ setColor(peerTree_parent(x), REDbool);
+ root = peerTree_parent(x).rotateRight();
+ sib = leftOf(peerTree_parent(x));
+ }
+ if (colorOf(rightOf(sib)) == BLACKbool && colorOf(leftOf(sib)) == BLACKbool) {
+ setColor(sib, REDbool);
+ x = peerTree_parent(x);
+ }
+ else {
+ if (colorOf(leftOf(sib)) == BLACKbool) {
+ setColor(rightOf(sib), BLACKbool);
+ setColor(sib, REDbool);
+ root = sib.rotateLeft();
+ sib = leftOf(peerTree_parent(x));
+ }
+ setColor(sib, colorOf(peerTree_parent(x)));
+ setColor(peerTree_parent(x), BLACKbool);
+ setColor(leftOf(sib), BLACKbool);
+ root = peerTree_parent(x).rotateRight();
+ x = root;
+ }
+ }
+ }
+ setColor(x, BLACKbool);
+ return parent.rootChild = root;
+ }
+
+ // Tree Manipulation /////////////////////////////////////////////////////////////////////
+
+ /** remove this node from its parent; INVARIANT: whenever the parent of a node is changed, remove() gets called. */
+ public void remove() {
+ if (parent == null) {
+ Surface surface = Surface.fromBox(this);
+ if (surface != null) surface.dispose(true);
+ return;
+ } else {
+ parent.numchildren--;
+ }
+ Box oldparent = parent;
+ if (oldparent == null) return;
+ MARK_REFLOW;
+ dirty();
+ clear(MOUSEINSIDE);
+ removeNode();
+ parent = null;
+ if (oldparent != null) { Box b = oldparent; MARK_REFLOW_b; }
+ if (oldparent != null) oldparent.putAndTriggerTraps("childremoved", this);
+ }
+
+ /** Returns ith child */
+ public Box getChild(int i) {
+ // FIXME: store numleft and numright in the tree
+ Box left = rootChild;
+ if (left == null) return null;
+ while (left.left != null) left = left.left;
+ for(; i > 0; i--) left = left.nextSibling();
+ return left;
+ }
+
+ /** Returns our index in our parent */
+ public int getIndexInParent() {
+ // FIXME: store numleft and numright in the tree
+ if (peerTree_parent == null) return left == null ? 0 : left.numPeerChildren() + 1;
+ else if (peerTree_parent.left == this) return peerTree_parent.getIndexInParent() - 1;
+ else if (peerTree_parent.right == this) return peerTree_parent.getIndexInParent() + 1;
+ else throw new Error("we're not a child of our parent!");
+ }
+
+ public int numPeerChildren() {
+ return (left == null ? 0 : left.numPeerChildren() + 1) + (right == null ? 0 : right.numPeerChildren() + 1);
+ }
+
+ public void put(int i, Object value) {
+ if (i < 0) return;
+
+ if (value != null && !(value instanceof Box)) {
+ if (Log.on) Log.logJS(this, "attempt to set a numerical property on a box to a non-box");
+ return;
+ }
+
+ if (redirect == null) {
+ if (value == null) putAndTriggerTraps("childremoved", getChild(i));
+ else Log.logJS(this, "attempt to add/remove children to/from a node with a null redirect");
+
+ } else if (redirect != this) {
+ if (value != null) putAndTriggerTraps("childadded", value);
+ redirect.put(i, value);
+ if (value == null) {
+ Box b = (Box)redirect.get(new Integer(i));
+ if (b != null) putAndTriggerTraps("childremoved", b);
+ }
+
+ } else if (value == null) {
+ if (i < 0 || i > numchildren) return;
+ Box b = getChild(i);
+ b.remove();
+ putAndTriggerTraps("childremoved", b);
+
+ } else {
+ Box b = (Box)value;
+
+ // check if box being moved is currently target of a redirect
+ for(Box cur = b.parent; cur != null; cur = cur.parent)
+ if (cur.redirect == b) {
+ if (Log.on) Log.logJS(this, "attempt to move a box that is the target of a redirect");
+ return;
+ }
+
+ // check for recursive ancestor violation
+ for(Box cur = this; cur != null; cur = cur.parent)
+ if (cur == b) {
+ if (Log.on) Log.logJS(this, "attempt to make a node a parent of its own ancestor");
+ if (Log.on) Log.log(this, "box == " + this + " ancestor == " + b);
+ return;
+ }
+
+ b.remove();
+ b.parent = this;
+ numchildren++;
+
+ Box before = getChild(i);
+ if (before == null) {
+ if (rootChild == null) rootChild = b;
+ else rootChild.peerTree_rightmost().insertAfterMe(b);
+ }
+ else before.insertBeforeMe(b);
+
+ // need both of these in case child was already uncalc'ed
+ MARK_REFLOW_b;
+ MARK_REFLOW;
+
+ b.dirty();
+ putAndTriggerTraps("childadded", b);
+ }
+ }
+
}