SortedSet

Usage

use SortedSet;

or

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

type eltType

The type of the elements contained in this sortedSet.

param parSafe = false

If true, this sortedSet will perform parallel safe operations.

type comparatorType = DefaultComparator

proc init(type eltType, param parSafe = false, type comparatorType = DefaultComparator)

Initializes an empty sortedSet containing elements of the given type.

Arguments:

• eltType – The type of the elements of this sortedSet.

• parSafe – If true, this sortedSet will use parallel safe operations.

• comparatorType – The comparator type

proc init(type eltType, param parSafe = false, comparator: record)

Initializes an empty sortedSet containing elements of the given type.

Arguments:

• eltType – The type of the elements of this sortedSet.

• parSafe – If true, this sortedSet will use parallel safe operations.

• comparator – The comparator used to compare elements.

proc init(type eltType, iterable, param parSafe = false, comparator: record = new 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.

Arguments:

• eltType – The type of the elements of this sortedSet.

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

• parSafe – If true, this sortedSet will use parallel safe operations.

• comparator – The comparator used to compare elements.

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.

Arguments:

other – An sortedSet to initialize this sortedSet with.

proc serialize(writer, ref serializer) throws

Write the contents of this sortedSet to a fileWriter.

proc size

The current number of elements contained in this sortedSet.

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.

Arguments:

x – The element to add to this sortedSet.

proc contains(const ref x: eltType) : bool

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

Arguments:

x – The element to test for membership.

Returns:

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

Return type:

bool

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.

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 sortedSet.

Warning

Clearing the contents of this sortedSet will invalidate all existing references to the elements contained in this sortedSet.

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

Return type:

(bool, eltType)

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

Return type:

(bool, eltType)

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.

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 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.

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 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.

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 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.

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.

Arguments:

other – The sortedSet to compare against.

Returns:

Whether or not this sortedSet and other are disjoint.

Return type:

bool

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.

Arguments:

other – The sortedSet to compare against.

Returns:

Whether or not this sortedSet and other intersect.

Return type:

bool

proc isEmpty() : bool

Returns true if this sortedSet 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 sortedSet. The array will be in order.

Returns:

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

Return type:

[] eltType

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.

Arguments:

• lhs – The sortedSet to assign to.

• rhs – The sortedSet to assign from.

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.

Arguments:

• a – An sortedSet to take the union of.

• b – An sortedSet to take the union of.

Returns:

A new sortedSet containing the union between a and b.

Return type:

sortedSet(?t)

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

Add to the sortedSet lhs all the elements of rhs.

Arguments:

• lhs – An sortedSet to take the union of and then assign to.

• rhs – An sortedSet to take the union of.

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.

Arguments:

• a – An sortedSet to take the union of.

• b – An sortedSet to take the union of.

Returns:

A new sortedSet containing the union between a and b.

Return type:

sortedSet(?t)

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

Add to the sortedSet lhs all the elements of rhs.

Arguments:

• lhs – An sortedSet to take the union of and then assign to.

• rhs – An sortedSet to take the union of.

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.

Arguments:

• a – An sortedSet to take the difference of.

• b – An sortedSet to take the difference of.

Returns:

A new sortedSet containing the difference between a and b.

Return type:

sortedSet(t)

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.

Arguments:

• lhs – An sortedSet to take the difference of and then assign to.

• rhs – An sortedSet to take the difference of.

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.

Arguments:

• a – An sortedSet to take the intersection of.

• b – An sortedSet to take the intersection of.

Returns:

A new sortedSet containing the intersection of a and b.

Return type:

sortedSet(t)

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.

Arguments:

• lhs – An sortedSet to take the intersection of and then assign to.

• rhs – An sortedSet to take the intersection of.

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

Return the symmetric difference of two sets.

Arguments:

• a – An sortedSet to take the symmetric difference of.

• b – An sortedSet to take the symmetric difference of.

Returns:

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

Return type:

sortedSet(?t)

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.

Arguments:

• lhs – An sortedSet to take the symmetric difference of and then assign to.

• rhs – An sortedSet to take the symmetric difference of.

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.

Arguments:

• a – An sortedSet to compare.

• b – An sortedSet to compare.

Returns:

true if two sets are equal.

Return type:

bool

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

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

Arguments:

• a – An sortedSet to compare.

• b – An sortedSet to compare.

Returns:

true if two sets are not equal.

Return type:

bool

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

Return true if a is a proper subset of b.

Arguments:

• a – An sortedSet to compare.

• b – An sortedSet to compare.

Returns:

true if a is a proper subset of b.

Return type:

bool

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

Return true if a is a subset of b.

Arguments:

• a – An sortedSet to compare.

• b – An sortedSet to compare.

Returns:

true if a is a subset of b.

Return type:

bool

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

Return true if a is a proper superset of b.

Arguments:

• a – An sortedSet to compare.

• b – An sortedSet to compare.

Returns:

true if a is a proper superset of b.

Return type:

bool

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

Return true if a is a superset of b.

Arguments:

• a – An sortedSet to compare.

• b – An sortedSet to compare.

Returns:

true if a is a superset of b.

Return type:

bool