package net.coderodde.util;

import java.util.NoSuchElementException;
import java.util.Objects;

/**
 * This class implements a sorted map mapping integer keys to values of
 * arbitrary type.
 *
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 9, 2017)
 * @param <V> the type of values.
 */
public final class VanEmdeBoasTreeIntMap<V> {

    /**
     * The minimum universe size a node of a van Emde Boas tree can hold.
     */
    private static final int MINIMUM_UNIVERSE_SIZE = 2;

    /**
     * The value used to denote the absence of an integer key.
     */
    private static final int NULL_KEY = -1;

    /**
     * Used to denote that there is an integer mapped to a {@code null} value.
     */
    private final V NULL_VALUE = (V) new Object();

    /**
     * This static inner class implements a node in a van Emde Boas tree.
     */
    private static final class VEBTree {

        /**
         * The universe size of this vEB node.
         */
        private final int universeSize;

        /**
         * The shift length for computing the high indices.
         */
        private final int highShift;

        /**
         * The mask used to compute the low indices.
         */
        private final int lowMask;

        /**
         * The minimum integer key in the tree starting from this node.
         */
        private int min;

        /**
         * The maximum integer key in the tree starting from this node.
         */
        private int max;

        /**
         * The summary vEB-tree.
         */
        private final VEBTree summary;

        /**
         * The children nodes of this vEB node.
         */
        private final VEBTree[] cluster;

        VEBTree(int universeSize) {
            this.universeSize = universeSize;

            int universeSizeLowerSquare = lowerSquare(universeSize);

            this.lowMask = universeSizeLowerSquare - 1;
            this.highShift =
                    Integer.numberOfTrailingZeros(universeSizeLowerSquare);

            this.min = NULL_KEY;
            this.max = NULL_KEY;

            if (universeSize != MINIMUM_UNIVERSE_SIZE) {
                int upperUniverseSizeSquare = upperSquare(universeSize);
                int lowerUniverseSizeSquare = lowerSquare(universeSize);
                this.summary = new VEBTree(upperUniverseSizeSquare);
                this.cluster = new VEBTree[upperUniverseSizeSquare];

                for (int i = 0; i != upperUniverseSizeSquare; ++i) {
                    this.cluster[i] = new VEBTree(lowerUniverseSizeSquare);
                }
            } else {
                this.summary = null;
                this.cluster = null;
            }
        }

        int getUniverseSize() {
            return universeSize;
        }

        int getMinimumKey() {
            return min;
        }

        int getMaximumKey() {
            return max;
        }

        int getSuccessor(int x) {
            if (universeSize == MINIMUM_UNIVERSE_SIZE) {
                if (x == 0 && max == 1) {
                    return 1;
                }

                return NULL_KEY;
            }

            if (min != NULL_KEY && x < min) {
                return min;
            }

            int maximumLow = cluster[high(x)].getMaximumKey();

            if (maximumLow != NULL_KEY && low(x) < maximumLow) {
                int offset = cluster[high(x)].getSuccessor(low(x));
                return index(high(x), offset);
            }

            int successorCluster = summary.getSuccessor(high(x));

            if (successorCluster == NULL_KEY) {
                return NULL_KEY;
            }

            int offset = cluster[successorCluster].getMinimumKey();
            return index(successorCluster, offset);
        }

        int getPredecessor(int x) {
            if (universeSize == MINIMUM_UNIVERSE_SIZE) {
                if (min == NULL_KEY) {
                    return NULL_KEY;
                }

                if (x == 1 && min == 0) {
                    return 0;
                }

                return NULL_KEY;
            }

            if (max != NULL_KEY && x > max) {
                return max;
            }

            int minimumLow = cluster[high(x)].getMinimumKey();

            if (minimumLow != NULL_KEY && low(x) > minimumLow) {
                int offset = cluster[high(x)].getPredecessor(low(x));
                return index(high(x), offset);
            }

            int predecessorCluster = summary.getPredecessor(high(x));

            if (predecessorCluster == NULL_KEY) {
                if (min != NULL_KEY && x > min) {
                    return min;
                }

                return NULL_KEY;
            }

            int offset = cluster[predecessorCluster].getMaximumKey();
            return index(predecessorCluster, offset);
        }

        void treeInsert(int x) {
            if (min == NULL_KEY) {
                emptyTreeInsert(x);
                return;
            }

            if (x < min) {
                int tmp = x;
                x = min;
                min = tmp;
            }

            if (universeSize != MINIMUM_UNIVERSE_SIZE) {
                int minimum = cluster[high(x)].getMinimumKey();

                if (minimum == NULL_KEY) {
                    summary.treeInsert(high(x));
                    cluster[high(x)].emptyTreeInsert(low(x));
                } else {
                    cluster[high(x)].treeInsert(low(x));
                }
            }

            if (max < x) {
                max = x;
            }
        }

