~ubuntu-branches/debian/squeeze/libcommons-collections-java/squeeze
» Revision
1
: src/java/org/apache/commons/collections/DoubleOrderedMap.java
« back to all changes in this revision
Viewing changes to src/java/org/apache/commons/collections/DoubleOrderedMap.java
- browse files at revision 1
- compare with another revision
- download diff
- download tarball
- view history from revision 1
- Committer: Bazaar Package Importer
- Author(s): Takashi Okamoto
- Date: 2004-08-07 00:02:50 UTC
- Revision ID: james.westby@ubuntu.com-20040807000250-hcnqvrdpxg95nmzr
Tags: upstream-2.1.1
Import upstream version 2.1.1
- files added:
- data
- data/test
- src
- src/conf
- src/java
- src/java/org
- src/java/org/apache
- src/java/org/apache/commons
- src/java/org/apache/commons/collections
- src/java/org/apache/commons/collections/comparators
- src/java/org/apache/commons/collections/iterators
- src/test
- src/test/org
- src/test/org/apache
- src/test/org/apache/commons
- src/test/org/apache/commons/collections
- src/test/org/apache/commons/collections/comparators
- src/test/org/apache/commons/collections/iterators
- xdocs
added
removed
src/java/org/apache/commons/collections/DoubleOrderedMap.java
1
/*
2
* Copyright 1999-2004 The Apache Software Foundation
3
*
4
* Licensed under the Apache License, Version 2.0 (the "License");
5
* you may not use this file except in compliance with the License.
6
* You may obtain a copy of the License at
7
*
8
* http://www.apache.org/licenses/LICENSE-2.0
9
*
10
* Unless required by applicable law or agreed to in writing, software
11
* distributed under the License is distributed on an "AS IS" BASIS,
12
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13
* See the License for the specific language governing permissions and
14
* limitations under the License.
15
*/
16
package org.apache.commons.collections;
17
18
19
20
import java.util.AbstractCollection;
21
import java.util.AbstractMap;
22
import java.util.AbstractSet;
23
import java.util.Collection;
24
import java.util.ConcurrentModificationException;
25
import java.util.Iterator;
26
import java.util.Map;
27
import java.util.NoSuchElementException;
28
import java.util.Set;
29
30
31
/**
32
* Red-Black tree-based implementation of Map. This class guarantees
33
* that the map will be in both ascending key order and ascending
34
* value order, sorted according to the natural order for the key's
35
* and value's classes.<p>
36
*
37
* This Map is intended for applications that need to be able to look
38
* up a key-value pairing by either key or value, and need to do so
39
* with equal efficiency.<p>
40
*
41
* While that goal could be accomplished by taking a pair of TreeMaps
42
* and redirecting requests to the appropriate TreeMap (e.g.,
43
* containsKey would be directed to the TreeMap that maps values to
44
* keys, containsValue would be directed to the TreeMap that maps keys
45
* to values), there are problems with that implementation,
46
* particularly when trying to keep the two TreeMaps synchronized with
47
* each other. And if the data contained in the TreeMaps is large, the
48
* cost of redundant storage becomes significant.<p>
49
*
50
* This solution keeps the data properly synchronized and minimizes
51
* the data storage. The red-black algorithm is based on TreeMap's,
52
* but has been modified to simultaneously map a tree node by key and
53
* by value. This doubles the cost of put operations (but so does
54
* using two TreeMaps), and nearly doubles the cost of remove
55
* operations (there is a savings in that the lookup of the node to be
56
* removed only has to be performed once). And since only one node
57
* contains the key and value, storage is significantly less than that
58
* required by two TreeMaps.<p>
59
*
60
* There are some limitations placed on data kept in this Map. The
61
* biggest one is this:<p>
62
*
63
* When performing a put operation, neither the key nor the value may
64
* already exist in the Map. In the java.util Map implementations
65
* (HashMap, TreeMap), you can perform a put with an already mapped
66
* key, and neither cares about duplicate values at all ... but this
67
* implementation's put method with throw an IllegalArgumentException
68
* if either the key or the value is already in the Map.<p>
69
*
70
* Obviously, that same restriction (and consequence of failing to
71
* heed that restriction) applies to the putAll method.<p>
72
*
73
* The Map.Entry instances returned by the appropriate methods will
74
* not allow setValue() and will throw an
75
* UnsupportedOperationException on attempts to call that method.<p>
76
*
77
* New methods are added to take advantage of the fact that values are
78
* kept sorted independently of their keys:<p>
79
*
80
* Object getKeyForValue(Object value) is the opposite of get; it
81
* takes a value and returns its key, if any.<p>
82
*
83
* Object removeValue(Object value) finds and removes the specified
84
* value and returns the now un-used key.<p>
85
*
86
* Set entrySetByValue() returns the Map.Entry's in a Set whose
87
* iterator will iterate over the Map.Entry's in ascending order by
88
* their corresponding values.<p>
89
*
90
* Set keySetByValue() returns the keys in a Set whose iterator will
91
* iterate over the keys in ascending order by their corresponding
92
* values.<p>
93
*
94
* Collection valuesByValue() returns the values in a Collection whose
95
* iterator will iterate over the values in ascending order.<p>
96
*
97
* @since 2.0
98
* @author Marc Johnson (marcj at users dot sourceforge dot net)
99
*/
100
101
// final for performance
102
public final class DoubleOrderedMap extends AbstractMap {
103
104
private Node[] rootNode = new Node[]{ null,
105
null };
106
private int nodeCount = 0;
107
private int modifications = 0;
108
private Set[] setOfKeys = new Set[]{ null,
109
null };
110
private Set[] setOfEntries = new Set[]{ null,
111
null };
112
private Collection[] collectionOfValues = new Collection[]{
113
null,
114
115
null };
116
private static final int KEY = 0;
117
private static final int VALUE = 1;
118
private static final int SUM_OF_INDICES = KEY + VALUE;
119
private static final int FIRST_INDEX = 0;
120
private static final int NUMBER_OF_INDICES = 2;
121
private static final String[] dataName = new String[]{ "key",
122
"value"
123
};
124
125
/**
126
* Construct a new DoubleOrderedMap
127
*/
128
public DoubleOrderedMap() {}
129
130
/**
131
* Constructs a new DoubleOrderedMap from an existing Map, with keys and
132
* values sorted
133
*
134
* @param map the map whose mappings are to be placed in this map.
135
*
136
* @exception ClassCastException if the keys in the map are not
137
* Comparable, or are not mutually
138
* comparable; also if the values in
139
* the map are not Comparable, or
140
* are not mutually Comparable
141
* @exception NullPointerException if any key or value in the map
142
* is null
143
* @exception IllegalArgumentException if there are duplicate keys
144
* or duplicate values in the
145
* map
146
*/
147
public DoubleOrderedMap(final Map map)
148
throws ClassCastException, NullPointerException,
149
IllegalArgumentException {
150
putAll(map);
151
}
152
153
/**
154
* Returns the key to which this map maps the specified value.
155
* Returns null if the map contains no mapping for this value.
156
*
157
* @param value value whose associated key is to be returned.
158
*
159
* @return the key to which this map maps the specified value, or
160
* null if the map contains no mapping for this value.
161
*
162
* @exception ClassCastException if the value is of an
163
* inappropriate type for this map.
164
* @exception NullPointerException if the value is null
165
*/
166
public Object getKeyForValue(final Object value)
167
throws ClassCastException, NullPointerException {
168
return doGet((Comparable) value, VALUE);
169
}
170
171
/**
172
* Removes the mapping for this value from this map if present
173
*
174
* @param value value whose mapping is to be removed from the map.
175
*
176
* @return previous key associated with specified value, or null
177
* if there was no mapping for value.
178
*/
179
public Object removeValue(final Object value) {
180
return doRemove((Comparable) value, VALUE);
181
}
182
183
/**
184
* Returns a set view of the mappings contained in this map. Each
185
* element in the returned set is a Map.Entry. The set is backed
186
* by the map, so changes to the map are reflected in the set, and
187
* vice-versa. If the map is modified while an iteration over the
188
* set is in progress, the results of the iteration are
189
* undefined. The set supports element removal, which removes the
190
* corresponding mapping from the map, via the Iterator.remove,
191
* Set.remove, removeAll, retainAll and clear operations. It does
192
* not support the add or addAll operations.<p>
193
*
194
* The difference between this method and entrySet is that
195
* entrySet's iterator() method returns an iterator that iterates
196
* over the mappings in ascending order by key. This method's
197
* iterator method iterates over the mappings in ascending order
198
* by value.
199
*
200
* @return a set view of the mappings contained in this map.
201
*/
202
public Set entrySetByValue() {
203
204
if (setOfEntries[VALUE] == null) {
205
setOfEntries[VALUE] = new AbstractSet() {
206
207
public Iterator iterator() {
208
209
return new DoubleOrderedMapIterator(VALUE) {
210
211
protected Object doGetNext() {
212
return lastReturnedNode;
213
}
214
};
215
}
216
217
public boolean contains(Object o) {
218
219
if (!(o instanceof Map.Entry)) {
220
return false;
221
}
222
223
Map.Entry entry = (Map.Entry) o;
224
Object key = entry.getKey();
225
Node node = lookup((Comparable) entry.getValue(),
226
VALUE);
227
228
return (node != null) && node.getData(KEY).equals(key);
229
}
230
231
public boolean remove(Object o) {
232
233
if (!(o instanceof Map.Entry)) {
234
return false;
235
}
236
237
Map.Entry entry = (Map.Entry) o;
238
Object key = entry.getKey();
239
Node node = lookup((Comparable) entry.getValue(),
240
VALUE);
241
242
if ((node != null) && node.getData(KEY).equals(key)) {
243
doRedBlackDelete(node);
244
245
return true;
246
}
247
248
return false;
249
}
250
251
public int size() {
252
return DoubleOrderedMap.this.size();
253
}
254
255
public void clear() {
256
DoubleOrderedMap.this.clear();
257
}
258
};
259
}
260
261
return setOfEntries[VALUE];
262
}
263
264
/**
265
* Returns a set view of the keys contained in this map. The set
266
* is backed by the map, so changes to the map are reflected in
267
* the set, and vice-versa. If the map is modified while an
268
* iteration over the set is in progress, the results of the
269
* iteration are undefined. The set supports element removal,
270
* which removes the corresponding mapping from the map, via the
271
* Iterator.remove, Set.remove, removeAll, retainAll, and clear
272
* operations. It does not support the add or addAll
273
* operations.<p>
274
*
275
* The difference between this method and keySet is that keySet's
276
* iterator() method returns an iterator that iterates over the
277
* keys in ascending order by key. This method's iterator method
278
* iterates over the keys in ascending order by value.
279
*
280
* @return a set view of the keys contained in this map.
281
*/
282
public Set keySetByValue() {
283
284
if (setOfKeys[VALUE] == null) {
285
setOfKeys[VALUE] = new AbstractSet() {
286
287
public Iterator iterator() {
288
289
return new DoubleOrderedMapIterator(VALUE) {
290
291
protected Object doGetNext() {
292
return lastReturnedNode.getData(KEY);
293
}
294
};
295
}
296
297
public int size() {
298
return DoubleOrderedMap.this.size();
299
}
300
301
public boolean contains(Object o) {
302
return containsKey(o);
303
}
304
305
public boolean remove(Object o) {
306
307
int oldnodeCount = nodeCount;
308
309
DoubleOrderedMap.this.remove(o);
310
311
return nodeCount != oldnodeCount;
312
}
313
314
public void clear() {
315
DoubleOrderedMap.this.clear();
316
}
317
};
318
}
319
320
return setOfKeys[VALUE];
321
}
322
323
/**
324
* Returns a collection view of the values contained in this
325
* map. The collection is backed by the map, so changes to the map
326
* are reflected in the collection, and vice-versa. If the map is
327
* modified while an iteration over the collection is in progress,
328
* the results of the iteration are undefined. The collection
329
* supports element removal, which removes the corresponding
330
* mapping from the map, via the Iterator.remove,
331
* Collection.remove, removeAll, retainAll and clear operations.
332
* It does not support the add or addAll operations.<p>
333
*
334
* The difference between this method and values is that values's
335
* iterator() method returns an iterator that iterates over the
336
* values in ascending order by key. This method's iterator method
337
* iterates over the values in ascending order by key.
338
*
339
* @return a collection view of the values contained in this map.
340
*/
341
public Collection valuesByValue() {
342
343
if (collectionOfValues[VALUE] == null) {
344
collectionOfValues[VALUE] = new AbstractCollection() {
345
346
public Iterator iterator() {
347
348
return new DoubleOrderedMapIterator(VALUE) {
349
350
protected Object doGetNext() {
351
return lastReturnedNode.getData(VALUE);
352
}
353
};
354
}
355
356
public int size() {
357
return DoubleOrderedMap.this.size();
358
}
359
360
public boolean contains(Object o) {
361
return containsValue(o);
362
}
363
364
public boolean remove(Object o) {
365
366
int oldnodeCount = nodeCount;
367
368
removeValue(o);
369
370
return nodeCount != oldnodeCount;
371
}
372
373
public boolean removeAll(Collection c) {
374
375
boolean modified = false;
376
Iterator iter = c.iterator();
377
378
while (iter.hasNext()) {
379
if (removeValue(iter.next()) != null) {
380
modified = true;
381
}
382
}
383
384
return modified;
385
}
386
387
public void clear() {
388
DoubleOrderedMap.this.clear();
389
}
390
};
391
}
392
393
return collectionOfValues[VALUE];
394
}
395
396
/**
397
* common remove logic (remove by key or remove by value)
398
*
399
* @param o the key, or value, that we're looking for
400
* @param index KEY or VALUE
401
*
402
* @return the key, if remove by value, or the value, if remove by
403
* key. null if the specified key or value could not be
404
* found
405
*/
406
private Object doRemove(final Comparable o, final int index) {
407
408
Node node = lookup(o, index);
409
Object rval = null;
410
411
if (node != null) {
412
rval = node.getData(oppositeIndex(index));
413
414
doRedBlackDelete(node);
415
}
416
417
return rval;
418
}
419
420
/**
421
* common get logic, used to get by key or get by value
422
*
423
* @param o the key or value that we're looking for
424
* @param index KEY or VALUE
425
*
426
* @return the key (if the value was mapped) or the value (if the
427
* key was mapped); null if we couldn't find the specified
428
* object
429
*/
430
private Object doGet(final Comparable o, final int index) {
431
432
checkNonNullComparable(o, index);
433
434
Node node = lookup(o, index);
435
436
return ((node == null)
437
? null
438
: node.getData(oppositeIndex(index)));
439
}
440
441
/**
442
* Get the opposite index of the specified index
443
*
444
* @param index KEY or VALUE
445
*
446
* @return VALUE (if KEY was specified), else KEY
447
*/
448
private int oppositeIndex(final int index) {
449
450
// old trick ... to find the opposite of a value, m or n,
451
// subtract the value from the sum of the two possible
452
// values. (m + n) - m = n; (m + n) - n = m
453
return SUM_OF_INDICES - index;
454
}
455
456
/**
457
* do the actual lookup of a piece of data
458
*
459
* @param data the key or value to be looked up
460
* @param index KEY or VALUE
461
*
462
* @return the desired Node, or null if there is no mapping of the
463
* specified data
464
*/
465
private Node lookup(final Comparable data, final int index) {
466
467
Node rval = null;
468
Node node = rootNode[index];
469
470
while (node != null) {
471
int cmp = compare(data, node.getData(index));
472
473
if (cmp == 0) {
474
rval = node;
475
476
break;
477
} else {
478
node = (cmp < 0)
479
? node.getLeft(index)
480
: node.getRight(index);
481
}
482
}
483
484
return rval;
485
}
486
487
/**
488
* Compare two objects
489
*
490
* @param o1 the first object
491
* @param o2 the second object
492
*
493
* @return negative value if o1 < o2; 0 if o1 == o2; positive
494
* value if o1 > o2
495
*/
496
private static int compare(final Comparable o1, final Comparable o2) {
497
return ((Comparable) o1).compareTo(o2);
498
}
499
500
/**
501
* find the least node from a given node. very useful for starting
502
* a sorting iterator ...
503
*
504
* @param node the node from which we will start searching
505
* @param index KEY or VALUE
506
*
507
* @return the smallest node, from the specified node, in the
508
* specified mapping
509
*/
510
private static Node leastNode(final Node node, final int index) {
511
512
Node rval = node;
513
514
if (rval != null) {
515
while (rval.getLeft(index) != null) {
516
rval = rval.getLeft(index);
517
}
518
}
519
520
return rval;
521
}
522
523
/**
524
* get the next larger node from the specified node
525
*
526
* @param node the node to be searched from
527
* @param index KEY or VALUE
528
*
529
* @return the specified node
530
*/
531
private Node nextGreater(final Node node, final int index) {
532
533
Node rval = null;
534
535
if (node == null) {
536
rval = null;
537
} else if (node.getRight(index) != null) {
538
539
// everything to the node's right is larger. The least of
540
// the right node's descendents is the next larger node
541
rval = leastNode(node.getRight(index), index);
542
} else {
543
544
// traverse up our ancestry until we find an ancestor that
545
// is null or one whose left child is our ancestor. If we
546
// find a null, then this node IS the largest node in the
547
// tree, and there is no greater node. Otherwise, we are
548
// the largest node in the subtree on that ancestor's left
549
// ... and that ancestor is the next greatest node
550
Node parent = node.getParent(index);
551
Node child = node;
552
553
while ((parent != null) && (child == parent.getRight(index))) {
554
child = parent;
555
parent = parent.getParent(index);
556
}
557
558
rval = parent;
559
}
560
561
return rval;
562
}
563
564
/**
565
* copy the color from one node to another, dealing with the fact
566
* that one or both nodes may, in fact, be null
567
*
568
* @param from the node whose color we're copying; may be null
569
* @param to the node whose color we're changing; may be null
570
* @param index KEY or VALUE
571
*/
572
private static void copyColor(final Node from, final Node to,
573
final int index) {
574
575
if (to != null) {
576
if (from == null) {
577
578
// by default, make it black
579
to.setBlack(index);
580
} else {
581
to.copyColor(from, index);
582
}
583
}
584
}
585
586
/**
587
* is the specified node red? if the node does not exist, no, it's
588
* black, thank you
589
*
590
* @param node the node (may be null) in question
591
* @param index KEY or VALUE
592
*/
593
private static boolean isRed(final Node node, final int index) {
594
595
return ((node == null)
596
? false
597
: node.isRed(index));
598
}
599
600
/**
601
* is the specified black red? if the node does not exist, sure,
602
* it's black, thank you
603
*
604
* @param node the node (may be null) in question
605
* @param index KEY or VALUE
606
*/
607
private static boolean isBlack(final Node node, final int index) {
608
609
return ((node == null)
610
? true
611
: node.isBlack(index));
612
}
613
614
/**
615
* force a node (if it exists) red
616
*
617
* @param node the node (may be null) in question
618
* @param index KEY or VALUE
619
*/
620
private static void makeRed(final Node node, final int index) {
621
622
if (node != null) {
623
node.setRed(index);
624
}
625
}
626
627
/**
628
* force a node (if it exists) black
629
*
630
* @param node the node (may be null) in question
631
* @param index KEY or VALUE
632
*/
633
private static void makeBlack(final Node node, final int index) {
634
635
if (node != null) {
636
node.setBlack(index);
637
}
638
}
639
640
/**
641
* get a node's grandparent. mind you, the node, its parent, or
642
* its grandparent may not exist. no problem
643
*
644
* @param node the node (may be null) in question
645
* @param index KEY or VALUE
646
*/
647
private static Node getGrandParent(final Node node, final int index) {
648
return getParent(getParent(node, index), index);
649
}
650
651
/**
652
* get a node's parent. mind you, the node, or its parent, may not
653
* exist. no problem
654
*
655
* @param node the node (may be null) in question
656
* @param index KEY or VALUE
657
*/
658
private static Node getParent(final Node node, final int index) {
659
660
return ((node == null)
661
? null
662
: node.getParent(index));
663
}
664
665
/**
666
* get a node's right child. mind you, the node may not exist. no
667
* problem
668
*
669
* @param node the node (may be null) in question
670
* @param index KEY or VALUE
671
*/
672
private static Node getRightChild(final Node node, final int index) {
673
674
return (node == null)
675
? null
676
: node.getRight(index);
677
}
678
679
/**
680
* get a node's left child. mind you, the node may not exist. no
681
* problem
682
*
683
* @param node the node (may be null) in question
684
* @param index KEY or VALUE
685
*/
686
private static Node getLeftChild(final Node node, final int index) {
687
688
return (node == null)
689
? null
690
: node.getLeft(index);
691
}
692
693
/**
694
* is this node its parent's left child? mind you, the node, or
695
* its parent, may not exist. no problem. if the node doesn't
696
* exist ... it's its non-existent parent's left child. If the
697
* node does exist but has no parent ... no, we're not the
698
* non-existent parent's left child. Otherwise (both the specified
699
* node AND its parent exist), check.
700
*
701
* @param node the node (may be null) in question
702
* @param index KEY or VALUE
703
*/
704
private static boolean isLeftChild(final Node node, final int index) {
705
706
return (node == null)
707
? true
708
: ((node.getParent(index) == null)
709
? false
710
: (node == node.getParent(index).getLeft(index)));
711
}
712
713
/**
714
* is this node its parent's right child? mind you, the node, or
715
* its parent, may not exist. no problem. if the node doesn't
716
* exist ... it's its non-existent parent's right child. If the
717
* node does exist but has no parent ... no, we're not the
718
* non-existent parent's right child. Otherwise (both the
719
* specified node AND its parent exist), check.
720
*
721
* @param node the node (may be null) in question
722
* @param index KEY or VALUE
723
*/
724
private static boolean isRightChild(final Node node, final int index) {
725
726
return (node == null)
727
? true
728
: ((node.getParent(index) == null)
729
? false
730
: (node == node.getParent(index).getRight(index)));
731
}
732
733
/**
734
* do a rotate left. standard fare in the world of balanced trees
735
*
736
* @param node the node to be rotated
737
* @param index KEY or VALUE
738
*/
739
private void rotateLeft(final Node node, final int index) {
740
741
Node rightChild = node.getRight(index);
742
743
node.setRight(rightChild.getLeft(index), index);
744
745
if (rightChild.getLeft(index) != null) {
746
rightChild.getLeft(index).setParent(node, index);
747
}
748
749
rightChild.setParent(node.getParent(index), index);
750
751
if (node.getParent(index) == null) {
752
753
// node was the root ... now its right child is the root
754
rootNode[index] = rightChild;
755
} else if (node.getParent(index).getLeft(index) == node) {
756
node.getParent(index).setLeft(rightChild, index);
757
} else {
758
node.getParent(index).setRight(rightChild, index);
759
}
760
761
rightChild.setLeft(node, index);
762
node.setParent(rightChild, index);
763
}
764
765
/**
766
* do a rotate right. standard fare in the world of balanced trees
767
*
768
* @param node the node to be rotated
769
* @param index KEY or VALUE
770
*/
771
private void rotateRight(final Node node, final int index) {
772
773
Node leftChild = node.getLeft(index);
774
775
node.setLeft(leftChild.getRight(index), index);
776
777
if (leftChild.getRight(index) != null) {
778
leftChild.getRight(index).setParent(node, index);
779
}
780
781
leftChild.setParent(node.getParent(index), index);
782
783
if (node.getParent(index) == null) {
784
785
// node was the root ... now its left child is the root
786
rootNode[index] = leftChild;
787
} else if (node.getParent(index).getRight(index) == node) {
788
node.getParent(index).setRight(leftChild, index);
789
} else {
790
node.getParent(index).setLeft(leftChild, index);
791
}
792
793
leftChild.setRight(node, index);
794
node.setParent(leftChild, index);
795
}
796
797
/**
798
* complicated red-black insert stuff. Based on Sun's TreeMap
799
* implementation, though it's barely recognizeable any more
800
*
801
* @param insertedNode the node to be inserted
802
* @param index KEY or VALUE
803
*/
804
private void doRedBlackInsert(final Node insertedNode, final int index)
805
{
806
807
Node currentNode = insertedNode;
808
809
makeRed(currentNode, index);
810
811
while ((currentNode != null) && (currentNode != rootNode[index])
812
&& (isRed(currentNode.getParent(index), index))) {
813
if (isLeftChild(getParent(currentNode, index), index)) {
814
Node y = getRightChild(getGrandParent(currentNode, index),
815
index);
816
817
if (isRed(y, index)) {
818
makeBlack(getParent(currentNode, index), index);
819
makeBlack(y, index);
820
makeRed(getGrandParent(currentNode, index), index);
821
822
currentNode = getGrandParent(currentNode, index);
823
} else {
824
if (isRightChild(currentNode, index)) {
825
currentNode = getParent(currentNode, index);
826
827
rotateLeft(currentNode, index);
828
}
829
830
makeBlack(getParent(currentNode, index), index);
831
makeRed(getGrandParent(currentNode, index), index);
832
833
if (getGrandParent(currentNode, index) != null) {
834
rotateRight(getGrandParent(currentNode, index),
835
index);
836
}
837
}
838
} else {
839
840
// just like clause above, except swap left for right
841
Node y = getLeftChild(getGrandParent(currentNode, index),
842
index);
843
844
if (isRed(y, index)) {
845
makeBlack(getParent(currentNode, index), index);
846
makeBlack(y, index);
847
makeRed(getGrandParent(currentNode, index), index);
848
849
currentNode = getGrandParent(currentNode, index);
850
} else {
851
if (isLeftChild(currentNode, index)) {
852
currentNode = getParent(currentNode, index);
853
854
rotateRight(currentNode, index);
855
}
856
857
makeBlack(getParent(currentNode, index), index);
858
makeRed(getGrandParent(currentNode, index), index);
859
860
if (getGrandParent(currentNode, index) != null) {
861
rotateLeft(getGrandParent(currentNode, index),
862
index);
863
}
864
}
865
}
866
}
867
868
makeBlack(rootNode[index], index);
869
}
870
871
/**
872
* complicated red-black delete stuff. Based on Sun's TreeMap
873
* implementation, though it's barely recognizeable any more
874
*
875
* @param deletedNode the node to be deleted
876
*/
877
private void doRedBlackDelete(final Node deletedNode) {
878
879
for (int index = FIRST_INDEX; index < NUMBER_OF_INDICES; index++) {
880
881
// if deleted node has both left and children, swap with
882
// the next greater node
883
if ((deletedNode.getLeft(index) != null)
884
&& (deletedNode.getRight(index) != null)) {
885
swapPosition(nextGreater(deletedNode, index), deletedNode,
886
index);
887
}
888
889
Node replacement = ((deletedNode.getLeft(index) != null)
890
? deletedNode.getLeft(index)
891
: deletedNode.getRight(index));
892
893
if (replacement != null) {
894
replacement.setParent(deletedNode.getParent(index), index);
895
896
if (deletedNode.getParent(index) == null) {
897
rootNode[index] = replacement;
898
} else if (deletedNode
899
== deletedNode.getParent(index).getLeft(index)) {
900
deletedNode.getParent(index).setLeft(replacement,
901
index);
902
} else {
903
deletedNode.getParent(index).setRight(replacement,
904
index);
905
}
906
907
deletedNode.setLeft(null, index);
908
deletedNode.setRight(null, index);
909
deletedNode.setParent(null, index);
910
911
if (isBlack(deletedNode, index)) {
912
doRedBlackDeleteFixup(replacement, index);
913
}
914
} else {
915
916
// replacement is null
917
if (deletedNode.getParent(index) == null) {
918
919
// empty tree
920
rootNode[index] = null;
921
} else {
922
923
// deleted node had no children
924
if (isBlack(deletedNode, index)) {
925
doRedBlackDeleteFixup(deletedNode, index);
926
}
927
928
if (deletedNode.getParent(index) != null) {
929
if (deletedNode
930
== deletedNode.getParent(index)
931
.getLeft(index)) {
932
deletedNode.getParent(index).setLeft(null,
933
index);
934
} else {
935
deletedNode.getParent(index).setRight(null,
936
index);
937
}
938
939
deletedNode.setParent(null, index);
940
}
941
}
942
}
943
}
944
945
shrink();
946
}
947
948
/**
949
* complicated red-black delete stuff. Based on Sun's TreeMap
950
* implementation, though it's barely recognizeable any more. This
951
* rebalances the tree (somewhat, as red-black trees are not
952
* perfectly balanced -- perfect balancing takes longer)
953
*
954
* @param replacementNode the node being replaced
955
* @param index KEY or VALUE
956
*/
957
private void doRedBlackDeleteFixup(final Node replacementNode,
958
final int index) {
959
960
Node currentNode = replacementNode;
961
962
while ((currentNode != rootNode[index])
963
&& (isBlack(currentNode, index))) {
964
if (isLeftChild(currentNode, index)) {
965
Node siblingNode =
966
getRightChild(getParent(currentNode, index), index);
967
968
if (isRed(siblingNode, index)) {
969
makeBlack(siblingNode, index);
970
makeRed(getParent(currentNode, index), index);
971
rotateLeft(getParent(currentNode, index), index);
972
973
siblingNode = getRightChild(getParent(currentNode,
974
index),
975
index);
976
}
977
978
if (isBlack(getLeftChild(siblingNode, index), index)
979
&& isBlack(getRightChild(siblingNode, index),
980
index)) {
981
makeRed(siblingNode, index);
982
983
currentNode = getParent(currentNode, index);
984
} else {
985
if (isBlack(getRightChild(siblingNode, index), index)) {
986
makeBlack(getLeftChild(siblingNode, index), index);
987
makeRed(siblingNode, index);
988
rotateRight(siblingNode, index);
989
990
siblingNode =
991
getRightChild(getParent(currentNode, index),
992
index);
993
}
994
995
copyColor(getParent(currentNode, index), siblingNode,
996
index);
997
makeBlack(getParent(currentNode, index), index);
998
makeBlack(getRightChild(siblingNode, index), index);
999
rotateLeft(getParent(currentNode, index), index);
1000
1001
currentNode = rootNode[index];
1002
}
1003
} else {
1004
Node siblingNode = getLeftChild(getParent(currentNode,
1005
index),
1006
index);
1007
1008
if (isRed(siblingNode, index)) {
1009
makeBlack(siblingNode, index);
1010
makeRed(getParent(currentNode, index), index);
1011
rotateRight(getParent(currentNode, index), index);
1012
1013
siblingNode = getLeftChild(getParent(currentNode,
1014
index),
1015
index);
1016
}
1017
1018
if (isBlack(getRightChild(siblingNode, index), index)
1019
&& isBlack(getLeftChild(siblingNode, index), index))
1020
{
1021
makeRed(siblingNode, index);
1022
1023
currentNode = getParent(currentNode, index);
1024
} else {
1025
if (isBlack(getLeftChild(siblingNode, index), index)) {
1026
makeBlack(getRightChild(siblingNode, index), index);
1027
makeRed(siblingNode, index);
1028
rotateLeft(siblingNode, index);
1029
1030
siblingNode =
1031
getLeftChild(getParent(currentNode, index),
1032
index);
1033
}
1034
1035
copyColor(getParent(currentNode, index), siblingNode,
1036
index);
1037
makeBlack(getParent(currentNode, index), index);
1038
makeBlack(getLeftChild(siblingNode, index), index);
1039
rotateRight(getParent(currentNode, index), index);
1040
1041
currentNode = rootNode[index];
1042
}
1043
}
1044
}
1045
1046
makeBlack(currentNode, index);
1047
}
1048
1049
/**
1050
* swap two nodes (except for their content), taking care of
1051
* special cases where one is the other's parent ... hey, it
1052
* happens.
1053
*
1054
* @param x one node
1055
* @param y another node
1056
* @param index KEY or VALUE
1057
*/
1058
private void swapPosition(final Node x, final Node y, final int index) {
1059
1060
// Save initial values.
1061
Node xFormerParent = x.getParent(index);
1062
Node xFormerLeftChild = x.getLeft(index);
1063
Node xFormerRightChild = x.getRight(index);
1064
Node yFormerParent = y.getParent(index);
1065
Node yFormerLeftChild = y.getLeft(index);
1066
Node yFormerRightChild = y.getRight(index);
1067
boolean xWasLeftChild =
1068
(x.getParent(index) != null)
1069
&& (x == x.getParent(index).getLeft(index));
1070
boolean yWasLeftChild =
1071
(y.getParent(index) != null)
1072
&& (y == y.getParent(index).getLeft(index));
1073
1074
// Swap, handling special cases of one being the other's parent.
1075
if (x == yFormerParent) { // x was y's parent
1076
x.setParent(y, index);
1077
1078
if (yWasLeftChild) {
1079
y.setLeft(x, index);
1080
y.setRight(xFormerRightChild, index);
1081
} else {
1082
y.setRight(x, index);
1083
y.setLeft(xFormerLeftChild, index);
1084
}
1085
} else {
1086
x.setParent(yFormerParent, index);
1087
1088
if (yFormerParent != null) {
1089
if (yWasLeftChild) {
1090
yFormerParent.setLeft(x, index);
1091
} else {
1092
yFormerParent.setRight(x, index);
1093
}
1094
}
1095
1096
y.setLeft(xFormerLeftChild, index);
1097
y.setRight(xFormerRightChild, index);
1098
}
1099
1100
if (y == xFormerParent) { // y was x's parent
1101
y.setParent(x, index);
1102
1103
if (xWasLeftChild) {
1104
x.setLeft(y, index);
1105
x.setRight(yFormerRightChild, index);
1106
} else {
1107
x.setRight(y, index);
1108
x.setLeft(yFormerLeftChild, index);
1109
}
1110
} else {
1111
y.setParent(xFormerParent, index);
1112
1113
if (xFormerParent != null) {
1114
if (xWasLeftChild) {
1115
xFormerParent.setLeft(y, index);
1116
} else {
1117
xFormerParent.setRight(y, index);
1118
}
1119
}
1120
1121
x.setLeft(yFormerLeftChild, index);
1122
x.setRight(yFormerRightChild, index);
1123
}
1124
1125
// Fix children's parent pointers
1126
if (x.getLeft(index) != null) {
1127
x.getLeft(index).setParent(x, index);
1128
}
1129
1130
if (x.getRight(index) != null) {
1131
x.getRight(index).setParent(x, index);
1132
}
1133
1134
if (y.getLeft(index) != null) {
1135
y.getLeft(index).setParent(y, index);
1136
}
1137
1138
if (y.getRight(index) != null) {
1139
y.getRight(index).setParent(y, index);
1140
}
1141
1142
x.swapColors(y, index);
1143
1144
// Check if root changed
1145
if (rootNode[index] == x) {
1146
rootNode[index] = y;
1147
} else if (rootNode[index] == y) {
1148
rootNode[index] = x;
1149
}
1150
}
1151
1152
/**
1153
* check if an object is fit to be proper input ... has to be
1154
* Comparable and non-null
1155
*
1156
* @param o the object being checked
1157
* @param index KEY or VALUE (used to put the right word in the
1158
* exception message)
1159
*
1160
* @exception NullPointerException if o is null
1161
* @exception ClassCastException if o is not Comparable
1162
*/
1163
private static void checkNonNullComparable(final Object o,
1164
final int index) {
1165
1166
if (o == null) {
1167
throw new NullPointerException(dataName[index]
1168
+ " cannot be null");
1169
}
1170
1171
if (!(o instanceof Comparable)) {
1172
throw new ClassCastException(dataName[index]
1173
+ " must be Comparable");
1174
}
1175
}
1176
1177
/**
1178
* check a key for validity (non-null and implements Comparable)
1179
*
1180
* @param key the key to be checked
1181
*
1182
* @exception NullPointerException if key is null
1183
* @exception ClassCastException if key is not Comparable
1184
*/
1185
private static void checkKey(final Object key) {
1186
checkNonNullComparable(key, KEY);
1187
}
1188
1189
/**
1190
* check a value for validity (non-null and implements Comparable)
1191
*
1192
* @param value the value to be checked
1193
*
1194
* @exception NullPointerException if value is null
1195
* @exception ClassCastException if value is not Comparable
1196
*/
1197
private static void checkValue(final Object value) {
1198
checkNonNullComparable(value, VALUE);
1199
}
1200
1201
/**
1202
* check a key and a value for validity (non-null and implements
1203
* Comparable)
1204
*
1205
* @param key the key to be checked
1206
* @param value the value to be checked
1207
*
1208
* @exception NullPointerException if key or value is null
1209
* @exception ClassCastException if key or value is not Comparable
1210
*/
1211
private static void checkKeyAndValue(final Object key,
1212
final Object value) {
1213
checkKey(key);
1214
checkValue(value);
1215
}
1216
1217
/**
1218
* increment the modification count -- used to check for
1219
* concurrent modification of the map through the map and through
1220
* an Iterator from one of its Set or Collection views
1221
*/
1222
private void modify() {
1223
modifications++;
1224
}
1225
1226
/**
1227
* bump up the size and note that the map has changed
1228
*/
1229
private void grow() {
1230
1231
modify();
1232
1233
nodeCount++;
1234
}
1235
1236
/**
1237
* decrement the size and note that the map has changed
1238
*/
1239
private void shrink() {
1240
1241
modify();
1242
1243
nodeCount--;
1244
}
1245
1246
/**
1247
* insert a node by its value
1248
*
1249
* @param newNode the node to be inserted
1250
*
1251
* @exception IllegalArgumentException if the node already exists
1252
* in the value mapping
1253
*/
1254
private void insertValue(final Node newNode)
1255
throws IllegalArgumentException {
1256
1257
Node node = rootNode[VALUE];
1258
1259
while (true) {
1260
int cmp = compare(newNode.getData(VALUE), node.getData(VALUE));
1261
1262
if (cmp == 0) {
1263
throw new IllegalArgumentException(
1264
"Cannot store a duplicate value (\""
1265
+ newNode.getData(VALUE) + "\") in this Map");
1266
} else if (cmp < 0) {
1267
if (node.getLeft(VALUE) != null) {
1268
node = node.getLeft(VALUE);
1269
} else {
1270
node.setLeft(newNode, VALUE);
1271
newNode.setParent(node, VALUE);
1272
doRedBlackInsert(newNode, VALUE);
1273
1274
break;
1275
}
1276
} else { // cmp > 0
1277
if (node.getRight(VALUE) != null) {
1278
node = node.getRight(VALUE);
1279
} else {
1280
node.setRight(newNode, VALUE);
1281
newNode.setParent(node, VALUE);
1282
doRedBlackInsert(newNode, VALUE);
1283
1284
break;
1285
}
1286
}
1287
}
1288
}
1289
1290
/* ********** START implementation of Map ********** */
1291
1292
/**
1293
* Returns the number of key-value mappings in this map. If the
1294
* map contains more than Integer.MAXVALUE elements, returns
1295
* Integer.MAXVALUE.
1296
*
1297
* @return the number of key-value mappings in this map.
1298
*/
1299
public int size() {
1300
return nodeCount;
1301
}
1302
1303
/**
1304
* Returns true if this map contains a mapping for the specified
1305
* key.
1306
*
1307
* @param key key whose presence in this map is to be tested.
1308
*
1309
* @return true if this map contains a mapping for the specified
1310
* key.
1311
*
1312
* @exception ClassCastException if the key is of an inappropriate
1313
* type for this map.
1314
* @exception NullPointerException if the key is null
1315
*/
1316
public boolean containsKey(final Object key)
1317
throws ClassCastException, NullPointerException {
1318
1319
checkKey(key);
1320
1321
return lookup((Comparable) key, KEY) != null;
1322
}
1323
1324
/**
1325
* Returns true if this map maps one or more keys to the
1326
* specified value.
1327
*
1328
* @param value value whose presence in this map is to be tested.
1329
*
1330
* @return true if this map maps one or more keys to the specified
1331
* value.
1332
*/
1333
public boolean containsValue(final Object value) {
1334
1335
checkValue(value);
1336
1337
return lookup((Comparable) value, VALUE) != null;
1338
}
1339
1340
/**
1341
* Returns the value to which this map maps the specified
1342
* key. Returns null if the map contains no mapping for this key.
1343
*
1344
* @param key key whose associated value is to be returned.
1345
*
1346
* @return the value to which this map maps the specified key, or
1347
* null if the map contains no mapping for this key.
1348
*
1349
* @exception ClassCastException if the key is of an inappropriate
1350
* type for this map.
1351
* @exception NullPointerException if the key is null
1352
*/
1353
public Object get(final Object key)
1354
throws ClassCastException, NullPointerException {
1355
return doGet((Comparable) key, KEY);
1356
}
1357
1358
/**
1359
* Associates the specified value with the specified key in this
1360
* map.
1361
*
1362
* @param key key with which the specified value is to be
1363
* associated.
1364
* @param value value to be associated with the specified key.
1365
*
1366
* @return null
1367
*
1368
* @exception ClassCastException if the class of the specified key
1369
* or value prevents it from being
1370
* stored in this map.
1371
* @exception NullPointerException if the specified key or value
1372
* is null
1373
* @exception IllegalArgumentException if the key duplicates an
1374
* existing key, or if the
1375
* value duplicates an
1376
* existing value
1377
*/
1378
public Object put(final Object key, final Object value)
1379
throws ClassCastException, NullPointerException,
1380
IllegalArgumentException {
1381
1382
checkKeyAndValue(key, value);
1383
1384
Node node = rootNode[KEY];
1385
1386
if (node == null) {
1387
Node root = new Node((Comparable) key, (Comparable) value);
1388
1389
rootNode[KEY] = root;
1390
rootNode[VALUE] = root;
1391
1392
grow();
1393
} else {
1394
while (true) {
1395
int cmp = compare((Comparable) key, node.getData(KEY));
1396
1397
if (cmp == 0) {
1398
throw new IllegalArgumentException(
1399
"Cannot store a duplicate key (\"" + key
1400
+ "\") in this Map");
1401
} else if (cmp < 0) {
1402
if (node.getLeft(KEY) != null) {
1403
node = node.getLeft(KEY);
1404
} else {
1405
Node newNode = new Node((Comparable) key,
1406
(Comparable) value);
1407
1408
insertValue(newNode);
1409
node.setLeft(newNode, KEY);
1410
newNode.setParent(node, KEY);
1411
doRedBlackInsert(newNode, KEY);
1412
grow();
1413
1414
break;
1415
}
1416
} else { // cmp > 0
1417
if (node.getRight(KEY) != null) {
1418
node = node.getRight(KEY);
1419
} else {
1420
Node newNode = new Node((Comparable) key,
1421
(Comparable) value);
1422
1423
insertValue(newNode);
1424
node.setRight(newNode, KEY);
1425
newNode.setParent(node, KEY);
1426
doRedBlackInsert(newNode, KEY);
1427
grow();
1428
1429
break;
1430
}
1431
}
1432
}
1433
}
1434
1435
return null;
1436
}
1437
1438
/**
1439
* Removes the mapping for this key from this map if present
1440
*
1441
* @param key key whose mapping is to be removed from the map.
1442
*
1443
* @return previous value associated with specified key, or null
1444
* if there was no mapping for key.
1445
*/
1446
public Object remove(final Object key) {
1447
return doRemove((Comparable) key, KEY);
1448
}
1449
1450
/**
1451
* Removes all mappings from this map
1452
*/
1453
public void clear() {
1454
1455
modify();
1456
1457
nodeCount = 0;
1458
rootNode[KEY] = null;
1459
rootNode[VALUE] = null;
1460
}
1461
1462
/**
1463
* Returns a set view of the keys contained in this map. The set
1464
* is backed by the map, so changes to the map are reflected in
1465
* the set, and vice-versa. If the map is modified while an
1466
* iteration over the set is in progress, the results of the
1467
* iteration are undefined. The set supports element removal,
1468
* which removes the corresponding mapping from the map, via the
1469
* Iterator.remove, Set.remove, removeAll, retainAll, and clear
1470
* operations. It does not support the add or addAll operations.
1471
*
1472
* @return a set view of the keys contained in this map.
1473
*/
1474
public Set keySet() {
1475
1476
if (setOfKeys[KEY] == null) {
1477
setOfKeys[KEY] = new AbstractSet() {
1478
1479
public Iterator iterator() {
1480
1481
return new DoubleOrderedMapIterator(KEY) {
1482
1483
protected Object doGetNext() {
1484
return lastReturnedNode.getData(KEY);
1485
}
1486
};
1487
}
1488
1489
public int size() {
1490
return DoubleOrderedMap.this.size();
1491
}
1492
1493
public boolean contains(Object o) {
1494
return containsKey(o);
1495
}
1496
1497
public boolean remove(Object o) {
1498
1499
int oldNodeCount = nodeCount;
1500
1501
DoubleOrderedMap.this.remove(o);
1502
1503
return nodeCount != oldNodeCount;
1504
}
1505
1506
public void clear() {
1507
DoubleOrderedMap.this.clear();
1508
}
1509
};
1510
}
1511
1512
return setOfKeys[KEY];
1513
}
1514
1515
/**
1516
* Returns a collection view of the values contained in this
1517
* map. The collection is backed by the map, so changes to the map
1518
* are reflected in the collection, and vice-versa. If the map is
1519
* modified while an iteration over the collection is in progress,
1520
* the results of the iteration are undefined. The collection
1521
* supports element removal, which removes the corresponding
1522
* mapping from the map, via the Iterator.remove,
1523
* Collection.remove, removeAll, retainAll and clear operations.
1524
* It does not support the add or addAll operations.
1525
*
1526
* @return a collection view of the values contained in this map.
1527
*/
1528
public Collection values() {
1529
1530
if (collectionOfValues[KEY] == null) {
1531
collectionOfValues[KEY] = new AbstractCollection() {
1532
1533
public Iterator iterator() {
1534
1535
return new DoubleOrderedMapIterator(KEY) {
1536
1537
protected Object doGetNext() {
1538
return lastReturnedNode.getData(VALUE);
1539
}
1540
};
1541
}
1542
1543
public int size() {
1544
return DoubleOrderedMap.this.size();
1545
}
1546
1547
public boolean contains(Object o) {
1548
return containsValue(o);
1549
}
1550
1551
public boolean remove(Object o) {
1552
1553
int oldNodeCount = nodeCount;
1554
1555
removeValue(o);
1556
1557
return nodeCount != oldNodeCount;
1558
}
1559
1560
public boolean removeAll(Collection c) {
1561
1562
boolean modified = false;
1563
Iterator iter = c.iterator();
1564
1565
while (iter.hasNext()) {
1566
if (removeValue(iter.next()) != null) {
1567
modified = true;
1568
}
1569
}
1570
1571
return modified;
1572
}
1573
1574
public void clear() {
1575
DoubleOrderedMap.this.clear();
1576
}
1577
};
1578
}
1579
1580
return collectionOfValues[KEY];
1581
}
1582
1583
/**
1584
* Returns a set view of the mappings contained in this map. Each
1585
* element in the returned set is a Map.Entry. The set is backed
1586
* by the map, so changes to the map are reflected in the set, and
1587
* vice-versa. If the map is modified while an iteration over the
1588
* set is in progress, the results of the iteration are
1589
* undefined. The set supports element removal, which removes the
1590
* corresponding mapping from the map, via the Iterator.remove,
1591
* Set.remove, removeAll, retainAll and clear operations. It does
1592
* not support the add or addAll operations.
1593
*
1594
* @return a set view of the mappings contained in this map.
1595
*/
1596
public Set entrySet() {
1597
1598
if (setOfEntries[KEY] == null) {
1599
setOfEntries[KEY] = new AbstractSet() {
1600
1601
public Iterator iterator() {
1602
1603
return new DoubleOrderedMapIterator(KEY) {
1604
1605
protected Object doGetNext() {
1606
return lastReturnedNode;
1607
}
1608
};
1609
}
1610
1611
public boolean contains(Object o) {
1612
1613
if (!(o instanceof Map.Entry)) {
1614
return false;
1615
}
1616
1617
Map.Entry entry = (Map.Entry) o;
1618
Object value = entry.getValue();
1619
Node node = lookup((Comparable) entry.getKey(),
1620
KEY);
1621
1622
return (node != null)
1623
&& node.getData(VALUE).equals(value);
1624
}
1625
1626
public boolean remove(Object o) {
1627
1628
if (!(o instanceof Map.Entry)) {
1629
return false;
1630
}
1631
1632
Map.Entry entry = (Map.Entry) o;
1633
Object value = entry.getValue();
1634
Node node = lookup((Comparable) entry.getKey(),
1635
KEY);
1636
1637
if ((node != null) && node.getData(VALUE).equals(value))
1638
{
1639
doRedBlackDelete(node);
1640
1641
return true;
1642
}
1643
1644
return false;
1645
}
1646
1647
public int size() {
1648
return DoubleOrderedMap.this.size();
1649
}
1650
1651
public void clear() {
1652
DoubleOrderedMap.this.clear();
1653
}
1654
};
1655
}
1656
1657
return setOfEntries[KEY];
1658
}
1659
1660
/* ********** END implementation of Map ********** */
1661
private abstract class DoubleOrderedMapIterator implements Iterator {
1662
1663
private int expectedModifications;
1664
protected Node lastReturnedNode;
1665
private Node nextNode;
1666
private int iteratorType;
1667
1668
/**
1669
* Constructor
1670
*
1671
* @param type
1672
*/
1673
DoubleOrderedMapIterator(final int type) {
1674
1675
iteratorType = type;
1676
expectedModifications = DoubleOrderedMap.this.modifications;
1677
lastReturnedNode = null;
1678
nextNode = leastNode(rootNode[iteratorType],
1679
iteratorType);
1680
}
1681
1682
/**
1683
* @return 'next', whatever that means for a given kind of
1684
* DoubleOrderedMapIterator
1685
*/
1686
protected abstract Object doGetNext();
1687
1688
/* ********** START implementation of Iterator ********** */
1689
1690
/**
1691
* @return true if the iterator has more elements.
1692
*/
1693
public final boolean hasNext() {
1694
return nextNode != null;
1695
}
1696
1697
/**
1698
* @return the next element in the iteration.
1699
*
1700
* @exception NoSuchElementException if iteration has no more
1701
* elements.
1702
* @exception ConcurrentModificationException if the
1703
* DoubleOrderedMap is
1704
* modified behind
1705
* the iterator's
1706
* back
1707
*/
1708
public final Object next()
1709
throws NoSuchElementException,
1710
ConcurrentModificationException {
1711
1712
if (nextNode == null) {
1713
throw new NoSuchElementException();
1714
}
1715
1716
if (modifications != expectedModifications) {
1717
throw new ConcurrentModificationException();
1718
}
1719
1720
lastReturnedNode = nextNode;
1721
nextNode = nextGreater(nextNode, iteratorType);
1722
1723
return doGetNext();
1724
}
1725
1726
/**
1727
* Removes from the underlying collection the last element
1728
* returned by the iterator. This method can be called only
1729
* once per call to next. The behavior of an iterator is
1730
* unspecified if the underlying collection is modified while
1731
* the iteration is in progress in any way other than by
1732
* calling this method.
1733
*
1734
* @exception IllegalStateException if the next method has not
1735
* yet been called, or the
1736
* remove method has already
1737
* been called after the last
1738
* call to the next method.
1739
* @exception ConcurrentModificationException if the
1740
* DoubleOrderedMap is
1741
* modified behind
1742
* the iterator's
1743
* back
1744
*/
1745
public final void remove()
1746
throws IllegalStateException,
1747
ConcurrentModificationException {
1748
1749
if (lastReturnedNode == null) {
1750
throw new IllegalStateException();
1751
}
1752
1753
if (modifications != expectedModifications) {
1754
throw new ConcurrentModificationException();
1755
}
1756
1757
doRedBlackDelete(lastReturnedNode);
1758
1759
expectedModifications++;
1760
1761
lastReturnedNode = null;
1762
}
1763
1764
/* ********** END implementation of Iterator ********** */
1765
} // end private abstract class DoubleOrderedMapIterator
1766
1767
// final for performance
1768
private static final class Node implements Map.Entry {
1769
1770
private Comparable[] data;
1771
private Node[] leftNode;
1772
private Node[] rightNode;
1773
private Node[] parentNode;
1774
private boolean[] blackColor;
1775
private int hashcodeValue;
1776
private boolean calculatedHashCode;
1777
1778
/**
1779
* Make a new cell with given key and value, and with null
1780
* links, and black (true) colors.
1781
*
1782
* @param key
1783
* @param value
1784
*/
1785
Node(final Comparable key, final Comparable value) {
1786
1787
data = new Comparable[]{ key, value };
1788
leftNode = new Node[]{ null, null };
1789
rightNode = new Node[]{ null, null };
1790
parentNode = new Node[]{ null, null };
1791
blackColor = new boolean[]{ true, true };
1792
calculatedHashCode = false;
1793
}
1794
1795
/**
1796
* get the specified data
1797
*
1798
* @param index KEY or VALUE
1799
*
1800
* @return the key or value
1801
*/
1802
private Comparable getData(final int index) {
1803
return data[index];
1804
}
1805
1806
/**
1807
* Set this node's left node
1808
*
1809
* @param node the new left node
1810
* @param index KEY or VALUE
1811
*/
1812
private void setLeft(final Node node, final int index) {
1813
leftNode[index] = node;
1814
}
1815
1816
/**
1817
* get the left node
1818
*
1819
* @param index KEY or VALUE
1820
*
1821
* @return the left node -- may be null
1822
*/
1823
private Node getLeft(final int index) {
1824
return leftNode[index];
1825
}
1826
1827
/**
1828
* Set this node's right node
1829
*
1830
* @param node the new right node
1831
* @param index KEY or VALUE
1832
*/
1833
private void setRight(final Node node, final int index) {
1834
rightNode[index] = node;
1835
}
1836
1837
/**
1838
* get the right node
1839
*
1840
* @param index KEY or VALUE
1841
*
1842
* @return the right node -- may be null
1843
*/
1844
private Node getRight(final int index) {
1845
return rightNode[index];
1846
}
1847
1848
/**
1849
* Set this node's parent node
1850
*
1851
* @param node the new parent node
1852
* @param index KEY or VALUE
1853
*/
1854
private void setParent(final Node node, final int index) {
1855
parentNode[index] = node;
1856
}
1857
1858
/**
1859
* get the parent node
1860
*
1861
* @param index KEY or VALUE
1862
*
1863
* @return the parent node -- may be null
1864
*/
1865
private Node getParent(final int index) {
1866
return parentNode[index];
1867
}
1868
1869
/**
1870
* exchange colors with another node
1871
*
1872
* @param node the node to swap with
1873
* @param index KEY or VALUE
1874
*/
1875
private void swapColors(final Node node, final int index) {
1876
1877
// Swap colors -- old hacker's trick
1878
blackColor[index] ^= node.blackColor[index];
1879
node.blackColor[index] ^= blackColor[index];
1880
blackColor[index] ^= node.blackColor[index];
1881
}
1882
1883
/**
1884
* is this node black?
1885
*
1886
* @param index KEY or VALUE
1887
*
1888
* @return true if black (which is represented as a true boolean)
1889
*/
1890
private boolean isBlack(final int index) {
1891
return blackColor[index];
1892
}
1893
1894
/**
1895
* is this node red?
1896
*
1897
* @param index KEY or VALUE
1898
*
1899
* @return true if non-black
1900
*/
1901
private boolean isRed(final int index) {
1902
return !blackColor[index];
1903
}
1904
1905
/**
1906
* make this node black
1907
*
1908
* @param index KEY or VALUE
1909
*/
1910
private void setBlack(final int index) {
1911
blackColor[index] = true;
1912
}
1913
1914
/**
1915
* make this node red
1916
*
1917
* @param index KEY or VALUE
1918
*/
1919
private void setRed(final int index) {
1920
blackColor[index] = false;
1921
}
1922
1923
/**
1924
* make this node the same color as another
1925
*
1926
* @param node the node whose color we're adopting
1927
* @param index KEY or VALUE
1928
*/
1929
private void copyColor(final Node node, final int index) {
1930
blackColor[index] = node.blackColor[index];
1931
}
1932
1933
/* ********** START implementation of Map.Entry ********** */
1934
1935
/**
1936
* @return the key corresponding to this entry.
1937
*/
1938
public Object getKey() {
1939
return data[KEY];
1940
}
1941
1942
/**
1943
* @return the value corresponding to this entry.
1944
*/
1945
public Object getValue() {
1946
return data[VALUE];
1947
}
1948
1949
/**
1950
* Optional operation that is not permitted in this
1951
* implementation
1952
*
1953
* @param ignored
1954
*
1955
* @return does not return
1956
*
1957
* @exception UnsupportedOperationException
1958
*/
1959
public Object setValue(Object ignored)
1960
throws UnsupportedOperationException {
1961
throw new UnsupportedOperationException(
1962
"Map.Entry.setValue is not supported");
1963
}
1964
1965
/**
1966
* Compares the specified object with this entry for equality.
1967
* Returns true if the given object is also a map entry and
1968
* the two entries represent the same mapping.
1969
*
1970
* @param o object to be compared for equality with this map
1971
* entry.
1972
* @return true if the specified object is equal to this map
1973
* entry.
1974
*/
1975
public boolean equals(Object o) {
1976
1977
if (this == o) {
1978
return true;
1979
}
1980
1981
if (!(o instanceof Map.Entry)) {
1982
return false;
1983
}
1984
1985
Map.Entry e = (Map.Entry) o;
1986
1987
return data[KEY].equals(e.getKey())
1988
&& data[VALUE].equals(e.getValue());
1989
}
1990
1991
/**
1992
* @return the hash code value for this map entry.
1993
*/
1994
public int hashCode() {
1995
1996
if (!calculatedHashCode) {
1997
hashcodeValue = data[KEY].hashCode()
1998
^ data[VALUE].hashCode();
1999
calculatedHashCode = true;
2000
}
2001
2002
return hashcodeValue;
2003
}
2004
2005
/* ********** END implementation of Map.Entry ********** */
2006
}
2007
} // end public class DoubleOrderedMap
Loggerhead is a web-based interface for Breezy
Version: 2.0.1