1
\$\begingroup\$

VanEmdeBoasTreeIntegerSet.java

package net.coderodde.util;

import java.util.Collection;
import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.SortedSet;
import java.util.Spliterator;

/**
 * This class implements a {@link java.util.SortedSet} over
 * {@link java.lang.Integer} keys via van Emde Boas tree.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 8, 2017)
 */
public final class VanEmdeBoasTreeIntegerSet implements SortedSet<Integer> {

    /**
     * The minimum universe size.
     */
    private static final int MINIMUM_UNIVERSE_SIZE = 2;

    /**
     * Implements a single node of the recursive tree.
     */
    private static final class VanEmdeBoasTree {

        /**
         * The universe size of this van Emde Boas tree.
         */
        private final int universeSize;

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

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

        /**
         * The minimum integer key in this tree.
         */
        private Integer min;

        /**
         * The maximum integer key in this tree.
         */
        private Integer max;

        /**
         * The summary van Emde Boas tree.
         */
        private final VanEmdeBoasTree summary;

        /**
         * The children van Emde Boas trees of this tree.
         */
        private final VanEmdeBoasTree[] cluster;

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

            int universeSizeLowerSquare = lowerSquare(universeSize);

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

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

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

        int getUniverseSize() {
            return universeSize;
        }

        Integer getMinimumKey() {
            return min;
        }

        Integer getMaximumKey() {
            return max;
        }

