import java.util.ArrayList;
import java.util.Comparator;
import java.util.TreeSet;

/*
 * Created on 08.07.2005
 *
 */

public class Tree {
    final private int minDegree;
    final private Comparator comp;
   
    private Node root;
   
    public Tree(final int minDegree, final Comparator comp) {
        this.minDegree = minDegree;
        this.comp = comp;
        this.root = new Node(minDegree);
    }
   
    public boolean insert(final Object key) {
        if (this.root.isFull()) { // root is full and will be split
            final Node oldRoot = this.root;
            final Node newRoot = new Node(this.minDegree); // create a new root
            this.root = newRoot;
            newRoot.setLeaf(false);
            newRoot.setSubNode(0, oldRoot); // add old root as a child to the new root
            newRoot.splitFullChild(oldRoot, 0); // split the old (full) root into two nodes
            return insertNonFull(newRoot, key); // insert into the (not anymore full) root
        } else {
            return insertNonFull(this.root, key); // insert into a non-full root
        }
    }
   
    private boolean insertNonFull(final Node node, final Object key) {
        assert !node.isFull();
        if (node.isLeaf()) { // node is a leaf
            return node.insertKey(key, this.comp); // since the node is not full, we can simply insert
        } else { // node is an inner node
            int i = node.findInsertionPosition(key, this.comp); // find the position where to insert
            if (i >= 0) { // the node doesn't contain the key, we insert at the found insertion position
                final Node child = node.getSubNode(i); // get the child where we continue our insertion
                if (child.isFull()) {
                    node.splitFullChild(child, i); // split the full child
                    final int comp = this.comp.compare(key, node.getKey(i));
                    if (comp > 0) {
                        i++;
                    } else if (comp == 0) {
                        return false;
                    }
                }
                return insertNonFull(node.getSubNode(i), key);
            } else { // the node already contained the key
                return false;
            }
        }
    }
   
    public boolean delete(final Object key) {
        return delete(this.root, key);
    }
   
    private boolean delete(final Node node, final Object key) {
        final NodeSearchResult search = node.search(key, this.comp);
        if (search.isFound()) {
            deleteFromNode(node, search.getKeyIndex());
            return true;
        } else {
            if (node.isLeaf()) return false; // key not in tree
           
            final Node child = ensureFullEnoughChild(node, search.getKeyIndex());
            return delete(child, key);
        }
    }
   
    private Node ensureFullEnoughChild(final Node node, final int index) {
        Node child = node.getSubNode(index);
        Node leftSibling = null;
        Node rightSibling = null;
        if (!child.isFullEnough()) {
            if (index > 0) { // check left sibling
                leftSibling = node.getSubNode(index - 1);
                if (leftSibling.isFullEnough()) {
                    //System.out.println("case 3a left");
                    final Object pushdownKey = node.getKey(index - 1);
                    child.shiftAllRight();
                    child.setKey(0, pushdownKey);
                    child.setSubNode(0, leftSibling.getSubNode(leftSibling.getNumKeys()));
                    leftSibling.setSubNode(leftSibling.getNumKeys(), null); // not necessary
                    final Object pushupKey = leftSibling.getKey(leftSibling.getNumKeys() - 1);
                    leftSibling.removeKey(leftSibling.getNumKeys() - 1);
                    node.setKey(index - 1, pushupKey);
                }
            }
        }
       
        if (!child.isFullEnough()) {
            if (index < node.getNumKeys()) { // check right sibling
                rightSibling = node.getSubNode(index + 1);
                if (rightSibling.isFullEnough()) {
                    //System.out.println("case 3a right");
                    final Object pushdownKey = node.getKey(index);
                    child.insertKey(pushdownKey, this.comp);
                    child.setSubNode(child.getNumKeys(), rightSibling.getSubNode(0));
                    final Object pushupKey = rightSibling.getKey(0);
                    rightSibling.shiftAllLeft();
                    node.setKey(index, pushupKey);
                }
            }
        }
       
        if (!child.isFullEnough()) {
            if (leftSibling != null) {
                //System.out.println("case 3b left");
                node.mergeRightIntoLeftChild(leftSibling, index - 1, child);
                child = leftSibling;
            } else if (rightSibling != null) {
                //System.out.println("case 3b right");
                node.mergeRightIntoLeftChild(child, index, rightSibling);
            } else {
                assert false;
            }
            if (node == this.root && node.getNumKeys() == 0) {
                this.root = child;
            }
        }

        assert child.isFullEnough();
       
        return child;
    }

