edu.emory.mathcs.backport.java.util

Class TreeMap

Implemented Interfaces:
NavigableMap, Serializable, SortedMap

public class TreeMap
extends AbstractMap
implements NavigableMap, Serializable

Sorted map implementation based on a red-black tree and implementing all the methods from the NavigableMap interface.
Author:
Dawid Kurzyniec

Nested Class Summary

static class
TreeMap.Entry

Nested classes/interfaces inherited from class edu.emory.mathcs.backport.java.util.AbstractMap

AbstractMap.SimpleEntry, AbstractMap.SimpleImmutableEntry

Constructor Summary

TreeMap()
Sole constructor.
TreeMap(Comparator comparator)
TreeMap(Map map)
TreeMap(SortedMap map)

Method Summary

Map.Entry
ceilingEntry(Object key)
Object
ceilingKey(Object key)
void
clear()
Object
clone()
Comparator
comparator()
boolean
containsKey(Object key)
boolean
containsValue(Object value)
NavigableSet
descendingKeySet()
Returns a reverse order NavigableSet view of the keys contained in this map.
NavigableMap
descendingMap()
Set
entrySet()
Map.Entry
firstEntry()
Object
firstKey()
Map.Entry
floorEntry(Object key)
Object
floorKey(Object key)
Object
get(Object key)
SortedMap
headMap(Object toKey)
Equivalent to headMap(toKey, false).
NavigableMap
headMap(Object toKey, boolean toInclusive)
Returns a view of the portion of this map whose keys are less than (or equal to, if inclusive is true) toKey.
Map.Entry
higherEntry(Object key)
Object
higherKey(Object key)
boolean
isEmpty()
Set
keySet()
Map.Entry
lastEntry()
Object
lastKey()
Map.Entry
lowerEntry(Object key)
Object
lowerKey(Object key)
NavigableSet
navigableKeySet()
Returns a NavigableSet view of the keys contained in this map.
Map.Entry
pollFirstEntry()
Map.Entry
pollLastEntry()
Object
put(Object key, Object value)
void
putAll(Map map)
Object
remove(Object key)
int
size()
SortedMap
subMap(Object fromKey, Object toKey)
Equivalent to subMap(fromKey, true, toKey, false).
NavigableMap
subMap(Object fromKey, boolean fromInclusive, Object toKey, boolean toInclusive)
Returns a view of the portion of this map whose keys range from fromKey to toKey.
SortedMap
tailMap(Object fromKey)
Equivalent to tailMap(fromKey, true).
NavigableMap
tailMap(Object fromKey, boolean fromInclusive)
Returns a view of the portion of this map whose keys are greater than (or equal to, if inclusive is true) fromKey.

Methods inherited from class edu.emory.mathcs.backport.java.util.AbstractMap

keySet

Constructor Details

TreeMap

public TreeMap()
Sole constructor. (For invocation by subclass constructors, typically implicit.)

TreeMap

public TreeMap(Comparator comparator)

TreeMap

public TreeMap(Map map)

TreeMap

public TreeMap(SortedMap map)

Method Details

ceilingEntry

public Map.Entry ceilingEntry(Object key)
Specified by:
ceilingEntry in interface NavigableMap
Since:
1.6

ceilingKey

public Object ceilingKey(Object key)
Specified by:
ceilingKey in interface NavigableMap
Since:
1.6

clear

public void clear()

clone

public Object clone()

comparator

public Comparator comparator()

containsKey

public boolean containsKey(Object key)

containsValue

public boolean containsValue(Object value)

descendingKeySet

public NavigableSet descendingKeySet()
Returns a reverse order NavigableSet view of the keys contained in this map. The set's iterator returns the keys in descending order. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. If the map is modified while an iteration over the set is in progress (except through the iterator's own remove operation), the results of the iteration are undefined. 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.
Specified by:
descendingKeySet in interface NavigableMap
Returns:
a reverse order navigable set view of the keys in this map

descendingMap

public NavigableMap descendingMap()
Specified by:
descendingMap in interface NavigableMap
Since:
1.6

entrySet

public Set entrySet()

firstEntry

public Map.Entry firstEntry()
Specified by:
firstEntry in interface NavigableMap
Since:
1.6

firstKey

public Object firstKey()

floorEntry

public Map.Entry floorEntry(Object key)
Specified by:
floorEntry in interface NavigableMap
Since:
1.6

floorKey

