java.util

Class TreeSet

Implemented Interfaces:
Cloneable, Collection, Serializable, Set, SortedSet

public class TreeSet
extends AbstractSet
implements SortedSet, Cloneable, Serializable

This class provides a TreeMap-backed implementation of the SortedSet interface. The elements will be sorted according to their natural order, or according to the provided Comparator.

Most operations are O(log n), but there is so much overhead that this makes small sets expensive. Note that the ordering must be consistent with equals to correctly implement the Set interface. If this condition is violated, the set is still well-behaved, but you may have suprising results when comparing it to other sets.

This implementation is not synchronized. If you need to share this between multiple threads, do something like:
SortedSet s = Collections.synchronizedSortedSet(new TreeSet(...));

The iterators are fail-fast, meaning that any structural modification, except for remove() called on the iterator itself, cause the iterator to throw a ConcurrentModificationException rather than exhibit non-deterministic behavior.

Since:
1.2
See Also:
Collection, Set, HashSet, LinkedHashSet, Comparable, Comparator, Collections.synchronizedSortedSet(SortedSet), TreeMap, Serialized Form

Constructor Summary

TreeSet()
Construct a new TreeSet whose backing TreeMap using the "natural" ordering of keys.
TreeSet(Collection collection)
Construct a new TreeSet whose backing TreeMap uses the "natural" orering of the keys and which contains all of the elements in the supplied Collection.
TreeSet(Comparator comparator)
Construct a new TreeSet whose backing TreeMap uses the supplied Comparator.
TreeSet(SortedSet sortedSet)
Construct a new TreeSet, using the same key ordering as the supplied SortedSet and containing all of the elements in the supplied SortedSet.

Method Summary

boolean
add(Object obj)
Adds the spplied Object to the Set if it is not already in the Set; returns true if the element is added, false otherwise.
boolean
addAll(Collection c)
Adds all of the elements in the supplied Collection to this TreeSet.
void
clear()
Removes all elements in this Set.
Object
clone()
Returns a shallow copy of this Set.
Comparator
comparator()
Returns this Set's comparator.
boolean
contains(Object obj)
Returns true if this Set contains the supplied Object, false otherwise.
Object
first()
Returns the first (by order) element in this Set.
SortedSet
headSet(Object to)
Returns a view of this Set including all elements less than to.
boolean
isEmpty()
Returns true if this Set has size 0, false otherwise.
Iterator
iterator()
Returns in Iterator over the elements in this TreeSet, which traverses in ascending order.
Object
last()
Returns the last (by order) element in this Set.
boolean
remove(Object obj)
If the supplied Object is in this Set, it is removed, and true is returned; otherwise, false is returned.
int
size()
Returns the number of elements in this Set
SortedSet
subSet(Object from, Object to)
Returns a view of this Set including all elements greater or equal to from and less than to (a half-open interval).
SortedSet
tailSet(Object from)
Returns a view of this Set including all elements greater or equal to from.

Methods inherited from class java.util.AbstractSet

equals, hashCode, removeAll

Methods inherited from class java.util.AbstractCollection

add, addAll, clear, contains, containsAll, isEmpty, iterator, remove, removeAll, retainAll, size, toArray, toArray, toString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

TreeSet

public TreeSet()
Construct a new TreeSet whose backing TreeMap using the "natural" ordering of keys. Elements that are not mutually comparable will cause ClassCastExceptions down the road.
See Also:
Comparable

TreeSet

public TreeSet(Collection collection)
Construct a new TreeSet whose backing TreeMap uses the "natural" orering of the keys and which contains all of the elements in the supplied Collection. This runs in n*log(n) time.
Parameters:
collection - the new Set will be initialized with all of the elements in this Collection
Throws:
ClassCastException - if the elements of the collection are not comparable
NullPointerException - if the collection is null
See Also:
Comparable

TreeSet

public TreeSet(Comparator comparator)
Construct a new TreeSet whose backing TreeMap uses the supplied Comparator. Elements that are not mutually comparable will cause ClassCastExceptions down the road.
Parameters:
comparator - the Comparator this Set will use

TreeSet

public TreeSet(SortedSet sortedSet)
Construct a new TreeSet, using the same key ordering as the supplied SortedSet and containing all of the elements in the supplied SortedSet. This constructor runs in linear time.
Parameters:
sortedSet - the new TreeSet will use this SortedSet's comparator and will initialize itself with all its elements
Throws:
NullPointerException - if sortedSet is null

Method Details

add

public boolean add(Object obj)
Adds the spplied Object to the Set if it is not already in the Set; returns true if the element is added, false otherwise.
Specified by:
add in interface Set
add in interface Collection
Overrides:
add in interface AbstractCollection
Parameters:
obj - the Object to be added to this Set
Throws:
ClassCastException - if the element cannot be compared with objects already in the set

addAll

public boolean addAll(Collection c)
Adds all of the elements in the supplied Collection to this TreeSet.
Specified by:
addAll in interface Set
addAll in interface Collection
Overrides:
addAll in interface AbstractCollection
Parameters:
c - The collection to add
Returns:
true if the Set is altered, false otherwise
Throws:
NullPointerException - if c is null
ClassCastException - if an element in c cannot be compared with objects already in the set