        void treeDelete(int x) {
            if (min == max) {
                min = NULL_KEY;
                max = NULL_KEY;
                return;
            }

            if (universeSize == MINIMUM_UNIVERSE_SIZE) {
                if (x == 0) {
                    min = 1;
                } else {
                    max = 0;
                }

                max = min;
                return;
            }

            if (min == x) {
                int firstCluster = summary.getMinimumKey();
                x = index(firstCluster, cluster[firstCluster].getMinimumKey());
                min = x;
            }

            cluster[high(x)].treeDelete(low(x));

            if (cluster[high(x)].getMinimumKey() == NULL_KEY) {
                summary.treeDelete(high(x));

                if (x == max) {
                    int summaryMaximum = summary.getMaximumKey();

                    if (summaryMaximum == NULL_KEY) {
                        max = min;
                    } else {
                        int maximumKey =
                                cluster[summaryMaximum].getMaximumKey();
                        max = index(summaryMaximum, maximumKey);
                    }
                }
            } else if (x == max) {
                int maximumKey = cluster[high(x)].getMaximumKey();
                max = index(high(x), maximumKey);
            }
        }

        private void emptyTreeInsert(int x) {
            min = x;
            max = x;
        }

        private int high(int x) {
            return x >>> highShift;
        }

        private int low(int x) {
            return x & lowMask;
        }

        private int index(int x, int y) {
            return (x << highShift) | (y & lowMask);
        }
    }

    private static int upperSquare(int number) {
        double exponent = Math.ceil(Math.log(number) / Math.log(2.0) / 2.0);
        return (int) Math.pow(2.0, exponent);
    }

    private static int lowerSquare(int number) {
        double exponent = Math.floor(Math.log(number) / Math.log(2.0) / 2.0);
        return (int) Math.pow(2.0, exponent);
    }

    private final VEBTree root;
    private final int minimumKey;
    private final int maximumKey;
    private final V[] table;
    private int size;

