Set API ¶Depending on which constructor is used,
nullT and isNullT may or may not be defined for a Set.
If one of these is defined the other will be too.
In some methods below, an error will be thrown unless nullT can be returned to indicate an
element is not present.
The Set_T structure has the following methods:
int size()returns the number of distinct elements in the set.
bool empty()returns true iff size() == 0.
bool contains(T item)returns true if item (or an equivalent item) is present in the set.
If isNullT is defined and isNullT(item) is true, this method
always returns false.
bool add(T item)adds item to the set if it is not already present.
This method does nothing if isNullT(item) is defined and true,
or if item or an equivalent item is already present.
The return value is true iff item was added.
void add(Iterable_T other)adds the elements from other to the set.
This method violates the principle of reversibility.
bool delete(T item)removes item from the set if it is present, otherwise does nothing.
This method does nothing if isNullT(item) is defined and true.
The return value is true iff the set was modified.
void delete(Iterable_T other)removes the elements from other from the set.
Elements of other that are not in the set are ignored.
This method violates the principle of reversibility.
Iter_T operator iter()returns an iterator over the elements of the set. It allows a set
s to be used in a range-based for loop:
for (T item : s) {<statements>}
If an item is deleted or a new item is inserted, then any iterators created before that change are undermined and may behave unpredictably. The current implementations attempt to throw errors if an iterator is used after being undermined, but this behavior is not guaranteed and might be removed in future versions for performance reasons.
Set_T newEmpty()returns a new empty set with the same nullT, isNullT,
equivalence relation, and (if applicable) ordering as the current set.
Implementors of new set types should implement this method, otherwise
the binary operators that are supposed to return a set will instead
throw errors.
The preceeding methods are sufficient assuming that equivalent elements are
interchangeable. However, on rare occasions, one may care which of two
equivalent elements is in the set. For example, if the set was configured such
that two ordered pairs are considered equivalent if they have the same first
element, then the methods above would provide no way to look up a pair based on
its first element. For this situation, the Set_T API provides the
following methods:
T get(T item)returns the item in the set equivalent to item. If no such item exists,
nullT is returned; if nullT is not defined,
an error is thrown.
T push(T item)inserts item into the set even if it is equivalent to an
existing item. If item is equivalent to an existing item, the
replaced item is returned; otherwise nullT is returned (unless
nullT is not defined, in which case an error is thrown). If
isNullT(item) is true,
the set is not modified and nullT is returned.
The push method
can be used to add a new item to the set, but only if nullT is defined.
T extract(T item)removes and returns an item in the set equivalent to item.
If no such item exists, nullT is returned; if
nullT is not defined, an error is thrown. If
isNullT(item) is true,
the set is not modified and nullT is returned.
In addition to the methods above, there are a number of autounraveled functions that deal with sets.
Iterable_T operator cast(Set_T set)implicitly casts a set to an iterable so that it can be passed as a parameter
to utilities like zip or enumerate.
bool operator <= (Set_T a, Set_T b)returns true if a is a subset of b.
bool operator >= (Set_T a, Set_T b)returns true if b is a subset of a.
bool operator == (Set_T a, Set_T b)returns true if a and b are subsets of each other.
bool operator != (Set_T a, Set_T b)returns true if either a or b contains an element not in the other.
bool sameElementsInOrder(Set_T a, Set_T b)returns true if iterating over a and b produces the same elements in the same order.
The following operators leave their two arguments unchanged; the
result is initialized by calling the newEmpty() method of the first
argument to produce a new set with the same underlying implementation as
the first argument.
Set_T operator + (Set_T a, Iterable_T b)returns the union of a and b.
Set_T operator - (Set_T a, Set_T b)returns a new set containing the elements of a that are not in b.
Set_T operator & (Set_T a, Set_T b)returns the intersection of a and b.
Set_T operator ^ (Set_T a, Set_T b) ¶returns the symmetric difference of a and b, in other words, the
set of all items in exactly one of a,b.
Note:
While it is possible to use the += and -= operators, they may not
function as expected. In particular, these two operators will
construct a new set, rather than modifying the set in place.
For most purposes, the add(Iterable_T) and delete(Iterable_T) methods are
preferred.