Red-Black tree based implementation of the SortedMap interface. This class guarantees that the map will be in ascending key order, sorted according to the natural order for the key's class (see Comparable), or by the comparator provided at creation time, depending on which constructor is used.

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.

Note that the ordering maintained by a sorted map (whether or not an explicit comparator is provided) must be consistent with equals if this sorted map is to correctly implement the Map interface. (See Comparable or Comparator for a precise definition of consistent with equals.) This is so because the Map interface is defined in terms of the equals operation, but a map performs all key comparisons using its compareTo (or compare) method, so two keys that are deemed equal by this method are, from the standpoint of the sorted map, equal. The behavior of a sorted map is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Map interface.

Note that this implementation is not synchronized. If multiple threads access a map concurrently, and at least one of the threads modifies the map structurally, it must be synchronized externally. (A structural modification is any operation that adds or deletes one or more mappings; merely changing the value associated with an existing key is not a structural modification.) This is typically accomplished by synchronizing on some object that naturally encapsulates the map. If no such object exists, the map should be "wrapped" using the Collections.synchronizedMap method. This is best done at creation time, to prevent accidental unsynchronized access to the map:

     Map m = Collections.synchronizedMap(new TreeMap(...));
 

The iterators returned by all of this class's "collection view methods" are fail-fast: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove or add methods, the iterator throws a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

Note that the fail-fast behavior of an iterator cannot be guaranteed as it is, generally speaking, impossible to make any hard guarantees in the presence of unsynchronized concurrent modification. Fail-fast iterators throw ConcurrentModificationException on a best-effort basis. Therefore, it would be wrong to write a program that depended on this exception for its correctness: the fail-fast behavior of iterators should be used only to detect bugs.

This class is a member of the Java Collections Framework.

@author
Josh Bloch and Doug Lea
@version
1.65, 02/19/04
@since
1.2
Constructs a new, empty map, sorted according to the keys' natural order. All keys inserted into the map must implement the Comparable interface. Furthermore, all such keys must be mutually comparable: k1.compareTo(k2) must not throw a ClassCastException for any elements k1 and k2 in the map. If the user attempts to put a key into the map that violates this constraint (for example, the user attempts to put a string key into a map whose keys are integers), the put(Object key, Object value) call will throw a ClassCastException.
See Also
Constructs a new, empty map, sorted according to the given comparator. All keys inserted into the map must be mutually comparable by the given comparator: comparator.compare(k1, k2) must not throw a ClassCastException for any keys k1 and k2 in the map. If the user attempts to put a key into the map that violates this constraint, the put(Object key, Object value) call will throw a ClassCastException.
Parameters
cthe comparator that will be used to sort this map. A null value indicates that the keys' natural ordering should be used.
Constructs a new map containing the same mappings as the given map, sorted according to the keys' natural order. All keys inserted into the new map must implement the Comparable interface. Furthermore, all such keys must be mutually comparable: k1.compareTo(k2) must not throw a ClassCastException for any elements k1 and k2 in the map. This method runs in n*log(n) time.
Parameters
mthe map whose mappings are to be placed in this map.
Throws
ClassCastExceptionthe keys in t are not Comparable, or are not mutually comparable.
NullPointerExceptionif the specified map is null.
Constructs a new map containing the same mappings as the given SortedMap, sorted according to the same ordering. This method runs in linear time.
Parameters
mthe sorted map whose mappings are to be placed in this map, and whose comparator is to be used to sort this map.
Throws
NullPointerExceptionif the specified sorted map is null.
Removes all mappings from this TreeMap.
Returns a shallow copy of this TreeMap instance. (The keys and values themselves are not cloned.)
Return
a shallow copy of this Map.
Returns the comparator associated with this sorted map, or null if it uses its keys' natural ordering.
Return
the comparator associated with this sorted map, or null if it uses its keys' natural ordering.
Returns true if this map contains a mapping for the specified key.
Parameters
keykey whose presence in this map is to be tested.
Return
true if this map contains a mapping for the specified key.
Throws
ClassCastExceptionif the key cannot be compared with the keys currently in the map.
NullPointerExceptionkey is null and this map uses natural ordering, or its comparator does not tolerate null keys.
Returns true if this map maps one or more keys to the specified value. More formally, returns true if and only if this map contains at least one mapping to a value v such that (value==null ? v==null : value.equals(v)). This operation will probably require time linear in the Map size for most implementations of Map.
Parameters
valuevalue whose presence in this Map is to be tested.
Return
true if a mapping to value exists; false otherwise.
@since
1.2
Returns a set view of the mappings contained in this map. The set's iterator returns the mappings in ascending key order. Each element in the returned set is a Map.Entry. The set is backed by this map, so changes to this map are reflected in the set, and vice-versa. The set supports element removal, which removes the corresponding mapping from the TreeMap, through the Iterator.remove, Set.remove, removeAll, retainAll and clear operations. It does not support the add or addAll operations.
Return
a set view of the mappings contained in this map.
See Also
Compares the specified object with this map for equality. Returns true if the given object is also a map and the two maps represent the same mappings. More formally, two maps t1 and t2 represent the same mappings if t1.keySet().equals(t2.keySet()) and for every key k in t1.keySet(), (t1.get(k)==null ? t2.get(k)==null : t1.get(k).equals(t2.get(k))) . This ensures that the equals method works properly across different implementations of the map interface.