    public VanEmdeBoasTreeIntMap(int minimumKey, int maximumKey) {
        checkBounds(minimumKey, maximumKey);
        this.minimumKey = minimumKey;
        this.maximumKey = maximumKey;
        int universeSize = maximumKey - minimumKey + 1;
        universeSize = fixUniverseSize(universeSize);
        this.root = new VEBTree(universeSize);
        this.table = (V[]) new Object[universeSize];
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public int getMinimumKey() {
        return size != 0 ? root.min + minimumKey : this.maximumKey + 1;
    }

    public int getMaximumKey() {
        return size != 0 ? root.max + minimumKey : this.minimumKey - 1;
    }

    public int getNextIntKey(int key) {
        checkKey(key);
        int nextKey = root.getSuccessor(key - minimumKey);
        return nextKey == NULL_KEY ?
                this.minimumKey - 1 :
                nextKey + minimumKey;
    }

    public int getPreviousIntKey(int key) {
        checkKey(key);
        int previousKey = root.getPredecessor(key - minimumKey);
        return previousKey == NULL_KEY ?
                this.maximumKey + 1 :
                previousKey + minimumKey;
    }

    public boolean containsKey(int key) {
        checkKey(key);
        return table[key - minimumKey] != null;
    }

    public V get(int key) {
        checkKey(key);
        V value = table[key - minimumKey];
        return (value == null || value == NULL_VALUE) ? null : value;
    }

    public V put(int key, V value) {
        checkKey(key);
        // Translate the key:
        key -= minimumKey;
        V currentValue = table[key];

        if (currentValue != null) {
            // key is present in this map.
            V oldValue = table[key];
            table[key] = value == null ? NULL_VALUE : value;
            return oldValue;
        } else {
            root.treeInsert(key);
            table[key] = value != null ? value : NULL_VALUE;
            size++;
            return null;
        }
    }

    public V remove(int key) {
        checkKey(key);
        // Translate the key:
        key -= minimumKey;
        V value = table[key];

        if (value != null) {
            // key is in this map.
            table[key] = null;
            root.treeDelete(key);
            size--;
            return value == NULL_VALUE ? null : value;
        } else {
            return null;
        }
    }

    public void clear() {
        int key = root.min;
        int nextKey;

        for (int i = 0; i != size; ++i) {
            nextKey = root.getSuccessor(key);
            root.treeDelete(key); // Remove key.
            table[key] = null;    // Remove value.
            key = nextKey;
        }

        size = 0;
    }

    /**
     * This inner interface specifies the API for key iterators.
     */
    public interface KeyIterator {

        /**
         * Returns {@code true} only if there is more keys to iterate.
         *
         * @return {@code true} if there is more keys to iterate.
         */
        public boolean hasNextKey();

        /**
         * Returns the next key in the sorted iteration order.
         *
         * @return the next key.
         */
        public int nextKey();

        /**
         * Removes the entire key/value pair of the current key.
         */
        public void removeKey();
    }

    /**
     * Holds a mapping while iterating the data structure.
     *
     * @param <V> the value type.
     */
    public static final class KeyValueMapping<V> {

        public int key;
        public V value;

        @Override
        public boolean equals(Object o) {
            if (o == this) {
                return true;
            }

            if (o == null) {
                return false;
            }

            if (!getClass().equals(o.getClass())) {
                return false;
            }

            KeyValueMapping<V> other = (KeyValueMapping<V>) o;
            return key == other.key && Objects.equals(value, other.value);
        }
    }

    /**
     * This inner interface specifies the API for the key/value iterators.
     *
     * @param <V> the value type.
     */
    public interface KeyValueIterator<V> {

        /**
         * Returns {@code true} only if there is more key/value pairs to
         * iterate.
         *
         * @return {@code true} if there is more pairs to iterate.
         */
        public boolean hasNextKeyValuePair();

        /**
         * Loads the current key/value pair.
         *
         * @param keyValueMapping the key/value pair where to store the data.
         */
        public void nextKeyValuePair(KeyValueMapping<V> keyValueMapping);

        /**
         * Removes the previously iterated key/value pair.
         */
        public void removeKeyValuePair();
    }

    /**
     * Implements the key iterator that traverses the integers in order via the
     * underlying van Emde Boas tree.
     */
    public final class TreeKeyIterator implements KeyIterator {

        private int iterated;
        private int lastReturned;

        /**
         * {@inheritDoc }
         */
        @Override
        public boolean hasNextKey() {
            return iterated < size;
        }

        /**
         * {@inheritDoc }
         */
        @Override
        public int nextKey() {
            if (!hasNextKey()) {
                throw new NoSuchElementException("Nothing to iterate left.");
            }

            if (iterated == 0) {
                lastReturned = getMinimumKey();
                iterated++;
                return lastReturned;
            } else {
                int next = getNextIntKey(lastReturned);
                lastReturned = next;
                iterated++;
                return next;
            }
        }

        /**
         * {@inheritDoc }
         */
        @Override
        public void removeKey() {
            if (iterated == 0) {
                throw new IllegalStateException(
                        "No current key to remove yet.");
            }

            remove(lastReturned);
        }
    }

    /**
     * Implements a key iterator that traverses directly the mapping table. This
     * may provide a speed up over the {@link TreeKeyIterator} if the table is
     * densely populated.
     */
    public final class TableKeyIterator implements KeyIterator {

        private int iterated;
        private int currentIndex;

        /**
         * {@inheritDoc }
         */
        @Override
        public boolean hasNextKey() {
            return iterated < size;
        }

        /**
         * {@inheritDoc }
         */
        @Override
        public int nextKey() {
            if (!hasNextKey()) {
                throw new NoSuchElementException("Nothing to iterate left.");
            }

            if (iterated == 0) {
                currentIndex = getMinimumKey() - minimumKey;
                iterated++;
                return getMinimumKey();
            } else {
                for (currentIndex++;
                        table[currentIndex] == null;
                        currentIndex++) {}

                iterated++;
                return currentIndex + minimumKey;
            }
        }

        /**
         * {@inheritDoc }
         */
        @Override
        public void removeKey() {
            if (iterated == 0) {
                throw new IllegalStateException(
                        "No current key to remove yet.");
            }

            remove(currentIndex + minimumKey);
        }
    }

    /**
     * Implements the key iterator that traverses the integers in order via the
     * underlying van Emde Boas tree.
     */
    public final class TreeKeyValueIterator implements KeyValueIterator<V> {

        private int iterated;
        private int lastReturned;

        /**
         * {@inheritDoc }
         */
        @Override
        public boolean hasNextKeyValuePair() {
            return iterated < size;
        }

        /**
         * {@inheritDoc }
         */
        @Override
        public void nextKeyValuePair(KeyValueMapping<V> keyValueMapping) {
            if (!hasNextKeyValuePair()) {
                throw new NoSuchElementException("Nothing to iterate left.");
            }

            if (iterated == 0) {
                lastReturned = getMinimumKey();
                iterated++;
                V value = table[lastReturned - minimumKey];
                keyValueMapping.key = lastReturned;
                keyValueMapping.value = value == NULL_VALUE ? null : value;
            } else {
                lastReturned = getNextIntKey(lastReturned);
                iterated++;
                V value = table[lastReturned - minimumKey];
                keyValueMapping.key = lastReturned;
                keyValueMapping.value = value == NULL_VALUE ? null : value;
            }
        }

        /**
         * {@inheritDoc }
         */
        @Override
        public void removeKeyValuePair() {
            if (iterated == 0) {
                throw new IllegalStateException(
                        "No current key to remove yet.");
            }

            remove(lastReturned);
        }
    }

    /**
     * Implements a key iterator that traverses directly the mapping table. This
     * may provide a speed up over the {@link TreeKeyIterator} if the table is
     * densely populated.
     */
    public final class TableKeyValueIterator implements KeyValueIterator<V> {

        private int iterated;
        private int currentIndex;

        /**
         * {@inheritDoc }
         */
        @Override
        public boolean hasNextKeyValuePair() {
            return iterated < size;
        }

        /**
         * {@inheritDoc }
         */
        @Override
        public void nextKeyValuePair(KeyValueMapping<V> keyValueMapping) {
            if (!hasNextKeyValuePair()) {
                throw new NoSuchElementException("Nothing to iterate left.");
            }

            if (iterated == 0) {
                currentIndex = getMinimumKey() - minimumKey;
                V value = table[currentIndex];
                iterated++;
                keyValueMapping.key = getMinimumKey();
                keyValueMapping.value = value == NULL_VALUE ?
                                        null :
                                        value;
            } else {
                for (currentIndex++;
                        table[currentIndex] == null;
                        currentIndex++) {}

                iterated++;
                V value = table[currentIndex];
                keyValueMapping.key = currentIndex + minimumKey;
                keyValueMapping.value = value == NULL_VALUE ?
                                        null :
                                        value;
            }
        }

        /**
         * {@inheritDoc }
         */
        @Override
        public void removeKeyValuePair() {
            if (iterated == 0) {
                throw new IllegalStateException(
                        "No current key to remove yet.");
            }

            remove(currentIndex + minimumKey);
        }
    }

    public float getTableDensityFactor() {
        if (size == 0) {
            return 0.0f;
        }

        int rangeLength = getMaximumKey() - getMinimumKey() + 1;
        return (1.0f * size) / rangeLength;
    }

    public KeyIterator treeKeyIterator() {
        return new TreeKeyIterator();
    }

    public KeyIterator tableKeyIterator() {
        return new TableKeyIterator();
    }

    public KeyValueIterator<V> treeKeyValueIterator() {
        return new TreeKeyValueIterator();
    }

    public KeyValueIterator<V> tableKeyValueIterator() {
        return new TableKeyValueIterator();
    }

    public static final class Mapping<V> {
        public int key;
        public V value;

        @Override
        public String toString() {
            return "(" + key + " -> " + value + ")";
        }
    }

    public static final class MappingIterator<V> {

        private final VanEmdeBoasTreeIntMap<V> tree;
        private int iterated = 0;
        private int lastReturned;

        MappingIterator(VanEmdeBoasTreeIntMap<V> tree) {
            this.tree = tree;
        }

        public boolean hasNext() {
            return iterated < tree.size;
        }

        public void next(Mapping<V> mapping) {
            if (!hasNext()) {
                throw new NoSuchElementException("Nothing to iterate left.");
            }

            if (iterated == 0) {
                lastReturned = tree.getMinimumKey();
                iterated++;
                mapping.key = lastReturned;
                mapping.value = tree.table[lastReturned - tree.minimumKey];
            } else {
                int next = tree.getNextIntKey(lastReturned);
                lastReturned = next;
                iterated++;
                mapping.key = lastReturned;
                mapping.value = tree.table[lastReturned - tree.minimumKey];
            }
        }
    }

    public MappingIterator<V> mappingIterator() {
        return new MappingIterator<>(this);
    }

    private void checkBounds(int minimumKey, int maximumKey) {
        if (minimumKey > maximumKey) {
            throw new IllegalArgumentException(
                    "minimumKey(" + minimumKey + ") > " +
                    "maximumKey(" + maximumKey + ")");
        }
    }

    private int fixUniverseSize(int requestedUniverseSize) {
        int tmp = Integer.highestOneBit(requestedUniverseSize);
        return tmp == requestedUniverseSize ?
                requestedUniverseSize :
               (tmp << 1);
    }

    private void checkKey(int key) {
        if (key < minimumKey) {
            throw new IllegalArgumentException(
                    "The given key (" + key + ") is too small. Must be at " +
                    "least " + minimumKey + ".");
        }

        if (key > maximumKey) {
            throw new IllegalArgumentException(
                    "The given key (" + key + ") is too large. Must be at " +
                    "most " + maximumKey + ".");
        }
    }
}

package net.coderodde.util;

import net.coderodde.util.VanEmdeBoasTreeIntMap.KeyValueMapping;
import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertFalse;
import static org.junit.Assert.assertNull;
import static org.junit.Assert.assertTrue;
import org.junit.Test;

public class VanEmdeBoasTreeIntMapTest {

