Skip to content

@dmx2010 /SkipListNode.java
Created

Embed URL

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
A SkiplistSet implementation. It provides add/remove T as well as get/remove index based access. The SkiplistSet can be used as a base for TableModel with index based access.
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;
}
}
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;
}
}
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");
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Something went wrong with that request. Please try again.