Module sets

The sets module implements an efficient hash set and ordered hash set.

Hash sets are different from the built in set type. Sets allow you to store any value that can be hashed and they don't contain duplicate entries.

Note: The data types declared here have value semantics: This means that = performs a copy of the set.

Types

HashSet[A] = object
  data: KeyValuePairSeq[A]
  counter: int

A generic hash set.

Use init() or initSet[type]() before calling other procs on it.

  Source Edit
OrderedSet[A] = object
  data: OrderedKeyValuePairSeq[A]
  counter, first, last: int

A generic hash set that remembers insertion order.

Use init() or initOrderedSet[type]() before calling other procs on it.

  Source Edit

Procs

proc clear[A](s: var HashSet[A])
Clears the HashSet back to an empty state, without shrinking any of the existing storage. O(n) where n is the size of the hash bucket.   Source Edit
proc isValid[A](s: HashSet[A]): bool

Returns true if the set has been initialized with initSet.

Most operations over an uninitialized set will crash at runtime and assert in debug builds. You can use this proc in your own procs to verify that sets passed to your procs are correctly initialized. Example:

proc savePreferences(options: HashSet[string]) =
  assert options.isValid, "Pass an initialized set!"
  # Do stuff here, may crash in release builds!
  Source Edit
proc len[A](s: HashSet[A]): int

Returns the number of keys in s.

Due to an implementation detail you can call this proc on variables which have not been initialized yet. The proc will return zero as the length then. Example:

var values: HashSet[int]
assert(not values.isValid)
assert values.len == 0
  Source Edit
proc card[A](s: HashSet[A]): int

Alias for len().

Card stands for the cardinality of a set.

  Source Edit
proc rightSize(count: Natural): int {.
inline, raises: [], tags: []
.}

Return the value of initialSize to support count items.

If more items are expected to be added, simply add that expected extra amount to the parameter before calling this.

Internally, we want mustRehash(rightSize(x), x) == false.

  Source Edit
proc `[]`[A](s: var HashSet[A]; key: A): var A
returns the element that is actually stored in 's' which has the same value as 'key' or raises the KeyError exception. This is useful when one overloaded 'hash' and '==' but still needs reference semantics for sharing.   Source Edit
proc mget[A](s: var HashSet[A]; key: A): var A {.
deprecated
.}
returns the element that is actually stored in 's' which has the same value as 'key' or raises the KeyError exception. This is useful when one overloaded 'hash' and '==' but still needs reference semantics for sharing. Use ```[]``` instead.   Source Edit
proc contains[A](s: HashSet[A]; key: A): bool

Returns true iff key is in s.

Example:

var values = initSet[int]()
assert(not values.contains(2))
values.incl(2)
assert values.contains(2)
values.excl(2)
assert(not values.contains(2))
  Source Edit
proc incl[A](s: var HashSet[A]; key: A)

Includes an element key in s.

This doesn't do anything if key is already in s. Example:

var values = initSet[int]()
values.incl(2)
values.incl(2)
assert values.len == 1
  Source Edit
proc incl[A](s: var HashSet[A]; other: HashSet[A])

Includes all elements from other into s.

Example:

var values = initSet[int]()
values.incl(2)
var others = toSet([6, 7])
values.incl(others)
assert values.len == 3
  Source Edit
proc missingOrExcl[A](s: var HashSet[A]; key: A): bool

Excludes key in the set s and tells if key was removed from s.

The difference with regards to the excl() proc is that this proc returns true if key was not present in s. Example:

var s = toSet([2, 3, 6, 7])
assert s.missingOrExcl(4) == true
assert s.missingOrExcl(6) == false
  Source Edit
proc excl[A](s: var HashSet[A]; key: A)

Excludes key from the set s.

This doesn't do anything if key is not found in s. Example:

var s = toSet([2, 3, 6, 7])
s.excl(2)
s.excl(2)
assert s.len == 3
  Source Edit
proc excl[A](s: var HashSet[A]; other: HashSet[A])