This implementation first checks if the specified object is this map; if so it returns true. Then, it checks if the specified object is a map whose size is identical to the size of this set; if not, it returns false. If so, it iterates over this map's entrySet collection, and checks that the specified map contains each mapping that this map contains. If the specified map fails to contain such a mapping, false is returned. If the iteration completes, true is returned.

Parameters
oobject to be compared for equality with this map.
Return
true if the specified object is equal to this map.
Returns the first (lowest) key currently in this sorted map.
Return
the first (lowest) key currently in this sorted map.
Throws
NoSuchElementExceptionif this map is empty.
Returns the value to which this map maps the specified key. Returns null if the map contains no mapping for this key. A return value of null does not necessarily indicate that the map contains no mapping for the key; it's also possible that the map explicitly maps the key to null. The containsKey operation may be used to distinguish these two cases.
Parameters
keykey whose associated value is to be returned.
Return
the value to which this map maps the specified key, or null if the map contains no mapping for the key.
Throws
ClassCastExceptionkey cannot be compared with the keys currently in the map.
NullPointerExceptionkey is null and this map uses natural ordering, or its comparator does not tolerate null keys.
Returns the runtime class of an object. That Class object is the object that is locked by static synchronized methods of the represented class.
Return
The java.lang.Class object that represents the runtime class of the object. The result is of type {@code Class} where X is the erasure of the static type of the expression on which getClass is called.
Returns the hash code value for this map. The hash code of a map is defined to be the sum of the hash codes of each entry in the map's entrySet() view. This ensures that t1.equals(t2) implies that t1.hashCode()==t2.hashCode() for any two maps t1 and t2, as required by the general contract of Object.hashCode.

This implementation iterates over entrySet(), calling hashCode on each element (entry) in the Collection, and adding up the results.

Return
the hash code value for this map.
Returns a view of the portion of this sorted map whose keys are strictly less than toKey. The returned sorted map is backed by this sorted map, so changes in the returned sorted map are reflected in this sorted map, and vice-versa. The returned map supports all optional map operations that this sorted map supports.

The map returned by this method will throw an IllegalArgumentException if the user attempts to insert a key outside the specified range.

Note: this method always returns a view that does not contain its (high) endpoint. If you need a view that does contain this endpoint, and the key type allows for calculation of the successor a given key, merely request a headMap bounded by successor(highEndpoint). For example, suppose that suppose that m is a map whose keys are strings. The following idiom obtains a view containing all of the key-value mappings in m whose keys are less than or equal to high:

    Map head = m.headMap(high+"\0");
Parameters
toKeyhigh endpoint (exclusive) of the subMap.
Return
a view of the specified initial range of this sorted map.
Throws
ClassCastExceptionif toKey is not compatible with this map's comparator (or, if the map has no comparator, if toKey does not implement Comparable). Implementations may, but are not required to, throw this exception if toKey cannot be compared to keys currently in the map.
IllegalArgumentExceptionif this map is itself a subMap, headMap, or tailMap, and toKey is not within the specified range of the subMap, headMap, or tailMap.
NullPointerExceptionif toKey is null and this sorted map does not tolerate null keys.
Returns true if this map contains no key-value mappings.

This implementation returns size() == 0.

