Class TreePMap<K,​V>

  • Type Parameters:
    K - the type of keys maintained by this map
    V - the type of mapped values
    All Implemented Interfaces:
    java.io.Serializable, java.util.Map<K,​V>, java.util.NavigableMap<K,​V>, java.util.SortedMap<K,​V>, PMap<K,​V>, PSortedMap<K,​V>

    public final class TreePMap<K,​V>
    extends AbstractUnmodifiableMap<K,​V>
    implements PSortedMap<K,​V>, java.io.Serializable
    An implementation of PSortedMap based on a self-balancing binary search tree.

    Instances of this class are obtained via any of various static factory methods and static collector methods. These methods come in pairs, with one version that accepts an explicit comparator to use and one version that uses the natural ordering of the elements.

    All operations are guaranteed to complete within O(log n) time, except for plusAll and minusAll, whose time cost is equivalent to the corresponding sequence of calls to plus or minus. A complete iteration pass over entrySet() completes in O(n) time. A few operations -- namely comparator, descendingKeySet, descendingMap, entrySet, isEmpty, keySet, navigableKeySet, and size -- complete in O(1) time.

    Since:
    3.2.0
    See Also:
    Serialized Form
    • Nested Class Summary

      • Nested classes/interfaces inherited from class java.util.AbstractMap

        java.util.AbstractMap.SimpleEntry<K extends java.lang.Object,​V extends java.lang.Object>, java.util.AbstractMap.SimpleImmutableEntry<K extends java.lang.Object,​V extends java.lang.Object>
      • Nested classes/interfaces inherited from interface java.util.Map

        java.util.Map.Entry<K extends java.lang.Object,​V extends java.lang.Object>
    • Constructor Summary

      Constructors 
      Modifier Constructor Description
      private TreePMap​(KVTree<K,​V> tree, java.util.Comparator<? super K> ltrComparator, boolean isLeftToRight)  
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      java.util.Map.Entry<K,​V> ceilingEntry​(K key)  
      K ceilingKey​(K key)  
      java.util.Comparator<? super K> comparator()  
      boolean containsKey​(java.lang.Object key)  
      PSortedSet<K> descendingKeySet()  
      TreePMap<K,​V> descendingMap()  
      static <K extends java.lang.Comparable<? super K>,​V>
      TreePMap<K,​V>
      empty()
      Returns an empty TreePMap using the natural ordering.
      static <K,​V>
      TreePMap<K,​V>
      empty​(java.util.Comparator<? super K> comparator)
      Returns an empty TreePMap using the specified comparator.
      java.util.Set<java.util.Map.Entry<K,​V>> entrySet()  
      java.util.Map.Entry<K,​V> firstEntry()  
      K firstKey()  
      java.util.Map.Entry<K,​V> floorEntry​(K key)  
      K floorKey​(K key)  
      static <K,​V>
      TreePMap<K,​V>
      from​(java.util.Comparator<? super K> comparator, java.util.Map<? extends K,​? extends V> map)
      Returns a TreePMap with the specified comparator and mappings.
      static <K extends java.lang.Comparable<? super K>,​V>
      TreePMap<K,​V>
      from​(java.util.Map<? extends K,​? extends V> map)
      Returns a TreePMap with the specified mappings, using the natural ordering of the keys.
      static <K,​V>
      TreePMap<K,​V>
      fromSortedMap​(java.util.SortedMap<K,​? extends V> map)
      Returns a TreePMap with the same mappings and ordering as the specified map.
      V get​(java.lang.Object key)  
      TreePMap<K,​V> headMap​(K toKey)  
      TreePMap<K,​V> headMap​(K toKey, boolean inclusive)  
      java.util.Map.Entry<K,​V> higherEntry​(K key)  
      K higherKey​(K key)  
      boolean isEmpty()  
      TreePSet<K> keySet()  
      java.util.Map.Entry<K,​V> lastEntry()  
      K lastKey()  
      java.util.Map.Entry<K,​V> lowerEntry​(K key)  
      K lowerKey​(K key)  
      TreePMap<K,​V> minus​(java.lang.Object key)  
      TreePMap<K,​V> minusAll​(java.util.Collection<?> keys)  
      TreePMap<K,​V> minusFirstEntry()  
      TreePMap<K,​V> minusLastEntry()  
      TreePSet<K> navigableKeySet()  
      TreePMap<K,​V> plus​(K key, V value)  
      TreePMap<K,​V> plusAll​(java.util.Map<? extends K,​? extends V> map)  
      private KVTree<K,​V> search​(K key, KVTree.SearchType searchTypeIfLeftToRight, KVTree.SearchType searchTypeIfRightToLeft)  
      static <K,​V>
      TreePMap<K,​V>
      singleton​(java.util.Comparator<? super K> comparator, K key, V value)
      Returns a TreePMap with a single element, using the specified comparator.
      static <K extends java.lang.Comparable<? super K>,​V>
      TreePMap<K,​V>
      singleton​(K key, V value)
      Returns a TreePMap with a single mapping, using the natural ordering of its keys.
      int size()  
      private static <T> T sneakilyDowncast​(java.lang.Object o)  
      TreePMap<K,​V> subMap​(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive)  
      TreePMap<K,​V> subMap​(K fromKey, K toKey)  
      TreePMap<K,​V> tailMap​(K fromKey)  
      TreePMap<K,​V> tailMap​(K fromKey, boolean inclusive)  
      static <T,​K,​V>
      java.util.stream.Collector<T,​?,​TreePMap<K,​V>>
      toTreePMap​(java.util.Comparator<? super K> comparator, java.util.function.Function<? super T,​? extends K> keyMapper, java.util.function.Function<? super T,​? extends V> valueMapper)
      Returns a collector that gathers a stream into a TreePMap with mappings computed from the elements of the stream (using the specified keyMapper and valueMapper), in the order determined by the specified comparator.
      static <T,​K,​V>
      java.util.stream.Collector<T,​?,​TreePMap<K,​V>>
      toTreePMap​(java.util.Comparator<? super K> comparator, java.util.function.Function<? super T,​? extends K> keyMapper, java.util.function.Function<? super T,​? extends V> valueMapper, java.util.function.BinaryOperator<V> mergeFunction)
      Returns a collector that gathers a stream into a TreePMap with mappings computed from the elements of the stream (using the specified keyMapper and valueMapper, with duplicates reconciled via the specified mergeFunction), in the order determined by the specified comparator.
      static <T,​K extends java.lang.Comparable<? super K>,​V>
      java.util.stream.Collector<T,​?,​TreePMap<K,​V>>
      toTreePMap​(java.util.function.Function<? super T,​? extends K> keyMapper, java.util.function.Function<? super T,​? extends V> valueMapper)
      Returns a collector that gathers a stream into a TreePMap with mappings computed from the elements of the stream (using the specified keyMapper and valueMapper), in the order determined by the natural ordering of the keys.
      static <T,​K extends java.lang.Comparable<? super K>,​V>
      java.util.stream.Collector<T,​?,​TreePMap<K,​V>>
      toTreePMap​(java.util.function.Function<? super T,​? extends K> keyMapper, java.util.function.Function<? super T,​? extends V> valueMapper, java.util.function.BinaryOperator<V> mergeFunction)
      Returns a collector that gathers a stream into a TreePMap with mappings computed from the elements of the stream (using the specified keyMapper and valueMapper, with duplicates reconciled via the specified mergeFunction), in the order determined by the natural ordering of the keys.
      private TreePMap<K,​V> withTree​(KVTree<K,​V> updatedTree)  
      • Methods inherited from class java.util.AbstractMap

        clone, containsValue, equals, hashCode, toString, values
      • Methods inherited from class java.lang.Object

        finalize, getClass, notify, notifyAll, wait, wait, wait
      • Methods inherited from interface java.util.Map

        compute, computeIfAbsent, computeIfPresent, containsValue, equals, forEach, getOrDefault, hashCode, merge, putIfAbsent, remove, replace, replace, replaceAll
      • Methods inherited from interface java.util.SortedMap

        values
    • Field Detail

      • tree

        private final KVTree<K,​V> tree
      • ltrComparator

        private final java.util.Comparator<? super K> ltrComparator
      • isLeftToRight

        private final boolean isLeftToRight
    • Constructor Detail

      • TreePMap

        private TreePMap​(KVTree<K,​V> tree,
                         java.util.Comparator<? super K> ltrComparator,
                         boolean isLeftToRight)
    • Method Detail

      • empty

        public static <K extends java.lang.Comparable<? super K>,​V> TreePMap<K,​V> empty()
        Returns an empty TreePMap using the natural ordering.
        Type Parameters:
        K - the type of keys to be maintained by the map
        V - the type of mapped values
        Returns:
        an empty TreePMap using the natural ordering
      • empty

        public static <K,​V> TreePMap<K,​V> empty​(java.util.Comparator<? super K> comparator)
        Returns an empty TreePMap using the specified comparator.
        Type Parameters:
        K - the type of keys to be maintained by the map
        V - the type of mapped values
        Parameters:
        comparator - the comparator according to which keys should be ordered
        Returns:
        an empty TreePMap using the specified comparator
        Throws:
        java.lang.NullPointerException - if comparator is null
      • from

        public static <K extends java.lang.Comparable<? super K>,​V> TreePMap<K,​V> from​(java.util.Map<? extends K,​? extends V> map)
        Returns a TreePMap with the specified mappings, using the natural ordering of the keys.
        Type Parameters:
        K - the type of keys to be maintained by the map
        V - the type of mapped values
        Parameters:
        map - the mappings to include
        Returns:
        a TreePMap containing the specified mappings and using the natural ordering of the keys
        Throws:
        java.lang.NullPointerException - if the map is null or contains a null key
      • from

        public static <K,​V> TreePMap<K,​V> from​(java.util.Comparator<? super K> comparator,
                                                           java.util.Map<? extends K,​? extends V> map)
        Returns a TreePMap with the specified comparator and mappings.
        Type Parameters:
        K - the type of keys to be maintained by the map
        V - the type of mapped values
        Parameters:
        comparator - the comparator to use
        map - the mappings to include
        Returns:
        a TreePMap with the specified comparator and mappings
        Throws:
        java.lang.NullPointerException - if the comparator or map is null or the map contains a null key
      • fromSortedMap

        public static <K,​V> TreePMap<K,​V> fromSortedMap​(java.util.SortedMap<K,​? extends V> map)
        Returns a TreePMap with the same mappings and ordering as the specified map. This is essentially equivalent to TreePMap.from(map.comparator(), map), except that it gracefully handles a null comparator, and is much more efficient.
        Type Parameters:
        K - the type of keys to be maintained by the map
        V - the type of mapped values
        Parameters:
        map - the map whose mappings and ordering to use
        Returns:
        a TreePMap with the same mappings and ordering as the specified set
        Throws:
        java.lang.NullPointerException - if the specified map is null or contains a null key
      • singleton

        public static <K extends java.lang.Comparable<? super K>,​V> TreePMap<K,​V> singleton​(K key,
                                                                                                        V value)
        Returns a TreePMap with a single mapping, using the natural ordering of its keys.
        Type Parameters:
        K - the type of keys to be maintained by the map
        V - the type of mapped values
        Parameters:
        key - the key
        value - the value
        Returns:
        a TreePMap containing the specified mapping and using the natural ordering
        Throws:
        java.lang.NullPointerException - if the specified key or value is null
      • singleton

        public static <K,​V> TreePMap<K,​V> singleton​(java.util.Comparator<? super K> comparator,
                                                                K key,
                                                                V value)
        Returns a TreePMap with a single element, using the specified comparator.
        Type Parameters:
        K - the type of keys to be maintained by the map
        V - the type of mapped values
        Parameters:
        comparator - the comparator according to which keys should be ordered
        key - the key
        value - the value
        Returns:
        a TreePMap containing the specified mapping and using the specified comparator
        Throws:
        java.lang.NullPointerException - if the specified comparator or key is null
      • toTreePMap

        public static <T,​K extends java.lang.Comparable<? super K>,​V> java.util.stream.Collector<T,​?,​TreePMap<K,​V>> toTreePMap​(java.util.function.Function<? super T,​? extends K> keyMapper,
                                                                                                                                                             java.util.function.Function<? super T,​? extends V> valueMapper)
        Returns a collector that gathers a stream into a TreePMap with mappings computed from the elements of the stream (using the specified keyMapper and valueMapper), in the order determined by the natural ordering of the keys. In the event of duplicate keys, the collector will throw IllegalStateException.
        Type Parameters:
        K - the type of keys to be maintained by the map
        V - the type of mapped values
        Parameters:
        keyMapper - a function to compute the key from a stream element
        valueMapper - a function to compute the value from a stream element
        Returns:
        a collector that gathers the elements of the stream into a TreePMap
        Throws:
        java.lang.NullPointerException - if either keyMapper or valueMapper is null
      • toTreePMap

        public static <T,​K,​V> java.util.stream.Collector<T,​?,​TreePMap<K,​V>> toTreePMap​(java.util.Comparator<? super K> comparator,
                                                                                                                     java.util.function.Function<? super T,​? extends K> keyMapper,
                                                                                                                     java.util.function.Function<? super T,​? extends V> valueMapper)
        Returns a collector that gathers a stream into a TreePMap with mappings computed from the elements of the stream (using the specified keyMapper and valueMapper), in the order determined by the specified comparator. In the event of duplicate keys, the collector will throw IllegalStateException.
        Type Parameters:
        K - the type of keys to be maintained by the map
        V - the type of mapped values
        Parameters:
        comparator - the comparator according to which keys should be ordered
        keyMapper - a function to compute the key from a stream element
        valueMapper - a function to compute the value from a stream element
        Returns:
        a collector that gathers the elements of the stream into a TreePMap
        Throws:
        java.lang.NullPointerException - if any of this method's arguments are null
      • toTreePMap

        public static <T,​K extends java.lang.Comparable<? super K>,​V> java.util.stream.Collector<T,​?,​TreePMap<K,​V>> toTreePMap​(java.util.function.Function<? super T,​? extends K> keyMapper,
                                                                                                                                                             java.util.function.Function<? super T,​? extends V> valueMapper,
                                                                                                                                                             java.util.function.BinaryOperator<V> mergeFunction)
        Returns a collector that gathers a stream into a TreePMap with mappings computed from the elements of the stream (using the specified keyMapper and valueMapper, with duplicates reconciled via the specified mergeFunction), in the order determined by the natural ordering of the keys.
        Type Parameters:
        K - the type of keys to be maintained by the map
        V - the type of mapped values
        Parameters:
        keyMapper - a function to compute the key from a stream element
        valueMapper - a function to compute the value from a stream element
        mergeFunction - a function to merge duplicate values
        Returns:
        a collector that gathers the elements of the stream into a TreePMap
        Throws:
        java.lang.NullPointerException - if any of this method's arguments are null
      • toTreePMap

        public static <T,​K,​V> java.util.stream.Collector<T,​?,​TreePMap<K,​V>> toTreePMap​(java.util.Comparator<? super K> comparator,
                                                                                                                     java.util.function.Function<? super T,​? extends K> keyMapper,
                                                                                                                     java.util.function.Function<? super T,​? extends V> valueMapper,
                                                                                                                     java.util.function.BinaryOperator<V> mergeFunction)
        Returns a collector that gathers a stream into a TreePMap with mappings computed from the elements of the stream (using the specified keyMapper and valueMapper, with duplicates reconciled via the specified mergeFunction), in the order determined by the specified comparator.
        Type Parameters:
        K - the type of keys to be maintained by the map
        V - the type of mapped values
        Parameters:
        comparator - the comparator according to which keys should be ordered
        keyMapper - a function to compute the key from a stream element
        valueMapper - a function to compute the value from a stream element
        mergeFunction - a function to merge duplicate values
        Returns:
        a collector that gathers the elements of the stream into a TreePMap
        Throws:
        java.lang.NullPointerException - if any of this method's arguments are null
      • ceilingEntry

        public java.util.Map.Entry<K,​V> ceilingEntry​(K key)
        Specified by:
        ceilingEntry in interface java.util.NavigableMap<K,​V>
      • ceilingKey

        public K ceilingKey​(K key)
        Specified by:
        ceilingKey in interface java.util.NavigableMap<K,​V>
      • comparator

        public java.util.Comparator<? super K> comparator()
        Specified by:
        comparator in interface PSortedMap<K,​V>
        Specified by:
        comparator in interface java.util.SortedMap<K,​V>
        Returns:
        The comparator used to order the keys in this map. (Never null.)
      • containsKey

        public boolean containsKey​(java.lang.Object key)
        Specified by:
        containsKey in interface java.util.Map<K,​V>
        Overrides:
        containsKey in class java.util.AbstractMap<K,​V>
      • descendingMap

        public TreePMap<K,​V> descendingMap()
        Specified by:
        descendingMap in interface java.util.NavigableMap<K,​V>
        Specified by:
        descendingMap in interface PSortedMap<K,​V>
      • entrySet

        public java.util.Set<java.util.Map.Entry<K,​V>> entrySet()
        Specified by:
        entrySet in interface java.util.Map<K,​V>
        Specified by:
        entrySet in interface java.util.SortedMap<K,​V>
        Specified by:
        entrySet in class java.util.AbstractMap<K,​V>
      • firstEntry

        public java.util.Map.Entry<K,​V> firstEntry()
        Specified by:
        firstEntry in interface java.util.NavigableMap<K,​V>
      • firstKey

        public K firstKey()
        Specified by:
        firstKey in interface java.util.SortedMap<K,​V>
      • floorEntry

        public java.util.Map.Entry<K,​V> floorEntry​(K key)
        Specified by:
        floorEntry in interface java.util.NavigableMap<K,​V>
      • floorKey

        public K floorKey​(K key)
        Specified by:
        floorKey in interface java.util.NavigableMap<K,​V>
      • get

        public V get​(java.lang.Object key)
        Specified by:
        get in interface java.util.Map<K,​V>
        Overrides:
        get in class java.util.AbstractMap<K,​V>
      • headMap

        public TreePMap<K,​V> headMap​(K toKey)
        Specified by:
        headMap in interface java.util.NavigableMap<K,​V>
        Specified by:
        headMap in interface PSortedMap<K,​V>
        Specified by:
        headMap in interface java.util.SortedMap<K,​V>
      • headMap

        public TreePMap<K,​V> headMap​(K toKey,
                                           boolean inclusive)
        Specified by:
        headMap in interface java.util.NavigableMap<K,​V>
        Specified by:
        headMap in interface PSortedMap<K,​V>
      • higherEntry

        public java.util.Map.Entry<K,​V> higherEntry​(K key)
        Specified by:
        higherEntry in interface java.util.NavigableMap<K,​V>
      • higherKey

        public K higherKey​(K key)
        Specified by:
        higherKey in interface java.util.NavigableMap<K,​V>
      • isEmpty

        public boolean isEmpty()
        Specified by:
        isEmpty in interface java.util.Map<K,​V>
        Overrides:
        isEmpty in class java.util.AbstractMap<K,​V>
      • keySet

        public TreePSet<K> keySet()
        Specified by:
        keySet in interface java.util.Map<K,​V>
        Specified by:
        keySet in interface PSortedMap<K,​V>
        Specified by:
        keySet in interface java.util.SortedMap<K,​V>
        Overrides:
        keySet in class java.util.AbstractMap<K,​V>
      • lastEntry

        public java.util.Map.Entry<K,​V> lastEntry()
        Specified by:
        lastEntry in interface java.util.NavigableMap<K,​V>
      • lastKey

        public K lastKey()
        Specified by:
        lastKey in interface java.util.SortedMap<K,​V>
      • lowerEntry

        public java.util.Map.Entry<K,​V> lowerEntry​(K key)
        Specified by:
        lowerEntry in interface java.util.NavigableMap<K,​V>
      • lowerKey

        public K lowerKey​(K key)
        Specified by:
        lowerKey in interface java.util.NavigableMap<K,​V>
      • minus

        public TreePMap<K,​V> minus​(java.lang.Object key)
        Specified by:
        minus in interface PMap<K,​V>
        Specified by:
        minus in interface PSortedMap<K,​V>
        Returns:
        a map with the mappings of this but with no value for key
      • minusAll

        public TreePMap<K,​V> minusAll​(java.util.Collection<?> keys)
        Specified by:
        minusAll in interface PMap<K,​V>
        Specified by:
        minusAll in interface PSortedMap<K,​V>
        Returns:
        a map with the mappings of this but with no value for any element of keys
      • minusFirstEntry

        public TreePMap<K,​V> minusFirstEntry()
        Specified by:
        minusFirstEntry in interface PSortedMap<K,​V>
        Returns:
        This map, minus its first mapping (the mapping with the least/lowest key).
      • minusLastEntry

        public TreePMap<K,​V> minusLastEntry()
        Specified by:
        minusLastEntry in interface PSortedMap<K,​V>
        Returns:
        This map, minus its last mapping (the mapping with the greatest/highest key).
      • navigableKeySet

        public TreePSet<K> navigableKeySet()
        Specified by:
        navigableKeySet in interface java.util.NavigableMap<K,​V>
        Specified by:
        navigableKeySet in interface PSortedMap<K,​V>
      • plus

        public TreePMap<K,​V> plus​(K key,
                                        V value)
        Specified by:
        plus in interface PMap<K,​V>
        Specified by:
        plus in interface PSortedMap<K,​V>
        Returns:
        a map with the mappings of this but with key mapped to value
      • plusAll

        public TreePMap<K,​V> plusAll​(java.util.Map<? extends K,​? extends V> map)
        Specified by:
        plusAll in interface PMap<K,​V>
        Specified by:
        plusAll in interface PSortedMap<K,​V>
        Returns:
        this combined with map, with map's mappings used for any keys in both map and this
      • size

        public int size()
        Specified by:
        size in interface java.util.Map<K,​V>
        Overrides:
        size in class java.util.AbstractMap<K,​V>
      • subMap

        public TreePMap<K,​V> subMap​(K fromKey,
                                          K toKey)
        Specified by:
        subMap in interface java.util.NavigableMap<K,​V>
        Specified by:
        subMap in interface PSortedMap<K,​V>
        Specified by:
        subMap in interface java.util.SortedMap<K,​V>
      • subMap

        public TreePMap<K,​V> subMap​(K fromKey,
                                          boolean fromInclusive,
                                          K toKey,
                                          boolean toInclusive)
        Specified by:
        subMap in interface java.util.NavigableMap<K,​V>
        Specified by:
        subMap in interface PSortedMap<K,​V>
      • tailMap

        public TreePMap<K,​V> tailMap​(K fromKey)
        Specified by:
        tailMap in interface java.util.NavigableMap<K,​V>
        Specified by:
        tailMap in interface PSortedMap<K,​V>
        Specified by:
        tailMap in interface java.util.SortedMap<K,​V>
      • tailMap

        public TreePMap<K,​V> tailMap​(K fromKey,
                                           boolean inclusive)
        Specified by:
        tailMap in interface java.util.NavigableMap<K,​V>
        Specified by:
        tailMap in interface PSortedMap<K,​V>
      • sneakilyDowncast

        private static <T> T sneakilyDowncast​(java.lang.Object o)