|
1 package prefuse.util.collections;
2
3 import java.util.Comparator  ;
4 import java.util.ConcurrentModificationException ;
5 import java.util.NoSuchElementException ;
6
7
8
14 public abstract class AbstractTreeMap implements IntSortedMap {
15
16 protected static final boolean RED = false;
17 protected static final boolean BLACK = true;
18
19 protected static final Entry NIL = new Entry(Integer.MIN_VALUE);
20 static {
21 NIL.left = NIL.right = NIL.p = NIL;
22 }
23
24 protected LiteralComparator cmp = null;
25 protected Entry root = NIL;
26
27 protected boolean allowDuplicates;
28 protected int size = 0;
29 protected int unique = 0;
30 protected int modCount = 0;
31 protected int lastOrder = 0;
32
33
36 public AbstractTreeMap(LiteralComparator comparator,
37 boolean allowDuplicates)
38 {
39 this.cmp = comparator==null ? DefaultLiteralComparator.getInstance()
40 : comparator;
41 this.allowDuplicates = allowDuplicates;
42 }
43
44
47 public boolean isAllowDuplicates() {
48 return allowDuplicates;
49 }
50
51
54 public int size() {
55 return size;
56 }
57
58 public boolean isEmpty() {
59 return root == NIL;
60 }
61
62
65 public Comparator comparator() {
66 return cmp;
67 }
68
69
72
75 public void clear() {
76 ++modCount;
77 size = 0;
78 root = NIL;
79 }
80
81 public int getMinimum() {
82 return minimum(root).getValue();
83 }
84
85 public int getMaximum() {
86 return maximum(root).getValue();
87 }
88
89 public int getMedian() {
90 Entry e = minimum(root);
91 for ( int i=0; i<size/2; ++i, e=successor(e) );
92 return e.getValue();
93 }
94
95 public int getUniqueCount() {
96 return unique;
97 }
98
99
102 public boolean containsValue(int value) {
103 return (root == NIL ? false : containsValue(root, value));
104 }
105
106 private boolean containsValue(Entry e, int value) {
107 if ( e.val == value ) {
108 return true;
109 } else {
110 return (e.left != NIL && containsValue(e.left, value)) ||
111 (e.right != NIL && containsValue(e.right, value));
112 }
113 }
114
115
117 public IntIterator valueIterator(boolean ascend) {
118 return new ValueIterator(new EntryIterator(!ascend));
119 }
120
121
124 protected void incrementSize(boolean isUnique) {
125 ++size; ++modCount;
126 if ( isUnique ) ++unique;
127 }
128
129 protected void decrementSize(boolean isUnique) {
130 --size; ++modCount;
131 if ( isUnique ) --unique;
132 }
133
134
138 protected abstract int compare(Entry e1, Entry e2);
139
140 protected Entry find(Entry x) {
141 Entry y = root;
142 while (y != NIL) {
143 int cmp = compare(x, y);
144 if (cmp == 0)
145 return y;
146 else if (cmp < 0)
147 y = y.left;
148 else
149 y = y.right;
150 }
151 return y;
152 }
153
154 protected Entry findPredecessor(Entry x) {
155 Entry y = root;
156 while (y != NIL) {
157 int cmp = compare(x, y);
158 if (cmp > 0) {
159 if ( y.right == NIL )
160 return y;
161 y = y.right;
162 } else {
163 if ( y.left != NIL ) {
164 y = y.left;
165 } else {
166 Entry up = y.p, c = y;
167 for ( ; up != NIL && c == up.left; c = up, up = up.p );
168 return up;
169 }
170 }
171 }
172 return y;
173 }
174
175 protected Entry findCeiling(Entry x) {
176 Entry y = root;
177
178 while ( y != NIL ) {
179 int cmp = compare(x, y);
180 if (cmp == 0) {
181 return y;
182 } else if (cmp < 0) {
183 if (y.left != NIL)
184 y = y.left;
185 else
186 return y;
187 } else {
188 if (y.right != NIL) {
189 y = y.right;
190 } else {
191 Entry up = y.p, c = y;
192 for ( ; up != NIL && c == up.right; c = up, up = up.p );
193 return up;
194 }
195 }
196 }
197 return y;
198 }
199
200 protected Entry minimum(Entry x) {
201 for ( ; x.left != NIL; x = x.left );
202 return x;
203 }
204
205 protected Entry maximum(Entry x) {
206 for ( ; x.right != NIL; x = x.right );
207 return x;
208 }
209
210 protected Entry successor(Entry x) {
211 if ( x.right != NIL ) return minimum(x.right);
213
214 Entry y = x.p;
216 while ( y != NIL && x == y.right ) {
217 x = y;
218 y = y.p;
219 }
220 return y;
221 }
222
223 protected Entry predecessor(Entry x) {
224 if ( x.left != NIL ) return maximum(x.left);
226
227 Entry y = x.p;
229 while ( y != NIL && x == y.left ) {
230 x = y;
231 y = y.p;
232 }
233 return y;
234 }
235
236 protected void rotateLeft(Entry x) {
237 Entry y = x.right;
238 x.right = y.left;
239 if (y.left != NIL)
240 y.left.p = x;
241 y.p = x.p;
242 if (x.p == NIL)
243 root = y;
244 else if (x.p.left == x)
245 x.p.left = y;
246 else
247 x.p.right = y;
248 y.left = x;
249 x.p = y;
250 }
251
252 protected void rotateRight(Entry x) {
253 Entry y = x.left;
254 x.left = y.right;
255 if (y.right != NIL)
256 y.right.p = x;
257 y.p = x.p;
258 if (x.p == NIL)
259 root = y;
260 else if (x.p.right == x)
261 x.p.right = y;
262 else x.p.left = y;
263 y.right = x;
264 x.p = y;
265 }
266
267 protected void fixUpInsert(Entry x) {
268 x.color = RED;
269
270 while (x != NIL && x != root && x.p.color == RED) {
271 if (x.p == x.p.p.left) {
272 Entry y = x.p.p.right;
273 if (y.color == RED) {
274 x.p.color = BLACK;
275 y.color = BLACK;
276 x.p.p.color = RED;
277 x = x.p.p;
278 } else {
279 if (x == x.p.right) {
280 x = x.p;
281 rotateLeft(x);
282 }
283 x.p.color = BLACK;
284 x.p.p.color = RED;
285 if (x.p.p != NIL)
286 rotateRight(x.p.p);
287 }
288 } else {
289 Entry y = x.p.p.left;
291 if (y.color == RED) {
292 x.p.color = BLACK;
293 y.color = BLACK;
294 x.p.p.color = RED;
295 x = x.p.p;
296 } else {
297 if (x == x.p.left) {
298 x = x.p;
299 rotateRight(x);
300 }
301 x.p.color = BLACK;
302 x.p.p.color = RED;
303 if (x.p.p != NIL)
304 rotateLeft(x.p.p);
305 }
306 }
307 }
308 root.color = BLACK;
309 }
310
311 protected void fixUpRemove(Entry x) {
312 while (x != root && x.color == BLACK) {
313 if (x == x.p.left) {
314 Entry sib = x.p.right;
315
316 if (sib.color == RED) {
317 sib.color = BLACK;
318 x.p.color = RED;
319 rotateLeft(x.p);
320 sib = x.p.right;
321 }
322
323 if (sib.left.color == BLACK &&
324 sib.right.color == BLACK) {
325 sib.color = RED;
326 x = x.p;
327 } else {
328 if (sib.right.color == BLACK) {
329 sib.left.color = BLACK;
330 sib.color = RED;
331 rotateRight(sib);
332 sib = x.p.right;
333 }
334 sib.color = x.p.color;
335 x.p.color = BLACK;
336 sib.right.color = BLACK;
337 rotateLeft(x.p);
338 x = root;
339 }
340 } else {
341 Entry sib = x.p.left;
343
344 if (sib.color == RED) {
345 sib.color = BLACK;
346 x.p.color = RED;
347 rotateRight(x.p);
348 sib = x.p.left;
349 }
350
351 if (sib.right.color == BLACK &&
352 sib.left.color == BLACK) {
353 sib.color = RED;
354 x = x.p;
355 } else {
356 if (sib.left.color == BLACK) {
357 sib.right.color = BLACK;
358 sib.color = RED;
359 rotateLeft(sib);
360 sib = x.p.left;
361 }
362 sib.color = x.p.color;
363 x.p.color = BLACK;
364 sib.left.color = BLACK;
365 rotateRight(x.p);
366 x = root;
367 }
368 }
369 }
370
371 x.color = BLACK;
372 }
373
374 protected void remove(Entry z) {
375 boolean isUnique = !( z.keyEquals(z.left) ||
376 z.keyEquals(z.right) || z.keyEquals(z.p) );
377
378 Entry y = ( z.left != NIL && z.right != NIL ? successor(z) : z );
379 Entry x = ( y.left != NIL ? y.left : y.right );
380 x.p = y.p;
381
382 if (y.p == NIL) {
383 root = x;
384 } else if (y == y.p.left) {
385 y.p.left = x;
386 } else {
387 y.p.right = x;
388 }
389
390 if (y != z) {
391 z.copyFields(y);
392 }
393 if (y.color == BLACK)
394 fixUpRemove(x);
395
396 decrementSize(isUnique);
397 }
398
399
402
405 public static class Entry {
406 int val;
407 int order;
409 Entry left = null;
410 Entry right = null;
411 Entry p;
412 boolean color = BLACK;
413
414 public Entry(int val) {
415 this.val = val;
416 }
417
418 public Entry(int val, Entry parent, int order) {
419 this.val = val;
420 this.p = parent;
421 this.order = order;
422 this.left = NIL;
423 this.right = NIL;
424 }
425
426 public int getIntKey() {
427 throw new UnsupportedOperationException ("Unsupported");
428 }
429
430 public long getLongKey() {
431 throw new UnsupportedOperationException ("Unsupported");
432 }
433
434 public float getFloatKey() {
435 throw new UnsupportedOperationException ("Unsupported");
436 }
437
438 public double getDoubleKey() {
439 throw new UnsupportedOperationException ("Unsupported");
440 }
441
442 public Object getKey() {
443 return null;
444 }
445
446 public int getValue() {
447 return val;
448 }
449
450 public int getOrder() {
451 return order;
452 }
453
454 public int setValue(int value) {
455 int old = val;
456 val = value;
457 return old;
458 }
459
460 public boolean keyEquals(Entry e) {
461 Object k = getKey();
462 return ( k==null ? k==e.getKey() : k.equals(e.getKey()) );
463 }
464
465 public boolean equals(Object o) {
466 if (!(o instanceof Entry))
467 return false;
468
469 Entry e = (Entry)o;
470
471 return (val == e.val && getKey() == e.getKey());
472 }
473
474 public int hashCode() {
475 int khash = getKey().hashCode();
476 int vhash = val;
477 return khash^vhash;
478 }
479
480 public String toString() {
481 return getKey() + "=" + val;
482 }
483
484 public void copyFields(Entry x) {
485 this.val = x.val;
486 this.order = x.order;
487 }
488
489 }
490
491
494 protected class EntryIterator extends AbstractLiteralIterator {
495 private int expectedModCount = AbstractTreeMap.this.modCount;
496 private Entry lastReturned = NIL;
497 private boolean reverse = false;
498 Entry next, end;
499
500 EntryIterator(boolean reverse) {
501 next = reverse ? maximum(root) : minimum(root);
502 end = NIL;
503 }
504
505 EntryIterator(Entry first, Entry last) {
506 next = first;
507 end = last;
508 reverse = first==NIL ? true
509 : last==NIL ? false
510 : compare(first,last) > 0;
511 }
512
513 public boolean hasNext() {
514 return next != end;
515 }
516
517 final Entry nextEntry() {
518 if (!hasNext())
519 throw new NoSuchElementException ();
520 if (modCount != expectedModCount)
521 throw new ConcurrentModificationException ();
522 lastReturned = next;
523 next = reverse ? predecessor(next) : successor(next);
524 if ( lastReturned == NIL ) {
526 System.err.println("Encountered NIL in iteration!");
527 }
528 return lastReturned;
529 }
530
531 public Object next() {
532 return nextEntry();
533 }
534
535 public void remove() {
536 if (lastReturned == NIL)
537 throw new IllegalStateException ();
538 if (modCount != expectedModCount)
539 throw new ConcurrentModificationException ();
540 if (lastReturned.left != NIL && lastReturned.right != NIL)
541 next = lastReturned;
542 AbstractTreeMap.this.remove(lastReturned);
543 ++expectedModCount;
544 lastReturned = NIL;
545 }
546 }
547
548 protected class KeyIterator extends EntryIterator {
549 public KeyIterator() {
550 super(false);
551 }
552 public KeyIterator(Entry start, Entry end) {
553 super(start, end);
554 }
555 public Object next() {
556 return nextEntry().getKey();
557 }
558 }
559
560 protected class ValueIterator extends IntIterator {
561 EntryIterator m_iter;
562
563 public ValueIterator(EntryIterator iter) {
564 m_iter = iter;
565 }
566 public boolean hasNext() {
567 return m_iter.hasNext();
568 }
569 public int nextInt() {
570 return m_iter.nextEntry().val;
571 }
572 public void remove() {
573 m_iter.remove();
574 }
575 }
576
577 } |
Popular Tags |
Java API By Example, From Geeks To Geeks.