    @Test
    public void testSize() {
        VanEmdeBoasTreeIntMap<Integer> tree =
                new VanEmdeBoasTreeIntMap<>(-10, 10);

        for (int i = -10, size = 0; i <= 10; ++i, ++size) {
            assertEquals(size, tree.size());
            tree.put(i, i);
            assertEquals(size + 1, tree.size());
        }
    }

    @Test
    public void testIsEmpty() {
        VanEmdeBoasTreeIntMap<Integer> tree =
                new VanEmdeBoasTreeIntMap<>(-10, 10);

        assertTrue(tree.isEmpty());
        tree.put(0, 0);
        assertFalse(tree.isEmpty());
        tree.put(1, 1);
        assertFalse(tree.isEmpty());
        tree.remove(0);
        assertFalse(tree.isEmpty());
        tree.remove(1);
        assertTrue(tree.isEmpty());
    }

    @Test
    public void testGetMinimumKey() {
        VanEmdeBoasTreeIntMap<Integer> tree =
                new VanEmdeBoasTreeIntMap<>(-5, 4);

        assertEquals(5, tree.getMinimumKey());

        for (int i = 4; i >= -5; --i) {
            tree.put(i, i);
            assertEquals(i, tree.getMinimumKey());
        }

        tree.clear();

        assertEquals(5, tree.getMinimumKey());

        tree = new VanEmdeBoasTreeIntMap<>(Integer.MAX_VALUE - 5,
                                           Integer.MAX_VALUE);

        assertEquals(Integer.MIN_VALUE, tree.getMinimumKey());
    }

    @Test
    public void testGetMaximumKey() {
        VanEmdeBoasTreeIntMap<Integer> tree =
                new VanEmdeBoasTreeIntMap<>(-5, 4);

        assertEquals(-6, tree.getMaximumKey());

        for (int i = -5; i <= 4; ++i) {
            tree.put(i, i);
            assertEquals(i, tree.getMaximumKey());
        }

        tree.clear();

        assertEquals(-6, tree.getMaximumKey());

        tree = new VanEmdeBoasTreeIntMap<>(Integer.MIN_VALUE,
                                           Integer.MIN_VALUE + 5);

        assertEquals(Integer.MAX_VALUE, tree.getMaximumKey());
    }

