Module java.base

Package java.util

Class TreeSet<E>

java.lang.Object

java.util.AbstractCollection<E>

java.util.AbstractSet<E>

java.util.TreeSet<E>

Type Parameters:

E - type of element

All Implemented Interfaces:

Serializable, Cloneable, Iterable<E>, Collection<E>, NavigableSet<E>, Set<E>, SortedSet<E>

public class TreeSet<E>
extends AbstractSet<E>
implements NavigableSet<E>, Cloneable, Serializable

TreeSet is an implementation of NavigableSet. All optional operations are supported, adding and removing. The elements can be any objects which are comparable to each other either using their natural order or a specified Comparator.

Since:

1.2

See Also:

• Serialized Form

Constructor Summary

Constructors

Constructor	Description
TreeSet()	Constructs a new empty instance of TreeSet which uses natural ordering.
TreeSet(Collection<? extends E> collection)	Constructs a new instance of TreeSet which uses natural ordering and containing the unique elements in the specified collection.
TreeSet(Comparator<? super E> comparator)	Constructs a new empty instance of TreeSet which uses the specified Comparator.
TreeSet(SortedSet<E> set)	Constructs a new instance of TreeSet containing the elements in the specified SortedSet and using the same Comparator.

Method Summary

Modifier and Type	Method	Description
boolean	add(E object)	Adds the specified object to this TreeSet.
boolean	addAll(Collection<? extends E> collection)	Adds the objects in the specified Collection to this TreeSet.
E	ceiling(E e)	Returns the least element in this set greater than or equal to the given element, or null if there is no such element.
void	clear()	Removes all elements from this TreeSet, leaving it empty.
Object	clone()	Answers a new TreeSet with the same elements, size and comparator as this TreeSet.
Comparator<? super E>	comparator()	Answers the Comparator used to compare elements in this TreeSet.
boolean	contains(Object object)	Searches this TreeSet for the specified object.
Iterator<E>	descendingIterator()	Returns an iterator over the elements in this set, in descending order.
NavigableSet<E>	descendingSet()	Returns a reverse order view of the elements contained in this set.
E	first()	Answers the first element in this TreeSet.
E	floor(E e)	Returns the greatest element in this set less than or equal to the given element, or null if there is no such element.
SortedSet<E>	headSet(E end)	Answers a SortedSet of the specified portion of this TreeSet which contains elements less than the end element.
NavigableSet<E>	headSet(E end, boolean endInclusive)	Returns a view of the portion of this set whose elements are less than (or equal to, if inclusive is true) toElement.
E	higher(E e)	Returns the least element in this set strictly greater than the given element, or null if there is no such element.
boolean	isEmpty()	Answers if this TreeSet has no elements, a size of zero.
Iterator<E>	iterator()	Answers an Iterator on the elements of this TreeSet.
E	last()	Answers the last element in this TreeSet.
E	lower(E e)	Returns the greatest element in this set strictly less than the given element, or null if there is no such element.
E	pollFirst()	Retrieves and removes the first (lowest) element, or returns null if this set is empty.
E	pollLast()	Retrieves and removes the last (highest) element, or returns null if this set is empty.
boolean	remove(Object object)	Removes an occurrence of the specified object from this TreeSet.
int	size()	Answers the number of elements in this TreeSet.
NavigableSet<E>	subSet(E start, boolean startInclusive, E end, boolean endInclusive)	Returns a view of the portion of this set whose elements range from fromElement to toElement.
SortedSet<E>	subSet(E start, E end)	Answers a SortedSet of the specified portion of this TreeSet which contains elements greater or equal to the start element but less than the end element.
SortedSet<E>	tailSet(E start)	Answers a SortedSet of the specified portion of this TreeSet which contains elements greater or equal to the start element.
NavigableSet<E>	tailSet(E start, boolean startInclusive)	Returns a view of the portion of this set whose elements are greater than (or equal to, if inclusive is true) fromElement.

Methods declared in class java.util.AbstractSet

equals, hashCode, removeAll

Methods declared in class java.util.AbstractCollection

