// Copyright (C) 2003 Adam Megacz <adam@xwt.org> all rights reserved.
//
// You may modify, copy, and redistribute this code under the terms of
// the GNU Library Public License version 2.1, with the exception of
// the portion of clause 6a after the semicolon (aka the "obnoxious
// relink clause")

package org.xwt.util;

// FEATURE: private void intersection() { }
// FEATURE: private void union() { }
// FEATURE: private void subset() { }
// FEATURE: grow if we run out of slots

/** a weight-balanced tree with fake leaves */
public class BalancedTree {


    // Instance Variables ///////////////////////////////////////////////////////////////////

    private int root = 0;                         ///< the slot of the root element

    private int cached_index = -1;
    private int cached_slot = -1;

    // Public API //////////////////////////////////////////////////////////////////////////

    /** the number of elements in the tree */
    public final int treeSize() { return root == 0 ? 0 : size[root]; }

    /** clamps index to [0..treeSize()] and inserts object o *before* the specified index */
    public final synchronized void insertNode(int index, Object o) {
        if(o == null) throw new Error("can't insert nulls in the balanced tree");
        cached_slot = cached_index = -1;
        if (index < 0) index = 0;
        if (index > treeSize()) index = treeSize();
        int arg = allocateSlot(o);
        if (root != 0) {
            insert(index, arg, root, 0, false, false);
        } else {
            root = arg;
            left[arg] = right[arg] = parent[arg] = 0;
            size[arg] = 1;
        }
    }

    /** clamps index to [0..treeSize()-1] and replaces the object at that index with object o */
    public final synchronized void replaceNode(int index, Object o) {
        if(o == null) throw new Error("can't insert nulls in the balanced tree");
        cached_slot = cached_index = -1;
        if(root == 0) throw new Error("called replaceNode() on an empty tree");
        if (index < 0) index = 0;
        if (index >= treeSize()) index = treeSize() - 1;
        int arg = allocateSlot(o);
        insert(index, arg, root, 0, true, false);
    }

    /** returns the index of o; runs in O((log n)^2) time unless cache hit */
    public final synchronized int indexNode(Object o) { 
        if(o == null) return -1;
        if (cached_slot != -1 && objects[cached_slot] == o) return cached_index;

        int slot = getSlot(o);
        if(slot == -1) return -1;
        
        int index = 0;
        while(true) {
            // everything to the left is before us so add that to the index
            index += sizeof(left[slot]);
            // we are before anything on the right
            while(left[parent[slot]] == slot) slot = parent[slot];
            // we end of the first node who isn't on the left, go to the node that has as its child
            slot = parent[slot];
            // if we just processed the root we're done
            if(slot == 0) break;
            // count the node we're currently on towards the index
            index++;
        }
        return index;
    }

    /** returns the object at index; runs in O(log n) time unless cache hit */
    public final synchronized Object getNode(int index) {
        if (index == cached_index) return objects[cached_slot];

        if (cached_index != -1) {
            int distance = Math.abs(index - cached_index);
            // if the in-order distance between the cached node and the
            // target node is less than log(n), it's probably faster to
            // search directly.
            if ((distance < 16) && ((2 << distance) < treeSize())) {
                while(cached_index > index) { cached_slot = prev(cached_slot); cached_index--; }
                while(cached_index < index) { cached_slot = next(cached_slot); cached_index++; }
                return objects[cached_slot];
            }
        }
        /*
        cached_index = index;
        cached_slot = get(index, root);
        return objects[cached_slot];
        */
        return objects[get(index, root)];
    }

    /** deletes the object at index, returning the deleted object */
    public final synchronized Object deleteNode(int index) {
        cached_slot = cached_index = -1;
        // FIXME: left[], right[], size[], and parent[] aren't getting cleared properly somewhere in here where a node had two children
        int del = delete(index, root, 0);
        left[del] = right[del] = size[del] = parent[del] = 0;
        Object ret = objects[del];
        objects[del] = null;
        return ret;
    }
    
    public final synchronized void clear() {
        if(root == 0) return;
        int i = leftmost(root);
        do {
            int next = next(i);
            objects[i] = null;
            left[i] = right[i] = size[i] = parent[i] = 0;
            i = next;
        } while(i != 0);
        root = 0;
    }
    
    protected void finalize() { clear(); }


    // Node Data /////////////////////////////////////////////////////////////////////////

    private final static int NUM_SLOTS = 64 * 1024;
    // FEATURE: GROW - private final static int MAX_SLOT_DISTANCE = 32;

    /**
     * Every object inserted into *any* tree gets a "slot" in this
     * array.  The slot is determined by hashcode modulo the length of
     * the array, with quadradic probing to resolve collisions.  NOTE
     * that the "slot" of a node is NOT the same as its index.
     * Furthermore, if an object is inserted into multiple trees, that
     * object will have multiple slots.
     */
    private static Object[] objects = new Object[NUM_SLOTS];

