/**
 *  An implementation of a non-blocking k-ary search tree with k=7.
 *  Copyright (C) 2011  Trevor Brown, Joanna Helga
 *  Contact Trevor Brown (tabrown@cs.toronto.edu) with any questions or comments.
 *
 *  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/>.
 */

import java.util.*;
import java.util.concurrent.atomic.*;

public class LockFree7ST<E extends Comparable<? super E>, V> {

    /**
     *
     * GLOBALS
     *
     */

    private static final AtomicReferenceFieldUpdater<Node, Node> c0Updater =
        AtomicReferenceFieldUpdater.newUpdater(Node.class, Node.class, "c0");
    private static final AtomicReferenceFieldUpdater<Node, Node> c1Updater =
        AtomicReferenceFieldUpdater.newUpdater(Node.class, Node.class, "c1");
    private static final AtomicReferenceFieldUpdater<Node, Node> c2Updater =
        AtomicReferenceFieldUpdater.newUpdater(Node.class, Node.class, "c2");
    private static final AtomicReferenceFieldUpdater<Node, Node> c3Updater =
        AtomicReferenceFieldUpdater.newUpdater(Node.class, Node.class, "c3");
    private static final AtomicReferenceFieldUpdater<Node, Node> c4Updater =
        AtomicReferenceFieldUpdater.newUpdater(Node.class, Node.class, "c4");
    private static final AtomicReferenceFieldUpdater<Node, Node> c5Updater =
        AtomicReferenceFieldUpdater.newUpdater(Node.class, Node.class, "c5");
    private static final AtomicReferenceFieldUpdater<Node, Node> c6Updater =
        AtomicReferenceFieldUpdater.newUpdater(Node.class, Node.class, "c6");

    private static final AtomicReferenceFieldUpdater<Node, Info> infoUpdater =
        AtomicReferenceFieldUpdater.newUpdater(Node.class, Info.class, "info");
    private final Node<E,V> root;



    /**
     *
     * CONSTRUCTORS
     *
     */

    public LockFree7ST() {
        this.root = new Node<E,V>(true);
    }

    private LockFree7ST(Node root) {
        this.root = root;
    }



    /**
     *
     * PUBLIC FUNCTIONS
     *
     */

    /**
     * Determines whether a key is present in the tree.
     * @return true if the key is present in the tree, and false otherwise
     * @throws NullPointerException in the event that key is null
     */
    public final boolean containsKey(final E key) {
        if (key == null) throw new NullPointerException();
        Node<E,V> l = root.c0;
        while (l.c0 != null) l = child(key, l);  /* while l is internal */
        return l.hasKey(key);
    }

    /**
     * Retrieves the value associated with key from the tree.
     * @return the value mapped to the key, or null in the event that
     *         (1) the key is not present in the tree, or
     *         (2) the value null is stored with the key
     * @throws NullPointerException in the event that key is null
     */
    public final V get(final E key) {
        if (key == null) throw new NullPointerException();
        Node<E,V> l = root.c0;
        while (l.c0 != null) l = child(key, l);  /* while l is internal */
        return l.getValue(key);
    }

    /**
     * Adds a key-value pair to the tree if the key does not already exist.
     * @return the previous value mapped to the key, or null in the event that
     *         (1) the key was not previously in the tree and the new
     *             value was successfully assigned, or
     *         (2) the key existed in the tree,
     *             and the value stored with it was null.
     * @throws NullPointerException in the event that key is null
     */
    public final V putIfAbsent(final E key, final V value) {
        if (key == null) throw new NullPointerException();
        Node<E,V> p, l, newchild;
        Info<E,V> pinfo;

        while (true) {
            // search
            p = root;
            pinfo = p.info;
            l = p.c0;
            while (l.c0 != null) {
                p = l;
                l = child(key, l);
            }
            pinfo = p.info;                     // read pinfo once instead of every iteration
            if (l != child(key, p)) continue;   // then confirm the child link to l is valid
                                                // (just as if we'd read p's info field before the reference to l)

            if (l.hasKey(key)) return l.getValue(key);
            else if (pinfo != null && pinfo.getClass() != Clean.class) help(pinfo);
            else {
                // SPROUTING INSERTION
                if (l.kcount == 6) { // l is full of keys
                    // create internal node with 7 children sorted by key
                    newchild = new Node<E,V>(key, value, l);

                // SIMPLE INSERTION
                } else {
                    // create leaf node with sorted keys
                    // (at least one key of l is null and, by structural invariant,
                    // nulls appear at the end, so the last key is null)
                    newchild = new Node<E,V>(key, value, l, false);
                }

                // flag and perform the insertion
                final IInfo<E,V> newPInfo = new IInfo<E,V>(l, p, newchild);
                if (infoUpdater.compareAndSet(p, pinfo, newPInfo)) {	    // [[ iflag CAS ]]
                    helpInsert(newPInfo);
                    return null;
                } else {
                    // help current operation first
                    help(p.info);
                }
            }
        }
    }

