- java.lang.Object
-
- java.util.AbstractMap<K,V>
-
- org.pcollections.AbstractUnmodifiableMap<K,V>
-
- org.pcollections.TreePMap<K,V>
-
- Type Parameters:
K
- the type of keys maintained by this mapV
- the type of mapped values
- All Implemented Interfaces:
java.io.Serializable
,java.util.Map<K,V>
,java.util.NavigableMap<K,V>
,java.util.SortedMap<K,V>
,PMap<K,V>
,PSortedMap<K,V>
public final class TreePMap<K,V> extends AbstractUnmodifiableMap<K,V> implements PSortedMap<K,V>, java.io.Serializable
An implementation ofPSortedMap
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.
- Since:
- 3.2.0
- See Also:
- Serialized Form
-
-
Field Summary
Fields Modifier and Type Field Description private boolean
isLeftToRight
private java.util.Comparator<? super K>
ltrComparator
private static long
serialVersionUID
private KVTree<K,V>
tree
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description java.util.Map.Entry<K,V>
ceilingEntry(K key)
K
ceilingKey(K key)
java.util.Comparator<? super K>
comparator()
boolean
containsKey(java.lang.Object key)
PSortedSet<K>
descendingKeySet()
TreePMap<K,V>
descendingMap()
static <K extends java.lang.Comparable<? super K>,V>
TreePMap<K,V>empty()
Returns an empty TreePMap using the natural ordering.static <K,V>
TreePMap<K,V>empty(java.util.Comparator<? super K> comparator)
Returns an empty TreePMap using the specified comparator.java.util.Set<java.util.Map.Entry<K,V>>
entrySet()
java.util.Map.Entry<K,V>
firstEntry()
K
firstKey()
java.util.Map.Entry<K,V>
floorEntry(K key)
K
floorKey(K key)
static <K,V>
TreePMap<K,V>from(java.util.Comparator<? super K> comparator, java.util.Map<? extends K,? extends V> map)
Returns a TreePMap with the specified comparator and mappings.static <K extends java.lang.Comparable<? super K>,V>
TreePMap<K,V>from(java.util.Map<? extends K,? extends V> map)
Returns a TreePMap with the specified mappings, using the natural ordering of the keys.static <K,V>
TreePMap<K,V>fromSortedMap(java.util.SortedMap<K,? extends V> map)
Returns a TreePMap with the same mappings and ordering as the specified map.V
get(java.lang.Object key)
TreePMap<K,V>
headMap(K toKey)
TreePMap<K,V>
headMap(K toKey, boolean inclusive)
java.util.Map.Entry<K,V>
higherEntry(K key)
K
higherKey(K key)
boolean
isEmpty()
TreePSet<K>
keySet()
java.util.Map.Entry<K,V>
lastEntry()
K
lastKey()
java.util.Map.Entry<K,V>
lowerEntry(K key)
K
lowerKey(K key)
TreePMap<K,V>
minus(java.lang.Object key)
TreePMap<K,V>
minusAll(java.util.Collection<?> keys)
TreePMap<K,V>
minusFirstEntry()
TreePMap<K,V>
minusLastEntry()
TreePSet<K>
navigableKeySet()
TreePMap<K,V>
plus(K key, V value)
TreePMap<K,V>
plusAll(java.util.Map<? extends K,? extends V> map)
private KVTree<K,V>
search(K key, KVTree.SearchType searchTypeIfLeftToRight, KVTree.SearchType searchTypeIfRightToLeft)
static <K,V>
TreePMap<K,V>singleton(java.util.Comparator<? super K> comparator, K key, V value)
Returns a TreePMap with a single element, using the specified comparator.static <K extends java.lang.Comparable<? super K>,V>
TreePMap<K,V>singleton(K key, V value)
Returns a TreePMap with a single mapping, using the natural ordering of its keys.int
size()
private static <T> T
sneakilyDowncast(java.lang.Object o)
TreePMap<K,V>
subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
TreePMap<K,V>
subMap(K fromKey, K toKey)
TreePMap<K,V>
tailMap(K fromKey)
TreePMap<K,V>
tailMap(K fromKey, boolean inclusive)
static <T,K,V>
java.util.stream.Collector<T,?,TreePMap<K,V>>toTreePMap(java.util.Comparator<? super K> comparator, java.util.function.Function<? super T,? extends K> keyMapper, java.util.function.Function<? super T,? extends V> 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.static <T,K,V>
java.util.stream.Collector<T,?,TreePMap<K,V>>toTreePMap(java.util.Comparator<? super K> comparator, java.util.function.Function<? super T,? extends K> keyMapper, java.util.function.Function<? super T,? extends V> valueMapper, java.util.function.BinaryOperator<V> 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.static <T,K extends java.lang.Comparable<? super K>,V>
java.util.stream.Collector<T,?,TreePMap<K,V>>toTreePMap(java.util.function.Function<? super T,? extends K> keyMapper, java.util.function.Function<? super T,? extends V> 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.static <T,K extends java.lang.Comparable<? super K>,V>
java.util.stream.Collector<T,?,TreePMap<K,V>>toTreePMap(java.util.function.Function<? super T,? extends K> keyMapper, java.util.function.Function<? super T,? extends V> valueMapper, java.util.function.BinaryOperator<V> 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.private TreePMap<K,V>
withTree(KVTree<K,V> updatedTree)
-
Methods inherited from class org.pcollections.AbstractUnmodifiableMap
clear, compute, computeIfAbsent, computeIfPresent, merge, put, putAll, putIfAbsent, remove, replace, replaceAll
-
Methods inherited from class java.util.AbstractMap
clone, containsValue, equals, hashCode, toString, values
-
Methods inherited from class java.lang.Object
finalize, getClass, notify, notifyAll, wait, wait, wait
-
Methods inherited from interface java.util.Map
compute, computeIfAbsent, computeIfPresent, containsValue, equals, forEach, getOrDefault, hashCode, merge, putIfAbsent, remove, replace, replace, replaceAll
-
Methods inherited from interface org.pcollections.PSortedMap
pollFirstEntry, pollLastEntry
-
-
-
-
Field Detail
-
serialVersionUID
private static final long serialVersionUID
- See Also:
- Constant Field Values
-
ltrComparator
private final java.util.Comparator<? super K> ltrComparator
-
isLeftToRight
private final boolean isLeftToRight
-
-
Method Detail
-
empty
public static <K extends java.lang.Comparable<? super K>,V> TreePMap<K,V> empty()
Returns an empty TreePMap using the natural ordering.- Type Parameters:
K
- the type of keys to be maintained by the mapV
- the type of mapped values- Returns:
- an empty TreePMap using the natural ordering
-
empty
public static <K,V> TreePMap<K,V> empty(java.util.Comparator<? super K> comparator)
Returns an empty TreePMap using the specified comparator.- Type Parameters:
K
- the type of keys to be maintained by the mapV
- the type of mapped values- Parameters:
comparator
- the comparator according to which keys should be ordered- Returns:
- an empty TreePMap using the specified comparator
- Throws:
java.lang.NullPointerException
- if comparator is null
-
from
public static <K extends java.lang.Comparable<? super K>,V> TreePMap<K,V> from(java.util.Map<? extends K,? extends V> map)
Returns a TreePMap with the specified mappings, using the natural ordering of the keys.- Type Parameters:
K
- the type of keys to be maintained by the mapV
- the type of mapped values- Parameters:
map
- the mappings to include- Returns:
- a TreePMap containing the specified mappings and using the natural ordering of the keys
- Throws:
java.lang.NullPointerException
- if the map is null or contains a null key
-
from
public static <K,V> TreePMap<K,V> from(java.util.Comparator<? super K> comparator, java.util.Map<? extends K,? extends V> map)
Returns a TreePMap with the specified comparator and mappings.- Type Parameters:
K
- the type of keys to be maintained by the mapV
- the type of mapped values- Parameters:
comparator
- the comparator to usemap
- the mappings to include- Returns:
- a TreePMap with the specified comparator and mappings
- Throws:
java.lang.NullPointerException
- if the comparator or map is null or the map contains a null key
-
fromSortedMap
public static <K,V> TreePMap<K,V> fromSortedMap(java.util.SortedMap<K,? extends V> map)
Returns a TreePMap with the same mappings and ordering as the specified map. This is essentially equivalent toTreePMap.from(map.comparator(), map)
, except that it gracefully handles a null comparator, and is much more efficient.- Type Parameters:
K
- the type of keys to be maintained by the mapV
- the type of mapped values- Parameters:
map
- the map whose mappings and ordering to use- Returns:
- a TreePMap with the same mappings and ordering as the specified set
- Throws:
java.lang.NullPointerException
- if the specified map is null or contains a null key
-
singleton
public static <K extends java.lang.Comparable<? super K>,V> TreePMap<K,V> singleton(K key, V value)
Returns a TreePMap with a single mapping, using the natural ordering of its keys.- Type Parameters:
K
- the type of keys to be maintained by the mapV
- the type of mapped values- Parameters:
key
- the keyvalue
- the value- Returns:
- a TreePMap containing the specified mapping and using the natural ordering
- Throws:
java.lang.NullPointerException
- if the specified key or value is null
-
singleton
public static <K,V> TreePMap<K,V> singleton(java.util.Comparator<? super K> comparator, K key, V value)
Returns a TreePMap with a single element, using the specified comparator.- Type Parameters:
K
- the type of keys to be maintained by the mapV
- the type of mapped values- Parameters:
comparator
- the comparator according to which keys should be orderedkey
- the keyvalue
- the value- Returns:
- a TreePMap containing the specified mapping and using the specified comparator
- Throws:
java.lang.NullPointerException
- if the specified comparator or key is null
-
toTreePMap
public static <T,K extends java.lang.Comparable<? super K>,V> java.util.stream.Collector<T,?,TreePMap<K,V>> toTreePMap(java.util.function.Function<? super T,? extends K> keyMapper, java.util.function.Function<? super T,? extends V> 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. In the event of duplicate keys, the collector will throw IllegalStateException.- Type Parameters:
K
- the type of keys to be maintained by the mapV
- the type of mapped values- Parameters:
keyMapper
- a function to compute the key from a stream elementvalueMapper
- a function to compute the value from a stream element- Returns:
- a collector that gathers the elements of the stream into a TreePMap
- Throws:
java.lang.NullPointerException
- if either keyMapper or valueMapper is null
-
toTreePMap
public static <T,K,V> java.util.stream.Collector<T,?,TreePMap<K,V>> toTreePMap(java.util.Comparator<? super K> comparator, java.util.function.Function<? super T,? extends K> keyMapper, java.util.function.Function<? super T,? extends V> 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. In the event of duplicate keys, the collector will throw IllegalStateException.- Type Parameters:
K
- the type of keys to be maintained by the mapV
- the type of mapped values- Parameters:
comparator
- the comparator according to which keys should be orderedkeyMapper
- a function to compute the key from a stream elementvalueMapper
- a function to compute the value from a stream element- Returns:
- a collector that gathers the elements of the stream into a TreePMap
- Throws:
java.lang.NullPointerException
- if any of this method's arguments are null
-
toTreePMap
public static <T,K extends java.lang.Comparable<? super K>,V> java.util.stream.Collector<T,?,TreePMap<K,V>> toTreePMap(java.util.function.Function<? super T,? extends K> keyMapper, java.util.function.Function<? super T,? extends V> valueMapper, java.util.function.BinaryOperator<V> 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.- Type Parameters:
K
- the type of keys to be maintained by the mapV
- the type of mapped values- Parameters:
keyMapper
- a function to compute the key from a stream elementvalueMapper
- a function to compute the value from a stream elementmergeFunction
- a function to merge duplicate values- Returns:
- a collector that gathers the elements of the stream into a TreePMap
- Throws:
java.lang.NullPointerException
- if any of this method's arguments are null
-
toTreePMap
public static <T,K,V> java.util.stream.Collector<T,?,TreePMap<K,V>> toTreePMap(java.util.Comparator<? super K> comparator, java.util.function.Function<? super T,? extends K> keyMapper, java.util.function.Function<? super T,? extends V> valueMapper, java.util.function.BinaryOperator<V> 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.- Type Parameters:
K
- the type of keys to be maintained by the mapV
- the type of mapped values- Parameters:
comparator
- the comparator according to which keys should be orderedkeyMapper
- a function to compute the key from a stream elementvalueMapper
- a function to compute the value from a stream elementmergeFunction
- a function to merge duplicate values- Returns:
- a collector that gathers the elements of the stream into a TreePMap
- Throws:
java.lang.NullPointerException
- if any of this method's arguments are null
-
comparator
public java.util.Comparator<? super K> comparator()
- Specified by:
comparator
in interfacePSortedMap<K,V>
- Specified by:
comparator
in interfacejava.util.SortedMap<K,V>
- Returns:
- The comparator used to order the keys in this map. (Never null.)
-
containsKey
public boolean containsKey(java.lang.Object key)
-
descendingKeySet
public PSortedSet<K> descendingKeySet()
- Specified by:
descendingKeySet
in interfacejava.util.NavigableMap<K,V>
- Specified by:
descendingKeySet
in interfacePSortedMap<K,V>
-
descendingMap
public TreePMap<K,V> descendingMap()
- Specified by:
descendingMap
in interfacejava.util.NavigableMap<K,V>
- Specified by:
descendingMap
in interfacePSortedMap<K,V>
-
get
public V get(java.lang.Object key)
-
isEmpty
public boolean isEmpty()
-
minusFirstEntry
public TreePMap<K,V> minusFirstEntry()
- Specified by:
minusFirstEntry
in interfacePSortedMap<K,V>
- Returns:
- This map, minus its first mapping (the mapping with the least/lowest key).
-
minusLastEntry
public TreePMap<K,V> minusLastEntry()
- Specified by:
minusLastEntry
in interfacePSortedMap<K,V>
- Returns:
- This map, minus its last mapping (the mapping with the greatest/highest key).
-
navigableKeySet
public TreePSet<K> navigableKeySet()
- Specified by:
navigableKeySet
in interfacejava.util.NavigableMap<K,V>
- Specified by:
navigableKeySet
in interfacePSortedMap<K,V>
-
size
public int size()
-
subMap
public TreePMap<K,V> subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)
-
search
private KVTree<K,V> search(K key, KVTree.SearchType searchTypeIfLeftToRight, KVTree.SearchType searchTypeIfRightToLeft)
-
sneakilyDowncast
private static <T> T sneakilyDowncast(java.lang.Object o)
-
-