Class KVTree<K,V>

java.lang.Object
org.pcollections.KVTree<K,V>
Type Parameters:
K - the key type; serves as the key type for TreePMap, and as the element type for TreePSet. This class provides various methods that maintain the ordering and distinctness of keys based on a client-provided instance of Comparator<? super K>.
V - the value type; serves as the value type for TreePMap. (Is ignored by TreePSet.)
All Implemented Interfaces:
Serializable, Map.Entry<K,V>
final class KVTree<K,V> extends Object implements Map.Entry<K,V>, Serializable
A persistent (immutable, purely functional) balanced-binary-tree implementation, with such functionality as is needed to support implementations of 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&lt;K,
V>} and providing methods 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

  • Field Details

    • serialVersionUID

      private static final long serialVersionUID
      See Also:

    • EMPTY

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

    • 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

    • left

      private final KVTree<K,V> left

    • key

      private final K key

    • value

      private final V value

  • Constructor Details

    • KVTree

      private KVTree()
      Constructor for the empty tree / leaf node EMPTY.

    • 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
      invalid reference 
      #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 Details

    • 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
      invalid reference 
      #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(Iterator<? extends Map.Entry<? extends K, ? extends V>> iterator)

    • fromKeyIterator

      static <K,V> KVTree<K,V> fromKeyIterator(Iterator<? extends K> iterator)

    • fromIterator

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

    • entryIterator

      Iterator<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(Object o)
      Implements equals(...) as specified by Map.Entry.
      Specified by:
      equals in interface Map.Entry<K,V>
      Overrides:
      equals in class Object

    • getKey

      public K getKey()
      Specified by:
      getKey in interface Map.Entry<K,V>
      Returns:
      This node's key, or null if this node is the root of the empty tree.

    • getLeftmost

      KVTree<K,V> getLeftmost()
      Returns:
      The leftmost non-empty node in this tree.
      Throws:
      NoSuchElementException - if this tree is empty.

    • getRightmost

      KVTree<K,V> getRightmost()
      Returns:
      The rightmost non-empty node in this tree.
      Throws:
      NoSuchElementException - if this tree is empty.

    • getValue

      public V getValue()
      Specified by:
      getValue in interface Map.Entry<K,V>
      Returns:
      This node's value (which may be null), or null if this node is the root of the empty tree.

    • hashCode

      public int hashCode()
      implements hashCode() as specified by Map.Entry
      Specified by:
      hashCode in interface Map.Entry<K,V>
      Overrides:
      hashCode in class Object

    • isEmpty

      boolean isEmpty()
      Returns:
      Whether this tree contains any mappings (i.e., whether its size is 0).

    • minus

      KVTree<K,V> minus(K key, Comparator<? super K> comparator)

    • minusLeftmost

      KVTree<K,V> minusLeftmost()
      Returns:
      A tree with the same mappings as this one, minus the leftmost.
      Throws:
      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:
      NoSuchElementException - if this tree is empty.

    • orNullIfEmpty

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

    • plus

      KVTree<K,V> plus(K key, V value, Comparator<? super K> comparator)

    • range

      KVTree<K,V> range(K leftBound, boolean isLeftBoundInclusive, K rightBound, boolean isRightBoundInclusive, Comparator<? super K> comparator)

    • rangeToLeft

      KVTree<K,V> rangeToLeft(K rightBound, boolean isRightBoundInclusive, Comparator<? super K> comparator)

    • rangeToRight

      KVTree<K,V> rangeToRight(K leftBound, boolean isleftBoundInclusive, Comparator<? super K> comparator)

    • search

      KVTree<K,V> search(K key, Comparator<? super K> comparator, KVTree.SearchType searchType)

    • setValue

      @Deprecated public V setValue(V value)
      Deprecated.
      Unsupported operation.
      Specified by:
      setValue in interface Map.Entry<K,V>
      Throws:
      UnsupportedOperationException - always

    • size

      int size()
      Returns:
      The number of mappings in this tree.

    • toString

      public 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 class Object

    • readResolve

      private Object readResolve()

    • checkNotEmpty

      private void checkNotEmpty()

    • replaceLeft

      private KVTree<K,V> replaceLeft(KVTree<K,V> newLeft)

    • replaceRight

      private KVTree<K,V> replaceRight(KVTree<K,V> newRight)

    • replaceValue

      private KVTree<K,V> replaceValue(V newValue)

    • concat

      private static <K,V> KVTree<K,V> concat(KVTree<K,V> left, KVTree<K,V> right)