SkipListNode.java

package org.rivendell.collections;

import java.lang.reflect.Array;

public class SkipListNode<T extends Comparable<? super T>> {

    private final T value;
    private final SkipListNode<T>[] next;
    /**
     * this is to provide index based access
     */
    private final int[] length;

    @SuppressWarnings("unchecked")
    public SkipListNode(T value, int height) {
        this.value = value;
        next = (SkipListNode<T>[]) Array.newInstance(SkipListNode.class, height);
        length = new int[height];
        for (int i = 0; i < height; i++) {
            length[i] = 0;
        }
    }

    public int getHeight() {
        return next.length;
    }

    public SkipListNode<T> getNextNode(int height) {
        return next[height];
    }

    public void setNextNode(int height, SkipListNode<T> nextNode) {
        next[height] = nextNode;
    }

    public int getLength(int height) {
        return length[height];
    }

    public void setLength(int height, int newLength) {
        length[height] = newLength;
    }

    public T getValue() {
        return value;
    }

}

SkiplistSet.java

package org.rivendell.collections;

import java.util.Random;

/**
 * supports add, remove, and also index based access. the reason to provide
 * index based access is so that it is suitable to be used as a TableModel
 * for JTable
 * 
 * @author dmx
 *
 * @param <T>
 */
public class SkiplistSet<T extends Comparable<? super T>> {

    private static final int MAX_HEIGHT = 32;
    private int randomSeed;

    private final SkipListNode<T> sentinel;
    private int existingHeight = 1;
    private int count = 0;

    //need to do more cost study to see whether it is worth
    //internal used to speed up add/remove etc.
    private int[] _length = new int[MAX_HEIGHT];
    @SuppressWarnings("unchecked")
    private SkipListNode<T>[] _updates = new SkipListNode[MAX_HEIGHT];

    public SkiplistSet() {
        sentinel = new SkipListNode<T>(null, MAX_HEIGHT);
        count = 0;
        randomSeed = new Random(System.currentTimeMillis()).nextInt()
                | 0x0100;
    }

    public void printDebug() {
        for (int i = existingHeight - 1; i >= 0; i--) {
            StringBuilder sb = new StringBuilder();
            sb.append(i + ":");
            SkipListNode<T> current = sentinel;
            //sb.append("[sentinel, L" + sentinel.getLength(i) + "]").append("->");
            //current = sentinel.getNextNode(i);
            while (current != null) {
                sb.append("[V").append(current.getValue() == null ? "sentinel" : current.getValue()).append(", L" + current.getLength(i) + "]").append("->");
                current = current.getNextNode(i);
            }
            sb.append("end");
            System.out.println(sb);
        }
    }

    public boolean contains(T value) {
        SkipListNode<T> current = sentinel;
        for (int i = existingHeight - 1; i >= 0; i--) {
            while (current.getNextNode(i) != null && current.getNextNode(i).getValue().compareTo(value) < 0) {
                current = current.getNextNode(i);
            }
        }
        current = current.getNextNode(0);
        return current != null && current.getValue().equals(value);
    }

    public T get(int index) {
        SkipListNode<T> current = findPrecedentNode(index);
        current = current.getNextNode(0);
        return current.getValue();
    }

    private SkipListNode<T> findPrecedentNode(int index) {
        SkipListNode<T> current = sentinel;
        int length = -1;
        for (int i = existingHeight - 1; i >= 0; i--) {
            while (current.getNextNode(i) != null && length + current.getLength(i) < index) {
                length += current.getLength(i);
                current = current.getNextNode(i);
            }
            _updates[i] = current;
        }
        return current;
    }

    public T remove(int index) {
        SkipListNode<T> current = findPrecedentNode(index);
        current = current.getNextNode(0);
        updateNodeAfterRemoval(current);
        updateExistingHeightAfterRemoval();
        T retValue = current.getValue();
        count--;
        return retValue;
    }

    public boolean remove(T value) {
        SkipListNode<T> current = findPrecedentNode(value);
        current = current.getNextNode(0);
        if (current != null && value.equals(current.getValue())) {
            updateNodeAfterRemoval(current);
            updateExistingHeightAfterRemoval();
            count--;
            return true;
        }
        else {
            return false;
        }
    }

