- 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:
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 ofPSortedSet
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
-
-
Field Summary
Fields Modifier and Type Field Description private boolean
isLeftToRight
private java.util.Comparator<? super E>
ltrComparator
private static long
serialVersionUID
private KVTree<E,?>
tree
-
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 org.pcollections.AbstractUnmodifiableSet
add, addAll, clear, remove, removeAll, removeIf, retainAll
-
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 org.pcollections.PCollection
add, addAll, clear, remove, removeAll, retainAll
-
Methods inherited from interface org.pcollections.PSortedSet
pollFirst, pollLast
-
-
-
-
Field Detail
-
serialVersionUID
private static final long serialVersionUID
- See Also:
- Constant Field Values
-
ltrComparator
private final java.util.Comparator<? super E> ltrComparator
-
isLeftToRight
private final boolean isLeftToRight
-
-
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 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:
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 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:
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 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:
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 orderede
- 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
-
comparator
public java.util.Comparator<? super E> comparator()
- Specified by:
comparator
in interfacePSortedSet<E>
- Specified by:
comparator
in interfacejava.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)
-
descendingIterator
public java.util.Iterator<E> descendingIterator()
- Specified by:
descendingIterator
in interfacejava.util.NavigableSet<E>
-
descendingSet
public TreePSet<E> descendingSet()
- Specified by:
descendingSet
in interfacejava.util.NavigableSet<E>
- Specified by:
descendingSet
in interfacePSortedSet<E>
-
headSet
public TreePSet<E> headSet(E toElement)
- Specified by:
headSet
in interfacejava.util.NavigableSet<E>
- Specified by:
headSet
in interfacePSortedSet<E>
- Specified by:
headSet
in interfacejava.util.SortedSet<E>
-
headSet
public TreePSet<E> headSet(E toElement, boolean inclusive)
- Specified by:
headSet
in interfacejava.util.NavigableSet<E>
- Specified by:
headSet
in interfacePSortedSet<E>
-
iterator
public java.util.Iterator<E> iterator()
-
minus
public TreePSet<E> minus(java.lang.Object e)
- Specified by:
minus
in interfacePCollection<E>
- Specified by:
minus
in interfacePSet<E>
- Specified by:
minus
in interfacePSortedSet<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 interfacePCollection<E>
- Specified by:
minusAll
in interfacePSet<E>
- Specified by:
minusAll
in interfacePSortedSet<E>
- Returns:
- This set, except with the elements of list removed (if they are elements of this set).
-
minusFirst
public TreePSet<E> minusFirst()
- Specified by:
minusFirst
in interfacePSortedSet<E>
- Returns:
- This set, except with its first (least) element removed.
-
minusLast
public TreePSet<E> minusLast()
- Specified by:
minusLast
in interfacePSortedSet<E>
- Returns:
- This set, except with its last (greatest) element removed.
-
plus
public TreePSet<E> plus(E e)
- Specified by:
plus
in interfacePCollection<E>
- Specified by:
plus
in interfacePSet<E>
- Specified by:
plus
in interfacePSortedSet<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 interfacePCollection<E>
- Specified by:
plusAll
in interfacePSet<E>
- Specified by:
plusAll
in interfacePSortedSet<E>
- Returns:
- This set, except with the elements of list added (unless they are already elements of this set).
-
size
public int size()
-
subSet
public TreePSet<E> subSet(E fromElement, E toElement)
- Specified by:
subSet
in interfacejava.util.NavigableSet<E>
- Specified by:
subSet
in interfacePSortedSet<E>
- Specified by:
subSet
in interfacejava.util.SortedSet<E>
-
subSet
public TreePSet<E> subSet(E fromElement, boolean fromInclusive, E toElement, boolean toInclusive)
- Specified by:
subSet
in interfacejava.util.NavigableSet<E>
- Specified by:
subSet
in interfacePSortedSet<E>
-
tailSet
public TreePSet<E> tailSet(E fromElement)
- Specified by:
tailSet
in interfacejava.util.NavigableSet<E>
- Specified by:
tailSet
in interfacePSortedSet<E>
- Specified by:
tailSet
in interfacejava.util.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 interfacejava.util.NavigableSet<E>
- Specified by:
tailSet
in interfacePSortedSet<E>
-
sneakilyDowncast
private static <T> T sneakilyDowncast(java.lang.Object o)
-
-