java.util

Class TreeMap

Implemented Interfaces:
Cloneable, Map, Serializable, SortedMap

public class TreeMap
extends AbstractMap
implements SortedMap, Cloneable, Serializable

This class provides a red-black tree implementation of the SortedMap interface. Elements in the Map will be sorted by either a user-provided Comparator object, or by the natural ordering of the keys. The algorithms are adopted from Corman, Leiserson, and Rivest's Introduction to Algorithms. TreeMap guarantees O(log n) insertion and deletion of elements. That being said, there is a large enough constant coefficient in front of that "log n" (overhead involved in keeping the tree balanced), that TreeMap may not be the best choice for small collections. If something is already sorted, you may want to just use a LinkedHashMap to maintain the order while providing O(1) access. TreeMap is a part of the JDK1.2 Collections API. Null keys are allowed only if a Comparator is used which can deal with them; natural ordering cannot cope with null. Null values are always allowed. Note that the ordering must be consistent with equals to correctly implement the Map interface. If this condition is violated, the map is still well-behaved, but you may have suprising results when comparing it to other maps.

This implementation is not synchronized. If you need to share this between multiple threads, do something like:
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

The iterators are fail-fast, meaning that any structural modification, except for remove() called on the iterator itself, cause the iterator to throw a ConcurrentModificationException rather than exhibit non-deterministic behavior.

Since:
1.2
See Also:
Map, HashMap, Hashtable, LinkedHashMap, Comparable, Comparator, Collection, Collections.synchronizedSortedMap(SortedMap), Serialized Form

Constructor Summary

TreeMap()
Instantiate a new TreeMap with no elements, using the keys' natural ordering to sort.
TreeMap(Comparator c)
Instantiate a new TreeMap with no elements, using the provided comparator to sort.
TreeMap(Map map)
Instantiate a new TreeMap, initializing it with all of the elements in the provided Map.
TreeMap(SortedMap sm)
Instantiate a new TreeMap, initializing it with all of the elements in the provided SortedMap.

Method Summary

void
clear()
Clears the Map so it has no keys.
Object
clone()
Returns a shallow clone of this TreeMap.
Comparator
comparator()
Return the comparator used to sort this map, or null if it is by natural order.
boolean
containsKey(Object key)
Returns true if the map contains a mapping for the given key.
boolean
containsValue(Object value)
Returns true if the map contains at least one mapping to the given value.
Set
entrySet()
Returns a "set view" of this TreeMap's entries.
Object
firstKey()
Returns the first (lowest) key in the map.
Object
get(Object key)
Return the value in this TreeMap associated with the supplied key, or null if the key maps to nothing.
SortedMap
headMap(Object toKey)
Returns a view of this Map including all entries with keys less than toKey.
Set
keySet()
Returns a "set view" of this TreeMap's keys.
Object
lastKey()
Returns the last (highest) key in the map.
Object
put(Object key, Object value)
Puts the supplied value into the Map, mapped by the supplied key.
void
putAll(Map m)
Copies all elements of the given map into this TreeMap.
Object
remove(Object key)
Removes from the TreeMap and returns the value which is mapped by the supplied key.
int
size()
Returns the number of key-value mappings currently in this Map.
SortedMap
subMap(Object fromKey, Object toKey)
Returns a view of this Map including all entries with keys greater or equal to fromKey and less than toKey (a half-open interval).
SortedMap
tailMap(Object fromKey)
Returns a view of this Map including all entries with keys greater or equal to fromKey.
Collection
values()
Returns a "collection view" (or "bag view") of this TreeMap's values.

Methods inherited from class java.util.AbstractMap

clear, clone, containsKey, containsValue, entrySet, equals, get, hashCode, isEmpty, keySet, put, putAll, remove, size, toString, values

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

TreeMap

public TreeMap()
Instantiate a new TreeMap with no elements, using the keys' natural ordering to sort. All entries in the map must have a key which implements Comparable, and which are mutually comparable, otherwise map operations may throw a ClassCastException. Attempts to use a null key will throw a NullPointerException.
See Also:
Comparable

TreeMap

public TreeMap(Comparator c)
Instantiate a new TreeMap with no elements, using the provided comparator to sort. All entries in the map must have keys which are mutually comparable by the Comparator, otherwise map operations may throw a ClassCastException.
Parameters:
c - the sort order for the keys of this map, or null for the natural order

TreeMap

