.. default-domain:: chpl .. module:: SortedSet :synopsis: Provides the 'sortedSet' type for storing sorted unique elements. SortedSet ========= **Usage** .. code-block:: chapel use SortedSet; or .. code-block:: chapel import SortedSet; Provides the 'sortedSet' type for storing sorted unique elements. An ``sortedSet`` is a collection of unique and sorted elements. The ``sortedSet`` accepts a :ref:`comparator ` to determine how elements are compared. The default comparator is `defaultComparator`. In this case, elements are stored and considered in ascending order. For example, ``these`` will yield elements in ascending order. All references to ``sortedSet`` elements are invalidated when the ``sortedSet`` is cleared or deinitialized. ``sortedSet`` is not parallel safe by default, but can be made parallel safe by setting the param formal `parSafe` to true in any ``sortedSet`` constructor. When constructed from another ``sortedSet``, the new ``sortedSet`` will inherit the parallel safety mode of its originating ``sortedSet``. .. record:: sortedSet : writeSerializable .. attribute:: type eltType The type of the elements contained in this sortedSet. .. attribute:: param parSafe = false If `true`, this sortedSet will perform parallel safe operations. .. attribute:: type comparatorType = defaultComparator.type .. method:: proc init(type eltType, param parSafe = false, type comparatorType = defaultComparator.type) Initializes an empty sortedSet containing elements of the given type. :arg eltType: The type of the elements of this sortedSet. :arg parSafe: If `true`, this sortedSet will use parallel safe operations. :arg comparatorType: The comparator type .. method:: proc init(type eltType, param parSafe = false, comparator: record) Initializes an empty sortedSet containing elements of the given type. :arg eltType: The type of the elements of this sortedSet. :arg parSafe: If `true`, this sortedSet will use parallel safe operations. :arg comparator: The comparator used to compare elements. .. method:: proc init(type eltType, iterable, param parSafe = false, comparator: record = defaultComparator) where canResolveMethod(iterable, "these") Initialize this sortedSet with a unique copy of each element contained in `iterable`. If an element from `iterable` is already contained in this sortedSet, 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 sortedSet. :arg parSafe: If `true`, this sortedSet will use parallel safe operations. :arg comparator: The comparator used to compare elements. .. method:: proc init=(const ref other: sortedSet(?t)) Initialize this sortedSet with a copy of each of the elements contained in the sortedSet `other`. This sortedSet will inherit the `parSafe` value of the sortedSet `other`. :arg other: An sortedSet to initialize this sortedSet with. .. method:: proc writeThis(ch: fileWriter) throws Write the contents of this sortedSet to a fileWriter. :arg ch: A fileWriter to write to. .. method:: proc size The current number of elements contained in this sortedSet. .. method:: proc ref add(in x: eltType) Add a copy of the element `x` to this sortedSet. Does nothing if this sortedSet already contains an element equal to the value of `x`. :arg x: The element to add to this sortedSet. .. method:: proc contains(const ref x: eltType): bool Returns `true` if the given element is a member of this sortedSet, and `false` otherwise. :arg x: The element to test for membership. :return: Whether or not the given element is a member of this sortedSet. :rtype: `bool` .. method:: proc ref remove(const ref x: eltType): bool Attempt to remove the item from this sortedSet with a value equal to `x`. If an element equal to `x` was removed from this sortedSet, return `true`, else return `false` if no such value was found. :arg x: The element to remove. :return: Whether or not an element equal to `x` was removed. :rtype: `bool` .. method:: proc ref clear() Clear the contents of this sortedSet. .. warning:: Clearing the contents of this sortedSet will invalidate all existing references to the elements contained in this sortedSet. .. method:: proc lowerBound(e: eltType): (bool, eltType) Find the first element in the sortedSet which is not less than e. Returns a tuple containing two elements: The first element is a `bool` that indicates whether there is such an element. The second element is the occurrence in the sortedSet, if there's any. :returns: a tuple containing result :rtype: `(bool, eltType)` .. method:: proc upperBound(e: eltType): (bool, eltType) Find the first element in the sortedSet which is greater than e. Returns a tuple containing two elements: The first element is a `bool` that indicates whether there is such an element. The second element is the occurrence in the sortedSet, if there's any. :returns: a tuple containing result :rtype: `(bool, eltType)` .. method:: proc predecessor(e: eltType): (bool, eltType) Find the predecessor of one element in the sortedSet. Returns a tuple containing two elements: The first element is a `bool` that indicates whether there is such an element. The second element is the occurrence in the sortedSet, if there's any. :arg e: The element to base :type e: `eltType` :returns: a tuple containing result :rtype: `(bool, eltType)` .. method:: proc successor(e: eltType): (bool, eltType) Find the successor of one element in the sortedSet. Returns a tuple containing two elements: The first element is a `bool` that indicates whether there is such an element. The second element is the occurrence in the sortedSet, if there's any. :arg e: The element to base :type e: `eltType` :returns: a tuple containing result :rtype: `(bool, eltType)` .. method:: proc kth(k: int): (bool, eltType) Find the k-th element in the sortedSet. k starts from 1. Returns a tuple containing two elements: The first element is a `bool` that indicates whether there is such an element. The second element is the occurrence in the sortedSet, if there's any. :arg k: To find k-th element :type k: `int` :returns: a tuple containing result :rtype: `(bool, eltType)` .. itermethod:: iter these() Iterate over the elements of this sortedSet. Yields constant references that cannot be modified. .. warning:: Modifying this sortedSet 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 sortedSet. .. method:: proc isDisjoint(const ref other: sortedSet(eltType, ?)): bool Returns `true` if this sortedSet shares no elements in common with the sortedSet `other`, and `false` otherwise. :arg other: The sortedSet to compare against. :return: Whether or not this sortedSet and `other` are disjoint. :rtype: `bool` .. method:: proc isIntersecting(const ref other: sortedSet(eltType, ?)): bool Returns `true` if this sortedSet and `other` have at least one element in common, and `false` otherwise. :arg other: The sortedSet to compare against. :return: Whether or not this sortedSet and `other` intersect. :rtype: `bool` .. method:: proc isEmpty(): bool Returns `true` if this sortedSet is empty (size == 0). :rtype: `bool` .. method:: proc toArray(): [] eltType Returns a new array containing a copy of each of the elements contained in this sortedSet. The array will be in order. :return: An array containing a copy of each of the elements in this sortedSet. :rtype: `[] eltType` .. method:: operator sortedSet. = (ref lhs: sortedSet(?t), rhs: sortedSet(t)) Clear the contents of this sortedSet, then extend this now empty sortedSet with the elements contained in another sortedSet. .. warning:: This will invalidate any references to elements previously contained in `lhs`. :arg lhs: The sortedSet to assign to. :arg rhs: The sortedSet to assign from. .. method:: operator sortedSet.|(const ref a: sortedSet(?t), const ref b: sortedSet(t)): sortedSet(t) Return a new sortedSet that contains the union of two sets. :arg a: An sortedSet to take the union of. :arg b: An sortedSet to take the union of. :return: A new sortedSet containing the union between `a` and `b`. :rtype: `sortedSet(?t)` .. method:: operator sortedSet.|=(ref lhs: sortedSet(?t), const ref rhs: sortedSet(t)) Add to the sortedSet `lhs` all the elements of `rhs`. :arg lhs: An sortedSet to take the union of and then assign to. :arg rhs: An sortedSet to take the union of. .. method:: operator sortedSet.+(const ref a: sortedSet(?t), const ref b: sortedSet(t)): sortedSet(t) Return a new sortedSet that contains the union of two sets. Alias for the `|` operator. :arg a: An sortedSet to take the union of. :arg b: An sortedSet to take the union of. :return: A new sortedSet containing the union between `a` and `b`. :rtype: `sortedSet(?t)` .. method:: operator sortedSet.+=(ref lhs: sortedSet(?t), const ref rhs: sortedSet(t)) Add to the sortedSet `lhs` all the elements of `rhs`. :arg lhs: An sortedSet to take the union of and then assign to. :arg rhs: An sortedSet to take the union of. .. method:: operator sortedSet.-(const ref a: sortedSet(?t), const ref b: sortedSet(t)): sortedSet(t) Return a new sortedSet that contains the difference of two sets. :arg a: An sortedSet to take the difference of. :arg b: An sortedSet to take the difference of. :return: A new sortedSet containing the difference between `a` and `b`. :rtype: `sortedSet(t)` .. method:: operator sortedSet.-=(ref lhs: sortedSet(?t), const ref rhs: sortedSet(t)) Remove from the sortedSet `lhs` the elements of `rhs`. .. warning:: This will invalidate any references to elements previously contained in the sortedSet `lhs`. :arg lhs: An sortedSet to take the difference of and then assign to. :arg rhs: An sortedSet to take the difference of. .. method:: operator sortedSet.&(const ref a: sortedSet(?t), const ref b: sortedSet(t)): sortedSet(t) Return a new sortedSet that contains the intersection of two sets. :arg a: An sortedSet to take the intersection of. :arg b: An sortedSet to take the intersection of. :return: A new sortedSet containing the intersection of `a` and `b`. :rtype: `sortedSet(t)` .. method:: operator sortedSet.&=(ref lhs: sortedSet(?t, ?), const ref rhs: sortedSet(t, ?)) Assign to the sortedSet `lhs` the sortedSet that is the intersection of `lhs` and `rhs`. .. warning:: This will invalidate any references to elements previously contained in the sortedSet `lhs`. :arg lhs: An sortedSet to take the intersection of and then assign to. :arg rhs: An sortedSet to take the intersection of. .. method:: operator sortedSet.^(const ref a: sortedSet(?t), const ref b: sortedSet(t)): sortedSet(t) Return the symmetric difference of two sets. :arg a: An sortedSet to take the symmetric difference of. :arg b: An sortedSet to take the symmetric difference of. :return: A new sortedSet containing the symmetric difference of `a` and `b`. :rtype: `sortedSet(?t)` .. method:: operator sortedSet.^=(ref lhs: sortedSet(?t), const ref rhs: sortedSet(t)) Assign to the sortedSet `lhs` the sortedSet that is the symmetric difference of `lhs` and `rhs`. .. warning:: This will invalidate any references to elements previously contained in the sortedSet `lhs`. :arg lhs: An sortedSet to take the symmetric difference of and then assign to. :arg rhs: An sortedSet to take the symmetric difference of. .. method:: operator sortedSet.==(const ref a: sortedSet(?t), const ref b: sortedSet(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: An sortedSet to compare. :arg b: An sortedSet to compare. :return: `true` if two sets are equal. :rtype: `bool` .. method:: operator sortedSet.!=(const ref a: sortedSet(?t), const ref b: sortedSet(t)): bool Return `true` if the sets `a` and `b` are not equal. :arg a: An sortedSet to compare. :arg b: An sortedSet to compare. :return: `true` if two sets are not equal. :rtype: `bool` .. method:: operator sortedSet.<(const ref a: sortedSet(?t), const ref b: sortedSet(t)): bool Return `true` if `a` is a proper subset of `b`. :arg a: An sortedSet to compare. :arg b: An sortedSet to compare. :return: `true` if `a` is a proper subset of `b`. :rtype: `bool` .. method:: operator sortedSet.<=(const ref a: sortedSet(?t), const ref b: sortedSet(t)): bool Return `true` if `a` is a subset of `b`. :arg a: An sortedSet to compare. :arg b: An sortedSet to compare. :return: `true` if `a` is a subset of `b`. :rtype: `bool` .. method:: operator sortedSet.>(const ref a: sortedSet(?t), const ref b: sortedSet(t)): bool Return `true` if `a` is a proper superset of `b`. :arg a: An sortedSet to compare. :arg b: An sortedSet to compare. :return: `true` if `a` is a proper superset of `b`. :rtype: `bool` .. method:: operator sortedSet.>=(const ref a: sortedSet(?t), const ref b: sortedSet(t)): bool Return `true` if `a` is a superset of `b`. :arg a: An sortedSet to compare. :arg b: An sortedSet to compare. :return: `true` if `a` is a superset of `b`. :rtype: `bool`