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

Procs

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: TSet[string]) =
  assert options.isValid, "Pass an initialized set!"
  # Do stuff here, may crash in release builds!
  Source
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: TSet[int]
assert(not values.isValid)
assert values.len == 0
  Source
proc card[A](s: HashSet[A]): int

Alias for len().

Card stands for the cardinality of a set.

  Source
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
proc mget[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 EInvalidKey exception. This is useful when one overloaded 'hash' and '==' but still needs reference semantics for sharing.   Source
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
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
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
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
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
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
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: TSet[int]
a.init(4)
a.incl(2)
a.init
assert a.len == 0 and a.isValid
  Source
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
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
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
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
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
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
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
proc `+`[A](s1, s2: HashSet[A]): HashSet[A] {.inline.}
Alias for union(s1, s2).   Source
proc `*`[A](s1, s2: HashSet[A]): HashSet[A] {.inline.}
Alias for intersection(s1, s2).   Source
proc `-`[A](s1, s2: HashSet[A]): HashSet[A] {.inline.}
Alias for difference(s1, s2).   Source
proc `-+-`[A](s1, s2: HashSet[A]): HashSet[A] {.inline.}
Alias for symmetricDifference(s1, s2).   Source
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
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
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
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
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
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: TOrderedSet[int]) =
  assert cards.isValid, "Pass an initialized set!"
  # Do stuff here, may crash in release builds!
  Source
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: TOrderedSet[int]
assert(not values.isValid)
assert values.len == 0
  Source
proc card[A](s: OrderedSet[A]): int {.inline.}

Alias for len().

Card stands for the cardinality of a set.

  Source
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
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
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
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
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: TOrderedSet[int]
a.init(4)
a.incl(2)
a.init
assert a.len == 0 and a.isValid
  Source
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
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
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
proc `==`[A](s, t: OrderedSet[A]): bool
Equality for ordered sets.   Source

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