// 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();
        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);
        }
    }
}