19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27
28 /**
29 * A Red-Black tree based {@link NavigableMap} implementation.
30 * The map is sorted according to the {@linkplain Comparable natural
31 * ordering} of its keys, or by a {@link Comparator} provided at map
32 * creation time, depending on which constructor is used.
33 *
34 * <p>This implementation provides guaranteed log(n) time cost for the
35 * <tt>containsKey</tt>, <tt>get</tt>, <tt>put</tt> and <tt>remove</tt>
36 * operations. Algorithms are adaptations of those in Cormen, Leiserson, and
37 * Rivest's <I>Introduction to Algorithms</I>.
38 *
39 * <p>Note that the ordering maintained by a sorted map (whether or not an
40 * explicit comparator is provided) must be <i>consistent with equals</i> if
41 * this sorted map is to correctly implement the <tt>Map</tt> interface. (See
42 * <tt>Comparable</tt> or <tt>Comparator</tt> for a precise definition of
43 * <i>consistent with equals</i>.) This is so because the <tt>Map</tt>
44 * interface is defined in terms of the equals operation, but a map performs
45 * all key comparisons using its <tt>compareTo</tt> (or <tt>compare</tt>)
46 * method, so two keys that are deemed equal by this method are, from the
47 * standpoint of the sorted map, equal. The behavior of a sorted map
48 * <i>is</i> well-defined even if its ordering is inconsistent with equals; it
49 * just fails to obey the general contract of the <tt>Map</tt> interface.
50 *
51 * <p><strong>Note that this implementation is not synchronized.</strong>
52 * If multiple threads access a map concurrently, and at least one of the
53 * threads modifies the map structurally, it <i>must</i> be synchronized
54 * externally. (A structural modification is any operation that adds or
55 * deletes one or more mappings; merely changing the value associated
56 * with an existing key is not a structural modification.) This is
57 * typically accomplished by synchronizing on some object that naturally
58 * encapsulates the map.
59 * If no such object exists, the map should be "wrapped" using the
60 * {@link Collections#synchronizedSortedMap Collections.synchronizedSortedMap}
61 * method. This is best done at creation time, to prevent accidental
62 * unsynchronized access to the map: <pre>
63 * SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));</pre>
64 *
65 * <p>The iterators returned by the <tt>iterator</tt> method of the collections
66 * returned by all of this class's "collection view methods" are
67 * <i>fail-fast</i>: if the map is structurally modified at any time after the
68 * iterator is created, in any way except through the iterator's own
69 * <tt>remove</tt> method, the iterator will throw a {@link
|
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package java.util;
27
28 /**
29 * A Red-Black tree based {@link NavigableMap} implementation.
30 * The map is sorted according to the {@linkplain Comparable natural
31 * ordering} of its keys, or by a {@link Comparator} provided at map
32 * creation time, depending on which constructor is used.
33 *
34 * <p>This implementation provides guaranteed log(n) time cost for the
35 * <tt>containsKey</tt>, <tt>get</tt>, <tt>put</tt> and <tt>remove</tt>
36 * operations. Algorithms are adaptations of those in Cormen, Leiserson, and
37 * Rivest's <I>Introduction to Algorithms</I>.
38 *
39 * <p>Note that the ordering maintained by a tree map, like any sorted map, and
40 * whether or not an explicit comparator is provided, must be <em>consistent
41 * with {@code equals}</em> if this sorted map is to correctly implement the
42 * {@code Map} interface. (See {@code Comparable} or {@code Comparator} for a
43 * precise definition of <i>consistent with equals</i>.) This is so because
44 * the <tt>Map</tt> interface is defined in terms of the {@code equals}
45 * operation, but a sorted map performs all key comparisons using its {@code
46 * compareTo} (or {@code compare}) method, so two keys that are deemed equal by
47 * this method are, from the standpoint of the sorted map, equal. The behavior
48 * of a sorted map <em>is</em> well-defined even if its ordering is
49 * inconsistent with {@code equals}; it just fails to obey the general contract
50 * of the {@code Map} interface.
51 *
52 * <p><strong>Note that this implementation is not synchronized.</strong>
53 * If multiple threads access a map concurrently, and at least one of the
54 * threads modifies the map structurally, it <i>must</i> be synchronized
55 * externally. (A structural modification is any operation that adds or
56 * deletes one or more mappings; merely changing the value associated
57 * with an existing key is not a structural modification.) This is
58 * typically accomplished by synchronizing on some object that naturally
59 * encapsulates the map.
60 * If no such object exists, the map should be "wrapped" using the
61 * {@link Collections#synchronizedSortedMap Collections.synchronizedSortedMap}
62 * method. This is best done at creation time, to prevent accidental
63 * unsynchronized access to the map: <pre>
64 * SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));</pre>
65 *
66 * <p>The iterators returned by the <tt>iterator</tt> method of the collections
67 * returned by all of this class's "collection view methods" are
68 * <i>fail-fast</i>: if the map is structurally modified at any time after the
69 * iterator is created, in any way except through the iterator's own
70 * <tt>remove</tt> method, the iterator will throw a {@link
|