Source Edit

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.

Common usages of sets:

  1. echo toHashSet([9, 5, 1]) # {9, 1, 5}
  2. echo toOrderedSet([9, 5, 1]) # {9, 5, 1}
  3. let
  4. s1 = toHashSet([9, 5, 1])
  5. s2 = toHashSet([3, 5, 7])
  6. echo s1 + s2 # {9, 1, 3, 5, 7}
  7. echo s1 - s2 # {1, 9}
  8. echo s1 * s2 # {5}
  9. echo s1 -+- s2 # {9, 1, 3, 7}

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

See also:

Imports

hashes, math, outparams

Types

  1. HashSet[A] {..} = object

A generic hash set.

Use init proc or initHashSet proc before calling other procs on it.

Source Edit

  1. OrderedSet[A] {..} = object

A generic hash set that remembers insertion order.

Use init proc or initOrderedSet proc before calling other procs on it.

Source Edit

  1. SomeSet[A] = HashSet[A] | OrderedSet[A]

Type union representing HashSet or OrderedSet. Source Edit

Consts

  1. defaultInitialSize = 64

Source Edit

Procs

  1. proc `$`[A](s: HashSet[A]): string

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

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

Examples:

  1. echo toHashSet([2, 4, 5])
  2. # --> {2, 4, 5}
  3. echo toHashSet(["no", "esc'aping", "is \" provided"])
  4. # --> {no, esc'aping, is " provided}

Source Edit

  1. proc `$`[A](s: OrderedSet[A]): string

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

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

Examples:

  1. echo toOrderedSet([2, 4, 5])
  2. # --> {2, 4, 5}
  3. echo toOrderedSet(["no", "esc'aping", "is \" provided"])
  4. # --> {no, esc'aping, is " provided}

Source Edit

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

Alias for intersection(s1, s2). Source Edit

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

Alias for union(s1, s2). Source Edit

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

Alias for difference(s1, s2). Source Edit

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

Alias for symmetricDifference(s1, s2). Source Edit

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

  1. let
  2. a = toHashSet(["a", "b"])
  3. b = toHashSet(["b", "c"])
  4. c = intersection(a, b)
  5. assert c < a and c < b
  6. assert(not (a < a))

Source Edit

  1. proc `<=`[A](s, t: HashSet[A]): bool

Returns true if s is a 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:

  1. let
  2. a = toHashSet(["a", "b"])
  3. b = toHashSet(["b", "c"])
  4. c = intersection(a, b)
  5. assert c <= a and c <= b
  6. assert a <= a

Source Edit

  1. proc `==`[A](s, t: HashSet[A]): bool

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

Example:

  1. var
  2. a = toHashSet([1, 2])
  3. b = toHashSet([2, 1])
  4. assert a == b

Source Edit

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

Equality for ordered sets.

Example:

  1. let
  2. a = toOrderedSet([1, 2])
  3. b = toOrderedSet([2, 1])
  4. assert(not (a == b))

Source Edit

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

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

Alias for len().

Card stands for the cardinality of a set.

Source Edit

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

Alias for len().

Card stands for the cardinality of a set.

Source Edit

  1. proc clear[A](s: var HashSet[A])

Clears the HashSet back to an empty state, without shrinking any of the existing storage.

O(n) operation, where n is the size of the hash bucket.

See also:

Example:

  1. var s = toHashSet([3, 5, 7])
  2. clear(s)
  3. assert len(s) == 0

Source Edit

  1. proc clear[A](s: var OrderedSet[A])

Clears the OrderedSet back to an empty state, without shrinking any of the existing storage.

O(n) operation where n is the size of the hash bucket.

Example:

  1. var s = toOrderedSet([3, 5, 7])
  2. clear(s)
  3. assert len(s) == 0

Source Edit

  1. proc contains[A](s: HashSet[A]; key: A): bool

Returns true if key is in s.

This allows the usage of in operator.

See also:

Example:

  1. var values = initHashSet[int]()
  2. assert(not values.contains(2))
  3. assert 2 notin values
  4. values.incl(2)
  5. assert values.contains(2)
  6. assert 2 in values