containsAll, retainAll, toArray, toArray, toString

Methods declared in class java.lang.Object

finalize, getClass, notify, notifyAll, wait, wait, wait

Methods declared in interface java.util.Collection

parallelStream, removeIf, stream, toArray

Methods declared in interface java.lang.Iterable

forEach

Methods declared in interface java.util.Set

containsAll, equals, hashCode, removeAll, retainAll, toArray, toArray

Methods declared in interface java.util.SortedSet

spliterator

Constructor Details

TreeSet

public TreeSet()

Constructs a new empty instance of TreeSet which uses natural ordering.

TreeSet

public TreeSet(Collection<? extends E> collection)

Constructs a new instance of TreeSet which uses natural ordering and containing the unique elements in the specified collection.

Parameters:

collection - the collection of elements to add

Throws:

ClassCastException - when an element in the Collection does not implement the Comparable interface, or the elements in the Collection cannot be compared

TreeSet

public TreeSet(Comparator<? super E> comparator)

Constructs a new empty instance of TreeSet which uses the specified Comparator.

Parameters:

comparator - the Comparator

TreeSet

public TreeSet(SortedSet<E> set)

Constructs a new instance of TreeSet containing the elements in the specified SortedSet and using the same Comparator.

Parameters:

set - the SortedSet of elements to add

Method Details

add

public boolean add(E object)

Adds the specified object to this TreeSet.

Specified by:

add in interface Collection<E>

Specified by:

add in interface Set<E>

Overrides:

add in class AbstractCollection<E>

Parameters:

object - the object to add

Returns:

true when this TreeSet did not already contain the object, false otherwise

Throws:

ClassCastException - when the object cannot be compared with the elements in this TreeSet

NullPointerException - when the object is null and the comparator cannot handle null

addAll

public boolean addAll(Collection<? extends E> collection)

Adds the objects in the specified Collection to this TreeSet.

Specified by:

addAll in interface Collection<E>

Specified by:

addAll in interface Set<E>

Overrides:

addAll in class AbstractCollection<E>

Parameters:

collection - the Collection of objects

Returns:

true if this TreeSet is modified, false otherwise

Throws:

ClassCastException - when an object in the Collection cannot be compared with the elements in this TreeSet

NullPointerException - when an object in the Collection is null and the comparator cannot handle null

See Also:

• AbstractCollection.add(Object)

clear

public void clear()

Removes all elements from this TreeSet, leaving it empty.

Specified by:

clear in interface Collection<E>

Specified by:

clear in interface Set<E>

Overrides:

clear in class AbstractCollection<E>

See Also:

• isEmpty()
• size()

clone

public Object clone()

Answers a new TreeSet with the same elements, size and comparator as this TreeSet.

Overrides:

clone in class Object

Returns:

a shallow copy of this TreeSet

See Also:

• Cloneable

comparator

public Comparator<? super E> comparator()

Answers the Comparator used to compare elements in this TreeSet.

Specified by:

comparator in interface SortedSet<E>

Returns:

a Comparator or null if the natural ordering is used

contains

public boolean contains(Object object)

Searches this TreeSet for the specified object.

Specified by:

contains in interface Collection<E>

Specified by:

contains in interface Set<E>

Overrides:

contains in class AbstractCollection<E>

Parameters:

object - the object to search for

Returns:

true if object is an element of this TreeSet, false otherwise

Throws:

ClassCastException - when the object cannot be compared with the elements in this TreeSet

NullPointerException - when the object is null and the comparator cannot handle null

isEmpty

public boolean isEmpty()

Answers if this TreeSet has no elements, a size of zero.

Specified by:

isEmpty in interface Collection<E>

Specified by:

isEmpty in interface Set<E>

Overrides:

isEmpty in class AbstractCollection<E>

Returns:

true if this TreeSet has no elements, false otherwise

See Also:

• size()

iterator

public Iterator<E> iterator()

Answers an Iterator on the elements of this TreeSet.

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>

Returns:

an Iterator on the elements of this TreeSet

See Also:

• Iterator

