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 hash[A](s: HashSet[A]): Hash
- hashing of HashSet 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 pop[A](s: var HashSet[A]): A
-
Remove and return an arbitrary element from the set s.
Raises KeyError if the set s is empty.
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 hash[A](s: OrderedSet[A]): Hash
- hashing of OrderedSet 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]
- "is greater or equals" operator. This is the same as y <= x. Source Edit