    /**
     * Adds a key-value pair to the tree, overwriting any pre-existing mapping.
     * @return the value that was previously mapped to the key, or null if the
     *         key was not in the tree (or if the value stored with it was null)
     * @throws NullPointerException in the event that key is null
     */
    public final V put(final E key, final V value) {
        if (key == null) throw new NullPointerException();
        Node<E, V> p, l, newchild;
        Info<E, V> pinfo;

        while (true) {
            // search
            p = root;
            pinfo = p.info;
            l = p.c0;
            while (l.c0 != null) {
                p = l;
                l = child(key, l);
            }
            pinfo = p.info;                     // read pinfo once instead of every iteration
            if (l != child(key, p)) continue;   // then confirm the child link to l is valid
                                                // (just as if we'd read p's info field before the reference to l)

            if (pinfo != null && pinfo.getClass() != Clean.class) {
                help(pinfo);
            } else if (l.hasKey(key)) {

                // REPLACE INSERTION
                newchild = new Node<E, V>(key, value, l, true); // true means key is already in node l

                // flag and perform the insertion
                final IInfo<E, V> newPInfo = new IInfo<E, V>(l, p, newchild);
                if (infoUpdater.compareAndSet(p, pinfo, newPInfo)) {	    // [[ iflag CAS ]]
                    helpInsert(newPInfo);
                    return l.getValue(key);
                } else {
                    // help current operation first
                    help(p.info);
                }
            } else {
                // SPROUTING INSERTION
                if (l.kcount == 6) { // l is full of keys
                    // create internal node with 7 children sorted by key
                    newchild = new Node<E, V>(key, value, l);

                // SIMPLE INSERTION
                } else {
                    // create leaf node with sorted keys
                    // (at least one key of l is null and, by structural invariant,
                    // nulls appear at the end, so the last key is null)
                    newchild = new Node<E, V>(key, value, l, false); // false means key is not in l
                }

                // flag and perform the insertion
                final IInfo<E, V> newPInfo = new IInfo<E, V>(l, p, newchild);
                if (infoUpdater.compareAndSet(p, pinfo, newPInfo)) {	    // [[ iflag CAS ]]
                    helpInsert(newPInfo);
                    return null;
                } else {
                    // help current operation first
                    help(p.info);
                }
            }
        }
    }

    /**
     * Remove a key from the tree.
     * @return the value that was removed from the tree, or null if the key was
     *         not in the tree (or if the value stored with it was null)
     * @throws NullPointerException in the event that key is null
     */
    public final V remove(final E key) {
        if (key == null) throw new NullPointerException();
        Node<E,V> gp, p, l, newchild;
        Info<E,V> gpinfo, pinfo;

        while (true) {
            // search
            gp = null;
            gpinfo = null;
            p = root;
            pinfo = p.info;
            l = p.c0;
            while (l.c0 != null) {
                gp = p;
                p = l;
                l = child(key, l);
            }
            gpinfo = gp.info;                   // - read gpinfo once instead of every iteration
            if (p != child(key, gp)) continue;  //   then confirm the child link to p is valid
            pinfo = p.info;                     //   (just as if we'd read gp's info field before the reference to p)
            if (l != child(key, p)) continue;   // - do the same for pinfo and l

            // if the key is not in the tree, return null
            if (!l.hasKey(key))
                return null;
            else if (gpinfo != null && gpinfo.getClass() != Clean.class)
                help(gpinfo);
            else if (pinfo != null && pinfo.getClass() != Clean.class)
                help(pinfo);
            else {
                // count number of non-empty children of p
                final int ccount = (p.c0.kcount > 0 ? 1 : 0) +
                                   (p.c1.kcount > 0 ? 1 : 0) +
                                   (p.c2.kcount > 0 ? 1 : 0) +
                                   (p.c3.kcount > 0 ? 1 : 0) +
                                   (p.c4.kcount > 0 ? 1 : 0) +
                                   (p.c5.kcount > 0 ? 1 : 0) +
                                   (p.c6.kcount > 0 ? 1 : 0);


                // two types of deletion: PRUNING and SIMPLE
                // simple deletion  --is removing a key within a leaf
                //                  --is performed when child-count > 2 or key-count > 1
                //                  --is like insertion in that it does not need a mark
                // pruning deletion --is pruning a leaf and its parent out of the tree
                //                  --is performed when key-count is 1 and child-count is 2
                //                  --needs a mark
                // simple deletion uses an "insert to replace" method of deletion.
                // pruning deletion uses a "bypass to replace" method of deletion.

		// SIMPLE DELETION
                if (ccount > 2 || l.kcount > 1) { // equivalent to (ccount>2 or (ccount==2 and l.kcount==1))
                    // observe: l.keycount never changes (we create objects to change it)
                    //          thus l.keycount is forever > 1

                    // create leaf with sorted keys
                    newchild = new Node<E,V>(key, l, l.kcount - 1);

                    // flag and perform the key deletion (like insertion)
                    final IInfo<E,V> newPInfo = new IInfo<E,V>(l, p, newchild);
                    if (infoUpdater.compareAndSet(p, pinfo, newPInfo)) {	// [[ kdflag CAS ]]
                        helpInsert(newPInfo);
                        return l.getValue(key);
                    } else {
                        help(p.info);
                    }

                // PRUNING DELETION
                } else {

                    // observe: if the number of nonempty children is different from
                    // ccount, then the child pointers of p will have changed, and p.info
                    // will have changed, so that the clean value is different from what
                    // was read in the search above and saved to use as the `expected'
                    // value for the upcoming CAS.  (so the cas will fail if it changes)
                    // (further, from data structure invariants, nodes always satisfy:
                    //  (0 nonempty children) or (2 <= number of nonempty children <= 4))

                    final DInfo<E,V> newGPInfo = new DInfo<E,V>(l, p, gp, pinfo);
                    if (infoUpdater.compareAndSet(gp, gpinfo, newGPInfo)) { // [[ dflag CAS ]]
                        if (helpDelete(newGPInfo)) return l.getValue(key);
                    } else {
                        help(gp.info);
                    }
                }
            }
        }
    }