    private void deleteFromNode(final Node node, final int index) {
        if (node.isLeaf()) {
            //System.out.println("case 1");
            node.removeKey(index);
        } else {
            // delete key in non-leaf-node
            final Node leftChild = node.getSubNode(index);
            if (leftChild.isFullEnough()) {
                //System.out.println("case 2a");
                final TreeSearchResult maxSearch = this.findMax(leftChild);
                final Node maxNode = maxSearch.getNode();
                final Object maxKey = maxNode.getKey(maxSearch.getKeyIndex());
                node.setKey(index, maxKey);
                delete(leftChild, maxKey);
            } else {
                final Node rightChild = node.getSubNode(index + 1);
                if (rightChild.isFullEnough()) {
                    //System.out.println("case 2b");
                    final TreeSearchResult minSearch = this.findMin(rightChild);
                    final Node minNode = minSearch.getNode();
                    final Object minKey = minNode.getKey(minSearch.getKeyIndex());
                    node.setKey(index, minKey);
                    delete(rightChild, minKey);
                } else {
                    //System.out.println("case 2c");
                    final Object key = node.getKey(index);
                    node.mergeRightIntoLeftChild(leftChild, index, rightChild);
                    // delete right child
                    delete(leftChild, key);
                }
            }
        }
    }
   
    private TreeSearchResult findMax(final Node node) {
        if (node.isLeaf()) {
            return new TreeSearchResult(true, node, node.getNumKeys() - 1);
        } else {
            return findMax(node.getSubNode(node.getNumKeys()));
        }
    }
   
    private TreeSearchResult findMin(final Node node) {
        if (node.isLeaf()) {
            return new TreeSearchResult(true, node, 0);
        } else {
            return findMin(node.getSubNode(0));
        }
    }

    public void print() {
        this.root.print();
        System.out.println();
    }
   
    public Object[] getAll() {
        ArrayList list = new ArrayList();
        this.root.inOrder(list);
       
        return list.toArray();
    }
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/*
 * Created on 08.07.2005
 *
 */

class Node {
   
    private final int minDegree; // the minimum number of sub-nodes
    private final int maxSize; // the maximum number of keys
   
    private int numKeys; // the current number of keys
    private Object[] keys; // the keys
    private Node[] subNodes; // the subnodes
   
    private boolean leaf;
   
    Node(final int minDegree) {
        this.minDegree = minDegree;
        this.maxSize = minDegree * 2 - 1;
        this.keys = new Object[this.maxSize];
        this.subNodes = new Node[this.maxSize + 1];
        this.numKeys = 0;
        this.leaf = true;
    }
   
    NodeSearchResult search(final Object key, final Comparator comp) {
        final int i = Node.binarySearch(this.keys, key, this.numKeys - 1, comp);
        if (i >= 0) {
            return new NodeSearchResult(true, i);
        } else {
            return new NodeSearchResult(false, -(i + 1));
        }
    }
   
    void setLeaf(final boolean leaf) {
        this.leaf = leaf;
    }
   
    boolean isLeaf() {
        return this.leaf;
    }
   
    boolean isFull() {
        return (this.numKeys == this.maxSize);
    }
   
    boolean isFullEnough() {
        return (this.numKeys >= this.minDegree);
    }

    void setSubNode(final int i, final Node node) {
        this.subNodes[i] = node;
    }
   
    void setKey(final int i, final Object key) {
        this.keys[i] = key;
    }

