.. default-domain:: chpl
.. module:: Set
:synopsis: This module contains the implementation of Chapel's standard 'set' type.
Set
===
**Usage**
.. code-block:: chapel
use Set;
or
.. code-block:: chapel
import Set;
This module contains the implementation of Chapel's standard 'set' type.
A set is a collection of unique elements. Sets are unordered and unindexed.
The highly parallel nature of Chapel means that great care should be taken
when performing operations that may invalidate references to set elements.
Adding or removing an element from a set may invalidate references to
elements contained in the set.
All references to set elements are invalidated when the set is cleared or
deinitialized.
Sets are not parallel safe by default, but can be made parallel safe by
setting the param formal 'parSafe` to true in any set constructor. When
constructed from another set, the new set will inherit the parallel safety
mode of its originating set.
When using set operators (e.g., ``A | B``), if both sets contain elements that
are ``==`` equivalent, the element from the first argument of the operation
will always be chosen for the resultant set. This may happen if the ``==``
operator has been overloaded on the set element type, causing values of
the set type to be ``==`` equivalent, even when there may be differences
between the elements of the first argument and the elements of the second
argument.
.. record:: set
A set is a collection of unique elements. Attempting to add a duplicate
element to a set has no effect.
The set type supports a test for membership via the :proc:`contains`
method, along with free functions for calculating the union, difference,
intersection, and symmetric difference of two sets. The set type also
defines the (proper) subset and (proper) superset operations by
overloading common comparison operators.
Sets can be iterated over. The set type makes no guarantee of a consistent
iteration order.
A set can be default initialized (containing no elements), or it may be
initialized with elements that are copies of those contained by any
type that supports an iterator.
The set type is not parallel safe by default. For situations in which
such protections are desirable, parallel safety can be enabled by setting
`parSafe = true` in any set constructor. A set constructed from another
set inherits the parallel safety mode of that set by default.
.. attribute:: type eltType
The type of the elements contained in this set.
.. attribute:: param parSafe = false
If `true`, this set will perform parallel safe operations.
.. attribute:: const resizeThreshold = defaultHashTableResizeThreshold
Fractional value that specifies how full this map can be
before requesting additional memory. The default value of
0.5 means that the map will not resize until the map is more
than 50% full. The acceptable values for this argument are
between 0 and 1, exclusive, meaning (0,1). This is useful
when you would like to reduce memory impact or potentially
speed up how fast the map finds a slot. To override the
default value of 0.5, the `defaultHashTableResizeThreshold`
config flag can be set at runtime. Note that this default
affects all hash-based data structures, including
associative domains and maps.
.. method:: proc init(type eltType, param parSafe = false, resizeThreshold = defaultHashTableResizeThreshold, initialCapacity = 16)
Initializes an empty set containing elements of the given type.
:arg eltType: The type of the elements of this set.
:arg parSafe: If `true`, this set will use parallel safe operations.
:arg resizeThreshold: Fractional value that specifies how full this map
can be before requesting additional memory.
:arg initialCapacity: Integer value that specifies starting map size. The
map can hold at least this many values before
attempting to resize.
.. method:: proc init(type eltType, iterable, param parSafe = false, resizeThreshold = defaultHashTableResizeThreshold, initialCapacity = 16)
Initialize this set with a unique copy of each element contained in
`iterable`. If an element from `iterable` is already contained in this
set, it will not be added again. The formal `iterable` must be a type
with an iterator named "these" defined for it.
:arg iterable: A collection of elements to add to this set.
:arg parSafe: If `true`, this set will use parallel safe operations.
:arg resizeThreshold: Fractional value that specifies how full this map
can be before requesting additional memory.
:arg initialCapacity: Integer value that specifies starting map size. The
map can hold at least this many values before
attempting to resize.
.. method:: proc init=(const ref other: set(?t, ?p))
Initialize this set with a copy of each of the elements contained in
the set `other`. This set will inherit the `parSafe` value of the
set `other`.
:arg other: A set to initialize this set with.
.. method:: proc ref add(in element: eltType)
Add a copy of the element `element` to this set. Does nothing if this set
already contains an element equal to the value of `element`.
:arg element: The element to add to this set.
.. method:: proc contains(const ref element: eltType): bool
Returns `true` if the given element is a member of this set, and `false`
otherwise.
:arg element: The element to test for membership.
:return: Whether or not the given element is a member of this set.
:rtype: `bool`
.. method:: proc isDisjoint(const ref other: set(eltType, ?)): bool
Returns `true` if this set shares no elements in common with the set
`other`, and `false` otherwise.
.. warning::
`other` must not be modified during this call.
:arg other: The set to compare against.
:return: Whether or not this set and `other` are disjoint.
:rtype: `bool`
.. method:: proc ref remove(const ref element: eltType): bool
Attempt to remove the item from this set with a value equal to `element`.
If an element equal to `element` was removed from this set, return `true`,
else return `false` if no such value was found.
.. warning::
Removing an element from this set may invalidate existing references
to the elements contained in this set.
:arg element: The element to remove.
:return: Whether or not an element equal to `element` was removed.
:rtype: `bool`
.. method:: proc ref clear()
Clear the contents of this set.
.. warning::
Clearing the contents of this set will invalidate all existing
references to the elements contained in this set.
.. itermethod:: iter these() const ref
Iterate over the elements of this set. Yields constant references
that cannot be modified.
.. warning::
Modifying this set while iterating over it may invalidate the
references returned by an iterator and is considered undefined
behavior.
:yields: A constant reference to an element in this set.
.. method:: proc writeThis(ch: fileWriter) throws
Write the contents of this set to a channel.
:arg ch: A channel to write to.
.. method:: proc isEmpty(): bool
Returns `true` if this set contains zero elements.
:return: `true` if this set is empty.
:rtype: `bool`
.. method:: proc size
The current number of elements contained in this set.
.. method:: proc toArray(): [] eltType
Returns a new DefaultRectangular array containing a copy of each of the
elements contained in this set. The elements of the returned array are
not guaranteed to follow any particular ordering.
:return: An array containing a copy of each of the elements in this set.
:rtype: `[] eltType`
.. method:: operator set. = (ref lhs: set(?t, ?), const ref rhs: set(t, ?))
Clear the contents of the set `lhs`, then iterate through the contents of
`rhs` and add a copy of each element to `lhs`.
.. warning::
This will invalidate any references to elements previously contained in
the set `lhs`.
:arg lhs: The set to assign to.
:arg rhs: The set to assign from.
.. method:: operator set.|(const ref a: set(?t, ?), const ref b: set(t, ?))
Return a new set that contains the union of two sets.
:arg a: A set to take the union of.
:arg b: A set to take the union of.
:return: A new set containing the union between `a` and `b`.
.. method:: operator set.|=(ref lhs: set(?t, ?), const ref rhs: set(t, ?))
Add to the set `lhs` all the elements of `rhs`.
:arg lhs: A set to take the union of and then assign to.
:arg rhs: A set to take the union of.
.. method:: operator set.+(const ref a: set(?t, ?), const ref b: set(t, ?))
Return a new set that contains the union of two sets. Alias for the `|`
operator.
:arg a: A set to take the union of.
:arg b: A set to take the union of.
:return: A new set containing the union between `a` and `b`.
.. method:: operator set.+=(ref lhs: set(?t, ?), const ref rhs: set(t, ?))
Add to the set `lhs` all the elements of `rhs`.
:arg lhs: A set to take the union of and then assign to.
:arg rhs: A set to take the union of.
.. method:: operator set.-(const ref a: set(?t, ?), const ref b: set(t, ?))
Return a new set that contains the difference of two sets.
:arg a: A set to take the difference of.
:arg b: A set to take the difference of.
:return: A new set containing the difference between `a` and `b`.
.. method:: operator set.-=(ref lhs: set(?t, ?), const ref rhs: set(t, ?))
Remove from the set `lhs` the elements of `rhs`.
.. warning::
This will invalidate any references to elements previously contained in
the set `lhs`.
:arg lhs: A set to take the difference of and then assign to.
:arg rhs: A set to take the difference of.
.. method:: operator set.&(const ref a: set(?t, ?), const ref b: set(t, ?))
Return a new set that contains the intersection of two sets.
:arg a: A set to take the intersection of.
:arg b: A set to take the intersection of.
:return: A new set containing the intersection of `a` and `b`.
.. method:: operator set.&=(ref lhs: set(?t, ?), const ref rhs: set(t, ?))
Assign to the set `lhs` the set that is the intersection of `lhs` and
`rhs`.
.. warning::
This will invalidate any references to elements previously contained in
the set `lhs`.
:arg lhs: A set to take the intersection of and then assign to.
:arg rhs: A set to take the intersection of.
.. method:: operator set.^(const ref a: set(?t, ?), const ref b: set(t, ?))
Return the symmetric difference of two sets.
:arg a: A set to take the symmetric difference of.
:arg b: A set to take the symmetric difference of.
:return: A new set containing the symmetric difference of `a` and `b`.
.. method:: operator set.^=(ref lhs: set(?t, ?), const ref rhs: set(t, ?))
Assign to the set `lhs` the set that is the symmetric difference of `lhs`
and `rhs`.
.. warning::
This will invalidate any references to elements previously contained in
the set `lhs`.
:arg lhs: A set to take the symmetric difference of and then assign to.
:arg rhs: A set to take the symmetric difference of.
.. method:: operator set.==(const ref a: set(?t, ?), const ref b: set(t, ?)): bool
Return `true` if the sets `a` and `b` are equal. That is, they are the
same size and contain the same elements.
:arg a: A set to compare.
:arg b: A set to compare.
:return: `true` if two sets are equal.
:rtype: `bool`
.. method:: operator set.!=(const ref a: set(?t, ?), const ref b: set(t, ?)): bool
Return `true` if the sets `a` and `b` are not equal.
:arg a: A set to compare.
:arg b: A set to compare.
:return: `true` if two sets are not equal.
:rtype: `bool`
.. method:: operator set.<(const ref a: set(?t, ?), const ref b: set(t, ?)): bool
Return `true` if `a` is a proper subset of `b`.
:arg a: A set to compare.
:arg b: A set to compare.
:return: `true` if `a` is a proper subset of `b`.
:rtype: `bool`
.. method:: operator set.<=(const ref a: set(?t, ?), const ref b: set(t, ?)): bool
Return `true` if `a` is a subset of `b`.
:arg a: A set to compare.
:arg b: A set to compare.
:return: `true` if `a` is a subset of `b`.
:rtype: `bool`
.. method:: operator set.>(const ref a: set(?t, ?), const ref b: set(t, ?)): bool
Return `true` if `a` is a proper superset of `b`.
:arg a: A set to compare.
:arg b: A set to compare.
:return: `true` if `a` is a proper superset of `b`.
:rtype: `bool`
.. method:: operator set.>=(const ref a: set(?t, ?), const ref b: set(t, ?)): bool
Return `true` if `a` is a superset of `b`.
:arg a: A set to compare.
:arg b: A set to compare.
:return: `true` if `a` is a superset of `b`.
:rtype: `bool`