    /**
     * Determines the size of the tree
     * @return the size of the tree, or -1 if the tree was concurrently modified
     */
    public final int size() {
        Node newroot = getSnapshot();
        if (newroot == null) return -1;
        return sequentialSize(newroot);
    }

    /**
     * Determines the size of the tree (retries until the tree can be read in
     * its entirety without concurrent modification)
     * @return the size of the tree
     */
    public final int sizeBlocking() {
        int sz = 0;
        for (;;) if ((sz = size()) != -1) return sz;
    }

    /**
     * This assumes that there are no concurrent accesses occurring.
     * If concurrent accesses can occur, use size() or sizeBlocking().
     */
    public int sequentialSize() {
        return sequentialSize(root);
    }

    /**
     * Clones the tree (retries until the tree can be read in its
     * entirety without concurrent modification)
     * @return a reference to a clone of the tree
     */
    @Override
    public final LockFree7ST clone() {
        Node newroot = null;
        for (;;) if ((newroot = getSnapshot()) != null) return new LockFree7ST(newroot);
    }

    @Override
    public final String toString() {
        StringBuffer sb = new StringBuffer();
        treeString(root, sb);
        return sb.toString();
    }



    /**
     *
     * PRIVATE FUNCTIONS
     *
     */

    // Precondition: `nonnull' is non-null
    private static <E extends Comparable<? super E>, V> boolean less(final E nonnull, final E other) {
        if (other == null) return true;
        return nonnull.compareTo(other) < 0;
    }

    // Precondition: `nonnull' is non-null
    private static <E extends Comparable<? super E>, V> boolean equal(final E nonnull, final E other) {
        if (other == null) return false;
        return nonnull.compareTo(other) == 0;
    }

    private Node<E,V> child(final E key, final Node<E,V> l) {
        if (less(key, l.k0)) return l.c0;
        if (less(key, l.k1)) return l.c1;
        if (less(key, l.k2)) return l.c2;
        if (less(key, l.k3)) return l.c3;
        if (less(key, l.k4)) return l.c4;
        if (less(key, l.k5)) return l.c5;
        return l.c6;

    }

    private void help(final Info<E,V> info) {
        if (info.getClass() == IInfo.class)      helpInsert((IInfo<E,V>) info);
        else if (info.getClass() == DInfo.class) helpDelete((DInfo<E,V>) info);
        else if (info.getClass() == Mark.class)  helpMarked(((Mark<E,V>) info).dinfo);
    }

    private void helpInsert(final IInfo<E,V> info) {
        // CAS the correct child pointer of p from oldchild to newchild
        ((info.p.c0 == info.oldchild) ? c0Updater :
        (info.p.c1 == info.oldchild) ? c1Updater :
        (info.p.c2 == info.oldchild) ? c2Updater :
        (info.p.c3 == info.oldchild) ? c3Updater :
        (info.p.c4 == info.oldchild) ? c4Updater :
        (info.p.c5 == info.oldchild) ? c5Updater :
        c6Updater).compareAndSet(info.p, info.oldchild, info.newchild);    // [[ ichild CAS ]]
        infoUpdater.compareAndSet(info.p, info, new Clean<E,V>());            // [[ iunflag CAS ]]
    }

    private boolean helpDelete(final DInfo<E,V> info) {
        final boolean markSuccess = infoUpdater.compareAndSet(
                info.p, info.pinfo, new Mark<E,V>(info));                     // [[ mark CAS ]]
        final Info<E,V> currentPInfo = info.p.info;
        if (markSuccess || (currentPInfo.getClass() == Mark.class
                && ((Mark<E,V>) currentPInfo).dinfo == info)) {
            helpMarked(info);
            return true;
        } else {
            help(currentPInfo);
            infoUpdater.compareAndSet(info.gp, info, new Clean<E,V>());       // [[ backtrack CAS ]]
            return false;
        }
    }

    private void helpMarked(final DInfo<E,V> info) {
        // observe that there are two non-empty children of info.p
        // so the following test correctly finds the "other" (remaining) node
        final Node<E,V> other = (info.p.c0.kcount > 0 && info.p.c0 != info.l) ? info.p.c0 :
                                (info.p.c1.kcount > 0 && info.p.c1 != info.l) ? info.p.c1 :
                                (info.p.c2.kcount > 0 && info.p.c2 != info.l) ? info.p.c2 :
                                (info.p.c3.kcount > 0 && info.p.c3 != info.l) ? info.p.c3 :
                                (info.p.c4.kcount > 0 && info.p.c4 != info.l) ? info.p.c4 :
                                (info.p.c5.kcount > 0 && info.p.c5 != info.l) ? info.p.c5 :
                                info.p.c6;


        // CAS the correct child pointer of info.gp from info.p to other
        ((info.gp.c0 == info.p) ? c0Updater :
        (info.gp.c1 == info.p) ? c1Updater :
        (info.gp.c2 == info.p) ? c2Updater :
        (info.gp.c3 == info.p) ? c3Updater :
        (info.gp.c4 == info.p) ? c4Updater :
        (info.gp.c5 == info.p) ? c5Updater :
        c6Updater).compareAndSet(info.gp, info.p, other);                  // [[ dchild CAS ]]
        infoUpdater.compareAndSet(info.gp, info, new Clean<E,V>());           // [[ dunflag CAS ]]
    }