    @Test
    public void testGetNextIntKey() {
        VanEmdeBoasTreeIntMap<Integer> tree =
                new VanEmdeBoasTreeIntMap<>(-3, 3);

        tree.put(-3, -3);
        tree.put(-1, -1);
        tree.put(0, 0);
        tree.put(2, 2);

        assertEquals(-1, tree.getNextIntKey(-3));
        assertEquals(-1, tree.getNextIntKey(-2));

        assertEquals(0, tree.getNextIntKey(-1));
        assertEquals(2, tree.getNextIntKey(0));
        assertEquals(2, tree.getNextIntKey(1));
        assertEquals(-4, tree.getNextIntKey(2));
        assertEquals(-4, tree.getNextIntKey(3));

        tree.clear();

        for (int i = -3; i <= 3; ++i) {
            assertEquals(-4, tree.getNextIntKey(i));
        }
    }

    @Test
    public void testGetPreviousIntKey() {
        VanEmdeBoasTreeIntMap<Integer> tree =
                new VanEmdeBoasTreeIntMap<>(-3, 3);

        tree.put(-3, -3);
        tree.put(-1, -1);
        tree.put(0, 0);
        tree.put(2, 2);

        assertEquals(2, tree.getPreviousIntKey(3));

        assertEquals(0, tree.getPreviousIntKey(2));
        assertEquals(0, tree.getPreviousIntKey(1));

        assertEquals(-1, tree.getPreviousIntKey(0));
        assertEquals(-3, tree.getPreviousIntKey(-1));
        assertEquals(-3, tree.getPreviousIntKey(-2));
        assertEquals(4, tree.getPreviousIntKey(-3));

        tree.clear();

        for (int i = -3; i <= 3; ++i) {
            assertEquals(4, tree.getPreviousIntKey(i));
        }
    }

    @Test
    public void testContains() {
        VanEmdeBoasTreeIntMap<Integer> tree =
                new VanEmdeBoasTreeIntMap<>(-5, -1);

        tree.put(-5, null);
        tree.put(-3, -3);
        tree.put(-1, -1);

        assertTrue(tree.containsKey(-5));
        assertTrue(tree.containsKey(-3));
        assertTrue(tree.containsKey(-1));

        assertFalse(tree.containsKey(-4));
        assertFalse(tree.containsKey(-2));
    }

    @Test
    public void testGet() {
        VanEmdeBoasTreeIntMap<Integer> tree =
                new VanEmdeBoasTreeIntMap<>(-5, -1);

        tree.put(-5, null);
        tree.put(-3, -13);
        tree.put(-1, -11);

        assertNull(tree.get(-5));
        assertEquals(Integer.valueOf(-11), tree.get(-1));
        assertEquals(Integer.valueOf(-13), tree.get(-3));
    }

    @Test
    public void testPut() {
        VanEmdeBoasTreeIntMap<Integer> tree =
                new VanEmdeBoasTreeIntMap<>(-5, 10);

        for (int i = -2; i <= 4; ++i) {
            assertFalse(tree.containsKey(i));
            assertNull(tree.put(i, 2 * i));
            assertTrue(tree.containsKey(i));
        }

        for (int i = -3; i >= -5; --i) {
            assertFalse(tree.containsKey(i));
            assertNull(tree.get(i));
        }

        assertTrue(tree.containsKey(0));
        tree.remove(0);
        assertFalse(tree.containsKey(0));
    }

    @Test(expected = IllegalArgumentException.class)
    public void testLowerBound() {
        VanEmdeBoasTreeIntMap<String> tree = new VanEmdeBoasTreeIntMap<>(-4, 4);

        tree.put(-5, "-5");
    }

    @Test(expected = IllegalArgumentException.class)
    public void testUpperBound() {
        VanEmdeBoasTreeIntMap<String> tree = new VanEmdeBoasTreeIntMap<>(-4, 4);

        tree.put(5, "5");
    }

    @Test
    public void testTreeKeyIterator() {
        VanEmdeBoasTreeIntMap<String> tree = new VanEmdeBoasTreeIntMap<>(-4, 4);

        for (int i = 4; i >= -4; --i) {
            tree.put(i, null);
        }

        VanEmdeBoasTreeIntMap.KeyIterator iterator = tree.treeKeyIterator();

        for (int i = -4; i <= 4; ++i) {
            assertTrue(iterator.hasNextKey());
            assertEquals(i, iterator.nextKey());
        }

        assertEquals(9, tree.size());

        iterator = tree.treeKeyIterator();

        assertEquals(-4, iterator.nextKey());
        iterator.removeKey();
        assertEquals(-3, iterator.nextKey());
        assertEquals(-2, iterator.nextKey());
        assertEquals(-1, iterator.nextKey());
        iterator.removeKey();

        assertFalse(tree.containsKey(-4));
        assertTrue(tree.containsKey(-3));
        assertTrue(tree.containsKey(-2));
        assertFalse(tree.containsKey(-1));

        assertEquals(7, tree.size());
    }

