public final class FTreeSet<Elt> extends AbstractFSet<Elt> implements SortedSet<Elt>, Comparable<FTreeSet<Elt>>, Serializable
SortedSet
, the elements must either implement Comparable
, or must be acceptable to a Comparator
which is
supplied to the FTreeSet
constructor.
Time costs: isEmpty
, size
, and arb
take
O(1) (constant) time. contains
, with
,
less
, first
, last
, subSet
,
headSet
, and tailSet
take O(log n) time.
union
, intersection
, difference
,
isSubset
, isSuperset
, and equals
take O(n)
(linear) time if the other set involved is also a FTreeSet
and
uses the same ordering; otherwise, they take O(n log n) time.
compareTo
(called, for instance, if this set is an element in a
containing FTreeSet
) takes O(n) (linear) time.
Space costs: FTreeSet
uses a heterogeneous binary tree
structure with boundedlength arrays at the leaves. It uses much less space than
traditional homogeneous binary trees; typical space consumption is roughly twice
that of a plain array, or even less.
FTreeSet
is declared as implementing SortedSet
.
However, there are some subtle semantic differences which the user should be
aware of; FTreeSet
does not perfectly fulfill the contract of
SortedSet
.
First, unlike SortedSet
, FTreeSet
does not
require the comparison to be consistent with equals
in order for it
to fulfill the contract of the Set
interface. In cases where the
set contains equivalent elements (elements for which equals
returns false
but for which the comparison method returns 0), there
is obviously no guarantee as to the order in which the iterator will return those
elements. Otherwise, the iterator returns the elements in order according to the
comparison. Although the ordering does not need to be consistent with
equals
, it does need to be selfconsistent: any two elements for
which it returns 0 must compare the same way against all other elements.
(Mathematically, it must be transitive, and the quotient must be an equivalence
relation. See Comparable
.) Also, the comparison must not be
finer than equals
: for any two elements on which
equals
returns true
, the comparison must return 0.
The second difference concerns exception behavior. SortedSet.subSet(E, E)
,
for instance, is documented to throw IllegalArgumentException
if its
bounds arguments are in the wrong order, or if this set is the result of a
previous subSet
operation and the new bounds are not within the
interval supplied to that previous operation. We feel that operations of a
general interface like SortedSet
should throw exceptions only in
truly erroneous cases, not simply as a debugging aid that may be useful to an
occasional client at the expense of cluttering all the implementations of the
interface. So with this class, subSet
and the related methods
headSet
and tailSet
do not throw
IllegalArgumentException
.
FTreeSet
accepts the null element; for ordering purposes,
it precedes all other elements.
Although FTreeSet
functions correctly in the presence of
equivalent but unequal elements, it does so with some loss of efficiency. As
long as these are rare, however, the cost will not be significant.
FTreeSet
implements Serializable
; an instance
of it is serializable provided that all elements it contains, and the
Comparator
it uses if any, are serializable.
FSet
,
FHashSet
,
Comparable
,
Comparator
,
Serialized FormConstructor and Description 

FTreeSet()
Constructs an empty
FTreeSet that uses the natural ordering
of the elements. 
FTreeSet(Collection<? extends Elt> coll)
Constructs a
FTreeSet containing the same elements as
coll , and that uses the natural ordering of the elements. 
FTreeSet(Collection<? extends Elt> coll,
Comparator<? super Elt> c)
Constructs a
FTreeSet containing the same elements as
coll , and that uses the supplied Comparator to
compare elements. 
FTreeSet(Comparator<? super Elt> c)
Constructs an empty
FTreeSet that uses the supplied
Comparator to compare elements. 
FTreeSet(Comparator<? super Elt> c,
T... elts)
Constructs a
FTreeSet whose elements are the components of
ary , and which uses the supplied Comparator to
compare elements. 
FTreeSet(Elt elt)
Constructs a
FTreeSet containing only elt , and
that uses the natural ordering of the elements. 
FTreeSet(Elt elt,
Comparator<? super Elt> c)
Constructs a
FTreeSet containing only elt , and
that uses the supplied Comparator to compare elements. 
FTreeSet(SortedSet<Elt> set)
Constructs a
FTreeSet containing the same elements as
set , and which uses the same ordering (natural ordering, or the
same Comparator ) as Set . 
FTreeSet(T... elts)
Constructs a
FTreeSet whose elements are the components of
ary , and which uses natural ordering to compare elements. 
Modifier and Type  Method and Description 