    public static void treeString(Node root, StringBuffer sb) {
        if (root == null) {
            sb.append("*");
            return;
        }
        sb.append("(");
        sb.append(root.kcount);
        sb.append(" keys,");
        sb.append((root.k0 == null ? "-" : root.k0.toString()));sb.append(",");
        sb.append((root.k1 == null ? "-" : root.k1.toString()));sb.append(",");
        sb.append((root.k2 == null ? "-" : root.k2.toString()));sb.append(",");
        sb.append((root.k3 == null ? "-" : root.k3.toString()));sb.append(",");
        sb.append((root.k4 == null ? "-" : root.k4.toString()));sb.append(",");
        sb.append((root.k5 == null ? "-" : root.k5.toString()));sb.append(",");

        treeString(root.c0, sb); sb.append(",");
        treeString(root.c1, sb); sb.append(",");
        treeString(root.c2, sb); sb.append(",");
        treeString(root.c3, sb); sb.append(",");
        treeString(root.c4, sb); sb.append(",");
        treeString(root.c5, sb); sb.append(",");
        treeString(root.c6, sb); sb.append(")");

    }

    /**
     * This assumes that there are no concurrent accesses occurring!
     * This is more efficient than size(), but its correctness is only
     * guaranteed if it is known that there will be no concurrent accesses
     * to the tree.  If this is not known for certain, then use size() instead.
     * @return the size of the tree
     */
    private int sequentialSize(final Node node) {
        if (node == null) return 0;
        if (node.c0 == null) {
            return (node.k5 != null ? 6 :
                    node.k4 != null ? 5 :
                    node.k3 != null ? 4 :
                    node.k2 != null ? 3 :
                    node.k1 != null ? 2 :
                    node.k0 != null ? 1 :
                    0);
        } else {
            return sequentialSize(node.c0) +
                   sequentialSize(node.c1) +
                   sequentialSize(node.c2) +
                   sequentialSize(node.c3) +
                   sequentialSize(node.c4) +
                   sequentialSize(node.c5) +
                   sequentialSize(node.c6);
        }
    }

    /**
     * Makes a shallow copy of node <code>node</code>, storing information
     * regarding its child references in map <code>refs</code>, before
     * recursively operating on its children.
     */
    private void readRefs(final Node node, final HashMap<Node, Children> refs) {
        if (node == null) return;
        refs.put(node, new Children(node));
        readRefs(node.c0, refs);
        readRefs(node.c1, refs);
        readRefs(node.c2, refs);
        readRefs(node.c3, refs);
        readRefs(node.c4, refs);
        readRefs(node.c5, refs);
        readRefs(node.c6, refs);

    }

    /**
     * Checks that the structure of the subtree rooted at <code>node</code>
     * matches the structure captured in the map <code>refs</code>.
     * @return true if the structures match, and false otherwise
     */
    private boolean checkRefs(final Node node, final HashMap<Node, Children> refs) {
        if (node == null) return true;
        Children children = refs.get(node);
        if (!children.equals(new Children(node))) return false;
        return checkRefs(children.c0, refs) &&
               checkRefs(children.c1, refs) &&
               checkRefs(children.c2, refs) &&
               checkRefs(children.c3, refs) &&
               checkRefs(children.c4, refs) &&
               checkRefs(children.c5, refs) &&
               checkRefs(children.c6, refs);
    }

    /**
     * Record the structure of the tree (child references) in map <code>refs</code>.
     */
    private Node buildRefs(final Node node, final HashMap<Node, Children> refs) {
        if (node == null) return null;
        Children children = refs.get(node);
        return new Node(node, buildRefs(children.c0, refs),
                              buildRefs(children.c1, refs),
                              buildRefs(children.c2, refs),
                              buildRefs(children.c3, refs),
                              buildRefs(children.c4, refs),
                              buildRefs(children.c5, refs),
                              buildRefs(children.c6, refs));
    }

    /**
     * Obtains a snapshot of the tree by reading and duplicating all tree
     * structure, then re-checking all "live" tree structure to see that it
     * matches the recorded structure (to ensure validity of the snapshot),
     * then building the copy from the recorded information.
     * @return a snapshot of the tree, or null if the tree was concurrently modified
     */
    private Node getSnapshot() {
        final HashMap<Node, Children> refs = new HashMap<Node, Children>();
        readRefs(root, refs);
        if (!checkRefs(root, refs)) return null;
        return buildRefs(root, refs);
    }



    /**
     *
     * PRIVATE CLASSES
     *
     */

