| 1 |
|
/* |
| 2 |
|
* %W% %E% |
| 3 |
|
* |
| 4 |
< |
* Copyright 2005 Sun Microsystems, Inc. All rights reserved. |
| 4 |
> |
* Copyright 2006 Sun Microsystems, Inc. All rights reserved. |
| 5 |
|
* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms. |
| 6 |
|
*/ |
| 7 |
|
|
| 8 |
|
package java.util; |
| 9 |
– |
import java.util.*; // for javadoc (till 6280605 is fixed) |
| 9 |
|
|
| 10 |
|
/** |
| 11 |
|
* A Red-Black tree based {@link NavigableMap} implementation. |
| 30 |
|
* <i>is</i> well-defined even if its ordering is inconsistent with equals; it |
| 31 |
|
* just fails to obey the general contract of the <tt>Map</tt> interface. |
| 32 |
|
* |
| 33 |
< |
* <p><b>Note that this implementation is not synchronized.</b> If multiple |
| 34 |
< |
* threads access a map concurrently, and at least one of the threads modifies |
| 35 |
< |
* the map structurally, it <i>must</i> be synchronized externally. (A |
| 36 |
< |
* structural modification is any operation that adds or deletes one or more |
| 37 |
< |
* mappings; merely changing the value associated with an existing key is not |
| 38 |
< |
* a structural modification.) This is typically accomplished by |
| 39 |
< |
* synchronizing on some object that naturally encapsulates the map. If no |
| 40 |
< |
* such object exists, the map should be "wrapped" using the |
| 41 |
< |
* <tt>Collections.synchronizedMap</tt> method. This is best done at creation |
| 42 |
< |
* time, to prevent accidental unsynchronized access to the map: |
| 43 |
< |
* <pre> |
| 44 |
< |
* Map m = Collections.synchronizedMap(new TreeMap(...)); |
| 45 |
< |
* </pre> |
| 33 |
> |
* <p><strong>Note that this implementation is not synchronized.</strong> |
| 34 |
> |
* If multiple threads access a map concurrently, and at least one of the |
| 35 |
> |
* threads modifies the map structurally, it <i>must</i> be synchronized |
| 36 |
> |
* externally. (A structural modification is any operation that adds or |
| 37 |
> |
* deletes one or more mappings; merely changing the value associated |
| 38 |
> |
* with an existing key is not a structural modification.) This is |
| 39 |
> |
* typically accomplished by synchronizing on some object that naturally |
| 40 |
> |
* encapsulates the map. |
| 41 |
> |
* If no such object exists, the map should be "wrapped" using the |
| 42 |
> |
* {@link Collections#synchronizedSortedMap Collections.synchronizedSortedMap} |
| 43 |
> |
* method. This is best done at creation time, to prevent accidental |
| 44 |
> |
* unsynchronized access to the map: <pre> |
| 45 |
> |
* SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));</pre> |
| 46 |
|
* |
| 47 |
|
* <p>The iterators returned by the <tt>iterator</tt> method of the collections |
| 48 |
|
* returned by all of this class's "collection view methods" are |
| 82 |
|
* @see Comparable |
| 83 |
|
* @see Comparator |
| 84 |
|
* @see Collection |
| 86 |
– |
* @see Collections#synchronizedMap(Map) |
| 85 |
|
* @since 1.2 |
| 86 |
|
*/ |
| 87 |
|
|
| 249 |
|
} |
| 250 |
|
|
| 251 |
|
/** |
| 252 |
< |
* Returns the value to which this map maps the specified key, or |
| 253 |
< |
* <tt>null</tt> if the map contains no mapping for the key. A return |
| 254 |
< |
* value of <tt>null</tt> does not <i>necessarily</i> indicate that the |
| 255 |
< |
* map contains no mapping for the key; it's also possible that the map |
| 256 |
< |
* explicitly maps the key to <tt>null</tt>. The {@link #containsKey |
| 257 |
< |
* containsKey} operation may be used to distinguish these two cases. |
| 258 |
< |
* |
| 259 |
< |
* @param key key whose associated value is to be returned |
| 260 |
< |
* @return the value to which this map maps the specified key, or |
| 261 |
< |
* <tt>null</tt> if the map contains no mapping for the key |
| 252 |
> |
* Returns the value to which the specified key is mapped, |
| 253 |
> |
* or {@code null} if this map contains no mapping for the key. |
| 254 |
> |
* |
| 255 |
> |
* <p>More formally, if this map contains a mapping from a key |
| 256 |
> |
* {@code k} to a value {@code v} such that {@code key} compares |
| 257 |
> |
* equal to {@code k} according to the map's ordering, then this |
| 258 |
> |
* method returns {@code v}; otherwise it returns {@code null}. |
| 259 |
> |
* (There can be at most one such mapping.) |
| 260 |
> |
* |
| 261 |
> |
* <p>A return value of {@code null} does not <i>necessarily</i> |
| 262 |
> |
* indicate that the map contains no mapping for the key; it's also |
| 263 |
> |
* possible that the map explicitly maps the key to {@code null}. |
| 264 |
> |
* The {@link #containsKey containsKey} operation may be used to |
| 265 |
> |
* distinguish these two cases. |
| 266 |
> |
* |
| 267 |
|
* @throws ClassCastException if the specified key cannot be compared |
| 268 |
|
* with the keys currently in the map |
| 269 |
|
* @throws NullPointerException if the specified key is null |
| 544 |
|
Entry<K,V> t = root; |
| 545 |
|
|
| 546 |
|
if (t == null) { |
| 547 |
< |
if (key == null) { |
| 548 |
< |
if (comparator == null) |
| 549 |
< |
throw new NullPointerException(); |
| 550 |
< |
comparator.compare(key, key); |
| 551 |
< |
} |
| 547 |
> |
// TBD |
| 548 |
> |
// if (key == null) { |
| 549 |
> |
// if (comparator == null) |
| 550 |
> |
// throw new NullPointerException(); |
| 551 |
> |
// comparator.compare(key, key); |
| 552 |
> |
// } |
| 553 |
|
incrementSize(); |
| 554 |
|
root = new Entry<K,V>(key, value, null); |
| 555 |
|
return null; |
| 2020 |
|
* @throws ClassNotFoundException propagated from readObject. |
| 2021 |
|
* This cannot occur if str is null. |
| 2022 |
|
*/ |
| 2023 |
< |
private |
| 2024 |
< |
void buildFromSorted(int size, Iterator it, |
| 2025 |
< |
java.io.ObjectInputStream str, |
| 2022 |
< |
V defaultVal) |
| 2023 |
> |
private void buildFromSorted(int size, Iterator it, |
| 2024 |
> |
java.io.ObjectInputStream str, |
| 2025 |
> |
V defaultVal) |
| 2026 |
|
throws java.io.IOException, ClassNotFoundException { |
| 2027 |
|
this.size = size; |
| 2028 |
< |
root = |
| 2029 |
< |
buildFromSorted(0, 0, size-1, computeRedLevel(size), |
| 2027 |
< |
it, str, defaultVal); |
| 2028 |
> |
root = buildFromSorted(0, 0, size-1, computeRedLevel(size), |
| 2029 |
> |
it, str, defaultVal); |
| 2030 |
|
} |
| 2031 |
|
|
| 2032 |
|
/** |
| 2033 |
|
* Recursive "helper method" that does the real work of the |
| 2034 |
< |
* of the previous method. Identically named parameters have |
| 2034 |
> |
* previous method. Identically named parameters have |
| 2035 |
|
* identical definitions. Additional parameters are documented below. |
| 2036 |
|
* It is assumed that the comparator and size fields of the TreeMap are |
| 2037 |
|
* already set prior to calling this method. (It ignores both fields.) |