public Object floorKey(Object key)
Specified by:
floorKey in interface NavigableMap
Since:
1.6

get

public Object get(Object key)

headMap

public SortedMap headMap(Object toKey)
Equivalent to headMap(toKey, false).
Specified by:
headMap in interface NavigableMap

headMap

public NavigableMap headMap(Object toKey,
                            boolean toInclusive)
Returns a view of the portion of this map whose keys are less than (or equal to, if inclusive is true) toKey. The returned map is backed by this map, so changes in the returned map are reflected in this map, and vice-versa. The returned map supports all optional map operations that this map supports.

The returned map will throw an IllegalArgumentException on an attempt to insert a key outside its range.

Specified by:
headMap in interface NavigableMap
Parameters:
toKey - high endpoint of the keys in the returned map
Returns:
a view of the portion of this map whose keys are less than (or equal to, if inclusive is true) toKey

higherEntry

public Map.Entry higherEntry(Object key)
Specified by:
higherEntry in interface NavigableMap
Since:
1.6

higherKey

public Object higherKey(Object key)
Specified by:
higherKey in interface NavigableMap
Since:
1.6

isEmpty

public boolean isEmpty()

keySet

public Set keySet()
Overrides:
keySet in interface AbstractMap

lastEntry

public Map.Entry lastEntry()
Specified by:
lastEntry in interface NavigableMap
Since:
1.6

lastKey

public Object lastKey()

lowerEntry

public Map.Entry lowerEntry(Object key)
Specified by:
lowerEntry in interface NavigableMap
Since:
1.6

lowerKey

public Object lowerKey(Object key)
Specified by:
lowerKey in interface NavigableMap
Since:
1.6

navigableKeySet

public NavigableSet navigableKeySet()
Returns a NavigableSet view of the keys contained in this map. The set's iterator returns the keys in ascending order. The set is backed by the map, so changes to the map are reflected in the set, and vice-versa. If the map is modified while an iteration over the set is in progress (except through the iterator's own remove operation), the results of the iteration are undefined. 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.
Specified by:
navigableKeySet in interface NavigableMap
Returns:
a navigable set view of the keys in this map

pollFirstEntry

public Map.Entry pollFirstEntry()
Specified by:
pollFirstEntry in interface NavigableMap
Since:
1.6

pollLastEntry

public Map.Entry pollLastEntry()
Specified by:
pollLastEntry in interface NavigableMap
Since:
1.6

put

public Object put(Object key,
                  Object value)

putAll

public void putAll(Map map)

remove

public Object remove(Object key)

size

public int size()

subMap

public SortedMap subMap(Object fromKey,
                        Object toKey)
Equivalent to subMap(fromKey, true, toKey, false).
Specified by:
subMap in interface NavigableMap

subMap

public NavigableMap subMap(Object fromKey,
                           boolean fromInclusive,
                           Object toKey,
                           boolean toInclusive)
Returns a view of the portion of this map whose keys range from fromKey to toKey. If fromKey and toKey are equal, the returned map is empty unless fromExclusive and toExclusive are both true. The returned map is backed by this map, so changes in the returned map are reflected in this map, and vice-versa. The returned map supports all optional map operations that this map supports.

The returned map will throw an IllegalArgumentException on an attempt to insert a key outside of its range, or to construct a submap either of whose endpoints lie outside its range.

Specified by:
subMap in interface NavigableMap
Parameters:
fromKey - low endpoint of the keys in the returned map
fromInclusive - true if the low endpoint is to be included in the returned view
toKey - high endpoint of the keys in the returned map
toInclusive - true if the high endpoint is to be included in the returned view
Returns:
a view of the portion of this map whose keys range from fromKey to toKey

tailMap

public SortedMap tailMap(Object fromKey)
Equivalent to tailMap(fromKey, true).
Specified by:
tailMap in interface NavigableMap

tailMap

public NavigableMap tailMap(Object fromKey,
                            boolean fromInclusive)
Returns a view of the portion of this map whose keys are greater than (or equal to, if inclusive is true) fromKey. The returned map is backed by this map, so changes in the returned map are reflected in this map, and vice-versa. The returned map supports all optional map operations that this map supports.

The returned map will throw an IllegalArgumentException on an attempt to insert a key outside its range.

Specified by:
tailMap in interface NavigableMap
Parameters:
fromKey - low endpoint of the keys in the returned map
Returns:
a view of the portion of this map whose keys are greater than (or equal to, if inclusive is true) fromKey