Source Edit

  1. proc contains[A](s: OrderedSet[A]; key: A): bool

Returns true if key is in s.

This allows the usage of in operator.

See also:

Example:

  1. var values = initOrderedSet[int]()
  2. assert(not values.contains(2))
  3. assert 2 notin values
  4. values.incl(2)
  5. assert values.contains(2)
  6. assert 2 in values

Source Edit

  1. proc containsOrIncl[A](s: var HashSet[A]; key: A): bool

Includes key in the set s and tells if key was already in s.

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

See also:

Example:

  1. var values = initHashSet[int]()
  2. assert values.containsOrIncl(2) == false
  3. assert values.containsOrIncl(2) == true
  4. assert values.containsOrIncl(3) == false

Source Edit

  1. proc containsOrIncl[A](s: var OrderedSet[A]; key: A): bool

Includes key in the set s and tells if key was already in s.

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

See also:

Example:

  1. var values = initOrderedSet[int]()
  2. assert values.containsOrIncl(2) == false
  3. assert values.containsOrIncl(2) == true
  4. assert values.containsOrIncl(3) == false

Source Edit

  1. proc difference[A](s1, s2: HashSet[A]): HashSet[A]

Returns the difference of the sets s1 and s2.

The same as s1 - 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.

See also:

Example:

  1. let
  2. a = toHashSet(["a", "b"])
  3. b = toHashSet(["b", "c"])
  4. c = difference(a, b)
  5. assert c == toHashSet(["a"])

Source Edit

  1. proc disjoint[A](s1, s2: HashSet[A]): bool

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

Example:

  1. let
  2. a = toHashSet(["a", "b"])
  3. b = toHashSet(["b", "c"])
  4. assert disjoint(a, b) == false
  5. assert disjoint(a, b - a) == true

Source Edit

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

See also:

Example:

  1. var s = toHashSet([2, 3, 6, 7])
  2. s.excl(2)
  3. s.excl(2)
  4. assert s.len == 3

Source Edit

  1. proc excl[A](s: var HashSet[A]; other: HashSet[A])

Excludes all elements of other set from s.

This is the in-place version of s - other.

See also:

Example:

  1. var
  2. numbers = toHashSet([1, 2, 3, 4, 5])
  3. even = toHashSet([2, 4, 6, 8])
  4. numbers.excl(even)
  5. assert len(numbers) == 3
  6. ## numbers == {1, 3, 5}

Source Edit

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

See also:

Example:

  1. var s = toOrderedSet([2, 3, 6, 7])
  2. s.excl(2)
  3. s.excl(2)
  4. assert s.len == 3

Source Edit

  1. proc hash[A](s: HashSet[A]): Hash

Hashing of HashSet. Source Edit

  1. proc hash[A](s: OrderedSet[A]): Hash

Hashing of OrderedSet. Source Edit

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

See also:

Example:

  1. var values = initHashSet[int]()
  2. values.incl(2)
  3. values.incl(2)
  4. assert values.len == 1

Source Edit

  1. proc incl[A](s: var HashSet[A]; other: HashSet[A])

Includes all elements from other set into s (must be declared as var).

This is the in-place version of s + other.

See also:

Example:

  1. var
  2. values = toHashSet([1, 2, 3])
  3. others = toHashSet([3, 4, 5])
  4. values.incl(others)
  5. assert values.len == 5

Source Edit

  1. proc incl[A](s: var HashSet[A]; other: OrderedSet[A])

Includes all elements from the OrderedSet other into HashSet s (must be declared as var).

See also:

Example:

  1. var
  2. values = toHashSet([1, 2, 3])
  3. others = toOrderedSet([3, 4, 5])
  4. values.incl(others)
  5. assert values.len == 5

Source Edit

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

See also:

Example:

  1. var values = initOrderedSet[int]()
  2. values.incl(2)
  3. values.incl(2)
  4. assert values.len == 1

Source Edit

  1. proc init[A](s: var HashSet[A]; initialSize = defaultInitialSize)

Initializes a hash set.

