Modifier and Type	Class and Description
private static class	KVTree.EntryIterator<K, V> An iterator over the mappings of a KVTree.
private static enum	KVTree.IteratorType Whether an iterator returns entries or just keys.
pack-priv static enum	KVTree.SearchType

Modifier and Type	Field and Description
private static final KVTree<?, ?>	EMPTY The empty tree / leaf node.
private final int	height The height of this tree: 0 if this tree is empty, otherwise 1 + max(left.height, right.height).
private final K	key
private final KVTree<K, V>	left
private final KVTree<K, V>	right
private static final long	serialVersionUID
private final int	size
private final V	value

Access	Constructor and Description
private	KVTree() Constructor for the empty tree / leaf node `EMPTY`.
private	KVTree(final KVTree<K, V> left, final K key, final V value, final KVTree<K, V> right) Constructor for a non-empty/non-leaf node.

Method Summary

Modifier and Type	Method and Description
private void	checkNotEmpty()
private static <K, V> KVTree<K, V>	concat(final KVTree<K, V> left, final KVTree<K, V> right)
pack-priv static <K, V> KVTree<K, V>	empty()
pack-priv Iterator<Map.Entry<K, V>>	Returns: An iterator over the mappings in this tree in the specified direction. entryIterator(final boolean - True if to iterate from left to right; false for right to left. isLeftToRight) Creates an iterator over the mappings in this tree.
public boolean	equals(final Object object to be compared for equality with this map entry o) Overrides java.lang.Object.equals. Implements java.util.Map.Entry.equals. Implements equals(...) as specified by Map.Entry.
pack-priv static <K, V> KVTree<K, V>	fromEntryIterator(final Iterator<? extends Map.Entry<? extends K, ? extends V>> iterator)
private static <K, V> KVTree<K, V>	fromIterator(final Iterator<?> iterator, final KVTree.IteratorType iteratorType, final int maxHeight)
pack-priv static <K, V> KVTree<K, V>	fromKeyIterator(final Iterator<? extends K> iterator)
public K	Returns: This node's key, or null if this node is the root of the empty tree. getKey() Implements java.util.Map.Entry.getKey. Returns the key corresponding to this entry.
pack-priv KVTree<K, V>	Returns: The leftmost non-empty node in this tree. getLeftmost()
pack-priv KVTree<K, V>	Returns: The rightmost non-empty node in this tree. getRightmost()
public V	Returns: This node's value (which may be null), or null if this node is the root of the empty tree. getValue() Implements java.util.Map.Entry.getValue. Returns the value corresponding to this entry.
public int	hashCode() Overrides java.lang.Object.hashCode. Implements java.util.Map.Entry.hashCode. implements hashCode() as specified by Map.Entry
pack-priv boolean	Returns: Whether this tree contains any mappings (i.e., whether its size is 0). isEmpty()
private static <K, V> KVTree<K, V>	Returns: A tree containing the specified mappings in the specified order. join(final KVTree<K, V> left, final K key, final V value, final 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.
pack-priv KVTree<K, V>	minus(final K key, final Comparator<? super K> comparator)
pack-priv KVTree<K, V>	Returns: A tree with the same mappings as this one, minus the leftmost. minusLeftmost()
pack-priv KVTree<K, V>	Returns: A tree with the same mappings as this one, minus the rightmost. minusRightmost()
pack-priv Map.Entry<K, V>	Returns: This node, or null if this node is the root of the empty tree. orNullIfEmpty()
pack-priv KVTree<K, V>	plus(final K key, final V value, final Comparator<? super K> comparator)
pack-priv KVTree<K, V>	range(final K leftBound, final boolean isLeftBoundInclusive, final K rightBound, final boolean isRightBoundInclusive, final Comparator<? super K> comparator)
pack-priv KVTree<K, V>	rangeToLeft(final K rightBound, final boolean isRightBoundInclusive, final Comparator<? super K> comparator)
pack-priv KVTree<K, V>	rangeToRight(final K leftBound, final boolean isleftBoundInclusive, final Comparator<? super K> comparator)
private Object	readResolve()
private KVTree<K, V>	replaceLeft(final KVTree<K, V> newLeft)
private KVTree<K, V>	replaceRight(final KVTree<K, V> newRight)
private KVTree<K, V>	replaceValue(final V newValue)
pack-priv KVTree<K, V>	search(final K key, final Comparator<? super K> comparator, final KVTree.SearchType searchType)
public V	setValue(final V new value to be stored in this entry value) Implements java.util.Map.Entry.setValue. Deprecated Unsupported operation. Replaces the value corresponding to this entry with the specified value (optional operation).
pack-priv int	Returns: The number of mappings in this tree. size()
public String	toString() Overrides java.lang.Object.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).

