- 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:
java.io.Serializable
,java.util.Map.Entry<K,V>
final class KVTree<K,V> extends java.lang.Object implements java.util.Map.Entry<K,V>, java.io.Serializable
A persistent (immutable, purely functional) balanced-binary-tree implementation, with such functionality as is needed to support implementations ofPSortedMap
andPSortedSet
, namelyTreePMap
andTreePSet
. 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 {@link Map.Entry<K, V>} and providing methodsgetKey()
andgetValue()
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 Classes Modifier and Type Class Description private static class
KVTree.EntryIterator<K,V>
An iterator over the mappings of a KVTree.private static class
KVTree.IteratorType
Whether an iterator returns entries or just keys.(package private) static class
KVTree.SearchType
-
Field Summary
Fields Modifier and Type Field Description private static KVTree<?,?>
EMPTY
The empty tree / leaf node.private int
height
The height of this tree: 0 if this tree is empty, otherwise 1 + max(left.height, right.height).private K
key
private KVTree<K,V>
left
private KVTree<K,V>
right
private static long
serialVersionUID
private int
size
private V
value
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Deprecated Methods Modifier and Type Method Description private void
checkNotEmpty()
private static <K,V>
KVTree<K,V>concat(KVTree<K,V> left, KVTree<K,V> right)
(package private) static <K,V>
KVTree<K,V>empty()
(package private) java.util.Iterator<java.util.Map.Entry<K,V>>
entryIterator(boolean isLeftToRight)
Creates an iterator over the mappings in this tree.boolean
equals(java.lang.Object o)
Implements equals(...) as specified by Map.Entry.(package private) static <K,V>
KVTree<K,V>fromEntryIterator(java.util.Iterator<? extends java.util.Map.Entry<? extends K,? extends V>> iterator)
private static <K,V>
KVTree<K,V>fromIterator(java.util.Iterator<?> iterator, KVTree.IteratorType iteratorType, int maxHeight)
(package private) static <K,V>
KVTree<K,V>fromKeyIterator(java.util.Iterator<? extends K> iterator)
K
getKey()
(package private) KVTree<K,V>
getLeftmost()
(package private) KVTree<K,V>
getRightmost()
V
getValue()
int
hashCode()
implements hashCode() as specified by Map.Entry(package private) boolean
isEmpty()
private static <K,V>
KVTree<K,V>join(KVTree<K,V> left, K key, V value, KVTree<K,V> right)
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.(package private) KVTree<K,V>
minus(K key, java.util.Comparator<? super K> comparator)
(package private) KVTree<K,V>
minusLeftmost()
(package private) KVTree<K,V>
minusRightmost()
(package private) java.util.Map.Entry<K,V>
orNullIfEmpty()
(package private) KVTree<K,V>
plus(K key, V value, java.util.Comparator<? super K> comparator)
(package private) KVTree<K,V>
range(K leftBound, boolean isLeftBoundInclusive, K rightBound, boolean isRightBoundInclusive, java.util.Comparator<? super K> comparator)
(package private) KVTree<K,V>
rangeToLeft(K rightBound, boolean isRightBoundInclusive, java.util.Comparator<? super K> comparator)
(package private) KVTree<K,V>
rangeToRight(K leftBound, boolean isleftBoundInclusive, java.util.Comparator<? super K> comparator)
private java.lang.Object
readResolve()
private KVTree<K,V>
replaceLeft(KVTree<K,V> newLeft)
private KVTree<K,V>
replaceRight(KVTree<K,V> newRight)
private KVTree<K,V>
replaceValue(V newValue)
(package private) KVTree<K,V>
search(K key, java.util.Comparator<? super K> comparator, KVTree.SearchType searchType)
V
setValue(V value)
Deprecated.Unsupported operation.(package private) int
size()
java.lang.String
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 Detail
-
serialVersionUID
private static final long serialVersionUID
- See Also:
- Constant Field Values
-
height
private final int height
The height of this tree: 0 if this tree is empty, otherwise 1 + max(left.height, right.height).
-
size
private final int size
-
key
private final K key
-
value
private final V value
-
-
Constructor Detail
-
KVTree
private KVTree()
Constructor for the empty tree / leaf nodeEMPTY
.
-
KVTree
private KVTree(KVTree<K,V> left, K key, V value, KVTree<K,V> right)
Constructor for a non-empty/non-leaf node. Only intended to be called via#join()
, which takes the same parameters but also handles rebalancing if needed. (This constructor just throws an exception if 'left' and 'right' have mismatched heights.)
-
-
Method Detail
-
join
private static <K,V> KVTree<K,V> join(KVTree<K,V> left, K key, V value, KVTree<K,V> right)
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 calls#KVTree(KVTree, K, V, KVTree)
directly; all other methods should delegate to this one.)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
static <K,V> KVTree<K,V> empty()
-
fromEntryIterator
static <K,V> KVTree<K,V> fromEntryIterator(java.util.Iterator<? extends java.util.Map.Entry<? extends K,? extends V>> iterator)
-
fromKeyIterator
static <K,V> KVTree<K,V> fromKeyIterator(java.util.Iterator<? extends K> iterator)
-
fromIterator
private static <K,V> KVTree<K,V> fromIterator(java.util.Iterator<?> iterator, KVTree.IteratorType iteratorType, int maxHeight)
-
entryIterator
java.util.Iterator<java.util.Map.Entry<K,V>> entryIterator(boolean isLeftToRight)
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
public boolean equals(java.lang.Object o)
Implements equals(...) as specified by Map.Entry.
-
getKey
public K getKey()
-
getLeftmost
KVTree<K,V> getLeftmost()
- Returns:
- The leftmost non-empty node in this tree.
- Throws:
java.util.NoSuchElementException
- if this tree is empty.
-
getRightmost
KVTree<K,V> getRightmost()
- Returns:
- The rightmost non-empty node in this tree.
- Throws:
java.util.NoSuchElementException
- if this tree is empty.
-
getValue
public V 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).
-
minusLeftmost
KVTree<K,V> minusLeftmost()
- Returns:
- A tree with the same mappings as this one, minus the leftmost.
- Throws:
java.util.NoSuchElementException
- if this tree is empty.
-
minusRightmost
KVTree<K,V> minusRightmost()
- Returns:
- A tree with the same mappings as this one, minus the rightmost.
- Throws:
java.util.NoSuchElementException
- if this tree is empty.
-
orNullIfEmpty
java.util.Map.Entry<K,V> orNullIfEmpty()
- Returns:
- This node, or null if this node is the root of the empty tree.
-
range
KVTree<K,V> range(K leftBound, boolean isLeftBoundInclusive, K rightBound, boolean isRightBoundInclusive, java.util.Comparator<? super K> comparator)
-
rangeToLeft
KVTree<K,V> rangeToLeft(K rightBound, boolean isRightBoundInclusive, java.util.Comparator<? super K> comparator)
-
rangeToRight
KVTree<K,V> rangeToRight(K leftBound, boolean isleftBoundInclusive, java.util.Comparator<? super K> comparator)
-
search
KVTree<K,V> search(K key, java.util.Comparator<? super K> comparator, KVTree.SearchType searchType)
-
size
int size()
- Returns:
- The number of mappings in this tree.
-
toString
public java.lang.String 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).- Overrides:
toString
in classjava.lang.Object
-
readResolve
private java.lang.Object readResolve()
-
checkNotEmpty
private void checkNotEmpty()
-
-