Return
true if this map contains no key-value mappings.
Returns a Set view of the keys contained in this map. The set's iterator will return the keys in ascending order. The map is backed by this TreeMap instance, so changes to this map are reflected in the Set, and vice-versa. The Set supports element removal, which removes the corresponding mapping from the map, via the Iterator.remove, Set.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations.
Return
a set view of the keys contained in this TreeMap.
Returns the last (highest) key currently in this sorted map.
Return
the last (highest) key currently in this sorted map.
Throws
NoSuchElementExceptionif this map is empty.
Wakes up a single thread that is waiting on this object's monitor. If any threads are waiting on this object, one of them is chosen to be awakened. The choice is arbitrary and occurs at the discretion of the implementation. A thread waits on an object's monitor by calling one of the wait methods.

The awakened thread will not be able to proceed until the current thread relinquishes the lock on this object. The awakened thread will compete in the usual manner with any other threads that might be actively competing to synchronize on this object; for example, the awakened thread enjoys no reliable privilege or disadvantage in being the next thread to lock this object.

This method should only be called by a thread that is the owner of this object's monitor. A thread becomes the owner of the object's monitor in one of three ways:

  • By executing a synchronized instance method of that object.
  • By executing the body of a synchronized statement that synchronizes on the object.
  • For objects of type Class, by executing a synchronized static method of that class.

Only one thread at a time can own an object's monitor.

Throws
IllegalMonitorStateExceptionif the current thread is not the owner of this object's monitor.
Wakes up all threads that are waiting on this object's monitor. A thread waits on an object's monitor by calling one of the wait methods.

The awakened threads will not be able to proceed until the current thread relinquishes the lock on this object. The awakened threads will compete in the usual manner with any other threads that might be actively competing to synchronize on this object; for example, the awakened threads enjoy no reliable privilege or disadvantage in being the next thread to lock this object.

This method should only be called by a thread that is the owner of this object's monitor. See the notify method for a description of the ways in which a thread can become the owner of a monitor.

Throws
IllegalMonitorStateExceptionif the current thread is not the owner of this object's monitor.
Associates the specified value with the specified key in this map. If the map previously contained a mapping for this key, the old value is replaced.
Parameters
keykey with which the specified value is to be associated.
valuevalue to be associated with the specified key.
Return
previous value associated with specified key, or null if there was no mapping for key. A null return can also indicate that the map previously associated null with the specified key.
Throws
ClassCastExceptionkey cannot be compared with the keys currently in the map.
NullPointerExceptionkey is null and this map uses natural order, or its comparator does not tolerate null keys.
Copies all of the mappings from the specified map to this map. These mappings replace any mappings that this map had for any of the keys currently in the specified map.
Parameters
mapmappings to be stored in this map.
Throws
ClassCastExceptionclass of a key or value in the specified map prevents it from being stored in this map.
NullPointerExceptionif the given map is null or this map does not permit null keys and a key in the specified map is null.
Removes the mapping for this key from this TreeMap if present.
Parameters
keykey for which mapping should be removed
Return
previous value associated with specified key, or null if there was no mapping for key. A null return can also indicate that the map previously associated null with the specified key.
Throws
ClassCastExceptionkey cannot be compared with the keys currently in the map.
NullPointerExceptionkey is null and this map uses natural order, or its comparator does not tolerate null keys.
Returns the number of key-value mappings in this map.
Return
the number of key-value mappings in this map.
Returns a view of the portion of this sorted map whose keys range from fromKey, inclusive, to toKey, exclusive. (If fromKey and toKey are equal, the returned sorted map is empty.) The returned sorted map is backed by this sorted map, so changes in the returned sorted map are reflected in this sorted map, and vice-versa. The returned Map supports all optional map operations that this sorted map supports.

The map returned by this method will throw an IllegalArgumentException if the user attempts to insert a key outside the specified range.

Note: this method always returns a half-open range (which includes its low endpoint but not its high endpoint). If you need a closed range (which includes both endpoints), and the key type allows for calculation of the successor a given key, merely request the subrange from lowEndpoint to successor(highEndpoint). For example, suppose that m is a map whose keys are strings. The following idiom obtains a view containing all of the key-value mappings in m whose keys are between low and high, inclusive:

    Map sub = m.subMap(low, high+"\0");
