diff options
author | Miran <narimiran@users.noreply.github.com> | 2018-10-09 22:39:51 +0200 |
---|---|---|
committer | Andreas Rumpf <rumpf_a@web.de> | 2018-10-09 22:39:51 +0200 |
commit | 98a8868cb43efca008a909178b3475d163847833 (patch) | |
tree | 4fcd0e294c7f60a399c4975e2d6a2ea835035759 | |
parent | 63c00d7be9f016296074e5b78e4a9aeee7771c5c (diff) | |
download | Nim-98a8868cb43efca008a909178b3475d163847833.tar.gz |
better docs for `tables` module (#9221)
* better docs for `tables` module * lower case for the first sentence in docs
-rw-r--r-- | lib/pure/collections/tables.nim | 366 |
1 files changed, 190 insertions, 176 deletions
diff --git a/lib/pure/collections/tables.nim b/lib/pure/collections/tables.nim index f85de7546..9fdae33ed 100644 --- a/lib/pure/collections/tables.nim +++ b/lib/pure/collections/tables.nim @@ -12,13 +12,15 @@ ## a mapping from keys to values. ``Table`` is the usual hash table, ## ``OrderedTable`` is like ``Table`` but remembers insertion order ## and ``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. ## For **reference** semantics use the ``Ref`` variant: ``TableRef``, ## ``OrderedTableRef``, ``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: +## +## 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 @@ -33,8 +35,8 @@ ## 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` reference the same data structure: +## On the other hand, when ``a`` is a TableRef instead, then changes to ``b`` +## also affect ``a``. Both ``a`` and ``b`` reference the same data structure: ## ## .. code-block:: ## import tables @@ -50,6 +52,18 @@ ## echo a == b # output: true ## ## +## Here is an example of ``CountTable`` usage: +## +## .. code-block:: nim +## let myString = "abracadabra" +## var myTable = initCountTable[char]() +## +## for c in myString: +## myTable.inc(c) +## +## echo myTable # output: {'a': 5, 'b': 2, 'c': 1, 'd': 1, 'r': 2} +## +## ## 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 @@ -69,7 +83,7 @@ ## 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 +## 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: @@ -119,15 +133,15 @@ template dataLen(t): untyped = len(t.data) include tableimpl proc clear*[A, B](t: var Table[A, B]) = - ## Resets the table so that it is empty. + ## resets the table so that it is empty. clearImpl() proc clear*[A, B](t: TableRef[A, B]) = - ## Resets the table so that it is empty. + ## resets the ref table so that it is empty. clearImpl() proc rightSize*(count: Natural): int {.inline.} = - ## Return the value of `initialSize` to support `count` items. + ## 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. @@ -136,12 +150,12 @@ proc rightSize*(count: Natural): int {.inline.} = result = nextPowerOfTwo(count * 3 div 2 + 4) proc len*[A, B](t: Table[A, B]): int = - ## returns the number of keys in `t`. + ## returns the number of keys in ``t``. result = t.counter 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. + ## If ``key`` is not in ``t``, the ``KeyError`` exception is raised. mixin rawGet var hc: Hash var index = rawGet(t, key, hc) @@ -165,36 +179,36 @@ template getOrDefaultImpl(t, key, default: untyped): untyped = result = if index >= 0: t.data[index].val else: default proc `[]`*[A, B](t: Table[A, B], key: A): B {.deprecatedGet.} = - ## retrieves the value at ``t[key]``. If `key` is not in `t`, the + ## retrieves the value at ``t[key]``. If ``key`` is not in ``t``, the ## ``KeyError`` exception is raised. One can check with ``hasKey`` whether ## the key exists. get(t, key) proc `[]`*[A, B](t: var Table[A, B], key: A): var B {.deprecatedGet.} = ## 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. get(t, key) proc mget*[A, B](t: var Table[A, B], key: A): var B {.deprecated.} = ## retrieves the value at ``t[key]``. The value can be modified. - ## If `key` is not in `t`, the ``KeyError`` exception is raised. Use ```[]``` - ## instead. + ## If ``key`` is not in ``t``, the ``KeyError`` exception is raised. + ## Use ``[]`` instead. get(t, key) proc getOrDefault*[A, B](t: Table[A, B], key: A): B = - ## retrieves the value at ``t[key]`` iff `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]`` iff ``key`` is in ``t``. Otherwise, the + ## default initialization value for type ``B`` is returned (e.g. 0 for any ## integer type). getOrDefaultImpl(t, key) proc getOrDefault*[A, B](t: Table[A, B], key: A, default: B): B = - ## retrieves the value at ``t[key]`` iff `key` is in `t`. Otherwise, `default` - ## is returned. + ## retrieves the value at ``t[key]`` iff ``key`` is in ``t``. + ## Otherwise, ``default`` is returned. getOrDefaultImpl(t, key, default) 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. + ## ``value`` can be modified in the scope of the ``withValue`` call. ## ## .. code-block:: nim ## @@ -214,7 +228,7 @@ 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. + ## ``value`` can be modified in the scope of the ``withValue`` call. ## ## .. code-block:: nim ## @@ -237,7 +251,7 @@ template withValue*[A, B](t: var Table[A, B], key: A, body2 iterator allValues*[A, B](t: Table[A, B]; key: A): B = - ## 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``. var h: Hash = genHash(key) and high(t.data) while isFilled(t.data[h].hcode): if t.data[h].key == key: @@ -245,46 +259,46 @@ iterator allValues*[A, B](t: Table[A, B]; key: A): B = h = nextTry(h, high(t.data)) proc hasKey*[A, B](t: Table[A, B], key: A): bool = - ## returns true iff `key` is in the table `t`. + ## returns true iff ``key`` is in the table ``t``. var hc: Hash result = rawGet(t, key, hc) >= 0 proc contains*[A, B](t: Table[A, B], key: A): bool = - ## alias of `hasKey` for use with the `in` operator. + ## alias of ``hasKey`` for use with the ``in`` operator. return hasKey[A, B](t, key) 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``. for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield (t.data[h].key, t.data[h].val) iterator mpairs*[A, B](t: var Table[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. for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield (t.data[h].key, t.data[h].val) iterator keys*[A, B](t: Table[A, B]): A = - ## iterates over any key in the table `t`. + ## iterates over any key in the table ``t``. for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield t.data[h].key iterator values*[A, B](t: Table[A, B]): B = - ## iterates over any value in the table `t`. + ## iterates over any value in the table ``t``. for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield t.data[h].val iterator mvalues*[A, B](t: var Table[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. for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield t.data[h].val 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. delImpl() proc take*[A, B](t: var Table[A, B], key: A, val: var B): bool = - ## Deletes the ``key`` from the table. + ## 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. @@ -313,26 +327,26 @@ proc mgetOrPut*[A, B](t: var Table[A, B], key: A, val: B): var B = mgetOrPutImpl(enlarge) proc hasKeyOrPut*[A, B](t: var Table[A, B], key: A, val: B): bool = - ## returns true iff `key` is in the table, otherwise inserts `value`. + ## returns true iff ``key`` is in the table, otherwise inserts ``value``. hasKeyOrPutImpl(enlarge) proc `[]=`*[A, B](t: var Table[A, B], key: A, val: B) = - ## puts a (key, value)-pair into `t`. + ## puts a ``(key, value)`` pair into ``t``. putImpl(enlarge) proc add*[A, B](t: var Table[A, B], key: A, val: B) = - ## 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! addImpl(enlarge) proc len*[A, B](t: TableRef[A, B]): int = - ## returns the number of keys in `t`. + ## returns the number of keys in ``t``. result = t.counter proc initTable*[A, B](initialSize=64): Table[A, B] = ## creates a new hash table that is empty. ## - ## `initialSize` needs to be a power of two. If you need to accept runtime + ## ``initialSize`` needs to be a power of two. If you need to accept runtime ## values for this you could use the ``nextPowerOfTwo`` proc from the ## `math <math.html>`_ module or the ``rightSize`` proc from this module. assert isPowerOfTwo(initialSize) @@ -340,7 +354,7 @@ proc initTable*[A, B](initialSize=64): Table[A, B] = newSeq(result.data, initialSize) 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``. result = initTable[A, B](rightSize(pairs.len)) for key, val in items(pairs): result[key] = val @@ -357,11 +371,11 @@ template dollarImpl(): untyped {.dirty.} = result.add("}") proc `$`*[A, B](t: Table[A, B]): string = - ## The `$` operator for hash tables. + ## the ``$`` operator for hash tables. dollarImpl() proc hasKey*[A, B](t: TableRef[A, B], key: A): bool = - ## returns true iff `key` is in the table `t`. + ## returns true iff ``key`` is in the table ``t``. result = t[].hasKey(key) template equalsImpl(s, t: typed): typed = @@ -374,7 +388,7 @@ template equalsImpl(s, t: typed): typed = return true proc `==`*[A, B](s, t: Table[A, B]): bool = - ## The `==` operator for hash tables. Returns ``true`` iff the content of both + ## The ``==`` operator for hash tables. Returns ``true`` iff the content of both ## tables contains the same key-value pairs. Insert order does not matter. equalsImpl(s, t) @@ -386,52 +400,52 @@ proc indexBy*[A, B, C](collection: A, index: proc(x: B): C): Table[C, B] = result[index(item)] = item 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``. for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield (t.data[h].key, t.data[h].val) 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. for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield (t.data[h].key, t.data[h].val) iterator keys*[A, B](t: TableRef[A, B]): A = - ## iterates over any key in the table `t`. + ## iterates over any key in the table ``t``. for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield t.data[h].key iterator values*[A, B](t: TableRef[A, B]): B = - ## iterates over any value in the table `t`. + ## iterates over any value in the table ``t``. for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield t.data[h].val 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. for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield t.data[h].val proc `[]`*[A, B](t: TableRef[A, B], key: A): var B {.deprecatedGet.} = - ## retrieves the value at ``t[key]``. If `key` is not in `t`, the + ## retrieves the value at ``t[key]``. If ``key`` is not in ``t``, the ## ``KeyError`` exception is raised. One can check with ``hasKey`` whether ## the key exists. result = t[][key] proc mget*[A, B](t: TableRef[A, B], key: A): var B {.deprecated.} = ## retrieves the value at ``t[key]``. The value can be modified. - ## If `key` is not in `t`, the ``KeyError`` exception is raised. - ## Use ```[]``` instead. + ## If ``key`` is not in ``t``, the ``KeyError`` exception is raised. + ## Use ``[]`` instead. t[][key] proc getOrDefault*[A, B](t: TableRef[A, B], key: A): B = - ## retrieves the value at ``t[key]`` iff `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]`` iff ``key`` is in ``t``. Otherwise, the + ## default initialization value for type ``B`` is returned (e.g. 0 for any ## integer type). getOrDefault(t[], key) proc getOrDefault*[A, B](t: TableRef[A, B], key: A, default: B): B = - ## retrieves the value at ``t[key]`` iff `key` is in `t`. Otherwise, `default` - ## is returned. + ## retrieves the value at ``t[key]`` iff ``key`` is in ``t``. + ## Otherwise, ``default`` is returned. getOrDefault(t[], key, default) proc mgetOrPut*[A, B](t: TableRef[A, B], key: A, val: B): var B = @@ -440,28 +454,28 @@ proc mgetOrPut*[A, B](t: TableRef[A, B], key: A, val: B): var B = t[].mgetOrPut(key, val) proc hasKeyOrPut*[A, B](t: var TableRef[A, B], key: A, val: B): bool = - ## returns true iff `key` is in the table, otherwise inserts `value`. + ## returns true iff ``key`` is in the table, otherwise inserts ``value``. t[].hasKeyOrPut(key, val) proc contains*[A, B](t: TableRef[A, B], key: A): bool = - ## alias of `hasKey` for use with the `in` operator. + ## Alias of ``hasKey`` for use with the ``in`` operator. return hasKey[A, B](t, key) proc `[]=`*[A, B](t: TableRef[A, B], key: A, val: B) = - ## puts a (key, value)-pair into `t`. + ## puts a ``(key, value)`` pair into ``t``. t[][key] = val proc add*[A, B](t: TableRef[A, B], key: A, val: B) = - ## 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! 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. t[].del(key) proc take*[A, B](t: TableRef[A, B], key: A, val: var B): bool = - ## Deletes the ``key`` from the table. + ## 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. @@ -472,16 +486,16 @@ proc newTable*[A, B](initialSize=64): TableRef[A, B] = result[] = initTable[A, B](initialSize) proc newTable*[A, B](pairs: openArray[(A, B)]): TableRef[A, B] = - ## creates a new hash table that contains the given `pairs`. + ## creates a new hash table that contains the given ``pairs``. new(result) result[] = toTable[A, B](pairs) proc `$`*[A, B](t: TableRef[A, B]): string = - ## The `$` operator for hash tables. + ## The ``$`` operator for hash tables. dollarImpl() proc `==`*[A, B](s, t: TableRef[A, B]): bool = - ## The `==` operator for hash tables. Returns ``true`` iff either both tables + ## The ``==`` operator for hash tables. Returns ``true`` iff either both tables ## are ``nil`` or none is ``nil`` and the content of both tables contains the ## same key-value pairs. Insert order does not matter. if isNil(s): result = isNil(t) @@ -509,17 +523,17 @@ type {.deprecated: [TOrderedTable: OrderedTable, POrderedTable: OrderedTableRef].} proc len*[A, B](t: OrderedTable[A, B]): int {.inline.} = - ## returns the number of keys in `t`. + ## returns the number of keys in ``t``. result = t.counter proc clear*[A, B](t: var OrderedTable[A, B]) = - ## Resets the table so that it is empty. + ## resets the table so that it is empty. clearImpl() t.first = -1 t.last = -1 proc clear*[A, B](t: var OrderedTableRef[A, B]) = - ## Resets the table so that is is empty. + ## resets the table so that is is empty. clear(t[]) template forAllOrderedPairs(yieldStmt: untyped): typed {.dirty.} = @@ -530,29 +544,29 @@ template forAllOrderedPairs(yieldStmt: untyped): typed {.dirty.} = h = nxt 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. forAllOrderedPairs: yield (t.data[h].key, t.data[h].val) iterator mpairs*[A, B](t: var OrderedTable[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. forAllOrderedPairs: yield (t.data[h].key, t.data[h].val) iterator keys*[A, B](t: OrderedTable[A, B]): A = - ## iterates over any key in the table `t` in insertion order. + ## iterates over any key in the table ``t`` in insertion order. forAllOrderedPairs: yield t.data[h].key iterator values*[A, B](t: OrderedTable[A, B]): B = - ## iterates over any value in the table `t` in insertion order. + ## iterates over any value in the table ``t`` in insertion order. forAllOrderedPairs: yield t.data[h].val iterator mvalues*[A, B](t: var OrderedTable[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. forAllOrderedPairs: yield t.data[h].val @@ -567,40 +581,40 @@ proc rawGet[A, B](t: OrderedTable[A, B], key: A, hc: var Hash): int = rawGetImpl() proc `[]`*[A, B](t: OrderedTable[A, B], key: A): B {.deprecatedGet.} = - ## retrieves the value at ``t[key]``. If `key` is not in `t`, the + ## retrieves the value at ``t[key]``. If ``key`` is not in ``t``, the ## ``KeyError`` exception is raised. One can check with ``hasKey`` whether ## the key exists. get(t, key) proc `[]`*[A, B](t: var OrderedTable[A, B], key: A): var B{.deprecatedGet.} = ## 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. get(t, key) proc mget*[A, B](t: var OrderedTable[A, B], key: A): var B {.deprecated.} = ## retrieves the value at ``t[key]``. The value can be modified. - ## If `key` is not in `t`, the ``KeyError`` exception is raised. - ## Use ```[]``` instead. + ## If ``key`` is not in ``t``, the ``KeyError`` exception is raised. + ## Use ``[]`` instead. get(t, key) proc getOrDefault*[A, B](t: OrderedTable[A, B], key: A): B = - ## retrieves the value at ``t[key]`` iff `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]`` iff ``key`` is in ``t``. Otherwise, the + ## default initialization value for type ``B`` is returned (e.g. 0 for any ## integer type). getOrDefaultImpl(t, key) proc getOrDefault*[A, B](t: OrderedTable[A, B], key: A, default: B): B = - ## retrieves the value at ``t[key]`` iff `key` is in `t`. Otherwise, `default` - ## is returned. + ## retrieves the value at ``t[key]`` iff ``key`` is in ``t``. Otherwise, + ## ``default`` is returned. getOrDefaultImpl(t, key, default) proc hasKey*[A, B](t: OrderedTable[A, B], key: A): bool = - ## returns true iff `key` is in the table `t`. + ## returns true iff ``key`` is in the table ``t``. var hc: Hash result = rawGet(t, key, hc) >= 0 proc contains*[A, B](t: OrderedTable[A, B], key: A): bool = - ## alias of `hasKey` for use with the `in` operator. + ## Alias of ``hasKey`` for use with the ``in`` operator. return hasKey[A, B](t, key) proc rawInsert[A, B](t: var OrderedTable[A, B], @@ -630,11 +644,11 @@ proc enlarge[A, B](t: var OrderedTable[A, B]) = h = nxt proc `[]=`*[A, B](t: var OrderedTable[A, B], key: A, val: B) = - ## puts a (key, value)-pair into `t`. + ## puts a ``(key, value)`` pair into ``t``. putImpl(enlarge) proc add*[A, B](t: var OrderedTable[A, B], key: A, val: B) = - ## 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! addImpl(enlarge) @@ -644,13 +658,13 @@ proc mgetOrPut*[A, B](t: var OrderedTable[A, B], key: A, val: B): var B = mgetOrPutImpl(enlarge) proc hasKeyOrPut*[A, B](t: var OrderedTable[A, B], key: A, val: B): bool = - ## returns true iff `key` is in the table, otherwise inserts `value`. + ## returns true iff ``key`` is in the table, otherwise inserts ``value``. hasKeyOrPutImpl(enlarge) proc initOrderedTable*[A, B](initialSize=64): OrderedTable[A, B] = ## creates a new ordered hash table that is empty. ## - ## `initialSize` needs to be a power of two. If you need to accept runtime + ## ``initialSize`` needs to be a power of two. If you need to accept runtime ## values for this you could use the ``nextPowerOfTwo`` proc from the ## `math <math.html>`_ module or the ``rightSize`` proc from this module. assert isPowerOfTwo(initialSize) @@ -660,16 +674,16 @@ proc initOrderedTable*[A, B](initialSize=64): OrderedTable[A, B] = newSeq(result.data, initialSize) 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``. result = initOrderedTable[A, B](rightSize(pairs.len)) for key, val in items(pairs): result[key] = val proc `$`*[A, B](t: OrderedTable[A, B]): string = - ## The `$` operator for ordered hash tables. + ## The ``$`` operator for ordered hash tables. dollarImpl() proc `==`*[A, B](s, t: OrderedTable[A, B]): bool = - ## The `==` operator for ordered hash tables. Returns true iff both the + ## The ``==`` operator for ordered hash tables. Returns true iff both the ## content and the order are equal. if s.counter != t.counter: return false @@ -686,10 +700,10 @@ proc `==`*[A, B](s, t: OrderedTable[A, B]): bool = return true proc sort*[A, B](t: var OrderedTable[A, B], cmp: proc (x,y: (A, B)): int) = - ## sorts `t` according to `cmp`. This modifies the internal list + ## sorts ``t`` according to ``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 - ## contrast to the `sort` for count tables). + ## call but key lookup and insertions remain possible after ``sort`` (in + ## contrast to the ``sort`` for count tables). var list = t.first var p, q, e, tail, oldhead: int @@ -731,58 +745,58 @@ proc sort*[A, B](t: var OrderedTable[A, B], cmp: proc (x,y: (A, B)): int) = t.last = tail proc len*[A, B](t: OrderedTableRef[A, B]): int {.inline.} = - ## returns the number of keys in `t`. + ## returns the number of keys in ``t``. result = t.counter 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. forAllOrderedPairs: yield (t.data[h].key, t.data[h].val) 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. forAllOrderedPairs: yield (t.data[h].key, t.data[h].val) iterator keys*[A, B](t: OrderedTableRef[A, B]): A = - ## iterates over any key in the table `t` in insertion order. + ## iterates over any key in the table ``t`` in insertion order. forAllOrderedPairs: yield t.data[h].key iterator values*[A, B](t: OrderedTableRef[A, B]): B = - ## iterates over any value in the table `t` in insertion order. + ## iterates over any value in the table ``t`` in insertion order. forAllOrderedPairs: yield t.data[h].val 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. forAllOrderedPairs: yield t.data[h].val proc `[]`*[A, B](t: OrderedTableRef[A, B], key: A): var B = - ## retrieves the value at ``t[key]``. If `key` is not in `t`, the + ## retrieves the value at ``t[key]``. If ``key`` is not in ``t``, the ## ``KeyError`` exception is raised. One can check with ``hasKey`` whether ## the key exists. result = t[][key] proc mget*[A, B](t: OrderedTableRef[A, B], key: A): var B {.deprecated.} = ## retrieves the value at ``t[key]``. The value can be modified. - ## If `key` is not in `t`, the ``KeyError`` exception is raised. - ## Use ```[]``` instead. + ## If ``key`` is not in ``t``, the ``KeyError`` exception is raised. + ## Use ``[]`` instead. result = t[][key] proc getOrDefault*[A, B](t: OrderedTableRef[A, B], key: A): B = - ## retrieves the value at ``t[key]`` iff `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]`` iff ``key`` is in ``t``. Otherwise, the + ## default initialization value for type ``B`` is returned (e.g. 0 for any ## integer type). getOrDefault(t[], key) proc getOrDefault*[A, B](t: OrderedTableRef[A, B], key: A, default: B): B = - ## retrieves the value at ``t[key]`` iff `key` is in `t`. Otherwise, `default` - ## is returned. + ## retrieves the value at ``t[key]`` iff ``key`` is in ``t``. Otherwise, + ## ``default`` is returned. getOrDefault(t[], key, default) proc mgetOrPut*[A, B](t: OrderedTableRef[A, B], key: A, val: B): var B = @@ -791,46 +805,46 @@ proc mgetOrPut*[A, B](t: OrderedTableRef[A, B], key: A, val: B): var B = result = t[].mgetOrPut(key, val) proc hasKeyOrPut*[A, B](t: var OrderedTableRef[A, B], key: A, val: B): bool = - ## returns true iff `key` is in the table, otherwise inserts `val`. + ## returns true iff ``key`` is in the table, otherwise inserts ``val``. result = t[].hasKeyOrPut(key, val) proc hasKey*[A, B](t: OrderedTableRef[A, B], key: A): bool = - ## returns true iff `key` is in the table `t`. + ## returns true iff ``key`` is in the table ``t``. result = t[].hasKey(key) proc contains*[A, B](t: OrderedTableRef[A, B], key: A): bool = - ## alias of `hasKey` for use with the `in` operator. + ## Alias of ``hasKey`` for use with the ``in`` operator. return hasKey[A, B](t, key) proc `[]=`*[A, B](t: OrderedTableRef[A, B], key: A, val: B) = - ## puts a (key, value)-pair into `t`. + ## puts a ``(key, value)`` pair into ``t``. t[][key] = val proc add*[A, B](t: OrderedTableRef[A, B], key: A, val: B) = - ## 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! t[].add(key, val) proc newOrderedTable*[A, B](initialSize=64): OrderedTableRef[A, B] = ## creates a new ordered hash table that is empty. ## - ## `initialSize` needs to be a power of two. If you need to accept runtime + ## ``initialSize`` needs to be a power of two. If you need to accept runtime ## values for this you could use the ``nextPowerOfTwo`` proc from the ## `math <math.html>`_ module or the ``rightSize`` proc from this module. new(result) result[] = initOrderedTable[A, B](initialSize) proc newOrderedTable*[A, B](pairs: openArray[(A, B)]): OrderedTableRef[A, B] = - ## creates a new ordered hash table that contains the given `pairs`. + ## creates a new ordered hash table that contains the given ``pairs``. result = newOrderedTable[A, B](rightSize(pairs.len)) for key, val in items(pairs): result.add(key, val) proc `$`*[A, B](t: OrderedTableRef[A, B]): string = - ## The `$` operator for ordered hash tables. + ## The ``$`` operator for ordered hash tables. dollarImpl() proc `==`*[A, B](s, t: OrderedTableRef[A, B]): bool = - ## The `==` operator for ordered hash tables. Returns true iff either both + ## The ``==`` operator for ordered hash tables. Returns true iff either both ## tables are ``nil`` or none is ``nil`` and the content and the order of ## both are equal. if isNil(s): result = isNil(t) @@ -838,14 +852,14 @@ proc `==`*[A, B](s, t: OrderedTableRef[A, B]): bool = else: result = s[] == t[] proc sort*[A, B](t: OrderedTableRef[A, B], cmp: proc (x,y: (A, B)): int) = - ## sorts `t` according to `cmp`. This modifies the internal list + ## sorts ``t`` according to ``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 - ## contrast to the `sort` for count tables). + ## call but key lookup and insertions remain possible after ``sort`` (in + ## contrast to the ``sort`` for count tables). t[].sort(cmp) proc del*[A, B](t: var OrderedTable[A, B], key: A) = - ## deletes `key` from ordered hash table `t`. O(n) complexity. Does nothing + ## deletes ``key`` from ordered hash table ``t``. O(n) complexity. Does nothing ## if the key does not exist. var n: OrderedKeyValuePairSeq[A, B] newSeq(n, len(t.data)) @@ -865,7 +879,7 @@ proc del*[A, B](t: var OrderedTable[A, B], key: A) = h = nxt proc del*[A, B](t: var OrderedTableRef[A, B], key: A) = - ## deletes `key` from ordered hash table `t`. O(n) complexity. Does nothing + ## deletes ``key`` from ordered hash table ``t``. O(n) complexity. Does nothing ## if the key does not exist. t[].del(key) @@ -881,40 +895,40 @@ type {.deprecated: [TCountTable: CountTable, PCountTable: CountTableRef].} 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 clear*[A](t: CountTableRef[A]) = - ## Resets the table so that it is empty. + ## resets the table so that it is empty. clearImpl() proc clear*[A](t: var CountTable[A]) = - ## Resets the table so that it is empty. + ## resets the table so that it is empty. clearImpl() 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``. for h in 0..high(t.data): if t.data[h].val != 0: yield (t.data[h].key, t.data[h].val) iterator mpairs*[A](t: var CountTable[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. for h in 0..high(t.data): if t.data[h].val != 0: yield (t.data[h].key, t.data[h].val) iterator keys*[A](t: CountTable[A]): A = - ## iterates over any key in the table `t`. + ## iterates over any key in the table ``t``. for h in 0..high(t.data): if t.data[h].val != 0: yield t.data[h].key iterator values*[A](t: CountTable[A]): int = - ## iterates over any value in the table `t`. + ## iterates over any value in the table ``t``. for h in 0..high(t.data): if t.data[h].val != 0: yield t.data[h].val iterator mvalues*[A](t: CountTable[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. for h in 0..high(t.data): if t.data[h].val != 0: yield t.data[h].val @@ -935,40 +949,40 @@ template ctget(t, key: untyped): untyped = raise newException(KeyError, "key not found") proc `[]`*[A](t: CountTable[A], key: A): int {.deprecatedGet.} = - ## retrieves the value at ``t[key]``. If `key` is not in `t`, + ## retrieves the value at ``t[key]``. If ``key`` is not in ``t``, ## the ``KeyError`` exception is raised. One can check with ``hasKey`` ## whether the key exists. ctget(t, key) proc `[]`*[A](t: var CountTable[A], key: A): var int {.deprecatedGet.} = ## 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. ctget(t, key) proc mget*[A](t: var CountTable[A], key: A): var int {.deprecated.} = ## retrieves the value at ``t[key]``. The value can be modified. - ## If `key` is not in `t`, the ``KeyError`` exception is raised. - ## Use ```[]``` instead. + ## If ``key`` is not in ``t``, the ``KeyError`` exception is raised. + ## Use ``[]`` instead. ctget(t, key) proc getOrDefault*[A](t: CountTable[A], key: A): int = - ## retrieves the value at ``t[key]`` iff `key` is in `t`. Otherwise, 0 (the - ## default initialization value of `int`), is returned. + ## retrieves the value at ``t[key]`` iff ``key`` is in ``t``. Otherwise, 0 (the + ## default initialization value of ``int``), is returned. var index = rawGet(t, key) if index >= 0: result = t.data[index].val proc getOrDefault*[A](t: CountTable[A], key: A, default: int): int = - ## retrieves the value at ``t[key]`` iff `key` is in `t`. Otherwise, the - ## integer value of `default` is returned. + ## retrieves the value at ``t[key]`` iff ``key`` is in ``t``. Otherwise, the + ## integer value of ``default`` is returned. var index = rawGet(t, key) result = if index >= 0: t.data[index].val else: default proc hasKey*[A](t: CountTable[A], key: A): bool = - ## returns true iff `key` is in the table `t`. + ## returns true iff ``key`` is in the table ``t``. result = rawGet(t, key) >= 0 proc contains*[A](t: CountTable[A], key: A): bool = - ## alias of `hasKey` for use with the `in` operator. + ## Alias of ``hasKey`` for use with the ``in`` operator. return hasKey[A](t, key) proc rawInsert[A](t: CountTable[A], data: var seq[tuple[key: A, val: int]], @@ -986,7 +1000,7 @@ proc enlarge[A](t: var CountTable[A]) = swap(t.data, n) proc `[]=`*[A](t: var CountTable[A], key: A, val: int) = - ## puts a (key, value)-pair into `t`. + ## puts a ``(key, value)`` pair into ``t``. assert val >= 0 var h = rawGet(t, key) if h >= 0: @@ -1000,7 +1014,7 @@ proc `[]=`*[A](t: var CountTable[A], key: A, val: int) = #t.data[h].val = val proc inc*[A](t: var CountTable[A], key: A, val = 1) = - ## increments `t[key]` by `val`. + ## increments ``t[key]`` by ``val``. var index = rawGet(t, key) if index >= 0: inc(t.data[index].val, val) @@ -1013,7 +1027,7 @@ proc inc*[A](t: var CountTable[A], key: A, val = 1) = proc initCountTable*[A](initialSize=64): CountTable[A] = ## creates a new count table that is empty. ## - ## `initialSize` needs to be a power of two. If you need to accept runtime + ## ``initialSize`` needs to be a power of two. If you need to accept runtime ## values for this you could use the ``nextPowerOfTwo`` proc from the ## `math <math.html>`_ module or the ``rightSize`` proc in this module. assert isPowerOfTwo(initialSize) @@ -1021,22 +1035,22 @@ proc initCountTable*[A](initialSize=64): CountTable[A] = newSeq(result.data, initialSize) proc toCountTable*[A](keys: openArray[A]): CountTable[A] = - ## creates a new count table with every key in `keys` having a count - ## of how many times it occurs in `keys`. + ## creates a new count table with every key in ``keys`` having a count + ## of how many times it occurs in ``keys``. result = initCountTable[A](rightSize(keys.len)) for key in items(keys): result.inc(key) proc `$`*[A](t: CountTable[A]): string = - ## The `$` operator for count tables. + ## The ``$`` operator for count tables. dollarImpl() proc `==`*[A](s, t: CountTable[A]): bool = - ## The `==` operator for count tables. Returns ``true`` iff both tables + ## The ``==`` operator for count tables. Returns ``true`` iff both tables ## contain the same keys with the same count. Insert order does not matter. equalsImpl(s, t) proc smallest*[A](t: CountTable[A]): tuple[key: A, val: int] = - ## returns the (key,val)-pair with the smallest `val`. Efficiency: O(n) + ## returns the ``(key, value)`` pair with the smallest ``val``. Efficiency: O(n) assert t.len > 0 var minIdx = -1 for h in 0..high(t.data): @@ -1046,7 +1060,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,val)-pair with the largest `val`. Efficiency: O(n) + ## returns the ``(key, value)`` pair with the largest ``val``. Efficiency: O(n) assert t.len > 0 var maxIdx = 0 for h in 1..high(t.data): @@ -1056,9 +1070,9 @@ proc largest*[A](t: CountTable[A]): tuple[key: A, val: int] = proc sort*[A](t: var CountTable[A]) = ## sorts the count table so that the entry with the highest counter comes - ## first. This is destructive! You must not modify `t` afterwards! - ## You can use the iterators `pairs`, `keys`, and `values` to iterate over - ## `t` in the sorted order. + ## first. This is destructive! You must not modify ``t`` afterwards! + ## You can use the iterators ``pairs``, ``keys``, and ``values`` to iterate over + ## ``t`` in the sorted order. # we use shellsort here; fast enough and simple var h = 1 @@ -1076,94 +1090,94 @@ proc sort*[A](t: var CountTable[A]) = if h == 1: break proc len*[A](t: CountTableRef[A]): int = - ## returns the number of keys in `t`. + ## returns the number of keys in ``t``. result = t.counter 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``. for h in 0..high(t.data): if t.data[h].val != 0: yield (t.data[h].key, t.data[h].val) 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. for h in 0..high(t.data): if t.data[h].val != 0: yield (t.data[h].key, t.data[h].val) iterator keys*[A](t: CountTableRef[A]): A = - ## iterates over any key in the table `t`. + ## iterates over any key in the table ``t``. for h in 0..high(t.data): if t.data[h].val != 0: yield t.data[h].key iterator values*[A](t: CountTableRef[A]): int = - ## iterates over any value in the table `t`. + ## iterates over any value in the table ``t``. for h in 0..high(t.data): if t.data[h].val != 0: yield t.data[h].val 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. for h in 0..high(t.data): if t.data[h].val != 0: yield t.data[h].val proc `[]`*[A](t: CountTableRef[A], key: A): var int {.deprecatedGet.} = ## 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. result = t[][key] proc mget*[A](t: CountTableRef[A], key: A): var int {.deprecated.} = ## retrieves the value at ``t[key]``. The value can be modified. - ## If `key` is not in `t`, the ``KeyError`` exception is raised. - ## Use ```[]``` instead. + ## If ``key`` is not in ``t``, the ``KeyError`` exception is raised. + ## Use ``[]`` instead. result = t[][key] proc getOrDefault*[A](t: CountTableRef[A], key: A): int = - ## retrieves the value at ``t[key]`` iff `key` is in `t`. Otherwise, 0 (the - ## default initialization value of `int`), is returned. + ## retrieves the value at ``t[key]`` iff ``key`` is in ``t``. Otherwise, 0 (the + ## default initialization value of ``int``), is returned. result = t[].getOrDefault(key) proc getOrDefault*[A](t: CountTableRef[A], key: A, default: int): int = - ## retrieves the value at ``t[key]`` iff `key` is in `t`. Otherwise, the - ## integer value of `default` is returned. + ## retrieves the value at ``t[key]`` iff ``key`` is in ``t``. Otherwise, the + ## integer value of ``default`` is returned. result = t[].getOrDefault(key, default) proc hasKey*[A](t: CountTableRef[A], key: A): bool = - ## returns true iff `key` is in the table `t`. + ## returns true iff ``key`` is in the table ``t``. result = t[].hasKey(key) proc contains*[A](t: CountTableRef[A], key: A): bool = - ## alias of `hasKey` for use with the `in` operator. + ## Alias of ``hasKey`` for use with the ``in`` operator. return hasKey[A](t, key) proc `[]=`*[A](t: CountTableRef[A], key: A, val: int) = - ## puts a (key, value)-pair into `t`. `val` has to be positive. + ## puts a ``(key, value)`` pair into ``t``. ``val`` has to be positive. assert val > 0 t[][key] = val proc inc*[A](t: CountTableRef[A], key: A, val = 1) = - ## increments `t[key]` by `val`. + ## increments ``t[key]`` by ``val``. t[].inc(key, val) proc newCountTable*[A](initialSize=64): CountTableRef[A] = ## creates a new count table that is empty. ## - ## `initialSize` needs to be a power of two. If you need to accept runtime + ## ``initialSize`` needs to be a power of two. If you need to accept runtime ## values for this you could use the ``nextPowerOfTwo`` proc from the ## `math <math.html>`_ module or the ``rightSize`` method in this module. new(result) result[] = initCountTable[A](initialSize) proc newCountTable*[A](keys: openArray[A]): CountTableRef[A] = - ## creates a new count table with every key in `keys` having a count - ## of how many times it occurs in `keys`. + ## creates a new count table with every key in ``keys`` having a count + ## of how many times it occurs in ``keys``. result = newCountTable[A](rightSize(keys.len)) for key in items(keys): result.inc(key) proc `$`*[A](t: CountTableRef[A]): string = - ## The `$` operator for count tables. + ## The ``$`` operator for count tables. dollarImpl() proc `==`*[A](s, t: CountTableRef[A]): bool = - ## The `==` operator for count tables. Returns ``true`` iff either both tables + ## The ``==`` operator for count tables. Returns ``true`` iff either both tables ## are ``nil`` or none is ``nil`` and both contain the same keys with the same ## count. Insert order does not matter. if isNil(s): result = isNil(t) @@ -1171,34 +1185,34 @@ proc `==`*[A](s, t: CountTableRef[A]): bool = else: result = s[] == t[] proc smallest*[A](t: CountTableRef[A]): (A, int) = - ## returns the (key,val)-pair with the smallest `val`. Efficiency: O(n) + ## returns the ``(key, value)`` pair with the smallest ``val``. Efficiency: O(n) t[].smallest proc largest*[A](t: CountTableRef[A]): (A, int) = - ## returns the (key,val)-pair with the largest `val`. Efficiency: O(n) + ## returns the ``(key, value)`` pair with the largest ``val``. Efficiency: O(n) t[].largest proc sort*[A](t: CountTableRef[A]) = ## sorts the count table so that the entry with the highest counter comes - ## first. This is destructive! You must not modify `t` afterwards! - ## You can use the iterators `pairs`, `keys`, and `values` to iterate over - ## `t` in the sorted order. + ## first. This is destructive! You must not modify ``t`` afterwards! + ## You can use the iterators ``pairs``, ``keys``, and ``values`` to iterate over + ## ``t`` in the sorted order. t[].sort proc merge*[A](s: var CountTable[A], t: CountTable[A]) = - ## merges the second table into the first one + ## merges the second table into the first one. for key, value in t: s.inc(key, value) proc merge*[A](s, t: CountTable[A]): CountTable[A] = - ## merges the two tables into a new one + ## merges the two tables into a new one. result = initCountTable[A](nextPowerOfTwo(max(s.len, t.len))) for table in @[s, t]: for key, value in table: result.inc(key, value) proc merge*[A](s, t: CountTableRef[A]) = - ## merges the second table into the first one + ## merges the second table into the first one. s[].merge(t[]) when isMainModule: |