6 |
|
*/ |
7 |
|
|
8 |
|
package java.util; |
9 |
< |
import java.util.*; // for javadoc |
9 |
> |
import java.util.*; // for javadoc (till 6280605 is fixed) |
10 |
|
|
11 |
|
/** |
12 |
|
* A Red-Black tree based {@link NavigableMap} implementation. |
31 |
|
* <i>is</i> well-defined even if its ordering is inconsistent with equals; it |
32 |
|
* just fails to obey the general contract of the <tt>Map</tt> interface. |
33 |
|
* |
34 |
< |
* <p><b>Note that this implementation is not synchronized.</b> If multiple |
35 |
< |
* threads access a map concurrently, and at least one of the threads modifies |
36 |
< |
* the map structurally, it <i>must</i> be synchronized externally. (A |
37 |
< |
* structural modification is any operation that adds or deletes one or more |
38 |
< |
* mappings; merely changing the value associated with an existing key is not |
39 |
< |
* a structural modification.) This is typically accomplished by |
40 |
< |
* synchronizing on some object that naturally encapsulates the map. If no |
41 |
< |
* such object exists, the map should be "wrapped" using the |
42 |
< |
* <tt>Collections.synchronizedMap</tt> method. This is best done at creation |
43 |
< |
* time, to prevent accidental unsynchronized access to the map: |
44 |
< |
* <pre> |
45 |
< |
* Map m = Collections.synchronizedMap(new TreeMap(...)); |
46 |
< |
* </pre> |
34 |
> |
* <p><strong>Note that this implementation is not synchronized.</strong> |
35 |
> |
* If multiple threads access a map concurrently, and at least one of the |
36 |
> |
* threads modifies the map structurally, it <i>must</i> be synchronized |
37 |
> |
* externally. (A structural modification is any operation that adds or |
38 |
> |
* deletes one or more mappings; merely changing the value associated |
39 |
> |
* with an existing key is not a structural modification.) This is |
40 |
> |
* typically accomplished by synchronizing on some object that naturally |
41 |
> |
* encapsulates the map. |
42 |
> |
* If no such object exists, the map should be "wrapped" using the |
43 |
> |
* {@link Collections#synchronizedSortedMap Collections.synchronizedSortedMap} |
44 |
> |
* method. This is best done at creation time, to prevent accidental |
45 |
> |
* unsynchronized access to the map: <pre> |
46 |
> |
* SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));</pre> |
47 |
|
* |
48 |
|
* <p>The iterators returned by the <tt>iterator</tt> method of the collections |
49 |
|
* returned by all of this class's "collection view methods" are |
83 |
|
* @see Comparable |
84 |
|
* @see Comparator |
85 |
|
* @see Collection |
86 |
– |
* @see Collections#synchronizedMap(Map) |
86 |
|
* @since 1.2 |
87 |
|
*/ |
88 |
|
|
216 |
|
* specified value. More formally, returns <tt>true</tt> if and only if |
217 |
|
* this map contains at least one mapping to a value <tt>v</tt> such |
218 |
|
* that <tt>(value==null ? v==null : value.equals(v))</tt>. This |
219 |
< |
* operation requires time linear in the map size. |
219 |
> |
* operation will probably require time linear in the map size for |
220 |
> |
* most implementations. |
221 |
|
* |
222 |
|
* @param value value whose presence in this map is to be tested |
223 |
|
* @return <tt>true</tt> if a mapping to <tt>value</tt> exists; |
254 |
|
* <tt>null</tt> if the map contains no mapping for the key. A return |
255 |
|
* value of <tt>null</tt> does not <i>necessarily</i> indicate that the |
256 |
|
* map contains no mapping for the key; it's also possible that the map |
257 |
< |
* explicitly maps the key to <tt>null</tt>. The {@link #containsKey} |
258 |
< |
* operation may be used to distinguish these two cases. |
257 |
> |
* explicitly maps the key to <tt>null</tt>. The {@link #containsKey |
258 |
> |
* containsKey} operation may be used to distinguish these two cases. |
259 |
|
* |
260 |
|
* @param key key whose associated value is to be returned |
261 |
|
* @return the value to which this map maps the specified key, or |
520 |
|
|
521 |
|
/** |
522 |
|
* Associates the specified value with the specified key in this map. |
523 |
< |
* If the map previously contained a mapping for this key, the old |
523 |
> |
* If the map previously contained a mapping for the key, the old |
524 |
|
* value is replaced. |
525 |
|
* |
526 |
|
* @param key key with which the specified value is to be associated |
540 |
|
Entry<K,V> t = root; |
541 |
|
|
542 |
|
if (t == null) { |
543 |
< |
if (key == null) { |
544 |
< |
if (comparator == null) |
545 |
< |
throw new NullPointerException(); |
546 |
< |
comparator.compare(key, key); |
547 |
< |
} |
543 |
> |
// TBD |
544 |
> |
// if (key == null) { |
545 |
> |
// if (comparator == null) |
546 |
> |
// throw new NullPointerException(); |
547 |
> |
// comparator.compare(key, key); |
548 |
> |
// } |
549 |
|
incrementSize(); |
550 |
|
root = new Entry<K,V>(key, value, null); |
551 |
|
return null; |
645 |
|
|
646 |
|
// NavigableMap API methods |
647 |
|
|
648 |
+ |
/** |
649 |
+ |
* @since 1.6 |
650 |
+ |
*/ |
651 |
|
public Map.Entry<K,V> firstEntry() { |
652 |
|
Entry<K,V> e = getFirstEntry(); |
653 |
|
return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e); |
654 |
|
} |
655 |
|
|
656 |
+ |
/** |
657 |
+ |
* @since 1.6 |
658 |
+ |
*/ |
659 |
|
public Map.Entry<K,V> lastEntry() { |
660 |
|
Entry<K,V> e = getLastEntry(); |
661 |
|
return (e == null)? null : new AbstractMap.SimpleImmutableEntry<K,V>(e); |
662 |
|
} |
663 |
|
|
664 |
+ |
/** |
665 |
+ |
* @since 1.6 |
666 |
+ |
*/ |
667 |
|
public Map.Entry<K,V> pollFirstEntry() { |
668 |
|
Entry<K,V> p = getFirstEntry(); |
669 |
|
if (p == null) |
673 |
|
return result; |
674 |
|
} |
675 |
|
|
676 |
+ |
/** |
677 |
+ |
* @since 1.6 |
678 |
+ |
*/ |
679 |
|
public Map.Entry<K,V> pollLastEntry() { |
680 |
|
Entry<K,V> p = getLastEntry(); |
681 |
|
if (p == null) |
690 |
|
* @throws NullPointerException if the specified key is null |
691 |
|
* and this map uses natural ordering, or its comparator |
692 |
|
* does not permit null keys |
693 |
+ |
* @since 1.6 |
694 |
|
*/ |
695 |
|
public Map.Entry<K,V> lowerEntry(K key) { |
696 |
|
Entry<K,V> e = getLowerEntry(key); |
702 |
|
* @throws NullPointerException if the specified key is null |
703 |
|
* and this map uses natural ordering, or its comparator |
704 |
|
* does not permit null keys |
705 |
+ |
* @since 1.6 |
706 |
|
*/ |
707 |
|
public K lowerKey(K key) { |
708 |
|
Entry<K,V> e = getLowerEntry(key); |
714 |
|
* @throws NullPointerException if the specified key is null |
715 |
|
* and this map uses natural ordering, or its comparator |
716 |
|
* does not permit null keys |
717 |
+ |
* @since 1.6 |
718 |
|
*/ |
719 |
|
public Map.Entry<K,V> floorEntry(K key) { |
720 |
|
Entry<K,V> e = getFloorEntry(key); |
726 |
|
* @throws NullPointerException if the specified key is null |
727 |
|
* and this map uses natural ordering, or its comparator |
728 |
|
* does not permit null keys |
729 |
+ |
* @since 1.6 |
730 |
|
*/ |
731 |
|
public K floorKey(K key) { |
732 |
|
Entry<K,V> e = getFloorEntry(key); |
738 |
|
* @throws NullPointerException if the specified key is null |
739 |
|
* and this map uses natural ordering, or its comparator |
740 |
|
* does not permit null keys |
741 |
+ |
* @since 1.6 |
742 |
|
*/ |
743 |
|
public Map.Entry<K,V> ceilingEntry(K key) { |
744 |
|
Entry<K,V> e = getCeilingEntry(key); |
750 |
|
* @throws NullPointerException if the specified key is null |
751 |
|
* and this map uses natural ordering, or its comparator |
752 |
|
* does not permit null keys |
753 |
+ |
* @since 1.6 |
754 |
|
*/ |
755 |
|
public K ceilingKey(K key) { |
756 |
|
Entry<K,V> e = getCeilingEntry(key); |
762 |
|
* @throws NullPointerException if the specified key is null |
763 |
|
* and this map uses natural ordering, or its comparator |
764 |
|
* does not permit null keys |
765 |
+ |
* @since 1.6 |
766 |
|
*/ |
767 |
|
public Map.Entry<K,V> higherEntry(K key) { |
768 |
|
Entry<K,V> e = getHigherEntry(key); |
774 |
|
* @throws NullPointerException if the specified key is null |
775 |
|
* and this map uses natural ordering, or its comparator |
776 |
|
* does not permit null keys |
777 |
+ |
* @since 1.6 |
778 |
|
*/ |
779 |
|
public K higherKey(K key) { |
780 |
|
Entry<K,V> e = getHigherEntry(key); |
942 |
|
} |
943 |
|
} |
944 |
|
|
945 |
+ |
/** |
946 |
+ |
* @since 1.6 |
947 |
+ |
*/ |
948 |
|
public Set<Map.Entry<K,V>> descendingEntrySet() { |
949 |
|
Set<Map.Entry<K,V>> es = descendingEntrySet; |
950 |
|
return (es != null) ? es : (descendingEntrySet = new DescendingEntrySet()); |
956 |
|
} |
957 |
|
} |
958 |
|
|
959 |
+ |
/** |
960 |
+ |
* @since 1.6 |
961 |
+ |
*/ |
962 |
|
public Set<K> descendingKeySet() { |
963 |
|
Set<K> ks = descendingKeySet; |
964 |
|
return (ks != null) ? ks : (descendingKeySet = new DescendingKeySet()); |
976 |
|
* null and this map uses natural ordering, or its comparator |
977 |
|
* does not permit null keys |
978 |
|
* @throws IllegalArgumentException {@inheritDoc} |
979 |
+ |
* @since 1.6 |
980 |
|
*/ |
981 |
|
public NavigableMap<K,V> navigableSubMap(K fromKey, K toKey) { |
982 |
|
return new SubMap(fromKey, toKey); |
988 |
|
* and this map uses natural ordering, or its comparator |
989 |
|
* does not permit null keys |
990 |
|
* @throws IllegalArgumentException {@inheritDoc} |
991 |
+ |
* @since 1.6 |
992 |
|
*/ |
993 |
|
public NavigableMap<K,V> navigableHeadMap(K toKey) { |
994 |
|
return new SubMap(toKey, true); |
1000 |
|
* and this map uses natural ordering, or its comparator |
1001 |
|
* does not permit null keys |
1002 |
|
* @throws IllegalArgumentException {@inheritDoc} |
1003 |
+ |
* @since 1.6 |
1004 |
|
*/ |
1005 |
|
public NavigableMap<K,V> navigableTailMap(K fromKey) { |
1006 |
|
return new SubMap(fromKey, false); |