A similarly technique can be used to generate an open range (which contains neither endpoint). The following idiom obtains a view containing all of the key-value mappings in m whose keys are between low and high, exclusive:
    Map sub = m.subMap(low+"\0", high);
Parameters
fromKeylow endpoint (inclusive) of the subMap.
toKeyhigh endpoint (exclusive) of the subMap.
Return
a view of the specified range within this sorted map.
Throws
ClassCastExceptionif fromKey and toKey cannot be compared to one another using this map's comparator (or, if the map has no comparator, using natural ordering). Implementations may, but are not required to, throw this exception if fromKey or toKey cannot be compared to keys currently in the map.
IllegalArgumentExceptionif fromKey is greater than toKey; or if this map is itself a subMap, headMap, or tailMap, and fromKey or toKey are not within the specified range of the subMap, headMap, or tailMap.
NullPointerExceptionif fromKey or toKey is null and this sorted map does not tolerate null keys.
Returns a view of the portion of this sorted map whose keys are greater than or equal to fromKey. The returned sorted map is backed by this sorted map, so changes in the returned sorted map are reflected in this sorted map, and vice-versa. The returned map supports all optional map operations that this sorted map supports.

The map returned by this method will throw an IllegalArgumentException if the user attempts to insert a key outside the specified range.

Note: this method always returns a view that contains its (low) endpoint. If you need a view that does not contain this endpoint, and the element type allows for calculation of the successor a given value, merely request a tailMap bounded by successor(lowEndpoint). For example, suppose that suppose that m is a map whose keys are strings. The following idiom obtains a view containing all of the key-value mappings in m whose keys are strictly greater than low:

    Map tail = m.tailMap(low+"\0");
Parameters
fromKeylow endpoint (inclusive) of the tailMap.
Return
a view of the specified final range of this sorted map.
Throws
ClassCastExceptionif fromKey is not compatible with this map's comparator (or, if the map has no comparator, if fromKey does not implement Comparable). Implementations may, but are not required to, throw this exception if fromKey cannot be compared to keys currently in the map.
IllegalArgumentExceptionif this map is itself a subMap, headMap, or tailMap, and fromKey is not within the specified range of the subMap, headMap, or tailMap.
NullPointerExceptionif fromKey is null and this sorted map does not tolerate null keys.
Returns a string representation of this map. The string representation consists of a list of key-value mappings in the order returned by the map's entrySet view's iterator, enclosed in braces ("{}"). Adjacent mappings are separated by the characters ", " (comma and space). Each key-value mapping is rendered as the key followed by an equals sign ("=") followed by the associated value. Keys and values are converted to strings as by String.valueOf(Object).

This implementation creates an empty string buffer, appends a left brace, and iterates over the map's entrySet view, appending the string representation of each map.entry in turn. After appending each entry except the last, the string ", " is appended. Finally a right brace is appended. A string is obtained from the stringbuffer, and returned.

Return
a String representation of this map.
Returns a collection view of the values contained in this map. The collection's iterator will return the values in the order that their corresponding keys appear in the tree. The collection is backed by this TreeMap instance, so changes to this map are reflected in the collection, and vice-versa. The collection supports element removal, which removes the corresponding mapping from the map through the Iterator.remove, Collection.remove, removeAll, retainAll, and clear operations. It does not support the add or addAll operations.
Return
a collection view of the values contained in this map.
Causes current thread to wait until another thread invokes the method or the method for this object. In other words, this method behaves exactly as if it simply performs the call wait(0).

The current thread must own this object's monitor. The thread releases ownership of this monitor and waits until another thread notifies threads waiting on this object's monitor to wake up either through a call to the notify method or the notifyAll method. The thread then waits until it can re-obtain ownership of the monitor and resumes execution.

As in the one argument version, interrupts and spurious wakeups are possible, and this method should always be used in a loop:

     synchronized (obj) {
         while (<condition does not hold>)
             obj.wait();
         ... // Perform action appropriate to condition
     }
 
This method should only be called by a thread that is the owner of this object's monitor. See the notify method for a description of the ways in which a thread can become the owner of a monitor.
Throws
IllegalMonitorStateExceptionif the current thread is not the owner of the object's monitor.
InterruptedExceptionif another thread interrupted the current thread before or while the current thread was waiting for a notification. The interrupted status of the current thread is cleared when this exception is thrown.
Causes current thread to wait until either another thread invokes the method or the method for this object, or a specified amount of time has elapsed.