    @Test
    public void testTableKeyIterator() {
        VanEmdeBoasTreeIntMap<String> tree = new VanEmdeBoasTreeIntMap<>(-4, 4);

        for (int i = 4; i >= -4; --i) {
            tree.put(i, null);
        }

        VanEmdeBoasTreeIntMap.KeyIterator iterator = tree.tableKeyIterator();

        for (int i = -4; i <= 4; ++i) {
            assertTrue(iterator.hasNextKey());
            assertEquals(i, iterator.nextKey());
        }

        assertEquals(9, tree.size());

        iterator = tree.treeKeyIterator();

        assertEquals(-4, iterator.nextKey());
        iterator.removeKey();
        assertEquals(-3, iterator.nextKey());
        assertEquals(-2, iterator.nextKey());
        assertEquals(-1, iterator.nextKey());
        iterator.removeKey();

        assertFalse(tree.containsKey(-4));
        assertTrue(tree.containsKey(-3));
        assertTrue(tree.containsKey(-2));
        assertFalse(tree.containsKey(-1));

        assertEquals(7, tree.size());
    }

    @Test
    public void testTreeKeyValueIterator() {
        KeyValueMapping<String> mapping = new KeyValueMapping<>();
        VanEmdeBoasTreeIntMap<String> tree = new VanEmdeBoasTreeIntMap<>(-4, 4);

        for (int i = 4; i >= -4; --i) {
            tree.put(i, "" + i);
        }

        VanEmdeBoasTreeIntMap.KeyValueIterator<String> iterator =
                tree.treeKeyValueIterator();

        for (int i = -4; i <= 4; ++i) {
            assertTrue(iterator.hasNextKeyValuePair());
            iterator.nextKeyValuePair(mapping);
            assertEquals(i, mapping.key);
            assertEquals("" + i, mapping.value);
        }

        assertEquals(9, tree.size());

        iterator = tree.treeKeyValueIterator();
        iterator.nextKeyValuePair(mapping);

        assertEquals(-4, mapping.key);
        assertEquals("-4", mapping.value);

        iterator.removeKeyValuePair();
        iterator.nextKeyValuePair(mapping);
        assertEquals(-3, mapping.key);
        assertEquals("-3", mapping.value);

        iterator.nextKeyValuePair(mapping);
        assertEquals(-2, mapping.key);
        assertEquals("-2", mapping.value);

        iterator.nextKeyValuePair(mapping);
        assertEquals(-1, mapping.key);
        assertEquals("-1", mapping.value);
        iterator.removeKeyValuePair();

        assertFalse(tree.containsKey(-4));
        assertTrue(tree.containsKey(-3));
        assertTrue(tree.containsKey(-2));
        assertFalse(tree.containsKey(-1));

        assertEquals(7, tree.size());
    }

    @Test
    public void testTableKeyValueIterator() {
        KeyValueMapping<String> mapping = new KeyValueMapping<>();
        VanEmdeBoasTreeIntMap<String> tree = new VanEmdeBoasTreeIntMap<>(-4, 4);

        for (int i = 4; i >= -4; --i) {
            tree.put(i, "" + i);
        }

        VanEmdeBoasTreeIntMap.KeyValueIterator<String> iterator =
                tree.tableKeyValueIterator();

        for (int i = -4; i <= 4; ++i) {
            assertTrue(iterator.hasNextKeyValuePair());
            iterator.nextKeyValuePair(mapping);
            assertEquals(i, mapping.key);
            assertEquals("" + i, mapping.value);
        }

        assertEquals(9, tree.size());

        iterator = tree.treeKeyValueIterator();
        iterator.nextKeyValuePair(mapping);

        assertEquals(-4, mapping.key);
        assertEquals("-4", mapping.value);

        iterator.removeKeyValuePair();
        iterator.nextKeyValuePair(mapping);
        assertEquals(-3, mapping.key);
        assertEquals("-3", mapping.value);

        iterator.nextKeyValuePair(mapping);
        assertEquals(-2, mapping.key);
        assertEquals("-2", mapping.value);

        iterator.nextKeyValuePair(mapping);
        assertEquals(-1, mapping.key);
        assertEquals("-1", mapping.value);
        iterator.removeKeyValuePair();

        assertFalse(tree.containsKey(-4));
        assertTrue(tree.containsKey(-3));
        assertTrue(tree.containsKey(-2));
        assertFalse(tree.containsKey(-1));

        assertEquals(7, tree.size());
    }

    @Test
    public void testRemove() {
        VanEmdeBoasTreeIntMap<Integer> tree = new VanEmdeBoasTreeIntMap<>(1, 5);

        tree.put(3, 3);
        tree.put(1, 1);
        tree.put(5, 5);

        assertTrue(tree.containsKey(1));
        assertTrue(tree.containsKey(3));
        assertTrue(tree.containsKey(5));

        tree.put(1, null);

        assertTrue(tree.containsKey(1));

        tree.remove(1);

        assertFalse(tree.containsKey(1));
    }

