java.lang.Object
org.pcollections.KVTree<K,V>
- Type Parameters:
K
- the key type; serves as the key type forTreePMap
, and as the element type forTreePSet
. This class provides various methods that maintain the ordering and distinctness of keys based on a client-provided instance ofComparator<? super K>
.V
- the value type; serves as the value type forTreePMap
. (Is ignored byTreePSet
.)
- All Implemented Interfaces:
Serializable
,Map.Entry<K,
V>
A persistent (immutable, purely functional) balanced-binary-tree implementation, with such
functionality as is needed to support implementations of
V>} and providing methods
PSortedMap
and PSortedSet
, namely TreePMap
and TreePSet
. Each instance of this class is both a
(sub)tree (with a host of methods for examining and manipulating that tree) and the node at the
root of that (sub)tree (implementing
invalid @link
{@link Map.Entry<K,
getKey()
and getValue()
to retrieve the mapping at the node). Method Javadoc refers to
'this node' or 'this tree' as appropriate.
All operations are guaranteed to complete within O(log n) time. A complete iteration pass over entryIterator(boolean) completes in O(n) time. A few operations -- namely getKey, getValue, isEmpty, orNullIfEmpty, and size -- complete in O(1) time.
- Since:
- 3.2.0
-
Nested Class Summary
Nested ClassesModifier and TypeClassDescriptionprivate static class
An iterator over the mappings of a KVTree.private static enum
Whether an iterator returns entries or just keys.(package private) static enum
-
Field Summary
Fields -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprivate void
private static <K,
V> KVTree <K, V> (package private) static <K,
V> KVTree <K, V> empty()
entryIterator
(boolean isLeftToRight) Creates an iterator over the mappings in this tree.boolean
Implements equals(...) as specified by Map.Entry.(package private) static <K,
V> KVTree <K, V> fromEntryIterator
(Iterator<? extends Map.Entry<? extends K, ? extends V>> iterator) private static <K,
V> KVTree <K, V> fromIterator
(Iterator<?> iterator, KVTree.IteratorType iteratorType, int maxHeight) (package private) static <K,
V> KVTree <K, V> fromKeyIterator
(Iterator<? extends K> iterator) getKey()
getValue()
int
hashCode()
implements hashCode() as specified by Map.Entry(package private) boolean
isEmpty()
private static <K,
V> KVTree <K, V> Creates a tree consisting of all the mappings of 'left', in order, followed by a mapping from 'key' to 'value', followed by all the mappings of 'right', in order.minus
(K key, Comparator<? super K> comparator) plus
(K key, V value, Comparator<? super K> comparator) range
(K leftBound, boolean isLeftBoundInclusive, K rightBound, boolean isRightBoundInclusive, Comparator<? super K> comparator) rangeToLeft
(K rightBound, boolean isRightBoundInclusive, Comparator<? super K> comparator) rangeToRight
(K leftBound, boolean isleftBoundInclusive, Comparator<? super K> comparator) private Object
replaceLeft
(KVTree<K, V> newLeft) replaceRight
(KVTree<K, V> newRight) replaceValue
(V newValue) search
(K key, Comparator<? super K> comparator, KVTree.SearchType searchType) Deprecated.Unsupported operation.(package private) int
size()
toString()
implements toString() in a form expected for an implementation of Map.Entry, namely "KEY=VALUE" (with no information about the presence or absence of child nodes).
-
Field Details
-
serialVersionUID
private static final long serialVersionUID- See Also:
-
EMPTY
The empty tree / leaf node. Access viaempty()
. -
height
private final int heightThe height of this tree: 0 if this tree is empty, otherwise 1 + max(left.height, right.height). -
size
private final int size -
left
-
key
-
value
-
right
-
-
Constructor Details
-
KVTree
private KVTree()Constructor for the empty tree / leaf nodeEMPTY
. -
KVTree
Constructor for a non-empty/non-leaf node. Only intended to be called viainvalid reference
#join()
-
-
Method Details
-
join
Creates a tree consisting of all the mappings of 'left', in order, followed by a mapping from 'key' to 'value', followed by all the mappings of 'right', in order. Handles any necessary rebalancing if 'left' and 'right' have mismatched heights. (The intention is that this method be the only code that callsinvalid reference
#KVTree(KVTree, K, V, KVTree)
Requires time proportional to the difference in heights between 'left' and 'right', which is in O(log(max(left.size, right.size))) = O(log(left.size + right.size)).
The height of the returned tree is guaranteed to be max(left.height, right.height) plus either zero or one. (This is important in ensuring the time guarantees of this method and of methods that call it.)
- Returns:
- A tree containing the specified mappings in the specified order.
-
empty
-
fromEntryIterator
-
fromKeyIterator
-
fromIterator
private static <K,V> KVTree<K,V> fromIterator(Iterator<?> iterator, KVTree.IteratorType iteratorType, int maxHeight) -
entryIterator
Creates an iterator over the mappings in this tree.- Parameters:
isLeftToRight
- - True if to iterate from left to right; false for right to left.- Returns:
- An iterator over the mappings in this tree in the specified direction.
-
equals
Implements equals(...) as specified by Map.Entry. -
getKey
-
getLeftmost
- Returns:
- The leftmost non-empty node in this tree.
- Throws:
NoSuchElementException
- if this tree is empty.
-
getRightmost
- Returns:
- The rightmost non-empty node in this tree.
- Throws:
NoSuchElementException
- if this tree is empty.
-
getValue
-
hashCode
public int hashCode()implements hashCode() as specified by Map.Entry -
isEmpty
boolean isEmpty()- Returns:
- Whether this tree contains any mappings (i.e., whether its size is 0).
-
minus
-
minusLeftmost
- Returns:
- A tree with the same mappings as this one, minus the leftmost.
- Throws:
NoSuchElementException
- if this tree is empty.
-
minusRightmost
- Returns:
- A tree with the same mappings as this one, minus the rightmost.
- Throws:
NoSuchElementException
- if this tree is empty.
-
orNullIfEmpty
- Returns:
- This node, or null if this node is the root of the empty tree.
-
plus
-
range
-
rangeToLeft
-
rangeToRight
-
search
-
setValue
Deprecated.Unsupported operation.- Specified by:
setValue
in interfaceMap.Entry<K,
V> - Throws:
UnsupportedOperationException
- always
-
size
int size()- Returns:
- The number of mappings in this tree.
-
toString
implements toString() in a form expected for an implementation of Map.Entry, namely "KEY=VALUE" (with no information about the presence or absence of child nodes). -
readResolve
-
checkNotEmpty
private void checkNotEmpty() -
replaceLeft
-
replaceRight
-
replaceValue
-
concat
-