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 Form| Constructor 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, tailSetequals, hashCode, removeAllcontainsAll, retainAll, toArray, toArray, toStringfinalize, getClass, notify, notifyAll, wait, wait, waitcontainsAll, equals, hashCode, removeAll, retainAll, toArray, toArrayparallelStream, removeIf, streampublic 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)