    private SkipListNode<T> findPrecedentNode(T value) {
        SkipListNode<T> current = sentinel;
        for (int i = existingHeight - 1; i >= 0; i--) {
            while (current.getNextNode(i) != null && current.getNextNode(i).getValue().compareTo(value) < 0) {
                current = current.getNextNode(i);
            }
            _updates[i] = current;
        }
        return current;
    }

    private void updateExistingHeightAfterRemoval() {
        while (existingHeight > 1 && sentinel.getNextNode(existingHeight - 1) == null) {
            existingHeight--;
        }
    }

    private void updateNodeAfterRemoval(SkipListNode<T> current) {
        for (int i = 0; i < existingHeight; i++) {
            if (_updates[i].getNextNode(i) == current) {
                _updates[i].setNextNode(i, current.getNextNode(i));
                if (current.getNextNode(i) == null) {
                    _updates[i].setLength(i, 0);
                }
                else {
                    _updates[i].setLength(i, _updates[i].getLength(i) + current.getLength(i)-1);
                }
            }
            else {
                if (_updates[i].getNextNode(i) != null) {
                    _updates[i].setLength(i, _updates[i].getLength(i)-1);
                }
            }
        }
    }

    public boolean add(T value) {
        SkipListNode<T> current = sentinel;
        findPrecendentNodeForAdd(value, current);
        current = current.getNextNode(0);
        
        if (current == null || !value.equals(current.getValue())) {
            int newHeight = updateNodeAfterAdd(value);
            updateAddintionalLength(newHeight);
            count++;
            return true;
        }
        else {
            return false;
        }
    }

    private void updateAddintionalLength(int newHeight) {
        for (int i = newHeight; i < existingHeight; i++) {
            if (_updates[i] != null) {
                _updates[i].setLength(i, _updates[i].getLength(i) + 1);
                //System.out.println("on height " + i + " update: " + length[0] + " - " + length[i]);
            }
        }
    }

    private int updateNodeAfterAdd(T value) {
        SkipListNode<T> current;
        int newHeight = randomHeight();
        _length[0]++;
        //System.out.println("newHeight is " + newHeight + ", new length is " + length[0] + " for value " + value);
        if (newHeight > existingHeight) {
            for (int i = existingHeight; i < newHeight; i++) {
                _updates[i] = sentinel;
                _length[i] = 0;
            }
            existingHeight = newHeight;
        }
        current = new SkipListNode<T>(value, newHeight);
        for (int i = 0; i < newHeight; i++) {
            current.setNextNode(i, _updates[i].getNextNode(i));
            if (i == 0) {
                current.setLength(i, _updates[i].getLength(i));
                _updates[i].setLength(i, 1);
            }
            else {
                int nextNodeTotalLength = 0;
                if (_updates[i].getNextNode(i) == null) {
                    nextNodeTotalLength = _length[0];
                }
                else {
                    nextNodeTotalLength = _length[i] + _updates[i].getLength(i) + 1;
                }
                //System.out.println("on height " + i + " set new: " + nextNodeTotalLength + " - " + length[0]);
                current.setLength(i, nextNodeTotalLength - _length[0]);
                //System.out.println("on height " + i + " set old: " + length[0] + " - " + length[i]);
                _updates[i].setLength(i, _length[0] - _length[i]);
            }
            _updates[i].setNextNode(i, current);
        }
        return newHeight;
    }

    private void findPrecendentNodeForAdd(T value, SkipListNode<T> current) {
        for (int i = existingHeight - 1; i >= 0; i--) {
            if (i == (existingHeight-1)) {
                _length[i] = 0;
            }
            else {
                _length[i] = _length[i+1];
            }
            while (current.getNextNode(i) != null && (current.getNextNode(i).getValue().compareTo(value) < 0)) {
                _length[i] += current.getLength(i);
                current = current.getNextNode(i);
            }
            _updates[i] = current;
        }
    }

    public int size() {
        return count;
    }

