diff options
Diffstat (limited to 'lib/pure/collections/tables.nim')
| -rw-r--r-- | lib/pure/collections/tables.nim | 2699 |
1 files changed, 2047 insertions, 652 deletions
diff --git a/lib/pure/collections/tables.nim b/lib/pure/collections/tables.nim index f46a368b1..84ec422d4 100644 --- a/lib/pure/collections/tables.nim +++ b/lib/pure/collections/tables.nim @@ -9,16 +9,21 @@ ## 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. +## a mapping from keys to values. +## +## There are several different types of hash tables available: +## * `Table<#Table>`_ is the usual hash table, +## * `OrderedTable<#OrderedTable>`_ is like ``Table`` but remembers insertion order, +## * `CountTable<#CountTable>`_ is a mapping from a key to its number of occurrences ## ## For consistency with every other data type in Nim these have **value** ## semantics, this means that ``=`` performs a copy of the hash table. -## 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`` +## For `ref semantics<manual.html#types-ref-and-pointer-types>`_ +## use their ``Ref`` variants: `TableRef<#TableRef>`_, +## `OrderedTableRef<#OrderedTableRef>`_, and `CountTableRef<#CountTableRef>`_. +## +## To give an example, when ``a`` is a ``Table``, then ``var b = a`` gives ``b`` ## as a new independent table. ``b`` is initialised with the contents of ``a``. ## Changing ``b`` does not affect ``a`` and vice versa: ## @@ -35,8 +40,8 @@ ## echo a, b # output: {1: one, 2: two}{1: one, 2: two, 3: three} ## echo a == b # output: false ## -## On the other hand, when ``a`` is a TableRef instead, then changes to ``b`` -## also affect ``a``. Both ``a`` and ``b`` reference the same data structure: +## On the other hand, when ``a`` is a ``TableRef`` instead, then changes to ``b`` +## also affect ``a``. Both ``a`` and ``b`` **ref** the same data structure: ## ## .. code-block:: ## import tables @@ -51,27 +56,111 @@ ## echo a, b # output: {1: one, 2: two, 3: three}{1: one, 2: two, 3: three} ## echo a == b # output: true ## +## ---- +## +## Basic usage +## =========== +## +## Table +## ----- +## +## .. code-block:: +## import tables +## from sequtils import zip +## +## let +## names = ["John", "Paul", "George", "Ringo"] +## years = [1940, 1942, 1943, 1940] +## +## var beatles = initTable[string, int]() +## +## for pairs in zip(names, years): +## let (name, birthYear) = pairs +## beatles[name] = birthYear +## +## echo beatles +## # {"George": 1943, "Ringo": 1940, "Paul": 1942, "John": 1940} +## +## +## var beatlesByYear = initTable[int, seq[string]]() +## +## for pairs in zip(years, names): +## let (birthYear, name) = pairs +## if not beatlesByYear.hasKey(birthYear): +## # if a key doesn't exists, we create one with an empty sequence +## # before we can add elements to it +## beatlesByYear[birthYear] = @[] +## beatlesByYear[birthYear].add(name) +## +## echo beatlesByYear +## # {1940: @["John", "Ringo"], 1942: @["Paul"], 1943: @["George"]} +## +## ## -## Here is an example of ``CountTable`` usage: +## OrderedTable +## ------------ +## +## `OrderedTable<#OrderedTable>`_ is used when it is important to preserve +## the insertion order of keys. +## +## .. code-block:: +## import tables +## +## let +## a = [('z', 1), ('y', 2), ('x', 3)] +## t = a.toTable # regular table +## ot = a.toOrderedTable # ordered tables +## +## echo t # {'x': 3, 'y': 2, 'z': 1} +## echo ot # {'z': 1, 'y': 2, 'x': 3} +## +## +## +## CountTable +## ---------- +## +## `CountTable<#CountTable>`_ is useful for counting number of items of some +## container (e.g. string, sequence or array), as it is a mapping where the +## items are the keys, and their number of occurrences are the values. +## For that purpose `toCountTable proc<#toCountTable,openArray[A]>`_ +## comes handy: +## +## .. code-block:: +## import tables ## -## .. code-block:: nim ## let myString = "abracadabra" -## var myTable = initCountTable[char]() +## let letterFrequencies = toCountTable(myString) +## echo letterFrequencies +## # 'a': 5, 'b': 2, 'c': 1, 'd': 1, 'r': 2} +## +## The same could have been achieved by manually iterating over a container +## and increasing each key's value with `inc proc<#inc,CountTable[A],A,int>`_: +## +## .. code-block:: +## import tables ## +## let myString = "abracadabra" +## var letterFrequencies = initCountTable[char]() ## for c in myString: -## myTable.inc(c) +## letterFrequencies.inc(c) +## echo letterFrequencies +## # output: {'a': 5, 'b': 2, 'c': 1, 'd': 1, 'r': 2} +## +## ---- +## ## -## echo myTable # output: {'a': 5, 'b': 2, 'c': 1, 'd': 1, 'r': 2} ## +## Hashing +## ------- ## ## 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: openArray[A]): Hash ## hashes.hash(x: int): Hash ## hashes.hash(x: float): Hash ## … @@ -89,6 +178,8 @@ ## example implementing only ``hash`` suffices: ## ## .. code-block:: +## import tables, hashes +## ## type ## Person = object ## firstName, lastName: string @@ -111,45 +202,50 @@ ## p2.firstName = "소진" ## p2.lastName = "박" ## salaries[p2] = 45_000 +## +## ---- +## +## See also +## ======== +## +## * `json module<json.html>`_ for table-like structure which allows +## heterogeneous members +## * `sharedtables module<sharedtables.html>`_ for shared hash table support +## * `strtabs module<strtabs.html>`_ for efficient hash tables +## mapping from strings to strings +## * `hashes module<hashes.html>`_ for helper functions for hashing -import - hashes, math + +import hashes, math include "system/inclrtl" 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,int>`_. 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,int>`_. + + +# ------------------------------ helpers --------------------------------- 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 ref 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 rightSize*(count: Natural): int {.inline.} template get(t, key): untyped = ## retrieves the value at ``t[key]``. The value can be modified. @@ -176,36 +272,340 @@ template getOrDefaultImpl(t, key, default: untyped): untyped = 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 - ## the key exists. - get(t, key) +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 `[]`*[A, B](t: var Table[A, B], key: A): var B {.deprecatedGet.} = - ## retrieves the value at ``t[key]``. The value can be modified. +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) + +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 + + + +# ------------------------------------------------------------------- +# ------------------------------ Table ------------------------------ +# ------------------------------------------------------------------- + +proc initTable*[A, B](initialSize=64): Table[A, B] = + ## Creates a new hash table that is empty. + ## + ## ``initialSize`` must be a power of two (default: 64). + ## If you need to accept runtime values for this you could use the + ## `nextPowerOfTwo proc<math.html#nextPowerOfTwo,int>`_ from the + ## `math module<math.html>`_ or the `rightSize proc<#rightSize,Natural>`_ + ## from this module. + ## + ## See also: + ## * `toTable proc<#toTable,openArray[]>`_ + ## * `newTable proc<#newTable,int>`_ for creating a `TableRef` + runnableExamples: + let + a = initTable[int, string]() + b = initTable[char, seq[int]]() + assert isPowerOfTwo(initialSize) + result.counter = 0 + newSeq(result.data, initialSize) + +proc toTable*[A, B](pairs: openArray[(A, B)]): Table[A, B] = + ## Creates a new hash table that contains the given ``pairs``. + ## + ## ``pairs`` is a container consisting of ``(key, value)`` tuples. + ## + ## See also: + ## * `initTable proc<#initTable,int>`_ + ## * `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](rightSize(pairs.len)) + for key, val in items(pairs): result[key] = val + +proc `[]`*[A, B](t: Table[A, B], key: A): B = + ## Retrieves the value at ``t[key]``. + ## ## 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,B>`_ 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 mget*[A, B](t: var Table[A, B], key: A): var B {.deprecated.} = - ## retrieves the value at ``t[key]``. The value can be modified. +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. - ## Use ``[]`` instead. + ## + ## See also: + ## * `getOrDefault proc<#getOrDefault,Table[A,B],A>`_ to return + ## a default value (e.g. zero for int) if the key doesn't exist + ## * `getOrDefault proc<#getOrDefault,Table[A,B],A,B>`_ to return + ## a custom value if the key doesn't exist + ## * `[]= proc<#[]=,Table[A,B],A,B>`_ for inserting a new + ## (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 `[]=`*[A, B](t: var Table[A, B], key: A, val: 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 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 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``. + ## 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 getOrDefaultImpl(t, key, default) +proc mgetOrPut*[A, B](t: var Table[A, B], key: A, val: B): var B = + ## Retrieves value at ``t[key]`` or puts ``val`` if not present, either way + ## returning a value which can be modified. + ## + ## 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 + 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: B) = + ## Puts a new ``(key, value)`` pair into ``t`` even if ``t[key]`` already exists. + ## + ## **This can introduce duplicate keys into the table!** + ## + ## Use `[]= proc<#[]=,Table[A,B],A,B>`_ for inserting a new + ## (key, value) pair in the table without introducing duplicates. + addImpl(enlarge) + +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. + ## + ## See also: + ## * `take proc<#take,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() + +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. + ## + ## 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.take('b', i) == true + doAssert a == {'a': 5, 'c': 13}.toTable + doAssert i == 9 + i = 0 + doAssert a.take('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: + shallowCopy(val, t.data[index].val) + delImplIdx(t, index) + +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>`_ + ## * `take proc<#take,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 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 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]``. + ## Retrieves the value at ``t[key]``. + ## ## ``value`` can be modified in the scope of the ``withValue`` call. ## ## .. code-block:: nim @@ -225,7 +625,8 @@ 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]``. + ## Retrieves the value at ``t[key]``. + ## ## ``value`` can be modified in the scope of the ``withValue`` call. ## ## .. code-block:: nim @@ -248,370 +649,535 @@ 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``. + ## 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:** + ## + ## .. code-block:: + ## 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] for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield (t.data[h].key, t.data[h].val) iterator mpairs*[A, B](t: var Table[A, B]): (A, var B) = - ## iterates over any ``(key, value)`` pair in the table ``t``. The values - ## can be modified. + ## 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 for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield (t.data[h].key, t.data[h].val) iterator keys*[A, B](t: Table[A, B]): A = - ## iterates over any key in the table ``t``. + ## Iterates over any key in the table ``t``. + ## + ## 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 for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield t.data[h].key iterator values*[A, B](t: Table[A, B]): B = - ## iterates over any value in the table ``t``. + ## Iterates over any value in the table ``t``. + ## + ## 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 for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield t.data[h].val iterator mvalues*[A, B](t: var Table[A, B]): var B = - ## iterates over any value in the table ``t``. The values can be modified. + ## Iterates over any value in the table ``t`` (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 for h in 0..high(t.data): if isFilled(t.data[h].hcode): yield t.data[h].val -proc del*[A, B](t: var Table[A, B], key: A) = - ## deletes ``key`` from hash table ``t``. Does nothing if the key does not exist. - 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) - -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) - -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) - -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) - -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. +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``. ## - ## ``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) + ## Used if you have a table with duplicate keys (as a result of using + ## `add proc<#add,Table[A,B],A,B>`_). + ## + ## **Examples:** + ## + ## .. code-block:: + ## var a = {'a': 3, 'b': 5}.toTable + ## for i in 1..3: + ## a.add('z', 10*i) + ## echo a # {'a': 3, 'b': 5, 'z': 10, 'z': 20, 'z': 30} + ## + ## for v in a.allValues('z'): + ## echo v + ## # 10 + ## # 20 + ## # 30 + 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 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 -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 `$`*[A, B](t: Table[A, B]): string = - ## the ``$`` operator for hash tables. - dollarImpl() +# ------------------------------------------------------------------- +# ---------------------------- TableRef ----------------------------- +# ------------------------------------------------------------------- -proc hasKey*[A, B](t: TableRef[A, B], key: A): bool = - ## returns true iff ``key`` is in the table ``t``. - result = t[].hasKey(key) -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 newTable*[A, B](initialSize=64): TableRef[A, B] = + ## Creates a new ref hash table that is empty. + ## + ## ``initialSize`` must be a power of two (default: 64). + ## If you need to accept runtime values for this you could use the + ## `nextPowerOfTwo proc<math.html#nextPowerOfTwo,int>`_ from the + ## `math module<math.html>`_ or the `rightSize proc<#rightSize,Natural>`_ + ## from this module. + ## + ## See also: + ## * `newTable proc<#newTable,openArray[]>`_ for creating a `TableRef` + ## from a collection of `(key, value)` pairs + ## * `initTable proc<#initTable,int>`_ for creating a `Table` + runnableExamples: + let + a = newTable[int, string]() + b = newTable[char, seq[int]]() + new(result) + result[] = initTable[A, B](initialSize) -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) +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,int>`_ + ## * `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 + new(result) + result[] = toTable[A, B](pairs) -proc indexBy*[A, B, C](collection: A, index: proc(x: B): C): Table[C, B] = +proc newTableFrom*[A, B, C](collection: A, index: proc(x: B): C): TableRef[C, B] = ## Index the collection with the proc provided. # TODO: As soon as supported, change collection: A to collection: A[B] - result = initTable[C, B]() + result = newTable[C, B]() for item in collection: result[index(item)] = item -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) - -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) - -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 +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,B>`_ 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'] + result = t[][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 `[]=`*[A, B](t: TableRef[A, B], key: A, val: 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 + t[][key] = val -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 +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 + result = t[].hasKey(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 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 + return hasKey[A, B](t, key) -proc mget*[A, B](t: TableRef[A, B], key: A): var B {.deprecated.} = - ## retrieves the value at ``t[key]``. The value can be modified. - ## If ``key`` is not in ``t``, the ``KeyError`` exception is raised. - ## Use ``[]`` instead. - t[][key] +proc hasKeyOrPut*[A, B](t: var TableRef[A, B], key: A, val: B): bool = + ## Returns true if ``key`` is in the table, otherwise inserts ``value``. + ## + ## 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 + 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``. + ## 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. + ## + ## 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 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 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) - -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 + result = t.counter 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! + ## 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,B>`_ 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``. Does nothing if the key does not exist. + ## Deletes ``key`` from hash table ``t``. Does nothing if the key does not exist. + ## + ## See also: + ## * `take proc<#take,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. + ## 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,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.take('b', i) == true + doAssert a == {'a': 5, 'c': 13}.newTable + doAssert i == 9 + i = 0 + doAssert a.take('z', i) == false + doAssert a == {'a': 5, 'c': 13}.newTable + doAssert i == 0 result = t[].take(key, val) -proc newTable*[A, B](initialSize=64): TableRef[A, B] = - new(result) - result[] = initTable[A, B](initialSize) - -proc newTable*[A, B](pairs: openArray[(A, B)]): TableRef[A, B] = - ## creates a new hash table that contains the given ``pairs``. - new(result) - result[] = toTable[A, B](pairs) +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>`_ + ## * `take proc<#take,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 + 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] - -proc len*[A, B](t: OrderedTable[A, B]): int {.inline.} = - ## returns the number of keys in ``t``. - result = t.counter +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:** + ## + ## .. code-block:: + ## 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] + for h in 0..high(t.data): + if isFilled(t.data[h].hcode): yield (t.data[h].key, t.data[h].val) -proc clear*[A, B](t: var OrderedTable[A, B]) = - ## resets the table so that it is empty. - clearImpl() - t.first = -1 - t.last = -1 +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 + for h in 0..high(t.data): + if isFilled(t.data[h].hcode): yield (t.data[h].key, t.data[h].val) -proc clear*[A, B](t: var OrderedTableRef[A, B]) = - ## resets the table so that is is empty. - clear(t[]) +iterator keys*[A, B](t: TableRef[A, B]): 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 + for h in 0..high(t.data): + if isFilled(t.data[h].hcode): yield t.data[h].key -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 values*[A, B](t: TableRef[A, B]): 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 + for h in 0..high(t.data): + if isFilled(t.data[h].hcode): yield t.data[h].val -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 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 + for h in 0..high(t.data): + if isFilled(t.data[h].hcode): yield 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 -proc rawGetKnownHC[A, B](t: OrderedTable[A, B], key: A, hc: Hash): int = - rawGetKnownHCImpl() -proc rawGetDeep[A, B](t: OrderedTable[A, B], key: A, hc: var Hash): int {.inline.} = - rawGetDeepImpl() -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) +# --------------------------------------------------------------------------- +# ------------------------------ OrderedTable ------------------------------- +# --------------------------------------------------------------------------- -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) +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,int>`_. + 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,int>`_. -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) +# ------------------------------ helpers --------------------------------- -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 rawGetKnownHC[A, B](t: OrderedTable[A, B], key: A, hc: Hash): int = + rawGetKnownHCImpl() -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 rawGetDeep[A, B](t: OrderedTable[A, B], key: A, hc: var Hash): int {.inline.} = + rawGetDeepImpl() -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 rawGet[A, B](t: OrderedTable[A, B], key: A, hc: var Hash): int = + rawGetImpl() proc rawInsert[A, B](t: var OrderedTable[A, B], data: var OrderedKeyValuePairSeq[A, B], @@ -639,30 +1205,32 @@ proc enlarge[A, B](t: var OrderedTable[A, B]) = rawInsert(t, t.data, n[h].key, 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``. - 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) +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 -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 - ## returning a value which can be modified. - 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 initOrderedTable*[A, B](initialSize=64): OrderedTable[A, B] = - ## creates a new ordered hash table that is empty. + ## Creates a new ordered hash table that is empty. + ## + ## ``initialSize`` must be a power of two (default: 64). + ## If you need to accept runtime values for this you could use the + ## `nextPowerOfTwo proc<math.html#nextPowerOfTwo,int>`_ from the + ## `math module<math.html>`_ or the `rightSize proc<#rightSize,Natural>`_ + ## from this module. ## - ## ``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. + ## See also: + ## * `toOrderedTable proc<#toOrderedTable,openArray[]>`_ + ## * `newOrderedTable proc<#newOrderedTable,int>`_ for creating an + ## `OrderedTableRef` + runnableExamples: + let + a = initOrderedTable[int, string]() + b = initOrderedTable[char, seq[int]]() assert isPowerOfTwo(initialSize) result.counter = 0 result.first = -1 @@ -670,36 +1238,250 @@ proc initOrderedTable*[A, B](initialSize=64): OrderedTable[A, B] = newSeq(result.data, initialSize) proc toOrderedTable*[A, B](pairs: openArray[(A, B)]): OrderedTable[A, B] = - ## creates a new ordered hash table that contains the given ``pairs``. + ## Creates a new ordered hash table that contains the given ``pairs``. + ## + ## ``pairs`` is a container consisting of ``(key, value)`` tuples. + ## + ## See also: + ## * `initOrderedTable proc<#initOrderedTable,int>`_ + ## * `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](rightSize(pairs.len)) for key, val in items(pairs): result[key] = val -proc `$`*[A, B](t: OrderedTable[A, B]): string = - ## The ``$`` operator for ordered hash tables. - dollarImpl() +proc `[]`*[A, B](t: OrderedTable[A, B], key: A): 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,B>`_ 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](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 `[]`*[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,B>`_ 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 `[]=`*[A, B](t: var OrderedTable[A, B], key: A, val: 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 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 + 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 + 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 + getOrDefaultImpl(t, key, default) + +proc mgetOrPut*[A, B](t: var OrderedTable[A, B], key: A, val: B): var B = + ## Retrieves value at ``t[key]`` or puts ``val`` if not present, either way + ## 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 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 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!** + ## + ## Use `[]= proc<#[]=,OrderedTable[A,B],A,B>`_ for inserting a new + ## (key, value) pair in the table without introducing duplicates. + addImpl(enlarge) + +proc del*[A, B](t: var OrderedTable[A, B], key: A) = + ## Deletes ``key`` from hash table ``t``. Does nothing if the key does not exist. + ## + ## O(n) complexity. + ## + ## See also: + ## * `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 + 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 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>`_ + 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) = - ## sorts ``t`` according to ``cmp``. This modifies the internal list + ## 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: + 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 + var list = t.first var p, q, e, tail, oldhead: int @@ -740,244 +1522,519 @@ 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 + 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:** + ## + ## .. code-block:: + ## 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] forAllOrderedPairs: yield (t.data[h].key, t.data[h].val) -iterator mpairs*[A, B](t: OrderedTableRef[A, B]): (A, var B) = - ## iterates over any ``(key, value)`` pair in the table ``t`` in insertion - ## 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 forAllOrderedPairs: yield (t.data[h].key, t.data[h].val) -iterator keys*[A, B](t: OrderedTableRef[A, B]): A = - ## iterates over any key in the table ``t`` in insertion order. +iterator keys*[A, B](t: OrderedTable[A, B]): 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 forAllOrderedPairs: yield t.data[h].key -iterator values*[A, B](t: OrderedTableRef[A, B]): B = - ## iterates over any value in the table ``t`` in insertion order. +iterator values*[A, B](t: OrderedTable[A, B]): 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 forAllOrderedPairs: yield t.data[h].val -iterator mvalues*[A, B](t: OrderedTableRef[A, B]): var B = - ## iterates over any value in the table ``t`` in insertion order. The values +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 forAllOrderedPairs: yield t.data[h].val + + + + +# --------------------------------------------------------------------------- +# --------------------------- OrderedTableRef ------------------------------- +# --------------------------------------------------------------------------- + +proc newOrderedTable*[A, B](initialSize=64): OrderedTableRef[A, B] = + ## Creates a new ordered ref hash table that is empty. + ## + ## ``initialSize`` must be a power of two (default: 64). + ## If you need to accept runtime values for this you could use the + ## `nextPowerOfTwo proc<math.html#nextPowerOfTwo,int>`_ from the + ## `math module<math.html>`_ or the `rightSize proc<#rightSize,Natural>`_ + ## from this module. + ## + ## See also: + ## * `newOrderedTable proc<#newOrderedTable,openArray[]>`_ for creating + ## an `OrderedTableRef` from a collection of `(key, value)` pairs + ## * `initOrderedTable proc<#initOrderedTable,int>`_ for creating an + ## `OrderedTable` + runnableExamples: + let + a = newOrderedTable[int, string]() + b = newOrderedTable[char, seq[int]]() + new(result) + 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,int>`_ + ## * `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](rightSize(pairs.len)) + for key, val in items(pairs): result.add(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,B>`_ 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: 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: var 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 hasKey*[A, B](t: OrderedTableRef[A, B], key: A): bool = - ## returns true iff ``key`` is in the table ``t``. - result = t[].hasKey(key) - -proc contains*[A, B](t: OrderedTableRef[A, B], key: A): bool = - ## Alias of ``hasKey`` for use with the ``in`` operator. - return hasKey[A, B](t, key) - -proc `[]=`*[A, B](t: OrderedTableRef[A, B], key: A, val: B) = - ## puts a ``(key, value)`` pair into ``t``. - t[][key] = val +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 + 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! + ## 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,B>`_ 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: var 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 + t[].del(key) -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) +proc clear*[A, B](t: var OrderedTableRef[A, B]) = + ## Resets the table so that it is empty. + ## + ## See also: + ## * `del proc<#del,OrderedTable[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) = + ## 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: + 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 + t[].sort(cmp) 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. Does nothing - ## if the key does not exist. - 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. Does nothing - ## if the key does not exist. - t[].del(key) - -# ------------------------------ count tables ------------------------------- - -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] - -proc len*[A](t: CountTable[A]): int = - ## returns the number of keys in ``t``. - result = t.counter -proc clear*[A](t: CountTableRef[A]) = - ## resets the table so that it is empty. - clearImpl() -proc clear*[A](t: var CountTable[A]) = - ## resets the table so that it is empty. - clearImpl() +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:** + ## + ## .. code-block:: + ## 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] + forAllOrderedPairs: + yield (t.data[h].key, t.data[h].val) -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, 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 + forAllOrderedPairs: + 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, B](t: OrderedTableRef[A, B]): 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 + forAllOrderedPairs: + yield t.data[h].key -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, B](t: OrderedTableRef[A, B]): 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 + forAllOrderedPairs: + yield t.data[h].val -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, 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 + forAllOrderedPairs: + 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,int>`_. + data: seq[tuple[key: A, val: int]] + counter: int + CountTableRef*[A] = ref CountTable[A] ## Ref version of + ## `CountTable<#CountTable>`_. + ## + ## For creating a new empty CountTableRef, use `newCountTable proc + ## <#newCountTable,int>`_. -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]], key: A, val: int) = @@ -993,22 +2050,87 @@ proc enlarge[A](t: var CountTable[A]) = if t.data[i].val != 0: rawInsert(t, n, t.data[i].key, t.data[i].val) swap(t.data, n) +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, 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=64): CountTable[A] = + ## Creates a new count table that is empty. + ## + ## ``initialSize`` must be a power of two (default: 64). + ## If you need to accept runtime values for this you could use the + ## `nextPowerOfTwo proc<math.html#nextPowerOfTwo,int>`_ from the + ## `math module<math.html>`_ or the `rightSize proc<#rightSize,Natural>`_ + ## from this module. + ## + ## See also: + ## * `toCountTable proc<#toCountTable,openArray[A]>`_ + ## * `newCountTable proc<#newCountTable,int>`_ for creating a + ## `CountTableRef` + assert isPowerOfTwo(initialSize) + result.counter = 0 + newSeq(result.data, 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](rightSize(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 + ## * `mget proc<#mget,CountTable[A],A>`_ + ## * `[]= proc<#[]%3D,CountTable[A],A,int>`_ for inserting a new + ## (key, value) pair in the table + ## * `hasKey proc<#hasKey,CountTable[A],A>`_ for checking if a key + ## is in the table + ctget(t, key, 0) + +proc mget*[A](t: var CountTable[A], key: A): var int = + ## 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 `[]=`*[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 val >= 0 - var h = rawGet(t, key) + let h = rawGet(t, key) if h >= 0: t.data[h].val = val 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 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") var index = rawGet(t, key) if index >= 0: inc(t.data[index].val, val) @@ -1018,33 +2140,11 @@ proc inc*[A](t: var CountTable[A], key: A, val = 1) = 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) - -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 smallest*[A](t: CountTable[A]): tuple[key: A, val: int] = - ## returns the ``(key, value)`` pair with the smallest ``val``. Efficiency: O(n) + ## Returns the ``(key, value)`` pair with the smallest ``val``. Efficiency: O(n) + ## + ## See also: + ## * `largest proc<#largest,CountTable[A]>`_ assert t.len > 0 var minIdx = -1 for h in 0..high(t.data): @@ -1054,7 +2154,10 @@ proc smallest*[A](t: CountTable[A]): tuple[key: A, val: int] = result.val = t.data[minIdx].val proc largest*[A](t: CountTable[A]): tuple[key: A, val: int] = - ## returns the ``(key, value)`` pair with the largest ``val``. Efficiency: O(n) + ## Returns the ``(key, value)`` pair with the largest ``val``. Efficiency: O(n) + ## + ## See also: + ## * `smallest proc<#smallest,CountTable[A]>`_ assert t.len > 0 var maxIdx = 0 for h in 1..high(t.data): @@ -1062,11 +2165,49 @@ proc largest*[A](t: CountTable[A]): tuple[key: A, val: int] = result.key = t.data[maxIdx].key result.val = t.data[maxIdx].val +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 + result = rawGet(t, key) >= 0 + +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 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 len*[A](t: CountTable[A]): int = + ## Returns the number of keys in ``t``. + result = t.counter + +proc clear*[A](t: var CountTable[A]) = + ## Resets the table so that it is empty. + clearImpl() + 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. + ## 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<#pairs.i,CountTable[A]>`_, + ## `keys<#keys.i,CountTable[A]>`_, and `values<#values.i,CountTable[A]>`_ + ## to iterate over ``t`` in the sorted order. # we use shellsort here; fast enough and simple var h = 1 @@ -1083,131 +2224,373 @@ proc sort*[A](t: var CountTable[A]) = if j < h: break if h == 1: break -proc len*[A](t: CountTableRef[A]): int = - ## returns the number of keys in ``t``. - result = t.counter +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") + for key, value in t: + s.inc(key, value) -iterator pairs*[A](t: CountTableRef[A]): (A, int) = - ## iterates over any ``(key, value)`` pair in the table ``t``. +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") + result = initCountTable[A](nextPowerOfTwo(max(s.len, t.len))) + for table in @[s, t]: + for key, value in table: + result.inc(key, value) + +proc `$`*[A](t: CountTable[A]): string = + ## The ``$`` operator for count tables. Used internally when calling `echo` + ## on a table. + dollarImpl() + +proc `==`*[A](s, t: CountTable[A]): bool = + ## The ``==`` operator for count tables. Returns ``true`` if both tables + ## contain the same keys with the same count. Insert order does not matter. + equalsImpl(s, t) + + +iterator pairs*[A](t: CountTable[A]): (A, int) = + ## Iterates over any ``(key, value)`` pair in the table ``t``. + ## + ## See also: + ## * `mpairs iterator<#mpairs.i,CountTable[A]>`_ + ## * `keys iterator<#keys.i,CountTable[A]>`_ + ## * `values iterator<#values.i,CountTable[A]>`_ + ## + ## **Examples:** + ## + ## .. code-block:: + ## 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 for h in 0..high(t.data): if t.data[h].val != 0: yield (t.data[h].key, t.data[h].val) -iterator mpairs*[A](t: CountTableRef[A]): (A, var int) = - ## iterates over any ``(key, value)`` pair in the table ``t``. The values can - ## be modified. +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") for h in 0..high(t.data): if t.data[h].val != 0: yield (t.data[h].key, t.data[h].val) -iterator keys*[A](t: CountTableRef[A]): A = - ## iterates over any key in the table ``t``. +iterator keys*[A](t: CountTable[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: + var a = toCountTable("abracadabra") + for k in keys(a): + a[k] = 2 + doAssert a == toCountTable("aabbccddrr") for h in 0..high(t.data): if t.data[h].val != 0: yield t.data[h].key -iterator values*[A](t: CountTableRef[A]): int = - ## iterates over any value in the table ``t``. +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 for h in 0..high(t.data): if t.data[h].val != 0: yield t.data[h].val -iterator mvalues*[A](t: CountTableRef[A]): var int = - ## iterates over any value in the table ``t``. The values can be modified. +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") for h in 0..high(t.data): if t.data[h].val != 0: yield t.data[h].val -proc `[]`*[A](t: CountTableRef[A], key: A): var int {.deprecatedGet.} = - ## retrieves the value at ``t[key]``. The value can be modified. - ## If ``key`` is not in ``t``, the ``KeyError`` exception is raised. - result = t[][key] -proc mget*[A](t: CountTableRef[A], key: A): var int {.deprecated.} = - ## retrieves the value at ``t[key]``. The value can be modified. - ## If ``key`` is not in ``t``, the ``KeyError`` exception is raised. - ## Use ``[]`` instead. - result = t[][key] -proc getOrDefault*[A](t: CountTableRef[A], key: A): int = - ## retrieves the value at ``t[key]`` iff ``key`` is in ``t``. Otherwise, 0 (the - ## default initialization value of ``int``), is returned. - result = t[].getOrDefault(key) -proc getOrDefault*[A](t: CountTableRef[A], key: A, default: int): int = - ## retrieves the value at ``t[key]`` iff ``key`` is in ``t``. Otherwise, the - ## integer value of ``default`` is returned. - result = t[].getOrDefault(key, default) -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) -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 +# --------------------------------------------------------------------------- +# ---------------------------- CountTableRef -------------------------------- +# --------------------------------------------------------------------------- -proc inc*[A](t: CountTableRef[A], key: A, val = 1) = - ## increments ``t[key]`` by ``val``. - t[].inc(key, val) +proc inc*[A](t: CountTableRef[A], key: A, val = 1) proc newCountTable*[A](initialSize=64): CountTableRef[A] = - ## creates a new count table that is empty. + ## Creates a new ref count table that is empty. + ## + ## ``initialSize`` must be a power of two (default: 64). + ## If you need to accept runtime values for this you could use the + ## `nextPowerOfTwo proc<math.html#nextPowerOfTwo,int>`_ from the + ## `math module<math.html>`_ or the `rightSize proc<#rightSize,Natural>`_ + ## from this module. ## - ## ``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,int>`_ for creating a + ## `CountTable` new(result) result[] = initCountTable[A](initialSize) proc newCountTable*[A](keys: openArray[A]): CountTableRef[A] = - ## creates a new count table with every key in ``keys`` having a count - ## of how many times it occurs in ``keys``. + ## Creates a new 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](rightSize(keys.len)) 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 + ## * `mget proc<#mget,CountTableRef[A],A>`_ + ## * `[]= 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 mget*[A](t: CountTableRef[A], key: A): var int = + ## Retrieves the value at ``t[key]``. The value can be modified. + ## + ## If ``key`` is not in ``t``, the ``KeyError`` exception is raised. + mget(t[], key) + +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 + t[][key] = val + +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") + t[].inc(key, val) + +proc smallest*[A](t: CountTableRef[A]): (A, 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, value)`` pair with the largest ``val``. Efficiency: O(n) + ## + ## See also: + ## * `smallest proc<#smallest,CountTable[A]>`_ + t[].largest + +proc hasKey*[A](t: CountTableRef[A], key: A): bool = + ## Returns true if ``key`` is in the table ``t``. + ## + ## 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 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 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 clear*[A](t: CountTableRef[A]) = + ## Resets the table so that it is empty. + clearImpl() + +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<#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 + +proc merge*[A](s, t: CountTableRef[A]) = + ## 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[]) + proc `$`*[A](t: CountTableRef[A]): string = - ## The ``$`` operator for count tables. + ## The ``$`` operator for count tables. Used internally when calling `echo` + ## on a table. dollarImpl() proc `==`*[A](s, t: CountTableRef[A]): bool = - ## The ``==`` operator for count tables. Returns ``true`` iff either both tables - ## are ``nil`` or none is ``nil`` and both contain the same keys with the same + ## The ``==`` operator for count tables. Returns ``true`` if either both tables + ## are ``nil``, or neither is ``nil`` and both contain the same keys with the same ## count. Insert order does not matter. if isNil(s): result = isNil(t) elif isNil(t): result = false else: result = s[] == t[] -proc smallest*[A](t: CountTableRef[A]): (A, int) = - ## returns the ``(key, value)`` pair with the smallest ``val``. Efficiency: O(n) - t[].smallest -proc largest*[A](t: CountTableRef[A]): (A, int) = - ## returns the ``(key, value)`` pair with the largest ``val``. Efficiency: O(n) - t[].largest +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:** + ## + ## .. code-block:: + ## 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 + for h in 0..high(t.data): + if t.data[h].val != 0: yield (t.data[h].key, t.data[h].val) -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 +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") + for h in 0..high(t.data): + if t.data[h].val != 0: yield (t.data[h].key, t.data[h].val) + +iterator keys*[A](t: CountTableRef[A]): A = + ## Iterates over any key in the table ``t``. + ## + ## 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") + for h in 0..high(t.data): + if t.data[h].val != 0: yield t.data[h].key + +iterator values*[A](t: CountTableRef[A]): int = + ## Iterates over any value in the table ``t``. + ## + ## 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 + for h in 0..high(t.data): + if t.data[h].val != 0: yield t.data[h].val + +iterator mvalues*[A](t: CountTableRef[A]): var int = + ## Iterates over any value in the table ``t``. The values can be modified. + ## + ## 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") + 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. - for key, value in t: - s.inc(key, value) -proc merge*[A](s, t: CountTable[A]): CountTable[A] = - ## merges the two tables into a new one. - result = initCountTable[A](nextPowerOfTwo(max(s.len, t.len))) - for table in @[s, t]: - for key, value in table: - result.inc(key, value) -proc merge*[A](s, t: CountTableRef[A]) = - ## merges the second table into the first one. - s[].merge(t[]) when isMainModule: type @@ -1325,9 +2708,9 @@ when isMainModule: #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) + doAssert 0 == t[testKey] t.inc(testKey, 3) - doAssert 3 == t.getOrDefault(testKey) + doAssert 3 == t[testKey] block: # Clear tests @@ -1394,6 +2777,18 @@ when isMainModule: let t = toCountTable([0, 0, 5, 5, 5]) doAssert t.smallest == (0, 2) + block: #10065 + let t = toCountTable("abracadabra") + doAssert t['z'] == 0 + + var t_mut = toCountTable("abracadabra") + doAssert t_mut['z'] == 0 + # the previous read may not have modified the table. + doAssert t_mut.hasKey('z') == false + t_mut['z'] = 1 + doAssert t_mut['z'] == 1 + doAssert t_mut.hasKey('z') == true + block: var tp: Table[string, string] = initTable[string, string]() doAssert "test1" == tp.getOrDefault("test1", "test1") |