PSortedMap based on a self-balancing binary search tree.
Instances of this class are obtained via any of various static factory methods and static collector methods. These methods come in pairs, with one version that accepts an explicit comparator to use and one version that uses the natural ordering of the elements.
All operations are guaranteed to complete within O(log n) time, except for plusAll and minusAll, whose time cost is equivalent to the corresponding sequence of calls to plus or minus. A complete iteration pass over entrySet() completes in O(n) time. A few operations -- namely comparator, descendingKeySet, descendingMap, entrySet, isEmpty, keySet, navigableKeySet, and size -- complete in O(1) time.
| Modifier and Type | Field and Description |
|---|---|
| private final boolean | |
| private final Comparator | |
| private static final long | |
| private final KVTree |
| Access | Constructor and Description |
|---|---|
| private | TreePMap(final KVTree<K, V> tree, final Comparator<? super K> ltrComparator, final boolean isLeftToRight)
|
| Modifier and Type | Method and Description |
|---|---|
| public Map. | ceilingEntry(final K
the key key)Implements java. Returns a key-value mapping associated with the least key
greater than or equal to the given key, or |
| public K | ceilingKey(final K
the key key)Implements java. Returns the least key greater than or equal to the given key,
or |
| public Comparator | comparator()
Implements org. Returns the comparator used to order the keys in this map, or
|
| public boolean | containsKey(final Object
key whose presence in this map is to be tested key)Overrides java. Implements java. Returns |
| public PSortedSet | descendingKeySet()
Implements org. Returns a reverse order |
| public TreePMap | descendingMap()
Implements org. Returns a reverse order view of the mappings contained in this map. |
| public static < the type of keys to be maintained by the map K extends Comparablethe type of mapped values V> TreePMap | Returns: an empty TreePMap using the natural orderingReturns an empty TreePMap using the natural ordering. |
| public static < the type of keys to be maintained by the map K, the type of mapped values V> TreePMap | Returns: an empty TreePMap using the specified comparatorthe comparator according to which keys should be ordered comparator)Returns an empty TreePMap using the specified comparator. |
| public Set | entrySet()
Implements abstract java. Implements java. Returns a |
| public Map. | firstEntry()
Implements java. Returns a key-value mapping associated with the least
key in this map, or |
| public K | firstKey()
Implements java. Returns the first (lowest) key currently in this map. |
| public Map. | floorEntry(final K
the key key)Implements java. Returns a key-value mapping associated with the greatest key
less than or equal to the given key, or |
| public K | floorKey(final K
the key key)Implements java. Returns the greatest key less than or equal to the given key,
or |
| public static < the type of keys to be maintained by the map K extends Comparablethe type of mapped values V> TreePMap | |
| public static < the type of keys to be maintained by the map K, the type of mapped values V> TreePMap | Returns: a TreePMap with the specified comparator and mappingsthe comparator to use comparator, final Map<? extends K, ? extends V> the mappings to include map)Returns a TreePMap with the specified comparator and mappings. |
| public static < the type of keys to be maintained by the map K, the type of mapped values V> TreePMap | Returns: a TreePMap with the same mappings and ordering as the specified setthe map whose mappings and ordering to use map)Returns a TreePMap with the same mappings and ordering as the specified map. |
| public V | get(final Object
the key whose associated value is to be returned key)Overrides java. Implements java. Returns the value to which the specified key is mapped,
or |
| public TreePMap | headMap(final K
high endpoint (exclusive) of the keys in the returned map toKey)Implements org. Returns a view of the portion of this map whose keys are
strictly less than |
| public TreePMap | headMap(final K
high endpoint of the keys in the returned map toKey, final boolean true if the high endpoint
is to be included in the returned viewImplements org. Returns a view of the portion of this map whose keys are less than (or
equal to, if |
| public Map. | higherEntry(final K
the key key)Implements java. Returns a key-value mapping associated with the least key
strictly greater than the given key, or |
| public K | higherKey(final K
the key key)Implements java. Returns the least key strictly greater than the given key, or
|
| public boolean | isEmpty()
Overrides java. Implements java. Returns |
| public TreePSet | keySet()
Overrides java. Implements org. Returns a |
| public Map. | lastEntry()
Implements java. Returns a key-value mapping associated with the greatest
key in this map, or |
| public K | lastKey()
Implements java. Returns the last (highest) key currently in this map. |
| public Map. | lowerEntry(final K
the key key)Implements java. Returns a key-value mapping associated with the greatest key
strictly less than the given key, or |
| public K | lowerKey(final K
the key key)Implements java. Returns the greatest key strictly less than the given key, or
|
| public TreePMap | |
| public TreePMap | |
| public TreePMap | |
| public TreePMap | |
| public TreePSet | navigableKeySet()
Implements org. Returns a |
| public TreePMap | |
| public TreePMap | |
| private KVTree | search(final K key, final KVTree.
|
| public static < the type of keys to be maintained by the map K extends Comparablethe type of mapped values V> TreePMap | Returns: a TreePMap containing the specified mapping and using the natural orderingthe key key, final V the value value)Returns a TreePMap with a single mapping, using the natural ordering of its keys. |
| public static < the type of keys to be maintained by the map K, the type of mapped values V> TreePMap | Returns: a TreePMap containing the specified mapping and using the specified comparatorthe comparator according to which keys should be ordered comparator, final K the key key, final V the value value)Returns a TreePMap with a single element, using the specified comparator. |
| public int | size()
Overrides java. Implements java. Returns the number of key-value mappings in this map. |
| private static <T> T | |
| public TreePMap | subMap(final K
low endpoint (inclusive) of the keys in the returned map fromKey, final K high endpoint (exclusive) of the keys in the returned map toKey)Implements org. Returns a view of the portion of this map whose keys range from
|
| public TreePMap | subMap(final K
low endpoint of the keys in the returned map fromKey, final boolean true if the low endpoint
is to be included in the returned viewhigh endpoint of the keys in the returned map toKey, final boolean true if the high endpoint
is to be included in the returned viewImplements org. Returns a view of the portion of this map whose keys range from
|
| public TreePMap | tailMap(final K
low endpoint (inclusive) of the keys in the returned map fromKey)Implements org. Returns a view of the portion of this map whose keys are
greater than or equal to |
| public TreePMap | tailMap(final K
low endpoint of the keys in the returned map fromKey, final boolean true if the low endpoint
is to be included in the returned viewImplements org. Returns a view of the portion of this map whose keys are greater than (or
equal to, if |
| public static <T, the type of keys to be maintained by the map K extends Comparablethe type of mapped values V> Collector | Returns: a collector that gathers the elements of the stream into a TreePMapa function to compute the key from a stream element keyMapper, final Function<? super T, ? extends V> a function to compute the value from a stream element valueMapper)Returns a collector that gathers a stream into a TreePMap with mappings computed from the elements of the stream (using the specified keyMapper and valueMapper), in the order determined by the natural ordering of the keys. |
| public static <T, the type of keys to be maintained by the map K, the type of mapped values V> Collector | Returns: a collector that gathers the elements of the stream into a TreePMapthe comparator according to which keys should be ordered comparator, final Function<? super T, ? extends K> a function to compute the key from a stream element keyMapper, final Function<? super T, ? extends V> a function to compute the value from a stream element valueMapper)Returns a collector that gathers a stream into a TreePMap with mappings computed from the elements of the stream (using the specified keyMapper and valueMapper), in the order determined by the specified comparator. |
| public static <T, the type of keys to be maintained by the map K extends Comparablethe type of mapped values V> Collector | Returns: a collector that gathers the elements of the stream into a TreePMapa function to compute the key from a stream element keyMapper, final Function<? super T, ? extends V> a function to compute the value from a stream element valueMapper, final BinaryOperator<V> a function to merge duplicate values mergeFunction)Returns a collector that gathers a stream into a TreePMap with mappings computed from the elements of the stream (using the specified keyMapper and valueMapper, with duplicates reconciled via the specified mergeFunction), in the order determined by the natural ordering of the keys. |
| public static <T, the type of keys to be maintained by the map K, the type of mapped values V> Collector | Returns: a collector that gathers the elements of the stream into a TreePMapthe comparator according to which keys should be ordered comparator, final Function<? super T, ? extends K> a function to compute the key from a stream element keyMapper, final Function<? super T, ? extends V> a function to compute the value from a stream element valueMapper, final BinaryOperator<V> a function to merge duplicate values mergeFunction)Returns a collector that gathers a stream into a TreePMap with mappings computed from the elements of the stream (using the specified keyMapper and valueMapper, with duplicates reconciled via the specified mergeFunction), in the order determined by the specified comparator. |
| private TreePMap |