Elt 
arb()
Returns an arbitrary element of the set, if the set is nonempty.

Comparator<Elt> 
comparator() 
int 
compareTo(FTreeSet<Elt> obj)
See the documentation for
Comparable.compareTo(T) . 
boolean 
contains(Object elt) 
FTreeSet<Elt> 
difference(Collection<? extends Elt> coll)
Returns the difference of this set less
coll . 
static <Elt> FTreeSet<Elt> 
emptySet()
Returns an empty
FTreeSet that uses the natural ordering of the
elements. 
static <Elt> FTreeSet<Elt> 
emptySet(Comparator<? super Elt> comp)
Return an empty FTreeSet that uses the supplied comparator.

boolean 
equals(Object obj) 
Elt 
first() 
int 
hashCode() 
SortedSet<Elt> 
headSet(Elt toElement)
Returns a set containing the elements of this set less than
toElement . 
FTreeSet<Elt> 
intersection(Collection<? extends Elt> coll)
Returns the intersection of this set with
coll . 
boolean 
isEmpty() 
boolean 
isSubset(Collection<?> coll)
Returns true if this set is a subset of
coll . 
boolean 
isSuperset(Collection<?> coll)
Returns true if this set is a superset of
coll . 
Iterator<Elt> 
iterator() 
Elt 
last() 
FTreeSet<Elt> 
less(Elt elt)
Removes
elt , returning a (possibly) new set. 
int 
size() 
SortedSet<Elt> 
subSet(Elt fromElement,
Elt toElement)
Returns a set containing the elements of this set greater than or equal (or
equivalent) to
fromElement and less than toElement . 
SortedSet<Elt> 
tailSet(Elt fromElement)
Returns a set containing the elements of this set greater than or equal (or
equivalent) to
fromElement . 
FTreeSet<Elt> 
union(Collection<? extends Elt> coll)
Returns the union of this set with
coll . 
FTreeSet<Elt> 
with(Elt elt)
Adds
elt , returning a (possibly) new set. 
add, addAll, clear, remove, removeAll, retainAll
containsAll, toArray, toArray, toString
public FTreeSet()
FTreeSet
that uses the natural ordering
of the elements.public FTreeSet(Elt elt)
FTreeSet
containing only elt
, and
that uses the natural ordering of the elements.public FTreeSet(Comparator<? super Elt> c)
FTreeSet
that uses the supplied
Comparator
to compare elements.c
 the comparatorpublic FTreeSet(Elt elt, Comparator<? super Elt> c)
FTreeSet
containing only elt
, and
that uses the supplied Comparator
to compare elements.public FTreeSet(Collection<? extends Elt> coll)
FTreeSet
containing the same elements as
coll
, and that uses the natural ordering of the elements.coll
 the collection to use the elements ofpublic FTreeSet(Collection<? extends Elt> coll, Comparator<? super Elt> c)
FTreeSet
containing the same elements as
coll
, and that uses the supplied Comparator
to
compare elements.coll
 the collection to use the elements ofc
 the comparatorpublic FTreeSet(SortedSet<Elt> set)
FTreeSet
containing the same elements as
set
, and which uses the same ordering (natural ordering, or the
same Comparator
) as Set
.set
 the set to use the elements and ordering ofpublic FTreeSet(T... elts)
FTreeSet
whose elements are the components of
ary
, and which uses natural ordering to compare elements. That
is, the elements are ary[0]
, ary[1]
, etc. (So, if
ary
is multidimensional, the elements of the set will be the
inner arrays, not the objects which are ultimately found after multiple
levels of indexing.)T
 type of the array elements; extends Elt
