1
\$\begingroup\$

Introduction

The following data structure is a dictionary mapping primitive int values to any value type. Basically, under the hood it is a hash table, where a translated key is mapped to an index into that hash table containing a value. We, however, use a van Emde Boas tree algorithm to bring the integer keys into order. Suppose this: we simply keep a table of mappings and the mappings implement a sorted linked list. Here lies a problem: suppose the table has a mapping at the very beginning and a mapping at the very end. If we wish to insert a new mapping somewhere in between, we would have to iterate the table in order to find the predecessor and successor mappings: \$\Theta(n)\$ time in the worst case. With the same van Emde Boas tree, we can do that always in \$\Theta(\log \log n)\$. Also, the aforementioned "translation" means that in order to find a valid index into the internal table, we subtract the given parameter minimum key from the input key thus bringing it to the value no less than zero, which, in turn, gives us an opportunity to input negative keys as well. Furthermore, we keep a special sentinel value using which we can indicate that the value exists but is null. This gives us possibility of answering get()/containsKey() in constant time even if the associated value is null.

Code

VanEmdeBoasTreeIntMap.java

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 + ".");
        }
    }
}

VanEmdeBoasTreeIntMapTest.java

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));
        }
    }
}

Benchmark.java

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;
    }
}

Performance figures

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.

Critique request

Any critique is much appreciated, be it about algorithm, unit testing or benchmarking.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.