/**
 * Implementation of the dictionary ADT with a thread-safe B-slack tree.
 * Copyright (C) 2014 Trevor Brown
 * Contact (tabrown [at] cs [dot] toronto [dot] edu) with questions or comments.
 *
 * Details of the B-slack tree algorithm appear in the paper:
 *    Brown, Trevor. B-slack trees: space efficient B-trees. SWAT 2014.
 * 
 * This tree is thread-safe, so multiple threads can perform operations on it
 * at the same time.  Updates synchronize with a single coarse-grained lock,
 * so only one updater can work at a time. However, one particularly nice
 * property of this implementation is that searches can proceed without any
 * synchronization. Therefore, searches are not blocked by updates, and are
 * very fast.
 * 
 * Unfortunately, in Java, you cannot embed arrays inside nodes, so nodes
 * contain pointers to key/value arrays. This makes the tree somewhat less
 * efficient in Java. This is a reference implementation intended to show how
 * to produce a simple implementation of a B-slack tree. The intention is to
 * provide others with a guide they can use to produce a simple B-slack tree
 * implementation in a language that gives more control over memory layout,
 * such as C or C++. Better implementations are possible. See the full version
 * of the paper for discussion of the algorithm and implementation details.
 * 
 * The paper leaves it up to the implementer to decide when and how to perform
 * rebalancing steps (i.e., Root-Zero, Root-Replace, Absorb, Split, Compress
 * and One-Child). In this implementation, since there is only one updater, it
 * is fairly straightforward to keep track of violations and fix them using
 * a recursive procedure. The recursive procedure is designed as follows.
 * After performing a rebalancing step, recursive invocations are made for every
 * rebalancing step that are needed as a consequence. If an invocation I is
 * trying to fix a violation at a node that has already been replaced by another
 * invocation I', then I can hand off responsibility for fixing the violation to
 * I'. Designing the rebalancing procedure to allow responsibility to be handed
 * off in this manner is not difficult; it simply requires going through each
 * rebalancing step S and observing which nodes involved in S can have
 * violations after S (and then making a recursive call for each violation).
 * 
 * Updated Oct 22, 2014.
 * 
 * -----------------------------------------------------------------------------
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

package algorithms.published;

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

/**
 *
 * @author Trevor Brown
 */
public class SyncBSlackTreeMap<K extends Comparable<? super K>,V> {
    
    public final Comparator<? super K> comparator;
    public final int b;
    private int size;
    private final Node<K> root;
    
    /**
     * Creates a new B-slack tree wherein: <br>
     *      each internal node has up to 16 child pointers, and <br>
     *      each leaf has up to 16 key/value pairs.
     */
    public SyncBSlackTreeMap() {
        this(16);
    }
    
    /**
     * Creates a new B-slack tree wherein: <br>
     *      each internal node has up to <code>nodeCapacity</code> child pointers, and <br>
     *      each leaf has up to <code>nodeCapacity</code> key/value pairs.
     */
    public SyncBSlackTreeMap(final int nodeCapacity) {
        this(nodeCapacity, null);
    }
    
    /**
     * Creates a new B-slack tree wherein: <br>
     *      each internal node has up to <code>nodeCapacity</code> child pointers, and <br>
     *      each leaf has up to <code>nodeCapacity</code> key/value pairs, and <br>
     *      keys are ordered according to the provided comparator.
     */
    public SyncBSlackTreeMap(final int nodeCapacity, final Comparator comparator) {
        this.b = nodeCapacity;
        this.comparator = comparator;
        this.root = new Node(
                new Object[0], // maybe can be null
                null,
                (Node<K>[]) new Node[]{
                    new Node<K>(
                        new Object[0],
                        new Object[0],
                        null,
                        true)
                },
                true);
    }
    
    /**
     * Returns true if the dictionary contains key and false otherwise.
     */
    public boolean containsKey(final K key) {
        return get(key) != null;
    }
    