    @Test
    public void clear() {
        VanEmdeBoasTreeIntMap<Integer> tree =
                new VanEmdeBoasTreeIntMap<>(3, 10);

        for (int i = 4, sz = 0; i <= 8; ++i, ++sz) {
            assertEquals(sz, tree.size());
            tree.put(i, null);
            assertEquals(sz + 1, tree.size());
        }

        assertEquals(5, tree.size());
        tree.clear();
        assertEquals(0, tree.size());

        for (int i = 3; i <= 10; ++i) {
            assertFalse(tree.containsKey(i));
            assertNull(tree.get(i));
            assertNull(tree.remove(i));
        }
    }
}

package net.coderodde.util;

import java.util.HashMap;
import java.util.Map;
import java.util.Random;
import java.util.TreeMap;
import net.coderodde.util.VanEmdeBoasTreeIntMap.KeyIterator;
import net.coderodde.util.VanEmdeBoasTreeIntMap.KeyValueIterator;
import net.coderodde.util.VanEmdeBoasTreeIntMap.KeyValueMapping;

/**
 * This class benchmarks the {@link VanEmdeBoasTreeIntMap} against a
 * {@link TreeMap} and {@link HashMap}.
 *
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 13, 2017)
 */
public final class Benchmark {

    private static final int MINIMUM_KEY = -1000_000;
    private static final int MAXIMUM_KEY = 1_000_000;
    private static final int INTEGER_ARRAY_LENGTH = 1_500_000;
    private static final Random RANDOM;

    static {
        long seed = System.currentTimeMillis();
        System.out.println("Seed = " + seed);
        RANDOM = new Random(seed);
    }

    public static void main(String[] args) {
        warmup();

        System.out.println();

        benchmark();
    }

    private static void benchmark() {
        Integer[] testArray = createRandomIntegerArray(INTEGER_ARRAY_LENGTH,
                                                       MINIMUM_KEY,
                                                       MAXIMUM_KEY);
        benchmarkTreeMap(testArray);
        System.out.println();
        benchmarkHashMap(testArray);
        System.out.println();
        benchmarkVebMap(testArray);
    }

    private static void benchmarkTreeMap(Integer[] testArray) {
        benchmarkMap(new TreeMap<>(), testArray);
    }

    private static void benchmarkHashMap(Integer[] testArray) {
        benchmarkMap(new HashMap<>(), testArray);
    }

    private static void benchmarkVebMap(Integer[] testArray) {
        System.out.println(

                "--- " + VanEmdeBoasTreeIntMap.class.getSimpleName() + " ---");

        long startTime;
        long endTime;
        long totalTime = 0L;

        startTime = System.currentTimeMillis();
        // Create.
        VanEmdeBoasTreeIntMap<Integer> map =
                new VanEmdeBoasTreeIntMap<>(MINIMUM_KEY, MAXIMUM_KEY);

        endTime = System.currentTimeMillis();
        totalTime += endTime - startTime;

        System.out.println("Constructed a van Emde Boas tree in " +
                (endTime - startTime) + " milliseconds.");

        // put().
        startTime = System.currentTimeMillis();

        for (Integer i : testArray) {
            map.put(i, i);
        }

        endTime = System.currentTimeMillis();
        totalTime += endTime - startTime;

        System.out.println(
                "put() in " + (endTime - startTime) + " milliseconds.");

        // Key iteration.
        startTime = System.currentTimeMillis();
        KeyIterator keyIterator = map.tableKeyIterator();

        while (keyIterator.hasNextKey()) {
            keyIterator.nextKey();
        }

        endTime = System.currentTimeMillis();
        totalTime += endTime - startTime;

        System.out.println(
                "Key iteration in " + (endTime - startTime) + " milliseconds.");

        // Entry set iteration.
        startTime = System.currentTimeMillis();
        KeyValueMapping<Integer> mapping = new KeyValueMapping<>();
        KeyValueIterator<Integer> keyValueIterator = map.tableKeyValueIterator();

        while (keyValueIterator.hasNextKeyValuePair()) {
            keyValueIterator.nextKeyValuePair(mapping);
        }

        endTime = System.currentTimeMillis();
        totalTime += endTime - startTime;

        System.out.println(
                "Key/value iteration in " + (endTime - startTime) +
                " milliseconds.");

        // get().
        startTime = System.currentTimeMillis();

        for (Integer i : testArray) {
            map.get(i);
        }

        endTime = System.currentTimeMillis();
        totalTime += endTime - startTime;

        System.out.println(
                "get() in " + (endTime - startTime) + " milliseconds.");

        // containsKey().
        startTime = System.currentTimeMillis();

        for (Integer i : testArray) {
            map.containsKey(i);
        }

        endTime = System.currentTimeMillis();
        totalTime += endTime - startTime;

        System.out.println(
                "contains() in " + (endTime - startTime) + " milliseconds.");

        // remove().
        startTime = System.currentTimeMillis();

        for (Integer i : testArray) {
            map.remove(i);
        }

        endTime = System.currentTimeMillis();
        totalTime += endTime - startTime;

        System.out.println(
                "remove() in " + (endTime - startTime) + " milliseconds.");
        System.out.println("Total time: " + totalTime + " milliseconds.");
    }