elts
 the elements (as an argument list or array)public FTreeSet(Comparator<? super Elt> c, T... elts)
FTreeSet
whose elements are the components of
ary
, and which uses the supplied Comparator
to
compare elements. That is, the elements are ary[0]
,
ary[1]
, etc. (So, if ary
is multidimensional, the
elements of the set will be the inner arrays, not the objects which are
ultimately found after multiple levels of indexing.)
Note that the comparator argument must come first; this is inconsistent with
the argument ordering of the other constructors.T
 type of the array elements; extends Elt
c
 the comparatorelts
 the elements (as an argument list or array)public static <Elt> FTreeSet<Elt> emptySet()
FTreeSet
that uses the natural ordering of the
elements. Slightly more efficient than calling the constructor, because it returns
a canonical instance.public static <Elt> FTreeSet<Elt> emptySet(Comparator<? super Elt> comp)
public boolean isEmpty()
isEmpty
in interface Collection<Elt>
isEmpty
in interface Set<Elt>
isEmpty
in class AbstractCollection<Elt>
public int size()
size
in interface Collection<Elt>
size
in interface Set<Elt>
size
in class AbstractCollection<Elt>
public Elt arb()
FSet
public boolean contains(Object elt)
contains
in interface Collection<Elt>
contains
in interface Set<Elt>
contains
in class AbstractCollection<Elt>
public FTreeSet<Elt> with(Elt elt)
FSet
elt
, returning a (possibly) new set. More formally, if the
set already contains an element e
such that (elt == null ?
e == null : elt.equals(e)), returns this
or a set equal to it;
otherwise returns a new set containing elt
as well as all the
elements of this set.

less
public FTreeSet<Elt> less(Elt elt)
Description copied from interface: FSet
Removes elt
, returning a (possibly) new set. More formally, if
the set does not already contain an element e
such that
(elt == null ? e == null : elt.equals(e))
, returns
this
or a set equal to it; otherwise returns a new set
containing all elements of this set except e
.

union
public FTreeSet<Elt> union(Collection<? extends Elt> coll)
Returns the union of this set with coll
. That is, returns a set
containing all elements that are in either this set, or coll
, or
both. The returned set is of the same class as this set and uses the same
ordering.
This operation runs in O(n) (linear) time if coll
is also a
FTreeSet
and uses the same ordering as this set; otherwise it
runs in O(n log n) time.
 Specified by:
union
in interface FSet<Elt>
 Parameters:
coll
 the set to take the union with
 Returns:
 the union of the two sets
 Throws:
ClassCastException
 if coll
contains elements whose class is
incompatible with this set or its Comparator

intersection
public FTreeSet<Elt> intersection(Collection<? extends Elt> coll)
Returns the intersection of this set with coll
. That is, returns a
set containing all elements that are in both this set and coll
.
The returned set is of the same class as this set and uses the same ordering.
This operation runs in O(n) (linear) time if coll
is also a
FTreeSet
and uses the same ordering as this set; otherwise it
runs in O(n log n) time.
 Specified by:
intersection
in interface FSet<Elt>
 Parameters:
coll
 the set to take the intersection with
 Returns:
 the intersection of the two sets
 Throws:
ClassCastException
 if elements of this set are incompatible with
coll
or its comparator, or conversely

difference
public FTreeSet<Elt> difference(Collection<? extends Elt> coll)
Returns the difference of this set less coll
. That is, returns a
set containing all elements that are in this set and not in coll
.
The returned set is of the same class as this set and uses the same ordering.
This operation runs in O(n) (linear) time if coll
is also a
FTreeSet
and uses the same ordering as this set; otherwise it
runs in O(n log n) time.
 Specified by:
difference
in interface FSet<Elt>
 Parameters:
coll
 the set to take the difference with
 Returns:
 the difference of the two sets (this set less
coll
)
 Throws:
ClassCastException
 if elements of this set are incompatible with
