Class TreePSet<E>

  • Type Parameters:
    E - the type of elements maintained by this set
    All Implemented Interfaces:
    java.io.Serializable, java.lang.Iterable<E>, java.util.Collection<E>, java.util.NavigableSet<E>, java.util.Set<E>, java.util.SortedSet<E>, PCollection<E>, PSet<E>, PSortedSet<E>

    public final class TreePSet<E>
    extends AbstractUnmodifiableSet<E>
    implements PSortedSet<E>, java.io.Serializable
    An implementation of PSortedSet based on a self-balancing binary search tree.

    Null values are not allowed.

    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 completes in O(n) time. A few operations -- namely comparator, descendingSet, isEmpty, and size -- complete in O(1) time.

    Since:
    3.2.0
    See Also:
    Serialized Form
    • Constructor Summary

      Constructors 
      Constructor Description
      TreePSet​(KVTree<E,​?> tree, java.util.Comparator<? super E> ltrComparator, boolean isLeftToRight)
      Non-private only because also used by TreePMap.keySet().
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      E ceiling​(E e)  
      java.util.Comparator<? super E> comparator()  
      boolean contains​(java.lang.Object e)  
      java.util.Iterator<E> descendingIterator()  
      TreePSet<E> descendingSet()  
      static <E extends java.lang.Comparable<? super E>>
      TreePSet<E>
      empty()
      Returns an empty TreePSet using the natural ordering.
      static <E> TreePSet<E> empty​(java.util.Comparator<? super E> comparator)
      Returns an empty TreePSet using the specified comparator.
      E first()  
      E floor​(E e)  
      static <E extends java.lang.Comparable<? super E>>
      TreePSet<E>
      from​(java.util.Collection<? extends E> list)
      Returns a TreePSet with the specified elements, using their natural ordering.
      static <E> TreePSet<E> from​(java.util.Comparator<? super E> comparator, java.util.Collection<? extends E> list)
      Returns a TreePSet with the specified comparator and elements.
      static <E> TreePSet<E> fromSortedSet​(java.util.SortedSet<E> set)
      Returns a TreePSet with the same elements and ordering as the specified set.
      TreePSet<E> headSet​(E toElement)  
      TreePSet<E> headSet​(E toElement, boolean inclusive)  
      E higher​(E e)  
      TreePSet<E> intersect​(java.util.Collection<? extends E> list)  
      java.util.Iterator<E> iterator()  
      E last()  
      E lower​(E e)  
      TreePSet<E> minus​(java.lang.Object e)  
      TreePSet<E> minusAll​(java.util.Collection<?> list)  
      TreePSet<E> minusFirst()  
      TreePSet<E> minusLast()  
      static <E extends java.lang.Comparable<? super E>>
      TreePSet<E>
      of​(E... elements)
      Returns a TreePSet with the specified elements, using their natural ordering.
      static <E> TreePSet<E> of​(java.util.Comparator<? super E> comparator, E... elements)
      Returns a TreePSet with the specified comparator and elements.
      TreePSet<E> plus​(E e)  
      TreePSet<E> plusAll​(java.util.Collection<? extends E> list)  
      private E search​(E e, KVTree.SearchType searchTypeIfLeftToRight, KVTree.SearchType searchTypeIfRightToLeft)  
      static <E extends java.lang.Comparable<? super E>>
      TreePSet<E>
      singleton​(E e)
      Returns a TreePSet with a single element, using the natural ordering.
      static <E> TreePSet<E> singleton​(java.util.Comparator<? super E> comparator, E e)
      Returns a TreePSet with a single element, using the specified comparator.
      int size()  
      private static <T> T sneakilyDowncast​(java.lang.Object o)  
      TreePSet<E> subSet​(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)  
      TreePSet<E> subSet​(E fromElement, E toElement)  
      TreePSet<E> tailSet​(E fromElement)  
      TreePSet<E> tailSet​(E fromElement, boolean inclusive)  
      static <E extends java.lang.Comparable<? super E>>
      java.util.stream.Collector<E,​?,​TreePSet<E>>
      toTreePSet()
      Returns a collector that gathers a stream into a TreePSet with the elements of that stream, using their natural ordering.
      static <E> java.util.stream.Collector<E,​?,​TreePSet<E>> toTreePSet​(java.util.Comparator<? super E> comparator)
      Returns a collector that gathers a stream into a TreePSet with the elements of that stream, using the specified comparator.
      private TreePSet<E> withTree​(KVTree<E,​?> tree)  
      • Methods inherited from class java.util.AbstractSet

        equals, hashCode
      • Methods inherited from class java.util.AbstractCollection

        containsAll, isEmpty, toArray, toArray, toString
      • Methods inherited from class java.lang.Object

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

        parallelStream, removeIf, stream, toArray
      • Methods inherited from interface java.lang.Iterable

        forEach
      • Methods inherited from interface java.util.Set

        add, addAll, clear, containsAll, equals, hashCode, isEmpty, remove, removeAll, retainAll, toArray, toArray
      • Methods inherited from interface java.util.SortedSet

        spliterator
    • Field Detail

      • tree

        private final KVTree<E,​?> tree
      • ltrComparator

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

        private final boolean isLeftToRight
    • Constructor Detail

      • TreePSet

        TreePSet​(KVTree<E,​?> tree,
                 java.util.Comparator<? super E> ltrComparator,
                 boolean isLeftToRight)
        Non-private only because also used by TreePMap.keySet(). No other code should use it from outside this class.
    • Method Detail

      • empty

        public static <E extends java.lang.Comparable<? super E>> TreePSet<E> empty()
        Returns an empty TreePSet using the natural ordering.
        Type Parameters:
        E - the type of elements to be maintained by the set
        Returns:
        an empty TreePSet using the natural ordering
      • empty

        public static <E> TreePSet<E> empty​(java.util.Comparator<? super E> comparator)
        Returns an empty TreePSet using the specified comparator.
        Type Parameters:
        E - the type of elements to be maintained by the set
        Parameters:
        comparator - the comparator according to which elements should be ordered
        Returns:
        an empty TreePSet using the specified comparator
        Throws:
        java.lang.NullPointerException - if comparator is null
      • from

        public static <E extends java.lang.Comparable<? super E>> TreePSet<E> from​(java.util.Collection<? extends E> list)
        Returns a TreePSet with the specified elements, using their natural ordering.
        Type Parameters:
        E - the type of elements to be maintained by the set
        Parameters:
        list - the elements to include
        Returns:
        a TreePSet containing the elements of list and using the natural ordering
        Throws:
        java.lang.NullPointerException - if list is null or contains null
      • from

        public static <E> TreePSet<E> from​(java.util.Comparator<? super E> comparator,
                                           java.util.Collection<? extends E> list)
        Returns a TreePSet with the specified comparator and elements.
        Type Parameters:
        E - the type of elements to be maintained by the set
        Parameters:
        comparator - the comparator to use
        list - the collection of elements to include; may include duplicates, but the returned TreePSet will not
        Returns:
        a TreePSet with the specified comparator and elements
        Throws:
        java.lang.NullPointerException - if the comparator is null or the collection is or contains null
      • fromSortedSet

        public static <E> TreePSet<E> fromSortedSet​(java.util.SortedSet<E> set)
        Returns a TreePSet with the same elements and ordering as the specified set. This is essentially equivalent to TreePSet.from(set.comparator(), set), except that it gracefully handles a null comparator, and is much more efficient.
        Type Parameters:
        E - the type of elements to be maintained by the set
        Parameters:
        set - the set whose elements and ordering to use
        Returns:
        a TreePSet with the same elements and ordering as the specified set
        Throws:
        java.lang.NullPointerException - if the specified set is or contains null
      • of

        @SafeVarargs
        public static <E extends java.lang.Comparable<? super E>> TreePSet<E> of​(E... elements)
        Returns a TreePSet with the specified elements, using their natural ordering.
        Type Parameters:
        E - the type of elements to be maintained by the set
        Parameters:
        elements - the elements to include; may include duplicates, but the returned TreePSet will not
        Returns:
        a TreePSet containing the specified elements and using their natural ordering
        Throws:
        java.lang.NullPointerException - if any of the specified elements is null, or if the varargs array-ref is itself null
      • of

        @SafeVarargs
        public static <E> TreePSet<E> of​(java.util.Comparator<? super E> comparator,
                                         E... elements)
        Returns a TreePSet with the specified comparator and elements.
        Type Parameters:
        E - the type of elements to be maintained by the set
        Parameters:
        comparator - the comparator to use
        elements - the elements to include; may include duplicates, but the returned TreePSet will not
        Returns:
        a TreePSet containing the specified elements and using the specified comparator
        Throws:
        java.lang.NullPointerException - if the specified comparator is null, or if any of the specified elements is null, or if the varargs array-ref is itself null
      • singleton

        public static <E extends java.lang.Comparable<? super E>> TreePSet<E> singleton​(E e)
        Returns a TreePSet with a single element, using the natural ordering.
        Type Parameters:
        E - the type of elements to be maintained by the set
        Parameters:
        e - the element
        Returns:
        a TreePSet containing the specified element and using the natural ordering
        Throws:
        java.lang.NullPointerException - if the specified element is null
      • singleton

        public static <E> TreePSet<E> singleton​(java.util.Comparator<? super E> comparator,
                                                E e)
        Returns a TreePSet with a single element, using the specified comparator.
        Type Parameters:
        E - the type of elements to be maintained by the set
        Parameters:
        comparator - the comparator according to which elements should be ordered
        e - the element
        Returns:
        a TreePSet containing the specified element and using the specified comparator
        Throws:
        java.lang.NullPointerException - if either the comparator or the element is null
      • toTreePSet

        public static <E extends java.lang.Comparable<? super E>> java.util.stream.Collector<E,​?,​TreePSet<E>> toTreePSet()
        Returns a collector that gathers a stream into a TreePSet with the elements of that stream, using their natural ordering.
        Type Parameters:
        E - the type of elements to be maintained by the set
        Returns:
        a collector that gathers the elements of the stream into a TreePSet that uses the natural ordering
      • toTreePSet

        public static <E> java.util.stream.Collector<E,​?,​TreePSet<E>> toTreePSet​(java.util.Comparator<? super E> comparator)
        Returns a collector that gathers a stream into a TreePSet with the elements of that stream, using the specified comparator.
        Type Parameters:
        E - the type of elements to be maintained by the set
        Parameters:
        comparator - the comparator to use
        Returns:
        a collector that gathers the elements of the stream into a TreePSet that uses the specified comparator
        Throws:
        java.lang.NullPointerException - if the comparator is null
      • ceiling

        public E ceiling​(E e)
        Specified by:
        ceiling in interface java.util.NavigableSet<E>
      • comparator

        public java.util.Comparator<? super E> comparator()
        Specified by:
        comparator in interface PSortedSet<E>
        Specified by:
        comparator in interface java.util.SortedSet<E>
        Returns:
        The comparator used to order the elements in this set. May be null if this set uses the natural ordering of its elements, though in that case the implementations provided by this library (pcollections) return a Comparator instance that implements the natural ordering.
      • contains

        public boolean contains​(java.lang.Object e)
        Specified by:
        contains in interface java.util.Collection<E>
        Specified by:
        contains in interface java.util.Set<E>
        Overrides:
        contains in class java.util.AbstractCollection<E>
      • descendingIterator

        public java.util.Iterator<E> descendingIterator()
        Specified by:
        descendingIterator in interface java.util.NavigableSet<E>
      • descendingSet

        public TreePSet<E> descendingSet()
        Specified by:
        descendingSet in interface java.util.NavigableSet<E>
        Specified by:
        descendingSet in interface PSortedSet<E>
      • first

        public E first()
        Specified by:
        first in interface java.util.SortedSet<E>
      • floor

        public E floor​(E e)
        Specified by:
        floor in interface java.util.NavigableSet<E>
      • headSet

        public TreePSet<E> headSet​(E toElement)
        Specified by:
        headSet in interface java.util.NavigableSet<E>
        Specified by:
        headSet in interface PSortedSet<E>
        Specified by:
        headSet in interface java.util.SortedSet<E>
      • headSet

        public TreePSet<E> headSet​(E toElement,
                                   boolean inclusive)
        Specified by:
        headSet in interface java.util.NavigableSet<E>
        Specified by:
        headSet in interface PSortedSet<E>
      • higher

        public E higher​(E e)
        Specified by:
        higher in interface java.util.NavigableSet<E>
      • iterator

        public java.util.Iterator<E> iterator()
        Specified by:
        iterator in interface java.util.Collection<E>
        Specified by:
        iterator in interface java.lang.Iterable<E>
        Specified by:
        iterator in interface java.util.NavigableSet<E>
        Specified by:
        iterator in interface java.util.Set<E>
        Specified by:
        iterator in class java.util.AbstractCollection<E>
      • last

        public E last()
        Specified by:
        last in interface java.util.SortedSet<E>
      • lower

        public E lower​(E e)
        Specified by:
        lower in interface java.util.NavigableSet<E>
      • minus

        public TreePSet<E> minus​(java.lang.Object e)
        Specified by:
        minus in interface PCollection<E>
        Specified by:
        minus in interface PSet<E>
        Specified by:
        minus in interface PSortedSet<E>
        Returns:
        This set, except with e removed (if e is an element of this set).
      • minusAll

        public TreePSet<E> minusAll​(java.util.Collection<?> list)
        Specified by:
        minusAll in interface PCollection<E>
        Specified by:
        minusAll in interface PSet<E>
        Specified by:
        minusAll in interface PSortedSet<E>
        Returns:
        This set, except with the elements of list removed (if they are elements of this set).
      • intersect

        public TreePSet<E> intersect​(java.util.Collection<? extends E> list)
        Specified by:
        intersect in interface PSet<E>
        Specified by:
        intersect in interface PSortedSet<E>
        Returns:
        the equivalent of this.minusAll(this.minusAll(list)).
      • minusFirst

        public TreePSet<E> minusFirst()
        Specified by:
        minusFirst in interface PSortedSet<E>
        Returns:
        This set, except with its first (least) element removed.
      • minusLast

        public TreePSet<E> minusLast()
        Specified by:
        minusLast in interface PSortedSet<E>
        Returns:
        This set, except with its last (greatest) element removed.
      • plus

        public TreePSet<E> plus​(E e)
        Specified by:
        plus in interface PCollection<E>
        Specified by:
        plus in interface PSet<E>
        Specified by:
        plus in interface PSortedSet<E>
        Returns:
        This set, except with e added (unless e is already an element of this set).
      • plusAll

        public TreePSet<E> plusAll​(java.util.Collection<? extends E> list)
        Specified by:
        plusAll in interface PCollection<E>
        Specified by:
        plusAll in interface PSet<E>
        Specified by:
        plusAll in interface PSortedSet<E>
        Returns:
        This set, except with the elements of list added (unless they are already elements of this set).
      • size

        public int size()
        Specified by:
        size in interface java.util.Collection<E>
        Specified by:
        size in interface java.util.Set<E>
        Specified by:
        size in class java.util.AbstractCollection<E>
      • subSet

        public TreePSet<E> subSet​(E fromElement,
                                  E toElement)
        Specified by:
        subSet in interface java.util.NavigableSet<E>
        Specified by:
        subSet in interface PSortedSet<E>
        Specified by:
        subSet in interface java.util.SortedSet<E>
      • subSet

        public TreePSet<E> subSet​(E fromElement,
                                  boolean fromInclusive,
                                  E toElement,
                                  boolean toInclusive)
        Specified by:
        subSet in interface java.util.NavigableSet<E>
        Specified by:
        subSet in interface PSortedSet<E>
      • tailSet

        public TreePSet<E> tailSet​(E fromElement)
        Specified by:
        tailSet in interface java.util.NavigableSet<E>
        Specified by:
        tailSet in interface PSortedSet<E>
        Specified by:
        tailSet in interface java.util.SortedSet<E>
      • tailSet

        public TreePSet<E> tailSet​(E fromElement,
                                   boolean inclusive)
        Specified by:
        tailSet in interface java.util.NavigableSet<E>
        Specified by:
        tailSet in interface PSortedSet<E>
      • sneakilyDowncast

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