        Integer getSuccessor(Integer x) {
            if (universeSize == 2) {
                if (x == 0 && max == 1) {
                    return 1;
                }

                return null;
            }

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

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

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

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

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

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

        Integer getPredecessor(Integer x) {
            if (universeSize == 2) {
                if (min == null) {
                    return null;
                }

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

                return null;
            }

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

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

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

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

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

                return null;
            }

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

        void treeInsert(Integer x) {
            if (min == null) {
                emptyTreeInsert(x);
                return;
            }

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

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

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

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

        void treeDelete(Integer x) {
            if (min.equals(max)) {
                min = null;
                max = null;
                return;
            }

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

                max = min;
                return;
            }

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

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

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

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

                    if (summaryMaximum == null) {
                        max = min;
                    } else {
                        Integer maximumKey = 
                                cluster[summaryMaximum].getMaximumKey();

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

        boolean contains(Integer x) {
            if (x.equals(min) || x.equals(max)) {
                return true;
            } else if (universeSize == 2) {
                return false;
            } else {
                return cluster[high(x)].contains(low(x));
            }
        }

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

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

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

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

    /**
     * The root of the tree.
     */
    private VanEmdeBoasTree root;

    /**
     * The number of elements in this integer set.
     */
    private int size;

    public VanEmdeBoasTreeIntegerSet(int requestedUniverseSize) {
        checkRequestedUniverseSize(requestedUniverseSize);
        requestedUniverseSize = fixUniverseSize(requestedUniverseSize);
        root = new VanEmdeBoasTree(requestedUniverseSize);
    }

    @Override
    public Integer first() {
        checkNotEmpty();
        return root.getMinimumKey();
    }

    @Override
    public Integer last() {
        checkNotEmpty();
        return root.getMaximumKey();
    }

    @Override
    public int size() {
        return size;
    }

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

    @Override
    public boolean contains(Object o) {
        if (o == null) {
            return false;
        }

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

        Integer other = (Integer) o;
        return root.contains(other);
    }

    @Override
    public Iterator<Integer> iterator() {
        throw new UnsupportedOperationException("Not supported yet."); //To change body of generated methods, choose Tools | Templates.
    }

    @Override
    public boolean add(Integer o) {
        if (!root.contains(o)) {
            root.treeInsert(o);
            return true;
        } else {
            return false;
        }
    }

    @Override
    public boolean remove(Object o) {
        if (root.contains((Integer) o)) {
            root.treeDelete((Integer) o);
            return true;
        } else {
            return false;
        }
    }

    @Override
    public void clear() {

    }

    @Override
    public Comparator<? super Integer> comparator() {
        throw new UnsupportedOperationException(
                "This SortedSet does not use a comparator.");
    }

    @Override
    public SortedSet<Integer> subSet(Integer fromElement, Integer toElement) {
        throw new UnsupportedOperationException("Not implemented.");
    }

    @Override
    public SortedSet<Integer> headSet(Integer toElement) {
        throw new UnsupportedOperationException("Not implemented.");
    }

    @Override
    public SortedSet<Integer> tailSet(Integer fromElement) {
        throw new UnsupportedOperationException("Not implemented."); 
    }

    @Override
    public Spliterator<Integer> spliterator() {
        throw new UnsupportedOperationException("Not implemented.");
    }

    @Override
    public Object[] toArray() {
        throw new UnsupportedOperationException("Not implemented."); 
    }

    @Override
    public <T> T[] toArray(T[] a) {
        throw new UnsupportedOperationException("Not implemented.");
    }

    @Override
    public boolean containsAll(Collection<?> c) {
        throw new UnsupportedOperationException("Not implemented.");
    }

    @Override
    public boolean addAll(Collection<? extends Integer> c) {
        throw new UnsupportedOperationException("Not implemented.");
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        throw new UnsupportedOperationException("Not implemented.");
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        throw new UnsupportedOperationException("Not implemented.");
    }

    private void checkNotEmpty() {
        if (size == 0) {
            throw new NoSuchElementException("The tree is empty.");
        }
    }

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

    private void checkRequestedUniverseSize(int requestedUniverseSize) {
        if (requestedUniverseSize < MINIMUM_UNIVERSE_SIZE) {
            throw new IllegalArgumentException(
                    "Universe size too small: " + requestedUniverseSize);
        }
    }

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

Benchmark.java

package net.coderodde.util;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Random;
import java.util.SortedSet;
import java.util.TreeSet;

/**
 * This class implements a benchmark comparing a {@code TreeSet<Integer>}
 * against a {@code VanEmdeBoasTreeIntegerSet}.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Dec 8, 2017)
 */
public final class Benchmark {

    private static final int UNIVERSE_SIZE = 2_000_000;
    private static Random random;

    public static void main(String[] args) {
        long seed = System.currentTimeMillis();
        random = new Random(seed);
        System.out.println("Seed = " + seed);

        List<Integer> insertList = generateData();
        List<Integer> deleteList = generateData();

        warmup(insertList, deleteList);
        benchmark(insertList, deleteList);
    }

    private static List<Integer> generateData() {
        List<Integer> data = new ArrayList<>(UNIVERSE_SIZE);

        for (int i = 0; i < UNIVERSE_SIZE; ++i) {
            data.add(i);
        }

        Collections.shuffle(data, random);
        return data;
    }

    private static void warmup(List<Integer> insertList,
                               List<Integer> deleteList) {
        System.out.println("Warming up...");
        warmupVEBTree(insertList, deleteList);
        warmupTreeSet(insertList, deleteList);
        System.out.println("Warming up done!");
        System.out.println();
    }

    private static void warmupVEBTree(List<Integer> insertList,
                                      List<Integer> deleteList) {
        VanEmdeBoasTreeIntegerSet set =
                new VanEmdeBoasTreeIntegerSet(UNIVERSE_SIZE);

        warmup(set, insertList, deleteList);
    }

    private static void warmupTreeSet(List<Integer> insertList,
                                      List<Integer> deleteList) {
        TreeSet<Integer> set = new TreeSet<>();

        warmup(set, insertList, deleteList);
    }

    private static void warmup(SortedSet<Integer> set,
                               List<Integer> insertList,
                               List<Integer> deleteList) {
        execute(set, insertList, deleteList, false);
    }

    private static void benchmark(List<Integer> insertList,
                                  List<Integer> deleteList) {
        System.out.println("Benchmarking " +
                VanEmdeBoasTreeIntegerSet.class.getSimpleName());

        benchmarkVEBTree(insertList, deleteList);

        System.out.println();
        System.out.println("Benchmarking " + TreeSet.class.getSimpleName());
        benchmarkTreeSet(insertList, deleteList);
        System.out.println();
    }

    private static void benchmarkVEBTree(List<Integer> insertList,
                                         List<Integer> deleteList) {
        long start = System.currentTimeMillis();

        VanEmdeBoasTreeIntegerSet set =
                new VanEmdeBoasTreeIntegerSet(UNIVERSE_SIZE);

        long end = System.currentTimeMillis();
        long totalTime = end - start;

        System.out.println("VanEmdeBoasTreeIntegerSet() in " + 
                           (end - start) + " ms.");

        totalTime += execute(set, insertList, deleteList, true);

        System.out.println("Total time: " + totalTime + " ms.");
    }

    private static void benchmarkTreeSet(List<Integer> insertList,
                                         List<Integer> deleteList) {
        long start = System.currentTimeMillis();

        TreeSet<Integer> set = new TreeSet();

        long end = System.currentTimeMillis();
        long totalTime = end - start;

        System.out.println("TreeSet() in " + (end - start) + " ms.");

        totalTime += execute(set, insertList, deleteList, true);

        System.out.println("Total time: " + totalTime + " ms.");
    }

    private static long execute(SortedSet<Integer> set,
                                List<Integer> insertList,
                                List<Integer> deleteList,
                                boolean output) {
        long start = System.currentTimeMillis();

        for (Integer i : insertList) {
            set.add(i);
        }

        long end = System.currentTimeMillis();
        long totalTime = end - start;

        if (output) {
            System.out.println(
                    set.getClass().getSimpleName() + ".add() in " +
                    (end - start) + " ms.");
        }

        start = System.currentTimeMillis();

        for (Integer i : deleteList) {
            set.remove(i);
        }

        end = System.currentTimeMillis();
        totalTime += end - start;

        if (output) {
            System.out.println(
                    set.getClass().getSimpleName() + ".remove() in " +
                    (end - start) + " ms.");
        }

        return totalTime;
    }
}

Output

Seed = 1512764868028
Warming up...
Warming up done!

Benchmarking VanEmdeBoasTreeIntegerSet
VanEmdeBoasTreeIntegerSet() in 1822 ms.
VanEmdeBoasTreeIntegerSet.add() in 2255 ms.
VanEmdeBoasTreeIntegerSet.remove() in 2304 ms.
Total time: 6381 ms.

Benchmarking TreeSet
TreeSet() in 0 ms.
TreeSet.add() in 4129 ms.
TreeSet.remove() in 4605 ms.
Total time: 8734 ms.

As always, any critique is welcome.

\$\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.