The current thread must own this object's monitor.

This method causes the current thread (call it T) to place itself in the wait set for this object and then to relinquish any and all synchronization claims on this object. Thread T becomes disabled for thread scheduling purposes and lies dormant until one of four things happens:

  • Some other thread invokes the notify method for this object and thread T happens to be arbitrarily chosen as the thread to be awakened.
  • Some other thread invokes the notifyAll method for this object.
  • Some other thread interrupts thread T.
  • The specified amount of real time has elapsed, more or less. If timeout is zero, however, then real time is not taken into consideration and the thread simply waits until notified.
The thread T is then removed from the wait set for this object and re-enabled for thread scheduling. It then competes in the usual manner with other threads for the right to synchronize on the object; once it has gained control of the object, all its synchronization claims on the object are restored to the status quo ante - that is, to the situation as of the time that the wait method was invoked. Thread T then returns from the invocation of the wait method. Thus, on return from the wait method, the synchronization state of the object and of thread T is exactly as it was when the wait method was invoked.

A thread can also wake up without being notified, interrupted, or timing out, a so-called spurious wakeup. While this will rarely occur in practice, applications must guard against it by testing for the condition that should have caused the thread to be awakened, and continuing to wait if the condition is not satisfied. In other words, waits should always occur in loops, like this one:

     synchronized (obj) {
         while (<condition does not hold>)
             obj.wait(timeout);
         ... // Perform action appropriate to condition
     }
 
(For more information on this topic, see Section 3.2.3 in Doug Lea's "Concurrent Programming in Java (Second Edition)" (Addison-Wesley, 2000), or Item 50 in Joshua Bloch's "Effective Java Programming Language Guide" (Addison-Wesley, 2001).

If the current thread is interrupted by another thread while it is waiting, then an InterruptedException is thrown. This exception is not thrown until the lock status of this object has been restored as described above.

Note that the wait method, as it places the current thread into the wait set for this object, unlocks only this object; any other objects on which the current thread may be synchronized remain locked while the thread waits.

This method should only be called by a thread that is the owner of this object's monitor. See the notify method for a description of the ways in which a thread can become the owner of a monitor.

Parameters
timeoutthe maximum time to wait in milliseconds.
Throws
IllegalArgumentExceptionif the value of timeout is negative.
IllegalMonitorStateExceptionif the current thread is not the owner of the object's monitor.
InterruptedExceptionif another thread interrupted the current thread before or while the current thread was waiting for a notification. The interrupted status of the current thread is cleared when this exception is thrown.
Causes current thread to wait until another thread invokes the method or the method for this object, or some other thread interrupts the current thread, or a certain amount of real time has elapsed.

This method is similar to the wait method of one argument, but it allows finer control over the amount of time to wait for a notification before giving up. The amount of real time, measured in nanoseconds, is given by:

 1000000*timeout+nanos

In all other respects, this method does the same thing as the method of one argument. In particular, wait(0, 0) means the same thing as wait(0).

The current thread must own this object's monitor. The thread releases ownership of this monitor and waits until either of the following two conditions has occurred:

  • Another thread notifies threads waiting on this object's monitor to wake up either through a call to the notify method or the notifyAll method.
  • The timeout period, specified by timeout milliseconds plus nanos nanoseconds arguments, has elapsed.

The thread then waits until it can re-obtain ownership of the monitor and resumes execution.

As in the one argument version, interrupts and spurious wakeups are possible, and this method should always be used in a loop:

     synchronized (obj) {
         while (<condition does not hold>)
             obj.wait(timeout, nanos);
         ... // Perform action appropriate to condition
     }
 
This method should only be called by a thread that is the owner of this object's monitor. See the notify method for a description of the ways in which a thread can become the owner of a monitor.
Parameters
timeoutthe maximum time to wait in milliseconds.
nanosadditional time, in nanoseconds range 0-999999.
Throws
IllegalArgumentExceptionif the value of timeout is negative or the value of nanos is not in the range 0-999999.
IllegalMonitorStateExceptionif the current thread is not the owner of this object's monitor.
InterruptedExceptionif another thread interrupted the current thread before or while the current thread was waiting for a notification. The interrupted status of the current thread is cleared when this exception is thrown.