descendingIterator

public Iterator<E> descendingIterator()

Returns an iterator over the elements in this set, in descending order. Equivalent in effect to descendingSet().iterator().

Specified by:

descendingIterator in interface NavigableSet<E>

Returns:

an iterator over the elements in this set, in descending order

Since:

1.6

See Also:

• NavigableSet.descendingIterator()

remove

public boolean remove(Object object)

Removes an occurrence of the specified object from this TreeSet.

Specified by:

remove in interface Collection<E>

Specified by:

remove in interface Set<E>

Overrides:

remove in class AbstractCollection<E>

Parameters:

object - the object to remove

Returns:

true if this TreeSet is modified, false otherwise

Throws:

ClassCastException - when the object cannot be compared with the elements in this TreeSet

NullPointerException - when the object is null and the comparator cannot handle null

size

public int size()

Answers the number of elements in this TreeSet.

Specified by:

size in interface Collection<E>

Specified by:

size in interface Set<E>

Returns:

the number of elements in this TreeSet

first

public E first()

Answers the first element in this TreeSet.

Specified by:

first in interface SortedSet<E>

Returns:

the first element

Throws:

NoSuchElementException - when this TreeSet is empty

last

public E last()

Answers the last element in this TreeSet.

Specified by:

last in interface SortedSet<E>

Returns:

the last element

Throws:

NoSuchElementException - when this TreeSet is empty

pollFirst

public E pollFirst()

Retrieves and removes the first (lowest) element, or returns null if this set is empty.

Specified by:

pollFirst in interface NavigableSet<E>

Returns:

the first element, or null if this set is empty

Since:

1.6

See Also:

• NavigableSet.pollFirst()

pollLast

public E pollLast()

Retrieves and removes the last (highest) element, or returns null if this set is empty.

Specified by:

pollLast in interface NavigableSet<E>

Returns:

the last element, or null if this set is empty

Since:

1.6

See Also:

• NavigableSet.pollLast()

higher

public E higher(E e)

Returns the least element in this set strictly greater than the given element, or null if there is no such element.

Specified by:

higher in interface NavigableSet<E>

Parameters:

e - the value to match

Returns:

the least element greater than e, or null if there is no such element

Since:

1.6

See Also:

• NavigableSet.higher(Object)

lower

public E lower(E e)

Returns the greatest element in this set strictly less than the given element, or null if there is no such element.

Specified by:

lower in interface NavigableSet<E>

Parameters:

e - the value to match

Returns:

the greatest element less than e, or null if there is no such element

Since:

1.6

See Also:

• NavigableSet.lower(Object)

ceiling

public E ceiling(E e)

Returns the least element in this set greater than or equal to the given element, or null if there is no such element.

Specified by:

ceiling in interface NavigableSet<E>

Parameters:

e - the value to match

Returns:

the least element greater than or equal to e, or null if there is no such element

Since:

1.6

See Also:

• NavigableSet.ceiling(Object)

floor

public E floor(E e)

Returns the greatest element in this set less than or equal to the given element, or null if there is no such element.

Specified by:

floor in interface NavigableSet<E>

Parameters:

e - the value to match

Returns:

the greatest element less than or equal to e, or null if there is no such element

Since:

1.6

See Also:

• NavigableSet.floor(Object)

descendingSet

public NavigableSet<E> descendingSet()