    public static final class Node<E extends Comparable<? super E>, V> {
        public final int kcount;                   // key count
        public final E k0, k1, k2, k3, k4, k5;                     // keys
        public final V v0, v1, v2, v3, v4, v5;                   // values
        public volatile Node<E,V> c0, c1, c2, c3, c4, c5, c6;        // children
        public volatile Info<E,V> info = null;

        /**
         * DEBUG CODE
         */
        public Node(final Node<E,V> node, final Node c0,
                                          final Node c1,
                                          final Node c2,
                                          final Node c3,
                                          final Node c4,
                                          final Node c5,
                                          final Node c6) {
            this.kcount = node.kcount;
            this.k0 = node.k0;
            this.k1 = node.k1;
            this.k2 = node.k2;
            this.k3 = node.k3;
            this.k4 = node.k4;
            this.k5 = node.k5;

            this.v0 = node.v0;
            this.v1 = node.v1;
            this.v2 = node.v2;
            this.v3 = node.v3;
            this.v4 = node.v4;
            this.v5 = node.v5;

            this.c0 = c0;
            this.c1 = c1;
            this.c2 = c2;
            this.c3 = c3;
            this.c4 = c4;
            this.c5 = c5;
            this.c6 = c6;

        }

        /**
         * Constructor for leaf with zero keys.
         */
        Node() {
            kcount = 0;
            this.k0 = this.k1 = this.k2 = this.k3 = this.k4 = this.k5 = null;
            this.v0 = this.v1 = this.v2 = this.v3 = this.v4 = this.v5 = null;
        }

        /**
         * Constructor for newly created leaves with one key.
         */
        public Node(final E key, final V value) {
            this.k0 = key;
            this.v0 = value;
            this.kcount = 1;

            // fill in the final variables
            this.k1 = this.k2 = this.k3 = this.k4 = this.k5 = null;
            this.v1 = this.v2 = this.v3 = this.v4 = this.v5 = null;
        }

        /**
         * Constructor for the root of the tree.
         *
         * The initial tree consists of 2+7 nodes.
         *   The root node has 1 child, its 6 keys are null (infinity),
         *     and its key count is 6.
         *   The sole child of the root, c0, is an internal node with 7 children.
         *     Its keys are also null, and its key count is 6.
         *     Its children are leaves.  c0 is an empty leaf (no keys).
         *     c1, c2, ... are leaves with 1 key, namely null (representing infinity).
         *     c1, c2, ... exist to prevent deletion of this node (root.c0).
         *
         * @param root if true, the root is created otherwise, if false,
         *             the root's child root.c0 is created.
         */
        public Node(final boolean root) {
            this.k0 = this.k1 = this.k2 = this.k3 = this.k4 = this.k5 = null;                   // fill in final variables
            this.v0 = this.v1 = this.v2 = this.v3 = this.v4 = this.v5 = null;
            this.kcount = 6;
            if (root) {
                c0 = new Node<E,V>(false); // only c0 since other children unused
            } else {
                this.c0 = new Node<E,V>();  // empty leaf
                // leaves with 1 key -- prevent deletion of this
                this.c1 = new Node<E,V>(null, null);
                this.c2 = new Node<E,V>(null, null);
                this.c3 = new Node<E,V>(null, null);
                this.c4 = new Node<E,V>(null, null);
                this.c5 = new Node<E,V>(null, null);
                this.c6 = new Node<E,V>(null, null);

            }
        }