Starting from Nim v0.20, sets are initialized by default and it is not necessary to call this function explicitly.

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.

See also:

Example:

  1. var a: HashSet[int]
  2. init(a)

Source Edit

  1. proc init[A](s: var OrderedSet[A]; initialSize = defaultInitialSize)

Initializes an ordered hash set.

Starting from Nim v0.20, sets are initialized by default and it is not necessary to call this function explicitly.

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.

See also:

Example:

  1. var a: OrderedSet[int]
  2. init(a)

Source Edit

  1. proc initHashSet[A](initialSize = defaultInitialSize): HashSet[A]

Wrapper around init proc for initialization of hash sets.

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

Starting from Nim v0.20, sets are initialized by default and it is not necessary to call this function explicitly.

See also:

Example:

  1. var a = initHashSet[int]()
  2. a.incl(3)
  3. assert len(a) == 1

Source Edit

  1. proc initOrderedSet[A](initialSize = defaultInitialSize): OrderedSet[A]

Wrapper around init proc for initialization of ordered hash sets.

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

Starting from Nim v0.20, sets are initialized by default and it is not necessary to call this function explicitly.

See also:

Example:

  1. var a = initOrderedSet[int]()
  2. a.incl(3)
  3. assert len(a) == 1

Source Edit

  1. proc initSet[A](initialSize = defaultInitialSize): HashSet[A] {.
  2. ...deprecated: "Deprecated since v0.20, use \'initHashSet\'".}

Deprecated: Deprecated since v0.20, use ‘initHashSet’

Source Edit

  1. proc intersection[A](s1, s2: HashSet[A]): HashSet[A]

Returns the intersection of the sets s1 and s2.

The same as s1 * 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.

See also:

Example:

  1. let
  2. a = toHashSet(["a", "b"])
  3. b = toHashSet(["b", "c"])
  4. c = intersection(a, b)
  5. assert c == toHashSet(["b"])

Source Edit

  1. proc isValid[A](s: HashSet[A]): bool {....deprecated: "Deprecated since v0.20; sets are initialized by default".}

Deprecated: Deprecated since v0.20; sets are initialized by default

Returns true if the set has been initialized (with initHashSet proc or init proc).

Example:

  1. proc savePreferences(options: HashSet[string]) =
  2. assert options.isValid, "Pass an initialized set!"
  3. # Do stuff here, may crash in release builds!

Source Edit

  1. proc len[A](s: HashSet[A]): int

Returns the number of elements 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:

  1. var a: HashSet[string]
  2. assert len(a) == 0
  3. let s = toHashSet([3, 5, 7])
  4. assert len(s) == 3

Source Edit

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

Returns the number of elements 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:

  1. var a: OrderedSet[string]
  2. assert len(a) == 0
  3. let s = toHashSet([3, 5, 7])
  4. assert len(s) == 3

Source Edit

  1. proc map[A, B](data: HashSet[A]; op: proc (x: A): B {.closure.}): HashSet[B] {.
  2. effectsOf: op.}

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

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

Example:

  1. let
  2. a = toHashSet([1, 2, 3])
  3. b = a.map(proc (x: int): string = $x)
  4. assert b == toHashSet(["1", "2", "3"])

Source Edit

  1. proc missingOrExcl[A](s: var HashSet[A]; key: A): bool

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

The difference with regards to the excl proc is that this proc returns true if key was missing from s. The proc will return false if key was in s and it was removed during this call.

See also:

Example:

  1. var s = toHashSet([2, 3, 6, 7])
  2. assert s.missingOrExcl(4) == true
  3. assert s.missingOrExcl(6) == false
  4. assert s.missingOrExcl(6) == true

Source Edit

  1. proc missingOrExcl[A](s: var OrderedSet[A]; key: A): bool

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

The difference with regards to the excl proc is that this proc returns true if key was missing from s. The proc will return false if key was in s and it was removed during this call.

See also:

Example:

  1. var s = toOrderedSet([2, 3, 6, 7])
  2. assert s.missingOrExcl(4) == true
  3. assert s.missingOrExcl(6) == false
  4. assert s.missingOrExcl(6) == true

