public
Created

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.

  • Download Gist
SkipListNode.java
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
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
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241
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
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232
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");
}
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.