    /**
     * Returns the value associated with key, or null if key is not in the
     * dictionary.
     */
    public V get(final K key) {
        final Comparable<? super K> k = comparable(key);
        Node<K> l = root.children[0];
        while (true) {
            if (l.isLeaf()) break;
            l = l.children[l.getChildIndex(k)];
        }
        final int keyIndex = l.getKeyIndex(k);
        return (l.containsKey(keyIndex)) ? (V) l.values[keyIndex] : null;
    }
    
    /**
     * Inserts a key/value pair into the dictionary if key is not already
     * present, and does not change the data structure otherwise.
     * Precondition: key != null
     * 
     * @param key key to insert into the dictionary
     * @param value value to associate with key
     * @return true if the key/value pair was inserted into the dictionary,
     *         and false if key was already in the dictionary.
     */
    public synchronized boolean putIfAbsent(final K key, final V value) {
        return doPut(key, value, false) == null;
    }
    /**
     * Inserts a key/value pair into the dictionary, replacing any previous
     * value associated with the key.
     * Precondition: key != null
     * 
     * @param key key to insert into the dictionary
     * @param value value to associate with key
     * @return the value associated with key just before this operation, and
     *         null if key was not previously in the dictionary.
     */
    public synchronized V put(final K key, final V value) {
        return doPut(key, value, true);
    }
    private V doPut(final K key, final V value, final boolean replace) {
        /**
         * search.
         */
        final Comparable<? super K> k = comparable(key);
        Node<K> gp = null;
        Node<K> p = root;
        Node<K> l = p.children[0];
        int ixToP = -1;
        int ixToL = -1;
        int ix = 0;
        while (true) {
            ixToP = ixToL;
            ixToL = ix;
            ix = l.getChildIndex(k);
            if (l.isLeaf()) break;
            gp = p;
            p = l;
            l = l.children[ix];
        }
        
        /**
         * do the update.
         */
        int keyIndex = l.getKeyIndex(k);
        if (l.containsKey(keyIndex)) {
            /**
             * if l already contains key, replace the existing value.
             */
            final V oldValue = (V) l.values[keyIndex];
            if (replace) {
                l.values[keyIndex] = value;
            }
            return oldValue;
        } else {
            /**
             * if l does not contain key, we have to insert it.
             */
            
            // we start by creating a sorted array containing key and all of l's existing keys
            // (and likewise for the values)
            keyIndex = -(keyIndex + 1); // 
            final Object[] keys = new Object[l.keys.length+1];
            final Object[] values = new Object[l.keys.length+1];
            System.arraycopy(l.keys, 0, keys, 0, keyIndex);
            System.arraycopy(l.keys, keyIndex, keys, keyIndex+1, l.keys.length-keyIndex);
            keys[keyIndex] = key;
            System.arraycopy(l.values, 0, values, 0, keyIndex);
            System.arraycopy(l.values, keyIndex, values, keyIndex+1, l.values.length-keyIndex);
            values[keyIndex] = value;

            if (l.keys.length < b) {
                /**
                 * Insert.
                 */
                // the new arrays are small enough to fit in a single node,
                // so we replace l by a new node containing these arrays.
                p.children[ixToL] = new Node<K>(keys, values, null, true);
            } else {
                /**
                 * Overflow.
                 */
                // the new arrays are too big to fit in a single node,
                // so we replace l by a new subtree containing three new nodes:
                // a parent, and two leaves.
                // the new arrays are then split between the two new leaves.
                final int size1 = keys.length/2;
                final Object[] keys1 = new Object[size1];
                final Object[] values1 = new Object[size1];
                System.arraycopy(keys, 0, keys1, 0, size1);
                System.arraycopy(values, 0, values1, 0, size1);
                final int size2 = keys.length - size1;
                final Object[] keys2 = new Object[size2];
                final Object[] values2 = new Object[size2];
                System.arraycopy(keys, size1, keys2, 0, size2);
                System.arraycopy(values, size1, values2, 0, size2);
                final Node<K> newL = new Node<K>(
                        new Object[]{keys2[0]},
                        null,
                        (Node<K>[]) new Node[]{
                            new Node<K>(keys1, values1, null, true),
                            new Node<K>(keys2, values2, null, true)
                        },
                        gp == null);
                // note: weight of new internal node newL will be zero,
                //       unless it is the root. this is because we test
                //       gp == null, above. in doing this, we are actually
                //       performing Root-Zero at the same time as this Overflow
                //       if newL will become the root.
                p.children[ixToL] = newL;
                
                // if the new internal node newL is not the root, then we need
                // to perform some rebalancing (at least one Split or Absorb)
                if (hasWeightViolation(newL)) fixWeightViolation(gp, p, newL, ixToP, ixToL);
            }
            ++size;
            return null;
        }
    }
    