Excludes everything in other from s.

Example:

var
  numbers = toSet([1, 2, 3, 4, 5])
  even = toSet([2, 4, 6, 8])
numbers.excl(even)
echo numbers
# --> {1, 3, 5}
  Source Edit
proc containsOrIncl[A](s: var HashSet[A]; key: A): bool

Includes key in the set s and tells if key was added to s.

The difference with regards to the incl() proc is that this proc returns true if key was already present in s. The proc will return false if key was added as a new value to s during this call. Example:

var values = initSet[int]()
assert values.containsOrIncl(2) == false
assert values.containsOrIncl(2) == true
  Source Edit
proc init[A](s: var HashSet[A]; initialSize = 64)

Initializes a hash set.

The initialSize parameter needs to be a power of two. You can use math.nextPowerOfTwo() or rightSize to guarantee that at runtime. All set variables must be initialized before use with other procs from this module with the exception of isValid() and len().

You can call this proc on a previously initialized hash set, which will discard all its values. This might be more convenient than iterating over existing values and calling excl() on them. Example:

var a: HashSet[int]
a.init(4)
a.incl(2)
a.init
assert a.len == 0 and a.isValid
  Source Edit
proc initSet[A](initialSize = 64): HashSet[A]

Wrapper around init() for initialization of hash sets.

Returns an empty hash set you can assign directly in var blocks in a single line. Example:

var a = initSet[int](4)
a.incl(2)
  Source Edit
proc toSet[A](keys: openArray[A]): HashSet[A]

Creates a new hash set that contains the given keys.

Example:

var numbers = toSet([1, 2, 3, 4, 5])
assert numbers.contains(2)
assert numbers.contains(4)
  Source Edit
proc `$`[A](s: HashSet[A]): string

Converts the set s to a string, mostly for logging purposes.

Don't use this proc for serialization, the representation may change at any moment and values are not escaped. Example:

Example:

echo toSet([2, 4, 5])
# --> {2, 4, 5}
echo toSet(["no", "esc'aping", "is \" provided"])
# --> {no, esc'aping, is " provided}
  Source Edit
proc union[A](s1, s2: HashSet[A]): HashSet[A]

Returns the union of the sets s1 and s2.

The union of two sets is represented mathematically as A ∪ B and is the set of all objects that are members of s1, s2 or both. Example:

var
  a = toSet(["a", "b"])
  b = toSet(["b", "c"])
  c = union(a, b)
assert c == toSet(["a", "b", "c"])
  Source Edit
proc intersection[A](s1, s2: HashSet[A]): HashSet[A]

Returns the intersection of the sets s1 and s2.

The intersection of two sets is represented mathematically as A ∩ B and is the set of all objects that are members of s1 and s2 at the same time. Example:

var
  a = toSet(["a", "b"])
  b = toSet(["b", "c"])
  c = intersection(a, b)
assert c == toSet(["b"])
  Source Edit
proc difference[A](s1, s2: HashSet[A]): HashSet[A]

Returns the difference of the sets s1 and s2.

The difference of two sets is represented mathematically as A B and is the set of all objects that are members of s1 and not members of s2. Example:

var
  a = toSet(["a", "b"])
  b = toSet(["b", "c"])
  c = difference(a, b)
assert c == toSet(["a"])
  Source Edit
proc symmetricDifference[A](s1, s2: HashSet[A]): HashSet[A]

Returns the symmetric difference of the sets s1 and s2.

The symmetric difference of two sets is represented mathematically as A △ B or A ⊖ B and is the set of all objects that are members of s1 or s2 but not both at the same time. Example:

var
  a = toSet(["a", "b"])
  b = toSet(["b", "c"])
  c = symmetricDifference(a, b)
assert c == toSet(["a", "c"])
  Source Edit
