Set

Usage

use Set;

or

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 : serializable

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 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. Note that the parSafe mode is currently unstable and will eventually be replaced by a standalone parallel-safe set type.

type eltType

The type of the elements contained in this set.

param parSafe = false

Warning

‘set.parSafe’ is unstable and is expected to be replaced by a separate set type in the future

If true, this set will perform parallel safe operations.

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.

proc init(type eltType, resizeThreshold = defaultHashTableResizeThreshold, initialCapacity = 16)

Initializes an empty set containing elements of the given type.

Arguments:
  • eltType – The type of the elements of this set.

  • resizeThreshold – Fractional value that specifies how full this map can be before requesting additional memory.

  • initialCapacity – Integer value that specifies starting map size. The map can hold at least this many values before attempting to resize.

proc init(type eltType, param parSafe, resizeThreshold = defaultHashTableResizeThreshold, initialCapacity = 16)

Warning

‘set.parSafe’ is unstable and is expected to be replaced by a separate set type in the future

proc init(type eltType, iterable, resizeThreshold = defaultHashTableResizeThreshold, initialCapacity = 16)  where canResolveMethod(iterable, "these")

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.

Arguments:
  • eltType – The type of the elements of this set.

  • iterable – A collection of elements to add to this set.

  • resizeThreshold – Fractional value that specifies how full this map can be before requesting additional memory.

  • initialCapacity – Integer value that specifies starting map size. The map can hold at least this many values before attempting to resize.

proc init(type eltType, iterable, param parSafe, resizeThreshold = defaultHashTableResizeThreshold, initialCapacity = 16)  where canResolveMethod(iterable, "these")

Warning

‘set.parSafe’ is unstable and is expected to be replaced by a separate set type in the future

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.

Arguments:

other – A set to initialize this set with.

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.

Arguments:

element – The element to add to this set.

proc contains(const ref element: eltType) : bool

Returns true if the given element is a member of this set, and false otherwise.

Arguments:

element – The element to test for membership.

Returns:

Whether or not the given element is a member of this set.

Return type:

bool

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.

Arguments:

other – The set to compare against.

Returns:

Whether or not this set and other are disjoint.

Return type:

bool

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.

Arguments:

element – The element to remove.

Returns:

Whether or not an element equal to element was removed.

Return type:

bool

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.

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.

proc serialize(writer: fileWriter(?), ref serializer) throws

Write the contents of this set to a fileWriter.

Arguments:
  • writer – A fileWriter to write to.

  • serializer – The serializer to use when writing.

proc isEmpty() : bool

Returns true if this set contains zero elements.

Returns:

true if this set is empty.

Return type:

bool

proc size

The current number of elements contained in this set.

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.

Returns:

An array containing a copy of each of the elements in this set.

Return type:

[] eltType

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.

Arguments:
  • lhs – The set to assign to.

  • rhs – The set to assign from.

operator set.|(const ref a: set(?t, ?), const ref b: set(t, ?))

Return a new set that contains the union of two sets.

Arguments:
  • a – A set to take the union of.

  • b – A set to take the union of.

Returns:

A new set containing the union between a and b.

operator set.|=(ref lhs: set(?t, ?), const ref rhs: set(t, ?))

Add to the set lhs all the elements of rhs.

Arguments:
  • lhs – A set to take the union of and then assign to.

  • rhs – A set to take the union of.

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.

Arguments:
  • a – A set to take the union of.

  • b – A set to take the union of.

Returns:

A new set containing the union between a and b.

operator set.+=(ref lhs: set(?t, ?), const ref rhs: set(t, ?))

Add to the set lhs all the elements of rhs.

Arguments:
  • lhs – A set to take the union of and then assign to.

  • rhs – A set to take the union of.

operator set.-(const ref a: set(?t, ?), const ref b: set(t, ?))

Return a new set that contains the difference of two sets.

Arguments:
  • a – A set to take the difference of.

  • b – A set to take the difference of.

Returns:

A new set containing the difference between a and b.

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.

Arguments:
  • lhs – A set to take the difference of and then assign to.

  • rhs – A set to take the difference of.

operator set.&(const ref a: set(?t, ?), const ref b: set(t, ?))

Return a new set that contains the intersection of two sets.

Arguments:
  • a – A set to take the intersection of.

  • b – A set to take the intersection of.

Returns:

A new set containing the intersection of a and b.

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.

Arguments:
  • lhs – A set to take the intersection of and then assign to.

  • rhs – A set to take the intersection of.

operator set.^(const ref a: set(?t, ?), const ref b: set(t, ?))

Return the symmetric difference of two sets.

Arguments:
  • a – A set to take the symmetric difference of.

  • b – A set to take the symmetric difference of.

Returns:

A new set containing the symmetric difference of a and b.

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.

Arguments:
  • lhs – A set to take the symmetric difference of and then assign to.

  • rhs – A set to take the symmetric difference of.

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.

Arguments:
  • a – A set to compare.

  • b – A set to compare.

Returns:

true if two sets are equal.

Return type:

bool

operator set.!=(const ref a: set(?t, ?), const ref b: set(t, ?)) : bool

Return true if the sets a and b are not equal.

Arguments:
  • a – A set to compare.

  • b – A set to compare.

Returns:

true if two sets are not equal.

Return type:

bool

operator set.<(const ref a: set(?t, ?), const ref b: set(t, ?)) : bool

Return true if a is a proper subset of b.

Arguments:
  • a – A set to compare.

  • b – A set to compare.

Returns:

true if a is a proper subset of b.

Return type:

bool

operator set.<=(const ref a: set(?t, ?), const ref b: set(t, ?)) : bool

Return true if a is a subset of b.

Arguments:
  • a – A set to compare.

  • b – A set to compare.

Returns:

true if a is a subset of b.

Return type:

bool

operator set.>(const ref a: set(?t, ?), const ref b: set(t, ?)) : bool

Return true if a is a proper superset of b.

Arguments:
  • a – A set to compare.

  • b – A set to compare.

Returns:

true if a is a proper superset of b.

Return type:

bool

operator set.>=(const ref a: set(?t, ?), const ref b: set(t, ?)) : bool

Return true if a is a superset of b.

Arguments:
  • a – A set to compare.

  • b – A set to compare.

Returns:

true if a is a superset of b.

Return type:

bool