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: public class SkipSpan {
032: public int nKeys = 0;
033: public Comparable[] keys;
034: public Object[] vals;
035: public SkipSpan next, prev;
036:
037: public SkipSpan newInstance(SkipList sl) {
038: return new SkipSpan(keys.length);
039: }
040:
041: public void killInstance() {
042: }
043:
044: public void flush() {
045: }
046:
047: protected SkipSpan() {
048: }
049:
050: public SkipSpan(int size) {
051: keys = new Comparable[size];
052: vals = new Object[size];
053: }
054:
055: public void print() {
056: System.out.println("Span");
057: for (int i = 0; i < nKeys; i++) {
058: System.out.println("\t" + keys[i] + " => " + vals[i]);
059: }
060: if (next != null) {
061: next.print();
062: }
063: }
064:
065: private int binarySearch(Comparable key) {
066: int high = nKeys - 1;
067: int low = 0;
068: int cur;
069: int cmp;
070: while (low <= high) {
071: cur = (low + high) >>> 1;
072: cmp = keys[cur].compareTo(key);
073: if (cmp > 0) {
074: high = cur - 1;
075: } else if (cmp < 0) {
076: low = cur + 1;
077: } else {
078: return cur;
079: }
080: }
081: return (-1 * (low + 1));
082: }
083:
084: public SkipSpan getEnd() {
085: if (next == null) {
086: return this ;
087: }
088: return next.getEnd();
089: }
090:
091: public SkipSpan getSpan(Comparable key, int[] search) {
092: if (nKeys == 0) {
093: search[0] = -1;
094: return this ;
095: }
096:
097: if (keys[nKeys - 1].compareTo(key) < 0) {
098: if (next == null) {
099: search[0] = (-1 * (nKeys - 1)) - 1;
100: return this ;
101: }
102: return next.getSpan(key, search);
103: }
104: search[0] = binarySearch(key);
105: return this ;
106: }
107:
108: public Object get(Comparable key) {
109: if (nKeys == 0) {
110: return null;
111: }
112: if (keys[nKeys - 1].compareTo(key) < 0) {
113: if (next == null) {
114: return null;
115: }
116: return next.get(key);
117: }
118: int loc = binarySearch(key);
119: if (loc < 0) {
120: return null;
121: }
122: return vals[loc];
123: }
124:
125: private void pushTogether(int hole) {
126: for (int i = hole; i < (nKeys - 1); i++) {
127: keys[i] = keys[i + 1];
128: vals[i] = vals[i + 1];
129: }
130: nKeys--;
131: }
132:
133: private void pushApart(int start) {
134: for (int i = (nKeys - 1); i >= start; i--) {
135: keys[i + 1] = keys[i];
136: vals[i + 1] = vals[i];
137: }
138: nKeys++;
139: }
140:
141: private void split(int loc, Comparable key, Object val, SkipList sl) {
142: SkipSpan right = newInstance(sl);
143: sl.spans++;
144:
145: if (this .next != null) {
146: this .next.prev = right;
147: }
148: right.next = this .next;
149: right.prev = this ;
150: this .next = right;
151:
152: int start = ((keys.length + 1) / 2);
153: for (int i = start; i < keys.length; i++) {
154: try {
155: right.keys[i - start] = keys[i];
156: right.vals[i - start] = vals[i];
157: right.nKeys++;
158: this .nKeys--;
159: } catch (ArrayIndexOutOfBoundsException e) {
160: System.out.println("i " + i + " start " + start);
161: System.out.println("key: " + keys[i].toString());
162: throw e;
163: }
164: }
165: if (loc >= start) {
166: right.pushApart(loc - start);
167: right.keys[loc - start] = key;
168: right.vals[loc - start] = val;
169: } else {
170: pushApart(loc);
171: keys[loc] = key;
172: vals[loc] = val;
173: }
174: this .flush();
175: this .next.flush();
176: }
177:
178: private SkipSpan insert(int loc, Comparable key, Object val,
179: SkipList sl) {
180: sl.size++;
181: if (nKeys == keys.length) {
182: // split.
183: split(loc, key, val, sl);
184: return next;
185: } else {
186: pushApart(loc);
187: keys[loc] = key;
188: vals[loc] = val;
189: this .flush();
190: return null;
191: }
192: }
193:
194: public SkipSpan put(Comparable key, Object val, SkipList sl) {
195: if (nKeys == 0) {
196: sl.size++;
197: keys[0] = key;
198: vals[0] = val;
199: nKeys++;
200: this .flush();
201: return null;
202: }
203: int loc = binarySearch(key);
204: if (loc < 0) {
205: loc = -1 * (loc + 1);
206: if (next != null) {
207: int cmp = next.keys[0].compareTo(key);
208: if ((loc >= nKeys) && (cmp > 0)) {
209: // It fits in between this span and the next
210: // Try to avoid a split...
211: if (nKeys == keys.length) {
212: if (next.nKeys == keys.length) {
213: return insert(loc, key, val, sl);
214: } else {
215: return next.put(key, val, sl);
216: }
217: } else {
218: return insert(loc, key, val, sl);
219: }
220: } else {
221: // Its either clearly in the next span or this span.
222: if (cmp > 0) {
223: return insert(loc, key, val, sl);
224: } else {
225: return next.put(key, val, sl);
226: }
227: }
228: } else {
229: // There is no next span, So
230: // either it goes here, or causes a split.
231: return insert(loc, key, val, sl);
232: }
233: } else {
234: // Key already exists. Overwrite value.
235: vals[loc] = val;
236: this .flush();
237: return null;
238: }
239: }
240:
241: public Object[] remove(Comparable key, SkipList sl) {
242: if (nKeys == 0) {
243: return null;
244: }
245: if (keys[nKeys - 1].compareTo(key) < 0) {
246: if (next == null) {
247: return null;
248: }
249: return next.remove(key, sl);
250: }
251: int loc = binarySearch(key);
252: if (loc < 0) {
253: return null;
254: }
255: Object o = vals[loc];
256: Object[] res = new Object[2];
257: res[0] = o;
258: sl.size--;
259: if (nKeys == 1) {
260: if (sl.spans > 1) {
261: sl.spans--;
262: }
263: if ((this .prev == null) && (this .next != null)) {
264: res[1] = this .next;
265: // We're the first node in the list...
266: for (int i = 0; i < next.nKeys; i++) {
267: keys[i] = next.keys[i];
268: vals[i] = next.vals[i];
269: }
270: nKeys = next.nKeys;
271: SkipSpan nn = next.next;
272: next.killInstance();
273: this .flush();
274: this .next = nn;
275: } else {
276: res[1] = this ;
277: if (this .prev != null) {
278: this .prev.next = this .next;
279: this .prev.flush();
280: }
281: if (this .next != null) {
282: this .next.prev = this .prev;
283: this .next.flush();
284: }
285: this .next = null;
286: this .prev = null;
287: nKeys = 0;
288: this.killInstance();
289: }
290: } else {
291: pushTogether(loc);
292: this.flush();
293: }
294: return res;
295: }
296: }
|