001: /*
002: Copyright (c) 2006, Matthew Estes
003: All rights reserved.
004:
005: Redistribution and use in source and binary forms, with or without
006: modification, are permitted provided that the following conditions are met:
007:
008: * Redistributions of source code must retain the above copyright
009: notice, this list of conditions and the following disclaimer.
010: * Redistributions in binary form must reproduce the above copyright
011: notice, this list of conditions and the following disclaimer in the
012: documentation and/or other materials provided with the distribution.
013: * Neither the name of Metanotion Software nor the names of its
014: contributors may be used to endorse or promote products derived from this
015: software without specific prior written permission.
016:
017: THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
018: IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
019: THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
020: PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
021: CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
022: EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
023: PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
024: PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
025: LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
026: NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
027: SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
028: */
029: package net.metanotion.util.skiplist;
030:
031: import java.util.Random;
032:
033: public class SkipList {
034: protected SkipSpan first;
035: protected SkipLevels stack;
036: public Random rng;
037:
038: public int size = 0;
039: public int spans = 0;
040:
041: public void flush() {
042: }
043:
044: protected SkipList() {
045: }
046:
047: public SkipList(int span) {
048: if (span < 1) {
049: throw new Error("Span size too small");
050: }
051: first = new SkipSpan(span);
052: stack = new SkipLevels(1, first);
053: spans = 1;
054: rng = new Random(System.currentTimeMillis());
055: }
056:
057: public int size() {
058: return size;
059: }
060:
061: public int maxLevels() {
062: int hob = 0, s = spans;
063: while (spans > 0) {
064: hob++;
065: spans = spans / 2;
066: }
067: return (hob > 4) ? hob : 4;
068: }
069:
070: public int generateColHeight() {
071: int bits = rng.nextInt();
072: boolean cont = true;
073: int res = 0;
074: for (res = 0; cont; res++) {
075: cont = ((bits % 2) == 0) ? true : false;
076: bits = bits / 2;
077: }
078: return Math.max(0, Math.min(res, maxLevels()));
079: }
080:
081: public void put(Comparable key, Object val) {
082: if (key == null) {
083: throw new NullPointerException();
084: }
085: if (val == null) {
086: throw new NullPointerException();
087: }
088: SkipLevels slvls = stack.put(stack.levels.length - 1, key, val,
089: this );
090: if (slvls != null) {
091: SkipLevels[] levels = new SkipLevels[slvls.levels.length];
092: for (int i = 0; i < slvls.levels.length; i++) {
093: if (i < stack.levels.length) {
094: levels[i] = stack.levels[i];
095: } else {
096: levels[i] = slvls;
097: }
098: }
099: stack.levels = levels;
100: stack.flush();
101: flush();
102: }
103: }
104:
105: public Object remove(Comparable key) {
106: if (key == null) {
107: throw new NullPointerException();
108: }
109: Object[] res = stack.remove(stack.levels.length - 1, key, this );
110: if (res != null) {
111: if (res[1] != null) {
112: SkipLevels slvls = (SkipLevels) res[1];
113: for (int i = 0; i < slvls.levels.length; i++) {
114: if (stack.levels[i] == slvls) {
115: stack.levels[i] = slvls.levels[i];
116: }
117: }
118: stack.flush();
119: }
120: flush();
121: return res[0];
122: }
123: return null;
124: }
125:
126: public void printSL() {
127: System.out.println("List size " + size + " spans " + spans);
128: stack.print();
129: }
130:
131: public void print() {
132: System.out.println("List size " + size + " spans " + spans);
133: first.print();
134: }
135:
136: public Object get(Comparable key) {
137: if (key == null) {
138: throw new NullPointerException();
139: }
140: return stack.get(stack.levels.length - 1, key);
141: }
142:
143: public SkipIterator iterator() {
144: return new SkipIterator(first, 0);
145: }
146:
147: public SkipIterator min() {
148: return new SkipIterator(first, 0);
149: }
150:
151: public SkipIterator max() {
152: SkipSpan ss = stack.getEnd();
153: return new SkipIterator(ss, ss.nKeys - 1);
154: }
155:
156: public SkipIterator find(Comparable key) {
157: int[] search = new int[1];
158: SkipSpan ss = stack.getSpan(stack.levels.length - 1, key,
159: search);
160: if (search[0] < 0) {
161: search[0] = -1 * (search[0] + 1);
162: }
163: return new SkipIterator(ss, search[0]);
164: }
165:
166: // Levels adjusted to guarantee O(log n) search
167: // This is expensive proportional to the number of spans.
168: public void balance() {
169: // TODO Skip List Balancing Algorithm
170: }
171:
172: /*
173: Basic Error generating conditions to test
174: insert into empty
175: insert into non empty
176: remove from empty
177: remove from non-empty a non-existant key
178: get from empty
179: get from non-empty a non-existant key
180:
181: Repeat, with splits induced, and collapse induced.
182: */
183: public static void main(String args[]) {
184: SkipList sl = new SkipList(3);
185: sl.put(".1", "1");
186: sl.remove("2");
187: sl.remove("1");
188: sl.put(".1", "1-1");
189: sl.put(".2", "2");
190: sl.put(".3", "3");
191: /* System.out.println("\n#1");
192: sl.print();
193: */
194:
195: sl.put(".4", "4");
196: /* System.out.println("\n#2");
197: sl.print();
198:
199: sl.remove("1");
200: System.out.println("\n#2.1");
201: sl.print();
202: sl.remove("2");
203: System.out.println("\n#2.2");
204: sl.print();
205: sl.remove("3");
206: System.out.println("\n#2.3");
207: sl.print();
208: sl.remove("4");
209:
210: System.out.println("\n#3");
211: sl.print();
212: */
213: sl.put(".1", "1-2");
214: sl.put(".2", "2-1");
215: sl.put(".3", "3-1");
216: sl.put(".4", "4-1");
217: // System.out.println("\n#4");
218: // sl.print();
219: sl.put(".5", "5-1");
220: sl.put(".6", "6-1");
221: sl.put(".7", "7-1");
222:
223: // System.out.println("\n#5");
224: // sl.print();
225:
226: // sl.remove("5");
227: sl.put(".5", "5-2");
228: // System.out.println("\n#6");
229: // sl.print();
230:
231: sl.put(".8", "8");
232: sl.put(".9", "9");
233: sl.put("10", "10");
234: sl.put("11", "11");
235: sl.put("12", "12");
236: sl.put("13", "13");
237: sl.put("14", "14");
238: sl.put("15", "15");
239: sl.put("16", "16");
240: sl.put("17", "17");
241: sl.put("18", "18");
242: sl.put("19", "19");
243: sl.put("20", "20");
244: sl.put("21", "21");
245: sl.put("22", "22");
246: sl.put("23", "23");
247: sl.put("24", "24");
248: sl.put("25", "25");
249: sl.put("26", "26");
250: sl.put("27", "27");
251: sl.put("28", "28");
252: sl.put("29", "29");
253: sl.put("30", "30");
254: sl.put("31", "31");
255: sl.put("32", "32");
256: sl.put("33", "33");
257: sl.put("34", "34");
258: sl.put("35", "35");
259: sl.put("36", "36");
260: sl.put("37", "37");
261: sl.put("38", "38");
262: sl.put("39", "39");
263: sl.put("40", "40");
264:
265: // System.out.println("\n#7");
266: // 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: sl.printSL();
275:
276: sl.remove("33");
277: sl.printSL();
278: sl.remove("34");
279: sl.printSL();
280: sl.remove("36");
281: sl.printSL();
282: sl.remove("35");
283: sl.printSL();
284:
285: // System.out.println("\n#8");
286: sl.print();
287: System.out.println("GET " + sl.get("10"));
288: System.out.println("GET " + sl.get("12"));
289: System.out.println("GET " + sl.get("32"));
290: System.out.println("GET " + sl.get("33"));
291: System.out.println("GET " + sl.get("37"));
292: System.out.println("GET " + sl.get("40"));
293:
294: System.out.println("Height " + sl.stack.levels.length);
295:
296: SkipIterator si = sl.iterator();
297: for (int i = 0; i < 5; i++) {
298: System.out.println("Iterator: " + si.next());
299: }
300: for (int i = 0; i < 3; i++) {
301: System.out.println("Iterator: " + si.previous());
302: }
303:
304: System.out.println("Find 10");
305: si = sl.find("10");
306: for (int i = 0; i < 5; i++) {
307: System.out.println("Iterator: " + si.next());
308: }
309: for (int i = 0; i < 3; i++) {
310: System.out.println("Iterator: " + si.previous());
311: }
312:
313: System.out.println("Find 34");
314: si = sl.find("34");
315: for (int i = 0; i < 3; i++) {
316: System.out.println("Iterator: " + si.previous());
317: }
318: for (int i = 0; i < 5; i++) {
319: System.out.println("Iterator: " + si.next());
320: }
321:
322: System.out.println("Max");
323: si = sl.max();
324: for (int i = 0; i < 3; i++) {
325: System.out.println("Iterator: " + si.previous());
326: }
327: for (int i = 0; i < 5; i++) {
328: System.out.println("Iterator: " + si.next());
329: }
330: }
331: }
|