    /**
     * Removes a key from the dictionary (eliminating any value associated with
     * it), and returns the value that was associated with the key just before
     * the key was removed.
     * Precondition: key != null
     * 
     * @param key the key to remove from the dictionary
     * @return the value associated with the key just before key was removed
     */
    public synchronized V remove(final K key) {
        
        /**
         * search.
         */
        final Comparable<? super K> k = comparable(key);
        Node<K> gp = null;
        Node<K> p = root;
        Node<K> l = p.children[0];
        int ixToP = -1;
        int ixToL = -1;
        int ix = 0;
        while (true) {
            ixToP = ixToL;
            ixToL = ix;
            ix = l.getChildIndex(k);
            if (l.isLeaf()) break;
            gp = p;
            p = l;
            l = l.children[ix];
        }
        
        /**
         * do the update.
         */
        final int keyIndex = l.getKeyIndex(k);
        if (!l.containsKey(keyIndex)) {
            /**
             * if l does not contain key, we are done.
             */
            return null;
        } else {
            /**
             * if l contains key, replace l by a new copy that does not contain key.
             */
            final V oldValue = (V) l.values[keyIndex];
            final Object[] keys = new Object[l.keys.length-1];
            final Object[] values = new Object[l.keys.length-1];
            System.arraycopy(l.keys, 0, keys, 0, keyIndex);
            System.arraycopy(l.keys, keyIndex+1, keys, keyIndex, keys.length-keyIndex);
            System.arraycopy(l.values, 0, values, 0, keyIndex);
            System.arraycopy(l.values, keyIndex+1, values, keyIndex, values.length-keyIndex);
            p.children[ixToL] = new Node<K>(keys, values, null, true);
            /**
             * Compress may be needed at p after removing key.
             */
            if (hasDegreeOrSlackViolation(p)) fixDegreeOrSlackViolation(gp, p, ixToP);
            --size;
            return oldValue;
        }
    }
    
    private Comparable<? super K> comparable(final Object key) {
        if (key == null) {
            throw new NullPointerException();
        }
        if (comparator == null) {
            return (Comparable<? super K>)key;
        }
        return new Comparable<K>() {
            final Comparator<? super K> _cmp = comparator;

            @SuppressWarnings("unchecked")
            public int compareTo(final K rhs) { return _cmp.compare((K)key, rhs); }
        };
    }
    
    // retrieves the current parent of a node in the tree.
    // this procedure could be replaced by parent pointers stored in nodes.
    // precondition: node just be in the tree.
    private Node<K> getParent(final Node<K> node) {
        if (node == root) return null;
        final Comparable<? super K> k = comparable(node.keys[0]);
        Node<K> p = root;
        Node<K> l = p.children[0];
        while (true) {
            if (l == node) break;
            if (l.isLeaf()) return null;
            p = l;
            l = l.children[l.getChildIndex(k)];
        }
        return p;
    }
    
    private int getNumberOfKeysInChildren(final Node<K> p) {
        int result = 0;
        for (int i=0;i<p.children.length;++i) {
            result += p.children[i].keys.length;
        }
        return result;
    }
    
    private int getNumberOfGrandchildren(final Node<K> p) {
        int result = 0;
        for (int i=0;i<p.children.length;++i) {
            result += p.children[i].children.length;
        }
        return result;
    }
    