        /**
         * Constructor for case that <code>(knew,vnew)</code> is being inserted,
         * the leaf's key set is full (<code>l.kcount == 6</code>), and knew is
         * not in l. This constructor creates a new internal node with 6 keys and
         * 7 children sorted by key.
         */
        public Node(final E knew, final V vnew, final Node<E,V> l) {
             if (less(knew, l.k0)) {
                this.c0 = new Node<E,V>(knew, vnew);
                this.c1 = new Node<E,V>(l.k0, l.v0);
                this.c2 = new Node<E,V>(l.k1, l.v1);
                this.c3 = new Node<E,V>(l.k2, l.v2);
                this.c4 = new Node<E,V>(l.k3, l.v3);
                this.c5 = new Node<E,V>(l.k4, l.v4);
                this.c6 = new Node<E,V>(l.k5, l.v5);
            } else if (less(knew, l.k1)) {
                this.c0 = new Node<E,V>(l.k0, l.v0);
                this.c1 = new Node<E,V>(knew, vnew);
                this.c2 = new Node<E,V>(l.k1, l.v1);
                this.c3 = new Node<E,V>(l.k2, l.v2);
                this.c4 = new Node<E,V>(l.k3, l.v3);
                this.c5 = new Node<E,V>(l.k4, l.v4);
                this.c6 = new Node<E,V>(l.k5, l.v5);
            } else if (less(knew, l.k2)) {
                this.c0 = new Node<E,V>(l.k0, l.v0);
                this.c1 = new Node<E,V>(l.k1, l.v1);
                this.c2 = new Node<E,V>(knew, vnew);
                this.c3 = new Node<E,V>(l.k2, l.v2);
                this.c4 = new Node<E,V>(l.k3, l.v3);
                this.c5 = new Node<E,V>(l.k4, l.v4);
                this.c6 = new Node<E,V>(l.k5, l.v5);
            } else if (less(knew, l.k3)) {
                this.c0 = new Node<E,V>(l.k0, l.v0);
                this.c1 = new Node<E,V>(l.k1, l.v1);
                this.c2 = new Node<E,V>(l.k2, l.v2);
                this.c3 = new Node<E,V>(knew, vnew);
                this.c4 = new Node<E,V>(l.k3, l.v3);
                this.c5 = new Node<E,V>(l.k4, l.v4);
                this.c6 = new Node<E,V>(l.k5, l.v5);
            } else if (less(knew, l.k4)) {
                this.c0 = new Node<E,V>(l.k0, l.v0);
                this.c1 = new Node<E,V>(l.k1, l.v1);
                this.c2 = new Node<E,V>(l.k2, l.v2);
                this.c3 = new Node<E,V>(l.k3, l.v3);
                this.c4 = new Node<E,V>(knew, vnew);
                this.c5 = new Node<E,V>(l.k4, l.v4);
                this.c6 = new Node<E,V>(l.k5, l.v5);
            } else if (less(knew, l.k5)) {
                this.c0 = new Node<E,V>(l.k0, l.v0);
                this.c1 = new Node<E,V>(l.k1, l.v1);
                this.c2 = new Node<E,V>(l.k2, l.v2);
                this.c3 = new Node<E,V>(l.k3, l.v3);
                this.c4 = new Node<E,V>(l.k4, l.v4);
                this.c5 = new Node<E,V>(knew, vnew);
                this.c6 = new Node<E,V>(l.k5, l.v5);
            } else {
                this.c0 = new Node<E,V>(l.k0, l.v0);
                this.c1 = new Node<E,V>(l.k1, l.v1);
                this.c2 = new Node<E,V>(l.k2, l.v2);
                this.c3 = new Node<E,V>(l.k3, l.v3);
                this.c4 = new Node<E,V>(l.k4, l.v4);
                this.c5 = new Node<E,V>(l.k5, l.v5);
                this.c6 = new Node<E,V>(knew, vnew);
            }

            this.k0 = this.c1.k0;
            this.k1 = this.c2.k0;
            this.k2 = this.c3.k0;
            this.k3 = this.c4.k0;
            this.k4 = this.c5.k0;
            this.k5 = this.c6.k0;

            this.v0 = this.v1 = this.v2 = this.v3 = this.v4 = this.v5 = null;
            this.kcount = 6;
        }

