public class SkipList<K extends Comparable<K>,V> extends AbstractMap<K,V> {
private int m, size;
private Elem l;
private ArrayList<Elem> p;
private class Elem implements Entry<K, V> {
K key;
V value;
ArrayList<Elem> next;
public Elem(K k, V v) {
key = k;
value = v;
next = new ArrayList<Elem>();
}
public V setValue(V v) {
this.value = v;
return value;
}
public K getKey() {
return key;
}
public V getValue() {
return value;
}
}
public SkipList(int levels) { //InitSkipList(in m, out l)
size = 0;
m = levels;
l = new Elem(null, null);
int i=0;
while(i<m) {
(l.next).add(i,null);
i++;
}
this.p = new ArrayList<Elem>();
}
public Elem MapEmpty(Elem l)//Map_Empty
{
l.next.set(0,null);
return l.next.get(0);
}
public Elem succ(Elem x) //succ
{
return x.next.get(0);
}
public ArrayList<Elem> skip(K key){ //skip
int i=0, j=0;
Elem x=l;
i=m-1;
while(i>=0){
while(x.next.get(i)!=null && x.next.get(i).key.compareTo(key) < 0)
{
x=x.next.get(i);
}
p.add(j++,x);
i--;
}
return p;
}
public V put(K key, V value){ //insert
int i=0;
p=skip(key);
//if...panic
Elem x=new Elem(key,value);
while(i<m){
(x.next).add(null);
i++;
}
int r=((int)Math.random()*1000000)*2;
i=0;
while (i<m && r%2==0){
x.next.set(i,p.get(i).next.get(i));
p.get(i).next.set(i, x);
i++;
r=r/2;
}
while(i<m){
x.next.set(i, null);
size++;
}
return null;
}
public V get(K key) {
p=skip(key);
Elem x=succ(p.get(0));
if(x != null && x.key.equals(key)){
return x.value;
}
else{
return null;
}
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public Set<Entry<K, V>> entrySet() {
return new MyEntrySet();
}
private class MyEntrySet extends AbstractSet{
public Iterator<SkipList<K, V>> iterator(){
return new Iterator1();
}
private class Iterator1 implements Iterator{
private Elem i = l;
@Override
public boolean hasNext() {
return i.next.get(0) != null;
}
@Override
public Elem next() {
i = i.next.get(0);
return i;
}
@Override
public void remove(){
SkipList.this.remove(i.getKey());
}
}
@Override
public int size() {
return size;
}
}
}