    //this random function is super important, a good random function would spread the 
    //height out. 
    private int randomHeight() {
        int x = randomSeed;
        x ^= x << 13;
        x ^= x >>> 17;
        randomSeed = x ^= x << 5;
        if ((x & 0x8001) != 0) {
            return 1;
        }
        int level = 1;
        while (((x >>>= 1) & 1) != 0) {
            ++level;
        }
        return level + 1;
    }

}

SkiplistSetTest.java

package org.rivendell.collections;

import static org.fest.assertions.Assertions.assertThat;

import java.util.Random;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;
import java.util.concurrent.ConcurrentSkipListSet;

import org.junit.Test;
import org.junit.runner.RunWith;
import org.powermock.modules.junit4.PowerMockRunner;

@RunWith(PowerMockRunner.class)
public class SkiplistSetTest {

    @Test
    public void test_simple_remove() throws Exception {
        SkiplistSet<Integer> skiplistSet = new SkiplistSet<Integer>();

        SortedSet<Integer> sortedSet = new TreeSet<Integer>();
        for (int i = 0; i <= 5000; i++) {
            int toAdd = i;
            sortedSet.add(toAdd);
            skiplistSet.add(toAdd);
        }
        skiplistSet.printDebug();
        for(int i = 3000; i >= 0; i--) {
            int toRemove = i;
            Integer value = skiplistSet.remove(toRemove);
            assertThat(value).isEqualTo(toRemove);
            sortedSet.remove(value);
            if (i % 200 == 0) {
                int index = 0;            
                for (int check : sortedSet) {
                    assertThat(skiplistSet.get(index)).isEqualTo(check);
                    index++;
                }
            }
        }
    }

    @Test
    public void test_simple_add() throws Exception {
        SkiplistSet<Integer> skiplistSet = new SkiplistSet<Integer>();

        SortedSet<Integer> sortedSet = new TreeSet<Integer>();
        for (int i = 0; i <= 50000; i++) {
            int toAdd = i;
            sortedSet.add(toAdd);
            skiplistSet.add(toAdd);
        }

        int index = 0;
        for (int check : sortedSet) {
            assertThat(skiplistSet.get(index)).isEqualTo(check);
            index++;
        }
    }

    @Test
    public void test_simple_reverse_add() throws Exception {
        SkiplistSet<Integer> skiplistSet = new SkiplistSet<Integer>();

        SortedSet<Integer> sortedSet = new TreeSet<Integer>();
        for (int i = 50000; i >= 0; i--) {
            int toAdd = i;
            sortedSet.add(toAdd);
            skiplistSet.add(toAdd);
            //skiplistSet.printDebug();
        }

        //skiplistSet.printDebug();
        int index = 0;
        for (int check : sortedSet) {
            assertThat(skiplistSet.get(index)).isEqualTo(check);
            index++;
        }
    }

    @Test
    public void test_simple_mix_add() throws Exception {
        SkiplistSet<Integer> skiplistSet = new SkiplistSet<Integer>();

        Random random = new Random(System.currentTimeMillis());
        SortedSet<Integer> sortedSet = new TreeSet<Integer>();
        for (int i = 500; i >= 0; i--) {
            int toAdd = random.nextInt();
            sortedSet.add(toAdd);
            skiplistSet.add(toAdd);
            //skiplistSet.printDebug();
        }

        skiplistSet.printDebug();
        int index = 0;
        for (int check : sortedSet) {
            assertThat(skiplistSet.get(index)).isEqualTo(check);
            index++;
        }
    }

