.. default-domain:: chpl .. module:: OrderedSet :synopsis: This module contains the implementation of the ``orderedSet`` type. OrderedSet ========== **Usage** .. code-block:: chapel use OrderedSet; or .. code-block:: chapel import OrderedSet; This module contains the implementation of the ``orderedSet`` type. An ``orderedSet`` is a collection of unique and ordered elements. The ``orderedSet`` 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 ``orderedSet`` elements are invalidated when the ``orderedSet`` is cleared or deinitialized. ``orderedSet`` is not parallel safe by default, but can be made parallel safe by setting the param formal `parSafe` to true in any ``orderedSet`` constructor. When constructed from another ``orderedSet``, the new ``orderedSet`` will inherit the parallel safety mode of its originating ``orderedSet``. .. record:: orderedSet .. attribute:: type eltType The type of the elements contained in this orderedSet. .. attribute:: param parSafe = false If `true`, this orderedSet will perform parallel safe operations. .. method:: proc init(type eltType, param parSafe = false, comparator: record = defaultComparator) Initializes an empty orderedSet containing elements of the given type. :arg eltType: The type of the elements of this orderedSet. :arg parSafe: If `true`, this orderedSet 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) Initialize this orderedSet with a unique copy of each element contained in `iterable`. If an element from `iterable` is already contained in this orderedSet, 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 orderedSet. :arg parSafe: If `true`, this orderedSet will use parallel safe operations. :arg comparator: The comparator used to compare elements. .. method:: proc init=(const ref other: orderedSet(?t)) Initialize this orderedSet with a copy of each of the elements contained in the orderedSet `other`. This orderedSet will inherit the `parSafe` value of the orderedSet `other`. :arg other: An orderedSet to initialize this orderedSet with. .. method:: proc writeThis(ch: channel) throws Write the contents of this orderedSet to a channel. :arg ch: A channel to write to. .. method:: proc size The current number of elements contained in this orderedSet. .. method:: proc ref add(in x: eltType) Add a copy of the element `x` to this orderedSet. Does nothing if this orderedSet already contains an element equal to the value of `x`. :arg x: The element to add to this orderedSet. .. method:: proc contains(const ref x: eltType): bool Returns `true` if the given element is a member of this orderedSet, and `false` otherwise. :arg x: The element to test for membership. :return: Whether or not the given element is a member of this orderedSet. :rtype: `bool` .. method:: proc ref remove(const ref x: eltType): bool Attempt to remove the item from this orderedSet with a value equal to `x`. If an element equal to `x` was removed from this orderedSet, 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 orderedSet. .. warning:: Clearing the contents of this orderedSet will invalidate all existing references to the elements contained in this orderedSet. .. method:: proc lowerBound(e: eltType): (bool, eltType) Find the first element in the orderedSet 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 orderedSet, 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 orderedSet 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 orderedSet, 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 orderedSet. 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 orderedSet, 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 orderedSet. 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 orderedSet, 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 orderedSet. 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 orderedSet, 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 orderedSet. Yields constant references that cannot be modified. .. warning:: Modifying this orderedSet 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 orderedSet. .. method:: proc isDisjoint(const ref other: orderedSet(eltType, ?)): bool Returns `true` if this orderedSet shares no elements in common with the orderedSet `other`, and `false` otherwise. :arg other: The orderedSet to compare against. :return: Whether or not this orderedSet and `other` are disjoint. :rtype: `bool` .. method:: proc isIntersecting(const ref other: orderedSet(eltType, ?)): bool Returns `true` if this orderedSet and `other` have at least one element in common, and `false` otherwise. :arg other: The orderedSet to compare against. :return: Whether or not this orderedSet and `other` intersect. :rtype: `bool` .. method:: proc isEmpty(): bool Returns `true` if this orderedSet 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 orderedSet. The array will be in order. :return: An array containing a copy of each of the elements in this orderedSet. :rtype: `[] eltType` .. function:: proc =(ref lhs: orderedSet(?t), rhs: orderedSet(t)) Clear the contents of this orderedSet, then extend this now empty orderedSet with the elements contained in another orderedSet. .. warning:: This will invalidate any references to elements previously contained in `lhs`. :arg lhs: The orderedSet to assign to. :arg rhs: The orderedSet to assign from. .. function:: proc |(const ref a: orderedSet(?t), const ref b: orderedSet(t)): orderedSet(t) Return a new orderedSet that contains the union of two sets. :arg a: An orderedSet to take the union of. :arg b: An orderedSet to take the union of. :return: A new orderedSet containing the union between `a` and `b`. :rtype: `orderedSet(?t)` .. function:: proc |=(ref lhs: orderedSet(?t), const ref rhs: orderedSet(t)) Add to the orderedSet `lhs` all the elements of `rhs`. :arg lhs: An orderedSet to take the union of and then assign to. :arg rhs: An orderedSet to take the union of. .. function:: proc +(const ref a: orderedSet(?t), const ref b: orderedSet(t)): orderedSet(t) Return a new orderedSet that contains the union of two sets. Alias for the `|` operator. :arg a: An orderedSet to take the union of. :arg b: An orderedSet to take the union of. :return: A new orderedSet containing the union between `a` and `b`. :rtype: `orderedSet(?t)` .. function:: proc +=(ref lhs: orderedSet(?t), const ref rhs: orderedSet(t)) Add to the orderedSet `lhs` all the elements of `rhs`. :arg lhs: An orderedSet to take the union of and then assign to. :arg rhs: An orderedSet to take the union of. .. function:: proc -(const ref a: orderedSet(?t), const ref b: orderedSet(t)): orderedSet(t) Return a new orderedSet that contains the difference of two sets. :arg a: An orderedSet to take the difference of. :arg b: An orderedSet to take the difference of. :return: A new orderedSet containing the difference between `a` and `b`. :rtype: `orderedSet(t)` .. function:: proc -=(ref lhs: orderedSet(?t), const ref rhs: orderedSet(t)) Remove from the orderedSet `lhs` the elements of `rhs`. .. warning:: This will invalidate any references to elements previously contained in the orderedSet `lhs`. :arg lhs: An orderedSet to take the difference of and then assign to. :arg rhs: An orderedSet to take the difference of. .. function:: proc &(const ref a: orderedSet(?t), const ref b: orderedSet(t)): orderedSet(t) Return a new orderedSet that contains the intersection of two sets. :arg a: An orderedSet to take the intersection of. :arg b: An orderedSet to take the intersection of. :return: A new orderedSet containing the intersection of `a` and `b`. :rtype: `orderedSet(t)` .. function:: proc &=(ref lhs: orderedSet(?t, ?), const ref rhs: orderedSet(t, ?)) Assign to the orderedSet `lhs` the orderedSet that is the intersection of `lhs` and `rhs`. .. warning:: This will invalidate any references to elements previously contained in the orderedSet `lhs`. :arg lhs: An orderedSet to take the intersection of and then assign to. :arg rhs: An orderedSet to take the intersection of. .. function:: proc ^(const ref a: orderedSet(?t), const ref b: orderedSet(t)): orderedSet(t) Return the symmetric difference of two sets. :arg a: An orderedSet to take the symmetric difference of. :arg b: An orderedSet to take the symmetric difference of. :return: A new orderedSet containing the symmetric difference of `a` and `b`. :rtype: `orderedSet(?t)` .. function:: proc ^=(ref lhs: orderedSet(?t), const ref rhs: orderedSet(t)) Assign to the orderedSet `lhs` the orderedSet that is the symmetric difference of `lhs` and `rhs`. .. warning:: This will invalidate any references to elements previously contained in the orderedSet `lhs`. :arg lhs: An orderedSet to take the symmetric difference of and then assign to. :arg rhs: An orderedSet to take the symmetric difference of. .. function:: proc ==(const ref a: orderedSet(?t), const ref b: orderedSet(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 orderedSet to compare. :arg b: An orderedSet to compare. :return: `true` if two sets are equal. :rtype: `bool` .. function:: proc !=(const ref a: orderedSet(?t), const ref b: orderedSet(t)): bool Return `true` if the sets `a` and `b` are not equal. :arg a: An orderedSet to compare. :arg b: An orderedSet to compare. :return: `true` if two sets are not equal. :rtype: `bool` .. function:: proc <(const ref a: orderedSet(?t), const ref b: orderedSet(t)): bool Return `true` if `a` is a proper subset of `b`. :arg a: An orderedSet to compare. :arg b: An orderedSet to compare. :return: `true` if `a` is a proper subset of `b`. :rtype: `bool` .. function:: proc <=(const ref a: orderedSet(?t), const ref b: orderedSet(t)): bool Return `true` if `a` is a subset of `b`. :arg a: An orderedSet to compare. :arg b: An orderedSet to compare. :return: `true` if `a` is a subset of `b`. :rtype: `bool` .. function:: proc >(const ref a: orderedSet(?t), const ref b: orderedSet(t)): bool Return `true` if `a` is a proper superset of `b`. :arg a: An orderedSet to compare. :arg b: An orderedSet to compare. :return: `true` if `a` is a proper superset of `b`. :rtype: `bool` .. function:: proc >=(const ref a: orderedSet(?t), const ref b: orderedSet(t)): bool Return `true` if `a` is a superset of `b`. :arg a: An orderedSet to compare. :arg b: An orderedSet to compare. :return: `true` if `a` is a superset of `b`. :rtype: `bool`