1 // Copyright 2002 Adam Megacz, see the COPYING file for licensing [GPL]
6 /** all the boxtree manipulation code goes here */
7 public final class BoxTree extends Box {
9 //#define MARK_REFLOW for(Box b2 = this; b2 != null && !b2.test(REFLOW); b2 = b2.parent) b2.set(REFLOW);
10 //#define MARK_REFLOW_b for(Box b2 = b; b2 != null && !b2.test(REFLOW); b2 = b2.parent) b2.set(REFLOW);
11 //#define MARK_RESIZE for(Box b2 = this; b2 != null && !b2.test(RESIZE); b2 = b2.parent) b2.set(RESIZE);
12 //#define MARK_RESIZE_b for(Box b2 = b; b2 != null && !b2.test(RESIZE); b2 = b2.parent) b2.set(RESIZE);
14 private static final boolean RED = false;
15 private static final boolean BLACK = true;
17 public final Box peerTree_leftmost() { for (Box p = this; ; p = p.left) if (p.left == null) return p; }
18 public final Box peerTree_rightmost() { for (Box p = this; ; p = p.right) if (p.right == null) return p; }
19 static Box peerTree_parent(Box p) { return (p == null)? null: p.peerTree_parent; }
21 public Box insertBeforeMe(Box cell) { left = cell; cell.peerTree_parent = this; return cell.fixAfterInsertion(); }
22 public Box insertAfterMe(Box cell) { right = cell; cell.peerTree_parent = this; return cell.fixAfterInsertion(); }
24 static boolean colorOf(Box p) { return (p == null) ? BLACK : p.test(Box.BLACK); }
25 static void setColor(Box p, boolean c) { if (p != null) { if (c) p.set(Box.BLACK); else p.clear(Box.BLACK); } }
26 static Box leftOf(Box p) { return (p == null)? null: p.left; }
27 static Box rightOf(Box p) { return (p == null)? null: p.right; }
29 public final Box nextSibling() {
31 return right.peerTree_leftmost();
33 Box p = peerTree_parent;
35 while (p != null && ch == p.right) { ch = p; p = p.peerTree_parent; }
40 public final Box prevSibling() {
42 return left.peerTree_rightmost();
44 Box p = peerTree_parent;
46 while (p != null && ch == p.left) { ch = p; p = p.peerTree_parent; }
51 public Box removeNode() {
52 Box root = peerTree_parent.rootChild;
54 // handle case where we are only node
55 if (left == null && right == null && peerTree_parent == null) return null;
57 // if strictly internal, swap places with a successor
58 if (left != null && right != null) {
59 Box s = nextSibling();
60 // To work nicely with arbitrary subclasses of Box, we don't want to
61 // just copy successor's fields. since we don't know what
62 // they are. Instead we swap positions in the tree.
63 root = swapPosition(this, s);
66 // Start fixup at replacement node (normally a child).
67 // But if no children, fake it by using self
69 if (left == null && right == null) {
71 if (test(Box.BLACK)) root = this.fixAfterDeletion();
73 // Unlink (Couldn't before since fixAfterDeletion needs peerTree_parent ptr)
75 if (peerTree_parent != null) {
76 if (this == peerTree_parent.left)
77 peerTree_parent.left = null;
78 else if (this == peerTree_parent.right)
79 peerTree_parent.right = null;
80 peerTree_parent = null;
85 Box replacement = left;
86 if (replacement == null) replacement = right;
88 // link replacement to peerTree_parent
89 replacement.peerTree_parent = peerTree_parent;
91 if (peerTree_parent == null) root = replacement;
92 else if (this == peerTree_parent.left) peerTree_parent.left = replacement;
93 else peerTree_parent.right = replacement;
97 peerTree_parent = null;
100 if (test(Box.BLACK)) root = replacement.fixAfterDeletion();
108 * Swap the linkages of two nodes in a tree.
109 * Return new root, in case it changed.
111 Box swapPosition(Box x, Box y) {
112 Box root = peerTree_parent.rootChild;
114 /* Too messy. TODO: find sequence of assigments that are always OK */
116 Box px = x.peerTree_parent;
117 boolean xpl = px != null && x == px.left;
121 Box py = y.peerTree_parent;
122 boolean ypl = py != null && y == py.left;
127 y.peerTree_parent = px;
128 if (px != null) if (xpl) px.left = y; else px.right = y;
129 x.peerTree_parent = y;
132 y.right = rx; if (rx != null) rx.peerTree_parent = y;
136 y.left = lx; if (lx != null) lx.peerTree_parent = y;
138 x.left = ly; if (ly != null) ly.peerTree_parent = x;
139 x.right = ry; if (ry != null) ry.peerTree_parent = x;
142 x.peerTree_parent = py;
143 if (py != null) if (ypl) py.left = x; else py.right = x;
144 y.peerTree_parent = x;
147 x.right = ry; if (ry != null) ry.peerTree_parent = x;
151 x.left = ly; if (ly != null) ly.peerTree_parent = x;
153 y.left = lx; if (lx != null) lx.peerTree_parent = y;
154 y.right = rx; if (rx != null) rx.peerTree_parent = y;
157 x.peerTree_parent = py; if (py != null) if (ypl) py.left = x; else py.right = x;
158 x.left = ly; if (ly != null) ly.peerTree_parent = x;
159 x.right = ry; if (ry != null) ry.peerTree_parent = x;
161 y.peerTree_parent = px; if (px != null) if (xpl) px.left = y; else px.right = y;
162 y.left = lx; if (lx != null) lx.peerTree_parent = y;
163 y.right = rx; if (rx != null) rx.peerTree_parent = y;
166 boolean c = x.test(Box.BLACK);
167 if (y.test(Box.BLACK)) x.set(Box.BLACK); else x.clear(Box.BLACK);
168 if (c) y.set(Box.BLACK); else y.clear(Box.BLACK);
170 if (root == x) root = y;
171 else if (root == y) root = x;
172 return parent.rootChild = root;
175 protected final Box rotateLeft() {
176 Box root = parent.rootChild;
179 if (r.left != null) r.left.peerTree_parent = this;
180 r.peerTree_parent = peerTree_parent;
181 if (peerTree_parent == null) root = r;
182 else if (peerTree_parent.left == this) peerTree_parent.left = r;
183 else peerTree_parent.right = r;
186 return parent.rootChild = root;
189 protected final Box rotateRight() {
190 Box root = parent.rootChild;
193 if (l.right != null) l.right.peerTree_parent = this;
194 l.peerTree_parent = peerTree_parent;
195 if (peerTree_parent == null) root = l;
196 else if (peerTree_parent.right == this) peerTree_parent.right = l;
197 else peerTree_parent.left = l;
200 return parent.rootChild;
203 protected final Box fixAfterInsertion() {
204 Box root = parent.rootChild;
208 while (x != null && x != root && !x.peerTree_parent.test(Box.BLACK)) {
209 if (peerTree_parent(x) == leftOf(peerTree_parent(peerTree_parent(x)))) {
210 Box y = rightOf(peerTree_parent(peerTree_parent(x)));
211 if (colorOf(y) == RED) {
212 setColor(peerTree_parent(x), BLACK);
214 setColor(peerTree_parent(peerTree_parent(x)), RED);
215 x = peerTree_parent(peerTree_parent(x));
218 if (x == rightOf(peerTree_parent(x))) {
219 x = peerTree_parent(x);
220 root = x.rotateLeft();
222 setColor(peerTree_parent(x), BLACK);
223 setColor(peerTree_parent(peerTree_parent(x)), RED);
224 if (peerTree_parent(peerTree_parent(x)) != null)
225 root = peerTree_parent(peerTree_parent(x)).rotateRight();
229 Box y = leftOf(peerTree_parent(peerTree_parent(x)));
230 if (colorOf(y) == RED) {
231 setColor(peerTree_parent(x), BLACK);
233 setColor(peerTree_parent(peerTree_parent(x)), RED);
234 x = peerTree_parent(peerTree_parent(x));
237 if (x == leftOf(peerTree_parent(x))) {
238 x = peerTree_parent(x);
239 root = x.rotateRight();
241 setColor(peerTree_parent(x), BLACK);
242 setColor(peerTree_parent(peerTree_parent(x)), RED);
243 if (peerTree_parent(peerTree_parent(x)) != null)
244 root = peerTree_parent(peerTree_parent(x)).rotateLeft();
249 return parent.rootChild = root;
253 protected final Box fixAfterDeletion() {
254 Box root = peerTree_parent.rootChild;
256 while (x != root && colorOf(x) == BLACK) {
257 if (x == leftOf(peerTree_parent(x))) {
258 Box sib = rightOf(peerTree_parent(x));
259 if (colorOf(sib) == RED) {
260 setColor(sib, BLACK);
261 setColor(peerTree_parent(x), RED);
262 root = peerTree_parent(x).rotateLeft();
263 sib = rightOf(peerTree_parent(x));
265 if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) {
267 x = peerTree_parent(x);
270 if (colorOf(rightOf(sib)) == BLACK) {
271 setColor(leftOf(sib), BLACK);
273 root = sib.rotateRight();
274 sib = rightOf(peerTree_parent(x));
276 setColor(sib, colorOf(peerTree_parent(x)));
277 setColor(peerTree_parent(x), BLACK);
278 setColor(rightOf(sib), BLACK);
279 root = peerTree_parent(x).rotateLeft();
284 Box sib = leftOf(peerTree_parent(x));
285 if (colorOf(sib) == RED) {
286 setColor(sib, BLACK);
287 setColor(peerTree_parent(x), RED);
288 root = peerTree_parent(x).rotateRight();
289 sib = leftOf(peerTree_parent(x));
291 if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) {
293 x = peerTree_parent(x);
296 if (colorOf(leftOf(sib)) == BLACK) {
297 setColor(rightOf(sib), BLACK);
299 root = sib.rotateLeft();
300 sib = leftOf(peerTree_parent(x));
302 setColor(sib, colorOf(peerTree_parent(x)));
303 setColor(peerTree_parent(x), BLACK);
304 setColor(leftOf(sib), BLACK);
305 root = peerTree_parent(x).rotateRight();
311 return parent.rootChild = root;
314 // Tree Manipulation /////////////////////////////////////////////////////////////////////
316 /** remove this node from its parent; INVARIANT: whenever the parent of a node is changed, remove() gets called. */
317 public void remove() {
318 if (parent == null) {
319 Surface surface = Surface.fromBox(this);
320 if (surface != null) surface.dispose(true);
323 parent.numchildren--;
325 Box oldparent = parent;
326 if (oldparent == null) return;
332 if (oldparent != null) { Box b = oldparent; MARK_REFLOW_b; }
333 if (oldparent != null) oldparent.putAndTriggerJSTraps("childremoved", this);
336 /** Returns ith child */
337 public Box getChild(int i) {
338 // FIXME: store numleft and numright in the tree
339 Box left = rootChild;
340 if (left == null) return null;
341 while (left.left != null) left = left.left;
342 for(; i > 0; i--) left = left.nextSibling();
346 /** Returns our index in our parent */
347 public int getIndexInParent() {
348 // FIXME: store numleft and numright in the tree
349 if (peerTree_parent == null) return left == null ? 0 : left.numPeerChildren();
350 else if (peerTree_parent.left == this) return peerTree_parent.getIndexInParent() - 1;
351 else if (peerTree_parent.right == this) return peerTree_parent.getIndexInParent() + 1;
352 else throw new Error("we're not a child of our parent!");
355 public int numPeerChildren() {
356 return (left == null ? 0 : left.numPeerChildren() + 1) + (right == null ? 0 : right.numPeerChildren() + 1);
359 /** returns the root of the surface that this box belongs to */
360 public final Box getRoot() {
361 if (parent == null && Surface.fromBox(this) != null) return this;
362 if (parent == null) return null;
363 return parent.getRoot();
366 public void put(int i, Object value) {
369 if (value != null && !(value instanceof Box)) {
370 if (Log.on) Log.logJS(this, "attempt to set a numerical property on a box to a non-box");
374 if (redirect == null) {
375 if (value == null) putAndTriggerJSTraps("childremoved", getChild(i));
376 else Log.logJS(this, "attempt to add/remove children to/from a node with a null redirect");
378 } else if (redirect != this) {
379 if (value != null) putAndTriggerJSTraps("childadded", value);
380 redirect.put(i, value);
382 Box b = (Box)redirect.get(new Integer(i));
383 if (b != null) putAndTriggerJSTraps("childremoved", b);
386 } else if (value == null) {
387 if (i < 0 || i > numchildren) return;
390 putAndTriggerJSTraps("childremoved", b);
395 // check if box being moved is currently target of a redirect
396 for(Box cur = b.parent; cur != null; cur = cur.parent)
397 if (cur.redirect == b) {
398 if (Log.on) Log.logJS(this, "attempt to move a box that is the target of a redirect");
402 // check for recursive ancestor violation
403 for(Box cur = this; cur != null; cur = cur.parent)
405 if (Log.on) Log.logJS(this, "attempt to make a node a parent of its own ancestor");
406 if (Log.on) Log.log(this, "box == " + this + " ancestor == " + b);
414 Box before = getChild(i);
415 if (before == null) rootChild.peerTree_rightmost().insertAfterMe(b);
416 else before.insertBeforeMe(b);
418 // need both of these in case child was already uncalc'ed
423 putAndTriggerJSTraps("childadded", b);