coll
or its comparator, or conversely

compareTo
public int compareTo(FTreeSet<Elt> obj)
See the documentation for Comparable.compareTo(T)
.
This method throws ClassCastException
even if
obj
is another FTreeSet
, if the two sets do not
use the same ordering for their elements (either natural ordering, or the
same Comparator
).
 Specified by:
compareTo
in interface Comparable<FTreeSet<Elt>>

equals
public boolean equals(Object obj)
 Specified by:
equals
in interface Collection<Elt>
 Specified by:
equals
in interface Set<Elt>
 Overrides:
equals
in class AbstractSet<Elt>

isSubset
public boolean isSubset(Collection<?> coll)
Returns true if this set is a subset of coll
. That is, returns
true if coll
contains all elements of this set. The inclusion need
not be proper; that is, this method returns true if the two sets are equal.
This operation runs in O(n) (linear) time if coll
is also a
FTreeSet
and uses the same ordering as this set; otherwise it
runs in O(n log n) time.
 Specified by:
isSubset
in interface FSet<Elt>
 Parameters:
coll
 the collection to compare against
 Returns:
 whether this set is a subset of
coll
 Throws:
ClassCastException
 if elements of this set are incompatible with
coll
or its comparator, or conversely

isSuperset
public boolean isSuperset(Collection<?> coll)
Returns true if this set is a superset of coll
. That is, returns
true if this set contains all elements of coll
. The inclusion need
not be proper; that is, this method returns true if the two sets are equal.
(Synonym for containsAll
.)
This operation runs in O(n) (linear) time if coll
is also a
FTreeSet
and uses the same ordering as this set; otherwise it
runs in O(n log n) time.
 Specified by:
isSuperset
in interface FSet<Elt>
 Parameters:
coll
 the collection to compare against
 Returns:
 whether this set is a superset of
coll
 Throws:
ClassCastException
 if elements of this set are incompatible with
coll
or its comparator, or conversely

hashCode
public int hashCode()
 Specified by:
hashCode
in interface Collection<Elt>
 Specified by:
hashCode
in interface Set<Elt>
 Overrides:
hashCode
in class AbstractSet<Elt>

comparator
public Comparator<Elt> comparator()
 Specified by:
comparator
in interface SortedSet<Elt>

subSet
public SortedSet<Elt> subSet(Elt fromElement,
Elt toElement)
Returns a set containing the elements of this set greater than or equal (or
equivalent) to fromElement
and less than toElement
.
Contrary to the documentation for SortedSet.subSet(E, E)
, this
never throws IllegalArgumentException
, no matter what values are
supplied for fromElement
and toElement
.
 Specified by:
subSet
in interface SortedSet<Elt>
 Parameters:
fromElement
 inclusive lower boundtoElement
 exclusive upper bound
 Returns:
 the new set
 Throws:
ClassCastException
 if fromElement
or
toElement
cannot be compared to each other or to the
elements in the set

headSet
public SortedSet<Elt> headSet(Elt toElement)
Returns a set containing the elements of this set less than
toElement
. Contrary to the documentation for SortedSet.headSet(E)
, this never throws IllegalArgumentException
,
no matter what value is supplied for toElement
.
 Specified by:
headSet
in interface SortedSet<Elt>
 Parameters:
toElement
 exclusive upper bound
 Returns:
 the new set
 Throws:
ClassCastException
 if toElement
cannot be compared to
the elements in the set

tailSet
public SortedSet<Elt> tailSet(Elt fromElement)
Returns a set containing the elements of this set greater than or equal (or
equivalent) to fromElement
. Contrary to the documentation for
SortedSet.tailSet(E)
, this never throws
IllegalArgumentException
, no matter what value is supplied for
fromElement
.
 Specified by:
tailSet
in interface SortedSet<Elt>
 Parameters:
fromElement
 inclusive lower bound
 Returns:
 the new set
 Throws:
ClassCastException
 if fromElement
cannot be compared
to the elements in the set