|
1
29 package net.metanotion.util.skiplist;
30
31 public class SkipLevels {
32
36 public SkipLevels[] levels;
37 public SkipSpan bottom;
38
39 public SkipLevels newInstance(int levels, SkipSpan ss, SkipList sl) { return new SkipLevels(levels, ss); }
40 public void killInstance() { }
41 public void flush() { }
42
43 protected SkipLevels() { }
44 public SkipLevels(int size, SkipSpan span) {
45 if(size < 1) { throw new Error  ("Invalid Level Skip size"); }
46 levels = new SkipLevels[size];
47 bottom = span;
48 }
49
50 public void print() {
51 SkipLevels prev = null;
52 SkipLevels max = null;
53 System.out.print("SL:" + key() + "::");
54 for(int i=0;i<levels.length;i++) {
55 if(levels[i] != null) {
56 max = levels[i];
57 System.out.print(i + "->" + levels[i].key() + " ");
58 } else {
59 System.out.print(i + "->() ");
60 }
61 }
62 System.out.print("\n");
63 if(levels[0] != null) {
64 levels[0].print();
65 }
66 }
67
68 public SkipSpan getEnd() {
69 for(int i=(levels.length - 1);i>=0;i--) {
70 if(levels[i] != null) { return levels[i].getEnd(); }
71 }
72 return bottom.getEnd();
73 }
74
75 public SkipSpan getSpan(int start, Comparable key, int[] search) {
76 for(int i=Math.min(start, levels.length - 1);i>=0;i--) {
77 if((levels[i] != null) && (levels[i].key().compareTo(key) <= 0)) {
78 return levels[i].getSpan(i,key,search);
79 }
80 }
81 return bottom.getSpan(key, search);
82 }
83
84 public Comparable key() { return bottom.keys[0]; }
85
86 public Object get(int start, Comparable key) {
87 for(int i=Math.min(start, levels.length - 1);i>=0;i--) {
88 if((levels[i] != null) && (levels[i].key().compareTo(key) <= 0)) {
89 return levels[i].get(i,key);
90 }
91 }
92 return bottom.get(key);
93 }
94
95 public Object [] remove(int start, Comparable key, SkipList sl) {
96 SkipSpan ss = null;
97 Object [] res = null;
98 SkipLevels slvls = null;
99 for(int i=Math.min(start, levels.length - 1);i>=0;i--) {
100 if(levels[i] != null) {
101 int cmp = levels[i].key().compareTo(key);
102 if((cmp < 0) || ((i==0) && (cmp <= 0))) {
103 res = levels[i].remove(i, key, sl);
104 if((res != null) && (res[1] != null)) {
105 slvls = (SkipLevels) res[1];
106 if(levels.length >= slvls.levels.length) { res[1] = null; }
107 for(int j=0;j<(Math.min(slvls.levels.length,levels.length));j++) {
108 if(levels[j] == slvls) {
109 levels[j] = slvls.levels[j];
110 }
111 }
112 this.flush();
113 }
114 return res;
115 }
116 }
117 }
118 res = bottom.remove(key, sl);
119 if((res!=null) && (res[1] != null)) {
120 if(res[1] == bottom) {
121 res[1] = this;
122 } else {
123 res[1] = null;
124 }
125 }
126 if((bottom.nKeys == 0) && (sl.first != bottom)) { this.killInstance(); }
127 return res;
128 }
129
130 public SkipLevels put(int start, Comparable key, Object val, SkipList sl) {
131 SkipSpan ss = null;
132 SkipLevels slvls = null;
133 for(int i=Math.min(start, levels.length - 1);i>=0;i--) {
134 if((levels[i] != null) && (levels[i].key().compareTo(key) <= 0)) {
135 slvls = levels[i].put(i, key, val, sl);
136 if(slvls != null) {
137 for(int j=i+1;j<(Math.min(slvls.levels.length,levels.length));j++) {
138 slvls.levels[j] = levels[j];
139 levels[j] = slvls;
140 }
141 if(levels.length < slvls.levels.length) {
142 this.flush();
143 return slvls;
144 }
145 }
146 this.flush();
147 return null;
148 }
149 }
150 ss = bottom.put(key,val,sl);
151 if(ss!=null) {
152 int height = sl.generateColHeight();
153 if(height != 0) {
154 slvls = this.newInstance(height, ss, sl);
155 for(int i=0;i<(Math.min(height,levels.length));i++) {
156 slvls.levels[i] = levels[i];
157 levels[i] = slvls;
158 }
159 }
160 this.flush();
161 if(levels.length >= height) { return null; }
162 return slvls;
163 } else {
164 return null;
165 }
166 }
167 }
168
169 |
Popular Tags |
Java API By Example, From Geeks To Geeks.