|
1 package prefuse.util.collections;
2
3
9 public class IntIntTreeMap extends AbstractTreeMap implements IntIntSortedMap {
10
11 private IntEntry dummy =
13 new IntEntry(Integer.MIN_VALUE, Integer.MAX_VALUE, NIL, 0);
14
15
18 public IntIntTreeMap() {
19 this(null, false);
20 }
21
22 public IntIntTreeMap(boolean allowDuplicates) {
23 this(null, allowDuplicates);
24 }
25
26 public IntIntTreeMap(LiteralComparator comparator) {
27 this(comparator, false);
28 }
29
30 public IntIntTreeMap(LiteralComparator comparator,
31 boolean allowDuplicates)
32 {
33 super(comparator, allowDuplicates);
34 }
35
36
39
42 public void clear() {
43 ++modCount;
44 size = 0;
45 root = NIL;
46 }
47
48
51 public boolean containsKey(int key) {
52 return find(key, 0) != NIL;
53 }
54
55
58 public int get(int key) {
59 Entry ret = find(key, 0);
60 return ( ret == NIL ? Integer.MIN_VALUE : ret.val );
61 }
62
63
66 public int put(int key, int value) {
67 Entry t = root;
68 lastOrder = 0;
69
70 if (t == NIL) {
71 incrementSize(true);
72 root = new IntEntry(key, value, NIL, lastOrder);
73 return Integer.MIN_VALUE;
74 }
75
76 dummy.key = key;
77 dummy.order = Integer.MAX_VALUE;
78
79 while (true) {
80 int cmp = compare(dummy, t);
81 if (cmp == 0) {
82 return t.setValue(value);
83 } else if (cmp < 0) {
84 if (t.left != NIL) {
85 t = t.left;
86 } else {
87 incrementSize(lastOrder==0);
88 t.left = new IntEntry(key, value, t, lastOrder);
89 fixUpInsert(t.left);
90 return Integer.MIN_VALUE;
91 }
92 } else { if (t.right != NIL) {
94 t = t.right;
95 } else {
96 incrementSize(lastOrder==0);
97 t.right = new IntEntry(key, value, t, lastOrder);
98 fixUpInsert(t.right);
99 return Integer.MIN_VALUE;
100 }
101 }
102 }
103 }
104
105
108 public int remove(int key) {
109 Entry x;
111 if ( allowDuplicates )
112 x = findPredecessor(key, Integer.MAX_VALUE);
113 else
114 x = find(key, 0);
115
116 if (x == NIL)
117 return Integer.MIN_VALUE;
118
119 int val = x.val;
120 remove(x);
121 return val;
122 }
123
124 public int remove(int key, int val) {
125 Entry x = findCeiling(key, 0);
127 if ( x!=NIL && x.getIntKey() != key )
128 x = successor(x);
129 if (x==NIL || x.getIntKey()!=key) return Integer.MIN_VALUE;
130
131 for ( ; x.val != val && x != NIL; x = successor(x) );
132 if (x == NIL) return Integer.MIN_VALUE;
133
134 remove(x);
135 return val;
136 }
137
138 public int getLast(int key) {
139 Entry ret = findPredecessor(key, Integer.MAX_VALUE);
140 return ( ret == NIL || ((IntEntry)ret).key != key
141 ? Integer.MIN_VALUE : ret.val );
142 }
143
144 public int getPreviousValue(int key, int value) {
145 Entry cur = find(key, value);
146 return predecessor(cur).val;
147 }
148
149 public int getNextValue(int key, int value) {
150 Entry cur = find(key, value);
151 return successor(cur).val;
152 }
153
154
157 public int firstKey() {
158 return minimum(root).getIntKey();
159 }
160
161
164 public int lastKey() {
165 return maximum(root).getIntKey();
166 }
167
168
170 public LiteralIterator keyIterator() {
171 return new KeyIterator();
172 }
173
174 public LiteralIterator keyRangeIterator(int fromKey, boolean fromInc,
175 int toKey, boolean toInc)
176 {
177 Entry start, end;
178
179 if ( cmp.compare(fromKey, toKey) <= 0 ) {
180 start = findCeiling(fromKey, (fromInc ? 0 : Integer.MAX_VALUE));
181 end = findCeiling(toKey, (toInc? Integer.MAX_VALUE : 0));
182 } else {
183 start = findCeiling(fromKey, (fromInc ? Integer.MAX_VALUE : 0));
184 start = predecessor(start);
185 end = findCeiling(toKey, (toInc ? 0 : Integer.MAX_VALUE));
186 end = predecessor(end);
187 }
188 return new KeyIterator(start, end);
189 }
190
191 public IntIterator valueRangeIterator(int fromKey, boolean fromInc,
192 int toKey, boolean toInc)
193 {
194 return new ValueIterator(
195 (EntryIterator)keyRangeIterator(fromKey,fromInc,toKey,toInc));
196 }
197
198
202 protected int compare(Entry e1, Entry e2) {
203 int c = cmp.compare(e1.getIntKey(), e2.getIntKey());
204 if ( allowDuplicates && c == 0 ) {
205 c = (e1.order < e2.order ? -1 : (e1.order > e2.order ? 1 : 0));
206 lastOrder = 1 + (c < 0 ? e1.order : e2.order);
207 }
208 return c;
209 }
210
211 private Entry find(int key, int order) {
212 dummy.key = key;
213 dummy.order = order;
214 Entry e = find(dummy);
215 return e;
216 }
217
218 private Entry findPredecessor(int key, int order) {
219 dummy.key = key;
220 dummy.order = order;
221 Entry e = findPredecessor(dummy);
222 return e;
223 }
224
225 private Entry findCeiling(int key, int order) {
226 dummy.key = key;
227 dummy.order = order;
228 Entry e = findCeiling(dummy);
229 return e;
230 }
231
232
235
238 static class IntEntry extends AbstractTreeMap.Entry {
239 int key;
240
241 public IntEntry(int key, int val) {
242 super(val);
243 this.key = key;
244 }
245
246 public IntEntry(int key, int val, Entry parent, int order) {
247 super(val, parent, order);
248 this.key = key;
249 }
250
251 public int getIntKey() {
252 return key;
253 }
254
255 public Object  getKey() {
256 return new Integer (key);
257 }
258
259 public boolean keyEquals(Entry e) {
260 return (e instanceof IntEntry && key == ((IntEntry)e).key);
261 }
262
263 public boolean equals(Object o) {
264 if (!(o instanceof IntEntry))
265 return false;
266
267 IntEntry e = (IntEntry)o;
268 return (key == e.key && val == e.val);
269 }
270
271 public int hashCode() {
272 int khash = key;
273 int vhash = val;
274 return khash ^ vhash ^ order;
275 }
276
277 public String toString() {
278 return key + "=" + val;
279 }
280
281 public void copyFields(Entry x) {
282 super.copyFields(x);
283 this.key = x.getIntKey();
284 }
285
286 }
287
288
291 private class KeyIterator extends AbstractTreeMap.KeyIterator {
292 public KeyIterator() {
293 super();
294 }
295 public KeyIterator(Entry start, Entry end) {
296 super(start, end);
297 }
298 public boolean isIntSupported() {
299 return true;
300 }
301 public int nextInt() {
302 return nextEntry().getIntKey();
303 }
304 }
305
306 } |
Popular Tags |
Java API By Example, From Geeks To Geeks.