Class TreePSet<E>

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

public final class TreePSet<E> extends AbstractUnmodifiableSet<E> implements PSortedSet<E>, 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:
  • Field Details

    • serialVersionUID

      private static final long serialVersionUID
      See Also:
    • tree

      private final KVTree<E,?> tree
    • ltrComparator

      private final Comparator<? super E> ltrComparator
    • isLeftToRight

      private final boolean isLeftToRight
  • Constructor Details

    • TreePSet

      TreePSet(KVTree<E,?> tree, 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 Details

    • empty

      public static <E extends 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(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:
      NullPointerException - if comparator is null
    • from

      public static <E extends Comparable<? super E>> TreePSet<E> from(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:
      NullPointerException - if list is null or contains null
    • from

      public static <E> TreePSet<E> from(Comparator<? super E> comparator, 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:
      NullPointerException - if the comparator is null or the collection is or contains null
    • fromSortedSet

      public static <E> TreePSet<E> fromSortedSet(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:
      NullPointerException - if the specified set is or contains null
    • of

      @SafeVarargs public static <E extends 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:
      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(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:
      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 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:
      NullPointerException - if the specified element is null
    • singleton

      public static <E> TreePSet<E> singleton(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:
      NullPointerException - if either the comparator or the element is null
    • toTreePSet

      public static <E extends Comparable<? super E>> 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> Collector<E,?,TreePSet<E>> toTreePSet(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:
      NullPointerException - if the comparator is null
    • ceiling

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

      public Comparator<? super E> comparator()
      Specified by:
      comparator in interface PSortedSet<E>
      Specified by:
      comparator in interface 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(Object e)
      Specified by:
      contains in interface Collection<E>
      Specified by:
      contains in interface Set<E>
      Overrides:
      contains in class AbstractCollection<E>
    • descendingIterator

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

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

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

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

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

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

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

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

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

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

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

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

      public TreePSet<E> intersect(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>
      Parameters:
      e -
      Returns:
      This set, except with e added (unless e is already an element of this set).
    • plusAll

      public TreePSet<E> plusAll(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>
      Parameters:
      list -
      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 Collection<E>
      Specified by:
      size in interface Set<E>
      Specified by:
      size in class AbstractCollection<E>
    • subSet

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

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

      public TreePSet<E> tailSet(E fromElement)
      Specified by:
      tailSet in interface NavigableSet<E>
      Specified by:
      tailSet in interface PSortedSet<E>
      Specified by:
      tailSet in interface SortedSet<E>
    • search

      private E search(E e, KVTree.SearchType searchTypeIfLeftToRight, KVTree.SearchType searchTypeIfRightToLeft)
    • tailSet

      public TreePSet<E> tailSet(E fromElement, boolean inclusive)
      Specified by:
      tailSet in interface NavigableSet<E>
      Specified by:
      tailSet in interface PSortedSet<E>
    • withTree

      private TreePSet<E> withTree(KVTree<E,?> tree)
    • sneakilyDowncast

      private static <T> T sneakilyDowncast(Object o)