diff options
Diffstat (limited to 'lib/pure/collections/tables.nim')
| -rw-r--r-- | lib/pure/collections/tables.nim | 921 |
1 files changed, 509 insertions, 412 deletions
diff --git a/lib/pure/collections/tables.nim b/lib/pure/collections/tables.nim index d7376b065..d414caeed 100644 --- a/lib/pure/collections/tables.nim +++ b/lib/pure/collections/tables.nim @@ -7,219 +7,198 @@ # distribution, for details about the copyright. # -## The ``tables`` module implements variants of an efficient `hash table`:idx: +## The `tables` module implements variants of an efficient `hash table`:idx: ## (also often named `dictionary`:idx: in other programming languages) that is ## a mapping from keys to values. ## ## There are several different types of hash tables available: ## * `Table<#Table>`_ is the usual hash table, -## * `OrderedTable<#OrderedTable>`_ is like ``Table`` but remembers insertion order, +## * `OrderedTable<#OrderedTable>`_ is like `Table` but remembers insertion order, ## * `CountTable<#CountTable>`_ is a mapping from a key to its number of occurrences ## ## For consistency with every other data type in Nim these have **value** -## semantics, this means that ``=`` performs a copy of the hash table. +## semantics, this means that `=` performs a copy of the hash table. ## ## For `ref semantics<manual.html#types-reference-and-pointer-types>`_ -## use their ``Ref`` variants: `TableRef<#TableRef>`_, +## use their `Ref` variants: `TableRef<#TableRef>`_, ## `OrderedTableRef<#OrderedTableRef>`_, and `CountTableRef<#CountTableRef>`_. ## -## To give an example, when ``a`` is a ``Table``, then ``var b = a`` gives ``b`` -## as a new independent table. ``b`` is initialised with the contents of ``a``. -## Changing ``b`` does not affect ``a`` and vice versa: -## -## .. code-block:: -## import tables -## -## var -## a = {1: "one", 2: "two"}.toTable # creates a Table -## b = a -## -## echo a, b # output: {1: one, 2: two}{1: one, 2: two} -## -## b[3] = "three" -## echo a, b # output: {1: one, 2: two}{1: one, 2: two, 3: three} -## echo a == b # output: false -## -## On the other hand, when ``a`` is a ``TableRef`` instead, then changes to ``b`` -## also affect ``a``. Both ``a`` and ``b`` **ref** the same data structure: -## -## .. code-block:: -## import tables -## -## var -## a = {1: "one", 2: "two"}.newTable # creates a TableRef -## b = a -## -## echo a, b # output: {1: one, 2: two}{1: one, 2: two} -## -## b[3] = "three" -## echo a, b # output: {1: one, 2: two, 3: three}{1: one, 2: two, 3: three} -## echo a == b # output: true +## To give an example, when `a` is a `Table`, then `var b = a` gives `b` +## as a new independent table. `b` is initialised with the contents of `a`. +## Changing `b` does not affect `a` and vice versa: + +runnableExamples: + var + a = {1: "one", 2: "two"}.toTable # creates a Table + b = a + + assert a == b + + b[3] = "three" + assert 3 notin a + assert 3 in b + assert a != b + +## On the other hand, when `a` is a `TableRef` instead, then changes to `b` +## also affect `a`. Both `a` and `b` **ref** the same data structure: + +runnableExamples: + var + a = {1: "one", 2: "two"}.newTable # creates a TableRef + b = a + + assert a == b + + b[3] = "three" + + assert 3 in a + assert 3 in b + assert a == b + ## ## ---- ## -## Basic usage -## =========== -## -## Table -## ----- -## -## .. code-block:: -## import tables -## from sequtils import zip -## -## let -## names = ["John", "Paul", "George", "Ringo"] -## years = [1940, 1942, 1943, 1940] -## -## var beatles = initTable[string, int]() -## -## for pairs in zip(names, years): -## let (name, birthYear) = pairs -## beatles[name] = birthYear -## -## echo beatles -## # {"George": 1943, "Ringo": 1940, "Paul": 1942, "John": 1940} -## -## -## var beatlesByYear = initTable[int, seq[string]]() -## -## for pairs in zip(years, names): -## let (birthYear, name) = pairs -## if not beatlesByYear.hasKey(birthYear): -## # if a key doesn't exist, we create one with an empty sequence -## # before we can add elements to it -## beatlesByYear[birthYear] = @[] -## beatlesByYear[birthYear].add(name) -## -## echo beatlesByYear -## # {1940: @["John", "Ringo"], 1942: @["Paul"], 1943: @["George"]} -## -## -## -## OrderedTable -## ------------ -## + +## # Basic usage + + +## ## Table +runnableExamples: + from std/sequtils import zip + + let + names = ["John", "Paul", "George", "Ringo"] + years = [1940, 1942, 1943, 1940] + + var beatles = initTable[string, int]() + + for pairs in zip(names, years): + let (name, birthYear) = pairs + beatles[name] = birthYear + + assert beatles == {"George": 1943, "Ringo": 1940, "Paul": 1942, "John": 1940}.toTable + + + var beatlesByYear = initTable[int, seq[string]]() + + for pairs in zip(years, names): + let (birthYear, name) = pairs + if not beatlesByYear.hasKey(birthYear): + # if a key doesn't exist, we create one with an empty sequence + # before we can add elements to it + beatlesByYear[birthYear] = @[] + beatlesByYear[birthYear].add(name) + + assert beatlesByYear == {1940: @["John", "Ringo"], 1942: @["Paul"], 1943: @["George"]}.toTable + +## ## OrderedTable ## `OrderedTable<#OrderedTable>`_ is used when it is important to preserve ## the insertion order of keys. -## -## .. code-block:: -## import tables -## -## let -## a = [('z', 1), ('y', 2), ('x', 3)] -## t = a.toTable # regular table -## ot = a.toOrderedTable # ordered tables -## -## echo t # {'x': 3, 'y': 2, 'z': 1} -## echo ot # {'z': 1, 'y': 2, 'x': 3} -## -## -## -## CountTable -## ---------- -## + +runnableExamples: + let + a = [('z', 1), ('y', 2), ('x', 3)] + ot = a.toOrderedTable # ordered tables + + assert $ot == """{'z': 1, 'y': 2, 'x': 3}""" + +## ## CountTable ## `CountTable<#CountTable>`_ is useful for counting number of items of some ## container (e.g. string, sequence or array), as it is a mapping where the ## items are the keys, and their number of occurrences are the values. ## For that purpose `toCountTable proc<#toCountTable,openArray[A]>`_ ## comes handy: -## -## .. code-block:: -## import tables -## -## let myString = "abracadabra" -## let letterFrequencies = toCountTable(myString) -## echo letterFrequencies -## # output: {'a': 5, 'b': 2, 'c': 1, 'd': 1, 'r': 2} -## + +runnableExamples: + let myString = "abracadabra" + let letterFrequencies = toCountTable(myString) + assert $letterFrequencies == "{'a': 5, 'd': 1, 'b': 2, 'r': 2, 'c': 1}" + ## The same could have been achieved by manually iterating over a container ## and increasing each key's value with `inc proc ## <#inc,CountTable[A],A,int>`_: -## -## .. code-block:: -## import tables -## -## let myString = "abracadabra" -## var letterFrequencies = initCountTable[char]() -## for c in myString: -## letterFrequencies.inc(c) -## echo letterFrequencies -## # output: {'a': 5, 'b': 2, 'c': 1, 'd': 1, 'r': 2} + +runnableExamples: + let myString = "abracadabra" + var letterFrequencies = initCountTable[char]() + for c in myString: + letterFrequencies.inc(c) + assert $letterFrequencies == "{'d': 1, 'r': 2, 'c': 1, 'a': 5, 'b': 2}" + ## ## ---- ## + +## ## Hashing ## -## -## Hashing -## ------- -## -## If you are using simple standard types like ``int`` or ``string`` for the +## If you are using simple standard types like `int` or `string` for the ## keys of the table you won't have any problems, but as soon as you try to use ## a more complex object as a key you will be greeted by a strange compiler ## error: ## -## Error: type mismatch: got (Person) -## but expected one of: -## hashes.hash(x: openArray[A]): Hash -## hashes.hash(x: int): Hash -## hashes.hash(x: float): Hash -## … +## Error: type mismatch: got (Person) +## but expected one of: +## hashes.hash(x: openArray[A]): Hash +## hashes.hash(x: int): Hash +## hashes.hash(x: float): Hash ## ## What is happening here is that the types used for table keys require to have -## a ``hash()`` proc which will convert them to a `Hash <hashes.html#Hash>`_ +## a `hash()` proc which will convert them to a `Hash <hashes.html#Hash>`_ ## value, and the compiler is listing all the hash functions it knows. -## Additionally there has to be a ``==`` operator that provides the same -## semantics as its corresponding ``hash`` proc. +## Additionally there has to be a `==` operator that provides the same +## semantics as its corresponding `hash` proc. ## -## After you add ``hash`` and ``==`` for your custom type everything will work. -## Currently, however, ``hash`` for objects is not defined, whereas -## ``system.==`` for objects does exist and performs a "deep" comparison (every +## After you add `hash` and `==` for your custom type everything will work. +## Currently, however, `hash` for objects is not defined, whereas +## `system.==` for objects does exist and performs a "deep" comparison (every ## field is compared) which is usually what you want. So in the following -## example implementing only ``hash`` suffices: -## -## .. code-block:: -## import tables, hashes -## -## type -## Person = object -## firstName, lastName: string -## -## proc hash(x: Person): Hash = -## ## Piggyback on the already available string hash proc. -## ## -## ## Without this proc nothing works! -## result = x.firstName.hash !& x.lastName.hash -## result = !$result -## -## var -## salaries = initTable[Person, int]() -## p1, p2: Person -## -## p1.firstName = "Jon" -## p1.lastName = "Ross" -## salaries[p1] = 30_000 -## -## p2.firstName = "소진" -## p2.lastName = "박" -## salaries[p2] = 45_000 +## example implementing only `hash` suffices: + +runnableExamples: + import std/hashes + + type + Person = object + firstName, lastName: string + + proc hash(x: Person): Hash = + ## Piggyback on the already available string hash proc. + ## + ## Without this proc nothing works! + result = x.firstName.hash !& x.lastName.hash + result = !$result + + var + salaries = initTable[Person, int]() + p1, p2: Person + + p1.firstName = "Jon" + p1.lastName = "Ross" + salaries[p1] = 30_000 + + p2.firstName = "소진" + p2.lastName = "박" + salaries[p2] = 45_000 + ## ## ---- ## -## See also -## ======== + +## # See also ## ## * `json module<json.html>`_ for table-like structure which allows ## heterogeneous members -## * `sharedtables module<sharedtables.html>`_ for shared hash table support ## * `strtabs module<strtabs.html>`_ for efficient hash tables ## mapping from strings to strings ## * `hashes module<hashes.html>`_ for helper functions for hashing import std/private/since +import std/[hashes, math, algorithm] -import hashes, math, algorithm + +when not defined(nimHasEffectsOf): + {.pragma: effectsOf.} type KeyValuePair[A, B] = tuple[hcode: Hash, key: A, val: B] @@ -238,8 +217,6 @@ type ## For creating a new empty TableRef, use `newTable proc ## <#newTable>`_. -const - defaultInitialSize* = 32 # ------------------------------ helpers --------------------------------- @@ -250,18 +227,21 @@ template dataLen(t): untyped = len(t.data) include tableimpl +proc raiseKeyError[T](key: T) {.noinline, noreturn.} = + when compiles($key): + raise newException(KeyError, "key not found: " & $key) + else: + raise newException(KeyError, "key not found") + template get(t, key): untyped = - ## retrieves the value at ``t[key]``. The value can be modified. - ## If ``key`` is not in ``t``, the ``KeyError`` exception is raised. + ## retrieves the value at `t[key]`. The value can be modified. + ## If `key` is not in `t`, the `KeyError` exception is raised. mixin rawGet var hc: Hash var index = rawGet(t, key, hc) if index >= 0: result = t.data[index].val else: - when compiles($key): - raise newException(KeyError, "key not found: " & $key) - else: - raise newException(KeyError, "key not found") + raiseKeyError(key) proc enlarge[A, B](t: var Table[A, B]) = var n: KeyValuePairSeq[A, B] @@ -298,10 +278,11 @@ proc initTable*[A, B](initialSize = defaultInitialSize): Table[A, B] = let a = initTable[int, string]() b = initTable[char, seq[int]]() + result = default(Table[A, B]) initImpl(result, initialSize) proc `[]=`*[A, B](t: var Table[A, B], key: A, val: sink B) = - ## Inserts a ``(key, value)`` pair into ``t``. + ## Inserts a `(key, value)` pair into `t`. ## ## See also: ## * `[] proc<#[],Table[A,B],A>`_ for retrieving a value of a key @@ -317,9 +298,9 @@ proc `[]=`*[A, B](t: var Table[A, B], key: A, val: sink B) = putImpl(enlarge) proc toTable*[A, B](pairs: openArray[(A, B)]): Table[A, B] = - ## Creates a new hash table that contains the given ``pairs``. + ## Creates a new hash table that contains the given `pairs`. ## - ## ``pairs`` is a container consisting of ``(key, value)`` tuples. + ## `pairs` is a container consisting of `(key, value)` tuples. ## ## See also: ## * `initTable proc<#initTable>`_ @@ -332,10 +313,10 @@ proc toTable*[A, B](pairs: openArray[(A, B)]): Table[A, B] = result = initTable[A, B](pairs.len) for key, val in items(pairs): result[key] = val -proc `[]`*[A, B](t: Table[A, B], key: A): B = - ## Retrieves the value at ``t[key]``. +proc `[]`*[A, B](t: Table[A, B], key: A): lent B = + ## Retrieves the value at `t[key]`. ## - ## If ``key`` is not in ``t``, the ``KeyError`` exception is raised. + ## If `key` is not in `t`, the `KeyError` exception is raised. ## One can check with `hasKey proc<#hasKey,Table[A,B],A>`_ whether ## the key exists. ## @@ -344,7 +325,7 @@ proc `[]`*[A, B](t: Table[A, B], key: A): B = ## a default value (e.g. zero for int) if the key doesn't exist ## * `getOrDefault proc<#getOrDefault,Table[A,B],A,B>`_ to return ## a custom value if the key doesn't exist - ## * `[]= proc<#[]=,Table[A,B],A,B>`_ for inserting a new + ## * `[]= proc<#[]=,Table[A,B],A,sinkB>`_ for inserting a new ## (key, value) pair in the table ## * `hasKey proc<#hasKey,Table[A,B],A>`_ for checking if a key is in ## the table @@ -356,23 +337,23 @@ proc `[]`*[A, B](t: Table[A, B], key: A): B = get(t, key) proc `[]`*[A, B](t: var Table[A, B], key: A): var B = - ## Retrieves the value at ``t[key]``. The value can be modified. + ## Retrieves the value at `t[key]`. The value can be modified. ## - ## If ``key`` is not in ``t``, the ``KeyError`` exception is raised. + ## If `key` is not in `t`, the `KeyError` exception is raised. ## ## See also: ## * `getOrDefault proc<#getOrDefault,Table[A,B],A>`_ to return ## a default value (e.g. zero for int) if the key doesn't exist ## * `getOrDefault proc<#getOrDefault,Table[A,B],A,B>`_ to return ## a custom value if the key doesn't exist - ## * `[]= proc<#[]=,Table[A,B],A,B>`_ for inserting a new + ## * `[]= proc<#[]=,Table[A,B],A,sinkB>`_ for inserting a new ## (key, value) pair in the table ## * `hasKey proc<#hasKey,Table[A,B],A>`_ for checking if a key is in ## the table get(t, key) proc hasKey*[A, B](t: Table[A, B], key: A): bool = - ## Returns true if ``key`` is in the table ``t``. + ## Returns true if `key` is in the table `t`. ## ## See also: ## * `contains proc<#contains,Table[A,B],A>`_ for use with the `in` operator @@ -391,7 +372,7 @@ proc hasKey*[A, B](t: Table[A, B], key: A): bool = proc contains*[A, B](t: Table[A, B], key: A): bool = ## Alias of `hasKey proc<#hasKey,Table[A,B],A>`_ for use with - ## the ``in`` operator. + ## the `in` operator. runnableExamples: let a = {'a': 5, 'b': 9}.toTable doAssert 'b' in a == true @@ -400,7 +381,7 @@ proc contains*[A, B](t: Table[A, B], key: A): bool = return hasKey[A, B](t, key) proc hasKeyOrPut*[A, B](t: var Table[A, B], key: A, val: B): bool = - ## Returns true if ``key`` is in the table, otherwise inserts ``value``. + ## Returns true if `key` is in the table, otherwise inserts `value`. ## ## See also: ## * `hasKey proc<#hasKey,Table[A,B],A>`_ @@ -420,8 +401,8 @@ proc hasKeyOrPut*[A, B](t: var Table[A, B], key: A, val: B): bool = hasKeyOrPutImpl(enlarge) proc getOrDefault*[A, B](t: Table[A, B], key: A): B = - ## Retrieves the value at ``t[key]`` if ``key`` is in ``t``. Otherwise, the - ## default initialization value for type ``B`` is returned (e.g. 0 for any + ## Retrieves the value at `t[key]` if `key` is in `t`. Otherwise, the + ## default initialization value for type `B` is returned (e.g. 0 for any ## integer type). ## ## See also: @@ -435,12 +416,12 @@ proc getOrDefault*[A, B](t: Table[A, B], key: A): B = let a = {'a': 5, 'b': 9}.toTable doAssert a.getOrDefault('a') == 5 doAssert a.getOrDefault('z') == 0 - + result = default(B) getOrDefaultImpl(t, key) proc getOrDefault*[A, B](t: Table[A, B], key: A, default: B): B = - ## Retrieves the value at ``t[key]`` if ``key`` is in ``t``. - ## Otherwise, ``default`` is returned. + ## Retrieves the value at `t[key]` if `key` is in `t`. + ## Otherwise, `default` is returned. ## ## See also: ## * `[] proc<#[],Table[A,B],A>`_ for retrieving a value of a key @@ -453,16 +434,16 @@ proc getOrDefault*[A, B](t: Table[A, B], key: A, default: B): B = let a = {'a': 5, 'b': 9}.toTable doAssert a.getOrDefault('a', 99) == 5 doAssert a.getOrDefault('z', 99) == 99 - + result = default(B) getOrDefaultImpl(t, key, default) proc mgetOrPut*[A, B](t: var Table[A, B], key: A, val: B): var B = - ## Retrieves value at ``t[key]`` or puts ``val`` if not present, either way + ## Retrieves value at `t[key]` or puts `val` if not present, either way ## returning a value which can be modified. ## ## ## Note that while the value returned is of type `var B`, - ## it is easy to accidentally create an copy of the value at `t[key]`. + ## it is easy to accidentally create a copy of the value at `t[key]`. ## Remember that seqs and strings are value types, and therefore ## cannot be copied into a separate variable for modification. ## See the example below. @@ -494,8 +475,20 @@ proc mgetOrPut*[A, B](t: var Table[A, B], key: A, val: B): var B = mgetOrPutImpl(enlarge) +proc mgetOrPut*[A, B](t: var Table[A, B], key: A): var B = + ## Retrieves the value at `t[key]` or puts the + ## default initialization value for type `B` (e.g. 0 for any + ## integer type). + runnableExamples: + var a = {'a': 5}.newTable + doAssert a.mgetOrPut('a') == 5 + a.mgetOrPut('z').inc + doAssert a == {'a': 5, 'z': 1}.newTable + + mgetOrPutImpl(enlarge) + proc len*[A, B](t: Table[A, B]): int = - ## Returns the number of keys in ``t``. + ## Returns the number of keys in `t`. runnableExamples: let a = {'a': 5, 'b': 9}.toTable doAssert len(a) == 2 @@ -504,11 +497,11 @@ proc len*[A, B](t: Table[A, B]): int = proc add*[A, B](t: var Table[A, B], key: A, val: sink B) {.deprecated: "Deprecated since v1.4; it was more confusing than useful, use `[]=`".} = - ## Puts a new ``(key, value)`` pair into ``t`` even if ``t[key]`` already exists. + ## Puts a new `(key, value)` pair into `t` even if `t[key]` already exists. ## ## **This can introduce duplicate keys into the table!** ## - ## Use `[]= proc<#[]=,Table[A,B],A,B>`_ for inserting a new + ## Use `[]= proc<#[]=,Table[A,B],A,sinkB>`_ for inserting a new ## (key, value) pair in the table without introducing duplicates. addImpl(enlarge) @@ -517,7 +510,10 @@ template tabCellEmpty(i) = isEmpty(t.data[i].hcode) template tabCellHash(i) = t.data[i].hcode proc del*[A, B](t: var Table[A, B], key: A) = - ## Deletes ``key`` from hash table ``t``. Does nothing if the key does not exist. + ## Deletes `key` from hash table `t`. Does nothing if the key does not exist. + ## + ## .. warning:: If duplicate keys were added (via the now deprecated `add` proc), + ## this may need to be called multiple times. ## ## See also: ## * `pop proc<#pop,Table[A,B],A,B>`_ @@ -532,11 +528,14 @@ proc del*[A, B](t: var Table[A, B], key: A) = delImpl(tabMakeEmpty, tabCellEmpty, tabCellHash) proc pop*[A, B](t: var Table[A, B], key: A, val: var B): bool = - ## Deletes the ``key`` from the table. - ## Returns ``true``, if the ``key`` existed, and sets ``val`` to the - ## mapping of the key. Otherwise, returns ``false``, and the ``val`` is + ## Deletes the `key` from the table. + ## Returns `true`, if the `key` existed, and sets `val` to the + ## mapping of the key. Otherwise, returns `false`, and the `val` is ## unchanged. ## + ## .. warning:: If duplicate keys were added (via the now deprecated `add` proc), + ## this may need to be called multiple times. + ## ## See also: ## * `del proc<#del,Table[A,B],A>`_ ## * `clear proc<#clear,Table[A,B]>`_ to empty the whole table @@ -579,12 +578,12 @@ proc clear*[A, B](t: var Table[A, B]) = clearImpl() proc `$`*[A, B](t: Table[A, B]): string = - ## The ``$`` operator for hash tables. Used internally when calling `echo` + ## The `$` operator for hash tables. Used internally when calling `echo` ## on a table. dollarImpl() proc `==`*[A, B](s, t: Table[A, B]): bool = - ## The ``==`` operator for hash tables. Returns ``true`` if the content of both + ## The `==` operator for hash tables. Returns `true` if the content of both ## tables contains the same key-value pairs. Insert order does not matter. runnableExamples: let @@ -604,17 +603,31 @@ proc indexBy*[A, B, C](collection: A, index: proc(x: B): C): Table[C, B] = template withValue*[A, B](t: var Table[A, B], key: A, value, body: untyped) = - ## Retrieves the value at ``t[key]``. - ## - ## ``value`` can be modified in the scope of the ``withValue`` call. - ## - ## .. code-block:: nim - ## - ## sharedTable.withValue(key, value) do: - ## # block is executed only if ``key`` in ``t`` - ## value.name = "username" - ## value.uid = 1000 + ## Retrieves the value at `t[key]`. ## + ## `value` can be modified in the scope of the `withValue` call. + runnableExamples: + type + User = object + name: string + uid: int + + var t = initTable[int, User]() + let u = User(name: "Hello", uid: 99) + t[1] = u + + t.withValue(1, value): + # block is executed only if `key` in `t` + value.name = "Nim" + value.uid = 1314 + + t.withValue(2, value): + value.name = "No" + value.uid = 521 + + assert t[1].name == "Nim" + assert t[1].uid == 1314 + mixin rawGet var hc: Hash var index = rawGet(t, key, hc) @@ -625,20 +638,35 @@ template withValue*[A, B](t: var Table[A, B], key: A, value, body: untyped) = template withValue*[A, B](t: var Table[A, B], key: A, value, body1, body2: untyped) = - ## Retrieves the value at ``t[key]``. - ## - ## ``value`` can be modified in the scope of the ``withValue`` call. - ## - ## .. code-block:: nim - ## - ## table.withValue(key, value) do: - ## # block is executed only if ``key`` in ``t`` - ## value.name = "username" - ## value.uid = 1000 - ## do: - ## # block is executed when ``key`` not in ``t`` - ## raise newException(KeyError, "Key not found") + ## Retrieves the value at `t[key]`. ## + ## `value` can be modified in the scope of the `withValue` call. + runnableExamples: + type + User = object + name: string + uid: int + + var t = initTable[int, User]() + let u = User(name: "Hello", uid: 99) + t[1] = u + + t.withValue(1, value): + # block is executed only if `key` in `t` + value.name = "Nim" + value.uid = 1314 + + t.withValue(521, value): + doAssert false + do: + # block is executed when `key` not in `t` + t[1314] = User(name: "exist", uid: 521) + + assert t[1].name == "Nim" + assert t[1].uid == 1314 + assert t[1314].name == "exist" + assert t[1314].uid == 521 + mixin rawGet var hc: Hash var index = rawGet(t, key, hc) @@ -651,7 +679,7 @@ template withValue*[A, B](t: var Table[A, B], key: A, iterator pairs*[A, B](t: Table[A, B]): (A, B) = - ## Iterates over any ``(key, value)`` pair in the table ``t``. + ## Iterates over any `(key, value)` pair in the table `t`. ## ## See also: ## * `mpairs iterator<#mpairs.i,Table[A,B]>`_ @@ -660,7 +688,7 @@ iterator pairs*[A, B](t: Table[A, B]): (A, B) = ## ## **Examples:** ## - ## .. code-block:: + ## ```Nim ## let a = { ## 'o': [1, 5, 7, 9], ## 'e': [2, 4, 6, 8] @@ -674,6 +702,7 @@ iterator pairs*[A, B](t: Table[A, B]): (A, B) = ## # value: [2, 4, 6, 8] ## # key: o ## # value: [1, 5, 7, 9] + ## ``` let L = len(t) for h in 0 .. high(t.data): if isFilled(t.data[h].hcode): @@ -681,7 +710,7 @@ iterator pairs*[A, B](t: Table[A, B]): (A, B) = assert(len(t) == L, "the length of the table changed while iterating over it") iterator mpairs*[A, B](t: var Table[A, B]): (A, var B) = - ## Iterates over any ``(key, value)`` pair in the table ``t`` (must be + ## Iterates over any `(key, value)` pair in the table `t` (must be ## declared as `var`). The values can be modified. ## ## See also: @@ -702,8 +731,8 @@ iterator mpairs*[A, B](t: var Table[A, B]): (A, var B) = yield (t.data[h].key, t.data[h].val) assert(len(t) == L, "the length of the table changed while iterating over it") -iterator keys*[A, B](t: Table[A, B]): A = - ## Iterates over any key in the table ``t``. +iterator keys*[A, B](t: Table[A, B]): lent A = + ## Iterates over any key in the table `t`. ## ## See also: ## * `pairs iterator<#pairs.i,Table[A,B]>`_ @@ -723,8 +752,8 @@ iterator keys*[A, B](t: Table[A, B]): A = yield t.data[h].key assert(len(t) == L, "the length of the table changed while iterating over it") -iterator values*[A, B](t: Table[A, B]): B = - ## Iterates over any value in the table ``t``. +iterator values*[A, B](t: Table[A, B]): lent B = + ## Iterates over any value in the table `t`. ## ## See also: ## * `pairs iterator<#pairs.i,Table[A,B]>`_ @@ -745,7 +774,7 @@ iterator values*[A, B](t: Table[A, B]): B = assert(len(t) == L, "the length of the table changed while iterating over it") iterator mvalues*[A, B](t: var Table[A, B]): var B = - ## Iterates over any value in the table ``t`` (must be + ## Iterates over any value in the table `t` (must be ## declared as `var`). The values can be modified. ## ## See also: @@ -768,13 +797,13 @@ iterator mvalues*[A, B](t: var Table[A, B]): var B = iterator allValues*[A, B](t: Table[A, B]; key: A): B {.deprecated: "Deprecated since v1.4; tables with duplicated keys are deprecated".} = - ## Iterates over any value in the table ``t`` that belongs to the given ``key``. + ## Iterates over any value in the table `t` that belongs to the given `key`. ## ## Used if you have a table with duplicate keys (as a result of using ## `add proc<#add,Table[A,B],A,sinkB>`_). ## runnableExamples: - import sequtils, algorithm + import std/[sequtils, algorithm] var a = {'a': 3, 'b': 5}.toTable for i in 1..3: a.add('z', 10*i) @@ -795,7 +824,7 @@ iterator allValues*[A, B](t: Table[A, B]; key: A): B {.deprecated: # ------------------------------------------------------------------- -proc newTable*[A, B](initialSize = defaultInitialSize): <//>TableRef[A, B] = +proc newTable*[A, B](initialSize = defaultInitialSize): TableRef[A, B] = ## Creates a new ref hash table that is empty. ## ## See also: @@ -808,12 +837,13 @@ proc newTable*[A, B](initialSize = defaultInitialSize): <//>TableRef[A, B] = b = newTable[char, seq[int]]() new(result) - result[] = initTable[A, B](initialSize) + {.noSideEffect.}: + result[] = initTable[A, B](initialSize) -proc newTable*[A, B](pairs: openArray[(A, B)]): <//>TableRef[A, B] = - ## Creates a new ref hash table that contains the given ``pairs``. +proc newTable*[A, B](pairs: openArray[(A, B)]): TableRef[A, B] = + ## Creates a new ref hash table that contains the given `pairs`. ## - ## ``pairs`` is a container consisting of ``(key, value)`` tuples. + ## `pairs` is a container consisting of `(key, value)` tuples. ## ## See also: ## * `newTable proc<#newTable>`_ @@ -824,19 +854,21 @@ proc newTable*[A, B](pairs: openArray[(A, B)]): <//>TableRef[A, B] = assert b == {'a': 5, 'b': 9}.newTable new(result) - result[] = toTable[A, B](pairs) + {.noSideEffect.}: + result[] = toTable[A, B](pairs) -proc newTableFrom*[A, B, C](collection: A, index: proc(x: B): C): <//>TableRef[C, B] = +proc newTableFrom*[A, B, C](collection: A, index: proc(x: B): C): TableRef[C, B] = ## Index the collection with the proc provided. # TODO: As soon as supported, change collection: A to collection: A[B] result = newTable[C, B]() - for item in collection: - result[index(item)] = item + {.noSideEffect.}: + for item in collection: + result[index(item)] = item proc `[]`*[A, B](t: TableRef[A, B], key: A): var B = - ## Retrieves the value at ``t[key]``. + ## Retrieves the value at `t[key]`. ## - ## If ``key`` is not in ``t``, the ``KeyError`` exception is raised. + ## If `key` is not in `t`, the `KeyError` exception is raised. ## One can check with `hasKey proc<#hasKey,TableRef[A,B],A>`_ whether ## the key exists. ## @@ -858,7 +890,7 @@ proc `[]`*[A, B](t: TableRef[A, B], key: A): var B = result = t[][key] proc `[]=`*[A, B](t: TableRef[A, B], key: A, val: sink B) = - ## Inserts a ``(key, value)`` pair into ``t``. + ## Inserts a `(key, value)` pair into `t`. ## ## See also: ## * `[] proc<#[],TableRef[A,B],A>`_ for retrieving a value of a key @@ -874,7 +906,7 @@ proc `[]=`*[A, B](t: TableRef[A, B], key: A, val: sink B) = t[][key] = val proc hasKey*[A, B](t: TableRef[A, B], key: A): bool = - ## Returns true if ``key`` is in the table ``t``. + ## Returns true if `key` is in the table `t`. ## ## See also: ## * `contains proc<#contains,TableRef[A,B],A>`_ for use with the `in` @@ -893,7 +925,7 @@ proc hasKey*[A, B](t: TableRef[A, B], key: A): bool = proc contains*[A, B](t: TableRef[A, B], key: A): bool = ## Alias of `hasKey proc<#hasKey,TableRef[A,B],A>`_ for use with - ## the ``in`` operator. + ## the `in` operator. runnableExamples: let a = {'a': 5, 'b': 9}.newTable doAssert 'b' in a == true @@ -901,8 +933,8 @@ proc contains*[A, B](t: TableRef[A, B], key: A): bool = return hasKey[A, B](t, key) -proc hasKeyOrPut*[A, B](t: var TableRef[A, B], key: A, val: B): bool = - ## Returns true if ``key`` is in the table, otherwise inserts ``value``. +proc hasKeyOrPut*[A, B](t: TableRef[A, B], key: A, val: B): bool = + ## Returns true if `key` is in the table, otherwise inserts `value`. ## ## See also: ## * `hasKey proc<#hasKey,TableRef[A,B],A>`_ @@ -922,8 +954,8 @@ proc hasKeyOrPut*[A, B](t: var TableRef[A, B], key: A, val: B): bool = t[].hasKeyOrPut(key, val) proc getOrDefault*[A, B](t: TableRef[A, B], key: A): B = - ## Retrieves the value at ``t[key]`` if ``key`` is in ``t``. Otherwise, the - ## default initialization value for type ``B`` is returned (e.g. 0 for any + ## Retrieves the value at `t[key]` if `key` is in `t`. Otherwise, the + ## default initialization value for type `B` is returned (e.g. 0 for any ## integer type). ## ## See also: @@ -941,8 +973,8 @@ proc getOrDefault*[A, B](t: TableRef[A, B], key: A): B = getOrDefault(t[], key) proc getOrDefault*[A, B](t: TableRef[A, B], key: A, default: B): B = - ## Retrieves the value at ``t[key]`` if ``key`` is in ``t``. - ## Otherwise, ``default`` is returned. + ## Retrieves the value at `t[key]` if `key` is in `t`. + ## Otherwise, `default` is returned. ## ## See also: ## * `[] proc<#[],TableRef[A,B],A>`_ for retrieving a value of a key @@ -959,7 +991,7 @@ proc getOrDefault*[A, B](t: TableRef[A, B], key: A, default: B): B = getOrDefault(t[], key, default) proc mgetOrPut*[A, B](t: TableRef[A, B], key: A, val: B): var B = - ## Retrieves value at ``t[key]`` or puts ``val`` if not present, either way + ## Retrieves value at `t[key]` or puts `val` if not present, either way ## returning a value which can be modified. ## ## Note that while the value returned is of type `var B`, @@ -994,8 +1026,20 @@ proc mgetOrPut*[A, B](t: TableRef[A, B], key: A, val: B): var B = doAssert t[25] == @[25, 35] t[].mgetOrPut(key, val) +proc mgetOrPut*[A, B](t: TableRef[A, B], key: A): var B = + ## Retrieves the value at `t[key]` or puts the + ## default initialization value for type `B` (e.g. 0 for any + ## integer type). + runnableExamples: + var a = {'a': 5}.newTable + doAssert a.mgetOrPut('a') == 5 + a.mgetOrPut('z').inc + doAssert a == {'a': 5, 'z': 1}.newTable + + t[].mgetOrPut(key) + proc len*[A, B](t: TableRef[A, B]): int = - ## Returns the number of keys in ``t``. + ## Returns the number of keys in `t`. runnableExamples: let a = {'a': 5, 'b': 9}.newTable doAssert len(a) == 2 @@ -1004,7 +1048,7 @@ proc len*[A, B](t: TableRef[A, B]): int = proc add*[A, B](t: TableRef[A, B], key: A, val: sink B) {.deprecated: "Deprecated since v1.4; it was more confusing than useful, use `[]=`".} = - ## Puts a new ``(key, value)`` pair into ``t`` even if ``t[key]`` already exists. + ## Puts a new `(key, value)` pair into `t` even if `t[key]` already exists. ## ## **This can introduce duplicate keys into the table!** ## @@ -1013,9 +1057,10 @@ proc add*[A, B](t: TableRef[A, B], key: A, val: sink B) {.deprecated: t[].add(key, val) proc del*[A, B](t: TableRef[A, B], key: A) = - ## Deletes ``key`` from hash table ``t``. Does nothing if the key does not exist. + ## Deletes `key` from hash table `t`. Does nothing if the key does not exist. ## - ## **If duplicate keys were added, this may need to be called multiple times.** + ## .. warning:: If duplicate keys were added (via the now deprecated `add` proc), + ## this may need to be called multiple times. ## ## See also: ## * `pop proc<#pop,TableRef[A,B],A,B>`_ @@ -1030,12 +1075,13 @@ proc del*[A, B](t: TableRef[A, B], key: A) = t[].del(key) proc pop*[A, B](t: TableRef[A, B], key: A, val: var B): bool = - ## Deletes the ``key`` from the table. - ## Returns ``true``, if the ``key`` existed, and sets ``val`` to the - ## mapping of the key. Otherwise, returns ``false``, and the ``val`` is + ## Deletes the `key` from the table. + ## Returns `true`, if the `key` existed, and sets `val` to the + ## mapping of the key. Otherwise, returns `false`, and the `val` is ## unchanged. ## - ## **If duplicate keys were added, this may need to be called multiple times.** + ## .. warning:: If duplicate keys were added (via the now deprecated `add` proc), + ## this may need to be called multiple times. ## ## See also: ## * `del proc<#del,TableRef[A,B],A>`_ @@ -1074,13 +1120,13 @@ proc clear*[A, B](t: TableRef[A, B]) = clearImpl() proc `$`*[A, B](t: TableRef[A, B]): string = - ## The ``$`` operator for hash tables. Used internally when calling `echo` + ## The `$` operator for hash tables. Used internally when calling `echo` ## on a table. dollarImpl() proc `==`*[A, B](s, t: TableRef[A, B]): bool = - ## The ``==`` operator for hash tables. Returns ``true`` if either both tables - ## are ``nil``, or neither is ``nil`` and the content of both tables contains the + ## The `==` operator for hash tables. Returns `true` if either both tables + ## are `nil`, or neither is `nil` and the content of both tables contains the ## same key-value pairs. Insert order does not matter. runnableExamples: let @@ -1095,7 +1141,7 @@ proc `==`*[A, B](s, t: TableRef[A, B]): bool = iterator pairs*[A, B](t: TableRef[A, B]): (A, B) = - ## Iterates over any ``(key, value)`` pair in the table ``t``. + ## Iterates over any `(key, value)` pair in the table `t`. ## ## See also: ## * `mpairs iterator<#mpairs.i,TableRef[A,B]>`_ @@ -1104,7 +1150,7 @@ iterator pairs*[A, B](t: TableRef[A, B]): (A, B) = ## ## **Examples:** ## - ## .. code-block:: + ## ```Nim ## let a = { ## 'o': [1, 5, 7, 9], ## 'e': [2, 4, 6, 8] @@ -1118,6 +1164,7 @@ iterator pairs*[A, B](t: TableRef[A, B]): (A, B) = ## # value: [2, 4, 6, 8] ## # key: o ## # value: [1, 5, 7, 9] + ## ``` let L = len(t) for h in 0 .. high(t.data): if isFilled(t.data[h].hcode): @@ -1125,7 +1172,7 @@ iterator pairs*[A, B](t: TableRef[A, B]): (A, B) = assert(len(t) == L, "the length of the table changed while iterating over it") iterator mpairs*[A, B](t: TableRef[A, B]): (A, var B) = - ## Iterates over any ``(key, value)`` pair in the table ``t``. The values + ## Iterates over any `(key, value)` pair in the table `t`. The values ## can be modified. ## ## See also: @@ -1146,8 +1193,8 @@ iterator mpairs*[A, B](t: TableRef[A, B]): (A, var B) = yield (t.data[h].key, t.data[h].val) assert(len(t) == L, "the length of the table changed while iterating over it") -iterator keys*[A, B](t: TableRef[A, B]): A = - ## Iterates over any key in the table ``t``. +iterator keys*[A, B](t: TableRef[A, B]): lent A = + ## Iterates over any key in the table `t`. ## ## See also: ## * `pairs iterator<#pairs.i,TableRef[A,B]>`_ @@ -1167,8 +1214,8 @@ iterator keys*[A, B](t: TableRef[A, B]): A = yield t.data[h].key assert(len(t) == L, "the length of the table changed while iterating over it") -iterator values*[A, B](t: TableRef[A, B]): B = - ## Iterates over any value in the table ``t``. +iterator values*[A, B](t: TableRef[A, B]): lent B = + ## Iterates over any value in the table `t`. ## ## See also: ## * `pairs iterator<#pairs.i,TableRef[A,B]>`_ @@ -1189,7 +1236,7 @@ iterator values*[A, B](t: TableRef[A, B]): B = assert(len(t) == L, "the length of the table changed while iterating over it") iterator mvalues*[A, B](t: TableRef[A, B]): var B = - ## Iterates over any value in the table ``t``. The values can be modified. + ## Iterates over any value in the table `t`. The values can be modified. ## ## See also: ## * `mpairs iterator<#mpairs.i,TableRef[A,B]>`_ @@ -1300,10 +1347,11 @@ proc initOrderedTable*[A, B](initialSize = defaultInitialSize): OrderedTable[A, let a = initOrderedTable[int, string]() b = initOrderedTable[char, seq[int]]() + result = default(OrderedTable[A, B]) initImpl(result, initialSize) proc `[]=`*[A, B](t: var OrderedTable[A, B], key: A, val: sink B) = - ## Inserts a ``(key, value)`` pair into ``t``. + ## Inserts a `(key, value)` pair into `t`. ## ## See also: ## * `[] proc<#[],OrderedTable[A,B],A>`_ for retrieving a value of a key @@ -1319,9 +1367,9 @@ proc `[]=`*[A, B](t: var OrderedTable[A, B], key: A, val: sink B) = putImpl(enlarge) proc toOrderedTable*[A, B](pairs: openArray[(A, B)]): OrderedTable[A, B] = - ## Creates a new ordered hash table that contains the given ``pairs``. + ## Creates a new ordered hash table that contains the given `pairs`. ## - ## ``pairs`` is a container consisting of ``(key, value)`` tuples. + ## `pairs` is a container consisting of `(key, value)` tuples. ## ## See also: ## * `initOrderedTable proc<#initOrderedTable>`_ @@ -1335,10 +1383,10 @@ proc toOrderedTable*[A, B](pairs: openArray[(A, B)]): OrderedTable[A, B] = result = initOrderedTable[A, B](pairs.len) for key, val in items(pairs): result[key] = val -proc `[]`*[A, B](t: OrderedTable[A, B], key: A): B = - ## Retrieves the value at ``t[key]``. +proc `[]`*[A, B](t: OrderedTable[A, B], key: A): lent B = + ## Retrieves the value at `t[key]`. ## - ## If ``key`` is not in ``t``, the ``KeyError`` exception is raised. + ## If `key` is not in `t`, the `KeyError` exception is raised. ## One can check with `hasKey proc<#hasKey,OrderedTable[A,B],A>`_ whether ## the key exists. ## @@ -1360,9 +1408,9 @@ proc `[]`*[A, B](t: OrderedTable[A, B], key: A): B = get(t, key) proc `[]`*[A, B](t: var OrderedTable[A, B], key: A): var B = - ## Retrieves the value at ``t[key]``. The value can be modified. + ## Retrieves the value at `t[key]`. The value can be modified. ## - ## If ``key`` is not in ``t``, the ``KeyError`` exception is raised. + ## If `key` is not in `t`, the `KeyError` exception is raised. ## ## See also: ## * `getOrDefault proc<#getOrDefault,OrderedTable[A,B],A>`_ to return @@ -1376,7 +1424,7 @@ proc `[]`*[A, B](t: var OrderedTable[A, B], key: A): var B = get(t, key) proc hasKey*[A, B](t: OrderedTable[A, B], key: A): bool = - ## Returns true if ``key`` is in the table ``t``. + ## Returns true if `key` is in the table `t`. ## ## See also: ## * `contains proc<#contains,OrderedTable[A,B],A>`_ for use with the `in` @@ -1391,12 +1439,12 @@ proc hasKey*[A, B](t: OrderedTable[A, B], key: A): bool = doAssert a.hasKey('a') == true doAssert a.hasKey('z') == false - var hc: Hash + var hc: Hash = default(Hash) result = rawGet(t, key, hc) >= 0 proc contains*[A, B](t: OrderedTable[A, B], key: A): bool = ## Alias of `hasKey proc<#hasKey,OrderedTable[A,B],A>`_ for use with - ## the ``in`` operator. + ## the `in` operator. runnableExamples: let a = {'a': 5, 'b': 9}.toOrderedTable doAssert 'b' in a == true @@ -1405,7 +1453,7 @@ proc contains*[A, B](t: OrderedTable[A, B], key: A): bool = return hasKey[A, B](t, key) proc hasKeyOrPut*[A, B](t: var OrderedTable[A, B], key: A, val: B): bool = - ## Returns true if ``key`` is in the table, otherwise inserts ``value``. + ## Returns true if `key` is in the table, otherwise inserts `value`. ## ## See also: ## * `hasKey proc<#hasKey,OrderedTable[A,B],A>`_ @@ -1425,8 +1473,8 @@ proc hasKeyOrPut*[A, B](t: var OrderedTable[A, B], key: A, val: B): bool = hasKeyOrPutImpl(enlarge) proc getOrDefault*[A, B](t: OrderedTable[A, B], key: A): B = - ## Retrieves the value at ``t[key]`` if ``key`` is in ``t``. Otherwise, the - ## default initialization value for type ``B`` is returned (e.g. 0 for any + ## Retrieves the value at `t[key]` if `key` is in `t`. Otherwise, the + ## default initialization value for type `B` is returned (e.g. 0 for any ## integer type). ## ## See also: @@ -1440,12 +1488,12 @@ proc getOrDefault*[A, B](t: OrderedTable[A, B], key: A): B = let a = {'a': 5, 'b': 9}.toOrderedTable doAssert a.getOrDefault('a') == 5 doAssert a.getOrDefault('z') == 0 - + result = default(B) getOrDefaultImpl(t, key) proc getOrDefault*[A, B](t: OrderedTable[A, B], key: A, default: B): B = - ## Retrieves the value at ``t[key]`` if ``key`` is in ``t``. - ## Otherwise, ``default`` is returned. + ## Retrieves the value at `t[key]` if `key` is in `t`. + ## Otherwise, `default` is returned. ## ## See also: ## * `[] proc<#[],OrderedTable[A,B],A>`_ for retrieving a value of a key @@ -1458,11 +1506,11 @@ proc getOrDefault*[A, B](t: OrderedTable[A, B], key: A, default: B): B = let a = {'a': 5, 'b': 9}.toOrderedTable doAssert a.getOrDefault('a', 99) == 5 doAssert a.getOrDefault('z', 99) == 99 - + result = default(B) getOrDefaultImpl(t, key, default) proc mgetOrPut*[A, B](t: var OrderedTable[A, B], key: A, val: B): var B = - ## Retrieves value at ``t[key]`` or puts ``val`` if not present, either way + ## Retrieves value at `t[key]` or puts `val` if not present, either way ## returning a value which can be modified. ## ## See also: @@ -1481,8 +1529,20 @@ proc mgetOrPut*[A, B](t: var OrderedTable[A, B], key: A, val: B): var B = mgetOrPutImpl(enlarge) +proc mgetOrPut*[A, B](t: var OrderedTable[A, B], key: A): var B = + ## Retrieves the value at `t[key]` or puts the + ## default initialization value for type `B` (e.g. 0 for any + ## integer type). + runnableExamples: + var a = {'a': 5}.toOrderedTable + doAssert a.mgetOrPut('a') == 5 + a.mgetOrPut('z').inc + doAssert a == {'a': 5, 'z': 1}.toOrderedTable + + mgetOrPutImpl(enlarge) + proc len*[A, B](t: OrderedTable[A, B]): int {.inline.} = - ## Returns the number of keys in ``t``. + ## Returns the number of keys in `t`. runnableExamples: let a = {'a': 5, 'b': 9}.toOrderedTable doAssert len(a) == 2 @@ -1491,7 +1551,7 @@ proc len*[A, B](t: OrderedTable[A, B]): int {.inline.} = proc add*[A, B](t: var OrderedTable[A, B], key: A, val: sink B) {.deprecated: "Deprecated since v1.4; it was more confusing than useful, use `[]=`".} = - ## Puts a new ``(key, value)`` pair into ``t`` even if ``t[key]`` already exists. + ## Puts a new `(key, value)` pair into `t` even if `t[key]` already exists. ## ## **This can introduce duplicate keys into the table!** ## @@ -1500,7 +1560,7 @@ proc add*[A, B](t: var OrderedTable[A, B], key: A, val: sink B) {.deprecated: addImpl(enlarge) proc del*[A, B](t: var OrderedTable[A, B], key: A) = - ## Deletes ``key`` from hash table ``t``. Does nothing if the key does not exist. + ## Deletes `key` from hash table `t`. Does nothing if the key does not exist. ## ## O(n) complexity. ## @@ -1533,9 +1593,9 @@ proc del*[A, B](t: var OrderedTable[A, B], key: A) = h = nxt proc pop*[A, B](t: var OrderedTable[A, B], key: A, val: var B): bool {.since: (1, 1).} = - ## Deletes the ``key`` from the table. - ## Returns ``true``, if the ``key`` existed, and sets ``val`` to the - ## mapping of the key. Otherwise, returns ``false``, and the ``val`` is + ## Deletes the `key` from the table. + ## Returns `true`, if the `key` existed, and sets `val` to the + ## mapping of the key. Otherwise, returns `false`, and the `val` is ## unchanged. ## ## O(n) complexity. @@ -1579,15 +1639,15 @@ proc clear*[A, B](t: var OrderedTable[A, B]) = t.last = -1 proc sort*[A, B](t: var OrderedTable[A, B], cmp: proc (x, y: (A, B)): int, - order = SortOrder.Ascending) = - ## Sorts ``t`` according to the function ``cmp``. + order = SortOrder.Ascending) {.effectsOf: cmp.} = + ## Sorts `t` according to the function `cmp`. ## ## This modifies the internal list ## that kept the insertion order, so insertion order is lost after this - ## call but key lookup and insertions remain possible after ``sort`` (in + ## call but key lookup and insertions remain possible after `sort` (in ## contrast to the `sort proc<#sort,CountTable[A]>`_ for count tables). runnableExamples: - import algorithm + import std/[algorithm] var a = initOrderedTable[char, int]() for i, c in "cab": a[c] = 10*i @@ -1638,12 +1698,12 @@ proc sort*[A, B](t: var OrderedTable[A, B], cmp: proc (x, y: (A, B)): int, t.last = tail proc `$`*[A, B](t: OrderedTable[A, B]): string = - ## The ``$`` operator for ordered hash tables. Used internally when calling + ## The `$` operator for ordered hash tables. Used internally when calling ## `echo` on a table. dollarImpl() proc `==`*[A, B](s, t: OrderedTable[A, B]): bool = - ## The ``==`` operator for ordered hash tables. Returns ``true`` if both the + ## The `==` operator for ordered hash tables. Returns `true` if both the ## content and the order are equal. runnableExamples: let @@ -1670,7 +1730,7 @@ proc `==`*[A, B](s, t: OrderedTable[A, B]): bool = iterator pairs*[A, B](t: OrderedTable[A, B]): (A, B) = - ## Iterates over any ``(key, value)`` pair in the table ``t`` in insertion + ## Iterates over any `(key, value)` pair in the table `t` in insertion ## order. ## ## See also: @@ -1680,7 +1740,7 @@ iterator pairs*[A, B](t: OrderedTable[A, B]): (A, B) = ## ## **Examples:** ## - ## .. code-block:: + ## ```Nim ## let a = { ## 'o': [1, 5, 7, 9], ## 'e': [2, 4, 6, 8] @@ -1694,6 +1754,7 @@ iterator pairs*[A, B](t: OrderedTable[A, B]): (A, B) = ## # value: [1, 5, 7, 9] ## # key: e ## # value: [2, 4, 6, 8] + ## ``` let L = len(t) forAllOrderedPairs: @@ -1701,7 +1762,7 @@ iterator pairs*[A, B](t: OrderedTable[A, B]): (A, B) = assert(len(t) == L, "the length of the table changed while iterating over it") iterator mpairs*[A, B](t: var OrderedTable[A, B]): (A, var B) = - ## Iterates over any ``(key, value)`` pair in the table ``t`` (must be + ## Iterates over any `(key, value)` pair in the table `t` (must be ## declared as `var`) in insertion order. The values can be modified. ## ## See also: @@ -1722,8 +1783,8 @@ iterator mpairs*[A, B](t: var OrderedTable[A, B]): (A, var B) = yield (t.data[h].key, t.data[h].val) assert(len(t) == L, "the length of the table changed while iterating over it") -iterator keys*[A, B](t: OrderedTable[A, B]): A = - ## Iterates over any key in the table ``t`` in insertion order. +iterator keys*[A, B](t: OrderedTable[A, B]): lent A = + ## Iterates over any key in the table `t` in insertion order. ## ## See also: ## * `pairs iterator<#pairs.i,OrderedTable[A,B]>`_ @@ -1743,8 +1804,8 @@ iterator keys*[A, B](t: OrderedTable[A, B]): A = yield t.data[h].key assert(len(t) == L, "the length of the table changed while iterating over it") -iterator values*[A, B](t: OrderedTable[A, B]): B = - ## Iterates over any value in the table ``t`` in insertion order. +iterator values*[A, B](t: OrderedTable[A, B]): lent B = + ## Iterates over any value in the table `t` in insertion order. ## ## See also: ## * `pairs iterator<#pairs.i,OrderedTable[A,B]>`_ @@ -1764,7 +1825,7 @@ iterator values*[A, B](t: OrderedTable[A, B]): B = assert(len(t) == L, "the length of the table changed while iterating over it") iterator mvalues*[A, B](t: var OrderedTable[A, B]): var B = - ## Iterates over any value in the table ``t`` (must be + ## Iterates over any value in the table `t` (must be ## declared as `var`) in insertion order. The values ## can be modified. ## @@ -1790,7 +1851,7 @@ iterator mvalues*[A, B](t: var OrderedTable[A, B]): var B = # --------------------------- OrderedTableRef ------------------------------- # --------------------------------------------------------------------------- -proc newOrderedTable*[A, B](initialSize = defaultInitialSize): <//>OrderedTableRef[A, B] = +proc newOrderedTable*[A, B](initialSize = defaultInitialSize): OrderedTableRef[A, B] = ## Creates a new ordered ref hash table that is empty. ## ## See also: @@ -1803,12 +1864,13 @@ proc newOrderedTable*[A, B](initialSize = defaultInitialSize): <//>OrderedTableR a = newOrderedTable[int, string]() b = newOrderedTable[char, seq[int]]() new(result) - result[] = initOrderedTable[A, B](initialSize) + {.noSideEffect.}: + result[] = initOrderedTable[A, B](initialSize) -proc newOrderedTable*[A, B](pairs: openArray[(A, B)]): <//>OrderedTableRef[A, B] = - ## Creates a new ordered ref hash table that contains the given ``pairs``. +proc newOrderedTable*[A, B](pairs: openArray[(A, B)]): OrderedTableRef[A, B] = + ## Creates a new ordered ref hash table that contains the given `pairs`. ## - ## ``pairs`` is a container consisting of ``(key, value)`` tuples. + ## `pairs` is a container consisting of `(key, value)` tuples. ## ## See also: ## * `newOrderedTable proc<#newOrderedTable>`_ @@ -1820,13 +1882,14 @@ proc newOrderedTable*[A, B](pairs: openArray[(A, B)]): <//>OrderedTableRef[A, B] assert b == {'a': 5, 'b': 9}.newOrderedTable result = newOrderedTable[A, B](pairs.len) - for key, val in items(pairs): result[key] = val + {.noSideEffect.}: + for key, val in items(pairs): result[key] = val proc `[]`*[A, B](t: OrderedTableRef[A, B], key: A): var B = - ## Retrieves the value at ``t[key]``. + ## Retrieves the value at `t[key]`. ## - ## If ``key`` is not in ``t``, the ``KeyError`` exception is raised. + ## If `key` is not in `t`, the `KeyError` exception is raised. ## One can check with `hasKey proc<#hasKey,OrderedTableRef[A,B],A>`_ whether ## the key exists. ## @@ -1847,7 +1910,7 @@ proc `[]`*[A, B](t: OrderedTableRef[A, B], key: A): var B = result = t[][key] proc `[]=`*[A, B](t: OrderedTableRef[A, B], key: A, val: sink B) = - ## Inserts a ``(key, value)`` pair into ``t``. + ## Inserts a `(key, value)` pair into `t`. ## ## See also: ## * `[] proc<#[],OrderedTableRef[A,B],A>`_ for retrieving a value of a key @@ -1863,7 +1926,7 @@ proc `[]=`*[A, B](t: OrderedTableRef[A, B], key: A, val: sink B) = t[][key] = val proc hasKey*[A, B](t: OrderedTableRef[A, B], key: A): bool = - ## Returns true if ``key`` is in the table ``t``. + ## Returns true if `key` is in the table `t`. ## ## See also: ## * `contains proc<#contains,OrderedTableRef[A,B],A>`_ for use with the `in` @@ -1882,7 +1945,7 @@ proc hasKey*[A, B](t: OrderedTableRef[A, B], key: A): bool = proc contains*[A, B](t: OrderedTableRef[A, B], key: A): bool = ## Alias of `hasKey proc<#hasKey,OrderedTableRef[A,B],A>`_ for use with - ## the ``in`` operator. + ## the `in` operator. runnableExamples: let a = {'a': 5, 'b': 9}.newOrderedTable doAssert 'b' in a == true @@ -1890,8 +1953,8 @@ proc contains*[A, B](t: OrderedTableRef[A, B], key: A): bool = return hasKey[A, B](t, key) -proc hasKeyOrPut*[A, B](t: var OrderedTableRef[A, B], key: A, val: B): bool = - ## Returns true if ``key`` is in the table, otherwise inserts ``value``. +proc hasKeyOrPut*[A, B](t: OrderedTableRef[A, B], key: A, val: B): bool = + ## Returns true if `key` is in the table, otherwise inserts `value`. ## ## See also: ## * `hasKey proc<#hasKey,OrderedTableRef[A,B],A>`_ @@ -1911,8 +1974,8 @@ proc hasKeyOrPut*[A, B](t: var OrderedTableRef[A, B], key: A, val: B): bool = result = t[].hasKeyOrPut(key, val) proc getOrDefault*[A, B](t: OrderedTableRef[A, B], key: A): B = - ## Retrieves the value at ``t[key]`` if ``key`` is in ``t``. Otherwise, the - ## default initialization value for type ``B`` is returned (e.g. 0 for any + ## Retrieves the value at `t[key]` if `key` is in `t`. Otherwise, the + ## default initialization value for type `B` is returned (e.g. 0 for any ## integer type). ## ## See also: @@ -1930,8 +1993,8 @@ proc getOrDefault*[A, B](t: OrderedTableRef[A, B], key: A): B = getOrDefault(t[], key) proc getOrDefault*[A, B](t: OrderedTableRef[A, B], key: A, default: B): B = - ## Retrieves the value at ``t[key]`` if ``key`` is in ``t``. - ## Otherwise, ``default`` is returned. + ## Retrieves the value at `t[key]` if `key` is in `t`. + ## Otherwise, `default` is returned. ## ## See also: ## * `[] proc<#[],OrderedTableRef[A,B],A>`_ for retrieving a value of a key @@ -1948,7 +2011,7 @@ proc getOrDefault*[A, B](t: OrderedTableRef[A, B], key: A, default: B): B = getOrDefault(t[], key, default) proc mgetOrPut*[A, B](t: OrderedTableRef[A, B], key: A, val: B): var B = - ## Retrieves value at ``t[key]`` or puts ``val`` if not present, either way + ## Retrieves value at `t[key]` or puts `val` if not present, either way ## returning a value which can be modified. ## ## See also: @@ -1967,8 +2030,20 @@ proc mgetOrPut*[A, B](t: OrderedTableRef[A, B], key: A, val: B): var B = result = t[].mgetOrPut(key, val) +proc mgetOrPut*[A, B](t: OrderedTableRef[A, B], key: A): var B = + ## Retrieves the value at `t[key]` or puts the + ## default initialization value for type `B` (e.g. 0 for any + ## integer type). + runnableExamples: + var a = {'a': 5}.toOrderedTable + doAssert a.mgetOrPut('a') == 5 + a.mgetOrPut('z').inc + doAssert a == {'a': 5, 'z': 1}.toOrderedTable + + t[].mgetOrPut(key) + proc len*[A, B](t: OrderedTableRef[A, B]): int {.inline.} = - ## Returns the number of keys in ``t``. + ## Returns the number of keys in `t`. runnableExamples: let a = {'a': 5, 'b': 9}.newOrderedTable doAssert len(a) == 2 @@ -1977,7 +2052,7 @@ proc len*[A, B](t: OrderedTableRef[A, B]): int {.inline.} = proc add*[A, B](t: OrderedTableRef[A, B], key: A, val: sink B) {.deprecated: "Deprecated since v1.4; it was more confusing than useful, use `[]=`".} = - ## Puts a new ``(key, value)`` pair into ``t`` even if ``t[key]`` already exists. + ## Puts a new `(key, value)` pair into `t` even if `t[key]` already exists. ## ## **This can introduce duplicate keys into the table!** ## @@ -1986,7 +2061,7 @@ proc add*[A, B](t: OrderedTableRef[A, B], key: A, val: sink B) {.deprecated: t[].add(key, val) proc del*[A, B](t: OrderedTableRef[A, B], key: A) = - ## Deletes ``key`` from hash table ``t``. Does nothing if the key does not exist. + ## Deletes `key` from hash table `t`. Does nothing if the key does not exist. ## ## See also: ## * `clear proc<#clear,OrderedTableRef[A,B]>`_ to empty the whole table @@ -2000,9 +2075,9 @@ proc del*[A, B](t: OrderedTableRef[A, B], key: A) = t[].del(key) proc pop*[A, B](t: OrderedTableRef[A, B], key: A, val: var B): bool {.since: (1, 1).} = - ## Deletes the ``key`` from the table. - ## Returns ``true``, if the ``key`` existed, and sets ``val`` to the - ## mapping of the key. Otherwise, returns ``false``, and the ``val`` is + ## Deletes the `key` from the table. + ## Returns `true`, if the `key` existed, and sets `val` to the + ## mapping of the key. Otherwise, returns `false`, and the `val` is ## unchanged. ## ## See also: @@ -2036,15 +2111,15 @@ proc clear*[A, B](t: OrderedTableRef[A, B]) = clear(t[]) proc sort*[A, B](t: OrderedTableRef[A, B], cmp: proc (x, y: (A, B)): int, - order = SortOrder.Ascending) = - ## Sorts ``t`` according to the function ``cmp``. + order = SortOrder.Ascending) {.effectsOf: cmp.} = + ## Sorts `t` according to the function `cmp`. ## ## This modifies the internal list ## that kept the insertion order, so insertion order is lost after this - ## call but key lookup and insertions remain possible after ``sort`` (in + ## call but key lookup and insertions remain possible after `sort` (in ## contrast to the `sort proc<#sort,CountTableRef[A]>`_ for count tables). runnableExamples: - import algorithm + import std/[algorithm] var a = newOrderedTable[char, int]() for i, c in "cab": a[c] = 10*i @@ -2057,13 +2132,13 @@ proc sort*[A, B](t: OrderedTableRef[A, B], cmp: proc (x, y: (A, B)): int, t[].sort(cmp, order = order) proc `$`*[A, B](t: OrderedTableRef[A, B]): string = - ## The ``$`` operator for hash tables. Used internally when calling `echo` + ## The `$` operator for hash tables. Used internally when calling `echo` ## on a table. dollarImpl() proc `==`*[A, B](s, t: OrderedTableRef[A, B]): bool = - ## The ``==`` operator for ordered hash tables. Returns true if either both - ## tables are ``nil``, or neither is ``nil`` and the content and the order of + ## The `==` operator for ordered hash tables. Returns true if either both + ## tables are `nil`, or neither is `nil` and the content and the order of ## both are equal. runnableExamples: let @@ -2078,7 +2153,7 @@ proc `==`*[A, B](s, t: OrderedTableRef[A, B]): bool = iterator pairs*[A, B](t: OrderedTableRef[A, B]): (A, B) = - ## Iterates over any ``(key, value)`` pair in the table ``t`` in insertion + ## Iterates over any `(key, value)` pair in the table `t` in insertion ## order. ## ## See also: @@ -2088,7 +2163,7 @@ iterator pairs*[A, B](t: OrderedTableRef[A, B]): (A, B) = ## ## **Examples:** ## - ## .. code-block:: + ## ```Nim ## let a = { ## 'o': [1, 5, 7, 9], ## 'e': [2, 4, 6, 8] @@ -2102,6 +2177,7 @@ iterator pairs*[A, B](t: OrderedTableRef[A, B]): (A, B) = ## # value: [1, 5, 7, 9] ## # key: e ## # value: [2, 4, 6, 8] + ## ``` let L = len(t) forAllOrderedPairs: @@ -2109,7 +2185,7 @@ iterator pairs*[A, B](t: OrderedTableRef[A, B]): (A, B) = assert(len(t) == L, "the length of the table changed while iterating over it") iterator mpairs*[A, B](t: OrderedTableRef[A, B]): (A, var B) = - ## Iterates over any ``(key, value)`` pair in the table ``t`` in insertion + ## Iterates over any `(key, value)` pair in the table `t` in insertion ## order. The values can be modified. ## ## See also: @@ -2130,8 +2206,8 @@ iterator mpairs*[A, B](t: OrderedTableRef[A, B]): (A, var B) = yield (t.data[h].key, t.data[h].val) assert(len(t) == L, "the length of the table changed while iterating over it") -iterator keys*[A, B](t: OrderedTableRef[A, B]): A = - ## Iterates over any key in the table ``t`` in insertion order. +iterator keys*[A, B](t: OrderedTableRef[A, B]): lent A = + ## Iterates over any key in the table `t` in insertion order. ## ## See also: ## * `pairs iterator<#pairs.i,OrderedTableRef[A,B]>`_ @@ -2151,8 +2227,8 @@ iterator keys*[A, B](t: OrderedTableRef[A, B]): A = yield t.data[h].key assert(len(t) == L, "the length of the table changed while iterating over it") -iterator values*[A, B](t: OrderedTableRef[A, B]): B = - ## Iterates over any value in the table ``t`` in insertion order. +iterator values*[A, B](t: OrderedTableRef[A, B]): lent B = + ## Iterates over any value in the table `t` in insertion order. ## ## See also: ## * `pairs iterator<#pairs.i,OrderedTableRef[A,B]>`_ @@ -2172,7 +2248,7 @@ iterator values*[A, B](t: OrderedTableRef[A, B]): B = assert(len(t) == L, "the length of the table changed while iterating over it") iterator mvalues*[A, B](t: OrderedTableRef[A, B]): var B = - ## Iterates over any value in the table ``t`` in insertion order. The values + ## Iterates over any value in the table `t` in insertion order. The values ## can be modified. ## ## See also: @@ -2262,22 +2338,22 @@ proc initCountTable*[A](initialSize = defaultInitialSize): CountTable[A] = ## * `toCountTable proc<#toCountTable,openArray[A]>`_ ## * `newCountTable proc<#newCountTable>`_ for creating a ## `CountTableRef` + result = default(CountTable[A]) initImpl(result, initialSize) proc toCountTable*[A](keys: openArray[A]): CountTable[A] = - ## Creates a new count table with every member of a container ``keys`` + ## Creates a new count table with every member of a container `keys` ## having a count of how many times it occurs in that container. result = initCountTable[A](keys.len) for key in items(keys): result.inc(key) proc `[]`*[A](t: CountTable[A], key: A): int = - ## Retrieves the value at ``t[key]`` if ``key`` is in ``t``. - ## Otherwise ``0`` is returned. + ## Retrieves the value at `t[key]` if `key` is in `t`. + ## Otherwise `0` is returned. ## ## See also: ## * `getOrDefault<#getOrDefault,CountTable[A],A,int>`_ to return ## a custom value if the key doesn't exist - ## * `mget proc<#mget,CountTable[A],A>`_ ## * `[]= proc<#[]%3D,CountTable[A],A,int>`_ for inserting a new ## (key, value) pair in the table ## * `hasKey proc<#hasKey,CountTable[A],A>`_ for checking if a key @@ -2290,7 +2366,7 @@ template cntCellEmpty(i) = t.data[i].val == 0 template cntCellHash(i) = hash(t.data[i].key) proc `[]=`*[A](t: var CountTable[A], key: A, val: int) = - ## Inserts a ``(key, value)`` pair into ``t``. + ## Inserts a `(key, value)` pair into `t`. ## ## See also: ## * `[] proc<#[],CountTable[A],A>`_ for retrieving a value of a key @@ -2308,7 +2384,7 @@ proc `[]=`*[A](t: var CountTable[A], key: A, val: int) = insertImpl() proc inc*[A](t: var CountTable[A], key: A, val = 1) = - ## Increments ``t[key]`` by ``val`` (default: 1). + ## Increments `t[key]` by `val` (default: 1). runnableExamples: var a = toCountTable("aab") a.inc('a') @@ -2326,11 +2402,11 @@ proc inc*[A](t: var CountTable[A], key: A, val = 1) = insertImpl() proc len*[A](t: CountTable[A]): int = - ## Returns the number of keys in ``t``. + ## Returns the number of keys in `t`. result = t.counter proc smallest*[A](t: CountTable[A]): tuple[key: A, val: int] = - ## Returns the ``(key, value)`` pair with the smallest ``val``. Efficiency: O(n) + ## Returns the `(key, value)` pair with the smallest `val`. Efficiency: O(n) ## ## See also: ## * `largest proc<#largest,CountTable[A]>`_ @@ -2343,7 +2419,7 @@ proc smallest*[A](t: CountTable[A]): tuple[key: A, val: int] = result.val = t.data[minIdx].val proc largest*[A](t: CountTable[A]): tuple[key: A, val: int] = - ## Returns the ``(key, value)`` pair with the largest ``val``. Efficiency: O(n) + ## Returns the `(key, value)` pair with the largest `val`. Efficiency: O(n) ## ## See also: ## * `smallest proc<#smallest,CountTable[A]>`_ @@ -2355,7 +2431,7 @@ proc largest*[A](t: CountTable[A]): tuple[key: A, val: int] = result.val = t.data[maxIdx].val proc hasKey*[A](t: CountTable[A], key: A): bool = - ## Returns true if ``key`` is in the table ``t``. + ## Returns true if `key` is in the table `t`. ## ## See also: ## * `contains proc<#contains,CountTable[A],A>`_ for use with the `in` @@ -2368,12 +2444,12 @@ proc hasKey*[A](t: CountTable[A], key: A): bool = proc contains*[A](t: CountTable[A], key: A): bool = ## Alias of `hasKey proc<#hasKey,CountTable[A],A>`_ for use with - ## the ``in`` operator. + ## the `in` operator. return hasKey[A](t, key) proc getOrDefault*[A](t: CountTable[A], key: A; default: int = 0): int = - ## Retrieves the value at ``t[key]`` if``key`` is in ``t``. Otherwise, the - ## integer value of ``default`` is returned. + ## Retrieves the value at `t[key]` if `key` is in `t`. Otherwise, the + ## integer value of `default` is returned. ## ## See also: ## * `[] proc<#[],CountTable[A],A>`_ for retrieving a value of a key @@ -2382,7 +2458,7 @@ proc getOrDefault*[A](t: CountTable[A], key: A; default: int = 0): int = ctget(t, key, default) proc del*[A](t: var CountTable[A], key: A) {.since: (1, 1).} = - ## Deletes ``key`` from table ``t``. Does nothing if the key does not exist. + ## Deletes `key` from table `t`. Does nothing if the key does not exist. ## ## See also: ## * `pop proc<#pop,CountTable[A],A,int>`_ @@ -2399,9 +2475,9 @@ proc del*[A](t: var CountTable[A], key: A) {.since: (1, 1).} = delImplNoHCode(cntMakeEmpty, cntCellEmpty, cntCellHash) proc pop*[A](t: var CountTable[A], key: A, val: var int): bool {.since: (1, 1).} = - ## Deletes the ``key`` from the table. - ## Returns ``true``, if the ``key`` existed, and sets ``val`` to the - ## mapping of the key. Otherwise, returns ``false``, and the ``val`` is + ## Deletes the `key` from the table. + ## Returns `true`, if the `key` existed, and sets `val` to the + ## mapping of the key. Otherwise, returns `false`, and the `val` is ## unchanged. ## ## See also: @@ -2438,13 +2514,13 @@ proc sort*[A](t: var CountTable[A], order = SortOrder.Descending) = ## Sorts the count table so that, by default, the entry with the ## highest counter comes first. ## - ## **WARNING:** This is destructive! Once sorted, you must not modify ``t`` afterwards! + ## .. warning:: This is destructive! Once sorted, you must not modify `t` afterwards! ## ## You can use the iterators `pairs<#pairs.i,CountTable[A]>`_, ## `keys<#keys.i,CountTable[A]>`_, and `values<#values.i,CountTable[A]>`_ - ## to iterate over ``t`` in the sorted order. + ## to iterate over `t` in the sorted order. runnableExamples: - import algorithm, sequtils + import std/[algorithm, sequtils] var a = toCountTable("abracadabra") doAssert a == "aaaaabbrrcd".toCountTable a.sort() @@ -2482,18 +2558,18 @@ when (NimMajor, NimMinor) <= (1, 0): result.inc(key, value) proc `$`*[A](t: CountTable[A]): string = - ## The ``$`` operator for count tables. Used internally when calling `echo` + ## The `$` operator for count tables. Used internally when calling `echo` ## on a table. dollarImpl() proc `==`*[A](s, t: CountTable[A]): bool = - ## The ``==`` operator for count tables. Returns ``true`` if both tables + ## The `==` operator for count tables. Returns `true` if both tables ## contain the same keys with the same count. Insert order does not matter. equalsImpl(s, t) iterator pairs*[A](t: CountTable[A]): (A, int) = - ## Iterates over any ``(key, value)`` pair in the table ``t``. + ## Iterates over any `(key, value)` pair in the table `t`. ## ## See also: ## * `mpairs iterator<#mpairs.i,CountTable[A]>`_ @@ -2502,7 +2578,7 @@ iterator pairs*[A](t: CountTable[A]): (A, int) = ## ## **Examples:** ## - ## .. code-block:: + ## ```Nim ## let a = toCountTable("abracadabra") ## ## for k, v in pairs(a): @@ -2519,6 +2595,7 @@ iterator pairs*[A](t: CountTable[A]): (A, int) = ## # value: 1 ## # key: r ## # value: 2 + ## ``` let L = len(t) for h in 0 .. high(t.data): if t.data[h].val != 0: @@ -2526,7 +2603,7 @@ iterator pairs*[A](t: CountTable[A]): (A, int) = assert(len(t) == L, "the length of the table changed while iterating over it") iterator mpairs*[A](t: var CountTable[A]): (A, var int) = - ## Iterates over any ``(key, value)`` pair in the table ``t`` (must be + ## Iterates over any `(key, value)` pair in the table `t` (must be ## declared as `var`). The values can be modified. ## ## See also: @@ -2544,8 +2621,8 @@ iterator mpairs*[A](t: var CountTable[A]): (A, var int) = yield (t.data[h].key, t.data[h].val) assert(len(t) == L, "the length of the table changed while iterating over it") -iterator keys*[A](t: CountTable[A]): A = - ## Iterates over any key in the table ``t``. +iterator keys*[A](t: CountTable[A]): lent A = + ## Iterates over any key in the table `t`. ## ## See also: ## * `pairs iterator<#pairs.i,CountTable[A]>`_ @@ -2563,7 +2640,7 @@ iterator keys*[A](t: CountTable[A]): A = assert(len(t) == L, "the length of the table changed while iterating over it") iterator values*[A](t: CountTable[A]): int = - ## Iterates over any value in the table ``t``. + ## Iterates over any value in the table `t`. ## ## See also: ## * `pairs iterator<#pairs.i,CountTable[A]>`_ @@ -2581,7 +2658,7 @@ iterator values*[A](t: CountTable[A]): int = assert(len(t) == L, "the length of the table changed while iterating over it") iterator mvalues*[A](t: var CountTable[A]): var int = - ## Iterates over any value in the table ``t`` (must be + ## Iterates over any value in the table `t` (must be ## declared as `var`). The values can be modified. ## ## See also: @@ -2611,7 +2688,7 @@ iterator mvalues*[A](t: var CountTable[A]): var int = proc inc*[A](t: CountTableRef[A], key: A, val = 1) -proc newCountTable*[A](initialSize = defaultInitialSize): <//>CountTableRef[A] = +proc newCountTable*[A](initialSize = defaultInitialSize): CountTableRef[A] = ## Creates a new ref count table that is empty. ## ## See also: @@ -2620,17 +2697,19 @@ proc newCountTable*[A](initialSize = defaultInitialSize): <//>CountTableRef[A] = ## * `initCountTable proc<#initCountTable>`_ for creating a ## `CountTable` new(result) - result[] = initCountTable[A](initialSize) + {.noSideEffect.}: + result[] = initCountTable[A](initialSize) -proc newCountTable*[A](keys: openArray[A]): <//>CountTableRef[A] = - ## Creates a new ref count table with every member of a container ``keys`` +proc newCountTable*[A](keys: openArray[A]): CountTableRef[A] = + ## Creates a new ref count table with every member of a container `keys` ## having a count of how many times it occurs in that container. result = newCountTable[A](keys.len) - for key in items(keys): result.inc(key) + {.noSideEffect.}: + for key in items(keys): result.inc(key) proc `[]`*[A](t: CountTableRef[A], key: A): int = - ## Retrieves the value at ``t[key]`` if ``key`` is in ``t``. - ## Otherwise ``0`` is returned. + ## Retrieves the value at `t[key]` if `key` is in `t`. + ## Otherwise `0` is returned. ## ## See also: ## * `getOrDefault<#getOrDefault,CountTableRef[A],A,int>`_ to return @@ -2643,40 +2722,42 @@ proc `[]`*[A](t: CountTableRef[A], key: A): int = result = t[][key] proc `[]=`*[A](t: CountTableRef[A], key: A, val: int) = - ## Inserts a ``(key, value)`` pair into ``t``. + ## Inserts a `(key, value)` pair into `t`. ## ## See also: ## * `[] proc<#[],CountTableRef[A],A>`_ for retrieving a value of a key ## * `inc proc<#inc,CountTableRef[A],A,int>`_ for incrementing a ## value of a key assert val > 0 - t[][key] = val + {.noSideEffect.}: + t[][key] = val proc inc*[A](t: CountTableRef[A], key: A, val = 1) = - ## Increments ``t[key]`` by ``val`` (default: 1). + ## Increments `t[key]` by `val` (default: 1). runnableExamples: var a = newCountTable("aab") a.inc('a') a.inc('b', 10) doAssert a == newCountTable("aaabbbbbbbbbbb") - t[].inc(key, val) + {.noSideEffect.}: + t[].inc(key, val) proc smallest*[A](t: CountTableRef[A]): tuple[key: A, val: int] = - ## Returns the ``(key, value)`` pair with the smallest ``val``. Efficiency: O(n) + ## Returns the `(key, value)` pair with the smallest `val`. Efficiency: O(n) ## ## See also: ## * `largest proc<#largest,CountTableRef[A]>`_ t[].smallest proc largest*[A](t: CountTableRef[A]): tuple[key: A, val: int] = - ## Returns the ``(key, value)`` pair with the largest ``val``. Efficiency: O(n) + ## Returns the `(key, value)` pair with the largest `val`. Efficiency: O(n) ## ## See also: ## * `smallest proc<#smallest,CountTable[A]>`_ t[].largest proc hasKey*[A](t: CountTableRef[A], key: A): bool = - ## Returns true if ``key`` is in the table ``t``. + ## Returns true if `key` is in the table `t`. ## ## See also: ## * `contains proc<#contains,CountTableRef[A],A>`_ for use with the `in` @@ -2688,12 +2769,12 @@ proc hasKey*[A](t: CountTableRef[A], key: A): bool = proc contains*[A](t: CountTableRef[A], key: A): bool = ## Alias of `hasKey proc<#hasKey,CountTableRef[A],A>`_ for use with - ## the ``in`` operator. + ## the `in` operator. return hasKey[A](t, key) proc getOrDefault*[A](t: CountTableRef[A], key: A, default: int): int = - ## Retrieves the value at ``t[key]`` if``key`` is in ``t``. Otherwise, the - ## integer value of ``default`` is returned. + ## Retrieves the value at `t[key]` if `key` is in `t`. Otherwise, the + ## integer value of `default` is returned. ## ## See also: ## * `[] proc<#[],CountTableRef[A],A>`_ for retrieving a value of a key @@ -2702,11 +2783,11 @@ proc getOrDefault*[A](t: CountTableRef[A], key: A, default: int): int = result = t[].getOrDefault(key, default) proc len*[A](t: CountTableRef[A]): int = - ## Returns the number of keys in ``t``. + ## Returns the number of keys in `t`. result = t.counter proc del*[A](t: CountTableRef[A], key: A) {.since: (1, 1).} = - ## Deletes ``key`` from table ``t``. Does nothing if the key does not exist. + ## Deletes `key` from table `t`. Does nothing if the key does not exist. ## ## See also: ## * `pop proc<#pop,CountTableRef[A],A,int>`_ @@ -2714,9 +2795,9 @@ proc del*[A](t: CountTableRef[A], key: A) {.since: (1, 1).} = del(t[], key) proc pop*[A](t: CountTableRef[A], key: A, val: var int): bool {.since: (1, 1).} = - ## Deletes the ``key`` from the table. - ## Returns ``true``, if the ``key`` existed, and sets ``val`` to the - ## mapping of the key. Otherwise, returns ``false``, and the ``val`` is + ## Deletes the `key` from the table. + ## Returns `true`, if the `key` existed, and sets `val` to the + ## mapping of the key. Otherwise, returns `false`, and the `val` is ## unchanged. ## ## See also: @@ -2740,7 +2821,7 @@ proc sort*[A](t: CountTableRef[A], order = SortOrder.Descending) = ## ## You can use the iterators `pairs<#pairs.i,CountTableRef[A]>`_, ## `keys<#keys.i,CountTableRef[A]>`_, and `values<#values.i,CountTableRef[A]>`_ - ## to iterate over ``t`` in the sorted order. + ## to iterate over `t` in the sorted order. t[].sort(order = order) proc merge*[A](s, t: CountTableRef[A]) = @@ -2755,13 +2836,13 @@ proc merge*[A](s, t: CountTableRef[A]) = s[].merge(t[]) proc `$`*[A](t: CountTableRef[A]): string = - ## The ``$`` operator for count tables. Used internally when calling `echo` + ## The `$` operator for count tables. Used internally when calling `echo` ## on a table. dollarImpl() proc `==`*[A](s, t: CountTableRef[A]): bool = - ## The ``==`` operator for count tables. Returns ``true`` if either both tables - ## are ``nil``, or neither is ``nil`` and both contain the same keys with the same + ## The `==` operator for count tables. Returns `true` if either both tables + ## are `nil`, or neither is `nil` and both contain the same keys with the same ## count. Insert order does not matter. if isNil(s): result = isNil(t) elif isNil(t): result = false @@ -2769,7 +2850,7 @@ proc `==`*[A](s, t: CountTableRef[A]): bool = iterator pairs*[A](t: CountTableRef[A]): (A, int) = - ## Iterates over any ``(key, value)`` pair in the table ``t``. + ## Iterates over any `(key, value)` pair in the table `t`. ## ## See also: ## * `mpairs iterator<#mpairs.i,CountTableRef[A]>`_ @@ -2778,7 +2859,7 @@ iterator pairs*[A](t: CountTableRef[A]): (A, int) = ## ## **Examples:** ## - ## .. code-block:: + ## ```Nim ## let a = newCountTable("abracadabra") ## ## for k, v in pairs(a): @@ -2795,6 +2876,7 @@ iterator pairs*[A](t: CountTableRef[A]): (A, int) = ## # value: 1 ## # key: r ## # value: 2 + ## ``` let L = len(t) for h in 0 .. high(t.data): if t.data[h].val != 0: @@ -2802,7 +2884,7 @@ iterator pairs*[A](t: CountTableRef[A]): (A, int) = assert(len(t) == L, "the length of the table changed while iterating over it") iterator mpairs*[A](t: CountTableRef[A]): (A, var int) = - ## Iterates over any ``(key, value)`` pair in the table ``t``. The values can + ## Iterates over any `(key, value)` pair in the table `t`. The values can ## be modified. ## ## See also: @@ -2821,7 +2903,7 @@ iterator mpairs*[A](t: CountTableRef[A]): (A, var int) = assert(len(t) == L, "table modified while iterating over it") iterator keys*[A](t: CountTableRef[A]): A = - ## Iterates over any key in the table ``t``. + ## Iterates over any key in the table `t`. ## ## See also: ## * `pairs iterator<#pairs.i,CountTable[A]>`_ @@ -2839,7 +2921,7 @@ iterator keys*[A](t: CountTableRef[A]): A = assert(len(t) == L, "the length of the table changed while iterating over it") iterator values*[A](t: CountTableRef[A]): int = - ## Iterates over any value in the table ``t``. + ## Iterates over any value in the table `t`. ## ## See also: ## * `pairs iterator<#pairs.i,CountTableRef[A]>`_ @@ -2857,7 +2939,7 @@ iterator values*[A](t: CountTableRef[A]): int = assert(len(t) == L, "the length of the table changed while iterating over it") iterator mvalues*[A](t: CountTableRef[A]): var int = - ## Iterates over any value in the table ``t``. The values can be modified. + ## Iterates over any value in the table `t`. The values can be modified. ## ## See also: ## * `mpairs iterator<#mpairs.i,CountTableRef[A]>`_ @@ -2873,3 +2955,18 @@ iterator mvalues*[A](t: CountTableRef[A]): var int = if t.data[h].val != 0: yield t.data[h].val assert(len(t) == L, "the length of the table changed while iterating over it") + +proc hash*[K,V](s: Table[K,V]): Hash = + for p in pairs(s): + result = result xor hash(p) + result = !$result + +proc hash*[K,V](s: OrderedTable[K,V]): Hash = + for p in pairs(s): + result = result !& hash(p) + result = !$result + +proc hash*[V](s: CountTable[V]): Hash = + for p in pairs(s): + result = result xor hash(p) + result = !$result |