    /**
     * Perform Compress or One-Child at p (and fix any violations we create).
     * 
     * Compress and One-Child can necessitate other Compress and One-Child
     * updates. In this function, if we perform a Compress or One-Child
     * and it necessitates another Compress or One-Child, we make a
     * recursive call to fixDegreeOrSlackViolation. However, a complication
     * arises if the recursive call replaces some of the nodes we were
     * working with. In this case, we assume that the recursive call
     * will take care of any necessary Compress or One-Child updates
     * at any nodes that it replaces. Thus, if we see that any of
     * the nodes we are working with have been replaced by a recursive
     * call, we can simply continue as if the problems we were trying
     * to fix at those nodes are already resolved.
     * 
     * Precondition: gp is in the tree, gp.children[ixToP] == p and
     *      a Compress or One-Child should be performed at p.
     */
    private void fixDegreeOrSlackViolation(final Node<K> gp, final Node<K> p, final int ixToP) {
        
        if (gp == null) return; // this line may be unnecessary
        // assert: gp is non-null
        // assert: p is internal
        
        if (p.children.length < 2) { // degree violation
            /**
             * If p has fewer than 2 children,
             * then we cannot do a Compress or One-Child here
             * until we first do Compress or One-Child at gp.
             */
            final Node<K> ggp = getParent(gp);
            // since this is not a concurrent implementation, ggp and gp are still in the tree.
            fixDegreeOrSlackViolation(ggp, gp, ggp.getChildIndex(gp));
            
            // if the recursive call replaced p, then we hand off responsibility
            // for the violation we were trying to fix to the recursive call.
            // otherwise, p is still in the tree, and we still need to fix
            // the violation we found earlier. we make a recursive call
            // to fix the violation. (another way to do this that avoids making
            // a recursive call is to wrap this function in a "retry loop."
            if (!p.replacedByCompressOrOneChild) {
                if (gp.replacedByCompressOrOneChild) {
                    // if gp was replaced, we must search for the new parent of p
                    final Node<K> newgp = getParent(p);
                    fixDegreeOrSlackViolation(newgp, p, newgp.getChildIndex(p));
                } else {
                    // otherwise, gp is still in the tree and gp[ixToP] = p
                    fixDegreeOrSlackViolation(gp, p, ixToP);
                }
            }
            
        } else { // slack violation
            /**
             * NOTE: the following code performs Compress if the children of p
             *   contain at most |children(p)| * b - b keys, and it will
             *   perform One-Child otherwise.
             * To see why, let c = total degree of p's children,
             *   and k = # of p's children.
             * The only difference between Compress and One-Child is that
             *   One-Child does not change the number of children p has.
             * The line "numberOfNodes = ((numberOfKeys + (b-1)) / b)",
             *   which determines how many children p will have after the
             *   update below takes effect, evaluates to:
             *     ceiling(c/b)    when Compress should occur
             *                     [i.e., when c is less than or equal to kb-b], and
             *     k               when One-Child should occur
             *                     [i.e., when c is greater than kb-b].
             * So, whenever One-Child is supposed to occur, the number of
             *   children of p will not change (which means the update performed
             *   is One-Child).
             */
            
            // since leaves and internal nodes use different fields of the node,
            // we have to have two separate code paths to do CompressOrOneChild
            // for the cases when
            //   1. all children of p are leaves, and
            //   2. all children of p are internal.
            
            int numberOfNodes;
            Node<K>[] childrenNewP;
            K[] keysNewP;

            if (p.children[0].isLeaf()) { // assert: all children of p are leaves
                /**
                 * if p's children are leaves, we replace these leaves
                 * with new copies that evenly share the keys/values originally
                 * contained in the children of p.
                 */

                // this is wasted computation (done before the call to compress),
                // but at least the data should all be cached...
                int numberOfKeys = getNumberOfKeysInChildren(p);

                // combine keys and values of all children into big arrays
                final K[] keys = (K[]) new Comparable[numberOfKeys];
                final V[] values = (V[]) new Object[numberOfKeys];
                numberOfKeys = 0;
                for (int i=0;i<p.children.length;++i) {
                    System.arraycopy(p.children[i].keys, 0, keys, numberOfKeys, p.children[i].keys.length);
                    System.arraycopy(p.children[i].values, 0, values, numberOfKeys, p.children[i].values.length);
                    numberOfKeys += p.children[i].keys.length;
                    p.children[i].replacedByCompressOrOneChild = true;
                }
                p.replacedByCompressOrOneChild = true;

                // determine how to divide keys&values into leaves as evenly as possible.
                // specifically, we divide them into nodesWithCeil + nodesWithFloor leaves,
                // containing keysPerNodeCeil and keysPerNodeFloor keys, respectively.
                numberOfNodes = ((numberOfKeys + (b-1)) / b); // how many leaves?
                int keysPerNodeCeil = (numberOfKeys + (numberOfNodes-1)) / numberOfNodes;
                int keysPerNodeFloor = numberOfKeys / numberOfNodes;
                int nodesWithCeil = numberOfKeys % numberOfNodes;
                int nodesWithFloor = numberOfNodes - nodesWithCeil;

                // divide keys&values into leaves of degree keysPerNodeCeil
                childrenNewP = (Node<K>[]) new Node[numberOfNodes];
                for (int i=0;i<nodesWithCeil;++i) {
                    final K[] keysNode = (K[]) new Comparable[keysPerNodeCeil];
                    final V[] valuesNode = (V[]) new Object[keysPerNodeCeil];
                    System.arraycopy(keys, keysPerNodeCeil*i, keysNode, 0, keysPerNodeCeil);
                    System.arraycopy(values, keysPerNodeCeil*i, valuesNode, 0, keysPerNodeCeil);
                    childrenNewP[i] = new Node<K>(keysNode, valuesNode, null, true);
                }

                // divide remaining keys&values into leaves of degree keysPerNodeFloor
                for (int i=0;i<nodesWithFloor;++i) {
                    final K[] keysNode = (K[]) new Comparable[keysPerNodeFloor];
                    final V[] valuesNode = (V[]) new Object[keysPerNodeFloor];
                    System.arraycopy(keys, keysPerNodeCeil*nodesWithCeil+keysPerNodeFloor*i, keysNode, 0, keysPerNodeFloor);
                    System.arraycopy(values, keysPerNodeCeil*nodesWithCeil+keysPerNodeFloor*i, valuesNode, 0, keysPerNodeFloor);
                    childrenNewP[i+nodesWithCeil] = new Node<K>(keysNode, valuesNode, null, true);
                }

                // build keys array for new parent
                keysNewP = (K[]) new Comparable[numberOfNodes-1];
                for (int i=1;i<numberOfNodes;++i) {
                    keysNewP[i-1] = (K) childrenNewP[i].keys[0];
                }

            } else { // assert all children of p are internal
                /**
                 * if p's children are internal nodes, we replace these nodes
                 * with new copies that evenly share the keys/pointers originally
                 * contained in the children of p.
                 */

                int numberOfChildren = getNumberOfGrandchildren(p);

                // combine keys and children of all children of p into big arrays
                final K[] keys = (K[]) new Comparable[numberOfChildren-1];
                final Node<K>[] children = (Node<K>[]) new Node[numberOfChildren];
                numberOfChildren = 0;
                for (int i=0;i<p.children.length;++i) {
                    System.arraycopy(p.children[i].keys, 0, keys, numberOfChildren, p.children[i].keys.length);
                    System.arraycopy(p.children[i].children, 0, children, numberOfChildren, p.children[i].children.length);
                    numberOfChildren += p.children[i].children.length;
                    // since we have one less key than children, we fill the hole
                    // with the key of p to the right of this child pointer.
                    // (we can't do this for the last child of p, but we don't
                    //  need to, since that last hole doesn't need to be filled.)
                    if (i < p.keys.length) keys[numberOfChildren-1] = (K) p.keys[i];
                    p.children[i].replacedByCompressOrOneChild = true;
                }
                p.replacedByCompressOrOneChild = true;

                // determine how to divide keys&pointers into leaves as evenly as possible.
                // specifically, we divide them into nodesWithCeil + nodesWithFloor leaves,
                // containing childrenPerNodeCeil and childrenPerNodeFloor pointers, respectively.
                numberOfNodes = ((numberOfChildren + (b-1)) / b);
                int childrenPerNodeCeil = (numberOfChildren + (numberOfNodes-1)) / numberOfNodes;
                int childrenPerNodeFloor = numberOfChildren / numberOfNodes;
                int nodesWithCeil = numberOfChildren % numberOfNodes;
                int nodesWithFloor = numberOfNodes - nodesWithCeil;

                // divide keys&pointers into internal nodes of degree childrenPerNodeCeil
                childrenNewP = (Node<K>[]) new Node[numberOfNodes];
                for (int i=0;i<nodesWithCeil;++i) {
                    final K[] keysNode = (K[]) new Comparable[childrenPerNodeCeil-1];
                    final Node<K>[] childrenNode = (Node<K>[]) new Node[childrenPerNodeCeil];
                    System.arraycopy(keys, childrenPerNodeCeil*i, keysNode, 0, childrenPerNodeCeil-1);
                    System.arraycopy(children, childrenPerNodeCeil*i, childrenNode, 0, childrenPerNodeCeil);
                    childrenNewP[i] = new Node<K>(keysNode, null, childrenNode, true);
                }

                // divide remaining keys&pointers into internal nodes of degree childrenPerNodeFloor
                for (int i=0;i<nodesWithFloor;++i) {
                    final K[] keysNode = (K[]) new Comparable[childrenPerNodeFloor-1];
                    final Node<K>[] childrenNode = (Node<K>[]) new Node[childrenPerNodeFloor];
                    System.arraycopy(keys, childrenPerNodeCeil*nodesWithCeil+childrenPerNodeFloor*i, keysNode, 0, childrenPerNodeFloor-1);
                    System.arraycopy(children, childrenPerNodeCeil*nodesWithCeil+childrenPerNodeFloor*i, childrenNode, 0, childrenPerNodeFloor);
                    childrenNewP[i+nodesWithCeil] = new Node<K>(keysNode, null, childrenNode, true);
                }

                // build keys array for new parent
                keysNewP = (K[]) new Comparable[numberOfNodes-1];
                for (int i=0;i<nodesWithCeil;++i) {
                    keysNewP[i] = keys[childrenPerNodeCeil*i + childrenPerNodeCeil-1];
                }
                for (int i=0;i<nodesWithFloor-1;++i) { // this is nodesWithFloor - 1 because we want to go up to numberOfNodes - 1, not numberOfNodes.
                    keysNewP[i+nodesWithCeil] = keys[childrenPerNodeCeil*nodesWithCeil + childrenPerNodeFloor*i + childrenPerNodeFloor-1];
                }
            }

            // now, we atomically replace p and its children with the new nodes.
            // if appropriate, we perform Root-Replace at the same time.
            if (gp == root && childrenNewP.length == 1) {
                /**
                 * Compress/One-Child AND Root-Replace.
                 */
                gp.children[ixToP] = childrenNewP[0];

            } else {
                /**
                 * Compress/One-Child.
                 */
                final Node<K> newP = new Node<K>(keysNewP, null, childrenNewP, true);
                gp.children[ixToP] = newP;

                /**
                 * Compress may be needed at the grandparent gp.
                 */
                if (hasDegreeOrSlackViolation(gp)) {
                    final Node<K> ggp = getParent(gp);
                    // since this is not a concurrent implementation, ggp and gp are still in the tree.
                    fixDegreeOrSlackViolation(ggp, gp, ggp.getChildIndex(gp));
                }

                /**
                 * Compress may be needed at some children of the new internal node newP.
                 */
                if (!newP.children[0].isLeaf()) {
                    // assert: all children of newP are internal
                    for (int i=0;i<numberOfNodes;++i) {
                        if (hasDegreeOrSlackViolation(childrenNewP[i])) {
                            // childrenNewP[i] is not in the tree only if a
                            // compress replaced it after we added it to the tree above.
                            // however:
                            //   1. isCompressNeeded returns false if a compress
                            //      replaced childrenNewP[i] (and that other compress
                            //      promises to perform any necessary compress at the
                            //      replacement node), and
                            //   2. currentP is in the tree if childrenNewP[i] is, so
                            //      currentP and childrenNewP[i] are both in the tree.
                            final Node<K> currentP = getParent(childrenNewP[i]);
                            fixDegreeOrSlackViolation(currentP, childrenNewP[i], currentP.getChildIndex(childrenNewP[i]));
                        }
                    }
                }
            }
        }
    }
        