proc `+`[A](s1, s2: HashSet[A]): HashSet[A] {.
inline
.}
Alias for union(s1, s2).   Source Edit
proc `*`[A](s1, s2: HashSet[A]): HashSet[A] {.
inline
.}
Alias for intersection(s1, s2).   Source Edit
proc `-`[A](s1, s2: HashSet[A]): HashSet[A] {.
inline
.}
Alias for difference(s1, s2).   Source Edit
proc `-+-`[A](s1, s2: HashSet[A]): HashSet[A] {.
inline
.}
Alias for symmetricDifference(s1, s2).   Source Edit
proc disjoint[A](s1, s2: HashSet[A]): bool

Returns true iff the sets s1 and s2 have no items in common.

Example:

var
  a = toSet(["a", "b"])
  b = toSet(["b", "c"])
assert disjoint(a, b) == false
assert disjoint(a, b - a) == true
  Source Edit
proc `<`[A](s, t: HashSet[A]): bool

Returns true if s is a strict or proper subset of t.

A strict or proper subset s has all of its members in t but t has more elements than s. Example:

var
  a = toSet(["a", "b"])
  b = toSet(["b", "c"])
  c = intersection(a, b)
assert c < a and c < b
assert((a < a) == false)
  Source Edit
proc `<=`[A](s, t: HashSet[A]): bool

Returns true if s is subset of t.

A subset s has all of its members in t and t doesn't necessarily have more members than s. That is, s can be equal to t. Example:

var
  a = toSet(["a", "b"])
  b = toSet(["b", "c"])
  c = intersection(a, b)
assert c <= a and c <= b
assert((a <= a))
  Source Edit
proc `==`[A](s, t: HashSet[A]): bool

Returns true if both s and t have the same members and set size.

Example:

var
  a = toSet([1, 2])
  b = toSet([1])
b.incl(2)
assert a == b
  Source Edit
proc map[A, B](data: HashSet[A]; op: proc (x: A): B {.
closure
.}): HashSet[B]

Returns a new set after applying op on each of the elements of data.

You can use this proc to transform the elements from a set. Example:

var a = toSet([1, 2, 3])
var b = a.map(proc (x: int): string = $x)
assert b == toSet(["1", "2", "3"])
  Source Edit
proc clear[A](s: var OrderedSet[A])
Clears the OrderedSet back to an empty state, without shrinking any of the existing storage. O(n) where n is the size of the hash bucket.   Source Edit
proc isValid[A](s: OrderedSet[A]): bool

Returns true if the ordered set has been initialized with initSet.

Most operations over an uninitialized ordered set will crash at runtime and assert in debug builds. You can use this proc in your own procs to verify that ordered sets passed to your procs are correctly initialized. Example:

proc saveTarotCards(cards: OrderedSet[int]) =
  assert cards.isValid, "Pass an initialized set!"
  # Do stuff here, may crash in release builds!
  Source Edit
proc len[A](s: OrderedSet[A]): int {.
inline
.}

Returns the number of keys in s.

Due to an implementation detail you can call this proc on variables which have not been initialized yet. The proc will return zero as the length then. Example:

var values: OrderedSet[int]
assert(not values.isValid)
assert values.len == 0
  Source Edit
proc card[A](s: OrderedSet[A]): int {.
inline
.}

Alias for len().

Card stands for the cardinality of a set.

  Source Edit
proc contains[A](s: OrderedSet[A]; key: A): bool

Returns true iff key is in s.

Example:

var values = initOrderedSet[int]()
assert(not values.contains(2))
values.incl(2)
assert values.contains(2)
  Source Edit
proc incl[A](s: var OrderedSet[A]; key: A)

Includes an element key in s.

This doesn't do anything if key is already in s. Example:

var values = initOrderedSet[int]()
values.incl(2)
values.incl(2)
assert values.len == 1
  Source Edit
proc incl[A](s: var HashSet[A]; other: OrderedSet[A])

Includes all elements from other into s.

Example:

var values = initOrderedSet[int]()
values.incl(2)
var others = toOrderedSet([6, 7])
values.incl(others)
assert values.len == 3
  Source Edit