        /**
         * Constructor for case that <code>cnew</code> is being inserted, and
         * the leaf's key set is not full.
         * This constructor creates a new leaf with keycount(old leaf)+1 keys.
         *
         * @param knew the key being inserted
         * @param l the leaf into which the key is being inserted
         * @param haskey indicates whether l already has <code>knew</code> as a key
         */
        public Node(final E knew, final V vnew, final Node<E,V> l, final boolean haskey) {
            if (haskey) {
                if (equal(knew, l.k0)) {
                    this.k0 = knew;
                    this.v0 = vnew;
                    this.k1 = l.k1;
                    this.v1 = l.v1;
                    this.k2 = l.k2;
                    this.v2 = l.v2;
                    this.k3 = l.k3;
                    this.v3 = l.v3;
                    this.k4 = l.k4;
                    this.v4 = l.v4;
                    this.k5 = l.k5;
                    this.v5 = l.v5;
                } else if (equal(knew, l.k1)) {
                    this.k0 = l.k0;
                    this.v0 = l.v0;
                    this.k1 = knew;
                    this.v1 = vnew;
                    this.k2 = l.k2;
                    this.v2 = l.v2;
                    this.k3 = l.k3;
                    this.v3 = l.v3;
                    this.k4 = l.k4;
                    this.v4 = l.v4;
                    this.k5 = l.k5;
                    this.v5 = l.v5;
                } else if (equal(knew, l.k2)) {
                    this.k0 = l.k0;
                    this.v0 = l.v0;
                    this.k1 = l.k1;
                    this.v1 = l.v1;
                    this.k2 = knew;
                    this.v2 = vnew;
                    this.k3 = l.k3;
                    this.v3 = l.v3;
                    this.k4 = l.k4;
                    this.v4 = l.v4;
                    this.k5 = l.k5;
                    this.v5 = l.v5;
                } else if (equal(knew, l.k3)) {
                    this.k0 = l.k0;
                    this.v0 = l.v0;
                    this.k1 = l.k1;
                    this.v1 = l.v1;
                    this.k2 = l.k2;
                    this.v2 = l.v2;
                    this.k3 = knew;
                    this.v3 = vnew;
                    this.k4 = l.k4;
                    this.v4 = l.v4;
                    this.k5 = l.k5;
                    this.v5 = l.v5;
                } else if (equal(knew, l.k4)) {
                    this.k0 = l.k0;
                    this.v0 = l.v0;
                    this.k1 = l.k1;
                    this.v1 = l.v1;
                    this.k2 = l.k2;
                    this.v2 = l.v2;
                    this.k3 = l.k3;
                    this.v3 = l.v3;
                    this.k4 = knew;
                    this.v4 = vnew;
                    this.k5 = l.k5;
                    this.v5 = l.v5;
                } else {
                    this.k0 = l.k0;
                    this.v0 = l.v0;
                    this.k1 = l.k1;
                    this.v1 = l.v1;
                    this.k2 = l.k2;
                    this.v2 = l.v2;
                    this.k3 = l.k3;
                    this.v3 = l.v3;
                    this.k4 = l.k4;
                    this.v4 = l.v4;
                    this.k5 = knew;
                    this.v5 = vnew;
                }
                this.kcount = l.kcount;
            } else {
                if (less(knew, l.k0)) {
                    this.k0 = knew;
                    this.v0 = vnew;
                    this.k1 = l.k0;
                    this.v1 = l.v0;
                    this.k2 = l.k1;
                    this.v2 = l.v1;
                    this.k3 = l.k2;
                    this.v3 = l.v2;
                    this.k4 = l.k3;
                    this.v4 = l.v3;
                    this.k5 = l.k4;
                    this.v5 = l.v4;
                } else if (less(knew, l.k1)) {
                    this.k0 = l.k0;
                    this.v0 = l.v0;
                    this.k1 = knew;
                    this.v1 = vnew;
                    this.k2 = l.k1;
                    this.v2 = l.v1;
                    this.k3 = l.k2;
                    this.v3 = l.v2;
                    this.k4 = l.k3;
                    this.v4 = l.v3;
                    this.k5 = l.k4;
                    this.v5 = l.v4;
                } else if (less(knew, l.k2)) {
                    this.k0 = l.k0;
                    this.v0 = l.v0;
                    this.k1 = l.k1;
                    this.v1 = l.v1;
                    this.k2 = knew;
                    this.v2 = vnew;
                    this.k3 = l.k2;
                    this.v3 = l.v2;
                    this.k4 = l.k3;
                    this.v4 = l.v3;
                    this.k5 = l.k4;
                    this.v5 = l.v4;
                } else if (less(knew, l.k3)) {
                    this.k0 = l.k0;
                    this.v0 = l.v0;
                    this.k1 = l.k1;
                    this.v1 = l.v1;
                    this.k2 = l.k2;
                    this.v2 = l.v2;
                    this.k3 = knew;
                    this.v3 = vnew;
                    this.k4 = l.k3;
                    this.v4 = l.v3;
                    this.k5 = l.k4;
                    this.v5 = l.v4;
                } else if (less(knew, l.k4)) {
                    this.k0 = l.k0;
                    this.v0 = l.v0;
                    this.k1 = l.k1;
                    this.v1 = l.v1;
                    this.k2 = l.k2;
                    this.v2 = l.v2;
                    this.k3 = l.k3;
                    this.v3 = l.v3;
                    this.k4 = knew;
                    this.v4 = vnew;
                    this.k5 = l.k4;
                    this.v5 = l.v4;
                } else {
                    this.k0 = l.k0;
                    this.v0 = l.v0;
                    this.k1 = l.k1;
                    this.v1 = l.v1;
                    this.k2 = l.k2;
                    this.v2 = l.v2;
                    this.k3 = l.k3;
                    this.v3 = l.v3;
                    this.k4 = l.k4;
                    this.v4 = l.v4;
                    this.k5 = knew;
                    this.v5 = vnew;
                }
                this.kcount = l.kcount + 1;
            }

        }

        /**
         * Constructor for the case that a key is being deleted from the
         * key set of a leaf.  This constructor creates a new leaf with
         * keycount(old leaf)-1 sorted keys.
         */
        public Node(final E key, final Node<E,V> l, final int kcount) {
            this.kcount = kcount;
            this.k5 = null;
            this.v5 = null;
             if (equal(key, l.k0)) {
                this.k0 = l.k1;
                this.v0 = l.v1;
                this.k1 = l.k2;
                this.v1 = l.v2;
                this.k2 = l.k3;
                this.v2 = l.v3;
                this.k3 = l.k4;
                this.v3 = l.v4;
                this.k4 = l.k5;
                this.v4 = l.v5;
            } else if (equal(key, l.k1)) {
                this.k0 = l.k0;
                this.v0 = l.v0;
                this.k1 = l.k2;
                this.v1 = l.v2;
                this.k2 = l.k3;
                this.v2 = l.v3;
                this.k3 = l.k4;
                this.v3 = l.v4;
                this.k4 = l.k5;
                this.v4 = l.v5;
            } else if (equal(key, l.k2)) {
                this.k0 = l.k0;
                this.v0 = l.v0;
                this.k1 = l.k1;
                this.v1 = l.v1;
                this.k2 = l.k3;
                this.v2 = l.v3;
                this.k3 = l.k4;
                this.v3 = l.v4;
                this.k4 = l.k5;
                this.v4 = l.v5;
            } else if (equal(key, l.k3)) {
                this.k0 = l.k0;
                this.v0 = l.v0;
                this.k1 = l.k1;
                this.v1 = l.v1;
                this.k2 = l.k2;
                this.v2 = l.v2;
                this.k3 = l.k4;
                this.v3 = l.v4;
                this.k4 = l.k5;
                this.v4 = l.v5;
            } else if (equal(key, l.k4)) {
                this.k0 = l.k0;
                this.v0 = l.v0;
                this.k1 = l.k1;
                this.v1 = l.v1;
                this.k2 = l.k2;
                this.v2 = l.v2;
                this.k3 = l.k3;
                this.v3 = l.v3;
                this.k4 = l.k5;
                this.v4 = l.v5;
            } else {
                this.k0 = l.k0;
                this.v0 = l.v0;
                this.k1 = l.k1;
                this.v1 = l.v1;
                this.k2 = l.k2;
                this.v2 = l.v2;
                this.k3 = l.k3;
                this.v3 = l.v3;
                this.k4 = l.k4;
                this.v4 = l.v4;
            }
        }

