TreeMap
A Red-Black tree based implementation of the MutableMap interface, striving for compatibility with the subset of TreeMap functionality potentially used by Lucene.
The map is sorted according to the natural ordering of its keys (if they implement Comparable), or by a Comparator provided at map creation time.
This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations.
Note that this implementation is not synchronized. External synchronization is required if multiple threads access a map concurrently and at least one modifies it structurally.
Iterators are fail-fast: they throw ConcurrentModificationException if the map is structurally modified after iterator creation, except through the iterator's own remove method.
Type Parameters
the type of keys maintained by this map
the type of mapped values
Constructors
Constructs a new, empty tree map, using the natural ordering of its keys. All keys inserted into the map must implement the Comparable interface and be mutually comparable.
Constructs a new, empty tree map, ordered according to the given comparator. All keys inserted into the map must be mutually comparable by the given comparator.
Constructs a new tree map containing the same mappings as the given map, ordered according to the natural ordering of its keys. Requires keys to be Comparable. Runs in n*log(n) time.
Constructs a new tree map containing the same mappings and using the same ordering as the specified sorted map (approximated by checking if the input map is also a TreeMap with the same comparator). If compatible, this method runs in linear time (O(n)). Otherwise, it falls back to O(n log n).
Types
Properties
Returns a MutableSet view of the mappings contained in this map. The set's iterator returns the entries in ascending key 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, or through the setValue operation on a map entry returned by the iterator) 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.
Returns a Set view of the mappings contained in this map. The set's iterator returns the entries in ascending key 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, or through the setValue operation on a map entry returned by the iterator) 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.
Returns a MutableSet 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.
Returns a Set 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.
Returns a {@link Collection} view of the values contained in this map.
Functions
Returns a key-value mapping associated with the least key greater than or equal to the given key, or null if there is no such key.
Returns the least key greater than or equal to the given key, or null if there is no such key.
Returns the comparator used to order the keys in this map, or null if this map uses the natural ordering of its keys.
If the specified key is not already associated with a value (or is mapped to null), computes its value using the given mapping function and enters it into this map unless null.
ported from java.util.Map.computeIfAbsent()
Returns true if this map contains a mapping for the specified key.
Returns true if this map maps one or more keys to the specified value. This operation requires time linear in the map size.
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.
Returns a reverse order view of the mappings contained in this map. The descending map is backed by this map, so changes to the map are reflected in the descending map, and vice-versa. If either map is modified while an iteration over a collection view of either map is in progress (except through the iterator's own remove operation), the results of the iteration are undefined.
Returns the first (lowest) key-value mapping currently in this map.
Returns a key-value mapping associated with the greatest key less than or equal to the given key, or null if there is no such key.
Returns a key-value mapping associated with the least key strictly greater than the given key, or null if there is no such key.
Returns a key-value mapping associated with the greatest key strictly less than the given key, or null if there is no such key.
If the specified key is not already associated with a value or is associated with null, associates it with the given non-null value. Otherwise, replaces the associated value with the results of the given remapping function, or removes if the result is null.
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.
Removes and returns a key-value mapping associated with the least key in this map, or null if the map is empty.
Removes and returns a key-value mapping associated with the greatest key in this map, or null if the map is empty.
If the specified key is not already associated with a value (or is mapped to null), associates it with the given value and returns null, else returns the current value.
ported from java.util.Map.putIfAbsent()
{@inheritDoc}
{@inheritDoc}
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 fromInclusive and toInclusive 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.
{@inheritDoc}
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.