    /**
     * Splits the i-th sub-node of this node into two nodes and moves the median of the i-th sub-node up into this node
     * @param i
     */
    void splitFullChild(final Node fullChildNode, final int i) {
        final Node newNode = new Node(this.minDegree);
       
        newNode.leaf = fullChildNode.leaf;
        newNode.numKeys = this.minDegree - 1;
       
        /* move upper half of the keys and possible subnodes from the full child to the new node */
        System.arraycopy(fullChildNode.keys, this.minDegree, newNode.keys, 0, this.minDegree - 1);
        Arrays.fill(fullChildNode.keys, this.minDegree, this.maxSize, null); // not necessary, note: the end index is not included!!
       
        if (!fullChildNode.leaf) {
            System.arraycopy(fullChildNode.subNodes, this.minDegree, newNode.subNodes, 0, this.minDegree);
            Arrays.fill(fullChildNode.subNodes, this.minDegree, this.maxSize, null); // not necessary
        }
        fullChildNode.numKeys = this.minDegree - 1;
       
        /* make space in this node for the new child node and add it */
        System.arraycopy(this.subNodes, i, this.subNodes, i + 1, this.numKeys + 1 - i);
        this.subNodes[i + 1] = newNode;
        System.arraycopy(this.keys, i, this.keys, i + 1, this.numKeys - i);
        this.keys[i] = fullChildNode.keys[this.minDegree - 1];
        fullChildNode.keys[this.minDegree - 1] = null; // not necessary
        this.numKeys++;
    }
   
   
    /**
     * Merges the right child (the one right of keyIndex) with the left child (left of keyIndex). The keys and subnodes
     * of the right child are copied into the left child. The current nodes key at the keyIndex position drops down to the
     * left child as well. The right child is removed from the tree.
     */
    void mergeRightIntoLeftChild(final Node leftChild, final int keyIndex, final Node rightChild) {
        leftChild.keys[leftChild.numKeys] = this.keys[keyIndex];
        leftChild.numKeys++;
       
        System.arraycopy(this.keys, keyIndex + 1, this.keys, keyIndex, this.numKeys - 1 - keyIndex);
        System.arraycopy(this.subNodes, keyIndex + 2, this.subNodes, keyIndex + 1, this.numKeys - 1 - keyIndex);
       
        this.keys[this.numKeys - 1] = null; // not necessary
        this.subNodes[this.numKeys] = null; // not necessary
        this.numKeys--;
       
        System.arraycopy(rightChild.keys, 0, leftChild.keys, leftChild.numKeys, rightChild.numKeys);
        System.arraycopy(rightChild.subNodes, 0, leftChild.subNodes, leftChild.numKeys, rightChild.numKeys);
       
        leftChild.numKeys += rightChild.numKeys;
        leftChild.subNodes[leftChild.numKeys] = rightChild.subNodes[rightChild.numKeys];
    }
   
    int findInsertionPosition(final Object key, final Comparator comp) {
        return -(Node.binarySearch(this.keys, key, this.numKeys - 1, comp) + 1);
    }
   
    boolean insertKey(final Object key, final Comparator comp) {
        final int i = this.findInsertionPosition(key, comp);
        if (i >= 0) {
            System.arraycopy(this.keys, i, this.keys, i + 1, this.numKeys - i);
            this.keys[i] = key;
            this.numKeys++;
            return true;
        } else {
            return false;
        }
    }
   
    void shiftAllRight() {
        System.arraycopy(this.keys, 0, this.keys, 1, this.numKeys);
        System.arraycopy(this.subNodes, 0, this.subNodes, 1, this.numKeys + 1);
        this.subNodes[0] = null; // not necessary
        this.keys[0] = null; // not necessary
        this.numKeys++;
    }
   
    void shiftAllLeft() {
        System.arraycopy(this.keys, 1, this.keys, 0, this.numKeys - 1);
        System.arraycopy(this.subNodes, 1, this.subNodes, 0, this.numKeys);
        this.keys[this.numKeys - 1] = null; // not necessary
        this.subNodes[this.numKeys] = null; // not necessary
        this.numKeys--;
    }
   
    /**
     * Removes a key (and only the key) from the node. If this is not a leaf care has to be taken of the subNodes.
     *
     * @param keyIndex the index of the key to delete
     */
    void removeKey(final int keyIndex) {
        System.arraycopy(this.keys, keyIndex + 1, this.keys, keyIndex, this.numKeys - 1 - keyIndex);
        this.keys[this.numKeys - 1] = null; // not necessary
        this.numKeys--;
    }

    Object getKey(final int i) {
        return this.keys[i];
    }

    Node getSubNode(final int i) {
        return this.subNodes[i];
    }
   
    int getNumKeys() {
        return this.numKeys;
    }
   
    public static int binarySearch(final Object[] a, final Object key, int high, final Comparator c) {
        int low = 0;

        while (low <= high) {
            final int mid = (low + high) >> 1;
            final Object midVal = a[mid];
            final int cmp = c.compare(midVal, key);

            if (cmp < 0) {
                low = mid + 1;
            } else if (cmp > 0) {
                high = mid - 1;
            } else {
                return mid; // key found
            }
        }
   
        return -(low + 1);  // key not found.
    }
}