    /// These two arrays hold the left and right children of each
    /// slot; in other words, left[x] is the *slot* of the left child
    /// of the node in slot x.
    ///
    /// If x has no left child, then left[x] is -1 multiplied by the
    /// slot of the node that precedes x; if x is the first node, then
    /// left[x] is 0.  The right[] array works the same way.
    ///
    private static int[] left = new int[NUM_SLOTS];
    private static int[] right = new int[NUM_SLOTS];
    
    /// The parent of this node (0 if it is the root node)
    private static int[] parent = new int[NUM_SLOTS];

    ///< the number of descendants of this node *including the node itself*
    private static int[] size = new int[NUM_SLOTS];


    // Slot Management //////////////////////////////////////////////////////////////////////
    
    /** if alloc == false returns the slot holding object o. if alloc is true returns a new slot for obejct o */
    private int getSlot(Object o, boolean alloc) {
        // we XOR with our own hashcode so that we don't get tons of
        // collisions when a single Object is inserted into multiple
        // trees
        int dest = Math.abs(o.hashCode() ^ this.hashCode()) % objects.length;
        Object search = alloc ? null : o;
        int odest = dest;
        boolean plus = true;
        int tries = 1;
        while (objects[dest] != search || !(alloc || root(dest) == root)) {
            if (dest == 0) dest++;
            dest = Math.abs((odest + (plus ? 1 : -1) * tries * tries) % objects.length);
            if (plus) tries++;
            plus = !plus;
            // FEATURE: GROW - if(tries > MAX_SLOT_DISTANCE) return -1;
        }
        return dest;
    }

    /** returns the slots holding object o */
    private int getSlot(Object o) { return getSlot(o,false); }
    
    /** allocates a new slot holding object o*/
    private int allocateSlot(Object o) {
        int slot = getSlot(o, true);
        // FEATURE: GROW - if(slot == -1) throw new Error("out of slots");
        objects[slot] = o;
        return slot;
    }



    // Helpers /////////////////////////////////////////////////////////////////////////

    private final int leftmost(int slot) { return left[slot] <= 0 ? slot : leftmost(left[slot]); }
    private final int rightmost(int slot) { return right[slot] <= 0 ? slot : rightmost(right[slot]); }
    private final int next(int slot) { return right[slot] <= 0 ? -1 * right[slot] : leftmost(right[slot]); }
    private final int prev(int slot) { return left[slot] <= 0 ? -1 * left[slot] : rightmost(left[slot]); }
    private final int sizeof(int slot) { return slot <= 0 ? 0 : size[slot]; }
    private final int root(int slot) { return parent[slot] == 0 ? slot : root(parent[slot]); }


    // Rotation and Balancing /////////////////////////////////////////////////////////////

    //      p                  p
    //      |                  |
    //      b                  d 
    //     / \                / \
    //    a   d    < == >    b   e
    //       / \            / \
    //      c   e          a   c
    // FIXME might be doing too much work here
    private void rotate(boolean toTheLeft, int b, int p) {
        int[] left = toTheLeft ? BalancedTree.left : BalancedTree.right;
        int[] right = toTheLeft ? BalancedTree.right : BalancedTree.left;
        int d = right[b];
        int c = left[d];
        if (d <= 0) throw new Error("rotation error");
        left[d] = b;
        if(size[b] <= 3) // b is now a leaf
            right[b] = -d;
        else
            right[b] = c;
        parent[b] = d;
        parent[d] = p;
        if(c > 0) parent[c] = b;
        if (p == 0)              root = d;
        else if (left[p] == b)   left[p] = d;
        else if (right[p] == b)  right[p] = d;
        else throw new Error("rotate called with invalid parent");
        size[b] = 1 + sizeof(left[b]) + sizeof(right[b]);
        size[d] = 1 + sizeof(left[d]) + sizeof(right[d]);
    }

    private void balance(int slot, int p) {
        if (slot <= 0) return;
        size[slot] = 1 + sizeof(left[slot]) + sizeof(right[slot]);
        if (sizeof(left[slot]) - 1 > 2 * sizeof(right[slot])) rotate(false, slot, p);
        else if (sizeof(left[slot]) * 2 < sizeof(right[slot]) - 1) rotate(true, slot, p);
    }



    // Insert /////////////////////////////////////////////////////////////////////////