clear

public void clear()
Removes all elements in this Set.
Specified by:
clear in interface Set
clear in interface Collection
Overrides:
clear in interface AbstractCollection

clone

public Object clone()
Returns a shallow copy of this Set. The elements are not cloned.
Overrides:
clone in interface Object
Returns:
the cloned set

comparator

public Comparator comparator()
Returns this Set's comparator.
Specified by:
comparator in interface SortedSet
Returns:
the comparator, or null if the set uses natural ordering

contains

public boolean contains(Object obj)
Returns true if this Set contains the supplied Object, false otherwise.
Specified by:
contains in interface Set
contains in interface Collection
Overrides:
contains in interface AbstractCollection
Parameters:
obj - the Object to check for
Returns:
true if it is in the set
Throws:
ClassCastException - if obj cannot be compared with objects already in the set

first

public Object first()
Returns the first (by order) element in this Set.
Specified by:
first in interface SortedSet
Returns:
the first element
Throws:
NoSuchElementException - if the set is empty

headSet

public SortedSet headSet(Object to)
Returns a view of this Set including all elements less than to. The returned set is backed by the original, so changes in one appear in the other. The subset will throw an IllegalArgumentException for any attempt to access or add an element beyond the specified cutoff. The returned set does not include the endpoint; if you want inclusion, pass the successor element.
Specified by:
headSet in interface SortedSet
Parameters:
to - the (exclusive) cutoff point
Returns:
a view of the set less than the cutoff
Throws:
ClassCastException - if to is not compatible with the comparator (or is not Comparable, for natural ordering)
NullPointerException - if to is null, but the comparator does not tolerate null elements

isEmpty

public boolean isEmpty()
Returns true if this Set has size 0, false otherwise.
Specified by:
isEmpty in interface Set
isEmpty in interface Collection
Overrides:
isEmpty in interface AbstractCollection
Returns:
true if the set is empty

iterator

public Iterator iterator()
Returns in Iterator over the elements in this TreeSet, which traverses in ascending order.
Specified by:
iterator in interface Set
iterator in interface Collection
Overrides:
iterator in interface AbstractCollection
Returns:
an iterator

last

public Object last()
Returns the last (by order) element in this Set.
Specified by:
last in interface SortedSet
Returns:
the last element
Throws:
NoSuchElementException - if the set is empty

remove

public boolean remove(Object obj)
If the supplied Object is in this Set, it is removed, and true is returned; otherwise, false is returned.
Specified by:
remove in interface Set
remove in interface Collection
Overrides:
remove in interface AbstractCollection
Parameters:
obj - the Object to remove from this Set
Returns:
true if the set was modified
Throws:
ClassCastException - if obj cannot be compared to set elements

size

public int size()
Returns the number of elements in this Set
Specified by:
size in interface Set
size in interface Collection
Overrides:
size in interface AbstractCollection
Returns:
the set size

subSet

public SortedSet subSet(Object from,
                        Object to)
Returns a view of this Set including all elements greater or equal to from and less than to (a half-open interval). The returned set is backed by the original, so changes in one appear in the other. The subset will throw an IllegalArgumentException for any attempt to access or add an element beyond the specified cutoffs. The returned set includes the low endpoint but not the high; if you want to reverse this behavior on either end, pass in the successor element.
Specified by:
subSet in interface SortedSet
Parameters:
from - the (inclusive) low cutoff point
to - the (exclusive) high cutoff point
Returns:
a view of the set between the cutoffs
Throws:
ClassCastException - if either cutoff is not compatible with the comparator (or is not Comparable, for natural ordering)
NullPointerException - if from or to is null, but the comparator does not tolerate null elements
IllegalArgumentException - if from is greater than to

tailSet

public SortedSet tailSet(Object from)
Returns a view of this Set including all elements greater or equal to from. The returned set is backed by the original, so changes in one appear in the other. The subset will throw an IllegalArgumentException for any attempt to access or add an element beyond the specified cutoff. The returned set includes the endpoint; if you want to exclude it, pass in the successor element.
Specified by:
tailSet in interface SortedSet
Parameters:
from - the (inclusive) low cutoff point
Returns:
a view of the set above the cutoff
Throws:
ClassCastException - if from is not compatible with the comparator (or is not Comparable, for natural ordering)
NullPointerException - if from is null, but the comparator does not tolerate null elements

TreeSet.java -- a class providing a TreeMap-backed SortedSet Copyright (C) 1999, 2000, 2001, 2004, 2005 Free Software Foundation, Inc. This file is part of GNU Classpath. GNU Classpath is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2, or (at your option) any later version. GNU Classpath is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with GNU Classpath; see the file COPYING. If not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. Linking this library statically or dynamically with other modules is making a combined work based on this library. Thus, the terms and conditions of the GNU General Public License cover the whole combination. As a special exception, the copyright holders of this library give you permission to link this library with independent modules to produce an executable, regardless of the license terms of these independent modules, and to copy and distribute the resulting executable under terms of your choice, provided that you also meet, for each linked independent module, the terms and conditions of the license of that module. An independent module is a module which is not derived from or based on this library. If you modify this library, you may extend this exception to your version of the library, but you are not obligated to do so. If you do not wish to do so, delete this exception statement from your version.