diff options
Diffstat (limited to 'lib/pure/collections/sets.nim')
| -rw-r--r-- | lib/pure/collections/sets.nim | 119 |
1 files changed, 66 insertions, 53 deletions
diff --git a/lib/pure/collections/sets.nim b/lib/pure/collections/sets.nim index a9df9ded8..af13135aa 100644 --- a/lib/pure/collections/sets.nim +++ b/lib/pure/collections/sets.nim @@ -7,7 +7,7 @@ # distribution, for details about the copyright. # -## The ``sets`` module implements an efficient `hash set`:idx: and +## The `sets` module implements an efficient `hash set`:idx: and ## ordered hash set. ## ## Hash sets are different from the `built in set type @@ -25,7 +25,9 @@ ## `difference <#difference,HashSet[A],HashSet[A]>`_, and ## `symmetric difference <#symmetricDifference,HashSet[A],HashSet[A]>`_ ## -## .. code-block:: +## **Examples:** +## +## ```Nim ## echo toHashSet([9, 5, 1]) # {9, 1, 5} ## echo toOrderedSet([9, 5, 1]) # {9, 5, 1} ## @@ -37,10 +39,10 @@ ## echo s1 - s2 # {1, 9} ## echo s1 * s2 # {5} ## 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. +## that `=` performs a copy of the set. ## ## **See also:** ## * `intsets module <intsets.html>`_ for efficient int sets @@ -48,12 +50,12 @@ import - hashes, math + std/[hashes, math] -{.pragma: myShallow.} -when not defined(nimhygiene): - {.pragma: dirty.} +when not defined(nimHasEffectsOf): + {.pragma: effectsOf.} +{.pragma: myShallow.} # For "integer-like A" that are too big for intsets/bit-vectors to be practical, # it would be best to shrink hcode to the same size as the integer. Larger # codes should never be needed, and this can pack more entries per cache-line. @@ -64,7 +66,7 @@ type HashSet*[A] {.myShallow.} = object ## \ ## A generic hash set. ## - ## Use `init proc <#init,HashSet[A]>`_ or `initHashSet proc <#initHashSet,int>`_ + ## Use `init proc <#init,HashSet[A]>`_ or `initHashSet proc <#initHashSet>`_ ## before calling other procs on it. data: KeyValuePairSeq[A] counter: int @@ -116,7 +118,7 @@ proc initHashSet*[A](initialSize = defaultInitialSize): HashSet[A] = ## Wrapper around `init proc <#init,HashSet[A]>`_ for initialization of ## hash sets. ## - ## Returns an empty hash set you can assign directly in ``var`` blocks in a + ## 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 @@ -128,12 +130,12 @@ proc initHashSet*[A](initialSize = defaultInitialSize): HashSet[A] = var a = initHashSet[int]() a.incl(3) assert len(a) == 1 - + result = default(HashSet[A]) result.init(initialSize) 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. + ## value as `key` or raises the `KeyError` exception. ## ## This is useful when one overloaded `hash` and `==` but still needs ## reference semantics for sharing. @@ -167,6 +169,27 @@ proc contains*[A](s: HashSet[A], key: A): bool = var index = rawGet(s, key, hc) result = index >= 0 +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. + runnableExamples: + var a: HashSet[string] + assert len(a) == 0 + let s = toHashSet([3, 5, 7]) + assert len(s) == 3 + + result = s.counter + +proc card*[A](s: HashSet[A]): int = + ## Alias for `len() <#len,HashSet[A]>`_. + ## + ## Card stands for the `cardinality + ## <http://en.wikipedia.org/wiki/Cardinality>`_ of a set. + result = s.counter + proc incl*[A](s: var HashSet[A], key: A) = ## Includes an element `key` in `s`. ## @@ -228,7 +251,7 @@ iterator items*[A](s: HashSet[A]): A = ## If you need a sequence with the elements you can use `sequtils.toSeq ## template <sequtils.html#toSeq.t,untyped>`_. ## - ## .. code-block:: + ## ```Nim ## type ## pair = tuple[a, b: int] ## var @@ -241,8 +264,12 @@ iterator items*[A](s: HashSet[A]): A = ## assert a.len == 2 ## echo b ## # --> {(a: 1, b: 3), (a: 0, b: 4)} + ## ``` + let length = s.len for h in 0 .. high(s.data): - if isFilled(s.data[h].hcode): yield s.data[h].key + if isFilled(s.data[h].hcode): + yield s.data[h].key + assert(len(s) == length, "the length of the HashSet changed while iterating over it") proc containsOrIncl*[A](s: var HashSet[A], key: A): bool = ## Includes `key` in the set `s` and tells if `key` was already in `s`. @@ -323,7 +350,7 @@ proc missingOrExcl*[A](s: var HashSet[A], key: A): bool = 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. + ## Raises `KeyError` if the set `s` is empty. ## ## See also: ## * `clear proc <#clear,HashSet[A]>`_ @@ -355,28 +382,9 @@ proc clear*[A](s: var HashSet[A]) = s.counter = 0 for i in 0 ..< s.data.len: s.data[i].hcode = 0 - s.data[i].key = default(type(s.data[i].key)) - -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. - runnableExamples: - var a: HashSet[string] - assert len(a) == 0 - let s = toHashSet([3, 5, 7]) - assert len(s) == 3 - - result = s.counter - -proc card*[A](s: HashSet[A]): int = - ## Alias for `len() <#len,HashSet[A]>`_. - ## - ## Card stands for the `cardinality - ## <http://en.wikipedia.org/wiki/Cardinality>`_ of a set. - result = s.counter + {.push warning[UnsafeDefault]:off.} + reset(s.data[i].key) + {.pop.} proc union*[A](s1, s2: HashSet[A]): HashSet[A] = @@ -422,7 +430,7 @@ proc intersection*[A](s1, s2: HashSet[A]): HashSet[A] = assert c == toHashSet(["b"]) result = initHashSet[A](max(min(s1.data.len, s2.data.len), 2)) - + # iterate over the elements of the smaller set if s1.data.len < s2.data.len: for item in s1: @@ -430,7 +438,7 @@ proc intersection*[A](s1, s2: HashSet[A]): HashSet[A] = else: for item in s2: if item in s1: incl(result, item) - + proc difference*[A](s1, s2: HashSet[A]): HashSet[A] = ## Returns the difference of the sets `s1` and `s2`. @@ -556,7 +564,7 @@ proc `==`*[A](s, t: HashSet[A]): bool = s.counter == t.counter and s <= t -proc map*[A, B](data: HashSet[A], op: proc (x: A): B {.closure.}): HashSet[B] = +proc map*[A, B](data: HashSet[A], op: proc (x: A): B {.closure.}): HashSet[B] {.effectsOf: op.} = ## Returns a new set after applying `op` proc on each of the elements of ##`data` set. ## @@ -583,12 +591,12 @@ proc `$`*[A](s: HashSet[A]): string = ## any moment and values are not escaped. ## ## **Examples:** - ## - ## .. code-block:: + ## ```Nim ## echo toHashSet([2, 4, 5]) ## # --> {2, 4, 5} ## echo toHashSet(["no", "esc'aping", "is \" provided"]) ## # --> {no, esc'aping, is " provided} + ## ``` dollarImpl() @@ -603,12 +611,10 @@ proc isValid*[A](s: HashSet[A]): bool {.deprecated: ## Returns `true` if the set has been initialized (with `initHashSet proc ## <#initHashSet>`_ or `init proc <#init,HashSet[A]>`_). ## - ## **Examples:** - ## - ## .. code-block :: - ## proc savePreferences(options: HashSet[string]) = - ## assert options.isValid, "Pass an initialized set!" - ## # Do stuff here, may crash in release builds! + runnableExamples: + proc savePreferences(options: HashSet[string]) = + assert options.isValid, "Pass an initialized set!" + # Do stuff here, may crash in release builds! result = s.data.len > 0 @@ -652,7 +658,7 @@ proc initOrderedSet*[A](initialSize = defaultInitialSize): OrderedSet[A] = ## Wrapper around `init proc <#init,OrderedSet[A]>`_ for initialization of ## ordered hash sets. ## - ## Returns an empty ordered hash set you can assign directly in ``var`` blocks + ## 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 @@ -812,7 +818,9 @@ proc clear*[A](s: var OrderedSet[A]) = for i in 0 ..< s.data.len: s.data[i].hcode = 0 s.data[i].next = 0 - s.data[i].key = default(type(s.data[i].key)) + {.push warning[UnsafeDefault]:off.} + reset(s.data[i].key) + {.pop.} proc len*[A](s: OrderedSet[A]): int {.inline.} = ## Returns the number of elements in `s`. @@ -873,12 +881,12 @@ proc `$`*[A](s: OrderedSet[A]): string = ## any moment and values are not escaped. ## ## **Examples:** - ## - ## .. code-block:: + ## ```Nim ## echo toOrderedSet([2, 4, 5]) ## # --> {2, 4, 5} ## echo toOrderedSet(["no", "esc'aping", "is \" provided"]) ## # --> {no, esc'aping, is " provided} + ## ``` dollarImpl() @@ -889,7 +897,7 @@ iterator items*[A](s: OrderedSet[A]): A = ## If you need a sequence with the elements you can use `sequtils.toSeq ## template <sequtils.html#toSeq.t,untyped>`_. ## - ## .. code-block:: + ## ```Nim ## var a = initOrderedSet[int]() ## for value in [9, 2, 1, 5, 1, 8, 4, 2]: ## a.incl(value) @@ -901,8 +909,11 @@ iterator items*[A](s: OrderedSet[A]): A = ## # --> Got 5 ## # --> Got 8 ## # --> Got 4 + ## ``` + let length = s.len forAllOrderedPairs: yield s.data[h].key + assert(len(s) == length, "the length of the OrderedSet changed while iterating over it") iterator pairs*[A](s: OrderedSet[A]): tuple[a: int, b: A] = ## Iterates through (position, value) tuples of OrderedSet `s`. @@ -913,5 +924,7 @@ iterator pairs*[A](s: OrderedSet[A]): tuple[a: int, b: A] = p.add(x) assert p == @[(0, 'a'), (1, 'b'), (2, 'r'), (3, 'c'), (4, 'd')] + let length = s.len forAllOrderedPairs: yield (idx, s.data[h].key) + assert(len(s) == length, "the length of the OrderedSet changed while iterating over it") |