public TreeMap(Map map)
Instantiate a new TreeMap, initializing it with all of the elements in the provided Map. The elements will be sorted using the natural ordering of the keys. This algorithm runs in n*log(n) time. All entries in the map must have keys which implement Comparable and are mutually comparable, otherwise map operations may throw a ClassCastException.
Parameters:
map - a Map, whose entries will be put into this TreeMap
Throws:
ClassCastException - if the keys in the provided Map are not comparable
NullPointerException - if map is null
See Also:
Comparable

TreeMap

public TreeMap(SortedMap sm)
Instantiate a new TreeMap, initializing it with all of the elements in the provided SortedMap. The elements will be sorted using the same comparator as in the provided SortedMap. This runs in linear time.
Parameters:
sm - a SortedMap, whose entries will be put into this TreeMap
Throws:
NullPointerException - if sm is null

Method Details

clear

public void clear()
Clears the Map so it has no keys. This is O(1).
Specified by:
clear in interface Map
Overrides:
clear in interface AbstractMap

clone

public Object clone()
Returns a shallow clone of this TreeMap. The Map itself is cloned, but its contents are not.
Overrides:
clone in interface AbstractMap
Returns:
the clone

comparator

public Comparator comparator()
Return the comparator used to sort this map, or null if it is by natural order.
Specified by:
comparator in interface SortedMap
Returns:
the map's comparator

containsKey

public boolean containsKey(Object key)
Returns true if the map contains a mapping for the given key.
Specified by:
containsKey in interface Map
Overrides:
containsKey in interface AbstractMap
Parameters:
key - the key to look for
Returns:
true if the key has a mapping
Throws:
ClassCastException - if key is not comparable to map elements
NullPointerException - if key is null and the comparator is not tolerant of nulls

containsValue

public boolean containsValue(Object value)
Returns true if the map contains at least one mapping to the given value. This requires linear time.
Specified by:
containsValue in interface Map
Overrides:
containsValue in interface AbstractMap
Parameters:
value - the value to look for
Returns:
true if the value appears in a mapping

entrySet

public Set entrySet()
Returns a "set view" of this TreeMap's entries. The set is backed by the TreeMap, so changes in one show up in the other. The set supports element removal, but not element addition.

Note that the iterators for all three views, from keySet(), entrySet(), and values(), traverse the TreeMap in sorted sequence.

Specified by:
entrySet in interface Map
Overrides:
entrySet in interface AbstractMap
Returns:
a set view of the entries

firstKey

public Object firstKey()
Returns the first (lowest) key in the map.
Specified by:
firstKey in interface SortedMap
Returns:
the first key
Throws:
NoSuchElementException - if the map is empty

get

public Object get(Object key)
Return the value in this TreeMap associated with the supplied key, or null if the key maps to nothing. NOTE: Since the value could also be null, you must use containsKey to see if this key actually maps to something.
Specified by:
get in interface Map
Overrides:
get in interface AbstractMap
Parameters:
key - the key for which to fetch an associated value
Returns:
what the key maps to, if present
Throws:
ClassCastException - if key is not comparable to elements in the map
NullPointerException - if key is null but the comparator does not tolerate nulls

headMap

public SortedMap headMap(Object toKey)
Returns a view of this Map including all entries with keys less than toKey. The returned map is backed by the original, so changes in one appear in the other. The submap will throw an IllegalArgumentException for any attempt to access or add an element beyond the specified cutoff. The returned map does not include the endpoint; if you want inclusion, pass the successor element.
Specified by:
headMap in interface SortedMap
Parameters:
toKey - the (exclusive) cutoff point
Returns:
a view of the map less than the cutoff
Throws:
ClassCastException - if toKey is not compatible with the comparator (or is not Comparable, for natural ordering)
NullPointerException - if toKey is null, but the comparator does not tolerate null elements

keySet

public Set keySet()
Returns a "set view" of this TreeMap's keys. The set is backed by the TreeMap, so changes in one show up in the other. The set supports element removal, but not element addition.
Specified by:
keySet in interface Map
Overrides:
keySet in interface AbstractMap
Returns:
a set view of the keys

lastKey

public Object lastKey()
Returns the last (highest) key in the map.
Specified by:
lastKey in interface SortedMap
Returns:
the last key
Throws:
NoSuchElementException - if the map is empty

put

public Object put(Object key,
                  Object value)