Inherited from java.lang.Object:: clone finalize getClass notify notifyAll wait wait wait

Field Detail

EMPTY	back to summary
private static final KVTree<?, ?> EMPTY The empty tree / leaf node. Access via `empty()`.

height	back to summary
private final int height The height of this tree: 0 if this tree is empty, otherwise 1 + max(left.height, right.height).

key	back to summary
private final K key

left	back to summary
private final KVTree<K, V> left

right	back to summary
private final KVTree<K, V> right

serialVersionUID	back to summary
private static final long serialVersionUID

size	back to summary
private final int size

value	back to summary
private final V value

Constructor Detail

KVTree	back to summary
private KVTree() Constructor for the empty tree / leaf node `EMPTY`.

KVTree	back to summary
private KVTree(final KVTree<K, V> left, final K key, final V value, final 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

checkNotEmpty	back to summary
private void checkNotEmpty()

concat	back to summary
private static <K, V> KVTree<K, V> concat(final KVTree<K, V> left, final KVTree<K, V> right)

empty	back to summary
pack-priv static <K, V> KVTree<K, V> empty() Annotations @SuppressWarnings:unchecked

entryIterator	back to summary
pack-priv Iterator<Map.Entry<K, V>> entryIterator(final boolean isLeftToRight) Creates an iterator over the mappings in this tree. Parameters isLeftToRight:boolean - True if to iterate from left to right; false for right to left. Returns:Iterator<Map.Entry<K, V>> An iterator over the mappings in this tree in the specified direction.

entryIterator

back to summary

pack-priv Iterator<Map.Entry<K, V>> entryIterator(final boolean isLeftToRight)

Creates an iterator over the mappings in this tree.

Parameters

isLeftToRight:boolean: - True if to iterate from left to right; false for right to left.

Returns:Iterator<Map.Entry<K, V>>

An iterator over the mappings in this tree in the specified direction.

equals back to summary

equals	back to summary
public boolean equals(final Object o) Overrides java.lang.Object.equals. Implements java.util.Map.Entry.equals. Implements equals(...) as specified by Map.Entry. Parameters o:Object Doc from java.util.Map.Entry.equals. object to be compared for equality with this map entry Returns:boolean Doc from java.util.Map.Entry.equals. `true` if the specified object is equal to this map entry Annotations @Override

public boolean equals(final Object o)

Overrides java.lang.Object.equals.

Implements java.util.Map.Entry.equals.

Implements equals(...) as specified by Map.Entry.

Parameters

o:Object

Doc from java.util.Map.Entry.equals.

object to be compared for equality with this map entry

Returns:boolean

Doc from java.util.Map.Entry.equals.

true if the specified object is equal to this map entry

Annotations

@Override

fromEntryIterator	back to summary
pack-priv static <K, V> KVTree<K, V> fromEntryIterator(final Iterator<? extends Map.Entry<? extends K, ? extends V>> iterator)

fromIterator	back to summary
private static <K, V> KVTree<K, V> fromIterator(final Iterator<?> iterator, final KVTree.IteratorType iteratorType, final int maxHeight)

fromKeyIterator	back to summary
pack-priv static <K, V> KVTree<K, V> fromKeyIterator(final Iterator<? extends K> iterator)

getKey	back to summary
public K getKey() Implements java.util.Map.Entry.getKey. Doc from java.util.Map.Entry.getKey. Returns the key corresponding to this entry. Returns:K This node's key, or null if this node is the root of the empty tree. Annotations @Override

getKey

back to summary

public K getKey()

Implements java.util.Map.Entry.getKey.

Doc from java.util.Map.Entry.getKey.

Returns the key corresponding to this entry.

Returns:K

This node's key, or null if this node is the root of the empty tree.

Annotations

@Override

getLeftmost	back to summary
pack-priv KVTree<K, V> getLeftmost() Returns:KVTree<K, V> The leftmost non-empty node in this tree. Exceptions NoSuchElementException: if this tree is empty.

getRightmost	back to summary
pack-priv KVTree<K, V> getRightmost() Returns:KVTree<K, V> The rightmost non-empty node in this tree. Exceptions NoSuchElementException: if this tree is empty.

getValue back to summary

getValue	back to summary
public V getValue() Implements java.util.Map.Entry.getValue. Doc from java.util.Map.Entry.getValue. Returns the value corresponding to this entry. If the mapping has been removed from the backing map (by the iterator's `remove` operation), the results of this call are undefined. Returns:V This node's value (which may be null), or null if this node is the root of the empty tree. Annotations @Override

public V getValue()

Implements java.util.Map.Entry.getValue.

Doc from java.util.Map.Entry.getValue.

Returns the value corresponding to this entry. If the mapping has been removed from the backing map (by the iterator's remove operation), the results of this call are undefined.

Returns:V

This node's value (which may be null), or null if this node is the root of the empty tree.

Annotations

@Override

hashCode	back to summary
public int hashCode() Overrides java.lang.Object.hashCode. Implements java.util.Map.Entry.hashCode. implements hashCode() as specified by Map.Entry Returns:int Doc from java.util.Map.Entry.hashCode. the hash code value for this map entry Annotations @Override

hashCode

back to summary

public int hashCode()

Overrides java.lang.Object.hashCode.

Implements java.util.Map.Entry.hashCode.

implements hashCode() as specified by Map.Entry

Returns:int

Doc from java.util.Map.Entry.hashCode.

the hash code value for this map entry

Annotations

@Override

isEmpty	back to summary
pack-priv boolean isEmpty() Returns:boolean Whether this tree contains any mappings (i.e., whether its size is 0).

join back to summary

join	back to summary
private static <K, V> KVTree<K, V> join(final KVTree<K, V> left, final K key, final V value, final 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:KVTree<K, V> A tree containing the specified mappings in the specified order.

private static <K, V> KVTree<K, V> join(final KVTree<K, V> left, final K key, final V value, final 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:KVTree<K, V>: A tree containing the specified mappings in the specified order.

minus	back to summary
pack-priv KVTree<K, V> minus(final K key, final Comparator<? super K> comparator)

minusLeftmost	back to summary
pack-priv KVTree<K, V> minusLeftmost() Returns:KVTree<K, V> A tree with the same mappings as this one, minus the leftmost. Exceptions NoSuchElementException: if this tree is empty.

minusRightmost	back to summary
pack-priv KVTree<K, V> minusRightmost() Returns:KVTree<K, V> A tree with the same mappings as this one, minus the rightmost. Exceptions NoSuchElementException: if this tree is empty.

orNullIfEmpty	back to summary
pack-priv Map.Entry<K, V> orNullIfEmpty() Returns:Map.Entry<K, V> This node, or null if this node is the root of the empty tree.

plus	back to summary
pack-priv KVTree<K, V> plus(final K key, final V value, final Comparator<? super K> comparator)

range	back to summary
pack-priv KVTree<K, V> range(final K leftBound, final boolean isLeftBoundInclusive, final K rightBound, final boolean isRightBoundInclusive, final Comparator<? super K> comparator)

rangeToLeft	back to summary
pack-priv KVTree<K, V> rangeToLeft(final K rightBound, final boolean isRightBoundInclusive, final Comparator<? super K> comparator)

rangeToRight	back to summary
pack-priv KVTree<K, V> rangeToRight(final K leftBound, final boolean isleftBoundInclusive, final Comparator<? super K> comparator)

readResolve	back to summary
private Object readResolve()

replaceLeft	back to summary
private KVTree<K, V> replaceLeft(final KVTree<K, V> newLeft)

replaceRight	back to summary
private KVTree<K, V> replaceRight(final KVTree<K, V> newRight)

replaceValue	back to summary
private KVTree<K, V> replaceValue(final V newValue)

search	back to summary
pack-priv KVTree<K, V> search(final K key, final Comparator<? super K> comparator, final KVTree.SearchType searchType)

setValue back to summary

setValue	back to summary
public V setValue(final V value) Implements java.util.Map.Entry.setValue. Doc from java.util.Map.Entry.setValue. Deprecated Unsupported operation. Replaces the value corresponding to this entry with the specified value (optional operation). (Writes through to the map.) The behavior of this call is undefined if the mapping has already been removed from the map (by the iterator's `remove` operation). Parameters value:V new value to be stored in this entry Returns:V old value corresponding to the entry Annotations @Deprecated @Override Exceptions UnsupportedOperationException: always

public V setValue(final V value)

Implements java.util.Map.Entry.setValue.

Doc from java.util.Map.Entry.setValue.

Deprecated

Unsupported operation.

Replaces the value corresponding to this entry with the specified value (optional operation). (Writes through to the map.) The behavior of this call is undefined if the mapping has already been removed from the map (by the iterator's remove operation).

Parameters

value:V: new value to be stored in this entry

Returns:V

old value corresponding to the entry

Annotations

@Deprecated
@Override

Exceptions

UnsupportedOperationException:: always

size	back to summary
pack-priv int size() Returns:int The number of mappings in this tree.

toString	back to summary
public String toString() Overrides java.lang.Object.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). Returns:String Doc from java.lang.Object.toString. a string representation of the object Annotations @Override

toString

back to summary

public String toString()

Overrides java.lang.Object.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).

Returns:String

Doc from java.lang.Object.toString.

a string representation of the object

Annotations

@Override

org.pcollections back to summary

private Class KVTree.EntryIterator<K, V>

Class Inheritance

extends Object
implements Iterator<Map.Entry<K, V>>

java.lang.Object
org.pcollections.KVTree.EntryIterator

All Implemented Interfaces

java.util.Iterator

An iterator over the mappings of a KVTree.

Field Summary

Modifier and Type	Field and Description
private final boolean	isLeftToRight whether we're iterating from left to right (vs. right to left)
private KVTree<K, V>	nextSubtree node that we need to enter
private final ArrayList<KVTree<K, V>>	stack nodes that we've recursed into, but not yet returned

Constructor Summary

Access	Constructor and Description
pack-priv	EntryIterator(final KVTree<K, V> tree, final boolean isLeftToRight)

Method Summary

Modifier and Type	Method and Description
private KVTree<K, V>	firstChild(final KVTree<K, V> node)
public boolean	hasNext() Implements java.util.Iterator.hasNext. Returns `true` if the iteration has more elements.
public Map.Entry<K, V>	next() Implements java.util.Iterator.next. Returns the next element in the iteration.
private KVTree<K, V>	secondChild(final KVTree<K, V> node)

Inherited from java.lang.Object:: clone equals finalize getClass hashCode notify notifyAll toString wait wait wait

Field Detail

isLeftToRight	back to summary
private final boolean isLeftToRight whether we're iterating from left to right (vs. right to left)

nextSubtree	back to summary
private KVTree<K, V> nextSubtree node that we need to enter

stack	back to summary
private final ArrayList<KVTree<K, V>> stack nodes that we've recursed into, but not yet returned

Constructor Detail

EntryIterator	back to summary
pack-priv EntryIterator(final KVTree<K, V> tree, final boolean isLeftToRight)

Method Detail

firstChild	back to summary
private KVTree<K, V> firstChild(final KVTree<K, V> node)

hasNext back to summary

public boolean hasNext()

Implements java.util.Iterator.hasNext.

Doc from java.util.Iterator.hasNext.

Returns true if the iteration has more elements. (In other words, returns true if next would return an element rather than throwing an exception.)

Returns:boolean

true if the iteration has more elements

Annotations

@Override

back to summary

public Map.Entry<K, V> next()

Implements java.util.Iterator.next.

Doc from java.util.Iterator.next.

Returns the next element in the iteration.

Returns:Map.Entry<K, V>

the next element in the iteration

Annotations

@Override

secondChild	back to summary
private KVTree<K, V> secondChild(final KVTree<K, V> node)

Modifier and Type	Method and Description
public static KVTree.IteratorType	valueOf(String name)
public static KVTree.IteratorType[]	values()

Modifier and Type	Field and Description
public static final KVTree.SearchType	EQ
public static final KVTree.SearchType	GE
public static final KVTree.SearchType	GT
public static final KVTree.SearchType	LE
public static final KVTree.SearchType	LT

Modifier and Type	Method and Description
public static KVTree.SearchType	valueOf(String name)
public static KVTree.SearchType[]	values()

pack-priv final Class KVTree<K, V>

Nested and Inner Type Summary

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

private Class KVTree.EntryIterator<K, V>

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

private final Enum KVTree.IteratorType

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

pack-priv final Enum KVTree.SearchType

Field Summary

Constructor Summary

Method Summary

Field Detail

Constructor Detail

Method Detail

Modifier and Type	Field and Description
public static final KVTree.IteratorType	ENTRY
public static final KVTree.IteratorType	KEY