diff options
Diffstat (limited to 'lib/pure/collections/tables.nim')
| -rw-r--r-- | lib/pure/collections/tables.nim | 3575 |
1 files changed, 2572 insertions, 1003 deletions
diff --git a/lib/pure/collections/tables.nim b/lib/pure/collections/tables.nim index 7b508b294..d414caeed 100644 --- a/lib/pure/collections/tables.nim +++ b/lib/pure/collections/tables.nim @@ -7,202 +7,627 @@ # 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. ``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: -## -## .. code-block:: -## import tables -## -## var -## a = {1: "one", 2: "two"}.toTable # creates a Table -## b = a +## a mapping from keys to values. ## -## echo a, b # output: {1: one, 2: two}{1: one, 2: two} +## 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, +## * `CountTable<#CountTable>`_ is a mapping from a key to its number of occurrences ## -## b[3] = "three" -## echo a, b # output: {1: one, 2: two}{1: one, 2: two, 3: three} -## echo a == b # output: false +## For consistency with every other data type in Nim these have **value** +## semantics, this means that `=` performs a copy of the hash table. ## -## 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: +## For `ref semantics<manual.html#types-reference-and-pointer-types>`_ +## use their `Ref` variants: `TableRef<#TableRef>`_, +## `OrderedTableRef<#OrderedTableRef>`_, and `CountTableRef<#CountTableRef>`_. ## -## .. code-block:: -## import tables +## 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 + ## -## var -## a = {1: "one", 2: "two"}.newTable # creates a TableRef -## b = a +## ---- ## -## echo a, b # output: {1: one, 2: two}{1: one, 2: two} + +## # 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. + +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: + +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>`_: + +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}" + ## -## b[3] = "three" -## echo a, b # output: {1: one, 2: two, 3: three}{1: one, 2: two, 3: three} -## echo a == b # output: true +## ---- ## + +## ## 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: ## -## 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:: -## 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 +## 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 + ## -## var -## salaries = initTable[Person, int]() -## p1, p2: Person +## ---- ## -## p1.firstName = "Jon" -## p1.lastName = "Ross" -## salaries[p1] = 30_000 + +## # See also ## -## p2.firstName = "소진" -## p2.lastName = "박" -## salaries[p2] = 45_000 +## * `json module<json.html>`_ for table-like structure which allows +## heterogeneous members +## * `strtabs module<strtabs.html>`_ for efficient hash tables +## mapping from strings to strings +## * `hashes module<hashes.html>`_ for helper functions for hashing + -import - hashes, math +import std/private/since +import std/[hashes, math, algorithm] -include "system/inclrtl" + +when not defined(nimHasEffectsOf): + {.pragma: effectsOf.} type KeyValuePair[A, B] = tuple[hcode: Hash, key: A, val: B] KeyValuePairSeq[A, B] = seq[KeyValuePair[A, B]] - Table*[A, B] = object ## generic hash table + Table*[A, B] = object + ## Generic hash table, consisting of a key-value pair. + ## + ## `data` and `counter` are internal implementation details which + ## can't be accessed. + ## + ## For creating an empty Table, use `initTable proc<#initTable>`_. data: KeyValuePairSeq[A, B] counter: int - TableRef*[A,B] = ref Table[A, B] + TableRef*[A, B] = ref Table[A, B] ## Ref version of `Table<#Table>`_. + ## + ## For creating a new empty TableRef, use `newTable proc + ## <#newTable>`_. -{.deprecated: [TTable: Table, PTable: TableRef].} +# ------------------------------ helpers --------------------------------- + +# Do NOT move these to tableimpl.nim, because sharedtables uses that +# file and has its own implementation. template maxHash(t): untyped = high(t.data) 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. - clearImpl() - -proc clear*[A, B](t: TableRef[A, B]) = - ## Resets the table so that it is empty. - clearImpl() - -proc rightSize*(count: Natural): int {.inline.} = - ## Return the value of `initialSize` to support `count` items. - ## - ## If more items are expected to be added, simply add that - ## expected extra amount to the parameter before calling this. - ## - ## Internally, we want mustRehash(rightSize(x), x) == false. - result = nextPowerOfTwo(count * 3 div 2 + 4) - -proc len*[A, B](t: Table[A, B]): int = - ## returns the number of keys in `t`. - result = t.counter +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) -template getOrDefaultImpl(t, key): untyped = - mixin rawGet - var hc: Hash - var index = rawGet(t, key, hc) - if index >= 0: result = t.data[index].val +proc enlarge[A, B](t: var Table[A, B]) = + var n: KeyValuePairSeq[A, B] + newSeq(n, len(t.data) * growthFactor) + swap(t.data, n) + for i in countup(0, high(n)): + let eh = n[i].hcode + if isFilled(eh): + var j: Hash = eh and maxHash(t) + while isFilled(t.data[j].hcode): + j = nextTry(j, maxHash(t)) + when defined(js): + rawInsert(t, t.data, n[i].key, n[i].val, eh, j) + else: + rawInsert(t, t.data, move n[i].key, move n[i].val, eh, j) -template getOrDefaultImpl(t, key, default: untyped): untyped = - mixin rawGet - var hc: Hash - var index = rawGet(t, key, hc) - 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 - ## ``KeyError`` exception is raised. One can check with ``hasKey`` whether + + +# ------------------------------------------------------------------- +# ------------------------------ Table ------------------------------ +# ------------------------------------------------------------------- + +proc initTable*[A, B](initialSize = defaultInitialSize): Table[A, B] = + ## Creates a new hash table that is empty. + ## + ## Starting from Nim v0.20, tables are initialized by default and it is + ## not necessary to call this function explicitly. + ## + ## See also: + ## * `toTable proc<#toTable,openArray[]>`_ + ## * `newTable proc<#newTable>`_ for creating a `TableRef` + runnableExamples: + 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`. + ## + ## See also: + ## * `[] proc<#[],Table[A,B],A>`_ for retrieving a value of a key + ## * `hasKeyOrPut proc<#hasKeyOrPut,Table[A,B],A,B>`_ + ## * `mgetOrPut proc<#mgetOrPut,Table[A,B],A,B>`_ + ## * `del proc<#del,Table[A,B],A>`_ for removing a key from the table + runnableExamples: + var a = initTable[char, int]() + a['x'] = 7 + a['y'] = 33 + doAssert a == {'x': 7, 'y': 33}.toTable + + putImpl(enlarge) + +proc toTable*[A, B](pairs: openArray[(A, B)]): Table[A, B] = + ## Creates a new hash table that contains the given `pairs`. + ## + ## `pairs` is a container consisting of `(key, value)` tuples. + ## + ## See also: + ## * `initTable proc<#initTable>`_ + ## * `newTable proc<#newTable,openArray[]>`_ for a `TableRef` version + runnableExamples: + let a = [('a', 5), ('b', 9)] + let b = toTable(a) + assert b == {'a': 5, 'b': 9}.toTable + + result = initTable[A, B](pairs.len) + for key, val in items(pairs): result[key] = val + +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. + ## One can check with `hasKey proc<#hasKey,Table[A,B],A>`_ whether ## the key exists. + ## + ## 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,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 + runnableExamples: + let a = {'a': 5, 'b': 9}.toTable + doAssert a['a'] == 5 + doAssertRaises(KeyError): + echo a['z'] 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. +proc `[]`*[A, B](t: var Table[A, B], key: A): var B = + ## Retrieves the value at `t[key]`. The value can be modified. + ## + ## 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,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 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. - get(t, key) +proc hasKey*[A, B](t: Table[A, B], key: A): bool = + ## Returns true if `key` is in the table `t`. + ## + ## See also: + ## * `contains proc<#contains,Table[A,B],A>`_ for use with the `in` operator + ## * `[] proc<#[],Table[A,B],A>`_ for retrieving a value of a key + ## * `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 + runnableExamples: + let a = {'a': 5, 'b': 9}.toTable + doAssert a.hasKey('a') == true + doAssert a.hasKey('z') == false + + var hc: Hash + result = rawGet(t, key, hc) >= 0 + +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. + runnableExamples: + let a = {'a': 5, 'b': 9}.toTable + doAssert 'b' in a == true + doAssert a.contains('z') == false + + 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`. + ## + ## See also: + ## * `hasKey proc<#hasKey,Table[A,B],A>`_ + ## * `[] proc<#[],Table[A,B],A>`_ for retrieving a value of a key + ## * `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 + runnableExamples: + var a = {'a': 5, 'b': 9}.toTable + if a.hasKeyOrPut('a', 50): + a['a'] = 99 + if a.hasKeyOrPut('z', 50): + a['z'] = 99 + doAssert a == {'a': 99, 'b': 9, 'z': 50}.toTable + + hasKeyOrPutImpl(enlarge) proc getOrDefault*[A, B](t: Table[A, B], key: A): B = - ## retrieves the value at ``t[key]`` iff `key` is in `t`. Otherwise, the + ## 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: + ## * `[] proc<#[],Table[A,B],A>`_ for retrieving a value of a key + ## * `hasKey proc<#hasKey,Table[A,B],A>`_ + ## * `hasKeyOrPut proc<#hasKeyOrPut,Table[A,B],A,B>`_ + ## * `mgetOrPut proc<#mgetOrPut,Table[A,B],A,B>`_ + ## * `getOrDefault proc<#getOrDefault,Table[A,B],A,B>`_ to return + ## a custom value if the key doesn't exist + runnableExamples: + 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]`` iff `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 + ## * `hasKey proc<#hasKey,Table[A,B],A>`_ + ## * `hasKeyOrPut proc<#hasKeyOrPut,Table[A,B],A,B>`_ + ## * `mgetOrPut proc<#mgetOrPut,Table[A,B],A,B>`_ + ## * `getOrDefault proc<#getOrDefault,Table[A,B],A>`_ to return + ## a default value (e.g. zero for int) if the key doesn't exist + runnableExamples: + 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) -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. +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 + ## returning a value which can be modified. + ## ## - ## .. code-block:: nim + ## Note that while the value returned is of type `var B`, + ## 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. ## - ## sharedTable.withValue(key, value) do: - ## # block is executed only if ``key`` in ``t`` - ## value.name = "username" - ## value.uid = 1000 + ## See also: + ## * `[] proc<#[],Table[A,B],A>`_ for retrieving a value of a key + ## * `hasKey proc<#hasKey,Table[A,B],A>`_ + ## * `hasKeyOrPut proc<#hasKeyOrPut,Table[A,B],A,B>`_ + ## * `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 + runnableExamples: + var a = {'a': 5, 'b': 9}.toTable + doAssert a.mgetOrPut('a', 99) == 5 + doAssert a.mgetOrPut('z', 99) == 99 + doAssert a == {'a': 5, 'b': 9, 'z': 99}.toTable + + # An example of accidentally creating a copy + var t = initTable[int, seq[int]]() + # In this example, we expect t[10] to be modified, + # but it is not. + var copiedSeq = t.mgetOrPut(10, @[10]) + copiedSeq.add(20) + doAssert t[10] == @[10] + # Correct + t.mgetOrPut(25, @[25]).add(35) + doAssert t[25] == @[25, 35] + + 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`. + runnableExamples: + let a = {'a': 5, 'b': 9}.toTable + doAssert len(a) == 2 + + result = t.counter + +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. + ## + ## **This can introduce duplicate keys into the table!** + ## + ## Use `[]= proc<#[]=,Table[A,B],A,sinkB>`_ for inserting a new + ## (key, value) pair in the table without introducing duplicates. + addImpl(enlarge) + +template tabMakeEmpty(i) = t.data[i].hcode = 0 +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. + ## + ## .. 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>`_ + ## * `clear proc<#clear,Table[A,B]>`_ to empty the whole table + runnableExamples: + var a = {'a': 5, 'b': 9, 'c': 13}.toTable + a.del('a') + doAssert a == {'b': 9, 'c': 13}.toTable + a.del('z') + doAssert a == {'b': 9, 'c': 13}.toTable + + 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 + ## 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 + runnableExamples: + var + a = {'a': 5, 'b': 9, 'c': 13}.toTable + i: int + doAssert a.pop('b', i) == true + doAssert a == {'a': 5, 'c': 13}.toTable + doAssert i == 9 + i = 0 + doAssert a.pop('z', i) == false + doAssert a == {'a': 5, 'c': 13}.toTable + doAssert i == 0 + + var hc: Hash + var index = rawGet(t, key, hc) + result = index >= 0 + if result: + val = move(t.data[index].val) + delImplIdx(t, index, tabMakeEmpty, tabCellEmpty, tabCellHash) + +proc take*[A, B](t: var Table[A, B], key: A, val: var B): bool {.inline.} = + ## Alias for: + ## * `pop proc<#pop,Table[A,B],A,B>`_ + pop(t, key, val) + +proc clear*[A, B](t: var Table[A, B]) = + ## Resets the table so that it is empty. + ## + ## See also: + ## * `del proc<#del,Table[A,B],A>`_ + ## * `pop proc<#pop,Table[A,B],A,B>`_ + runnableExamples: + var a = {'a': 5, 'b': 9, 'c': 13}.toTable + doAssert len(a) == 3 + clear(a) + doAssert len(a) == 0 + + clearImpl() + +proc `$`*[A, B](t: Table[A, B]): string = + ## 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 + ## tables contains the same key-value pairs. Insert order does not matter. + runnableExamples: + let + a = {'a': 5, 'b': 9, 'c': 13}.toTable + b = {'b': 9, 'c': 13, 'a': 5}.toTable + doAssert a == b + + equalsImpl(s, t) + +proc indexBy*[A, B, C](collection: A, index: proc(x: B): C): Table[C, B] = + ## Index the collection with the proc provided. + # TODO: As soon as supported, change collection: A to collection: A[B] + result = initTable[C, B]() + for item in collection: + result[index(item)] = item + + + +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. + 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) @@ -213,19 +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) @@ -236,326 +677,615 @@ template withValue*[A, B](t: var Table[A, B], key: A, else: 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`. - var h: Hash = genHash(key) and high(t.data) - while isFilled(t.data[h].hcode): - if t.data[h].key == key: - yield t.data[h].val - 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`. - 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. - 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`. - for h in 0..high(t.data): - if isFilled(t.data[h].hcode): yield (t.data[h].key, t.data[h].val) + ## Iterates over any `(key, value)` pair in the table `t`. + ## + ## See also: + ## * `mpairs iterator<#mpairs.i,Table[A,B]>`_ + ## * `keys iterator<#keys.i,Table[A,B]>`_ + ## * `values iterator<#values.i,Table[A,B]>`_ + ## + ## **Examples:** + ## + ## ```Nim + ## let a = { + ## 'o': [1, 5, 7, 9], + ## 'e': [2, 4, 6, 8] + ## }.toTable + ## + ## for k, v in a.pairs: + ## echo "key: ", k + ## echo "value: ", v + ## + ## # key: e + ## # 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): + yield (t.data[h].key, t.data[h].val) + 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`. 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`. - 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`. - for h in 0..high(t.data): - if isFilled(t.data[h].hcode): yield t.data[h].val + ## Iterates over any `(key, value)` pair in the table `t` (must be + ## declared as `var`). The values can be modified. + ## + ## See also: + ## * `pairs iterator<#pairs.i,Table[A,B]>`_ + ## * `mvalues iterator<#mvalues.i,Table[A,B]>`_ + runnableExamples: + var a = { + 'o': @[1, 5, 7, 9], + 'e': @[2, 4, 6, 8] + }.toTable + for k, v in a.mpairs: + v.add(v[0] + 10) + doAssert a == {'e': @[2, 4, 6, 8, 12], 'o': @[1, 5, 7, 9, 11]}.toTable + + let L = len(t) + for h in 0 .. high(t.data): + if isFilled(t.data[h].hcode): + 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]): lent A = + ## Iterates over any key in the table `t`. + ## + ## See also: + ## * `pairs iterator<#pairs.i,Table[A,B]>`_ + ## * `values iterator<#values.i,Table[A,B]>`_ + runnableExamples: + var a = { + 'o': @[1, 5, 7, 9], + 'e': @[2, 4, 6, 8] + }.toTable + for k in a.keys: + a[k].add(99) + doAssert a == {'e': @[2, 4, 6, 8, 99], 'o': @[1, 5, 7, 9, 99]}.toTable + + let L = len(t) + for h in 0 .. high(t.data): + if isFilled(t.data[h].hcode): + 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]): lent B = + ## Iterates over any value in the table `t`. + ## + ## See also: + ## * `pairs iterator<#pairs.i,Table[A,B]>`_ + ## * `keys iterator<#keys.i,Table[A,B]>`_ + ## * `mvalues iterator<#mvalues.i,Table[A,B]>`_ + runnableExamples: + let a = { + 'o': @[1, 5, 7, 9], + 'e': @[2, 4, 6, 8] + }.toTable + for v in a.values: + doAssert v.len == 4 + + let L = len(t) + for h in 0 .. high(t.data): + if isFilled(t.data[h].hcode): + yield t.data[h].val + 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`. 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`. - delImpl() - -proc take*[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 - ## unchanged. - var hc: Hash - var index = rawGet(t, key, hc) - result = index >= 0 - if result: - shallowCopy(val, t.data[index].val) - delImplIdx(t, index) + ## Iterates over any value in the table `t` (must be + ## declared as `var`). The values can be modified. + ## + ## See also: + ## * `mpairs iterator<#mpairs.i,Table[A,B]>`_ + ## * `values iterator<#values.i,Table[A,B]>`_ + runnableExamples: + var a = { + 'o': @[1, 5, 7, 9], + 'e': @[2, 4, 6, 8] + }.toTable + for v in a.mvalues: + v.add(99) + doAssert a == {'e': @[2, 4, 6, 8, 99], 'o': @[1, 5, 7, 9, 99]}.toTable + + let L = len(t) + for h in 0 .. high(t.data): + if isFilled(t.data[h].hcode): + yield t.data[h].val + assert(len(t) == L, "the length of the table changed while iterating over it") -proc enlarge[A, B](t: var Table[A, B]) = - var n: KeyValuePairSeq[A, B] - newSeq(n, len(t.data) * growthFactor) - swap(t.data, n) - for i in countup(0, high(n)): - let eh = n[i].hcode - if isFilled(eh): - var j: Hash = eh and maxHash(t) - while isFilled(t.data[j].hcode): - j = nextTry(j, maxHash(t)) - rawInsert(t, t.data, n[i].key, n[i].val, eh, j) +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`. + ## + ## Used if you have a table with duplicate keys (as a result of using + ## `add proc<#add,Table[A,B],A,sinkB>`_). + ## + runnableExamples: + import std/[sequtils, algorithm] -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 - ## returning a value which can be modified. - mgetOrPutImpl(enlarge) + var a = {'a': 3, 'b': 5}.toTable + for i in 1..3: a.add('z', 10*i) + doAssert toSeq(a.pairs).sorted == @[('a', 3), ('b', 5), ('z', 10), ('z', 20), ('z', 30)] + doAssert sorted(toSeq(a.allValues('z'))) == @[10, 20, 30] + var h: Hash = genHash(key) and high(t.data) + let L = len(t) + while isFilled(t.data[h].hcode): + if t.data[h].key == key: + yield t.data[h].val + assert(len(t) == L, "the length of the table changed while iterating over it") + h = nextTry(h, high(t.data)) -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`. - hasKeyOrPutImpl(enlarge) -proc `[]=`*[A, B](t: var Table[A, B], key: A, val: B) = - ## 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. - ## This can introduce duplicate keys into the table! - addImpl(enlarge) +# ------------------------------------------------------------------- +# ---------------------------- TableRef ----------------------------- +# ------------------------------------------------------------------- -proc len*[A, B](t: TableRef[A, B]): int = - ## 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. +proc newTable*[A, B](initialSize = defaultInitialSize): TableRef[A, B] = + ## Creates a new ref hash table that is empty. ## - ## `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) - result.counter = 0 - newSeq(result.data, initialSize) + ## See also: + ## * `newTable proc<#newTable,openArray[]>`_ for creating a `TableRef` + ## from a collection of `(key, value)` pairs + ## * `initTable proc<#initTable>`_ for creating a `Table` + runnableExamples: + let + a = newTable[int, string]() + b = newTable[char, seq[int]]() -proc toTable*[A, B](pairs: openArray[(A, B)]): Table[A, B] = - ## 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 + new(result) + {.noSideEffect.}: + result[] = initTable[A, B](initialSize) -template dollarImpl(): untyped {.dirty.} = - if t.len == 0: - result = "{:}" - else: - result = "{" - for key, val in pairs(t): - if result.len > 1: result.add(", ") - result.addQuoted(key) - result.add(": ") - result.addQuoted(val) - result.add("}") +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. + ## + ## See also: + ## * `newTable proc<#newTable>`_ + ## * `toTable proc<#toTable,openArray[]>`_ for a `Table` version + runnableExamples: + let a = [('a', 5), ('b', 9)] + let b = newTable(a) + assert b == {'a': 5, 'b': 9}.newTable -proc `$`*[A, B](t: Table[A, B]): string = - ## The `$` operator for hash tables. - dollarImpl() + new(result) + {.noSideEffect.}: + result[] = toTable[A, B](pairs) -proc hasKey*[A, B](t: TableRef[A, B], key: A): bool = - ## returns true iff `key` is in the table `t`. - result = t[].hasKey(key) +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]() + {.noSideEffect.}: + for item in collection: + result[index(item)] = item -template equalsImpl(s, t: typed): typed = - if s.counter == t.counter: - # different insertion orders mean different 'data' seqs, so we have - # to use the slow route here: - for key, val in s: - if not t.hasKey(key): return false - if t.getOrDefault(key) != val: return false - return true +proc `[]`*[A, B](t: TableRef[A, B], key: A): var B = + ## Retrieves the value at `t[key]`. + ## + ## 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. + ## + ## See also: + ## * `getOrDefault proc<#getOrDefault,TableRef[A,B],A>`_ to return + ## a default value (e.g. zero for int) if the key doesn't exist + ## * `getOrDefault proc<#getOrDefault,TableRef[A,B],A,B>`_ to return + ## a custom value if the key doesn't exist + ## * `[]= proc<#[]=,TableRef[A,B],A,sinkB>`_ for inserting a new + ## (key, value) pair in the table + ## * `hasKey proc<#hasKey,TableRef[A,B],A>`_ for checking if a key is in + ## the table + runnableExamples: + let a = {'a': 5, 'b': 9}.newTable + doAssert a['a'] == 5 + doAssertRaises(KeyError): + echo a['z'] -proc `==`*[A, B](s, t: Table[A, B]): bool = - ## 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) + result = t[][key] -proc indexBy*[A, B, C](collection: A, index: proc(x: B): C): Table[C, B] = - ## Index the collection with the proc provided. - # TODO: As soon as supported, change collection: A to collection: A[B] - result = initTable[C, B]() - for item in collection: - result[index(item)] = item +proc `[]=`*[A, B](t: TableRef[A, B], key: A, val: sink B) = + ## Inserts a `(key, value)` pair into `t`. + ## + ## See also: + ## * `[] proc<#[],TableRef[A,B],A>`_ for retrieving a value of a key + ## * `hasKeyOrPut proc<#hasKeyOrPut,TableRef[A,B],A,B>`_ + ## * `mgetOrPut proc<#mgetOrPut,TableRef[A,B],A,B>`_ + ## * `del proc<#del,TableRef[A,B],A>`_ for removing a key from the table + runnableExamples: + var a = newTable[char, int]() + a['x'] = 7 + a['y'] = 33 + doAssert a == {'x': 7, 'y': 33}.newTable -iterator pairs*[A, B](t: TableRef[A, B]): (A, B) = - ## 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) + t[][key] = val -iterator mpairs*[A, B](t: TableRef[A, B]): (A, var B) = - ## 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) +proc hasKey*[A, B](t: TableRef[A, B], key: A): bool = + ## Returns true if `key` is in the table `t`. + ## + ## See also: + ## * `contains proc<#contains,TableRef[A,B],A>`_ for use with the `in` + ## operator + ## * `[] proc<#[],TableRef[A,B],A>`_ for retrieving a value of a key + ## * `getOrDefault proc<#getOrDefault,TableRef[A,B],A>`_ to return + ## a default value (e.g. zero for int) if the key doesn't exist + ## * `getOrDefault proc<#getOrDefault,TableRef[A,B],A,B>`_ to return + ## a custom value if the key doesn't exist + runnableExamples: + let a = {'a': 5, 'b': 9}.newTable + doAssert a.hasKey('a') == true + doAssert a.hasKey('z') == false -iterator keys*[A, B](t: TableRef[A, B]): A = - ## 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 + result = t[].hasKey(key) -iterator values*[A, B](t: TableRef[A, B]): B = - ## 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 +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. + runnableExamples: + let a = {'a': 5, 'b': 9}.newTable + doAssert 'b' in a == true + doAssert a.contains('z') == false -iterator mvalues*[A, B](t: TableRef[A, B]): var B = - ## 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 + return hasKey[A, B](t, key) -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 - ## ``KeyError`` exception is raised. One can check with ``hasKey`` whether - ## the key exists. - result = t[][key] +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>`_ + ## * `[] proc<#[],TableRef[A,B],A>`_ for retrieving a value of a key + ## * `getOrDefault proc<#getOrDefault,TableRef[A,B],A>`_ to return + ## a default value (e.g. zero for int) if the key doesn't exist + ## * `getOrDefault proc<#getOrDefault,TableRef[A,B],A,B>`_ to return + ## a custom value if the key doesn't exist + runnableExamples: + var a = {'a': 5, 'b': 9}.newTable + if a.hasKeyOrPut('a', 50): + a['a'] = 99 + if a.hasKeyOrPut('z', 50): + a['z'] = 99 + doAssert a == {'a': 99, 'b': 9, 'z': 50}.newTable -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. - t[][key] + t[].hasKeyOrPut(key, val) proc getOrDefault*[A, B](t: TableRef[A, B], key: A): B = - ## retrieves the value at ``t[key]`` iff `key` is in `t`. Otherwise, the + ## 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: + ## * `[] proc<#[],TableRef[A,B],A>`_ for retrieving a value of a key + ## * `hasKey proc<#hasKey,TableRef[A,B],A>`_ + ## * `hasKeyOrPut proc<#hasKeyOrPut,TableRef[A,B],A,B>`_ + ## * `mgetOrPut proc<#mgetOrPut,TableRef[A,B],A,B>`_ + ## * `getOrDefault proc<#getOrDefault,TableRef[A,B],A,B>`_ to return + ## a custom value if the key doesn't exist + runnableExamples: + let a = {'a': 5, 'b': 9}.newTable + doAssert a.getOrDefault('a') == 5 + doAssert a.getOrDefault('z') == 0 + 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]` if `key` is in `t`. + ## Otherwise, `default` is returned. + ## + ## See also: + ## * `[] proc<#[],TableRef[A,B],A>`_ for retrieving a value of a key + ## * `hasKey proc<#hasKey,TableRef[A,B],A>`_ + ## * `hasKeyOrPut proc<#hasKeyOrPut,TableRef[A,B],A,B>`_ + ## * `mgetOrPut proc<#mgetOrPut,TableRef[A,B],A,B>`_ + ## * `getOrDefault proc<#getOrDefault,TableRef[A,B],A>`_ to return + ## a default value (e.g. zero for int) if the key doesn't exist + runnableExamples: + let a = {'a': 5, 'b': 9}.newTable + doAssert a.getOrDefault('a', 99) == 5 + doAssert a.getOrDefault('z', 99) == 99 + 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`, + ## it is easy to accidentally create an 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. + ## + ## See also: + ## * `[] proc<#[],TableRef[A,B],A>`_ for retrieving a value of a key + ## * `hasKey proc<#hasKey,TableRef[A,B],A>`_ + ## * `hasKeyOrPut proc<#hasKeyOrPut,TableRef[A,B],A,B>`_ + ## * `getOrDefault proc<#getOrDefault,TableRef[A,B],A>`_ to return + ## a default value (e.g. zero for int) if the key doesn't exist + ## * `getOrDefault proc<#getOrDefault,TableRef[A,B],A,B>`_ to return + ## a custom value if the key doesn't exist + runnableExamples: + var a = {'a': 5, 'b': 9}.newTable + doAssert a.mgetOrPut('a', 99) == 5 + doAssert a.mgetOrPut('z', 99) == 99 + doAssert a == {'a': 5, 'b': 9, 'z': 99}.newTable + + # An example of accidentally creating a copy + var t = newTable[int, seq[int]]() + # In this example, we expect t[10] to be modified, + # but it is not. + var copiedSeq = t.mgetOrPut(10, @[10]) + copiedSeq.add(20) + doAssert t[10] == @[10] + # Correct + t.mgetOrPut(25, @[25]).add(35) + doAssert t[25] == @[25, 35] 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`. - t[].hasKeyOrPut(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 -proc contains*[A, B](t: TableRef[A, B], key: A): bool = - ## alias of `hasKey` for use with the `in` operator. - return hasKey[A, B](t, key) + t[].mgetOrPut(key) -proc `[]=`*[A, B](t: TableRef[A, B], key: A, val: B) = - ## puts a (key, value)-pair into `t`. - t[][key] = val +proc len*[A, B](t: TableRef[A, B]): int = + ## Returns the number of keys in `t`. + runnableExamples: + let a = {'a': 5, 'b': 9}.newTable + doAssert len(a) == 2 -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. - ## This can introduce duplicate keys into the table! + result = t.counter + +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. + ## + ## **This can introduce duplicate keys into the table!** + ## + ## Use `[]= proc<#[]=,TableRef[A,B],A,sinkB>`_ for inserting a new + ## (key, value) pair in the table without introducing duplicates. t[].add(key, val) proc del*[A, B](t: TableRef[A, B], key: A) = - ## deletes `key` from hash table `t`. + ## 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,TableRef[A,B],A,B>`_ + ## * `clear proc<#clear,TableRef[A,B]>`_ to empty the whole table + runnableExamples: + var a = {'a': 5, 'b': 9, 'c': 13}.newTable + a.del('a') + doAssert a == {'b': 9, 'c': 13}.newTable + a.del('z') + doAssert a == {'b': 9, 'c': 13}.newTable + t[].del(key) -proc take*[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 +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 ## unchanged. - result = t[].take(key, val) + ## + ## .. 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>`_ + ## * `clear proc<#clear,TableRef[A,B]>`_ to empty the whole table + runnableExamples: + var + a = {'a': 5, 'b': 9, 'c': 13}.newTable + i: int + doAssert a.pop('b', i) == true + doAssert a == {'a': 5, 'c': 13}.newTable + doAssert i == 9 + i = 0 + doAssert a.pop('z', i) == false + doAssert a == {'a': 5, 'c': 13}.newTable + doAssert i == 0 + + result = t[].pop(key, val) + +proc take*[A, B](t: TableRef[A, B], key: A, val: var B): bool {.inline.} = + ## Alias for: + ## * `pop proc<#pop,TableRef[A,B],A,B>`_ + pop(t, key, val) -proc newTable*[A, B](initialSize=64): TableRef[A, B] = - new(result) - result[] = initTable[A, B](initialSize) +proc clear*[A, B](t: TableRef[A, B]) = + ## Resets the table so that it is empty. + ## + ## See also: + ## * `del proc<#del,Table[A,B],A>`_ + ## * `pop proc<#pop,Table[A,B],A,B>`_ + runnableExamples: + var a = {'a': 5, 'b': 9, 'c': 13}.newTable + doAssert len(a) == 3 + clear(a) + doAssert len(a) == 0 -proc newTable*[A, B](pairs: openArray[(A, B)]): TableRef[A, B] = - ## creates a new hash table that contains the given `pairs`. - new(result) - result[] = toTable[A, B](pairs) + clearImpl() proc `$`*[A, B](t: TableRef[A, B]): string = - ## The `$` operator for hash tables. + ## 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`` iff either both tables - ## are ``nil`` or none 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 + a = {'a': 5, 'b': 9, 'c': 13}.newTable + b = {'b': 9, 'c': 13, 'a': 5}.newTable + doAssert a == b + if isNil(s): result = isNil(t) elif isNil(t): result = false else: equalsImpl(s[], t[]) -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 -# ------------------------------ ordered table ------------------------------ -type - OrderedKeyValuePair[A, B] = tuple[ - hcode: Hash, next: int, key: A, val: B] - OrderedKeyValuePairSeq[A, B] = seq[OrderedKeyValuePair[A, B]] - OrderedTable* [A, B] = object ## table that remembers insertion order - data: OrderedKeyValuePairSeq[A, B] - counter, first, last: int - OrderedTableRef*[A, B] = ref OrderedTable[A, B] +iterator pairs*[A, B](t: TableRef[A, B]): (A, B) = + ## Iterates over any `(key, value)` pair in the table `t`. + ## + ## See also: + ## * `mpairs iterator<#mpairs.i,TableRef[A,B]>`_ + ## * `keys iterator<#keys.i,TableRef[A,B]>`_ + ## * `values iterator<#values.i,TableRef[A,B]>`_ + ## + ## **Examples:** + ## + ## ```Nim + ## let a = { + ## 'o': [1, 5, 7, 9], + ## 'e': [2, 4, 6, 8] + ## }.newTable + ## + ## for k, v in a.pairs: + ## echo "key: ", k + ## echo "value: ", v + ## + ## # key: e + ## # 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): + yield (t.data[h].key, t.data[h].val) + assert(len(t) == L, "the length of the table changed while iterating over it") -{.deprecated: [TOrderedTable: OrderedTable, POrderedTable: OrderedTableRef].} +iterator mpairs*[A, B](t: TableRef[A, B]): (A, var B) = + ## Iterates over any `(key, value)` pair in the table `t`. The values + ## can be modified. + ## + ## See also: + ## * `pairs iterator<#pairs.i,TableRef[A,B]>`_ + ## * `mvalues iterator<#mvalues.i,TableRef[A,B]>`_ + runnableExamples: + let a = { + 'o': @[1, 5, 7, 9], + 'e': @[2, 4, 6, 8] + }.newTable + for k, v in a.mpairs: + v.add(v[0] + 10) + doAssert a == {'e': @[2, 4, 6, 8, 12], 'o': @[1, 5, 7, 9, 11]}.newTable + + let L = len(t) + for h in 0 .. high(t.data): + if isFilled(t.data[h].hcode): + 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]): lent A = + ## Iterates over any key in the table `t`. + ## + ## See also: + ## * `pairs iterator<#pairs.i,TableRef[A,B]>`_ + ## * `values iterator<#values.i,TableRef[A,B]>`_ + runnableExamples: + let a = { + 'o': @[1, 5, 7, 9], + 'e': @[2, 4, 6, 8] + }.newTable + for k in a.keys: + a[k].add(99) + doAssert a == {'e': @[2, 4, 6, 8, 99], 'o': @[1, 5, 7, 9, 99]}.newTable + + let L = len(t) + for h in 0 .. high(t.data): + if isFilled(t.data[h].hcode): + 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]): lent B = + ## Iterates over any value in the table `t`. + ## + ## See also: + ## * `pairs iterator<#pairs.i,TableRef[A,B]>`_ + ## * `keys iterator<#keys.i,TableRef[A,B]>`_ + ## * `mvalues iterator<#mvalues.i,TableRef[A,B]>`_ + runnableExamples: + let a = { + 'o': @[1, 5, 7, 9], + 'e': @[2, 4, 6, 8] + }.newTable + for v in a.values: + doAssert v.len == 4 + + let L = len(t) + for h in 0 .. high(t.data): + if isFilled(t.data[h].hcode): + yield t.data[h].val + assert(len(t) == L, "the length of the table changed while iterating over it") -proc len*[A, B](t: OrderedTable[A, B]): int {.inline.} = - ## returns the number of keys in `t`. - result = t.counter +iterator mvalues*[A, B](t: TableRef[A, B]): var B = + ## Iterates over any value in the table `t`. The values can be modified. + ## + ## See also: + ## * `mpairs iterator<#mpairs.i,TableRef[A,B]>`_ + ## * `values iterator<#values.i,TableRef[A,B]>`_ + runnableExamples: + let a = { + 'o': @[1, 5, 7, 9], + 'e': @[2, 4, 6, 8] + }.newTable + for v in a.mvalues: + v.add(99) + doAssert a == {'e': @[2, 4, 6, 8, 99], 'o': @[1, 5, 7, 9, 99]}.newTable + + let L = len(t) + for h in 0 .. high(t.data): + if isFilled(t.data[h].hcode): + yield t.data[h].val + assert(len(t) == L, "the length of the table changed while iterating over it") -proc clear*[A, B](t: var OrderedTable[A, B]) = - ## 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. - clear(t[]) -template forAllOrderedPairs(yieldStmt: untyped): typed {.dirty.} = - var h = t.first - while h >= 0: - var nxt = t.data[h].next - if isFilled(t.data[h].hcode): yieldStmt - h = nxt -iterator pairs*[A, B](t: OrderedTable[A, B]): (A, B) = - ## 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 - ## 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. - 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. - 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 - ## can be modified. - forAllOrderedPairs: - yield t.data[h].val +# --------------------------------------------------------------------------- +# ------------------------------ OrderedTable ------------------------------- +# --------------------------------------------------------------------------- + +type + OrderedKeyValuePair[A, B] = tuple[ + hcode: Hash, next: int, key: A, val: B] + OrderedKeyValuePairSeq[A, B] = seq[OrderedKeyValuePair[A, B]] + OrderedTable*[A, B] = object + ## Hash table that remembers insertion order. + ## + ## For creating an empty OrderedTable, use `initOrderedTable proc + ## <#initOrderedTable>`_. + data: OrderedKeyValuePairSeq[A, B] + counter, first, last: int + OrderedTableRef*[A, B] = ref OrderedTable[A, B] ## Ref version of + ## `OrderedTable<#OrderedTable>`_. + ## + ## For creating a new empty OrderedTableRef, use `newOrderedTable proc + ## <#newOrderedTable>`_. + + +# ------------------------------ helpers --------------------------------- proc rawGetKnownHC[A, B](t: OrderedTable[A, B], key: A, hc: Hash): int = rawGetKnownHCImpl() @@ -566,46 +1296,9 @@ proc rawGetDeep[A, B](t: OrderedTable[A, B], key: A, hc: var Hash): int {.inline 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 - ## ``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. - 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. - 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 - ## 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. - getOrDefaultImpl(t, key, default) - -proc hasKey*[A, B](t: OrderedTable[A, B], key: A): bool = - ## 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. - return hasKey[A, B](t, key) - proc rawInsert[A, B](t: var OrderedTable[A, B], data: var OrderedKeyValuePairSeq[A, B], - key: A, val: B, hc: Hash, h: Hash) = + key: A, val: sink B, hc: Hash, h: Hash) = rawInsertImpl() data[h].next = -1 if t.first < 0: t.first = h @@ -626,70 +1319,344 @@ proc enlarge[A, B](t: var OrderedTable[A, B]) = var j: Hash = eh and maxHash(t) while isFilled(t.data[j].hcode): j = nextTry(j, maxHash(t)) - rawInsert(t, t.data, n[h].key, n[h].val, n[h].hcode, j) + rawInsert(t, t.data, move n[h].key, move n[h].val, n[h].hcode, j) h = nxt -proc `[]=`*[A, B](t: var OrderedTable[A, B], key: A, val: B) = - ## puts a (key, value)-pair into `t`. +template forAllOrderedPairs(yieldStmt: untyped) {.dirty.} = + if t.counter > 0: + var h = t.first + while h >= 0: + var nxt = t.data[h].next + if isFilled(t.data[h].hcode): + yieldStmt + h = nxt + +# ---------------------------------------------------------------------- + +proc initOrderedTable*[A, B](initialSize = defaultInitialSize): OrderedTable[A, B] = + ## Creates a new ordered hash table that is empty. + ## + ## Starting from Nim v0.20, tables are initialized by default and it is + ## not necessary to call this function explicitly. + ## + ## See also: + ## * `toOrderedTable proc<#toOrderedTable,openArray[]>`_ + ## * `newOrderedTable proc<#newOrderedTable>`_ for creating an + ## `OrderedTableRef` + runnableExamples: + 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`. + ## + ## See also: + ## * `[] proc<#[],OrderedTable[A,B],A>`_ for retrieving a value of a key + ## * `hasKeyOrPut proc<#hasKeyOrPut,OrderedTable[A,B],A,B>`_ + ## * `mgetOrPut proc<#mgetOrPut,OrderedTable[A,B],A,B>`_ + ## * `del proc<#del,OrderedTable[A,B],A>`_ for removing a key from the table + runnableExamples: + var a = initOrderedTable[char, int]() + a['x'] = 7 + a['y'] = 33 + doAssert a == {'x': 7, 'y': 33}.toOrderedTable + 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. - ## This can introduce duplicate keys into the table! - addImpl(enlarge) +proc toOrderedTable*[A, B](pairs: openArray[(A, B)]): OrderedTable[A, B] = + ## Creates a new ordered hash table that contains the given `pairs`. + ## + ## `pairs` is a container consisting of `(key, value)` tuples. + ## + ## See also: + ## * `initOrderedTable proc<#initOrderedTable>`_ + ## * `newOrderedTable proc<#newOrderedTable,openArray[]>`_ for an + ## `OrderedTableRef` version + runnableExamples: + let a = [('a', 5), ('b', 9)] + let b = toOrderedTable(a) + assert b == {'a': 5, 'b': 9}.toOrderedTable + + result = initOrderedTable[A, B](pairs.len) + for key, val in items(pairs): result[key] = val + +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. + ## One can check with `hasKey proc<#hasKey,OrderedTable[A,B],A>`_ whether + ## the key exists. + ## + ## See also: + ## * `getOrDefault proc<#getOrDefault,OrderedTable[A,B],A>`_ to return + ## a default value (e.g. zero for int) if the key doesn't exist + ## * `getOrDefault proc<#getOrDefault,OrderedTable[A,B],A,B>`_ to return + ## a custom value if the key doesn't exist + ## * `[]= proc<#[]=,OrderedTable[A,B],A,sinkB>`_ for inserting a new + ## (key, value) pair in the table + ## * `hasKey proc<#hasKey,OrderedTable[A,B],A>`_ for checking if a + ## key is in the table + runnableExamples: + let a = {'a': 5, 'b': 9}.toOrderedTable + doAssert a['a'] == 5 + doAssertRaises(KeyError): + echo a['z'] + + 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. + ## + ## If `key` is not in `t`, the `KeyError` exception is raised. + ## + ## See also: + ## * `getOrDefault proc<#getOrDefault,OrderedTable[A,B],A>`_ to return + ## a default value (e.g. zero for int) if the key doesn't exist + ## * `getOrDefault proc<#getOrDefault,OrderedTable[A,B],A,B>`_ to return + ## a custom value if the key doesn't exist + ## * `[]= proc<#[]=,OrderedTable[A,B],A,sinkB>`_ for inserting a new + ## (key, value) pair in the table + ## * `hasKey proc<#hasKey,OrderedTable[A,B],A>`_ for checking if a + ## key is in the table + get(t, key) + +proc hasKey*[A, B](t: OrderedTable[A, B], key: A): bool = + ## Returns true if `key` is in the table `t`. + ## + ## See also: + ## * `contains proc<#contains,OrderedTable[A,B],A>`_ for use with the `in` + ## operator + ## * `[] proc<#[],OrderedTable[A,B],A>`_ for retrieving a value of a key + ## * `getOrDefault proc<#getOrDefault,OrderedTable[A,B],A>`_ to return + ## a default value (e.g. zero for int) if the key doesn't exist + ## * `getOrDefault proc<#getOrDefault,OrderedTable[A,B],A,B>`_ to return + ## a custom value if the key doesn't exist + runnableExamples: + let a = {'a': 5, 'b': 9}.toOrderedTable + doAssert a.hasKey('a') == true + doAssert a.hasKey('z') == false + + 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. + runnableExamples: + let a = {'a': 5, 'b': 9}.toOrderedTable + doAssert 'b' in a == true + doAssert a.contains('z') == false + + 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`. + ## + ## See also: + ## * `hasKey proc<#hasKey,OrderedTable[A,B],A>`_ + ## * `[] proc<#[],OrderedTable[A,B],A>`_ for retrieving a value of a key + ## * `getOrDefault proc<#getOrDefault,OrderedTable[A,B],A>`_ to return + ## a default value (e.g. zero for int) if the key doesn't exist + ## * `getOrDefault proc<#getOrDefault,OrderedTable[A,B],A,B>`_ to return + ## a custom value if the key doesn't exist + runnableExamples: + var a = {'a': 5, 'b': 9}.toOrderedTable + if a.hasKeyOrPut('a', 50): + a['a'] = 99 + if a.hasKeyOrPut('z', 50): + a['z'] = 99 + doAssert a == {'a': 99, 'b': 9, 'z': 50}.toOrderedTable + + 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 + ## integer type). + ## + ## See also: + ## * `[] proc<#[],OrderedTable[A,B],A>`_ for retrieving a value of a key + ## * `hasKey proc<#hasKey,OrderedTable[A,B],A>`_ + ## * `hasKeyOrPut proc<#hasKeyOrPut,OrderedTable[A,B],A,B>`_ + ## * `mgetOrPut proc<#mgetOrPut,OrderedTable[A,B],A,B>`_ + ## * `getOrDefault proc<#getOrDefault,OrderedTable[A,B],A,B>`_ to return + ## a custom value if the key doesn't exist + runnableExamples: + 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. + ## + ## See also: + ## * `[] proc<#[],OrderedTable[A,B],A>`_ for retrieving a value of a key + ## * `hasKey proc<#hasKey,OrderedTable[A,B],A>`_ + ## * `hasKeyOrPut proc<#hasKeyOrPut,OrderedTable[A,B],A,B>`_ + ## * `mgetOrPut proc<#mgetOrPut,OrderedTable[A,B],A,B>`_ + ## * `getOrDefault proc<#getOrDefault,OrderedTable[A,B],A>`_ to return + ## a default value (e.g. zero for int) if the key doesn't exist + runnableExamples: + 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 ``value`` 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: + ## * `[] proc<#[],OrderedTable[A,B],A>`_ for retrieving a value of a key + ## * `hasKey proc<#hasKey,OrderedTable[A,B],A>`_ + ## * `hasKeyOrPut proc<#hasKeyOrPut,OrderedTable[A,B],A,B>`_ + ## * `getOrDefault proc<#getOrDefault,OrderedTable[A,B],A>`_ to return + ## a default value (e.g. zero for int) if the key doesn't exist + ## * `getOrDefault proc<#getOrDefault,OrderedTable[A,B],A,B>`_ to return + ## a custom value if the key doesn't exist + runnableExamples: + var a = {'a': 5, 'b': 9}.toOrderedTable + doAssert a.mgetOrPut('a', 99) == 5 + doAssert a.mgetOrPut('z', 99) == 99 + doAssert a == {'a': 5, 'b': 9, 'z': 99}.toOrderedTable + 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`. - hasKeyOrPutImpl(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`. + runnableExamples: + let a = {'a': 5, 'b': 9}.toOrderedTable + doAssert len(a) == 2 + + result = t.counter -proc initOrderedTable*[A, B](initialSize=64): OrderedTable[A, B] = - ## creates a new ordered hash table that is empty. +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. + ## + ## **This can introduce duplicate keys into the table!** ## - ## `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) - result.counter = 0 - result.first = -1 - result.last = -1 - newSeq(result.data, initialSize) + ## Use `[]= proc<#[]=,OrderedTable[A,B],A,sinkB>`_ for inserting a new + ## (key, value) pair in the table without introducing duplicates. + addImpl(enlarge) -proc toOrderedTable*[A, B](pairs: openArray[(A, B)]): OrderedTable[A, B] = - ## 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 del*[A, B](t: var OrderedTable[A, B], key: A) = + ## Deletes `key` from hash table `t`. Does nothing if the key does not exist. + ## + ## O(n) complexity. + ## + ## See also: + ## * `pop proc<#pop,OrderedTable[A,B],A,B>`_ + ## * `clear proc<#clear,OrderedTable[A,B]>`_ to empty the whole table + runnableExamples: + var a = {'a': 5, 'b': 9, 'c': 13}.toOrderedTable + a.del('a') + doAssert a == {'b': 9, 'c': 13}.toOrderedTable + a.del('z') + doAssert a == {'b': 9, 'c': 13}.toOrderedTable -proc `$`*[A, B](t: OrderedTable[A, B]): string = - ## The `$` operator for ordered hash tables. - dollarImpl() + if t.counter == 0: return + var n: OrderedKeyValuePairSeq[A, B] + newSeq(n, len(t.data)) + var h = t.first + t.first = -1 + t.last = -1 + swap(t.data, n) + let hc = genHash(key) + while h >= 0: + var nxt = n[h].next + if isFilled(n[h].hcode): + if n[h].hcode == hc and n[h].key == key: + dec t.counter + else: + var j = -1 - rawGetKnownHC(t, n[h].key, n[h].hcode) + rawInsert(t, t.data, move n[h].key, move n[h].val, n[h].hcode, j) + h = nxt -proc `==`*[A, B](s, t: OrderedTable[A, B]): bool = - ## The `==` operator for ordered hash tables. Returns true iff both the - ## content and the order are equal. - if s.counter != t.counter: - return false - var ht = t.first - var hs = s.first - while ht >= 0 and hs >= 0: - var nxtt = t.data[ht].next - var nxts = s.data[hs].next - if isFilled(t.data[ht].hcode) and isFilled(s.data[hs].hcode): - if (s.data[hs].key != t.data[ht].key) or (s.data[hs].val != t.data[ht].val): - return false - ht = nxtt - hs = nxts - return true +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 + ## unchanged. + ## + ## O(n) complexity. + ## + ## See also: + ## * `del proc<#del,OrderedTable[A,B],A>`_ + ## * `clear proc<#clear,OrderedTable[A,B]>`_ to empty the whole table + runnableExamples: + var + a = {'c': 5, 'b': 9, 'a': 13}.toOrderedTable + i: int + doAssert a.pop('b', i) == true + doAssert a == {'c': 5, 'a': 13}.toOrderedTable + doAssert i == 9 + i = 0 + doAssert a.pop('z', i) == false + doAssert a == {'c': 5, 'a': 13}.toOrderedTable + doAssert i == 0 + + var hc: Hash + var index = rawGet(t, key, hc) + result = index >= 0 + if result: + val = move(t.data[index].val) + del(t, key) -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 +proc clear*[A, B](t: var OrderedTable[A, B]) = + ## Resets the table so that it is empty. + ## + ## See also: + ## * `del proc<#del,OrderedTable[A,B],A>`_ + ## * `pop proc<#pop,OrderedTable[A,B],A,B>`_ + runnableExamples: + var a = {'a': 5, 'b': 9, 'c': 13}.toOrderedTable + doAssert len(a) == 3 + clear(a) + doAssert len(a) == 0 + + clearImpl() + t.first = -1 + t.last = -1 + +proc sort*[A, B](t: var OrderedTable[A, B], cmp: proc (x, y: (A, B)): int, + 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 - ## contrast to the `sort` for count tables). + ## contrast to the `sort proc<#sort,CountTable[A]>`_ for count tables). + runnableExamples: + import std/[algorithm] + var a = initOrderedTable[char, int]() + for i, c in "cab": + a[c] = 10*i + doAssert a == {'c': 0, 'a': 10, 'b': 20}.toOrderedTable + a.sort(system.cmp) + doAssert a == {'a': 10, 'b': 20, 'c': 0}.toOrderedTable + a.sort(system.cmp, order = SortOrder.Descending) + doAssert a == {'c': 0, 'b': 20, 'a': 10}.toOrderedTable + var list = t.first var p, q, e, tail, oldhead: int @@ -716,7 +1683,7 @@ proc sort*[A, B](t: var OrderedTable[A, B], cmp: proc (x,y: (A, B)): int) = elif qsize == 0 or q < 0: e = p; p = t.data[p].next; dec(psize) elif cmp((t.data[p].key, t.data[p].val), - (t.data[q].key, t.data[q].val)) <= 0: + (t.data[q].key, t.data[q].val)) * order <= 0: e = p; p = t.data[p].next; dec(psize) else: e = q; q = t.data[q].next; dec(qsize) @@ -730,246 +1697,607 @@ proc sort*[A, B](t: var OrderedTable[A, B], cmp: proc (x,y: (A, B)): int) = t.first = list t.last = tail -proc len*[A, B](t: OrderedTableRef[A, B]): int {.inline.} = - ## returns the number of keys in `t`. - result = t.counter +proc `$`*[A, B](t: OrderedTable[A, B]): string = + ## The `$` operator for ordered hash tables. Used internally when calling + ## `echo` on a table. + dollarImpl() -iterator pairs*[A, B](t: OrderedTableRef[A, B]): (A, B) = - ## iterates over any (key, value) pair in the table `t` in insertion +proc `==`*[A, B](s, t: OrderedTable[A, B]): bool = + ## The `==` operator for ordered hash tables. Returns `true` if both the + ## content and the order are equal. + runnableExamples: + let + a = {'a': 5, 'b': 9, 'c': 13}.toOrderedTable + b = {'b': 9, 'c': 13, 'a': 5}.toOrderedTable + doAssert a != b + + if s.counter != t.counter: + return false + if s.counter == 0 and t.counter == 0: + return true + var ht = t.first + var hs = s.first + while ht >= 0 and hs >= 0: + var nxtt = t.data[ht].next + var nxts = s.data[hs].next + if isFilled(t.data[ht].hcode) and isFilled(s.data[hs].hcode): + if (s.data[hs].key != t.data[ht].key) or (s.data[hs].val != t.data[ht].val): + return false + ht = nxtt + hs = nxts + return true + + + +iterator pairs*[A, B](t: OrderedTable[A, B]): (A, B) = + ## Iterates over any `(key, value)` pair in the table `t` in insertion ## order. + ## + ## See also: + ## * `mpairs iterator<#mpairs.i,OrderedTable[A,B]>`_ + ## * `keys iterator<#keys.i,OrderedTable[A,B]>`_ + ## * `values iterator<#values.i,OrderedTable[A,B]>`_ + ## + ## **Examples:** + ## + ## ```Nim + ## let a = { + ## 'o': [1, 5, 7, 9], + ## 'e': [2, 4, 6, 8] + ## }.toOrderedTable + ## + ## for k, v in a.pairs: + ## echo "key: ", k + ## echo "value: ", v + ## + ## # key: o + ## # value: [1, 5, 7, 9] + ## # key: e + ## # value: [2, 4, 6, 8] + ## ``` + + let L = len(t) forAllOrderedPairs: yield (t.data[h].key, t.data[h].val) + 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 - ## order. The values can be modified. +iterator mpairs*[A, B](t: var OrderedTable[A, B]): (A, var B) = + ## 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: + ## * `pairs iterator<#pairs.i,OrderedTable[A,B]>`_ + ## * `mvalues iterator<#mvalues.i,OrderedTable[A,B]>`_ + runnableExamples: + var a = { + 'o': @[1, 5, 7, 9], + 'e': @[2, 4, 6, 8] + }.toOrderedTable + for k, v in a.mpairs: + v.add(v[0] + 10) + doAssert a == {'o': @[1, 5, 7, 9, 11], + 'e': @[2, 4, 6, 8, 12]}.toOrderedTable + + let L = len(t) forAllOrderedPairs: 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: 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]>`_ + ## * `values iterator<#values.i,OrderedTable[A,B]>`_ + runnableExamples: + var a = { + 'o': @[1, 5, 7, 9], + 'e': @[2, 4, 6, 8] + }.toOrderedTable + for k in a.keys: + a[k].add(99) + doAssert a == {'o': @[1, 5, 7, 9, 99], + 'e': @[2, 4, 6, 8, 99]}.toOrderedTable + + let L = len(t) forAllOrderedPairs: 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: 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]>`_ + ## * `keys iterator<#keys.i,OrderedTable[A,B]>`_ + ## * `mvalues iterator<#mvalues.i,OrderedTable[A,B]>`_ + runnableExamples: + let a = { + 'o': @[1, 5, 7, 9], + 'e': @[2, 4, 6, 8] + }.toOrderedTable + for v in a.values: + doAssert v.len == 4 + + let L = len(t) forAllOrderedPairs: yield t.data[h].val + 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 +iterator mvalues*[A, B](t: var OrderedTable[A, B]): var B = + ## Iterates over any value in the table `t` (must be + ## declared as `var`) in insertion order. The values ## can be modified. + ## + ## See also: + ## * `mpairs iterator<#mpairs.i,OrderedTable[A,B]>`_ + ## * `values iterator<#values.i,OrderedTable[A,B]>`_ + runnableExamples: + var a = { + 'o': @[1, 5, 7, 9], + 'e': @[2, 4, 6, 8] + }.toOrderedTable + for v in a.mvalues: + v.add(99) + doAssert a == {'o': @[1, 5, 7, 9, 99], + 'e': @[2, 4, 6, 8, 99]}.toOrderedTable + + let L = len(t) forAllOrderedPairs: yield t.data[h].val + assert(len(t) == L, "the length of the table changed while iterating over it") + +# --------------------------------------------------------------------------- +# --------------------------- OrderedTableRef ------------------------------- +# --------------------------------------------------------------------------- + +proc newOrderedTable*[A, B](initialSize = defaultInitialSize): OrderedTableRef[A, B] = + ## Creates a new ordered ref hash table that is empty. + ## + ## See also: + ## * `newOrderedTable proc<#newOrderedTable,openArray[]>`_ for creating + ## an `OrderedTableRef` from a collection of `(key, value)` pairs + ## * `initOrderedTable proc<#initOrderedTable>`_ for creating an + ## `OrderedTable` + runnableExamples: + let + a = newOrderedTable[int, string]() + b = newOrderedTable[char, seq[int]]() + new(result) + {.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`. + ## + ## `pairs` is a container consisting of `(key, value)` tuples. + ## + ## See also: + ## * `newOrderedTable proc<#newOrderedTable>`_ + ## * `toOrderedTable proc<#toOrderedTable,openArray[]>`_ for an + ## `OrderedTable` version + runnableExamples: + let a = [('a', 5), ('b', 9)] + let b = newOrderedTable(a) + assert b == {'a': 5, 'b': 9}.newOrderedTable + + result = newOrderedTable[A, B](pairs.len) + {.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]``. If `key` is not in `t`, the - ## ``KeyError`` exception is raised. One can check with ``hasKey`` whether + ## Retrieves the value at `t[key]`. + ## + ## 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. + ## + ## See also: + ## * `getOrDefault proc<#getOrDefault,OrderedTableRef[A,B],A>`_ to return + ## a default value (e.g. zero for int) if the key doesn't exist + ## * `getOrDefault proc<#getOrDefault,OrderedTableRef[A,B],A,B>`_ to return + ## a custom value if the key doesn't exist + ## * `[]= proc<#[]=,OrderedTableRef[A,B],A,sinkB>`_ for inserting a new + ## (key, value) pair in the table + ## * `hasKey proc<#hasKey,OrderedTableRef[A,B],A>`_ for checking if + ## a key is in the table + runnableExamples: + let a = {'a': 5, 'b': 9}.newOrderedTable + doAssert a['a'] == 5 + doAssertRaises(KeyError): + echo a['z'] 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. - result = t[][key] +proc `[]=`*[A, B](t: OrderedTableRef[A, B], key: A, val: sink B) = + ## Inserts a `(key, value)` pair into `t`. + ## + ## See also: + ## * `[] proc<#[],OrderedTableRef[A,B],A>`_ for retrieving a value of a key + ## * `hasKeyOrPut proc<#hasKeyOrPut,OrderedTableRef[A,B],A,B>`_ + ## * `mgetOrPut proc<#mgetOrPut,OrderedTableRef[A,B],A,B>`_ + ## * `del proc<#del,OrderedTableRef[A,B],A>`_ for removing a key from the table + runnableExamples: + var a = newOrderedTable[char, int]() + a['x'] = 7 + a['y'] = 33 + doAssert a == {'x': 7, 'y': 33}.newOrderedTable + + t[][key] = val + +proc hasKey*[A, B](t: OrderedTableRef[A, B], key: A): bool = + ## Returns true if `key` is in the table `t`. + ## + ## See also: + ## * `contains proc<#contains,OrderedTableRef[A,B],A>`_ for use with the `in` + ## operator + ## * `[] proc<#[],OrderedTableRef[A,B],A>`_ for retrieving a value of a key + ## * `getOrDefault proc<#getOrDefault,OrderedTableRef[A,B],A>`_ to return + ## a default value (e.g. zero for int) if the key doesn't exist + ## * `getOrDefault proc<#getOrDefault,OrderedTableRef[A,B],A,B>`_ to return + ## a custom value if the key doesn't exist + runnableExamples: + let a = {'a': 5, 'b': 9}.newOrderedTable + doAssert a.hasKey('a') == true + doAssert a.hasKey('z') == false + + result = t[].hasKey(key) + +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. + runnableExamples: + let a = {'a': 5, 'b': 9}.newOrderedTable + doAssert 'b' in a == true + doAssert a.contains('z') == false + + return hasKey[A, B](t, key) + +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>`_ + ## * `[] proc<#[],OrderedTableRef[A,B],A>`_ for retrieving a value of a key + ## * `getOrDefault proc<#getOrDefault,OrderedTableRef[A,B],A>`_ to return + ## a default value (e.g. zero for int) if the key doesn't exist + ## * `getOrDefault proc<#getOrDefault,OrderedTableRef[A,B],A,B>`_ to return + ## a custom value if the key doesn't exist + runnableExamples: + var a = {'a': 5, 'b': 9}.newOrderedTable + if a.hasKeyOrPut('a', 50): + a['a'] = 99 + if a.hasKeyOrPut('z', 50): + a['z'] = 99 + doAssert a == {'a': 99, 'b': 9, 'z': 50}.newOrderedTable + + result = t[].hasKeyOrPut(key, val) proc getOrDefault*[A, B](t: OrderedTableRef[A, B], key: A): B = - ## retrieves the value at ``t[key]`` iff `key` is in `t`. Otherwise, the + ## 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: + ## * `[] proc<#[],OrderedTableRef[A,B],A>`_ for retrieving a value of a key + ## * `hasKey proc<#hasKey,OrderedTableRef[A,B],A>`_ + ## * `hasKeyOrPut proc<#hasKeyOrPut,OrderedTableRef[A,B],A,B>`_ + ## * `mgetOrPut proc<#mgetOrPut,OrderedTableRef[A,B],A,B>`_ + ## * `getOrDefault proc<#getOrDefault,OrderedTableRef[A,B],A,B>`_ to return + ## a custom value if the key doesn't exist + runnableExamples: + let a = {'a': 5, 'b': 9}.newOrderedTable + doAssert a.getOrDefault('a') == 5 + doAssert a.getOrDefault('z') == 0 + 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]` if `key` is in `t`. + ## Otherwise, `default` is returned. + ## + ## See also: + ## * `[] proc<#[],OrderedTableRef[A,B],A>`_ for retrieving a value of a key + ## * `hasKey proc<#hasKey,OrderedTableRef[A,B],A>`_ + ## * `hasKeyOrPut proc<#hasKeyOrPut,OrderedTableRef[A,B],A,B>`_ + ## * `mgetOrPut proc<#mgetOrPut,OrderedTableRef[A,B],A,B>`_ + ## * `getOrDefault proc<#getOrDefault,OrderedTableRef[A,B],A>`_ to return + ## a default value (e.g. zero for int) if the key doesn't exist + runnableExamples: + let a = {'a': 5, 'b': 9}.newOrderedTable + doAssert a.getOrDefault('a', 99) == 5 + doAssert a.getOrDefault('z', 99) == 99 + 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: + ## * `[] proc<#[],OrderedTableRef[A,B],A>`_ for retrieving a value of a key + ## * `hasKey proc<#hasKey,OrderedTableRef[A,B],A>`_ + ## * `hasKeyOrPut proc<#hasKeyOrPut,OrderedTableRef[A,B],A,B>`_ + ## * `getOrDefault proc<#getOrDefault,OrderedTableRef[A,B],A>`_ to return + ## a default value (e.g. zero for int) if the key doesn't exist + ## * `getOrDefault proc<#getOrDefault,OrderedTableRef[A,B],A,B>`_ to return + ## a custom value if the key doesn't exist + runnableExamples: + var a = {'a': 5, 'b': 9}.newOrderedTable + doAssert a.mgetOrPut('a', 99) == 5 + doAssert a.mgetOrPut('z', 99) == 99 + doAssert a == {'a': 5, 'b': 9, 'z': 99}.newOrderedTable + 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`. - result = t[].hasKeyOrPut(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 -proc hasKey*[A, B](t: OrderedTableRef[A, B], key: A): bool = - ## returns true iff `key` is in the table `t`. - result = t[].hasKey(key) + t[].mgetOrPut(key) -proc contains*[A, B](t: OrderedTableRef[A, B], key: A): bool = - ## alias of `hasKey` for use with the `in` operator. - return hasKey[A, B](t, key) +proc len*[A, B](t: OrderedTableRef[A, B]): int {.inline.} = + ## Returns the number of keys in `t`. + runnableExamples: + let a = {'a': 5, 'b': 9}.newOrderedTable + doAssert len(a) == 2 -proc `[]=`*[A, B](t: OrderedTableRef[A, B], key: A, val: B) = - ## puts a (key, value)-pair into `t`. - t[][key] = val + result = t.counter -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. - ## This can introduce duplicate keys into the table! +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. + ## + ## **This can introduce duplicate keys into the table!** + ## + ## Use `[]= proc<#[]=,OrderedTableRef[A,B],A,sinkB>`_ for inserting a new + ## (key, value) pair in the table without introducing duplicates. t[].add(key, val) -proc newOrderedTable*[A, B](initialSize=64): OrderedTableRef[A, B] = - ## creates a new ordered hash table that is empty. +proc del*[A, B](t: OrderedTableRef[A, B], key: A) = + ## Deletes `key` from hash table `t`. Does nothing if the key does not exist. ## - ## `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) + ## See also: + ## * `clear proc<#clear,OrderedTableRef[A,B]>`_ to empty the whole table + runnableExamples: + var a = {'a': 5, 'b': 9, 'c': 13}.newOrderedTable + a.del('a') + doAssert a == {'b': 9, 'c': 13}.newOrderedTable + a.del('z') + doAssert a == {'b': 9, 'c': 13}.newOrderedTable -proc newOrderedTable*[A, B](pairs: openArray[(A, B)]): OrderedTableRef[A, B] = - ## 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) + 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 + ## unchanged. + ## + ## See also: + ## * `del proc<#del,OrderedTableRef[A,B],A>`_ + ## * `clear proc<#clear,OrderedTableRef[A,B]>`_ to empty the whole table + runnableExamples: + var + a = {'c': 5, 'b': 9, 'a': 13}.newOrderedTable + i: int + doAssert a.pop('b', i) == true + doAssert a == {'c': 5, 'a': 13}.newOrderedTable + doAssert i == 9 + i = 0 + doAssert a.pop('z', i) == false + doAssert a == {'c': 5, 'a': 13}.newOrderedTable + doAssert i == 0 + + pop(t[], key, val) + +proc clear*[A, B](t: OrderedTableRef[A, B]) = + ## Resets the table so that it is empty. + ## + ## See also: + ## * `del proc<#del,OrderedTableRef[A,B],A>`_ + runnableExamples: + var a = {'a': 5, 'b': 9, 'c': 13}.newOrderedTable + doAssert len(a) == 3 + clear(a) + doAssert len(a) == 0 + + clear(t[]) + +proc sort*[A, B](t: OrderedTableRef[A, B], cmp: proc (x, y: (A, B)): int, + 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 + ## contrast to the `sort proc<#sort,CountTableRef[A]>`_ for count tables). + runnableExamples: + import std/[algorithm] + var a = newOrderedTable[char, int]() + for i, c in "cab": + a[c] = 10*i + doAssert a == {'c': 0, 'a': 10, 'b': 20}.newOrderedTable + a.sort(system.cmp) + doAssert a == {'a': 10, 'b': 20, 'c': 0}.newOrderedTable + a.sort(system.cmp, order = SortOrder.Descending) + doAssert a == {'c': 0, 'b': 20, 'a': 10}.newOrderedTable + + t[].sort(cmp, order = order) proc `$`*[A, B](t: OrderedTableRef[A, B]): string = - ## The `$` operator for ordered hash tables. + ## 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 iff either both - ## tables are ``nil`` or none 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 + a = {'a': 5, 'b': 9, 'c': 13}.newOrderedTable + b = {'b': 9, 'c': 13, 'a': 5}.newOrderedTable + doAssert a != b + if isNil(s): result = isNil(t) elif isNil(t): result = false 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 - ## 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). - t[].sort(cmp) -proc del*[A, B](t: var OrderedTable[A, B], key: A) = - ## deletes `key` from ordered hash table `t`. O(n) complexity. - var n: OrderedKeyValuePairSeq[A, B] - newSeq(n, len(t.data)) - var h = t.first - t.first = -1 - t.last = -1 - swap(t.data, n) - let hc = genHash(key) - while h >= 0: - var nxt = n[h].next - if isFilled(n[h].hcode): - if n[h].hcode == hc and n[h].key == key: - dec t.counter - else: - var j = -1 - rawGetKnownHC(t, n[h].key, n[h].hcode) - rawInsert(t, t.data, n[h].key, n[h].val, n[h].hcode, j) - h = nxt -proc del*[A, B](t: var OrderedTableRef[A, B], key: A) = - ## deletes `key` from ordered hash table `t`. O(n) complexity. - t[].del(key) - -# ------------------------------ count tables ------------------------------- +iterator pairs*[A, B](t: OrderedTableRef[A, B]): (A, B) = + ## Iterates over any `(key, value)` pair in the table `t` in insertion + ## order. + ## + ## See also: + ## * `mpairs iterator<#mpairs.i,OrderedTableRef[A,B]>`_ + ## * `keys iterator<#keys.i,OrderedTableRef[A,B]>`_ + ## * `values iterator<#values.i,OrderedTableRef[A,B]>`_ + ## + ## **Examples:** + ## + ## ```Nim + ## let a = { + ## 'o': [1, 5, 7, 9], + ## 'e': [2, 4, 6, 8] + ## }.newOrderedTable + ## + ## for k, v in a.pairs: + ## echo "key: ", k + ## echo "value: ", v + ## + ## # key: o + ## # value: [1, 5, 7, 9] + ## # key: e + ## # value: [2, 4, 6, 8] + ## ``` -type - CountTable* [ - A] = object ## table that counts the number of each key - data: seq[tuple[key: A, val: int]] - counter: int - CountTableRef*[A] = ref CountTable[A] + let L = len(t) + forAllOrderedPairs: + yield (t.data[h].key, t.data[h].val) + assert(len(t) == L, "the length of the table changed while iterating over it") -{.deprecated: [TCountTable: CountTable, PCountTable: CountTableRef].} +iterator mpairs*[A, B](t: OrderedTableRef[A, B]): (A, var B) = + ## Iterates over any `(key, value)` pair in the table `t` in insertion + ## order. The values can be modified. + ## + ## See also: + ## * `pairs iterator<#pairs.i,OrderedTableRef[A,B]>`_ + ## * `mvalues iterator<#mvalues.i,OrderedTableRef[A,B]>`_ + runnableExamples: + let a = { + 'o': @[1, 5, 7, 9], + 'e': @[2, 4, 6, 8] + }.newOrderedTable + for k, v in a.mpairs: + v.add(v[0] + 10) + doAssert a == {'o': @[1, 5, 7, 9, 11], + 'e': @[2, 4, 6, 8, 12]}.newOrderedTable + + let L = len(t) + forAllOrderedPairs: + yield (t.data[h].key, t.data[h].val) + assert(len(t) == L, "the length of the table changed while iterating over it") -proc len*[A](t: CountTable[A]): int = - ## returns the number of keys in `t`. - result = t.counter +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]>`_ + ## * `values iterator<#values.i,OrderedTableRef[A,B]>`_ + runnableExamples: + let a = { + 'o': @[1, 5, 7, 9], + 'e': @[2, 4, 6, 8] + }.newOrderedTable + for k in a.keys: + a[k].add(99) + doAssert a == {'o': @[1, 5, 7, 9, 99], 'e': @[2, 4, 6, 8, + 99]}.newOrderedTable + + let L = len(t) + forAllOrderedPairs: + yield t.data[h].key + assert(len(t) == L, "the length of the table changed while iterating over it") -proc clear*[A](t: CountTableRef[A]) = - ## Resets the table so that it is empty. - clearImpl() +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]>`_ + ## * `keys iterator<#keys.i,OrderedTableRef[A,B]>`_ + ## * `mvalues iterator<#mvalues.i,OrderedTableRef[A,B]>`_ + runnableExamples: + let a = { + 'o': @[1, 5, 7, 9], + 'e': @[2, 4, 6, 8] + }.newOrderedTable + for v in a.values: + doAssert v.len == 4 + + let L = len(t) + forAllOrderedPairs: + yield t.data[h].val + assert(len(t) == L, "the length of the table changed while iterating over it") -proc clear*[A](t: var CountTable[A]) = - ## Resets the table so that it is empty. - clearImpl() +iterator mvalues*[A, B](t: OrderedTableRef[A, B]): var B = + ## Iterates over any value in the table `t` in insertion order. The values + ## can be modified. + ## + ## See also: + ## * `mpairs iterator<#mpairs.i,OrderedTableRef[A,B]>`_ + ## * `values iterator<#values.i,OrderedTableRef[A,B]>`_ + runnableExamples: + let a = { + 'o': @[1, 5, 7, 9], + 'e': @[2, 4, 6, 8] + }.newOrderedTable + for v in a.mvalues: + v.add(99) + doAssert a == {'o': @[1, 5, 7, 9, 99], + 'e': @[2, 4, 6, 8, 99]}.newOrderedTable + + let L = len(t) + forAllOrderedPairs: + yield t.data[h].val + assert(len(t) == L, "the length of the table changed while iterating over it") -iterator pairs*[A](t: CountTable[A]): (A, int) = - ## 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 - ## 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`. - 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`. - 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. - for h in 0..high(t.data): - if t.data[h].val != 0: yield t.data[h].val -proc rawGet[A](t: CountTable[A], key: A): int = - var h: Hash = hash(key) and high(t.data) # start with real hash value - while t.data[h].val != 0: - if t.data[h].key == key: return h - h = nextTry(h, high(t.data)) - result = -1 - h # < 0 => MISSING; insert idx = -1 - result -template ctget(t, key: untyped): untyped = - var index = rawGet(t, key) - 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") - -proc `[]`*[A](t: CountTable[A], key: A): int {.deprecatedGet.} = - ## 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. - 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. - 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. - var index = rawGet(t, key) - if index >= 0: result = t.data[index].val +# ------------------------------------------------------------------------- +# ------------------------------ CountTable ------------------------------- +# ------------------------------------------------------------------------- -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. - var index = rawGet(t, key) - result = if index >= 0: t.data[index].val else: default +type + CountTable*[A] = object + ## Hash table that counts the number of each key. + ## + ## For creating an empty CountTable, use `initCountTable proc + ## <#initCountTable>`_. + data: seq[tuple[key: A, val: int]] + counter: int + isSorted: bool + CountTableRef*[A] = ref CountTable[A] ## Ref version of + ## `CountTable<#CountTable>`_. + ## + ## For creating a new empty CountTableRef, use `newCountTable proc + ## <#newCountTable>`_. -proc hasKey*[A](t: CountTable[A], key: A): bool = - ## 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. - return hasKey[A](t, key) +# ------------------------------ helpers --------------------------------- -proc rawInsert[A](t: CountTable[A], data: var seq[tuple[key: A, val: int]], +proc ctRawInsert[A](t: CountTable[A], data: var seq[tuple[key: A, val: int]], key: A, val: int) = var h: Hash = hash(key) and high(data) while data[h].val != 0: h = nextTry(h, high(data)) @@ -980,424 +2308,665 @@ proc enlarge[A](t: var CountTable[A]) = var n: seq[tuple[key: A, val: int]] newSeq(n, len(t.data) * growthFactor) for i in countup(0, high(t.data)): - if t.data[i].val != 0: rawInsert(t, n, t.data[i].key, t.data[i].val) + if t.data[i].val != 0: ctRawInsert(t, n, move t.data[i].key, move t.data[i].val) swap(t.data, n) +proc rawGet[A](t: CountTable[A], key: A): int = + if t.data.len == 0: + return -1 + var h: Hash = hash(key) and high(t.data) # start with real hash value + while t.data[h].val != 0: + if t.data[h].key == key: return h + h = nextTry(h, high(t.data)) + result = -1 - h # < 0 => MISSING; insert idx = -1 - result + +template ctget(t, key, default: untyped): untyped = + var index = rawGet(t, key) + result = if index >= 0: t.data[index].val else: default + +proc inc*[A](t: var CountTable[A], key: A, val = 1) + +# ---------------------------------------------------------------------- + +proc initCountTable*[A](initialSize = defaultInitialSize): CountTable[A] = + ## Creates a new count table that is empty. + ## + ## Starting from Nim v0.20, tables are initialized by default and it is + ## not necessary to call this function explicitly. + ## + ## See also: + ## * `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` + ## 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. + ## + ## See also: + ## * `getOrDefault<#getOrDefault,CountTable[A],A,int>`_ to return + ## a custom value if the key doesn't exist + ## * `[]= 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 + ## is in the table + assert(not t.isSorted, "CountTable must not be used after sorting") + ctget(t, key, 0) + +template cntMakeEmpty(i) = t.data[i].val = 0 +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) = - ## puts 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 + ## * `inc proc<#inc,CountTable[A],A,int>`_ for incrementing a + ## value of a key + assert(not t.isSorted, "CountTable must not be used after sorting") assert val >= 0 - var h = rawGet(t, key) - if h >= 0: - t.data[h].val = val + if val == 0: + delImplNoHCode(cntMakeEmpty, cntCellEmpty, cntCellHash) else: - if mustRehash(len(t.data), t.counter): enlarge(t) - rawInsert(t, t.data, key, val) - inc(t.counter) - #h = -1 - h - #t.data[h].key = key - #t.data[h].val = val + let h = rawGet(t, key) + if h >= 0: + t.data[h].val = val + else: + insertImpl() proc inc*[A](t: var CountTable[A], key: A, val = 1) = - ## increments `t[key]` by `val`. + ## Increments `t[key]` by `val` (default: 1). + runnableExamples: + var a = toCountTable("aab") + a.inc('a') + a.inc('b', 10) + doAssert a == toCountTable("aaabbbbbbbbbbb") + + assert(not t.isSorted, "CountTable must not be used after sorting") var index = rawGet(t, key) if index >= 0: inc(t.data[index].val, val) - if t.data[index].val == 0: dec(t.counter) + if t.data[index].val == 0: + delImplIdx(t, index, cntMakeEmpty, cntCellEmpty, cntCellHash) else: - if mustRehash(len(t.data), t.counter): enlarge(t) - rawInsert(t, t.data, key, val) - inc(t.counter) - -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 - ## 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) - result.counter = 0 - newSeq(result.data, initialSize) + if val != 0: + insertImpl() -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`. - 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. - dollarImpl() - -proc `==`*[A](s, t: CountTable[A]): bool = - ## 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 len*[A](t: CountTable[A]): int = + ## Returns the number of keys in `t`. + result = t.counter proc smallest*[A](t: CountTable[A]): tuple[key: A, val: int] = - ## returns the (key,val)-pair with the smallest `val`. Efficiency: O(n) - assert t.len > 0 + ## Returns the `(key, value)` pair with the smallest `val`. Efficiency: O(n) + ## + ## See also: + ## * `largest proc<#largest,CountTable[A]>`_ + assert t.len > 0, "counttable is empty" var minIdx = -1 - for h in 0..high(t.data): + for h in 0 .. high(t.data): if t.data[h].val > 0 and (minIdx == -1 or t.data[minIdx].val > t.data[h].val): minIdx = h result.key = t.data[minIdx].key 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) - assert t.len > 0 + ## Returns the `(key, value)` pair with the largest `val`. Efficiency: O(n) + ## + ## See also: + ## * `smallest proc<#smallest,CountTable[A]>`_ + assert t.len > 0, "counttable is empty" var maxIdx = 0 - for h in 1..high(t.data): + for h in 1 .. high(t.data): if t.data[maxIdx].val < t.data[h].val: maxIdx = h result.key = t.data[maxIdx].key result.val = t.data[maxIdx].val -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. +proc hasKey*[A](t: CountTable[A], key: A): bool = + ## Returns true if `key` is in the table `t`. + ## + ## See also: + ## * `contains proc<#contains,CountTable[A],A>`_ for use with the `in` + ## operator + ## * `[] proc<#[],CountTable[A],A>`_ for retrieving a value of a key + ## * `getOrDefault proc<#getOrDefault,CountTable[A],A,int>`_ to return + ## a custom value if the key doesn't exist + assert(not t.isSorted, "CountTable must not be used after sorting") + result = rawGet(t, key) >= 0 - # we use shellsort here; fast enough and simple - var h = 1 - while true: - h = 3 * h + 1 - if h >= high(t.data): break - while true: - h = h div 3 - for i in countup(h, high(t.data)): - var j = i - while t.data[j-h].val <= t.data[j].val: - swap(t.data[j], t.data[j-h]) - j = j-h - if j < h: break - if h == 1: break +proc contains*[A](t: CountTable[A], key: A): bool = + ## Alias of `hasKey proc<#hasKey,CountTable[A],A>`_ for use with + ## the `in` operator. + return hasKey[A](t, key) -proc len*[A](t: CountTableRef[A]): int = - ## returns the number of keys in `t`. - result = t.counter +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. + ## + ## See also: + ## * `[] proc<#[],CountTable[A],A>`_ for retrieving a value of a key + ## * `hasKey proc<#hasKey,CountTable[A],A>`_ for checking if a key + ## is in the table + 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. + ## + ## See also: + ## * `pop proc<#pop,CountTable[A],A,int>`_ + ## * `clear proc<#clear,CountTable[A]>`_ to empty the whole table + runnableExamples: + var a = toCountTable("aabbbccccc") + a.del('b') + assert a == toCountTable("aaccccc") + a.del('b') + assert a == toCountTable("aaccccc") + a.del('c') + assert a == toCountTable("aa") + + 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 + ## unchanged. + ## + ## See also: + ## * `del proc<#del,CountTable[A],A>`_ + ## * `clear proc<#clear,CountTable[A]>`_ to empty the whole table + runnableExamples: + var a = toCountTable("aabbbccccc") + var i = 0 + assert a.pop('b', i) + assert i == 3 + i = 99 + assert not a.pop('b', i) + assert i == 99 -iterator pairs*[A](t: CountTableRef[A]): (A, int) = - ## 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) + var index = rawGet(t, key) + result = index >= 0 + if result: + val = move(t.data[index].val) + delImplIdx(t, index, cntMakeEmpty, cntCellEmpty, cntCellHash) -iterator mpairs*[A](t: CountTableRef[A]): (A, var int) = - ## 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) +proc clear*[A](t: var CountTable[A]) = + ## Resets the table so that it is empty. + ## + ## See also: + ## * `del proc<#del,CountTable[A],A>`_ + ## * `pop proc<#pop,CountTable[A],A,int>`_ + clearImpl() + t.isSorted = false -iterator keys*[A](t: CountTableRef[A]): A = - ## 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 +func ctCmp[T](a, b: tuple[key: T, val: int]): int = + result = system.cmp(a.val, b.val) -iterator values*[A](t: CountTableRef[A]): int = - ## 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 +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! + ## + ## 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. + runnableExamples: + import std/[algorithm, sequtils] + var a = toCountTable("abracadabra") + doAssert a == "aaaaabbrrcd".toCountTable + a.sort() + doAssert toSeq(a.values) == @[5, 2, 2, 1, 1] + a.sort(SortOrder.Ascending) + doAssert toSeq(a.values) == @[1, 1, 2, 2, 5] + + t.data.sort(cmp = ctCmp, order = order) + t.isSorted = true -iterator mvalues*[A](t: CountTableRef[A]): var int = - ## 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 merge*[A](s: var CountTable[A], t: CountTable[A]) = + ## Merges the second table into the first one (must be declared as `var`). + runnableExamples: + var a = toCountTable("aaabbc") + let b = toCountTable("bcc") + a.merge(b) + doAssert a == toCountTable("aaabbbccc") + + assert(not s.isSorted, "CountTable must not be used after sorting") + for key, value in t: + s.inc(key, value) -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. - result = t[][key] +when (NimMajor, NimMinor) <= (1, 0): + proc merge*[A](s, t: CountTable[A]): CountTable[A] = + ## Merges the two tables into a new one. + runnableExamples: + let + a = toCountTable("aaabbc") + b = toCountTable("bcc") + doAssert merge(a, b) == toCountTable("aaabbbccc") -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. - result = t[][key] + result = initCountTable[A](nextPowerOfTwo(max(s.len, t.len))) + for table in @[s, t]: + for key, value in table: + result.inc(key, value) -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. - result = t[].getOrDefault(key) +proc `$`*[A](t: CountTable[A]): string = + ## The `$` operator for count tables. Used internally when calling `echo` + ## on a table. + dollarImpl() -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. - result = t[].getOrDefault(key, default) +proc `==`*[A](s, t: CountTable[A]): bool = + ## 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) -proc hasKey*[A](t: CountTableRef[A], key: A): bool = - ## 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. - return hasKey[A](t, key) +iterator pairs*[A](t: CountTable[A]): (A, int) = + ## Iterates over any `(key, value)` pair in the table `t`. + ## + ## See also: + ## * `mpairs iterator<#mpairs.i,CountTable[A]>`_ + ## * `keys iterator<#keys.i,CountTable[A]>`_ + ## * `values iterator<#values.i,CountTable[A]>`_ + ## + ## **Examples:** + ## + ## ```Nim + ## let a = toCountTable("abracadabra") + ## + ## for k, v in pairs(a): + ## echo "key: ", k + ## echo "value: ", v + ## + ## # key: a + ## # value: 5 + ## # key: b + ## # value: 2 + ## # key: c + ## # value: 1 + ## # key: d + ## # value: 1 + ## # key: r + ## # value: 2 + ## ``` + let L = len(t) + for h in 0 .. high(t.data): + if t.data[h].val != 0: + yield (t.data[h].key, t.data[h].val) + 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 + ## declared as `var`). The values can be modified. + ## + ## See also: + ## * `pairs iterator<#pairs.i,CountTable[A]>`_ + ## * `mvalues iterator<#mvalues.i,CountTable[A]>`_ + runnableExamples: + var a = toCountTable("abracadabra") + for k, v in mpairs(a): + v = 2 + doAssert a == toCountTable("aabbccddrr") + + let L = len(t) + for h in 0 .. high(t.data): + if t.data[h].val != 0: + 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]): lent A = + ## Iterates over any key in the table `t`. + ## + ## See also: + ## * `pairs iterator<#pairs.i,CountTable[A]>`_ + ## * `values iterator<#values.i,CountTable[A]>`_ + runnableExamples: + var a = toCountTable("abracadabra") + for k in keys(a): + a[k] = 2 + doAssert a == toCountTable("aabbccddrr") + + let L = len(t) + for h in 0 .. high(t.data): + if t.data[h].val != 0: + yield t.data[h].key + 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`. + ## + ## See also: + ## * `pairs iterator<#pairs.i,CountTable[A]>`_ + ## * `keys iterator<#keys.i,CountTable[A]>`_ + ## * `mvalues iterator<#mvalues.i,CountTable[A]>`_ + runnableExamples: + let a = toCountTable("abracadabra") + for v in values(a): + assert v < 10 + + let L = len(t) + for h in 0 .. high(t.data): + 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") + +iterator mvalues*[A](t: var CountTable[A]): var int = + ## Iterates over any value in the table `t` (must be + ## declared as `var`). The values can be modified. + ## + ## See also: + ## * `mpairs iterator<#mpairs.i,CountTable[A]>`_ + ## * `values iterator<#values.i,CountTable[A]>`_ + runnableExamples: + var a = toCountTable("abracadabra") + for v in mvalues(a): + v = 2 + doAssert a == toCountTable("aabbccddrr") + + let L = len(t) + for h in 0 .. high(t.data): + 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 `[]=`*[A](t: CountTableRef[A], key: A, val: int) = - ## 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`. - t[].inc(key, val) -proc newCountTable*[A](initialSize=64): CountTableRef[A] = - ## creates a new count table that is empty. + + + +# --------------------------------------------------------------------------- +# ---------------------------- CountTableRef -------------------------------- +# --------------------------------------------------------------------------- + +proc inc*[A](t: CountTableRef[A], key: A, val = 1) + +proc newCountTable*[A](initialSize = defaultInitialSize): CountTableRef[A] = + ## Creates a new ref count table that is empty. ## - ## `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. + ## See also: + ## * `newCountTable proc<#newCountTable,openArray[A]>`_ for creating + ## a `CountTableRef` from a collection + ## * `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 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. - dollarImpl() + ## 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) + {.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. + ## + ## See also: + ## * `getOrDefault<#getOrDefault,CountTableRef[A],A,int>`_ to return + ## a custom value if the key doesn't exist + ## * `inc proc<#inc,CountTableRef[A],A,int>`_ to inc even if missing + ## * `[]= proc<#[]%3D,CountTableRef[A],A,int>`_ for inserting a new + ## (key, value) pair in the table + ## * `hasKey proc<#hasKey,CountTableRef[A],A>`_ for checking if a key + ## is in the table + result = t[][key] -proc `==`*[A](s, t: CountTableRef[A]): bool = - ## 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) - elif isNil(t): result = false - else: result = s[] == t[] +proc `[]=`*[A](t: CountTableRef[A], key: A, val: int) = + ## 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 + {.noSideEffect.}: + t[][key] = val -proc smallest*[A](t: CountTableRef[A]): (A, int) = - ## returns the (key,val)-pair with the smallest `val`. Efficiency: O(n) +proc inc*[A](t: CountTableRef[A], key: A, val = 1) = + ## Increments `t[key]` by `val` (default: 1). + runnableExamples: + var a = newCountTable("aab") + a.inc('a') + a.inc('b', 10) + doAssert a == newCountTable("aaabbbbbbbbbbb") + {.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) + ## + ## See also: + ## * `largest proc<#largest,CountTableRef[A]>`_ t[].smallest -proc largest*[A](t: CountTableRef[A]): (A, int) = - ## returns the (key,val)-pair with the largest `val`. Efficiency: O(n) +proc largest*[A](t: CountTableRef[A]): tuple[key: A, val: int] = + ## Returns the `(key, value)` pair with the largest `val`. Efficiency: O(n) + ## + ## See also: + ## * `smallest proc<#smallest,CountTable[A]>`_ 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. - t[].sort +proc hasKey*[A](t: CountTableRef[A], key: A): bool = + ## Returns true if `key` is in the table `t`. + ## + ## See also: + ## * `contains proc<#contains,CountTableRef[A],A>`_ for use with the `in` + ## operator + ## * `[] proc<#[],CountTableRef[A],A>`_ for retrieving a value of a key + ## * `getOrDefault proc<#getOrDefault,CountTableRef[A],A,int>`_ to return + ## a custom value if the key doesn't exist + result = t[].hasKey(key) -proc merge*[A](s: var CountTable[A], t: CountTable[A]) = - ## merges the second table into the first one - for key, value in t: - s.inc(key, value) +proc contains*[A](t: CountTableRef[A], key: A): bool = + ## Alias of `hasKey proc<#hasKey,CountTableRef[A],A>`_ for use with + ## the `in` operator. + return hasKey[A](t, key) -proc merge*[A](s, t: CountTable[A]): CountTable[A] = - ## 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 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. + ## + ## See also: + ## * `[] proc<#[],CountTableRef[A],A>`_ for retrieving a value of a key + ## * `hasKey proc<#hasKey,CountTableRef[A],A>`_ for checking if a key + ## is in the table + result = t[].getOrDefault(key, default) + +proc len*[A](t: CountTableRef[A]): int = + ## 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. + ## + ## See also: + ## * `pop proc<#pop,CountTableRef[A],A,int>`_ + ## * `clear proc<#clear,CountTableRef[A]>`_ to empty the whole table + 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 + ## unchanged. + ## + ## See also: + ## * `del proc<#del,CountTableRef[A],A>`_ + ## * `clear proc<#clear,CountTableRef[A]>`_ to empty the whole table + pop(t[], key, val) + +proc clear*[A](t: CountTableRef[A]) = + ## Resets the table so that it is empty. + ## + ## See also: + ## * `del proc<#del,CountTableRef[A],A>`_ + ## * `pop proc<#pop,CountTableRef[A],A,int>`_ + clear(t[]) + +proc sort*[A](t: CountTableRef[A], order = SortOrder.Descending) = + ## Sorts the count table so that, by default, the entry with the + ## highest counter comes first. + ## + ## **This is destructive! You must not modify `t` afterwards!** + ## + ## 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. + t[].sort(order = order) proc merge*[A](s, t: CountTableRef[A]) = - ## merges the second table into the first one + ## Merges the second table into the first one. + runnableExamples: + let + a = newCountTable("aaabbc") + b = newCountTable("bcc") + a.merge(b) + doAssert a == newCountTable("aaabbbccc") + s[].merge(t[]) -when isMainModule: - type - Person = object - firstName, lastName: string +proc `$`*[A](t: CountTableRef[A]): string = + ## The `$` operator for count tables. Used internally when calling `echo` + ## on a table. + dollarImpl() - 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 +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 + ## count. Insert order does not matter. + if isNil(s): result = isNil(t) + elif isNil(t): result = false + else: result = s[] == t[] - 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 - var - s2 = initOrderedTable[Person, int]() - s3 = initCountTable[Person]() - s2[p1] = 30_000 - s2[p2] = 45_000 - s3[p1] = 30_000 - s3[p2] = 45_000 - - block: # Ordered table should preserve order after deletion - var - s4 = initOrderedTable[int, int]() - s4[1] = 1 - s4[2] = 2 - s4[3] = 3 - - var prev = 0 - for i in s4.values: - doAssert(prev < i) - prev = i - - s4.del(2) - doAssert(2 notin s4) - doAssert(s4.len == 2) - prev = 0 - for i in s4.values: - doAssert(prev < i) - prev = i - - block: # Deletion from OrderedTable should account for collision groups. See issue #5057. - # The bug is reproducible only with exact keys - const key1 = "boy_jackpot.inGamma" - const key2 = "boy_jackpot.outBlack" - - var t = { - key1: 0, - key2: 0 - }.toOrderedTable() - - t.del(key1) - assert(t.len == 1) - assert(key2 in t) - var - t1 = initCountTable[string]() - t2 = initCountTable[string]() - t1.inc("foo") - t1.inc("bar", 2) - t1.inc("baz", 3) - t2.inc("foo", 4) - t2.inc("bar") - t2.inc("baz", 11) - merge(t1, t2) - assert(t1["foo"] == 5) - assert(t1["bar"] == 3) - assert(t1["baz"] == 14) +iterator pairs*[A](t: CountTableRef[A]): (A, int) = + ## Iterates over any `(key, value)` pair in the table `t`. + ## + ## See also: + ## * `mpairs iterator<#mpairs.i,CountTableRef[A]>`_ + ## * `keys iterator<#keys.i,CountTableRef[A]>`_ + ## * `values iterator<#values.i,CountTableRef[A]>`_ + ## + ## **Examples:** + ## + ## ```Nim + ## let a = newCountTable("abracadabra") + ## + ## for k, v in pairs(a): + ## echo "key: ", k + ## echo "value: ", v + ## + ## # key: a + ## # value: 5 + ## # key: b + ## # value: 2 + ## # key: c + ## # value: 1 + ## # key: d + ## # value: 1 + ## # key: r + ## # value: 2 + ## ``` + let L = len(t) + for h in 0 .. high(t.data): + if t.data[h].val != 0: + yield (t.data[h].key, t.data[h].val) + assert(len(t) == L, "the length of the table changed while iterating over it") - let - t1r = newCountTable[string]() - t2r = newCountTable[string]() - t1r.inc("foo") - t1r.inc("bar", 2) - t1r.inc("baz", 3) - t2r.inc("foo", 4) - t2r.inc("bar") - t2r.inc("baz", 11) - merge(t1r, t2r) - assert(t1r["foo"] == 5) - assert(t1r["bar"] == 3) - assert(t1r["baz"] == 14) +iterator mpairs*[A](t: CountTableRef[A]): (A, var int) = + ## Iterates over any `(key, value)` pair in the table `t`. The values can + ## be modified. + ## + ## See also: + ## * `pairs iterator<#pairs.i,CountTableRef[A]>`_ + ## * `mvalues iterator<#mvalues.i,CountTableRef[A]>`_ + runnableExamples: + let a = newCountTable("abracadabra") + for k, v in mpairs(a): + v = 2 + doAssert a == newCountTable("aabbccddrr") + + let L = len(t) + for h in 0 .. high(t.data): + if t.data[h].val != 0: + yield (t.data[h].key, t.data[h].val) + assert(len(t) == L, "table modified while iterating over it") - var - t1l = initCountTable[string]() - t2l = initCountTable[string]() - t1l.inc("foo") - t1l.inc("bar", 2) - t1l.inc("baz", 3) - t2l.inc("foo", 4) - t2l.inc("bar") - t2l.inc("baz", 11) - let - t1merging = t1l - t2merging = t2l - let merged = merge(t1merging, t2merging) - assert(merged["foo"] == 5) - assert(merged["bar"] == 3) - assert(merged["baz"] == 14) - - block: - const testKey = "TESTKEY" - let t: CountTableRef[string] = newCountTable[string]() - - # Before, does not compile with error message: - #test_counttable.nim(7, 43) template/generic instantiation from here - #lib/pure/collections/tables.nim(117, 21) template/generic instantiation from here - #lib/pure/collections/tableimpl.nim(32, 27) Error: undeclared field: 'hcode - doAssert 0 == t.getOrDefault(testKey) - t.inc(testKey, 3) - doAssert 3 == t.getOrDefault(testKey) - - block: - # Clear tests - var clearTable = newTable[int, string]() - clearTable[42] = "asd" - clearTable[123123] = "piuyqwb " - doAssert clearTable[42] == "asd" - clearTable.clear() - doAssert(not clearTable.hasKey(123123)) - doAssert clearTable.getOrDefault(42) == nil - - block: #5482 - var a = [("wrong?","foo"), ("wrong?", "foo2")].newOrderedTable() - var b = newOrderedTable[string, string](initialSize=2) - b.add("wrong?", "foo") - b.add("wrong?", "foo2") - assert a == b - - block: #5482 - var a = {"wrong?": "foo", "wrong?": "foo2"}.newOrderedTable() - var b = newOrderedTable[string, string](initialSize=2) - b.add("wrong?", "foo") - b.add("wrong?", "foo2") - assert a == b - - block: #5487 - var a = {"wrong?": "foo", "wrong?": "foo2"}.newOrderedTable() - var b = newOrderedTable[string, string]() # notice, default size! - b.add("wrong?", "foo") - b.add("wrong?", "foo2") - assert a == b - - block: #5487 - var a = [("wrong?","foo"), ("wrong?", "foo2")].newOrderedTable() - var b = newOrderedTable[string, string]() # notice, default size! - b.add("wrong?", "foo") - b.add("wrong?", "foo2") - assert a == b - - block: - var a = {"wrong?": "foo", "wrong?": "foo2"}.newOrderedTable() - var b = [("wrong?","foo"), ("wrong?", "foo2")].newOrderedTable() - var c = newOrderedTable[string, string]() # notice, default size! - c.add("wrong?", "foo") - c.add("wrong?", "foo2") - assert a == b - assert a == c - - block: #6250 - let - a = {3: 1}.toOrderedTable - b = {3: 2}.toOrderedTable - assert((a == b) == false) - assert((b == a) == false) +iterator keys*[A](t: CountTableRef[A]): A = + ## Iterates over any key in the table `t`. + ## + ## See also: + ## * `pairs iterator<#pairs.i,CountTable[A]>`_ + ## * `values iterator<#values.i,CountTable[A]>`_ + runnableExamples: + let a = newCountTable("abracadabra") + for k in keys(a): + a[k] = 2 + doAssert a == newCountTable("aabbccddrr") + + let L = len(t) + for h in 0 .. high(t.data): + if t.data[h].val != 0: + yield t.data[h].key + assert(len(t) == L, "the length of the table changed while iterating over it") - block: #6250 - let - a = {3: 2}.toOrderedTable - b = {3: 2}.toOrderedTable - assert((a == b) == true) - assert((b == a) == true) - - block: # CountTable.smallest - let t = toCountTable([0, 0, 5, 5, 5]) - doAssert t.smallest == (0, 2) - - block: - var tp: Table[string, string] = initTable[string, string]() - doAssert "test1" == tp.getOrDefault("test1", "test1") - tp["test2"] = "test2" - doAssert "test2" == tp.getOrDefault("test2", "test1") - var tr: TableRef[string, string] = newTable[string, string]() - doAssert "test1" == tr.getOrDefault("test1", "test1") - tr["test2"] = "test2" - doAssert "test2" == tr.getOrDefault("test2", "test1") - var op: OrderedTable[string, string] = initOrderedTable[string, string]() - doAssert "test1" == op.getOrDefault("test1", "test1") - op["test2"] = "test2" - doAssert "test2" == op.getOrDefault("test2", "test1") - var orf: OrderedTableRef[string, string] = newOrderedTable[string, string]() - doAssert "test1" == orf.getOrDefault("test1", "test1") - orf["test2"] = "test2" - doAssert "test2" == orf.getOrDefault("test2", "test1") +iterator values*[A](t: CountTableRef[A]): int = + ## Iterates over any value in the table `t`. + ## + ## See also: + ## * `pairs iterator<#pairs.i,CountTableRef[A]>`_ + ## * `keys iterator<#keys.i,CountTableRef[A]>`_ + ## * `mvalues iterator<#mvalues.i,CountTableRef[A]>`_ + runnableExamples: + let a = newCountTable("abracadabra") + for v in values(a): + assert v < 10 + + let L = len(t) + for h in 0 .. high(t.data): + 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") + +iterator mvalues*[A](t: CountTableRef[A]): var int = + ## Iterates over any value in the table `t`. The values can be modified. + ## + ## See also: + ## * `mpairs iterator<#mpairs.i,CountTableRef[A]>`_ + ## * `values iterator<#values.i,CountTableRef[A]>`_ + runnableExamples: + var a = newCountTable("abracadabra") + for v in mvalues(a): + v = 2 + doAssert a == newCountTable("aabbccddrr") + + let L = len(t) + for h in 0 .. high(t.data): + 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 |