    private static void benchmarkMap(Map<Integer, Integer> map,
                                     Integer[] testArray) {
        System.out.println("--- " + map.getClass().getSimpleName() + " ---");

        long startTime;
        long endTime;
        long totalTime = 0L;

        // put().
        startTime = System.currentTimeMillis();

        for (Integer i : testArray) {
            map.put(i, i);
        }

        endTime = System.currentTimeMillis();
        totalTime += endTime - startTime;

        System.out.println(
                "put() in " + (endTime - startTime) + " milliseconds.");

        // Key iteration.
        startTime = System.currentTimeMillis();

        for (Integer i : map.keySet()) {

        }

        endTime = System.currentTimeMillis();
        totalTime += endTime - startTime;

        System.out.println(
                "keySet().iterator() in " + (endTime - startTime) +
                " milliseconds.");

        // Entry set iteration.
        startTime = System.currentTimeMillis();

        for (Map.Entry<Integer, Integer> e : map.entrySet()) {

        }

        endTime = System.currentTimeMillis();
        totalTime += endTime - startTime;

        System.out.println(
                "entrySet().iterator() in " + (endTime - startTime) +
                " milliseconds.");

        // get().
        startTime = System.currentTimeMillis();

        for (Integer i : testArray) {
            map.get(i);
        }

        endTime = System.currentTimeMillis();
        totalTime += endTime - startTime;

        System.out.println(
                "get() in " + (endTime - startTime) + " milliseconds.");

        // containsKey().
        startTime = System.currentTimeMillis();

        for (int i = MINIMUM_KEY; i <= MAXIMUM_KEY; ++i) {
            map.containsKey(i);
        }

        endTime = System.currentTimeMillis();
        totalTime += endTime - startTime;

        System.out.println(
                "containsKey() in " + (endTime - startTime) + " milliseconds.");

        // remove().
        startTime = System.currentTimeMillis();

        for (Integer i : testArray) {
            map.remove(i);
        }

        endTime = System.currentTimeMillis();
        totalTime += endTime - startTime;

        System.out.println(
                "remove() in " + (endTime - startTime) + " milliseconds.");
        System.out.println("Total time: " + totalTime + " milliseconds.");
    }

    private static void warmup() {
        System.out.println("Warming up...");
        VanEmdeBoasTreeIntMap<Integer> vebMap =
                new VanEmdeBoasTreeIntMap<>(MINIMUM_KEY, MAXIMUM_KEY);

        Map<Integer, Integer> treeMap = new TreeMap<>();
        Map<Integer, Integer> hashMap = new HashMap<>();

        Integer[] randomIntegerArray =
                createRandomIntegerArray(INTEGER_ARRAY_LENGTH,
                                         MINIMUM_KEY,
                                         MAXIMUM_KEY);

        for (Integer i : randomIntegerArray) {
            vebMap.put(i, i);
            treeMap.put(i, i);
            hashMap.put(i, i);
        }

        for (Integer i : randomIntegerArray) {
            vebMap.containsKey(i);
            treeMap.containsKey(i);
            hashMap.containsKey(i);
        }

        for (Map.Entry<Integer, Integer> e : treeMap.entrySet()) {

        }

        for (Integer i : treeMap.keySet()) {

        }

        for (Map.Entry<Integer, Integer> e : hashMap.entrySet()) {

        }

        for (Integer i : hashMap.keySet()) {

        }

        KeyIterator keyIterator = vebMap.treeKeyIterator();

        while (keyIterator.hasNextKey()) {
            keyIterator.nextKey();
        }

        keyIterator = vebMap.tableKeyIterator();

        while (keyIterator.hasNextKey()) {
            keyIterator.nextKey();
        }

        KeyValueMapping<Integer> mapping = new KeyValueMapping<>();
        KeyValueIterator<Integer> keyValueIterator =
                vebMap.treeKeyValueIterator();

        while (keyValueIterator.hasNextKeyValuePair()) {
            keyValueIterator.nextKeyValuePair(mapping);
        }

        keyValueIterator =
                vebMap.tableKeyValueIterator();

        while (keyValueIterator.hasNextKeyValuePair()) {
            keyValueIterator.nextKeyValuePair(mapping);
        }

        for (Integer i : randomIntegerArray) {
            vebMap.remove(i);
            treeMap.remove(i);
            hashMap.remove(i);
        }

        System.out.println("Warming up done!");
    }

    private static Integer[] createRandomIntegerArray(int length,
                                                      int minimumKey,
                                                      int maximumKey) {
        Integer[] array = new Integer[length];
        int rangeLength = maximumKey - minimumKey + 1;

        for (int i = 0; i < length; ++i) {
            array[i] = RANDOM.nextInt(rangeLength) + minimumKey;
        }

        return array;
    }
}

Seed = 1513196888667
Warming up...
Warming up done!

--- TreeMap ---
put() in 2222 milliseconds.
keySet().iterator() in 166 milliseconds.
entrySet().iterator() in 160 milliseconds.
get() in 2148 milliseconds.
containsKey() in 424 milliseconds.
remove() in 2131 milliseconds.
Total time: 7251 milliseconds.

--- HashMap ---
put() in 563 milliseconds.
keySet().iterator() in 160 milliseconds.
entrySet().iterator() in 114 milliseconds.
get() in 169 milliseconds.
containsKey() in 190 milliseconds.
remove() in 118 milliseconds.
Total time: 1314 milliseconds.

--- VanEmdeBoasTreeIntMap ---
Constructed a van Emde Boas tree in 1698 milliseconds.
put() in 754 milliseconds.
Key iteration in 32 milliseconds.
Key/value iteration in 32 milliseconds.
get() in 40 milliseconds.
contains() in 39 milliseconds.
remove() in 804 milliseconds.
Total time: 3399 milliseconds.