    private void insert(int index, int arg, int slot, int p, boolean replace, boolean wentLeft) {
        int diff = slot <= 0 ? 0 : index - sizeof(left[slot]);
        if (slot > 0 && diff != 0) {
            if (diff < 0) insert(index, arg, left[slot], slot, replace, true);
            else insert(index - sizeof(left[slot]) - 1, arg, right[slot], slot, replace, false);
            balance(slot, p);
            return;
        }

        if (size[arg] != 0) throw new Error("double insertion");

        // we are replacing an existing node
        if (replace) {
            if (diff != 0) throw new Error("this should never happen"); // since we already clamped the index
            if (p == 0)                 root = arg;
            else if (left[p] == slot)   left[p] = arg;
            else if (right[p] == slot)  right[p] = arg;
            left[arg] = left[slot];
            right[arg] = right[slot];
            size[arg] = size[slot];
            parent[arg] = parent[slot];
            if(left[slot] > 0) parent[left[slot]] = arg;
            if(right[slot] > 0) parent[right[slot]] = arg;
            objects[slot] = null;
            left[slot] = right[slot] = size[slot] = parent[slot] = 0;
        
        // we become the child of a former leaf
        } else if (slot <= 0) {
            int[] left = wentLeft ? BalancedTree.left : BalancedTree.right;
            int[] right = wentLeft ? BalancedTree.right : BalancedTree.left;
            left[arg] = slot;
            left[p] = arg;
            right[arg] = -1 * p;
            parent[arg] = p;
            balance(arg, p);

        // we take the place of a preexisting node
        } else {
            left[arg] = left[slot];   // steal slot's left subtree
            left[slot] = -1 * arg;
            right[arg] = slot;        // make slot our right subtree
            parent[arg] = parent[slot];
            parent[slot] = arg;
            if (slot == root) {
                root = arg;
                balance(slot, arg);
                balance(arg, 0);
            } else {
                if (left[p] == slot)        left[p] = arg;
                else if (right[p] == slot)  right[p] = arg;
                else throw new Error("should never happen");
                balance(slot, arg);
                balance(arg, p);
            }
        }
    }


    // Retrieval //////////////////////////////////////////////////////////////////////

    private int get(int index, int slot) {
        int diff = index - sizeof(left[slot]);
        if (diff > 0) return get(diff - 1, right[slot]);
        else if (diff < 0) return get(index, left[slot]);
        else return slot;
    }


    // Deletion //////////////////////////////////////////////////////////////////////

    private int delete(int index, int slot, int p) {
        int diff = index - sizeof(left[slot]);
        if (diff < 0) {
            int ret = delete(index, left[slot], slot);
            balance(slot, p);
            return ret;

        } else if (diff > 0) {
            int ret = delete(diff - 1, right[slot], slot);
            balance(slot, p);
            return ret;

        // we found the node to delete
        } else {

            // fast path: it has no children
            if (left[slot] <= 0 && right[slot] <= 0) {
                if (p == 0) root = 0;
                else {
                    int[] side = left[p] == slot ? left : right;
                    side[p] = side[slot];      // fix parent's pointer
                }
                
            // fast path: it has no left child, so we replace it with its right child
            } else if (left[slot] <= 0) {
                if (p == 0) root = right[slot];
                else (left[p] == slot ? left : right)[p] = right[slot];     // fix parent's pointer
                parent[right[slot]] = p;
                left[leftmost(right[slot])] = left[slot];                             // fix our successor-leaf's fake right ptr
                balance(right[slot], p);

            // fast path; it has no right child, so we replace it with its left child
            } else if (right[slot] <= 0) {
                if (p == 0) root = left[slot];
                else (left[p] == slot ? left : right)[p] = left[slot];      // fix parent's pointer
                parent[left[slot]] = p;
                right[rightmost(left[slot])] = right[slot];                           // fix our successor-leaf's fake right ptr
                balance(left[slot], p);

            // node to be deleted has two children, so we replace it with its left child's rightmost descendant
            } else {
                int left_childs_rightmost = delete(sizeof(left[slot]) - 1, left[slot], slot);
                left[left_childs_rightmost] = left[slot];
                right[left_childs_rightmost] = right[slot];
                if(left[slot] > 0) parent[left[slot]] = left_childs_rightmost;
                if(right[slot] > 0) parent[right[slot]] = left_childs_rightmost;
                parent[left_childs_rightmost] = parent[slot];
                if (p == 0) root = left_childs_rightmost;
                else (left[p] == slot ? left : right)[p] = left_childs_rightmost;     // fix parent's pointer
                balance(left_childs_rightmost, p);
            }

            return slot;
        }
    }

    // Debugging ///////////////////////////////////////////////////////////////////////////
    
    public void printTree() {
        if(root == 0) System.err.println("Tree is empty");
        else printTree(root,0,false);
    }
    private void printTree(int node,int indent,boolean l) {
        for(int i=0;i<indent;i++) System.err.print("   ");
        if(node < 0) System.err.println((l?"Prev: " : "Next: ") + -node);
        else if(node == 0)  System.err.println(l ? "Start" : "End");
        else {
            System.err.print("" + node + ": " + objects[node]);
            System.err.println(" Parent: " + parent[node]);
            printTree(left[node],indent+1,true);
            printTree(right[node],indent+1,false);
        }
    }
}