    private boolean hasDegreeOrSlackViolation(final Node<K> p) {
        if (p.isLeaf()) return false;
        
        // if a Compress/One-Child C (at parent(p)) replaced p,
        // then C is responsible for any violation that was at p before C.
        if (p.replacedByCompressOrOneChild) return false;
        
        // check if any child has exactly one child pointer
        for (int i=0;i<p.children.length;++i) {
            if (!p.children[i].isLeaf() && p.children[i].children.length == 1) return true;
        }
        
        // check if there is too much total slack amongst the children of p
        return ((p.children[0].isLeaf())
                ? getNumberOfKeysInChildren(p)
                : getNumberOfGrandchildren(p)) <= b*p.children.length - b;
    }
    
    /**
     * Perform Absorb or Split at l (and fix any other violations we create).
     * Precondition: gp is in the tree, gp.children[ixToP] == p,
     *      p.children[ixToL] == l and a Split should be performed.
     */
    private void fixWeightViolation(final Node<K> gp, final Node<K> p, final Node<K> l, final int ixToP, final int ixToL) {
        
        // merge keys of p and l into one big array (and similarly for children)
        // (we essentially replace the pointer to l with the contents of l)
        final int c = p.children.length + l.children.length;
        final int size = c-1;
        final K[] keys = (K[]) new Comparable[size-1];
        final Node<K>[] children = (Node<K>[]) new Node[size];
        System.arraycopy(p.children, 0, children, 0, ixToL);
        System.arraycopy(l.children, 0, children, ixToL, l.children.length);
        System.arraycopy(p.children, ixToL+1, children, ixToL+l.children.length, p.children.length-(ixToL+1));
        System.arraycopy(p.keys, 0, keys, 0, ixToL);
        System.arraycopy(l.keys, 0, keys, ixToL, l.keys.length);
        System.arraycopy(p.keys, ixToL, keys, ixToL+l.keys.length, p.keys.length-ixToL);
        
        if (size <= b) {
            /**
             * Absorb.
             */
            // the new arrays are small enough to fit in a single node,
            // so we replace p by a new internal node.
            final Node<K> newP = new Node<K>(keys, null, children, true);
            gp.children[ixToP] = newP;

            /**
             * Compress may be needed at the new internal node we created
             * (since we move grandchildren from two parents together).
             */
            if (hasDegreeOrSlackViolation(newP)) {
                // since this is not a concurrent implementation, gp and newP are in the tree.
                fixDegreeOrSlackViolation(gp, newP, gp.getChildIndex(newP));
            }
        } else {
            /**
             * Split.
             */
            // the new arrays are too big to fit in a single node,
            // so we replace p by a new internal node and two new children.
            
            // we take the big merged array and split it into two arrays,
            // which are used to create two new children u and v.
            // we then create a new internal node (whose weight will be zero
            // if it is not the root), with u and v as its children.
            final int size1 = size / 2;
            final int size2 = size - size1;
            final K[] keys1 = (K[]) new Comparable[size1-1];
            final K[] keys2 = (K[]) new Comparable[size2-1];
            final Node<K>[] children1 = (Node<K>[]) new Node[size1];
            final Node<K>[] children2 = (Node<K>[]) new Node[size2];
            System.arraycopy(keys, 0, keys1, 0, size1-1);
            System.arraycopy(keys, size1, keys2, 0, size2-1);
            System.arraycopy(children, 0, children1, 0, size1);
            System.arraycopy(children, size1, children2, 0, size2);
            final Node<K> left = new Node<K>(keys1, null, children1, true);
            final Node<K> right = new Node<K>(keys2, null, children2, true);
            final Node<K> newP = new Node<K>(
                    new Comparable[]{keys[size1-1]},
                    null,
                    (Node<K>[]) new Node[]{left, right},
                    gp == root);
            gp.children[ixToP] = newP;
            
            /**
             * Split may be needed at the new parent we created.
             */
            if (hasWeightViolation(newP)) {
                final Node<K> ggp = getParent(gp);
                // since this is not a concurrent implementation,
                // we know ggp, gp, newP are still in the tree.
                fixWeightViolation(ggp, gp, newP, ggp.getChildIndex(gp), ixToP);
            }
            /**
             * Compress may be needed at the new children we created.
             */
            if (hasDegreeOrSlackViolation(left)) {
                final Node<K> leftP = getParent(left);
                
                // left is not in the tree only if a compress replaced left
                // (since the recursive split calls cannot replace left).
                // however, isCompressNeeded returns false if a compress replaced left,
                // and leftP is in the tree if left is, so left and leftP are in the tree.
                fixDegreeOrSlackViolation(leftP, left, leftP.getChildIndex(left));
            }
            if (hasDegreeOrSlackViolation(right)) {
                final Node<K> rightP = getParent(right);
                // same comment as above, but with "right" instead of "left."
                fixDegreeOrSlackViolation(rightP, right, rightP.getChildIndex(right));
            }
        }
    }
    