    //@Test
    public void test_random_add_and_remove() throws Exception {
        Random random = new Random(System.currentTimeMillis());

        Set<Integer> goodSet = new TreeSet<Integer>();
        SkiplistSet<Integer> skiplistSet = new SkiplistSet<Integer>();

        for (int i = 0; i < 700000; i++) {
            int toAdd = random.nextInt() % 90001;
            boolean added = goodSet.add(toAdd);
            boolean skipListAdded = skiplistSet.add(toAdd);
            assertThat(skipListAdded).isEqualTo(added);
            assertThat(skiplistSet.size()).isEqualTo(goodSet.size());
        }

        //set.printDebug();

        for (Integer i : goodSet) {
            assertThat(skiplistSet.contains(i)).isTrue();
        }
        {
            int index = 0;
            for (int check : goodSet) {
                assertThat(skiplistSet.get(index)).isEqualTo(check);
                index++;
            }
        }

        for (int i = 0; i < 400000; i++) {
            int toRemove = random.nextInt() % 30001;
            boolean removed = goodSet.remove(toRemove);
            boolean skipListRemoved = skiplistSet.remove((Integer) toRemove);
            assertThat(skipListRemoved).isEqualTo(removed);
            assertThat(skiplistSet.size()).isEqualTo(goodSet.size());
            assertThat(skiplistSet.contains(toRemove)).isFalse();
            if (i % 1000 == 0) {
                {
                    int index = 0;
                    for (int check : goodSet) {
                        assertThat(skiplistSet.get(index)).isEqualTo(check);
                        index++;
                    }
                }
            }
        }

        assertThat(skiplistSet.size()).isEqualTo(goodSet.size());
        {
            int index = 0;
            for (int check : goodSet) {
                assertThat(skiplistSet.get(index)).isEqualTo(check);
                index++;
            }
        }
        assertThat(skiplistSet.size()).isEqualTo(goodSet.size());
        for (Integer i : goodSet) {
            assertThat(skiplistSet.contains(i)).isTrue();
        }
        assertThat(skiplistSet.size()).isEqualTo(goodSet.size());
        for (int i = 0; i < 500000; i++) {
            assertThat(skiplistSet.contains(i)).isEqualTo(goodSet.contains(i));
        }

        assertThat(skiplistSet.size()).isEqualTo(goodSet.size());
        for (int i = 0; i < 500000; i++) {
            int toAdd = random.nextInt() % 90001;
            boolean added = goodSet.add(toAdd);
            boolean skipListAdded = skiplistSet.add(toAdd);
            assertThat(skiplistSet.size()).isEqualTo(goodSet.size());
            assertThat(skipListAdded).isEqualTo(added);
            if (i % 1000 == 0) {
                {
                    assertThat(skiplistSet.size()).isEqualTo(goodSet.size());
                    int index = 0;
                    for (int check : goodSet) {
                        assertThat(skiplistSet.get(index)).isEqualTo(check);
                        index++;
                    }
                }
            }
        }
        assertThat(skiplistSet.size()).isEqualTo(goodSet.size());
        for (Integer i : goodSet) {
            assertThat(skiplistSet.contains(i)).isTrue();
        }
        assertThat(skiplistSet.size()).isEqualTo(goodSet.size());
        for (int i = 0; i < 500000; i++) {
            assertThat(skiplistSet.contains(i)).isEqualTo(goodSet.contains(i));
        }
        {
            assertThat(skiplistSet.size()).isEqualTo(goodSet.size());
            int index = 0;
            for (int check : goodSet) {
                assertThat(skiplistSet.get(index)).isEqualTo(check);
                index++;
            }
        }

    }

    @Test
    public void test_cost() throws Exception {
        //Set<Integer> set = new TreeSet<Integer>();
        //Set<Integer> set = new ConcurrentSkipListSet<Integer>();
        SkiplistSet<Integer> set = new SkiplistSet<Integer>();
        Random random = new Random(System.currentTimeMillis());
        long start = System.currentTimeMillis();
        for (int i = 0; i <= 1000000; i++) {
            int toAdd = i;//random.nextInt() % 700001;
            set.add(toAdd);
        }
        long end = System.currentTimeMillis();
        System.out.println((end - start) + " millis");
    }
    
    @Test
    public void test_reverse_cost() throws Exception {
        //Set<Integer> set = new TreeSet<Integer>();
        //Set<Integer> set = new ConcurrentSkipListSet<Integer>();
        SkiplistSet<Integer> set = new SkiplistSet<Integer>();
        Random random = new Random(System.currentTimeMillis());
        long start = System.currentTimeMillis();
        for (int i = 1000000; i >= 0; i--) {
            int toAdd = i;//random.nextInt() % 700001;
            set.add(toAdd);
        }
        long end = System.currentTimeMillis();
        System.out.println((end - start) + " millis");
    }
}