Class 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:
    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 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 {@link Map.Entry<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
    • 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  
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private KVTree()
      Constructor for the empty tree / leaf node EMPTY.
      private KVTree​(KVTree<K,​V> left, K key, V value, KVTree<K,​V> right)
      Constructor for a non-empty/non-leaf node.
    • 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).
      • Methods inherited from class java.lang.Object

        clone, finalize, getClass, notify, notifyAll, wait, wait, wait
    • Field Detail

      • 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
      • right

        private final KVTree<K,​V> right
    • Constructor Detail

      • 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 #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.
        Specified by:
        equals in interface java.util.Map.Entry<K,​V>
        Overrides:
        equals in class java.lang.Object
      • getKey

        public K getKey()
        Specified by:
        getKey in interface java.util.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:
        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()
        Specified by:
        getValue in interface java.util.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 java.util.Map.Entry<K,​V>
        Overrides:
        hashCode in class java.lang.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,
                                java.util.Comparator<? super K> comparator)
      • 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.
      • plus

        KVTree<K,​V> plus​(K key,
                               V value,
                               java.util.Comparator<? super K> comparator)
      • 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)
      • setValue

        @Deprecated
        public V setValue​(V value)
        Deprecated.
        Unsupported operation.
        Specified by:
        setValue in interface java.util.Map.Entry<K,​V>
        Throws:
        java.lang.UnsupportedOperationException - always
      • 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 class java.lang.Object
      • readResolve

        private java.lang.Object readResolve()
      • checkNotEmpty

        private void checkNotEmpty()
      • 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)