java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractSet<E>
org.pcollections.AbstractUnmodifiableSet<E>
org.pcollections.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 Summary
FieldsModifier and TypeFieldDescriptionprivate final boolean
private final Comparator
<? super E> private static final long
-
Constructor Summary
ConstructorsConstructorDescriptionTreePSet
(KVTree<E, ?> tree, Comparator<? super E> ltrComparator, boolean isLeftToRight) Non-private only because also used by TreePMap.keySet(). -
Method Summary
Modifier and TypeMethodDescriptionComparator
<? super E> boolean
static <E extends Comparable<? super E>>
TreePSet<E> empty()
Returns an empty TreePSet using the natural ordering.static <E> TreePSet
<E> empty
(Comparator<? super E> comparator) Returns an empty TreePSet using the specified comparator.first()
static <E extends Comparable<? super E>>
TreePSet<E> from
(Collection<? extends E> list) Returns a TreePSet with the specified elements, using their natural ordering.static <E> TreePSet
<E> from
(Comparator<? super E> comparator, Collection<? extends E> list) Returns a TreePSet with the specified comparator and elements.static <E> TreePSet
<E> fromSortedSet
(SortedSet<E> set) Returns a TreePSet with the same elements and ordering as the specified set.intersect
(Collection<? extends E> list) iterator()
last()
minusAll
(Collection<?> list) static <E extends Comparable<? super E>>
TreePSet<E> of
(E... elements) Returns a TreePSet with the specified elements, using their natural ordering.static <E> TreePSet
<E> of
(Comparator<? super E> comparator, E... elements) Returns a TreePSet with the specified comparator and elements.plusAll
(Collection<? extends E> list) private E
search
(E e, KVTree.SearchType searchTypeIfLeftToRight, KVTree.SearchType searchTypeIfRightToLeft) static <E extends Comparable<? super E>>
TreePSet<E> singleton
(E e) Returns a TreePSet with a single element, using the natural ordering.static <E> TreePSet
<E> singleton
(Comparator<? super E> comparator, E e) Returns a TreePSet with a single element, using the specified comparator.int
size()
private static <T> T
static <E extends Comparable<? super E>>
Collector<E, ?, TreePSet<E>> Returns a collector that gathers a stream into a TreePSet with the elements of that stream, using their natural ordering.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.Methods inherited from class org.pcollections.AbstractUnmodifiableSet
add, addAll, clear, remove, removeAll, removeIf, retainAll
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 org.pcollections.PCollection
add, addAll, clear, remove, removeAll, retainAll
Methods inherited from interface org.pcollections.PSortedSet
pollFirst, pollLast
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 Details
-
serialVersionUID
private static final long serialVersionUID- See Also:
-
tree
-
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
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
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
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
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 uselist
- 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
Returns a TreePSet with the same elements and ordering as the specified set. This is essentially equivalent toTreePSet.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
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
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 useelements
- 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
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
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 orderede
- 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
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
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
- Specified by:
ceiling
in interfaceNavigableSet<E>
-
comparator
- Specified by:
comparator
in interfacePSortedSet<E>
- Specified by:
comparator
in interfaceSortedSet<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
- Specified by:
contains
in interfaceCollection<E>
- Specified by:
contains
in interfaceSet<E>
- Overrides:
contains
in classAbstractCollection<E>
-
descendingIterator
- Specified by:
descendingIterator
in interfaceNavigableSet<E>
-
descendingSet
- Specified by:
descendingSet
in interfaceNavigableSet<E>
- Specified by:
descendingSet
in interfacePSortedSet<E>
-
first
-
floor
- Specified by:
floor
in interfaceNavigableSet<E>
-
headSet
- Specified by:
headSet
in interfaceNavigableSet<E>
- Specified by:
headSet
in interfacePSortedSet<E>
- Specified by:
headSet
in interfaceSortedSet<E>
-
headSet
- Specified by:
headSet
in interfaceNavigableSet<E>
- Specified by:
headSet
in interfacePSortedSet<E>
-
higher
- Specified by:
higher
in interfaceNavigableSet<E>
-
iterator
- Specified by:
iterator
in interfaceCollection<E>
- Specified by:
iterator
in interfaceIterable<E>
- Specified by:
iterator
in interfaceNavigableSet<E>
- Specified by:
iterator
in interfaceSet<E>
- Specified by:
iterator
in classAbstractCollection<E>
-
last
-
lower
- Specified by:
lower
in interfaceNavigableSet<E>
-
minus
- Specified by:
minus
in interfacePCollection<E>
- Specified by:
minus
in interfacePSet<E>
- Specified by:
minus
in interfacePSortedSet<E>
- Parameters:
e
-- Returns:
- This set, except with e removed (if e is an element of this set).
-
minusAll
- Specified by:
minusAll
in interfacePCollection<E>
- Specified by:
minusAll
in interfacePSet<E>
- Specified by:
minusAll
in interfacePSortedSet<E>
- Parameters:
list
-- Returns:
- This set, except with the elements of list removed (if they are elements of this set).
-
intersect
-
minusFirst
- Specified by:
minusFirst
in interfacePSortedSet<E>
- Returns:
- This set, except with its first (least) element removed.
-
minusLast
- Specified by:
minusLast
in interfacePSortedSet<E>
- Returns:
- This set, except with its last (greatest) element removed.
-
plus
- Specified by:
plus
in interfacePCollection<E>
- Specified by:
plus
in interfacePSet<E>
- Specified by:
plus
in interfacePSortedSet<E>
- Parameters:
e
-- Returns:
- This set, except with e added (unless e is already an element of this set).
-
plusAll
- Specified by:
plusAll
in interfacePCollection<E>
- Specified by:
plusAll
in interfacePSet<E>
- Specified by:
plusAll
in interfacePSortedSet<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 interfaceCollection<E>
- Specified by:
size
in interfaceSet<E>
- Specified by:
size
in classAbstractCollection<E>
-
subSet
- Specified by:
subSet
in interfaceNavigableSet<E>
- Specified by:
subSet
in interfacePSortedSet<E>
- Specified by:
subSet
in interfaceSortedSet<E>
-
subSet
- Specified by:
subSet
in interfaceNavigableSet<E>
- Specified by:
subSet
in interfacePSortedSet<E>
-
tailSet
- Specified by:
tailSet
in interfaceNavigableSet<E>
- Specified by:
tailSet
in interfacePSortedSet<E>
- Specified by:
tailSet
in interfaceSortedSet<E>
-
search
private E search(E e, KVTree.SearchType searchTypeIfLeftToRight, KVTree.SearchType searchTypeIfRightToLeft) -
tailSet
- Specified by:
tailSet
in interfaceNavigableSet<E>
- Specified by:
tailSet
in interfacePSortedSet<E>
-
withTree
-
sneakilyDowncast
-