Puts the supplied value into the Map, mapped by the supplied key. The value may be retrieved by any object which equals() this key. NOTE: Since the prior value could also be null, you must first use containsKey if you want to see if you are replacing the key's mapping.
Specified by:
put in interface Map
Overrides:
put in interface AbstractMap
Parameters:
key - the key used to locate the value
value - the value to be stored in the Map
Returns:
the prior mapping of the key, or null if there was none
Throws:
ClassCastException - if key is not comparable to current map keys
NullPointerException - if key is null, but the comparator does not tolerate nulls

putAll

public void putAll(Map m)
Copies all elements of the given map into this TreeMap. If this map already has a mapping for a key, the new mapping replaces the current one.
Specified by:
putAll in interface Map
Overrides:
putAll in interface AbstractMap
Parameters:
m - the map to be added
Throws:
ClassCastException - if a key in m is not comparable with keys in the map
NullPointerException - if a key in m is null, and the comparator does not tolerate nulls

remove

public Object remove(Object key)
Removes from the TreeMap and returns the value which is mapped by the supplied key. If the key maps to nothing, then the TreeMap remains unchanged, and null is returned. NOTE: Since the value could also be null, you must use containsKey to see if you are actually removing a mapping.
Specified by:
remove in interface Map
Overrides:
remove in interface AbstractMap
Parameters:
key - the key used to locate the value to remove
Returns:
whatever the key mapped to, if present
Throws:
ClassCastException - if key is not comparable to current map keys
NullPointerException - if key is null, but the comparator does not tolerate nulls

size

public int size()
Returns the number of key-value mappings currently in this Map.
Specified by:
size in interface Map
Overrides:
size in interface AbstractMap
Returns:
the size

subMap

public SortedMap subMap(Object fromKey,
                        Object toKey)
Returns a view of this Map including all entries with keys greater or equal to fromKey and less than toKey (a half-open interval). The returned map is backed by the original, so changes in one appear in the other. The submap will throw an IllegalArgumentException for any attempt to access or add an element beyond the specified cutoffs. The returned map includes the low endpoint but not the high; if you want to reverse this behavior on either end, pass in the successor element.
Specified by:
subMap in interface SortedMap
Parameters:
fromKey - the (inclusive) low cutoff point
toKey - the (exclusive) high cutoff point
Returns:
a view of the map between the cutoffs
Throws:
ClassCastException - if either cutoff is not compatible with the comparator (or is not Comparable, for natural ordering)
NullPointerException - if fromKey or toKey is null, but the comparator does not tolerate null elements
IllegalArgumentException - if fromKey is greater than toKey

tailMap

public SortedMap tailMap(Object fromKey)
Returns a view of this Map including all entries with keys greater or equal to fromKey. The returned map is backed by the original, so changes in one appear in the other. The submap will throw an IllegalArgumentException for any attempt to access or add an element beyond the specified cutoff. The returned map includes the endpoint; if you want to exclude it, pass in the successor element.
Specified by:
tailMap in interface SortedMap
Parameters:
fromKey - the (inclusive) low cutoff point
Returns:
a view of the map above the cutoff
Throws:
ClassCastException - if fromKey is not compatible with the comparator (or is not Comparable, for natural ordering)
NullPointerException - if fromKey is null, but the comparator does not tolerate null elements

values

public Collection values()
Returns a "collection view" (or "bag view") of this TreeMap's values. The collection is backed by the TreeMap, so changes in one show up in the other. The collection supports element removal, but not element addition.
Specified by:
values in interface Map
Overrides:
values in interface AbstractMap
Returns:
a bag view of the values

TreeMap.java -- a class providing a basic Red-Black Tree data structure, mapping Object --> Object Copyright (C) 1998, 1999, 2000, 2001, 2002, 2004, 2005 Free Software Foundation, Inc. This file is part of GNU Classpath. GNU Classpath is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version. GNU Classpath is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with GNU Classpath; see the file COPYING. If not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. Linking this library statically or dynamically with other modules is making a combined work based on this library. Thus, the terms and conditions of the GNU General Public License cover the whole combination. As a special exception, the copyright holders of this library give you permission to link this library with independent modules to produce an executable, regardless of the license terms of these independent modules, and to copy and distribute the resulting executable under terms of your choice, provided that you also meet, for each linked independent module, the terms and conditions of the license of that module. An independent module is a module which is not derived from or based on this library. If you modify this library, you may extend this exception to your version of the library, but you are not obligated to do so. If you do not wish to do so, delete this exception statement from your version.