|
1
29 package net.metanotion.util.skiplist;
30
31 import java.util.Random  ;
32
33 public class SkipList {
34 protected SkipSpan first;
35 protected SkipLevels stack;
36 public Random rng;
37
38 public int size=0;
39 public int spans=0;
40
41 public void flush() { }
42 protected SkipList() { }
43
44 public SkipList(int span) {
45 if(span < 1) { throw new Error ("Span size too small"); }
46 first = new SkipSpan(span);
47 stack = new SkipLevels(1, first);
48 spans = 1;
49 rng = new Random (System.currentTimeMillis());
50 }
51
52 public int size() { return size; }
53
54 public int maxLevels() {
55 int hob = 0, s = spans;
56 while(spans > 0) {
57 hob++;
58 spans = spans / 2;
59 }
60 return (hob > 4) ? hob : 4;
61 }
62
63 public int generateColHeight() {
64 int bits = rng.nextInt();
65 boolean cont = true;
66 int res=0;
67 for(res=0; cont; res++) {
68 cont = ((bits % 2) == 0) ? true : false;
69 bits = bits / 2;
70 }
71 return Math.max(0, Math.min(res, maxLevels()));
72 }
73
74 public void put(Comparable key, Object val) {
75 if(key == null) { throw new NullPointerException (); }
76 if(val == null) { throw new NullPointerException (); }
77 SkipLevels slvls = stack.put(stack.levels.length - 1, key, val, this);
78 if(slvls != null) {
79 SkipLevels[] levels = new SkipLevels[slvls.levels.length];
80 for(int i=0;i < slvls.levels.length; i++) {
81 if(i < stack.levels.length) {
82 levels[i] = stack.levels[i];
83 } else {
84 levels[i] = slvls;
85 }
86 }
87 stack.levels = levels;
88 stack.flush();
89 flush();
90 }
91 }
92
93 public Object remove(Comparable key) {
94 if(key == null) { throw new NullPointerException (); }
95 Object [] res = stack.remove(stack.levels.length - 1, key, this);
96 if(res != null) {
97 if(res[1] != null) {
98 SkipLevels slvls = (SkipLevels) res[1];
99 for(int i=0;i < slvls.levels.length; i++) {
100 if(stack.levels[i] == slvls) {
101 stack.levels[i] = slvls.levels[i];
102 }
103 }
104 stack.flush();
105 }
106 flush();
107 return res[0];
108 }
109 return null;
110 }
111
112 public void printSL() {
113 System.out.println("List size " + size + " spans " + spans);
114 stack.print();
115 }
116
117 public void print() {
118 System.out.println("List size " + size + " spans " + spans);
119 first.print();
120 }
121
122 public Object get(Comparable key) {
123 if(key == null) { throw new NullPointerException (); }
124 return stack.get(stack.levels.length - 1, key);
125 }
126
127 public SkipIterator iterator() { return new SkipIterator(first, 0); }
128
129 public SkipIterator min() { return new SkipIterator(first, 0); }
130
131 public SkipIterator max() {
132 SkipSpan ss = stack.getEnd();
133 return new SkipIterator(ss, ss.nKeys - 1);
134 }
135
136 public SkipIterator find(Comparable key) {
137 int[] search = new int[1];
138 SkipSpan ss = stack.getSpan(stack.levels.length - 1, key, search);
139 if(search[0] < 0) { search[0] = -1 * (search[0] + 1); }
140 return new SkipIterator(ss, search[0]);
141 }
142
143
144 public void balance() {
147 }
149
150
151
152
163 public static void main(String args[]) {
164 SkipList sl = new SkipList(3);
165 sl.put(".1", "1");
166 sl.remove("2");
167 sl.remove("1");
168 sl.put(".1", "1-1");
169 sl.put(".2", "2");
170 sl.put(".3", "3");
171
174
175 sl.put(".4", "4");
176
193 sl.put(".1", "1-2");
194 sl.put(".2", "2-1");
195 sl.put(".3", "3-1");
196 sl.put(".4", "4-1");
197 sl.put(".5", "5-1");
200 sl.put(".6", "6-1");
201 sl.put(".7", "7-1");
202
203
206 sl.put(".5", "5-2");
208
211 sl.put(".8", "8");
212 sl.put(".9", "9");
213 sl.put("10", "10");
214 sl.put("11", "11");
215 sl.put("12", "12");
216 sl.put("13", "13");
217 sl.put("14", "14");
218 sl.put("15", "15");
219 sl.put("16", "16");
220 sl.put("17", "17");
221 sl.put("18", "18");
222 sl.put("19", "19");
223 sl.put("20", "20");
224 sl.put("21", "21");
225 sl.put("22", "22");
226 sl.put("23", "23");
227 sl.put("24", "24");
228 sl.put("25", "25");
229 sl.put("26", "26");
230 sl.put("27", "27");
231 sl.put("28", "28");
232 sl.put("29", "29");
233 sl.put("30", "30");
234 sl.put("31", "31");
235 sl.put("32", "32");
236 sl.put("33", "33");
237 sl.put("34", "34");
238 sl.put("35", "35");
239 sl.put("36", "36");
240 sl.put("37", "37");
241 sl.put("38", "38");
242 sl.put("39", "39");
243 sl.put("40", "40");
244
245 System.out.println("GET " + sl.get("10"));
248 System.out.println("GET " + sl.get("12"));
249 System.out.println("GET " + sl.get("32"));
250 System.out.println("GET " + sl.get("33"));
251 System.out.println("GET " + sl.get("37"));
252 System.out.println("GET " + sl.get("40"));
253
254 sl.printSL();
255
256 sl.remove("33");
257 sl.printSL();
258 sl.remove("34");
259 sl.printSL();
260 sl.remove("36");
261 sl.printSL();
262 sl.remove("35");
263 sl.printSL();
264
265 sl.print();
267 System.out.println("GET " + sl.get("10"));
268 System.out.println("GET " + sl.get("12"));
269 System.out.println("GET " + sl.get("32"));
270 System.out.println("GET " + sl.get("33"));
271 System.out.println("GET " + sl.get("37"));
272 System.out.println("GET " + sl.get("40"));
273
274 System.out.println("Height " + sl.stack.levels.length);
275
276 SkipIterator si = sl.iterator();
277 for(int i=0;i<5;i++) {
278 System.out.println("Iterator: " + si.next());
279 }
280 for(int i=0;i<3;i++) {
281 System.out.println("Iterator: " + si.previous());
282 }
283
284 System.out.println("Find 10");
285 si = sl.find("10");
286 for(int i=0;i<5;i++) {
287 System.out.println("Iterator: " + si.next());
288 }
289 for(int i=0;i<3;i++) {
290 System.out.println("Iterator: " + si.previous());
291 }
292
293 System.out.println("Find 34");
294 si = sl.find("34");
295 for(int i=0;i<3;i++) {
296 System.out.println("Iterator: " + si.previous());
297 }
298 for(int i=0;i<5;i++) {
299 System.out.println("Iterator: " + si.next());
300 }
301
302 System.out.println("Max");
303 si = sl.max();
304 for(int i=0;i<3;i++) {
305 System.out.println("Iterator: " + si.previous());
306 }
307 for(int i=0;i<5;i++) {
308 System.out.println("Iterator: " + si.next());
309 }
310 }
311 }
312 |
Popular Tags |
Java API By Example, From Geeks To Geeks.