Returns a reverse order view of the elements contained in this set. The descending set is backed by this set, so changes to the set are reflected in the descending set, and vice-versa. If either set is modified while an iteration over either set is in progress (except through the iterator's own remove operation), the results of the iteration are undefined.

The returned set has an ordering equivalent to Collections.reverseOrder(comparator()). The expression s.descendingSet().descendingSet() returns a view of s essentially equivalent to s.

Specified by:

descendingSet in interface NavigableSet<E>

Returns:

a reverse order view of this set

Since:

1.6

See Also:

• NavigableSet.descendingSet()

subSet

public NavigableSet<E> subSet(E start,
 boolean startInclusive,
 E end,
 boolean endInclusive)

Returns a view of the portion of this set whose elements range from fromElement to toElement. If fromElement and toElement are equal, the returned set is empty unless fromInclusive and toInclusive are both true. The returned set is backed by this set, so changes in the returned set are reflected in this set, and vice-versa. The returned set supports all optional set operations that this set supports.

The returned set will throw an IllegalArgumentException on an attempt to insert an element outside its range.

Specified by:

subSet in interface NavigableSet<E>

Parameters:

start - low endpoint of the returned set

startInclusive - true if the low endpoint is to be included in the returned view

end - high endpoint of the returned set

endInclusive - true if the high endpoint is to be included in the returned view

Returns:

a view of the portion of this set whose elements range from fromElement, inclusive, to toElement, exclusive

Since:

1.6

See Also:

• NavigableSet.subSet(Object, boolean, Object, boolean)

headSet

public NavigableSet<E> headSet(E end,
 boolean endInclusive)

Returns a view of the portion of this set whose elements are less than (or equal to, if inclusive is true) toElement. The returned set is backed by this set, so changes in the returned set are reflected in this set, and vice-versa. The returned set supports all optional set operations that this set supports.

The returned set will throw an IllegalArgumentException on an attempt to insert an element outside its range.

Specified by:

headSet in interface NavigableSet<E>

Parameters:

end - high endpoint of the returned set

endInclusive - true if the high endpoint is to be included in the returned view

Returns:

a view of the portion of this set whose elements are less than (or equal to, if inclusive is true) toElement

Since:

1.6

See Also:

• NavigableSet.headSet(Object, boolean)

tailSet

public NavigableSet<E> tailSet(E start,
 boolean startInclusive)

Returns a view of the portion of this set whose elements are greater than (or equal to, if inclusive is true) fromElement. The returned set is backed by this set, so changes in the returned set are reflected in this set, and vice-versa. The returned set supports all optional set operations that this set supports.

The returned set will throw an IllegalArgumentException on an attempt to insert an element outside its range.

Specified by:

tailSet in interface NavigableSet<E>

Parameters:

start - low endpoint of the returned set

startInclusive - true if the low endpoint is to be included in the returned view

Returns:

a view of the portion of this set whose elements are greater than or equal to fromElement

Since:

1.6

See Also:

• NavigableSet.tailSet(Object, boolean)

subSet

public SortedSet<E> subSet(E start,
 E end)

Answers a SortedSet of the specified portion of this TreeSet which contains elements greater or equal to the start element but less than the end element. The returned SortedSet is backed by this TreeSet so changes to one are reflected by the other.

Specified by:

subSet in interface NavigableSet<E>

Specified by:

subSet in interface SortedSet<E>

Parameters:

start - the start element

end - the end element

Returns:

a subset where the elements are greater or equal to start and less than end

Throws:

ClassCastException - when the start or end object cannot be compared with the elements in this TreeSet

NullPointerException - when the start or end object is null and the comparator cannot handle null

headSet

public SortedSet<E> headSet(E end)

Answers a SortedSet of the specified portion of this TreeSet which contains elements less than the end element. The returned SortedSet is backed by this TreeSet so changes to one are reflected by the other.

Specified by:

headSet in interface NavigableSet<E>

Specified by:

headSet in interface SortedSet<E>

Parameters:

end - the end element

Returns:

a subset where the elements are less than end

Throws:

ClassCastException - when the end object cannot be compared with the elements in this TreeSet

NullPointerException - when the end object is null and the comparator cannot handle null

tailSet

public SortedSet<E> tailSet(E start)

Answers a SortedSet of the specified portion of this TreeSet which contains elements greater or equal to the start element. The returned SortedSet is backed by this TreeSet so changes to one are reflected by the other.

Specified by:

tailSet in interface NavigableSet<E>

Specified by:

tailSet in interface SortedSet<E>

Parameters:

start - the start element

Returns:

a subset where the elements are greater or equal to start

Throws:

ClassCastException - when the start object cannot be compared with the elements in this TreeSet

NullPointerException - when the start object is null and the comparator cannot handle null