java.util
Class TreeMap
- Cloneable, Map, Serializable, SortedMap
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.
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.
|
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.
|
clear , clone , containsKey , containsValue , entrySet , equals , get , hashCode , isEmpty , keySet , put , putAll , remove , size , toString , values |
clone , equals , finalize , getClass , hashCode , notify , notifyAll , toString , wait , wait , wait |
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
.
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
.
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
.
map
- a Map, whose entries will be put into this TreeMap
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.
sm
- a SortedMap, whose entries will be put into this TreeMap
clone
public Object clone()
Returns a shallow clone of this TreeMap. The Map itself is cloned,
but its contents are not.
- clone in interface AbstractMap
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.
- entrySet in interface Map
- entrySet in interface AbstractMap
- a set view of the entries
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.
- get in interface Map
- get in interface AbstractMap
key
- the key for which to fetch an associated value
- what the key maps to, if present
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.
- headMap in interface SortedMap
toKey
- the (exclusive) cutoff point
- a view of the map less than the cutoff
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.
- keySet in interface Map
- keySet in interface AbstractMap
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.
- put in interface Map
- put in interface AbstractMap
key
- the key used to locate the valuevalue
- the value to be stored in the Map
- the prior mapping of the key, or null if there was none
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.
- putAll in interface Map
- putAll in interface AbstractMap
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.
- remove in interface Map
- remove in interface AbstractMap
key
- the key used to locate the value to remove
- whatever the key mapped to, if present
size
public int size()
Returns the number of key-value mappings currently in this Map.
- size in interface Map
- size in interface AbstractMap
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.
- subMap in interface SortedMap
fromKey
- the (inclusive) low cutoff pointtoKey
- the (exclusive) high cutoff point
- a view of the map between the cutoffs
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.
- tailMap in interface SortedMap
fromKey
- the (inclusive) low cutoff point
- a view of the map above the cutoff
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.
- values in interface Map
- values in interface AbstractMap
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.