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.

Imports

hashes, math

Types

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

A generic hash set.

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

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.

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.

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!

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

proc card[A](s: HashSet[A]): int

Alias for len().

Card stands for the cardinality of a set.

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.

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.

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.

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

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

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

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

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}

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

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

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)

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)

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}

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"])

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"])

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"])

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"])

proc `+`[A](s1, s2: HashSet[A]): HashSet[A] {.inline.}

Alias for union(s1, s2).

proc `*`[A](s1, s2: HashSet[A]): HashSet[A] {.inline.}

Alias for intersection(s1, s2).

proc `-`[A](s1, s2: HashSet[A]): HashSet[A] {.inline.}

Alias for difference(s1, s2).

proc `-+-`[A](s1, s2: HashSet[A]): HashSet[A] {.inline.}

Alias for symmetricDifference(s1, s2).

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

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)

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

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

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"])

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.

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!

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

proc card[A](s: OrderedSet[A]): int {.inline.}

Alias for len().

Card stands for the cardinality of a set.

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)

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

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

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

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

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)

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)

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}

proc `==`[A](s, t: OrderedSet[A]): bool

Equality for ordered sets.

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

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