* 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 implements JSTrap.JSTrappable {
// Macros //////////////////////////////////////////////////////////////////////
// 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);
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) {
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) {
// 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 set(int mask, boolean setclear) { if (setclear) set(mask); else clear(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.putAndTriggerJSTraps("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) putAndTriggerJSTraps("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) putAndTriggerJSTraps("childadded", value);
+ redirect.put(i, value);
+ if (value == null) {
+ Box b = (Box)redirect.get(new Integer(i));
+ if (b != null) putAndTriggerJSTraps("childremoved", b);
+ }
+
+ } else if (value == null) {
+ if (i < 0 || i > numchildren) return;
+ Box b = getChild(i);
+ b.remove();
+ putAndTriggerJSTraps("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();
+ putAndTriggerJSTraps("childadded", b);
+ }
+ }
+
}
+++ /dev/null
-// Copyright 2002 Adam Megacz, see the COPYING file for licensing [GPL]
-package org.xwt;
-import org.xwt.js.*;
-import org.xwt.util.*;
-
-/** all the boxtree manipulation code goes here */
-public final class BoxTree extends Box {
-
- //#define MARK_REFLOW for(Box b2 = this; b2 != null && !b2.test(REFLOW); b2 = b2.parent) b2.set(REFLOW);
- //#define MARK_REFLOW_b for(Box b2 = b; b2 != null && !b2.test(REFLOW); b2 = b2.parent) b2.set(REFLOW);
- //#define MARK_RESIZE for(Box b2 = this; b2 != null && !b2.test(RESIZE); b2 = b2.parent) b2.set(RESIZE);
- //#define MARK_RESIZE_b for(Box b2 = b; b2 != null && !b2.test(RESIZE); b2 = b2.parent) b2.set(RESIZE);
-
- private static final boolean RED = false;
- private static final boolean BLACK = 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) ? BLACK : p.test(Box.BLACK); }
- static void setColor(Box p, boolean c) { if (p != null) { if (c) p.set(Box.BLACK); else p.clear(Box.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(Box.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(Box.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(Box.BLACK);
- if (y.test(Box.BLACK)) x.set(Box.BLACK); else x.clear(Box.BLACK);
- if (c) y.set(Box.BLACK); else y.clear(Box.BLACK);
-
- if (root == x) root = y;
- else if (root == y) root = x;
- return parent.rootChild = root;
- }
-
- protected final 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;
- }
-
- protected final 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;
- }
-
- protected final Box fixAfterInsertion() {
- Box root = parent.rootChild;
- clear(Box.BLACK);
- Box x = this;
-
- while (x != null && x != root && !x.peerTree_parent.test(Box.BLACK)) {
- if (peerTree_parent(x) == leftOf(peerTree_parent(peerTree_parent(x)))) {
- Box y = rightOf(peerTree_parent(peerTree_parent(x)));
- if (colorOf(y) == RED) {
- setColor(peerTree_parent(x), BLACK);
- setColor(y, BLACK);
- setColor(peerTree_parent(peerTree_parent(x)), RED);
- x = peerTree_parent(peerTree_parent(x));
- }
- else {
- if (x == rightOf(peerTree_parent(x))) {
- x = peerTree_parent(x);
- root = x.rotateLeft();
- }
- setColor(peerTree_parent(x), BLACK);
- setColor(peerTree_parent(peerTree_parent(x)), RED);
- 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) == RED) {
- setColor(peerTree_parent(x), BLACK);
- setColor(y, BLACK);
- setColor(peerTree_parent(peerTree_parent(x)), RED);
- x = peerTree_parent(peerTree_parent(x));
- }
- else {
- if (x == leftOf(peerTree_parent(x))) {
- x = peerTree_parent(x);
- root = x.rotateRight();
- }
- setColor(peerTree_parent(x), BLACK);
- setColor(peerTree_parent(peerTree_parent(x)), RED);
- if (peerTree_parent(peerTree_parent(x)) != null)
- root = peerTree_parent(peerTree_parent(x)).rotateLeft();
- }
- }
- }
- root.set(Box.BLACK);
- return parent.rootChild = root;
- }
-
- /** From CLR **/
- protected final Box fixAfterDeletion() {
- Box root = peerTree_parent.rootChild;
- Box x = this;
- while (x != root && colorOf(x) == BLACK) {
- if (x == leftOf(peerTree_parent(x))) {
- Box sib = rightOf(peerTree_parent(x));
- if (colorOf(sib) == RED) {
- setColor(sib, BLACK);
- setColor(peerTree_parent(x), RED);
- root = peerTree_parent(x).rotateLeft();
- sib = rightOf(peerTree_parent(x));
- }
- if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) {
- setColor(sib, RED);
- x = peerTree_parent(x);
- }
- else {
- if (colorOf(rightOf(sib)) == BLACK) {
- setColor(leftOf(sib), BLACK);
- setColor(sib, RED);
- root = sib.rotateRight();
- sib = rightOf(peerTree_parent(x));
- }
- setColor(sib, colorOf(peerTree_parent(x)));
- setColor(peerTree_parent(x), BLACK);
- setColor(rightOf(sib), BLACK);
- root = peerTree_parent(x).rotateLeft();
- x = root;
- }
- }
- else {
- Box sib = leftOf(peerTree_parent(x));
- if (colorOf(sib) == RED) {
- setColor(sib, BLACK);
- setColor(peerTree_parent(x), RED);
- root = peerTree_parent(x).rotateRight();
- sib = leftOf(peerTree_parent(x));
- }
- if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) {
- setColor(sib, RED);
- x = peerTree_parent(x);
- }
- else {
- if (colorOf(leftOf(sib)) == BLACK) {
- setColor(rightOf(sib), BLACK);
- setColor(sib, RED);
- root = sib.rotateLeft();
- sib = leftOf(peerTree_parent(x));
- }
- setColor(sib, colorOf(peerTree_parent(x)));
- setColor(peerTree_parent(x), BLACK);
- setColor(leftOf(sib), BLACK);
- root = peerTree_parent(x).rotateRight();
- x = root;
- }
- }
- }
- setColor(x, BLACK);
- 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.putAndTriggerJSTraps("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);
- }
-
- /** returns the root of the surface that this box belongs to */
- public final Box getRoot() {
- if (parent == null && Surface.fromBox(this) != null) return this;
- if (parent == null) return null;
- return parent.getRoot();
- }
-
- 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) putAndTriggerJSTraps("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) putAndTriggerJSTraps("childadded", value);
- redirect.put(i, value);
- if (value == null) {
- Box b = (Box)redirect.get(new Integer(i));
- if (b != null) putAndTriggerJSTraps("childremoved", b);
- }
-
- } else if (value == null) {
- if (i < 0 || i > numchildren) return;
- Box b = getChild(i);
- b.remove();
- putAndTriggerJSTraps("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();
- putAndTriggerJSTraps("childadded", b);
- }
- }
-}
projects / org.ibex.core.git / commitdiff