From 4ec2efbf4728b2db0225443dbcc59a3b6083ee07 Mon Sep 17 00:00:00 2001 From: megacz Date: Fri, 30 Jan 2004 07:41:42 +0000 Subject: [PATCH] 2003/11/17 10:18:31 darcs-hash:20040130074142-2ba56-5342b683f76f1be1d6c8eec806cf411516411eb6.gz --- Makefile | 4 +- src/org/xwt/Box.java | 466 ++++++++++++++++++++++++++++++++++++++++++---- src/org/xwt/BoxTree.java | 429 ------------------------------------------ 3 files changed, 434 insertions(+), 465 deletions(-) delete mode 100644 src/org/xwt/BoxTree.java diff --git a/Makefile b/Makefile index bb82c5f..6cb0ce6 100644 --- a/Makefile +++ b/Makefile @@ -331,7 +331,7 @@ dist-private: # this is for Adam; don't mess with it -test: JVM; /System/Library/Frameworks/JavaVM.framework/Versions/1.3.1/Commands/java -jar build/JVM/xwt.jar http://localhost/demo.xwar -#test: JVM; java -jar build/JVM/xwt.jar http://localhost/demo.xwar +#test: JVM; /System/Library/Frameworks/JavaVM.framework/Versions/1.3.1/Commands/java -jar build/JVM/xwt.jar http://localhost/demo.xwar +test: JVM; java -jar build/JVM/xwt.jar http://localhost/demo.xwar oldcompile: preprocess; CLASSPATH=$$CLASSPATH:lib/libgcj-minimal.jar javac -d build/class `find build/java/ src/org/xwt/mips -name \*.java` diff --git a/src/org/xwt/Box.java b/src/org/xwt/Box.java index 0d23a6f..e8fb03d 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 implements JSTrap.JSTrappable { // Macros ////////////////////////////////////////////////////////////////////// @@ -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); @@ -186,8 +186,8 @@ public abstract class Box extends JSScope implements JSTrap.JSTrappable { private static LENGTH[] rowMaxHeight = new LENGTH[65535]; static { for(int i=0; ib) 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); + } + } + } diff --git a/src/org/xwt/BoxTree.java b/src/org/xwt/BoxTree.java deleted file mode 100644 index 86f1566..0000000 --- a/src/org/xwt/BoxTree.java +++ /dev/null @@ -1,429 +0,0 @@ -// 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); - } - } -} -- 1.7.10.4