        // Precondition: key is not null
        final boolean hasKey(final E key) {
            return equal(key, k0) || equal(key, k1) || equal(key, k2) || equal(key, k3) || equal(key, k4) || equal(key, k5);
        }

        // Precondition: key is not null
        V getValue(E key) {
            return equal(key, k0) ? v0 :
                   equal(key, k1) ? v1 :
                   equal(key, k2) ? v2 :
                   equal(key, k3) ? v3 :
                   equal(key, k4) ? v4 :
                   equal(key, k5) ? v5 : null;
        }

        @Override
        public String toString() {
            StringBuffer sb = new StringBuffer();
            treeString(this, sb);
            return sb.toString();
        }

        @Override
        public final boolean equals(final Object o) {
            if (o == null) return false;
            if (o.getClass() != getClass()) return false;
            Node n = (Node) o;
            if (n.c0 != null && !n.c0.equals(c0) ||
                n.c1 != null && !n.c1.equals(c1) ||
                n.c2 != null && !n.c2.equals(c2) ||
                n.c3 != null && !n.c3.equals(c3) ||
                n.c4 != null && !n.c4.equals(c4) ||
                n.c5 != null && !n.c5.equals(c5) ||
                n.c6 != null && !n.c6.equals(c6)) return false;
            if (n.k0 != null && !n.k0.equals(k0) ||
                n.k1 != null && !n.k1.equals(k1) ||
                n.k2 != null && !n.k2.equals(k2) ||
                n.k3 != null && !n.k3.equals(k3) ||
                n.k4 != null && !n.k4.equals(k4) ||
                n.k5 != null && !n.k5.equals(k5)) return false;
            if (n.v0 != null && !n.v0.equals(v0) ||
                n.v1 != null && !n.v1.equals(v1) ||
                n.v2 != null && !n.v2.equals(v2) ||
                n.v3 != null && !n.v3.equals(v3) ||
                n.v4 != null && !n.v4.equals(v4) ||
                n.v5 != null && !n.v5.equals(v5)) return false;
            if ((n.info != null && !n.info.equals(info)) || n.kcount != kcount) return false;
            return true;
        }

    }

    static interface Info<E extends Comparable<? super E>, V> {}

    static final class IInfo<E extends Comparable<? super E>, V> implements Info<E,V> {
        final Node<E,V> p, oldchild, newchild;

        IInfo(final Node<E,V> oldchild, final Node<E,V> p, final Node<E,V> newchild) {
            this.p = p;
            this.oldchild = oldchild;
            this.newchild = newchild;
        }

        @Override
        public boolean equals(Object o) {
            IInfo x = (IInfo) o;
            if (x.p != p || x.oldchild != oldchild || x.newchild != newchild) return false;
            return true;
        }
    }

    static final class DInfo<E extends Comparable<? super E>, V> implements Info<E,V> {
        final Node<E,V> p, l, gp;
        final Info<E,V> pinfo;

        DInfo(final Node<E,V> l, final Node<E,V> p, final Node<E,V> gp, final Info<E,V> pinfo) {
            this.p = p;
            this.l = l;
            this.gp = gp;
            this.pinfo = pinfo;
        }

        @Override
        public boolean equals(Object o) {
            DInfo x = (DInfo) o;
            if (x.p != p || x.l != l || x.gp != gp || x.pinfo != pinfo) return false;
            return true;
        }
    }

    static final class Mark<E extends Comparable<? super E>, V> implements Info<E,V> {
        final DInfo<E,V> dinfo;

        Mark(final DInfo<E,V> dinfo) {
            this.dinfo = dinfo;
        }

        @Override
        public boolean equals(Object o) {
            Mark x = (Mark) o;
            if (x.dinfo != dinfo) return false;
            return true;
        }
    }

    static final class Clean<E extends Comparable<? super E>, V> implements Info<E,V> {
        @Override
        public boolean equals(Object o) {
            return (this == o);
        }
    }

    private class Children {
        Node c0, c1, c2, c3, c4, c5, c6;
        public Children(Node node) {
            this.c0 = node.c0;
            this.c1 = node.c1;
            this.c2 = node.c2;
            this.c3 = node.c3;
            this.c4 = node.c4;
            this.c5 = node.c5;
            this.c6 = node.c6;

        }
        @Override
        public boolean equals(Object o) {
            if (o == null || !o.getClass().equals(getClass())) return false; // CAN DO AWAY WITH THIS AT THE COST OF TYPE SAFETY!!
            Children children = (Children) o;
            return this.c0 == children.c0 &&
                   this.c1 == children.c1 &&
                   this.c2 == children.c2 &&
                   this.c3 == children.c3 &&
                   this.c4 == children.c4 &&
                   this.c5 == children.c5 &&
                   this.c6 == children.c6;
        }
    }



}