|
1
29 package net.metanotion.util.skiplist;
30
31 public class SkipSpan {
32 public int nKeys = 0;
33 public Comparable  [] keys;
34 public Object [] vals;
35 public SkipSpan next, prev;
36
37 public SkipSpan newInstance(SkipList sl) { return new SkipSpan(keys.length); }
38 public void killInstance() { }
39 public void flush() { }
40
41 protected SkipSpan() { }
42 public SkipSpan(int size) {
43 keys = new Comparable [size];
44 vals = new Object [size];
45 }
46
47 public void print() {
48 System.out.println("Span");
49 for(int i=0;i<nKeys;i++) {
50 System.out.println("\t" + keys[i] + " => " + vals[i]);
51 }
52 if(next != null) { next.print(); }
53 }
54
55 private int binarySearch(Comparable key) {
56 int high = nKeys - 1;
57 int low = 0;
58 int cur;
59 int cmp;
60 while(low <= high) {
61 cur = (low + high) >>> 1;
62 cmp = keys[cur].compareTo(key);
63 if(cmp > 0) {
64 high = cur - 1;
65 } else if(cmp < 0) {
66 low = cur + 1;
67 } else {
68 return cur;
69 }
70 }
71 return (-1 * (low + 1));
72 }
73
74 public SkipSpan getEnd() {
75 if(next == null) { return this; }
76 return next.getEnd();
77 }
78
79 public SkipSpan getSpan(Comparable key, int[] search) {
80 if(nKeys == 0) {
81 search[0] = -1;
82 return this;
83 }
84
85 if(keys[nKeys - 1].compareTo(key) < 0) {
86 if(next == null) {
87 search[0] = (-1 * (nKeys - 1)) - 1;
88 return this;
89 }
90 return next.getSpan(key, search);
91 }
92 search[0] = binarySearch(key);
93 return this;
94 }
95
96 public Object get(Comparable key) {
97 if(nKeys == 0) { return null; }
98 if(keys[nKeys - 1].compareTo(key) < 0) {
99 if(next == null) { return null; }
100 return next.get(key);
101 }
102 int loc = binarySearch(key);
103 if(loc < 0) { return null; }
104 return vals[loc];
105 }
106
107 private void pushTogether(int hole) {
108 for(int i=hole;i<(nKeys - 1);i++) {
109 keys[i] = keys[i+1];
110 vals[i] = vals[i+1];
111 }
112 nKeys--;
113 }
114
115 private void pushApart(int start) {
116 for(int i=(nKeys-1);i>=start;i--) {
117 keys[i+1] = keys[i];
118 vals[i+1] = vals[i];
119 }
120 nKeys++;
121 }
122
123 private void split(int loc, Comparable key, Object val, SkipList sl) {
124 SkipSpan right = newInstance(sl);
125 sl.spans++;
126
127 if(this.next != null) { this.next.prev = right; }
128 right.next = this.next;
129 right.prev = this;
130 this.next = right;
131
132 int start = ((keys.length+1)/2);
133 for(int i=start;i < keys.length; i++) {
134 try {
135 right.keys[i-start] = keys[i];
136 right.vals[i-start] = vals[i];
137 right.nKeys++;
138 this.nKeys--;
139 } catch (ArrayIndexOutOfBoundsException e) {
140 System.out.println("i " + i + " start " + start);
141 System.out.println("key: " + keys[i].toString());
142 throw e;
143 }
144 }
145 if(loc >= start) {
146 right.pushApart(loc - start);
147 right.keys[loc - start] = key;
148 right.vals[loc - start] = val;
149 } else {
150 pushApart(loc);
151 keys[loc] = key;
152 vals[loc] = val;
153 }
154 this.flush();
155 this.next.flush();
156 }
157
158 private SkipSpan insert(int loc, Comparable key, Object val, SkipList sl) {
159 sl.size++;
160 if(nKeys == keys.length) {
161 split(loc, key, val, sl);
163 return next;
164 } else {
165 pushApart(loc);
166 keys[loc] = key;
167 vals[loc] = val;
168 this.flush();
169 return null;
170 }
171 }
172
173 public SkipSpan put(Comparable key, Object val, SkipList sl) {
174 if(nKeys == 0) {
175 sl.size++;
176 keys[0] = key;
177 vals[0] = val;
178 nKeys++;
179 this.flush();
180 return null;
181 }
182 int loc = binarySearch(key);
183 if(loc < 0) {
184 loc = -1 * (loc + 1);
185 if(next != null) {
186 int cmp = next.keys[0].compareTo(key);
187 if((loc >= nKeys) && (cmp > 0)) {
188 if(nKeys == keys.length) {
191 if(next.nKeys == keys.length) {
192 return insert(loc, key, val, sl);
193 } else {
194 return next.put(key, val, sl);
195 }
196 } else {
197 return insert(loc, key, val, sl);
198 }
199 } else {
200 if(cmp > 0) {
202 return insert(loc, key, val, sl);
203 } else {
204 return next.put(key, val, sl);
205 }
206 }
207 } else {
208 return insert(loc, key, val, sl);
211 }
212 } else {
213 vals[loc] = val;
215 this.flush();
216 return null;
217 }
218 }
219
220 public Object [] remove(Comparable key, SkipList sl) {
221 if(nKeys == 0) { return null; }
222 if(keys[nKeys - 1].compareTo(key) < 0) {
223 if(next == null) { return null; }
224 return next.remove(key, sl);
225 }
226 int loc = binarySearch(key);
227 if(loc < 0) { return null; }
228 Object o = vals[loc];
229 Object [] res = new Object [2];
230 res[0] = o;
231 sl.size--;
232 if(nKeys == 1) {
233 if(sl.spans > 1) { sl.spans--; }
234 if((this.prev == null) && (this.next != null)) {
235 res[1] = this.next;
236 for(int i=0;i<next.nKeys;i++) {
238 keys[i] = next.keys[i];
239 vals[i] = next.vals[i];
240 }
241 nKeys = next.nKeys;
242 SkipSpan nn = next.next;
243 next.killInstance();
244 this.flush();
245 this.next = nn;
246 } else {
247 res[1] = this;
248 if(this.prev != null) {
249 this.prev.next = this.next;
250 this.prev.flush();
251 }
252 if(this.next != null) {
253 this.next.prev = this.prev;
254 this.next.flush();
255 }
256 this.next = null;
257 this.prev = null;
258 nKeys = 0;
259 this.killInstance();
260 }
261 } else {
262 pushTogether(loc);
263 this.flush();
264 }
265 return res;
266 }
267 }
268 |
Popular Tags |
Java API By Example, From Geeks To Geeks.