src/org/xwt/BoxTree.java

   1 // Copyright 2002 Adam Megacz, see the COPYING file for licensing [GPL]
   2 package org.xwt;
   3 import org.xwt.js.*;
   4 import org.xwt.util.*;
   5
   6 /** all the boxtree manipulation code goes here */
   7 public final class BoxTree extends Box {
   8
   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);
  13
  14     private static final boolean RED = false;
  15     private static final boolean BLACK = true;
  16
  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; }
  20
  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(); }
  23
  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; }
  28
  29     public final Box nextSibling() {
  30         if (right != null)
  31             return right.peerTree_leftmost();
  32         else {
  33             Box p = peerTree_parent;
  34             Box ch = this;
  35             while (p != null && ch == p.right) { ch = p; p = p.peerTree_parent; }
  36             return p;
  37         }
  38     }
  39
  40     public final Box prevSibling() {
  41         if (left != null)
  42             return left.peerTree_rightmost();
  43         else {
  44             Box p = peerTree_parent;
  45             Box ch = this;
  46             while (p != null && ch == p.left) { ch = p; p = p.peerTree_parent; }
  47             return p;
  48         }
  49     }
  50
  51     public Box removeNode() {
  52         Box root = peerTree_parent.rootChild;
  53
  54         // handle case where we are only node
  55         if (left == null && right == null && peerTree_parent == null) return null;
  56
  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);
  64         }
  65
  66         // Start fixup at replacement node (normally a child).
  67         // But if no children, fake it by using self
  68
  69         if (left == null && right == null) {
  70
  71             if (test(Box.BLACK)) root = this.fixAfterDeletion();
  72
  73             // Unlink  (Couldn't before since fixAfterDeletion needs peerTree_parent ptr)
  74
  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;
  81             }
  82
  83         }
  84         else {
  85             Box replacement = left;
  86             if  (replacement == null) replacement = right;
  87
  88             // link replacement to peerTree_parent
  89             replacement.peerTree_parent = peerTree_parent;
  90
  91             if (peerTree_parent == null)             root = replacement;
  92             else if (this == peerTree_parent.left)  peerTree_parent.left  = replacement;
  93             else                             peerTree_parent.right = replacement;
  94
  95             left = null;
  96             right = null;
  97             peerTree_parent = null;
  98
  99             // fix replacement
 100             if (test(Box.BLACK)) root = replacement.fixAfterDeletion();
 101
 102         }
 103
 104         return root;
 105     }
 106
 107     /**
 108      * Swap the linkages of two nodes in a tree.
 109      * Return new root, in case it changed.
 110      **/
 111     Box swapPosition(Box x, Box y) {
 112         Box root = peerTree_parent.rootChild;
 113
 114         /* Too messy. TODO: find sequence of assigments that are always OK */
 115
 116         Box px = x.peerTree_parent;
 117         boolean xpl = px != null && x == px.left;
 118         Box lx = x.left;
 119         Box rx = x.right;
 120
 121         Box py = y.peerTree_parent;
 122         boolean ypl = py != null && y == py.left;
 123         Box ly = y.left;
 124         Box ry = y.right;
 125
 126         if (x == py) {
 127             y.peerTree_parent = px;
 128             if (px != null) if (xpl) px.left = y; else px.right = y;
 129             x.peerTree_parent = y;
 130             if (ypl) {
 131                 y.left = x;
 132                 y.right = rx; if (rx != null) rx.peerTree_parent = y;
 133             }
 134             else {
 135                 y.right = x;
 136                 y.left = lx;   if (lx != null) lx.peerTree_parent = y;
 137             }
 138             x.left = ly;   if (ly != null) ly.peerTree_parent = x;
 139             x.right = ry;  if (ry != null) ry.peerTree_parent = x;
 140         }
 141         else if (y == px) {
 142             x.peerTree_parent = py;
 143             if (py != null) if (ypl) py.left = x; else py.right = x;
 144             y.peerTree_parent = x;
 145             if (xpl) {
 146                 x.left = y;
 147                 x.right = ry; if (ry != null) ry.peerTree_parent = x;
 148             }
 149             else {
 150                 x.right = y;
 151                 x.left = ly;   if (ly != null) ly.peerTree_parent = x;
 152             }
 153             y.left = lx;   if (lx != null) lx.peerTree_parent = y;
 154             y.right = rx;  if (rx != null) rx.peerTree_parent = y;
 155         }
 156         else {
 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;
 160
 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;
 164         }
 165
 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);
 169
 170         if (root == x) root = y;
 171         else if (root == y) root = x;
 172         return parent.rootChild = root;
 173     }
 174
 175     protected final Box rotateLeft() {
 176         Box root = parent.rootChild;
 177         Box r = right;
 178         right = r.left;
 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;
 184         r.left = this;
 185         peerTree_parent = r;
 186         return parent.rootChild = root;
 187     }
 188
 189     protected final Box rotateRight() {
 190         Box root = parent.rootChild;
 191         Box l = left;
 192         left = l.right;
 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;
 198         l.right = this;
 199         peerTree_parent = l;
 200         return parent.rootChild;
 201     }
 202
 203     protected final Box fixAfterInsertion() {
 204         Box root = parent.rootChild;
 205         clear(Box.BLACK);
 206         Box x = this;
 207
 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);
 213                     setColor(y, BLACK);
 214                     setColor(peerTree_parent(peerTree_parent(x)), RED);
 215                     x = peerTree_parent(peerTree_parent(x));
 216                 }
 217                 else {
 218                     if (x == rightOf(peerTree_parent(x))) {
 219                         x = peerTree_parent(x);
 220                         root = x.rotateLeft();
 221                     }
 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();
 226                 }
 227             }
 228             else {
 229                 Box y = leftOf(peerTree_parent(peerTree_parent(x)));
 230                 if (colorOf(y) == RED) {
 231                     setColor(peerTree_parent(x), BLACK);
 232                     setColor(y, BLACK);
 233                     setColor(peerTree_parent(peerTree_parent(x)), RED);
 234                     x = peerTree_parent(peerTree_parent(x));
 235                 }
 236                 else {
 237                     if (x == leftOf(peerTree_parent(x))) {
 238                         x = peerTree_parent(x);
 239                         root = x.rotateRight();
 240                     }
 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();
 245                 }
 246             }
 247         }
 248         root.set(Box.BLACK);
 249         return parent.rootChild = root;
 250     }
 251
 252     /** From CLR **/
 253     protected final Box fixAfterDeletion() {
 254         Box root = peerTree_parent.rootChild;
 255         Box x = this;
 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));
 264                 }
 265                 if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) {
 266                     setColor(sib,  RED);
 267                     x = peerTree_parent(x);
 268                 }
 269                 else {
 270                     if (colorOf(rightOf(sib)) == BLACK) {
 271                         setColor(leftOf(sib), BLACK);
 272                         setColor(sib, RED);
 273                         root = sib.rotateRight();
 274                         sib = rightOf(peerTree_parent(x));
 275                     }
 276                     setColor(sib, colorOf(peerTree_parent(x)));
 277                     setColor(peerTree_parent(x), BLACK);
 278                     setColor(rightOf(sib), BLACK);
 279                     root = peerTree_parent(x).rotateLeft();
 280                     x = root;
 281                 }
 282             }
 283             else {
 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));
 290                 }
 291                 if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) {
 292                     setColor(sib,  RED);
 293                     x = peerTree_parent(x);
 294                 }
 295                 else {
 296                     if (colorOf(leftOf(sib)) == BLACK) {
 297                         setColor(rightOf(sib), BLACK);
 298                         setColor(sib, RED);
 299                         root = sib.rotateLeft();
 300                         sib = leftOf(peerTree_parent(x));
 301                     }
 302                     setColor(sib, colorOf(peerTree_parent(x)));
 303                     setColor(peerTree_parent(x), BLACK);
 304                     setColor(leftOf(sib), BLACK);
 305                     root = peerTree_parent(x).rotateRight();
 306                     x = root;
 307                 }
 308             }
 309         }
 310         setColor(x, BLACK);
 311         return parent.rootChild = root;
 312     }
 313
 314     // Tree Manipulation /////////////////////////////////////////////////////////////////////
 315
 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);
 321             return;
 322         } else {
 323             parent.numchildren--;
 324         }
 325         Box oldparent = parent;
 326         if (oldparent == null) return;
 327         MARK_REFLOW;
 328         dirty();
 329         clear(MOUSEINSIDE);
 330         removeNode();
 331         parent = null;
 332         if (oldparent != null) { Box b = oldparent; MARK_REFLOW_b; }
 333         if (oldparent != null) oldparent.putAndTriggerJSTraps("childremoved", this);
 334     }
 335
 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();
 343         return left;
 344     }
 345
 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() + 1;
 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!");
 353     }
 354
 355     public int numPeerChildren() {
 356         return (left == null ? 0 : left.numPeerChildren() + 1) + (right == null ? 0 : right.numPeerChildren() + 1);
 357     }
 358
 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();
 364     }
 365
 366     public void put(int i, Object value) {
 367         if (i < 0) return;
 368
 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");
 371             return;
 372         }
 373
 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");
 377
 378         } else if (redirect != this) {
 379             if (value != null) putAndTriggerJSTraps("childadded", value);
 380             redirect.put(i, value);
 381             if (value == null) {
 382                 Box b = (Box)redirect.get(new Integer(i));
 383                 if (b != null) putAndTriggerJSTraps("childremoved", b);
 384             }
 385
 386         } else if (value == null) {
 387             if (i < 0 || i > numchildren) return;
 388             Box b = getChild(i);
 389             b.remove();
 390             putAndTriggerJSTraps("childremoved", b);
 391
 392         } else {
 393             Box b = (Box)value;
 394
 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");
 399                     return;
 400                 }
 401
 402             // check for recursive ancestor violation
 403             for(Box cur = this; cur != null; cur = cur.parent)
 404                 if (cur == b) {
 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);
 407                     return;
 408                 }
 409
 410             b.remove();
 411             b.parent = this;
 412             numchildren++;
 413
 414             Box before = getChild(i);
 415             if (before == null) {
 416                 if (rootChild == null) rootChild = b;
 417                 else rootChild.peerTree_rightmost().insertAfterMe(b);
 418             }
 419             else before.insertBeforeMe(b);
 420
 421             // need both of these in case child was already uncalc'ed
 422             MARK_REFLOW_b;
 423             MARK_REFLOW;
 424
 425             b.dirty();
 426             putAndTriggerJSTraps("childadded", b);
 427         }
 428     }
 429 }