Source Edit

  1. proc pop[A](s: var HashSet[A]): A

Removes and returns an arbitrary element from the set s.

Raises KeyError if the set s is empty.

See also:

Example:

  1. var s = toHashSet([2, 1])
  2. assert [s.pop, s.pop] in [[1, 2], [2,1]] # order unspecified
  3. doAssertRaises(KeyError, echo s.pop)

Source Edit

  1. proc symmetricDifference[A](s1, s2: HashSet[A]): HashSet[A]

Returns the symmetric difference of the sets s1 and s2.

The same as s1 -+- 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.

See also:

Example:

  1. let
  2. a = toHashSet(["a", "b"])
  3. b = toHashSet(["b", "c"])
  4. c = symmetricDifference(a, b)
  5. assert c == toHashSet(["a", "c"])

Source Edit

  1. proc toHashSet[A](keys: openArray[A]): HashSet[A]

Creates a new hash set that contains the members of the given collection (seq, array, or string) keys.

Duplicates are removed.

See also:

Example:

  1. let
  2. a = toHashSet([5, 3, 2])
  3. b = toHashSet("abracadabra")
  4. assert len(a) == 3
  5. ## a == {2, 3, 5}
  6. assert len(b) == 5
  7. ## b == {'a', 'b', 'c', 'd', 'r'}

Source Edit

  1. proc toOrderedSet[A](keys: openArray[A]): OrderedSet[A]

Creates a new hash set that contains the members of the given collection (seq, array, or string) keys.

Duplicates are removed.

See also:

Example:

  1. let
  2. a = toOrderedSet([5, 3, 2])
  3. b = toOrderedSet("abracadabra")
  4. assert len(a) == 3
  5. ## a == {5, 3, 2} # different than in HashSet
  6. assert len(b) == 5
  7. ## b == {'a', 'b', 'r', 'c', 'd'} # different than in HashSet

Source Edit

  1. proc toSet[A](keys: openArray[A]): HashSet[A] {.
  2. ...deprecated: "Deprecated since v0.20, use \'toHashSet\'".}

Deprecated: Deprecated since v0.20, use ‘toHashSet’

Source Edit

  1. proc union[A](s1, s2: HashSet[A]): HashSet[A]

Returns the union of the sets s1 and s2.

The same as s1 + 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.

See also:

Example:

  1. let
  2. a = toHashSet(["a", "b"])
  3. b = toHashSet(["b", "c"])
  4. c = union(a, b)
  5. assert c == toHashSet(["a", "b", "c"])

Source Edit

Iterators

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

Iterates over elements of the set s.

If you need a sequence with the elements you can use sequtils.toSeq template.

  1. type
  2. pair = tuple[a, b: int]
  3. var
  4. a, b = initHashSet[pair]()
  5. a.incl((2, 3))
  6. a.incl((3, 2))
  7. a.incl((2, 3))
  8. for x, y in a.items:
  9. b.incl((x - 2, y + 1))
  10. assert a.len == 2
  11. echo b
  12. # --> {(a: 1, b: 3), (a: 0, b: 4)}

Source Edit

  1. 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 elements you can use sequtils.toSeq template.

  1. var a = initOrderedSet[int]()
  2. for value in [9, 2, 1, 5, 1, 8, 4, 2]:
  3. a.incl(value)
  4. for value in a.items:
  5. echo "Got ", value
  6. # --> Got 9
  7. # --> Got 2
  8. # --> Got 1
  9. # --> Got 5
  10. # --> Got 8
  11. # --> Got 4

Source Edit

  1. iterator pairs[A](s: OrderedSet[A]): tuple[a: int, b: A]

Iterates through (position, value) tuples of OrderedSet s.

Example:

  1. let a = toOrderedSet("abracadabra")
  2. var p = newSeq[(int, char)]()
  3. for x in pairs(a):
  4. p.add(x)
  5. assert p == @[(0, 'a'), (1, 'b'), (2, 'r'), (3, 'c'), (4, 'd')]

Source Edit