    private boolean hasWeightViolation(final Node<K> p) {
        return !p.weight;
    }
    
    private static class Node<K> {
        public final Object[] keys;
        public final Object[] values;
        public final Node<K>[] children;
        public final boolean weight;
        public boolean replacedByCompressOrOneChild;
        
        public Node(final Object[] keys, final Object[] values, final Node<K>[] children, final boolean weight) {
            this.keys = keys;
            this.values = values;
            this.children = children;
            this.weight = weight;
        }
        
        public boolean isLeaf() {
            return children == null;
        }
        
        public boolean containsKey(final Comparable<? super K> key) {
            return containsKey(getKeyIndex(key));
        }
        public boolean containsKey(final int keyIndex) {
            return (keyIndex >= 0);
        }
        
        /**
         * if this returns a negative value, add one and then negate it to
         * learn where key should appear in the array.
         */
        public int getKeyIndex(final Comparable<? super K> key) {
            if (keys == null || keys.length == 0) return -1;
            return Arrays.binarySearch(keys, key, null);
        }
        
        public int getChildIndex(final Node<K> child) {
            if (child == null) return 0;
            if (child.keys == null) return 0;
            return getChildIndex((Comparable) child.keys[0]);
        }
        public int getChildIndex(final Comparable<? super K> key) {
            return getChildIndex(getKeyIndex(key), key);
        }
        public int getChildIndex(int keyIndex, final Comparable<? super K> key) {
            if (keyIndex < 0) {         // key not in node
                return -(keyIndex + 1); // return position of first key greater than key (i.e., the position key would be at)
            } else {                    // key in node
                return keyIndex + 1;    // return 1+position key is at
            }
        }
        
        public String getKeysString() {
            StringBuilder sb = new StringBuilder();
            for (int i=0;i<keys.length;++i) {
                sb.append(keys[i]);
                if (i+1 < keys.length) sb.append(",");
            }
            return sb.toString();
        }
        
        public String toString() {
            StringBuilder sb = new StringBuilder();
            sb.append("[@");
            sb.append(Integer.toHexString(hashCode()));
            sb.append(" keys={");
            sb.append(getKeysString());
            sb.append("}");
            sb.append("]");
            return sb.toString();
        }
    }
    
    /**
     * Constant time size method. This just reads and returns a single variable.
     * @return number of keys in the dictionary
     */
    public int size() {
        return size;
    }
}