proc missingOrExcl[A](s: var OrderedSet[A]; key: A): bool

Excludes key in the set s and tells if key was removed from s. Efficiency: O(n).

The difference with regards to the excl() proc is that this proc returns true if key was not present in s. Example:

var s = toOrderedSet([2, 3, 6, 7])
assert s.missingOrExcl(4) == true
assert s.missingOrExcl(6) == false
  Source Edit
proc excl[A](s: var OrderedSet[A]; key: A)

Excludes key from the set s. Efficiency: O(n).

This doesn't do anything if key is not found in s. Example:

var s = toOrderedSet([2, 3, 6, 7])
s.excl(2)
s.excl(2)
assert s.len == 3
  Source Edit
proc containsOrIncl[A](s: var OrderedSet[A]; key: A): bool

Includes key in the set s and tells if key was added to s.

The difference with regards to the incl() proc is that this proc returns true if key was already present in s. The proc will return false if key was added as a new value to s during this call. Example:

var values = initOrderedSet[int]()
assert values.containsOrIncl(2) == false
assert values.containsOrIncl(2) == true
  Source Edit
proc init[A](s: var OrderedSet[A]; initialSize = 64)

Initializes an ordered hash set.

The initialSize parameter needs to be a power of two. You can use math.nextPowerOfTwo() or rightSize to guarantee that at runtime. All set variables must be initialized before use with other procs from this module with the exception of isValid() and len().

You can call this proc on a previously initialized ordered hash set to discard its values. At the moment this is the only proc to remove elements from an ordered hash set. Example:

var a: OrderedSet[int]
a.init(4)
a.incl(2)
a.init
assert a.len == 0 and a.isValid
  Source Edit
proc initOrderedSet[A](initialSize = 64): OrderedSet[A]

Wrapper around init() for initialization of ordered hash sets.

Returns an empty ordered hash set you can assign directly in var blocks in a single line. Example:

var a = initOrderedSet[int](4)
a.incl(2)
  Source Edit
proc toOrderedSet[A](keys: openArray[A]): OrderedSet[A]

Creates a new ordered hash set that contains the given keys.

Example:

var numbers = toOrderedSet([1, 2, 3, 4, 5])
assert numbers.contains(2)
assert numbers.contains(4)
  Source Edit
proc `$`[A](s: OrderedSet[A]): string

Converts the ordered hash set s to a string, mostly for logging purposes.

Don't use this proc for serialization, the representation may change at any moment and values are not escaped. Example:

Example:

echo toOrderedSet([2, 4, 5])
# --> {2, 4, 5}
echo toOrderedSet(["no", "esc'aping", "is \" provided"])
# --> {no, esc'aping, is " provided}
  Source Edit
proc `==`[A](s, t: OrderedSet[A]): bool
Equality for ordered sets.   Source Edit

Iterators

iterator items[A](s: HashSet[A]): A

Iterates over keys in the set s.

If you need a sequence with the keys you can use sequtils.toSeq() on the iterator. Usage example:

type
  pair = tuple[a, b: int]
var
  a, b = initSet[pair]()
a.incl((2, 3))
a.incl((3, 2))
a.incl((2, 3))
for x, y in a.items:
  b.incl((x - 2, y + 1))
assert a.len == 2
echo b
# --> {(a: 1, b: 3), (a: 0, b: 4)}
  Source Edit
iterator items[A](s: OrderedSet[A]): A

Iterates over keys in the ordered set s in insertion order.

If you need a sequence with the keys you can use sequtils.toSeq() on the iterator. Usage example:

var a = initOrderedSet[int]()
for value in [9, 2, 1, 5, 1, 8, 4, 2]:
  a.incl(value)
for value in a.items:
  echo "Got ", value
# --> Got 9
# --> Got 2
# --> Got 1
# --> Got 5
# --> Got 8
# --> Got 4
  Source Edit
iterator pairs[A](s: OrderedSet[A]): tuple[a: int, b: A]
  Source Edit