X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;f=src%2Forg%2Fxwt%2FBox.java;h=fb365945250afd48ff46f7c871ce7438b1311d14;hb=d3a783aafa7fb21b328f42c568cd3302be224f0f;hp=60f1fbd5f048d14aed454f7a6962ee3535f6884a;hpb=679661c1f27b31d928d20edf698cb22adb086b17;p=org.ibex.core.git diff --git a/src/org/xwt/Box.java b/src/org/xwt/Box.java index 60f1fbd..fb36594 100644 --- a/src/org/xwt/Box.java +++ b/src/org/xwt/Box.java @@ -39,7 +39,7 @@ import org.xwt.translators.*; * 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 ////////////////////////////////////////////////////////////////////// @@ -93,20 +93,20 @@ public abstract class Box extends JSScope implements JSTrap.JSTrappable { 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; @@ -136,8 +136,8 @@ public abstract class Box extends JSScope implements JSTrap.JSTrappable { // 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); @@ -152,9 +152,6 @@ public abstract class Box extends JSScope implements JSTrap.JSTrappable { } } - 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) { @@ -164,10 +161,10 @@ public abstract class Box extends JSScope implements JSTrap.JSTrappable { 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; @@ -185,14 +182,16 @@ public abstract class Box extends JSScope implements JSTrap.JSTrappable { private static LENGTH[] rowMaxHeight = new LENGTH[65535]; static { for(int i=0; i 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 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; } } @@ -274,22 +274,27 @@ public abstract class Box extends JSScope implements JSTrap.JSTrappable { // 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.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)); - continue; + 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 } - 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 colWidth/rowHeight child_width/child_height - unbounded = 0; - for(int i = child.col; i < child.col + child.colspan; i++) unbounded += colWidth[i]; - int child_width = bound(child.contentwidth, unbounded, child.test(HSHRINK) ? child.contentwidth : child.maxwidth); - int 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; - //#end child.resize(child_x, child_y, child_width, child_height); } @@ -318,22 +323,22 @@ public abstract class Box extends JSScope implements JSTrap.JSTrappable { cy1 = max(cy1, parent == null ? 0 : globaly); cx2 = min(cx2, globalx + width); cy2 = min(cy2, globaly + height); - //if (cx2 <= cx1 || cy2 <= cy1) return; + 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); } @@ -346,31 +351,30 @@ public abstract class Box extends JSScope implements JSTrap.JSTrappable { 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); @@ -408,30 +412,31 @@ public abstract class Box extends JSScope implements JSTrap.JSTrappable { case "Minimized": if (parent == null && getSurface() != null) return B(getSurface().minimized); default: return super.get(name); //#end - return null; + throw new Error("unreachable"); // unreachable } - 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; @@ -462,12 +467,13 @@ public abstract class Box extends JSScope implements JSTrap.JSTrappable { case "fontsize": font = Font.getFont(font == null ? null : font.res, toInt(value)); MARK_RESIZE; dirty(); case "x": if (test(PACKED) && parent != null) return; CHECKSET_INT(x); dirty(); MARK_RESIZE; dirty(); case "y": if (test(PACKED) && parent != null) return; CHECKSET_INT(y); dirty(); MARK_RESIZE; dirty(); - case "KeyPressed": // prevent stuff from hitting the Hash - case "KeyReleased": // prevent stuff from hitting the Hash - case "PosChange": // prevent stuff from hitting the Hash - case "SizeChange": // prevent stuff from hitting the Hash - case "childadded": // prevent stuff from hitting the Hash - case "childremoved": // prevent stuff from hitting the Hash + case "KeyPressed": return; // prevent stuff from hitting the Hash + case "KeyReleased": return; // prevent stuff from hitting the Hash + case "PosChange": return; // prevent stuff from hitting the Hash + case "SizeChange": return; // prevent stuff from hitting the Hash + case "childadded": return; // prevent stuff from hitting the Hash + case "childremoved": return; // prevent stuff from hitting the Hash + default: super.put(name, value); //#end } @@ -513,21 +519,29 @@ public abstract class Box extends JSScope implements JSTrap.JSTrappable { } 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; } }); } @@ -537,8 +551,8 @@ public abstract class Box extends JSScope implements JSTrap.JSTrappable { 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) { @@ -598,36 +612,429 @@ public abstract class Box extends JSScope implements JSTrap.JSTrappable { // Trivial Helper Methods (should be inlined) ///////////////////////////////////////// - static final short min(short a, short b) { if (ab) 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 void insertBeforeMe(Box cell) { left = cell; cell.peerTree_parent = this; cell.fixAfterInsertion(); } + public void insertAfterMe(Box cell) { right = cell; cell.peerTree_parent = this; 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 void removeNode() { + + // handle case where we are only node + if (left == null && right == null && peerTree_parent == null) return; + + // 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. + 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)) 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) parent.rootChild = 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)) replacement.fixAfterDeletion(); + + } + } + + /** + * Swap the linkages of two nodes in a tree. + * Return new root, in case it changed. + **/ + void swapPosition(Box x, Box y) { + + /* 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 (parent.rootChild == x) parent.rootChild = y; + else if (parent.rootChild == y) parent.rootChild = x; + } + + void rotateLeft() { + Box r = right; + right = r.left; + if (r.left != null) r.left.peerTree_parent = this; + r.peerTree_parent = peerTree_parent; + if (peerTree_parent == null) parent.rootChild = r; + else if (peerTree_parent.left == this) peerTree_parent.left = r; + else peerTree_parent.right = r; + r.left = this; + peerTree_parent = r; + } + + void rotateRight() { + Box l = left; + left = l.right; + if (l.right != null) l.right.peerTree_parent = this; + l.peerTree_parent = peerTree_parent; + if (peerTree_parent == null) parent.rootChild = l; + else if (peerTree_parent.right == this) peerTree_parent.right = l; + else peerTree_parent.left = l; + l.right = this; + peerTree_parent = l; + } + + void fixAfterInsertion() { + clear(BLACK); + Box x = this; + + while (x != null && x != parent.rootChild && !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); + x.rotateLeft(); + } + setColor(peerTree_parent(x), BLACKbool); + setColor(peerTree_parent(peerTree_parent(x)), REDbool); + if (peerTree_parent(peerTree_parent(x)) != null) + 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); + x.rotateRight(); + } + setColor(peerTree_parent(x), BLACKbool); + setColor(peerTree_parent(peerTree_parent(x)), REDbool); + if (peerTree_parent(peerTree_parent(x)) != null) + peerTree_parent(peerTree_parent(x)).rotateLeft(); + } + } + } + parent.rootChild.set(BLACK); + } + + /** From CLR **/ + void fixAfterDeletion() { + Box x = this; + while (x != parent.rootChild && 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); + 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); + sib.rotateRight(); + sib = rightOf(peerTree_parent(x)); + } + setColor(sib, colorOf(peerTree_parent(x))); + setColor(peerTree_parent(x), BLACKbool); + setColor(rightOf(sib), BLACKbool); + peerTree_parent(x).rotateLeft(); + x = parent.rootChild; + } + } + else { + Box sib = leftOf(peerTree_parent(x)); + if (colorOf(sib) == REDbool) { + setColor(sib, BLACKbool); + setColor(peerTree_parent(x), REDbool); + 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); + sib.rotateLeft(); + sib = leftOf(peerTree_parent(x)); + } + setColor(sib, colorOf(peerTree_parent(x))); + setColor(peerTree_parent(x), BLACKbool); + setColor(leftOf(sib), BLACKbool); + peerTree_parent(x).rotateRight(); + x = parent.rootChild; + } + } + } + setColor(x, BLACKbool); + } + + // 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); + } + } + }