SkipList

  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
import java.lang.Object;
import java.lang.Override;
import java.lang.reflect.Array;
import java.util.AbstractMap;
import java.util.AbstractSet;
import java.util.Collection;
import java.util.Iterator;
import java.util.Map;
import java.util.Random;
import java.util.Set;
/**
* Created by sher on 01.04.15.
*/
class SkipList<K extends Comparable<K>, V> extends AbstractMap<K,V> {
private class MyList implements Map.Entry<K,V> {
private final MyList[] elem;
private K key;
private V value;
MyList(K k, V v, int n) {
key = k; value = v;
elem = (MyList[]) Array.newInstance(new MyList().getClass(), n); // не знаю, что это за магия нагуглил
}
MyList() {elem = null; }
@Override
public K getKey() { return key; }
@Override
public V getValue() { return value; }
public MyList[] getNext() { return elem; }
@Override
public V setValue(V v) { return this.value = v; }
}
private MyList[] skip(K k) {
MyList[] BigMrList = (MyList[]) Array.newInstance(new MyList().getClass(), levels);
MyList MsList = MrList;
for(int i = levels - 1; i >= 0; i--) {
while (MsList.getNext()[i] != null && MsList.getNext()[i].getKey().compareTo((K) k) < 0) {
MsList = MsList.getNext()[i];
}
BigMrList[i] = MsList;
}
return BigMrList;
}
public V get(Object k){
MyList p = skip((K) k)[0].getNext()[0];
if (p != null && p.getKey().equals((K) k)) return p.getValue() ;
return null;
}
@Override
public V put(K k, V v) {
MyList[] MsList = skip(k);
MyList x = new MyList(k, v, levels);
V res = get(k);
int mrrandom = myrandom.nextInt()*2, i = 0;
for(; i < levels && mrrandom % 2 == 0; i++, mrrandom /= 2) {
x.getNext()[i] = MsList[i].getNext()[i];
MsList[i].getNext()[i] = x;
}
if (res == null) size++;
return res;
}
public boolean containsKey(Object k) { return get(k) == null? false : true; }
@Override
public V remove(Object k) {
MyList[] p = skip((K) k);
MyList MsList = p[0].getNext()[0];
V value;
int i = 0;
if(MsList == null || MsList.getKey().compareTo((K) k) != 0 )
return null;
value = MsList.getValue();
while(i < levels && p[i].getNext()[i] == MsList) {
p[i].getNext()[i] = MsList.getNext()[i];
i++;
}
size--;
return value;
}
public void putAll(Map<? extends K, ? extends V> m) {
for(Entry<? extends K, ? extends V> a : m.entrySet())
put(a.getKey(), a.getValue());
}
public class MySet extends AbstractSet<Map.Entry<K, V>> {
class MyIter implements Iterator<Map.Entry<K, V>> {
MyList Mlist;
MyIter() { Mlist = MrList; }
@Override
public boolean hasNext() { return Mlist.getNext()[0] != null; }
@Override
public MyList next() {
return Mlist = Mlist.getNext()[0];
}
@Override
public void remove() { SkipList.this.remove((K) Mlist.getKey()); }
}
MySet() {}
@Override
public int size() { return SkipList.this.size(); }
@Override
public Iterator<Entry<K, V>> iterator() { return new MyIter(); }
}
public int size() { return size; }
public Set<Entry<K, V>> entrySet() { return new MySet(); }
@Override
public void clear() {
size = 0;
MyList p = MrList;
for(int i = 0; i < levels;p.getNext()[i] = null, i++) {}
}
private MyList MrList;
private Random myrandom;
private int size, levels;
SkipList(int levels) {
MrList = new MyList(null, null, levels);
size = 0;
myrandom = new Random();
this.levels = levels;
}
}