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 SkipLevels {
032: /* "Next" pointers
033: The highest indexed level is the "highest" level in the list.
034: The "bottom" level is the direct pointer to a SkipSpan.
035: */
036: public SkipLevels[] levels;
037: public SkipSpan bottom;
038:
039: public SkipLevels newInstance(int levels, SkipSpan ss, SkipList sl) {
040: return new SkipLevels(levels, ss);
041: }
042:
043: public void killInstance() {
044: }
045:
046: public void flush() {
047: }
048:
049: protected SkipLevels() {
050: }
051:
052: public SkipLevels(int size, SkipSpan span) {
053: if (size < 1) {
054: throw new Error("Invalid Level Skip size");
055: }
056: levels = new SkipLevels[size];
057: bottom = span;
058: }
059:
060: public void print() {
061: SkipLevels prev = null;
062: SkipLevels max = null;
063: System.out.print("SL:" + key() + "::");
064: for (int i = 0; i < levels.length; i++) {
065: if (levels[i] != null) {
066: max = levels[i];
067: System.out.print(i + "->" + levels[i].key() + " ");
068: } else {
069: System.out.print(i + "->() ");
070: }
071: }
072: System.out.print("\n");
073: if (levels[0] != null) {
074: levels[0].print();
075: }
076: }
077:
078: public SkipSpan getEnd() {
079: for (int i = (levels.length - 1); i >= 0; i--) {
080: if (levels[i] != null) {
081: return levels[i].getEnd();
082: }
083: }
084: return bottom.getEnd();
085: }
086:
087: public SkipSpan getSpan(int start, Comparable key, int[] search) {
088: for (int i = Math.min(start, levels.length - 1); i >= 0; i--) {
089: if ((levels[i] != null)
090: && (levels[i].key().compareTo(key) <= 0)) {
091: return levels[i].getSpan(i, key, search);
092: }
093: }
094: return bottom.getSpan(key, search);
095: }
096:
097: public Comparable key() {
098: return bottom.keys[0];
099: }
100:
101: public Object get(int start, Comparable key) {
102: for (int i = Math.min(start, levels.length - 1); i >= 0; i--) {
103: if ((levels[i] != null)
104: && (levels[i].key().compareTo(key) <= 0)) {
105: return levels[i].get(i, key);
106: }
107: }
108: return bottom.get(key);
109: }
110:
111: public Object[] remove(int start, Comparable key, SkipList sl) {
112: SkipSpan ss = null;
113: Object[] res = null;
114: SkipLevels slvls = null;
115: for (int i = Math.min(start, levels.length - 1); i >= 0; i--) {
116: if (levels[i] != null) {
117: int cmp = levels[i].key().compareTo(key);
118: if ((cmp < 0) || ((i == 0) && (cmp <= 0))) {
119: res = levels[i].remove(i, key, sl);
120: if ((res != null) && (res[1] != null)) {
121: slvls = (SkipLevels) res[1];
122: if (levels.length >= slvls.levels.length) {
123: res[1] = null;
124: }
125: for (int j = 0; j < (Math.min(
126: slvls.levels.length, levels.length)); j++) {
127: if (levels[j] == slvls) {
128: levels[j] = slvls.levels[j];
129: }
130: }
131: this .flush();
132: }
133: return res;
134: }
135: }
136: }
137: res = bottom.remove(key, sl);
138: if ((res != null) && (res[1] != null)) {
139: if (res[1] == bottom) {
140: res[1] = this ;
141: } else {
142: res[1] = null;
143: }
144: }
145: if ((bottom.nKeys == 0) && (sl.first != bottom)) {
146: this .killInstance();
147: }
148: return res;
149: }
150:
151: public SkipLevels put(int start, Comparable key, Object val,
152: SkipList sl) {
153: SkipSpan ss = null;
154: SkipLevels slvls = null;
155: for (int i = Math.min(start, levels.length - 1); i >= 0; i--) {
156: if ((levels[i] != null)
157: && (levels[i].key().compareTo(key) <= 0)) {
158: slvls = levels[i].put(i, key, val, sl);
159: if (slvls != null) {
160: for (int j = i + 1; j < (Math.min(
161: slvls.levels.length, levels.length)); j++) {
162: slvls.levels[j] = levels[j];
163: levels[j] = slvls;
164: }
165: if (levels.length < slvls.levels.length) {
166: this .flush();
167: return slvls;
168: }
169: }
170: this .flush();
171: return null;
172: }
173: }
174: ss = bottom.put(key, val, sl);
175: if (ss != null) {
176: int height = sl.generateColHeight();
177: if (height != 0) {
178: slvls = this .newInstance(height, ss, sl);
179: for (int i = 0; i < (Math.min(height, levels.length)); i++) {
180: slvls.levels[i] = levels[i];
181: levels[i] = slvls;
182: }
183: }
184: this.flush();
185: if (levels.length >= height) {
186: return null;
187: }
188: return slvls;
189: } else {
190: return null;
191: }
192: }
193: }
|