E
- the type of the elements of the setpublic class OrderedSet<E extends Comparable<E>> extends TreeSet<E>
TreeSet
class and is based
on a TreeMap
.
The elements are ordered using their natural ordering, or by a
Comparator provided at set creation time, depending on which constructor is used.
This implementation provides guaranteed log(n) time cost for the basic operations
(add, remove and contains). Note that the ordering maintained by a set
(whether or not an explicit comparator is provided) must be consistent with
equals if it is to correctly implement the Set interface.
(See Comparable
or Comparator
for a
precise definition of "consistent with equals.")
This is so because the Set
interface is defined in terms of the
equals
operation, but an OrderedSet
instance performs
all element comparisons using its compareTo
(or compare
)
method, so two elements that are deemed equal by this method are, from the
standpoint of the set, equal. The behavior of a set is well-defined
even if its ordering is inconsistent with equals; it just fails to obey the
general contract of the Set
interface.
TreeSet
.MathSet
,
TreeSet
,
Serialized FormConstructor and Description |
---|
OrderedSet()
Constructs a new, empty ordered set, sorted according to the
natural ordering of its elements.
|
OrderedSet(Collection<? extends E> c)
Constructs a new ordered set containing the elements in the specified
collection, sorted according to the natural ordering of its
elements.
|
OrderedSet(Comparator<? super E> comparator)
Constructs a new, empty ordered set, sorted according to the specified
comparator.
|
OrderedSet(E element)
Constructs a new set from the input element.
|
OrderedSet(E[] elements)
Constructs a new set from the input array.
|
Modifier and Type | Method and Description |
---|---|
OrderedSet<E> |
copy()
Creates and returns a clone copy of this set.
|
static <E extends Comparable<E>> |
emptySet()
Returns the empty set.
|
static <E extends Comparable<E>> |
emptySet(OrderedSet<E> set)
Returns the empty set.
|
OrderedSet<E> |
intersect(ArrayList<? extends SortedSet<E>> sets)
Returns the intersection of this set and the specified set list.
|
OrderedSet<E> |
intersect(SortedSet<E> set)
Returns the intersection of this set and the specified set.
|
OrderedSet<E> |
minus(E element)
Returns the set difference of this set minus the specified element.
|
OrderedSet<E> |
minus(SortedSet<E> minuend)
Returns the set difference of this set minus the specified minuend.
|
ArrayList<MathSet<OrderedSet<E>>> |
partitions()
Returns a list of partitions of this set.
|
static <E extends Comparable<E>> |
partitions(E[] set)
Returns a list of partitions of the specified set,
each partition encoded as an array
partition[] meaning that
set element i is in subset partition[i] . |
static <E extends Comparable<E>> |
partitions(OrderedSet<E> set)
Returns a list of partitions of the specified set.
|
ArrayList<OrderedSet<E>> |
subsets(int k)
Returns the k-element subsets of this set,
i.e., each of its k-element combination, stored in an array list.
|
static <E extends Comparable<E>> |
subsets(SortedSet<E> set,
int k)
Returns the k-element subsets of a set s,
i.e., each k-element combination of s,
stored in an array list.
|
OrderedSet<E> |
unify(ArrayList<? extends SortedSet<E>> sets)
Returns the union of this set and the specified set list.
|
OrderedSet<E> |
unify(SortedSet<E> set)
Returns the union of this set and the specified set.
|
add, addAll, ceiling, clear, clone, comparator, contains, descendingIterator, descendingSet, first, floor, headSet, headSet, higher, isEmpty, iterator, last, lower, pollFirst, pollLast, remove, size, spliterator, subSet, subSet, tailSet, tailSet
equals, hashCode, removeAll
containsAll, retainAll, toArray, toArray, toString
finalize, getClass, notify, notifyAll, wait, wait, wait
containsAll, equals, hashCode, removeAll, retainAll, toArray, toArray
parallelStream, removeIf, stream
public OrderedSet()
Comparable
interface.
Furthermore, all such elements must be mutually
comparable, i.e., e1.compareTo(e2)
must not throw a
ClassCastException
for any elements e1
and
e2
in the set. If the user attempts to add an element
to the set that violates this constraint (for example, the user
attempts to add a string element to a set whose elements are
integers), the add
call will throw a
ClassCastException
.public OrderedSet(Comparator<? super E> comparator)
comparator.compare(e1,
e2)
must not throw a ClassCastException
for any elements
e1
and e2
in the set. If the user attempts to add
an element to the set that violates this constraint, the
add
call will throw a ClassCastException
.comparator
- the comparator that will be used to order this set.
If null
, the natural ordering of the
elements will be used.public OrderedSet(Collection<? extends E> c)
Comparable
interface. Furthermore, all such elements must be
mutually comparable: e1.compareTo(e2)
must not throw a
ClassCastException
for any elements e1
and
e2
in the set.c
- collection whose elements will comprise the new setClassCastException
- if the elements in c
are
not Comparable
, or are not mutually comparableNullPointerException
- if the specified collection is nullpublic OrderedSet(E[] elements)
SortedSet
.
The backing HashMap instance has the
initial capacity of the array size and the default load factor (0.75).elements
- array containing the elementsClassCastException
- if the elements in c
are
not Comparable
, or are not mutually comparablepublic OrderedSet(E element)
OrderedSet<Integer> s = new OrderedSet<>(new Integer(2));
.element
- an elementpublic OrderedSet<E> copy()
public OrderedSet<E> minus(SortedSet<E> minuend)
minuend
- the set to be subtracted from this setpublic OrderedSet<E> minus(E element)
element
- the set to be subtracted from this setpublic OrderedSet<E> intersect(SortedSet<E> set)
E
.set
- a setpublic OrderedSet<E> intersect(ArrayList<? extends SortedSet<E>> sets)
OrderedSet
or being of OrderedSet
itself,
and each set is expected to contain only elements of
class E
.sets
- a list of setspublic OrderedSet<E> unify(SortedSet<E> set)
E
.set
- a setpublic OrderedSet<E> unify(ArrayList<? extends SortedSet<E>> sets)
OrderedSet
or being of OrderedSet
itself,
and each set is expected to contain only elements of
class E
.sets
- a list of setspublic ArrayList<OrderedSet<E>> subsets(int k)
k
- an integerpublic ArrayList<MathSet<OrderedSet<E>>> partitions()
{{a}, {b}, {c}},
{{a, b}, {c}}, {{a, c}, {b}}, {{a}, {c, b}},
{{a, b, c}}.
The running time of this algorithm with respect to the size n of the set is very bad, its time complexity is estimated as O(nn). For n ≤ 10 it requires less than 2 sec on a 2 GHz dual core processor, but for n ≤ 11 the running time is about 10 seconds and explodes for greater n. The number of partitions of a set of n is given by the n-th Bell number Bn, see http://oeis.org/A000110.public static <E extends Comparable<E>> OrderedSet<E> emptySet()
OrderedSet<String> s = OrderedSet.emptySet();Implementation note: Implementations of this method need not create a separate OrderedSet object for each call. If an explicit variable for the empty set is not desired, the method
emptySet(OrderedSet)
may be used..E
- type of elements of this setemptySet(OrderedSet)
,
Collections.emptySet()
public static <E extends Comparable<E>> OrderedSet<E> emptySet(OrderedSet<E> set)
OrderedSet.emptySet(new OrderedSet<String>());This method is appropriate if an explicit variable for the empty set is not desired.
E
- type of elements of this setset
- a setemptySet()
public static <E extends Comparable<E>> ArrayList<OrderedSet<E>> subsets(SortedSet<E> set, int k)
E
- type of elements of this setset
- a setk
- an integerpublic static <E extends Comparable<E>> ArrayList<MathSet<OrderedSet<E>>> partitions(OrderedSet<E> set)
{{a}, {b}, {c}},
{{a, b}, {c}}, {{a, c}, {b}}, {{a}, {c, b}},
{{a, b, c}}.
The running time of this algorithm with respect to the size n of the set is very bad, its time complexity is estimated as O(nn). For n ≤ 10 it requires less than 2 sec on a 2 GHz dual core processor, but for n ≤ 12 the running time is about 10 seconds and explodes for greater n. The number of partitions of a set of n is given by the n-th Bell number Bn, see http://oeis.org/A000110.E
- the type of the elements of the setset
- a setpublic static <E extends Comparable<E>> ArrayList<int[]> partitions(E[] set)
partition[]
meaning that
set element i
is in subset partition[i]
.
In general, a partition of a set is a collection of disjoint subsets whose union equals
the set. For instance, the set S = {a, b, c}
has the five partitions
{{a}, {b}, {c}},
{{a, b}, {c}}, {{a, c}, {b}}, {{a}, {c, b}},
{{a, b, c}}.
The running time of this algorithm with respect to the size n of the set is very bad, its time complexity is estimated as O(nn). For n ≤ 10 it requires less than 2 sec on a 2 GHz dual core processor, but for n ≤ 12 the running time is about 10 seconds and explodes for greater n. The number of partitions of a set of n is given by the n-th Bell number Bn, see http://oeis.org/A000110.E
- the type of the elements of the setset
- a setpartitions(OrderedSet)