OrderedSet¶
Usage
use OrderedSet;
or
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 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
¶ -
type
eltType
¶ The type of the elements contained in this orderedSet.
-
param
parSafe
= false¶ If true, this orderedSet will perform parallel safe operations.
-
proc
init
(type eltType, param parSafe = false, comparator: record = defaultComparator)¶ Initializes an empty orderedSet containing elements of the given type.
- Arguments
eltType – The type of the elements of this orderedSet.
parSafe – If true, this orderedSet will use parallel safe operations.
comparator – The comparator used to compare elements.
-
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.
- Arguments
iterable – A collection of elements to add to this orderedSet.
parSafe – If true, this orderedSet will use parallel safe operations.
comparator – The comparator used to compare elements.
-
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.
- Arguments
other – An orderedSet to initialize this orderedSet with.
-
proc
writeThis
(ch: channel) throws¶ Write the contents of this orderedSet to a channel.
- Arguments
ch – A channel to write to.
-
proc
size
¶ The current number of elements contained in this orderedSet.
-
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.
- Arguments
x – The element to add to this orderedSet.
-
proc
contains
(const ref x: eltType): bool¶ Returns true if the given element is a member of this orderedSet, and false otherwise.
- Arguments
x – The element to test for membership.
- Returns
Whether or not the given element is a member of this orderedSet.
- Return type
bool
-
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.
- Arguments
x – The element to remove.
- Returns
Whether or not an element equal to x was removed.
- Return type
bool
-
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.
-
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
- Return type
(bool, eltType)
-
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
- Return type
(bool, eltType)
-
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.
- Arguments
e : eltType – The element to base
- Returns
a tuple containing result
- Return type
(bool, eltType)
-
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.
- Arguments
e : eltType – The element to base
- Returns
a tuple containing result
- Return type
(bool, eltType)
-
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.
- Arguments
k : int – To find k-th element
- Returns
a tuple containing result
- Return type
(bool, eltType)
-
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.
-
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.
- Arguments
other – The orderedSet to compare against.
- Returns
Whether or not this orderedSet and other are disjoint.
- Return type
bool
-
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.
- Arguments
other – The orderedSet to compare against.
- Returns
Whether or not this orderedSet and other intersect.
- Return type
bool
-
proc
isEmpty
(): bool¶ Returns true if this orderedSet is empty (size == 0).
- Return type
bool
-
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.
- Returns
An array containing a copy of each of the elements in this orderedSet.
- Return type
[] eltType
-
type
-
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.
- Arguments
lhs – The orderedSet to assign to.
rhs – The orderedSet to assign from.
-
proc |(const ref a: orderedSet(?t), const ref b: orderedSet(t)): orderedSet(t)
Return a new orderedSet that contains the union of two sets.
- Arguments
a – An orderedSet to take the union of.
b – An orderedSet to take the union of.
- Returns
A new orderedSet containing the union between a and b.
- Return type
orderedSet(?t)
-
proc |=(ref lhs: orderedSet(?t), const ref rhs: orderedSet(t))
Add to the orderedSet lhs all the elements of rhs.
- Arguments
lhs – An orderedSet to take the union of and then assign to.
rhs – An orderedSet to take the union of.
-
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.
- Arguments
a – An orderedSet to take the union of.
b – An orderedSet to take the union of.
- Returns
A new orderedSet containing the union between a and b.
- Return type
orderedSet(?t)
-
proc
+=
(ref lhs: orderedSet(?t), const ref rhs: orderedSet(t))¶ Add to the orderedSet lhs all the elements of rhs.
- Arguments
lhs – An orderedSet to take the union of and then assign to.
rhs – An orderedSet to take the union of.
-
proc
-
(const ref a: orderedSet(?t), const ref b: orderedSet(t)): orderedSet(t)¶ Return a new orderedSet that contains the difference of two sets.
- Arguments
a – An orderedSet to take the difference of.
b – An orderedSet to take the difference of.
- Returns
A new orderedSet containing the difference between a and b.
- Return type
orderedSet(t)
-
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.
- Arguments
lhs – An orderedSet to take the difference of and then assign to.
rhs – An orderedSet to take the difference of.
-
proc &(const ref a: orderedSet(?t), const ref b: orderedSet(t)): orderedSet(t)
Return a new orderedSet that contains the intersection of two sets.
- Arguments
a – An orderedSet to take the intersection of.
b – An orderedSet to take the intersection of.
- Returns
A new orderedSet containing the intersection of a and b.
- Return type
orderedSet(t)
-
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.
- Arguments
lhs – An orderedSet to take the intersection of and then assign to.
rhs – An orderedSet to take the intersection of.
-
proc ^(const ref a: orderedSet(?t), const ref b: orderedSet(t)): orderedSet(t)
Return the symmetric difference of two sets.
- Arguments
a – An orderedSet to take the symmetric difference of.
b – An orderedSet to take the symmetric difference of.
- Returns
A new orderedSet containing the symmetric difference of a and b.
- Return type
orderedSet(?t)
-
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.
- Arguments
lhs – An orderedSet to take the symmetric difference of and then assign to.
rhs – An orderedSet to take the symmetric difference of.
-
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.
- Arguments
a – An orderedSet to compare.
b – An orderedSet to compare.
- Returns
true if two sets are equal.
- Return type
bool
-
proc
!=
(const ref a: orderedSet(?t), const ref b: orderedSet(t)): bool¶ Return true if the sets a and b are not equal.
- Arguments
a – An orderedSet to compare.
b – An orderedSet to compare.
- Returns
true if two sets are not equal.
- Return type
bool
-
proc
<
(const ref a: orderedSet(?t), const ref b: orderedSet(t)): bool¶ Return true if a is a proper subset of b.
- Arguments
a – An orderedSet to compare.
b – An orderedSet to compare.
- Returns
true if a is a proper subset of b.
- Return type
bool
-
proc
<=
(const ref a: orderedSet(?t), const ref b: orderedSet(t)): bool¶ Return true if a is a subset of b.
- Arguments
a – An orderedSet to compare.
b – An orderedSet to compare.
- Returns
true if a is a subset of b.
- Return type
bool
-
proc
>
(const ref a: orderedSet(?t), const ref b: orderedSet(t)): bool¶ Return true if a is a proper superset of b.
- Arguments
a – An orderedSet to compare.
b – An orderedSet to compare.
- Returns
true if a is a proper superset of b.
- Return type
bool
-
proc
>=
(const ref a: orderedSet(?t), const ref b: orderedSet(t)): bool¶ Return true if a is a superset of b.
- Arguments
a – An orderedSet to compare.
b – An orderedSet to compare.
- Returns
true if a is a superset of b.
- Return type
bool