3242 lines
104 KiB
Nim
3242 lines
104 KiB
Nim
#
|
|
#
|
|
# Nim's Runtime Library
|
|
# (c) Copyright 2015 Andreas Rumpf
|
|
#
|
|
# See the file "copying.txt", included in this
|
|
# distribution, for details about the copyright.
|
|
#
|
|
|
|
## The ``tables`` module implements variants of an efficient `hash table`:idx:
|
|
## (also often named `dictionary`:idx: in other programming languages) that is
|
|
## a mapping from keys to values.
|
|
##
|
|
## There are several different types of hash tables available:
|
|
## * `Table<#Table>`_ is the usual hash table,
|
|
## * `OrderedTable<#OrderedTable>`_ is like ``Table`` but remembers insertion order,
|
|
## * `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 `ref semantics<manual.html#types-reference-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:
|
|
##
|
|
## .. code-block::
|
|
## import tables
|
|
##
|
|
## var
|
|
## a = {1: "one", 2: "two"}.toTable # creates a Table
|
|
## b = a
|
|
##
|
|
## echo a, b # output: {1: one, 2: two}{1: one, 2: two}
|
|
##
|
|
## b[3] = "three"
|
|
## echo a, b # output: {1: one, 2: two}{1: one, 2: two, 3: three}
|
|
## echo a == b # output: false
|
|
##
|
|
## On the other hand, when ``a`` is a ``TableRef`` instead, then changes to ``b``
|
|
## also affect ``a``. Both ``a`` and ``b`` **ref** the same data structure:
|
|
##
|
|
## .. code-block::
|
|
## import tables
|
|
##
|
|
## var
|
|
## a = {1: "one", 2: "two"}.newTable # creates a TableRef
|
|
## b = a
|
|
##
|
|
## echo a, b # output: {1: one, 2: two}{1: one, 2: two}
|
|
##
|
|
## b[3] = "three"
|
|
## echo a, b # output: {1: one, 2: two, 3: three}{1: one, 2: two, 3: three}
|
|
## echo a == b # output: true
|
|
##
|
|
## ----
|
|
##
|
|
## Basic usage
|
|
## ===========
|
|
##
|
|
## Table
|
|
## -----
|
|
##
|
|
## .. code-block::
|
|
## import tables
|
|
## from sequtils import zip
|
|
##
|
|
## let
|
|
## names = ["John", "Paul", "George", "Ringo"]
|
|
## years = [1940, 1942, 1943, 1940]
|
|
##
|
|
## var beatles = initTable[string, int]()
|
|
##
|
|
## for pairs in zip(names, years):
|
|
## let (name, birthYear) = pairs
|
|
## beatles[name] = birthYear
|
|
##
|
|
## echo beatles
|
|
## # {"George": 1943, "Ringo": 1940, "Paul": 1942, "John": 1940}
|
|
##
|
|
##
|
|
## var beatlesByYear = initTable[int, seq[string]]()
|
|
##
|
|
## for pairs in zip(years, names):
|
|
## let (birthYear, name) = pairs
|
|
## if not beatlesByYear.hasKey(birthYear):
|
|
## # if a key doesn't exist, we create one with an empty sequence
|
|
## # before we can add elements to it
|
|
## beatlesByYear[birthYear] = @[]
|
|
## beatlesByYear[birthYear].add(name)
|
|
##
|
|
## echo beatlesByYear
|
|
## # {1940: @["John", "Ringo"], 1942: @["Paul"], 1943: @["George"]}
|
|
##
|
|
##
|
|
##
|
|
## OrderedTable
|
|
## ------------
|
|
##
|
|
## `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
|
|
##
|
|
## let myString = "abracadabra"
|
|
## 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,Positive>`_:
|
|
##
|
|
## .. code-block::
|
|
## import tables
|
|
##
|
|
## let myString = "abracadabra"
|
|
## var letterFrequencies = initCountTable[char]()
|
|
## for c in myString:
|
|
## letterFrequencies.inc(c)
|
|
## echo letterFrequencies
|
|
## # output: {'a': 5, 'b': 2, 'c': 1, 'd': 1, 'r': 2}
|
|
##
|
|
## ----
|
|
##
|
|
##
|
|
##
|
|
## 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: type mismatch: got (Person)
|
|
## but expected one of:
|
|
## hashes.hash(x: openArray[A]): Hash
|
|
## hashes.hash(x: int): Hash
|
|
## hashes.hash(x: float): Hash
|
|
## …
|
|
##
|
|
## What is happening here is that the types used for table keys require to have
|
|
## a ``hash()`` proc which will convert them to a `Hash <hashes.html#Hash>`_
|
|
## value, and the compiler is listing all the hash functions it knows.
|
|
## Additionally there has to be a ``==`` operator that provides the same
|
|
## semantics as its corresponding ``hash`` proc.
|
|
##
|
|
## After you add ``hash`` and ``==`` for your custom type everything will work.
|
|
## Currently, however, ``hash`` for objects is not defined, whereas
|
|
## ``system.==`` for objects does exist and performs a "deep" comparison (every
|
|
## field is compared) which is usually what you want. So in the following
|
|
## example implementing only ``hash`` suffices:
|
|
##
|
|
## .. code-block::
|
|
## import tables, hashes
|
|
##
|
|
## type
|
|
## Person = object
|
|
## firstName, lastName: string
|
|
##
|
|
## proc hash(x: Person): Hash =
|
|
## ## Piggyback on the already available string hash proc.
|
|
## ##
|
|
## ## Without this proc nothing works!
|
|
## result = x.firstName.hash !& x.lastName.hash
|
|
## result = !$result
|
|
##
|
|
## var
|
|
## salaries = initTable[Person, int]()
|
|
## p1, p2: Person
|
|
##
|
|
## p1.firstName = "Jon"
|
|
## p1.lastName = "Ross"
|
|
## salaries[p1] = 30_000
|
|
##
|
|
## p2.firstName = "소진"
|
|
## p2.lastName = "박"
|
|
## salaries[p2] = 45_000
|
|
##
|
|
## ----
|
|
##
|
|
## 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, algorithm
|
|
|
|
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, 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
|
|
countDeleted: int
|
|
TableRef*[A, B] = ref Table[A, B] ## Ref version of `Table<#Table>`_.
|
|
##
|
|
## For creating a new empty TableRef, use `newTable proc
|
|
## <#newTable,int>`_.
|
|
|
|
const
|
|
defaultInitialSize* = 64
|
|
|
|
# ------------------------------ helpers ---------------------------------
|
|
|
|
# Do NOT move these to tableimpl.nim, because sharedtables uses that
|
|
# file and has its own implementation.
|
|
template maxHash(t): untyped = high(t.data)
|
|
template dataLen(t): untyped = len(t.data)
|
|
|
|
include tableimpl
|
|
|
|
template get(t, key): untyped =
|
|
## retrieves the value at ``t[key]``. The value can be modified.
|
|
## If ``key`` is not in ``t``, the ``KeyError`` exception is raised.
|
|
mixin rawGet
|
|
var hc: Hash
|
|
var index = rawGet(t, key, hc)
|
|
if index >= 0: result = t.data[index].val
|
|
else:
|
|
when compiles($key):
|
|
raise newException(KeyError, "key not found: " & $key)
|
|
else:
|
|
raise newException(KeyError, "key not found")
|
|
|
|
proc enlarge[A, B](t: var Table[A, B]) =
|
|
var n: KeyValuePairSeq[A, B]
|
|
newSeq(n, t.counter.rightSize)
|
|
swap(t.data, n)
|
|
t.countDeleted = 0
|
|
for i in countup(0, high(n)):
|
|
let eh = n[i].hcode
|
|
if isFilledAndValid(eh):
|
|
var j: Hash = eh and maxHash(t)
|
|
var perturb = t.getPerturb(eh)
|
|
while isFilled(t.data[j].hcode):
|
|
j = nextTry(j, maxHash(t), perturb)
|
|
when defined(js):
|
|
rawInsert(t, t.data, n[i].key, n[i].val, eh, j)
|
|
else:
|
|
rawInsert(t, t.data, move n[i].key, move n[i].val, eh, j)
|
|
|
|
|
|
|
|
|
|
# -------------------------------------------------------------------
|
|
# ------------------------------ Table ------------------------------
|
|
# -------------------------------------------------------------------
|
|
|
|
proc initTable*[A, B](initialSize = defaultInitialSize): 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.
|
|
##
|
|
## Starting from Nim v0.20, tables are initialized by default and it is
|
|
## not necessary to call this function explicitly.
|
|
##
|
|
## See also:
|
|
## * `toTable proc<#toTable,openArray[]>`_
|
|
## * `newTable proc<#newTable,int>`_ for creating a `TableRef`
|
|
runnableExamples:
|
|
let
|
|
a = initTable[int, string]()
|
|
b = initTable[char, seq[int]]()
|
|
initImpl(result, initialSize)
|
|
|
|
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 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 `[]`*[A, B](t: var Table[A, B], key: A): var B =
|
|
## Retrieves the value at ``t[key]``. The value can be modified.
|
|
##
|
|
## If ``key`` is not in ``t``, the ``KeyError`` exception is raised.
|
|
##
|
|
## See also:
|
|
## * `getOrDefault proc<#getOrDefault,Table[A,B],A>`_ to return
|
|
## a default value (e.g. zero for int) if the key doesn't exist
|
|
## * `getOrDefault proc<#getOrDefault,Table[A,B],A,B>`_ to return
|
|
## a custom value if the key doesn't exist
|
|
## * `[]= proc<#[]=,Table[A,B],A,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 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]`` 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]`` 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:
|
|
## * `pop proc<#pop,Table[A,B],A,B>`_
|
|
## * `clear proc<#clear,Table[A,B]>`_ to empty the whole table
|
|
runnableExamples:
|
|
var a = {'a': 5, 'b': 9, 'c': 13}.toTable
|
|
a.del('a')
|
|
doAssert a == {'b': 9, 'c': 13}.toTable
|
|
a.del('z')
|
|
doAssert a == {'b': 9, 'c': 13}.toTable
|
|
|
|
delImpl()
|
|
|
|
proc pop*[A, B](t: var Table[A, B], key: A, val: var B): bool =
|
|
## Deletes the ``key`` from the table.
|
|
## Returns ``true``, if the ``key`` existed, and sets ``val`` to the
|
|
## mapping of the key. Otherwise, returns ``false``, and the ``val`` is
|
|
## unchanged.
|
|
##
|
|
## See also:
|
|
## * `del proc<#del,Table[A,B],A>`_
|
|
## * `clear proc<#clear,Table[A,B]>`_ to empty the whole table
|
|
runnableExamples:
|
|
var
|
|
a = {'a': 5, 'b': 9, 'c': 13}.toTable
|
|
i: int
|
|
doAssert a.pop('b', i) == true
|
|
doAssert a == {'a': 5, 'c': 13}.toTable
|
|
doAssert i == 9
|
|
i = 0
|
|
doAssert a.pop('z', i) == false
|
|
doAssert a == {'a': 5, 'c': 13}.toTable
|
|
doAssert i == 0
|
|
|
|
var hc: Hash
|
|
var index = rawGet(t, key, hc)
|
|
result = index >= 0
|
|
if result:
|
|
val = move(t.data[index].val)
|
|
delImplIdx(t, index)
|
|
|
|
proc take*[A, B](t: var Table[A, B], key: A, val: var B): bool {.inline.} =
|
|
## Alias for:
|
|
## * `pop proc<#pop,Table[A,B],A,B>`_
|
|
pop(t, key, val)
|
|
|
|
proc clear*[A, B](t: var Table[A, B]) =
|
|
## Resets the table so that it is empty.
|
|
##
|
|
## See also:
|
|
## * `del proc<#del,Table[A,B],A>`_
|
|
## * `pop proc<#pop,Table[A,B],A,B>`_
|
|
runnableExamples:
|
|
var a = {'a': 5, 'b': 9, 'c': 13}.toTable
|
|
doAssert len(a) == 3
|
|
clear(a)
|
|
doAssert len(a) == 0
|
|
|
|
clearImpl()
|
|
|
|
proc `$`*[A, B](t: Table[A, B]): string =
|
|
## The ``$`` operator for hash tables. Used internally when calling `echo`
|
|
## on a table.
|
|
dollarImpl()
|
|
|
|
proc `==`*[A, B](s, t: Table[A, B]): bool =
|
|
## The ``==`` operator for hash tables. Returns ``true`` if the content of both
|
|
## tables contains the same key-value pairs. Insert order does not matter.
|
|
runnableExamples:
|
|
let
|
|
a = {'a': 5, 'b': 9, 'c': 13}.toTable
|
|
b = {'b': 9, 'c': 13, 'a': 5}.toTable
|
|
doAssert a == b
|
|
|
|
equalsImpl(s, t)
|
|
|
|
proc indexBy*[A, B, C](collection: A, index: proc(x: B): C): Table[C, B] =
|
|
## Index the collection with the proc provided.
|
|
# TODO: As soon as supported, change collection: A to collection: A[B]
|
|
result = initTable[C, B]()
|
|
for item in collection:
|
|
result[index(item)] = item
|
|
|
|
|
|
|
|
template withValue*[A, B](t: var Table[A, B], key: A, value, body: untyped) =
|
|
## Retrieves the value at ``t[key]``.
|
|
##
|
|
## ``value`` can be modified in the scope of the ``withValue`` call.
|
|
##
|
|
## .. code-block:: nim
|
|
##
|
|
## sharedTable.withValue(key, value) do:
|
|
## # block is executed only if ``key`` in ``t``
|
|
## value.name = "username"
|
|
## value.uid = 1000
|
|
##
|
|
mixin rawGet
|
|
var hc: Hash
|
|
var index = rawGet(t, key, hc)
|
|
let hasKey = index >= 0
|
|
if hasKey:
|
|
var value {.inject.} = addr(t.data[index].val)
|
|
body
|
|
|
|
template withValue*[A, B](t: var Table[A, B], key: A,
|
|
value, body1, body2: untyped) =
|
|
## Retrieves the value at ``t[key]``.
|
|
##
|
|
## ``value`` can be modified in the scope of the ``withValue`` call.
|
|
##
|
|
## .. code-block:: nim
|
|
##
|
|
## table.withValue(key, value) do:
|
|
## # block is executed only if ``key`` in ``t``
|
|
## value.name = "username"
|
|
## value.uid = 1000
|
|
## do:
|
|
## # block is executed when ``key`` not in ``t``
|
|
## raise newException(KeyError, "Key not found")
|
|
##
|
|
mixin rawGet
|
|
var hc: Hash
|
|
var index = rawGet(t, key, hc)
|
|
let hasKey = index >= 0
|
|
if hasKey:
|
|
var value {.inject.} = addr(t.data[index].val)
|
|
body1
|
|
else:
|
|
body2
|
|
|
|
|
|
iterator pairs*[A, B](t: Table[A, B]): (A, B) =
|
|
## 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]
|
|
let L = len(t)
|
|
for h in 0 .. high(t.data):
|
|
if isFilledAndValid(t.data[h].hcode):
|
|
yield (t.data[h].key, t.data[h].val)
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
iterator mpairs*[A, B](t: var Table[A, B]): (A, var B) =
|
|
## Iterates over any ``(key, value)`` pair in the table ``t`` (must be
|
|
## declared as `var`). The values can be modified.
|
|
##
|
|
## See also:
|
|
## * `pairs iterator<#pairs.i,Table[A,B]>`_
|
|
## * `mvalues iterator<#mvalues.i,Table[A,B]>`_
|
|
runnableExamples:
|
|
var a = {
|
|
'o': @[1, 5, 7, 9],
|
|
'e': @[2, 4, 6, 8]
|
|
}.toTable
|
|
for k, v in a.mpairs:
|
|
v.add(v[0] + 10)
|
|
doAssert a == {'e': @[2, 4, 6, 8, 12], 'o': @[1, 5, 7, 9, 11]}.toTable
|
|
|
|
let L = len(t)
|
|
for h in 0 .. high(t.data):
|
|
if isFilledAndValid(t.data[h].hcode):
|
|
yield (t.data[h].key, t.data[h].val)
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
iterator keys*[A, B](t: Table[A, B]): A =
|
|
## Iterates over any key in the table ``t``.
|
|
##
|
|
## See also:
|
|
## * `pairs iterator<#pairs.i,Table[A,B]>`_
|
|
## * `values iterator<#values.i,Table[A,B]>`_
|
|
runnableExamples:
|
|
var a = {
|
|
'o': @[1, 5, 7, 9],
|
|
'e': @[2, 4, 6, 8]
|
|
}.toTable
|
|
for k in a.keys:
|
|
a[k].add(99)
|
|
doAssert a == {'e': @[2, 4, 6, 8, 99], 'o': @[1, 5, 7, 9, 99]}.toTable
|
|
|
|
let L = len(t)
|
|
for h in 0 .. high(t.data):
|
|
if isFilledAndValid(t.data[h].hcode):
|
|
yield t.data[h].key
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
iterator values*[A, B](t: Table[A, B]): B =
|
|
## Iterates over any value in the table ``t``.
|
|
##
|
|
## See also:
|
|
## * `pairs iterator<#pairs.i,Table[A,B]>`_
|
|
## * `keys iterator<#keys.i,Table[A,B]>`_
|
|
## * `mvalues iterator<#mvalues.i,Table[A,B]>`_
|
|
runnableExamples:
|
|
let a = {
|
|
'o': @[1, 5, 7, 9],
|
|
'e': @[2, 4, 6, 8]
|
|
}.toTable
|
|
for v in a.values:
|
|
doAssert v.len == 4
|
|
|
|
let L = len(t)
|
|
for h in 0 .. high(t.data):
|
|
if isFilledAndValid(t.data[h].hcode):
|
|
yield t.data[h].val
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
iterator mvalues*[A, B](t: var Table[A, B]): var B =
|
|
## Iterates over any value in the table ``t`` (must be
|
|
## declared as `var`). The values can be modified.
|
|
##
|
|
## See also:
|
|
## * `mpairs iterator<#mpairs.i,Table[A,B]>`_
|
|
## * `values iterator<#values.i,Table[A,B]>`_
|
|
runnableExamples:
|
|
var a = {
|
|
'o': @[1, 5, 7, 9],
|
|
'e': @[2, 4, 6, 8]
|
|
}.toTable
|
|
for v in a.mvalues:
|
|
v.add(99)
|
|
doAssert a == {'e': @[2, 4, 6, 8, 99], 'o': @[1, 5, 7, 9, 99]}.toTable
|
|
|
|
let L = len(t)
|
|
for h in 0 .. high(t.data):
|
|
if isFilledAndValid(t.data[h].hcode):
|
|
yield t.data[h].val
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
template hasKeyOrPutCache(cache, h): bool =
|
|
# using `IntSet` would be an option worth considering to avoid quadratic
|
|
# behavior in case user misuses Table with lots of duplicate keys; but it
|
|
# has overhead in the common case of small number of duplicates.
|
|
# However: when lots of duplicates are used, all operations would be slow
|
|
# anyway because the full `hash(key)` is identical for these, which makes
|
|
# `nextTry` follow the exact same path for each key, resulting in large
|
|
# collision clusters. Alternatives could involve modifying the hash/retrieval
|
|
# based on duplicate key count.
|
|
var ret = false
|
|
for hi in cache:
|
|
if hi == h:
|
|
ret = true
|
|
break
|
|
if not ret: cache.add h
|
|
ret
|
|
|
|
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``.
|
|
##
|
|
## Used if you have a table with duplicate keys (as a result of using
|
|
## `add proc<#add,Table[A,B],A,B>`_).
|
|
##
|
|
runnableExamples:
|
|
import sequtils, algorithm
|
|
|
|
var a = {'a': 3, 'b': 5}.toTable
|
|
for i in 1..3: a.add('z', 10*i)
|
|
doAssert toSeq(a.pairs).sorted == @[('a', 3), ('b', 5), ('z', 10), ('z', 20), ('z', 30)]
|
|
doAssert sorted(toSeq(a.allValues('z'))) == @[10, 20, 30]
|
|
|
|
let hc = genHash(key)
|
|
var h: Hash = hc and high(t.data)
|
|
let L = len(t)
|
|
var perturb = t.getPerturb(hc)
|
|
|
|
var num = 0
|
|
var cache: seq[Hash]
|
|
while isFilled(t.data[h].hcode): # `isFilledAndValid` would be incorrect, see test for `allValues`
|
|
if t.data[h].hcode == hc and t.data[h].key == key:
|
|
if not hasKeyOrPutCache(cache, h):
|
|
yield t.data[h].val
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
h = nextTry(h, high(t.data), perturb)
|
|
|
|
|
|
|
|
# -------------------------------------------------------------------
|
|
# ---------------------------- TableRef -----------------------------
|
|
# -------------------------------------------------------------------
|
|
|
|
|
|
proc newTable*[A, B](initialSize = defaultInitialSize): <//>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 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 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
|
|
|
|
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]
|
|
|
|
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
|
|
|
|
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 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 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]`` 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]`` 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
|
|
## 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 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!**
|
|
##
|
|
## 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.
|
|
##
|
|
## **If duplicate keys were added, this may need to be called multiple times.**
|
|
##
|
|
## See also:
|
|
## * `pop proc<#pop,TableRef[A,B],A,B>`_
|
|
## * `clear proc<#clear,TableRef[A,B]>`_ to empty the whole table
|
|
runnableExamples:
|
|
var a = {'a': 5, 'b': 9, 'c': 13}.newTable
|
|
a.del('a')
|
|
doAssert a == {'b': 9, 'c': 13}.newTable
|
|
a.del('z')
|
|
doAssert a == {'b': 9, 'c': 13}.newTable
|
|
|
|
t[].del(key)
|
|
|
|
proc pop*[A, B](t: TableRef[A, B], key: A, val: var B): bool =
|
|
## Deletes the ``key`` from the table.
|
|
## Returns ``true``, if the ``key`` existed, and sets ``val`` to the
|
|
## mapping of the key. Otherwise, returns ``false``, and the ``val`` is
|
|
## unchanged.
|
|
##
|
|
## **If duplicate keys were added, this may need to be called multiple times.**
|
|
##
|
|
## See also:
|
|
## * `del proc<#del,TableRef[A,B],A>`_
|
|
## * `clear proc<#clear,TableRef[A,B]>`_ to empty the whole table
|
|
runnableExamples:
|
|
var
|
|
a = {'a': 5, 'b': 9, 'c': 13}.newTable
|
|
i: int
|
|
doAssert a.pop('b', i) == true
|
|
doAssert a == {'a': 5, 'c': 13}.newTable
|
|
doAssert i == 9
|
|
i = 0
|
|
doAssert a.pop('z', i) == false
|
|
doAssert a == {'a': 5, 'c': 13}.newTable
|
|
doAssert i == 0
|
|
|
|
result = t[].pop(key, val)
|
|
|
|
proc take*[A, B](t: TableRef[A, B], key: A, val: var B): bool {.inline.} =
|
|
## Alias for:
|
|
## * `pop proc<#pop,TableRef[A,B],A,B>`_
|
|
pop(t, key, val)
|
|
|
|
proc clear*[A, B](t: TableRef[A, B]) =
|
|
## Resets the table so that it is empty.
|
|
##
|
|
## See also:
|
|
## * `del proc<#del,Table[A,B],A>`_
|
|
## * `pop proc<#pop,Table[A,B],A,B>`_
|
|
runnableExamples:
|
|
var a = {'a': 5, 'b': 9, 'c': 13}.newTable
|
|
doAssert len(a) == 3
|
|
clear(a)
|
|
doAssert len(a) == 0
|
|
|
|
clearImpl()
|
|
|
|
proc `$`*[A, B](t: TableRef[A, B]): string =
|
|
## The ``$`` operator for hash tables. Used internally when calling `echo`
|
|
## on a table.
|
|
dollarImpl()
|
|
|
|
proc `==`*[A, B](s, t: TableRef[A, B]): bool =
|
|
## The ``==`` operator for hash tables. Returns ``true`` if either both tables
|
|
## are ``nil``, or neither is ``nil`` and the content of both tables contains the
|
|
## 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[])
|
|
|
|
|
|
|
|
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]
|
|
let L = len(t)
|
|
for h in 0 .. high(t.data):
|
|
if isFilledAndValid(t.data[h].hcode):
|
|
yield (t.data[h].key, t.data[h].val)
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
iterator mpairs*[A, B](t: TableRef[A, B]): (A, var B) =
|
|
## Iterates over any ``(key, value)`` pair in the table ``t``. The values
|
|
## can be modified.
|
|
##
|
|
## See also:
|
|
## * `pairs iterator<#pairs.i,TableRef[A,B]>`_
|
|
## * `mvalues iterator<#mvalues.i,TableRef[A,B]>`_
|
|
runnableExamples:
|
|
let a = {
|
|
'o': @[1, 5, 7, 9],
|
|
'e': @[2, 4, 6, 8]
|
|
}.newTable
|
|
for k, v in a.mpairs:
|
|
v.add(v[0] + 10)
|
|
doAssert a == {'e': @[2, 4, 6, 8, 12], 'o': @[1, 5, 7, 9, 11]}.newTable
|
|
|
|
let L = len(t)
|
|
for h in 0 .. high(t.data):
|
|
if isFilledAndValid(t.data[h].hcode):
|
|
yield (t.data[h].key, t.data[h].val)
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
iterator keys*[A, B](t: TableRef[A, B]): A =
|
|
## Iterates over any key in the table ``t``.
|
|
##
|
|
## See also:
|
|
## * `pairs iterator<#pairs.i,TableRef[A,B]>`_
|
|
## * `values iterator<#values.i,TableRef[A,B]>`_
|
|
runnableExamples:
|
|
let a = {
|
|
'o': @[1, 5, 7, 9],
|
|
'e': @[2, 4, 6, 8]
|
|
}.newTable
|
|
for k in a.keys:
|
|
a[k].add(99)
|
|
doAssert a == {'e': @[2, 4, 6, 8, 99], 'o': @[1, 5, 7, 9, 99]}.newTable
|
|
|
|
let L = len(t)
|
|
for h in 0 .. high(t.data):
|
|
if isFilledAndValid(t.data[h].hcode):
|
|
yield t.data[h].key
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
iterator values*[A, B](t: TableRef[A, B]): B =
|
|
## Iterates over any value in the table ``t``.
|
|
##
|
|
## See also:
|
|
## * `pairs iterator<#pairs.i,TableRef[A,B]>`_
|
|
## * `keys iterator<#keys.i,TableRef[A,B]>`_
|
|
## * `mvalues iterator<#mvalues.i,TableRef[A,B]>`_
|
|
runnableExamples:
|
|
let a = {
|
|
'o': @[1, 5, 7, 9],
|
|
'e': @[2, 4, 6, 8]
|
|
}.newTable
|
|
for v in a.values:
|
|
doAssert v.len == 4
|
|
|
|
let L = len(t)
|
|
for h in 0 .. high(t.data):
|
|
if isFilledAndValid(t.data[h].hcode):
|
|
yield t.data[h].val
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
iterator mvalues*[A, B](t: TableRef[A, B]): var B =
|
|
## Iterates over any value in the table ``t``. The values can be modified.
|
|
##
|
|
## See also:
|
|
## * `mpairs iterator<#mpairs.i,TableRef[A,B]>`_
|
|
## * `values iterator<#values.i,TableRef[A,B]>`_
|
|
runnableExamples:
|
|
let a = {
|
|
'o': @[1, 5, 7, 9],
|
|
'e': @[2, 4, 6, 8]
|
|
}.newTable
|
|
for v in a.mvalues:
|
|
v.add(99)
|
|
doAssert a == {'e': @[2, 4, 6, 8, 99], 'o': @[1, 5, 7, 9, 99]}.newTable
|
|
|
|
let L = len(t)
|
|
for h in 0 .. high(t.data):
|
|
if isFilledAndValid(t.data[h].hcode):
|
|
yield t.data[h].val
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
# ---------------------------------------------------------------------------
|
|
# ------------------------------ OrderedTable -------------------------------
|
|
# ---------------------------------------------------------------------------
|
|
|
|
type
|
|
OrderedKeyValuePair[A, B] = tuple[
|
|
hcode: Hash, next: int, key: A, val: B]
|
|
OrderedKeyValuePairSeq[A, B] = seq[OrderedKeyValuePair[A, B]]
|
|
OrderedTable*[A, B] = object
|
|
## Hash table that remembers insertion order.
|
|
##
|
|
## For creating an empty OrderedTable, use `initOrderedTable proc
|
|
## <#initOrderedTable,int>`_.
|
|
data: OrderedKeyValuePairSeq[A, B]
|
|
counter, first, last: int
|
|
countDeleted: int
|
|
|
|
OrderedTableRef*[A, B] = ref OrderedTable[A, B] ## Ref version of
|
|
## `OrderedTable<#OrderedTable>`_.
|
|
##
|
|
## For creating a new empty OrderedTableRef, use `newOrderedTable proc
|
|
## <#newOrderedTable,int>`_.
|
|
|
|
|
|
# ------------------------------ helpers ---------------------------------
|
|
|
|
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 rawInsert[A, B](t: var OrderedTable[A, B],
|
|
data: var OrderedKeyValuePairSeq[A, B],
|
|
key: A, val: B, hc: Hash, h: Hash) =
|
|
rawInsertImpl(t)
|
|
data[h].next = -1
|
|
if t.first < 0: t.first = h
|
|
if t.last >= 0: data[t.last].next = h
|
|
t.last = h
|
|
|
|
proc enlarge[A, B](t: var OrderedTable[A, B]) =
|
|
var n: OrderedKeyValuePairSeq[A, B]
|
|
newSeq(n, t.counter.rightSize)
|
|
var h = t.first
|
|
t.first = -1
|
|
t.last = -1
|
|
swap(t.data, n)
|
|
t.countDeleted = 0
|
|
while h >= 0:
|
|
var nxt = n[h].next
|
|
let eh = n[h].hcode
|
|
if isFilledAndValid(eh):
|
|
var j: Hash = eh and maxHash(t)
|
|
var perturb = t.getPerturb(eh)
|
|
while isFilled(t.data[j].hcode):
|
|
j = nextTry(j, maxHash(t), perturb)
|
|
rawInsert(t, t.data, move n[h].key, move n[h].val, n[h].hcode, j)
|
|
h = nxt
|
|
|
|
template forAllOrderedPairs(yieldStmt: untyped) {.dirty.} =
|
|
if t.counter > 0:
|
|
var h = t.first
|
|
while h >= 0:
|
|
var nxt = t.data[h].next
|
|
# For OrderedTable/OrderedTableRef, isFilled is ok because `del` is O(n)
|
|
# and doesn't create tombsones, but if it does start using tombstones,
|
|
# carefully replace `isFilled` by `isFilledAndValid` as appropriate for these
|
|
# table types only, ditto with `OrderedSet`.
|
|
if isFilled(t.data[h].hcode):
|
|
yieldStmt
|
|
h = nxt
|
|
|
|
# ----------------------------------------------------------------------
|
|
|
|
proc initOrderedTable*[A, B](initialSize = defaultInitialSize): OrderedTable[A, B] =
|
|
## Creates a new ordered hash table that is empty.
|
|
##
|
|
## ``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.
|
|
##
|
|
## Starting from Nim v0.20, tables are initialized by default and it is
|
|
## not necessary to call this function explicitly.
|
|
##
|
|
## See also:
|
|
## * `toOrderedTable proc<#toOrderedTable,openArray[]>`_
|
|
## * `newOrderedTable proc<#newOrderedTable,int>`_ for creating an
|
|
## `OrderedTableRef`
|
|
runnableExamples:
|
|
let
|
|
a = initOrderedTable[int, string]()
|
|
b = initOrderedTable[char, seq[int]]()
|
|
initImpl(result, initialSize)
|
|
|
|
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 toOrderedTable*[A, B](pairs: openArray[(A, B)]): OrderedTable[A, B] =
|
|
## Creates a new ordered hash table that contains the given ``pairs``.
|
|
##
|
|
## ``pairs`` is a container consisting of ``(key, value)`` tuples.
|
|
##
|
|
## See also:
|
|
## * `initOrderedTable proc<#initOrderedTable,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], 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](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 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:
|
|
## * `pop proc<#pop,OrderedTable[A,B],A,B>`_
|
|
## * `clear proc<#clear,OrderedTable[A,B]>`_ to empty the whole table
|
|
runnableExamples:
|
|
var a = {'a': 5, 'b': 9, 'c': 13}.toOrderedTable
|
|
a.del('a')
|
|
doAssert a == {'b': 9, 'c': 13}.toOrderedTable
|
|
a.del('z')
|
|
doAssert a == {'b': 9, 'c': 13}.toOrderedTable
|
|
|
|
if t.counter == 0: return
|
|
var n: OrderedKeyValuePairSeq[A, B]
|
|
newSeq(n, len(t.data))
|
|
var h = t.first
|
|
t.first = -1
|
|
t.last = -1
|
|
swap(t.data, n)
|
|
let hc = genHash(key)
|
|
while h >= 0:
|
|
var nxt = n[h].next
|
|
if isFilled(n[h].hcode):
|
|
if n[h].hcode == hc and n[h].key == key:
|
|
dec t.counter
|
|
else:
|
|
var j = -1 - rawGetKnownHC(t, n[h].key, n[h].hcode)
|
|
rawInsert(t, t.data, move n[h].key, move n[h].val, n[h].hcode, j)
|
|
h = nxt
|
|
|
|
proc pop*[A, B](t: var OrderedTable[A, B], key: A, val: var B): bool {.since: (1, 1).} =
|
|
## Deletes the ``key`` from the table.
|
|
## Returns ``true``, if the ``key`` existed, and sets ``val`` to the
|
|
## mapping of the key. Otherwise, returns ``false``, and the ``val`` is
|
|
## unchanged.
|
|
##
|
|
## O(n) complexity.
|
|
##
|
|
## See also:
|
|
## * `del proc<#del,OrderedTable[A,B],A>`_
|
|
## * `clear proc<#clear,OrderedTable[A,B]>`_ to empty the whole table
|
|
runnableExamples:
|
|
var
|
|
a = {'c': 5, 'b': 9, 'a': 13}.toOrderedTable
|
|
i: int
|
|
doAssert a.pop('b', i) == true
|
|
doAssert a == {'c': 5, 'a': 13}.toOrderedTable
|
|
doAssert i == 9
|
|
i = 0
|
|
doAssert a.pop('z', i) == false
|
|
doAssert a == {'c': 5, 'a': 13}.toOrderedTable
|
|
doAssert i == 0
|
|
|
|
var hc: Hash
|
|
var index = rawGet(t, key, hc)
|
|
result = index >= 0
|
|
if result:
|
|
val = move(t.data[index].val)
|
|
del(t, key)
|
|
|
|
proc clear*[A, B](t: var OrderedTable[A, B]) =
|
|
## Resets the table so that it is empty.
|
|
##
|
|
## See also:
|
|
## * `del proc<#del,OrderedTable[A,B],A>`_
|
|
## * `pop proc<#pop,OrderedTable[A,B],A,B>`_
|
|
runnableExamples:
|
|
var a = {'a': 5, 'b': 9, 'c': 13}.toOrderedTable
|
|
doAssert len(a) == 3
|
|
clear(a)
|
|
doAssert len(a) == 0
|
|
|
|
clearImpl()
|
|
t.first = -1
|
|
t.last = -1
|
|
|
|
proc sort*[A, B](t: var OrderedTable[A, B], cmp: proc (x, y: (A, B)): int,
|
|
order = SortOrder.Ascending) =
|
|
## 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,CountTable[A]>`_ for count tables).
|
|
runnableExamples:
|
|
import algorithm
|
|
var a = initOrderedTable[char, int]()
|
|
for i, c in "cab":
|
|
a[c] = 10*i
|
|
doAssert a == {'c': 0, 'a': 10, 'b': 20}.toOrderedTable
|
|
a.sort(system.cmp)
|
|
doAssert a == {'a': 10, 'b': 20, 'c': 0}.toOrderedTable
|
|
a.sort(system.cmp, order = SortOrder.Descending)
|
|
doAssert a == {'c': 0, 'b': 20, 'a': 10}.toOrderedTable
|
|
|
|
var list = t.first
|
|
var
|
|
p, q, e, tail, oldhead: int
|
|
nmerges, psize, qsize, i: int
|
|
if t.counter == 0: return
|
|
var insize = 1
|
|
while true:
|
|
p = list; oldhead = list
|
|
list = -1; tail = -1; nmerges = 0
|
|
while p >= 0:
|
|
inc(nmerges)
|
|
q = p
|
|
psize = 0
|
|
i = 0
|
|
while i < insize:
|
|
inc(psize)
|
|
q = t.data[q].next
|
|
if q < 0: break
|
|
inc(i)
|
|
qsize = insize
|
|
while psize > 0 or (qsize > 0 and q >= 0):
|
|
if psize == 0:
|
|
e = q; q = t.data[q].next; dec(qsize)
|
|
elif qsize == 0 or q < 0:
|
|
e = p; p = t.data[p].next; dec(psize)
|
|
elif cmp((t.data[p].key, t.data[p].val),
|
|
(t.data[q].key, t.data[q].val)) * order <= 0:
|
|
e = p; p = t.data[p].next; dec(psize)
|
|
else:
|
|
e = q; q = t.data[q].next; dec(qsize)
|
|
if tail >= 0: t.data[tail].next = e
|
|
else: list = e
|
|
tail = e
|
|
p = q
|
|
t.data[tail].next = -1
|
|
if nmerges <= 1: break
|
|
insize = insize * 2
|
|
t.first = list
|
|
t.last = tail
|
|
|
|
proc `$`*[A, B](t: OrderedTable[A, B]): string =
|
|
## The ``$`` operator for ordered hash tables. Used internally when calling
|
|
## `echo` on a table.
|
|
dollarImpl()
|
|
|
|
proc `==`*[A, B](s, t: OrderedTable[A, B]): bool =
|
|
## The ``==`` operator for ordered hash tables. Returns ``true`` if both the
|
|
## 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]
|
|
|
|
let L = len(t)
|
|
forAllOrderedPairs:
|
|
yield (t.data[h].key, t.data[h].val)
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
iterator mpairs*[A, B](t: var OrderedTable[A, B]): (A, var B) =
|
|
## Iterates over any ``(key, value)`` pair in the table ``t`` (must be
|
|
## declared as `var`) in insertion order. The values can be modified.
|
|
##
|
|
## See also:
|
|
## * `pairs iterator<#pairs.i,OrderedTable[A,B]>`_
|
|
## * `mvalues iterator<#mvalues.i,OrderedTable[A,B]>`_
|
|
runnableExamples:
|
|
var a = {
|
|
'o': @[1, 5, 7, 9],
|
|
'e': @[2, 4, 6, 8]
|
|
}.toOrderedTable
|
|
for k, v in a.mpairs:
|
|
v.add(v[0] + 10)
|
|
doAssert a == {'o': @[1, 5, 7, 9, 11],
|
|
'e': @[2, 4, 6, 8, 12]}.toOrderedTable
|
|
|
|
let L = len(t)
|
|
forAllOrderedPairs:
|
|
yield (t.data[h].key, t.data[h].val)
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
iterator keys*[A, B](t: 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
|
|
|
|
let L = len(t)
|
|
forAllOrderedPairs:
|
|
yield t.data[h].key
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
iterator values*[A, B](t: 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
|
|
|
|
let L = len(t)
|
|
forAllOrderedPairs:
|
|
yield t.data[h].val
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
iterator mvalues*[A, B](t: var OrderedTable[A, B]): var B =
|
|
## Iterates over any value in the table ``t`` (must be
|
|
## declared as `var`) in insertion order. The values
|
|
## can be modified.
|
|
##
|
|
## See also:
|
|
## * `mpairs iterator<#mpairs.i,OrderedTable[A,B]>`_
|
|
## * `values iterator<#values.i,OrderedTable[A,B]>`_
|
|
runnableExamples:
|
|
var a = {
|
|
'o': @[1, 5, 7, 9],
|
|
'e': @[2, 4, 6, 8]
|
|
}.toOrderedTable
|
|
for v in a.mvalues:
|
|
v.add(99)
|
|
doAssert a == {'o': @[1, 5, 7, 9, 99],
|
|
'e': @[2, 4, 6, 8, 99]}.toOrderedTable
|
|
|
|
let L = len(t)
|
|
forAllOrderedPairs:
|
|
yield t.data[h].val
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
|
|
|
|
|
|
|
|
# ---------------------------------------------------------------------------
|
|
# --------------------------- OrderedTableRef -------------------------------
|
|
# ---------------------------------------------------------------------------
|
|
|
|
proc newOrderedTable*[A, B](initialSize = defaultInitialSize): <//>OrderedTableRef[A, B] =
|
|
## Creates a new ordered ref hash table that is empty.
|
|
##
|
|
## ``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 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 `[]=`*[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]`` 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]`` 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
|
|
## 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 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!**
|
|
##
|
|
## 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 del*[A, B](t: OrderedTableRef[A, B], key: A) =
|
|
## Deletes ``key`` from hash table ``t``. Does nothing if the key does not exist.
|
|
##
|
|
## See also:
|
|
## * `clear proc<#clear,OrderedTableRef[A,B]>`_ to empty the whole table
|
|
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 pop*[A, B](t: OrderedTableRef[A, B], key: A, val: var B): bool {.since: (1, 1).} =
|
|
## Deletes the ``key`` from the table.
|
|
## Returns ``true``, if the ``key`` existed, and sets ``val`` to the
|
|
## mapping of the key. Otherwise, returns ``false``, and the ``val`` is
|
|
## unchanged.
|
|
##
|
|
## See also:
|
|
## * `del proc<#del,OrderedTableRef[A,B],A>`_
|
|
## * `clear proc<#clear,OrderedTableRef[A,B]>`_ to empty the whole table
|
|
runnableExamples:
|
|
var
|
|
a = {'c': 5, 'b': 9, 'a': 13}.newOrderedTable
|
|
i: int
|
|
doAssert a.pop('b', i) == true
|
|
doAssert a == {'c': 5, 'a': 13}.newOrderedTable
|
|
doAssert i == 9
|
|
i = 0
|
|
doAssert a.pop('z', i) == false
|
|
doAssert a == {'c': 5, 'a': 13}.newOrderedTable
|
|
doAssert i == 0
|
|
|
|
pop(t[], key, val)
|
|
|
|
proc clear*[A, B](t: OrderedTableRef[A, B]) =
|
|
## Resets the table so that it is empty.
|
|
##
|
|
## See also:
|
|
## * `del proc<#del,OrderedTableRef[A,B],A>`_
|
|
runnableExamples:
|
|
var a = {'a': 5, 'b': 9, 'c': 13}.newOrderedTable
|
|
doAssert len(a) == 3
|
|
clear(a)
|
|
doAssert len(a) == 0
|
|
|
|
clear(t[])
|
|
|
|
proc sort*[A, B](t: OrderedTableRef[A, B], cmp: proc (x, y: (A, B)): int,
|
|
order = SortOrder.Ascending) =
|
|
## Sorts ``t`` according to the function ``cmp``.
|
|
##
|
|
## This modifies the internal list
|
|
## that kept the insertion order, so insertion order is lost after this
|
|
## call but key lookup and insertions remain possible after ``sort`` (in
|
|
## contrast to the `sort proc<#sort,CountTableRef[A]>`_ for count tables).
|
|
runnableExamples:
|
|
import algorithm
|
|
var a = newOrderedTable[char, int]()
|
|
for i, c in "cab":
|
|
a[c] = 10*i
|
|
doAssert a == {'c': 0, 'a': 10, 'b': 20}.newOrderedTable
|
|
a.sort(system.cmp)
|
|
doAssert a == {'a': 10, 'b': 20, 'c': 0}.newOrderedTable
|
|
a.sort(system.cmp, order = SortOrder.Descending)
|
|
doAssert a == {'c': 0, 'b': 20, 'a': 10}.newOrderedTable
|
|
|
|
t[].sort(cmp, order = order)
|
|
|
|
proc `$`*[A, B](t: OrderedTableRef[A, B]): string =
|
|
## The ``$`` operator for hash tables. Used internally when calling `echo`
|
|
## on a table.
|
|
dollarImpl()
|
|
|
|
proc `==`*[A, B](s, t: OrderedTableRef[A, B]): bool =
|
|
## The ``==`` operator for ordered hash tables. Returns true if either both
|
|
## tables are ``nil``, or neither is ``nil`` and the content and the order of
|
|
## 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[]
|
|
|
|
|
|
|
|
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]
|
|
|
|
let L = len(t)
|
|
forAllOrderedPairs:
|
|
yield (t.data[h].key, t.data[h].val)
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
iterator mpairs*[A, B](t: OrderedTableRef[A, B]): (A, var B) =
|
|
## Iterates over any ``(key, value)`` pair in the table ``t`` in insertion
|
|
## order. The values can be modified.
|
|
##
|
|
## See also:
|
|
## * `pairs iterator<#pairs.i,OrderedTableRef[A,B]>`_
|
|
## * `mvalues iterator<#mvalues.i,OrderedTableRef[A,B]>`_
|
|
runnableExamples:
|
|
let a = {
|
|
'o': @[1, 5, 7, 9],
|
|
'e': @[2, 4, 6, 8]
|
|
}.newOrderedTable
|
|
for k, v in a.mpairs:
|
|
v.add(v[0] + 10)
|
|
doAssert a == {'o': @[1, 5, 7, 9, 11],
|
|
'e': @[2, 4, 6, 8, 12]}.newOrderedTable
|
|
|
|
let L = len(t)
|
|
forAllOrderedPairs:
|
|
yield (t.data[h].key, t.data[h].val)
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
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
|
|
|
|
let L = len(t)
|
|
forAllOrderedPairs:
|
|
yield t.data[h].key
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
iterator values*[A, B](t: OrderedTableRef[A, B]): B =
|
|
## Iterates over any value in the table ``t`` in insertion order.
|
|
##
|
|
## See also:
|
|
## * `pairs iterator<#pairs.i,OrderedTableRef[A,B]>`_
|
|
## * `keys iterator<#keys.i,OrderedTableRef[A,B]>`_
|
|
## * `mvalues iterator<#mvalues.i,OrderedTableRef[A,B]>`_
|
|
runnableExamples:
|
|
let a = {
|
|
'o': @[1, 5, 7, 9],
|
|
'e': @[2, 4, 6, 8]
|
|
}.newOrderedTable
|
|
for v in a.values:
|
|
doAssert v.len == 4
|
|
|
|
let L = len(t)
|
|
forAllOrderedPairs:
|
|
yield t.data[h].val
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
iterator mvalues*[A, B](t: OrderedTableRef[A, B]): var B =
|
|
## Iterates over any value in the table ``t`` in insertion order. The values
|
|
## can be modified.
|
|
##
|
|
## See also:
|
|
## * `mpairs iterator<#mpairs.i,OrderedTableRef[A,B]>`_
|
|
## * `values iterator<#values.i,OrderedTableRef[A,B]>`_
|
|
runnableExamples:
|
|
let a = {
|
|
'o': @[1, 5, 7, 9],
|
|
'e': @[2, 4, 6, 8]
|
|
}.newOrderedTable
|
|
for v in a.mvalues:
|
|
v.add(99)
|
|
doAssert a == {'o': @[1, 5, 7, 9, 99],
|
|
'e': @[2, 4, 6, 8, 99]}.newOrderedTable
|
|
|
|
let L = len(t)
|
|
forAllOrderedPairs:
|
|
yield t.data[h].val
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
# -------------------------------------------------------------------------
|
|
# ------------------------------ CountTable -------------------------------
|
|
# -------------------------------------------------------------------------
|
|
|
|
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
|
|
countDeleted: int
|
|
isSorted: bool
|
|
CountTableRef*[A] = ref CountTable[A] ## Ref version of
|
|
## `CountTable<#CountTable>`_.
|
|
##
|
|
## For creating a new empty CountTableRef, use `newCountTable proc
|
|
## <#newCountTable,int>`_.
|
|
|
|
|
|
# ------------------------------ helpers ---------------------------------
|
|
|
|
proc ctRawInsert[A](t: CountTable[A], data: var seq[tuple[key: A, val: int]],
|
|
key: A, val: int) =
|
|
let hc = hash(key)
|
|
var perturb = t.getPerturb(hc)
|
|
var h: Hash = hc and high(data)
|
|
while data[h].val != 0: h = nextTry(h, high(data), perturb) # TODO: handle deletedMarker
|
|
data[h].key = key
|
|
data[h].val = val
|
|
|
|
proc enlarge[A](t: var CountTable[A]) =
|
|
var n: seq[tuple[key: A, val: int]]
|
|
newSeq(n, len(t.data) * growthFactor)
|
|
for i in countup(0, high(t.data)):
|
|
if t.data[i].val != 0: ctRawInsert(t, n, move t.data[i].key, move t.data[i].val)
|
|
swap(t.data, n)
|
|
|
|
proc remove[A](t: var CountTable[A], key: A) =
|
|
var n: seq[tuple[key: A, val: int]]
|
|
newSeq(n, len(t.data))
|
|
var removed: bool
|
|
for i in countup(0, high(t.data)):
|
|
if t.data[i].val != 0:
|
|
if t.data[i].key != key:
|
|
ctRawInsert(t, n, move t.data[i].key, move t.data[i].val)
|
|
else:
|
|
removed = true
|
|
swap(t.data, n)
|
|
if removed: dec(t.counter)
|
|
|
|
proc rawGet[A](t: CountTable[A], key: A): int =
|
|
if t.data.len == 0:
|
|
return -1
|
|
let hc = hash(key)
|
|
var perturb = t.getPerturb(hc)
|
|
var h: Hash = hc and high(t.data) # start with real hash value
|
|
while t.data[h].val != 0: # TODO: may need to handle t.data[h].hcode == deletedMarker?
|
|
if t.data[h].key == key: return h
|
|
h = nextTry(h, high(t.data), perturb)
|
|
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: Positive = 1)
|
|
|
|
# ----------------------------------------------------------------------
|
|
|
|
proc initCountTable*[A](initialSize = defaultInitialSize): 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.
|
|
##
|
|
## Starting from Nim v0.20, tables are initialized by default and it is
|
|
## not necessary to call this function explicitly.
|
|
##
|
|
## See also:
|
|
## * `toCountTable proc<#toCountTable,openArray[A]>`_
|
|
## * `newCountTable proc<#newCountTable,int>`_ for creating a
|
|
## `CountTableRef`
|
|
initImpl(result, initialSize)
|
|
|
|
proc toCountTable*[A](keys: openArray[A]): CountTable[A] =
|
|
## Creates a new count table with every member of a container ``keys``
|
|
## having a count of how many times it occurs in that container.
|
|
result = initCountTable[A](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
|
|
assert(not t.isSorted, "CountTable must not be used after sorting")
|
|
ctget(t, key, 0)
|
|
|
|
proc `[]=`*[A](t: var CountTable[A], key: A, val: int) =
|
|
## 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,Positive>`_ for incrementing a
|
|
## value of a key
|
|
assert(not t.isSorted, "CountTable must not be used after sorting")
|
|
assert val >= 0
|
|
if val == 0:
|
|
t.remove(key)
|
|
else:
|
|
let h = rawGet(t, key)
|
|
if h >= 0:
|
|
t.data[h].val = val
|
|
else:
|
|
insertImpl()
|
|
|
|
proc inc*[A](t: var CountTable[A], key: A, val: Positive = 1) =
|
|
## Increments ``t[key]`` by ``val`` (default: 1).
|
|
##
|
|
## ``val`` must be a positive number. If you need to decrement a value,
|
|
## use a regular ``Table`` instead.
|
|
runnableExamples:
|
|
var a = toCountTable("aab")
|
|
a.inc('a')
|
|
a.inc('b', 10)
|
|
doAssert a == toCountTable("aaabbbbbbbbbbb")
|
|
|
|
assert(not t.isSorted, "CountTable must not be used after sorting")
|
|
var index = rawGet(t, key)
|
|
if index >= 0:
|
|
inc(t.data[index].val, val)
|
|
if t.data[index].val == 0: dec(t.counter)
|
|
else:
|
|
insertImpl()
|
|
|
|
proc smallest*[A](t: CountTable[A]): tuple[key: A, val: int] =
|
|
## 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):
|
|
if t.data[h].val > 0 and (minIdx == -1 or t.data[minIdx].val > t.data[h].val):
|
|
minIdx = h
|
|
result.key = t.data[minIdx].key
|
|
result.val = t.data[minIdx].val
|
|
|
|
proc largest*[A](t: CountTable[A]): tuple[key: A, val: int] =
|
|
## Returns the ``(key, 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):
|
|
if t.data[maxIdx].val < t.data[h].val: maxIdx = h
|
|
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
|
|
assert(not t.isSorted, "CountTable must not be used after sorting")
|
|
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 del*[A](t: var CountTable[A], key: A) {.since: (1, 1).} =
|
|
## Deletes ``key`` from table ``t``. Does nothing if the key does not exist.
|
|
##
|
|
## O(n) complexity.
|
|
##
|
|
## See also:
|
|
## * `pop proc<#pop,CountTable[A],A,int>`_
|
|
## * `clear proc<#clear,CountTable[A]>`_ to empty the whole table
|
|
runnableExamples:
|
|
var a = toCountTable("aabbbccccc")
|
|
a.del('b')
|
|
assert a == toCountTable("aaccccc")
|
|
a.del('b')
|
|
assert a == toCountTable("aaccccc")
|
|
a.del('c')
|
|
assert a == toCountTable("aa")
|
|
|
|
remove(t, key)
|
|
|
|
proc pop*[A](t: var CountTable[A], key: A, val: var int): bool {.since: (1, 1).} =
|
|
## Deletes the ``key`` from the table.
|
|
## Returns ``true``, if the ``key`` existed, and sets ``val`` to the
|
|
## mapping of the key. Otherwise, returns ``false``, and the ``val`` is
|
|
## unchanged.
|
|
##
|
|
## O(n) complexity.
|
|
##
|
|
## See also:
|
|
## * `del proc<#del,CountTable[A],A>`_
|
|
## * `clear proc<#clear,CountTable[A]>`_ to empty the whole table
|
|
runnableExamples:
|
|
var a = toCountTable("aabbbccccc")
|
|
var i = 0
|
|
assert a.pop('b', i)
|
|
assert i == 3
|
|
i = 99
|
|
assert not a.pop('b', i)
|
|
assert i == 99
|
|
|
|
var index = rawGet(t, key)
|
|
result = index >= 0
|
|
if result:
|
|
val = move(t.data[index].val)
|
|
remove(t, key)
|
|
|
|
proc clear*[A](t: var CountTable[A]) =
|
|
## Resets the table so that it is empty.
|
|
##
|
|
## See also:
|
|
## * `del proc<#del,CountTable[A],A>`_
|
|
## * `pop proc<#pop,CountTable[A],A,int>`_
|
|
clearImpl()
|
|
t.isSorted = false
|
|
|
|
func ctCmp[T](a, b: tuple[key: T, val: int]): int =
|
|
result = system.cmp(a.val, b.val)
|
|
|
|
proc sort*[A](t: var CountTable[A], order = SortOrder.Descending) =
|
|
## Sorts the count table so that, by default, the entry with the
|
|
## highest counter comes first.
|
|
##
|
|
## **WARNING:** This is destructive! Once sorted, you must not modify ``t`` afterwards!
|
|
##
|
|
## You can use the iterators `pairs<#pairs.i,CountTable[A]>`_,
|
|
## `keys<#keys.i,CountTable[A]>`_, and `values<#values.i,CountTable[A]>`_
|
|
## to iterate over ``t`` in the sorted order.
|
|
runnableExamples:
|
|
import algorithm, sequtils
|
|
var a = toCountTable("abracadabra")
|
|
doAssert a == "aaaaabbrrcd".toCountTable
|
|
a.sort()
|
|
doAssert toSeq(a.values) == @[5, 2, 2, 1, 1]
|
|
a.sort(SortOrder.Ascending)
|
|
doAssert toSeq(a.values) == @[1, 1, 2, 2, 5]
|
|
|
|
t.data.sort(cmp = ctCmp, order = order)
|
|
t.isSorted = true
|
|
|
|
proc merge*[A](s: var CountTable[A], t: CountTable[A]) =
|
|
## Merges the second table into the first one (must be declared as `var`).
|
|
runnableExamples:
|
|
var a = toCountTable("aaabbc")
|
|
let b = toCountTable("bcc")
|
|
a.merge(b)
|
|
doAssert a == toCountTable("aaabbbccc")
|
|
|
|
assert(not s.isSorted, "CountTable must not be used after sorting")
|
|
for key, value in t:
|
|
s.inc(key, value)
|
|
|
|
when (NimMajor, NimMinor) <= (1, 0):
|
|
proc merge*[A](s, t: CountTable[A]): CountTable[A] =
|
|
## Merges the two tables into a new one.
|
|
runnableExamples:
|
|
let
|
|
a = toCountTable("aaabbc")
|
|
b = toCountTable("bcc")
|
|
doAssert merge(a, b) == toCountTable("aaabbbccc")
|
|
|
|
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
|
|
let L = len(t)
|
|
for h in 0 .. high(t.data):
|
|
if t.data[h].val != 0:
|
|
yield (t.data[h].key, t.data[h].val)
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
iterator mpairs*[A](t: var CountTable[A]): (A, var int) =
|
|
## Iterates over any ``(key, value)`` pair in the table ``t`` (must be
|
|
## declared as `var`). The values can be modified.
|
|
##
|
|
## See also:
|
|
## * `pairs iterator<#pairs.i,CountTable[A]>`_
|
|
## * `mvalues iterator<#mvalues.i,CountTable[A]>`_
|
|
runnableExamples:
|
|
var a = toCountTable("abracadabra")
|
|
for k, v in mpairs(a):
|
|
v = 2
|
|
doAssert a == toCountTable("aabbccddrr")
|
|
|
|
let L = len(t)
|
|
for h in 0 .. high(t.data):
|
|
if t.data[h].val != 0:
|
|
yield (t.data[h].key, t.data[h].val)
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
iterator keys*[A](t: CountTable[A]): A =
|
|
## Iterates over any key in the table ``t``.
|
|
##
|
|
## See also:
|
|
## * `pairs iterator<#pairs.i,CountTable[A]>`_
|
|
## * `values iterator<#values.i,CountTable[A]>`_
|
|
runnableExamples:
|
|
var a = toCountTable("abracadabra")
|
|
for k in keys(a):
|
|
a[k] = 2
|
|
doAssert a == toCountTable("aabbccddrr")
|
|
|
|
let L = len(t)
|
|
for h in 0 .. high(t.data):
|
|
if t.data[h].val != 0:
|
|
yield t.data[h].key
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
iterator values*[A](t: CountTable[A]): int =
|
|
## Iterates over any value in the table ``t``.
|
|
##
|
|
## See also:
|
|
## * `pairs iterator<#pairs.i,CountTable[A]>`_
|
|
## * `keys iterator<#keys.i,CountTable[A]>`_
|
|
## * `mvalues iterator<#mvalues.i,CountTable[A]>`_
|
|
runnableExamples:
|
|
let a = toCountTable("abracadabra")
|
|
for v in values(a):
|
|
assert v < 10
|
|
|
|
let L = len(t)
|
|
for h in 0 .. high(t.data):
|
|
if t.data[h].val != 0:
|
|
yield t.data[h].val
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
iterator mvalues*[A](t: var CountTable[A]): var int =
|
|
## Iterates over any value in the table ``t`` (must be
|
|
## declared as `var`). The values can be modified.
|
|
##
|
|
## See also:
|
|
## * `mpairs iterator<#mpairs.i,CountTable[A]>`_
|
|
## * `values iterator<#values.i,CountTable[A]>`_
|
|
runnableExamples:
|
|
var a = toCountTable("abracadabra")
|
|
for v in mvalues(a):
|
|
v = 2
|
|
doAssert a == toCountTable("aabbccddrr")
|
|
|
|
let L = len(t)
|
|
for h in 0 .. high(t.data):
|
|
if t.data[h].val != 0:
|
|
yield t.data[h].val
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
# ---------------------------------------------------------------------------
|
|
# ---------------------------- CountTableRef --------------------------------
|
|
# ---------------------------------------------------------------------------
|
|
|
|
proc inc*[A](t: CountTableRef[A], key: A, val = 1)
|
|
|
|
proc newCountTable*[A](initialSize = defaultInitialSize): <//>CountTableRef[A] =
|
|
## Creates a new ref count table that is empty.
|
|
##
|
|
## ``initialSize`` 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:
|
|
## * `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 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 `[]=`*[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 del*[A](t: CountTableRef[A], key: A) {.since: (1, 1).} =
|
|
## Deletes ``key`` from table ``t``. Does nothing if the key does not exist.
|
|
##
|
|
## O(n) complexity.
|
|
##
|
|
## See also:
|
|
## * `pop proc<#pop,CountTableRef[A],A,int>`_
|
|
## * `clear proc<#clear,CountTableRef[A]>`_ to empty the whole table
|
|
del(t[], key)
|
|
|
|
proc pop*[A](t: CountTableRef[A], key: A, val: var int): bool {.since: (1, 1).} =
|
|
## Deletes the ``key`` from the table.
|
|
## Returns ``true``, if the ``key`` existed, and sets ``val`` to the
|
|
## mapping of the key. Otherwise, returns ``false``, and the ``val`` is
|
|
## unchanged.
|
|
##
|
|
## O(n) complexity.
|
|
##
|
|
## See also:
|
|
## * `del proc<#del,CountTableRef[A],A>`_
|
|
## * `clear proc<#clear,CountTableRef[A]>`_ to empty the whole table
|
|
pop(t[], key, val)
|
|
|
|
proc clear*[A](t: CountTableRef[A]) =
|
|
## Resets the table so that it is empty.
|
|
##
|
|
## See also:
|
|
## * `del proc<#del,CountTableRef[A],A>`_
|
|
## * `pop proc<#pop,CountTableRef[A],A,int>`_
|
|
clear(t[])
|
|
|
|
proc sort*[A](t: CountTableRef[A], order = SortOrder.Descending) =
|
|
## Sorts the count table so that, by default, the entry with the
|
|
## highest counter comes first.
|
|
##
|
|
## **This is destructive! You must not modify `t` afterwards!**
|
|
##
|
|
## You can use the iterators `pairs<#pairs.i,CountTableRef[A]>`_,
|
|
## `keys<#keys.i,CountTableRef[A]>`_, and `values<#values.i,CountTableRef[A]>`_
|
|
## to iterate over ``t`` in the sorted order.
|
|
t[].sort(order = order)
|
|
|
|
proc merge*[A](s, t: CountTableRef[A]) =
|
|
## Merges the second table into the first one.
|
|
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. Used internally when calling `echo`
|
|
## on a table.
|
|
dollarImpl()
|
|
|
|
proc `==`*[A](s, t: CountTableRef[A]): bool =
|
|
## The ``==`` operator for count tables. Returns ``true`` if either both tables
|
|
## are ``nil``, or neither is ``nil`` and both contain the same keys with the same
|
|
## count. Insert order does not matter.
|
|
if isNil(s): result = isNil(t)
|
|
elif isNil(t): result = false
|
|
else: result = s[] == t[]
|
|
|
|
|
|
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
|
|
let L = len(t)
|
|
for h in 0 .. high(t.data):
|
|
if t.data[h].val != 0:
|
|
yield (t.data[h].key, t.data[h].val)
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
iterator mpairs*[A](t: CountTableRef[A]): (A, var int) =
|
|
## Iterates over any ``(key, value)`` pair in the table ``t``. The values can
|
|
## be modified.
|
|
##
|
|
## See also:
|
|
## * `pairs iterator<#pairs.i,CountTableRef[A]>`_
|
|
## * `mvalues iterator<#mvalues.i,CountTableRef[A]>`_
|
|
runnableExamples:
|
|
let a = newCountTable("abracadabra")
|
|
for k, v in mpairs(a):
|
|
v = 2
|
|
doAssert a == newCountTable("aabbccddrr")
|
|
|
|
let L = len(t)
|
|
for h in 0 .. high(t.data):
|
|
if t.data[h].val != 0:
|
|
yield (t.data[h].key, t.data[h].val)
|
|
assert(len(t) == L, "table modified while iterating over it")
|
|
|
|
iterator keys*[A](t: CountTableRef[A]): A =
|
|
## Iterates over any key in the table ``t``.
|
|
##
|
|
## See also:
|
|
## * `pairs iterator<#pairs.i,CountTable[A]>`_
|
|
## * `values iterator<#values.i,CountTable[A]>`_
|
|
runnableExamples:
|
|
let a = newCountTable("abracadabra")
|
|
for k in keys(a):
|
|
a[k] = 2
|
|
doAssert a == newCountTable("aabbccddrr")
|
|
|
|
let L = len(t)
|
|
for h in 0 .. high(t.data):
|
|
if t.data[h].val != 0:
|
|
yield t.data[h].key
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
iterator values*[A](t: CountTableRef[A]): int =
|
|
## Iterates over any value in the table ``t``.
|
|
##
|
|
## See also:
|
|
## * `pairs iterator<#pairs.i,CountTableRef[A]>`_
|
|
## * `keys iterator<#keys.i,CountTableRef[A]>`_
|
|
## * `mvalues iterator<#mvalues.i,CountTableRef[A]>`_
|
|
runnableExamples:
|
|
let a = newCountTable("abracadabra")
|
|
for v in values(a):
|
|
assert v < 10
|
|
|
|
let L = len(t)
|
|
for h in 0 .. high(t.data):
|
|
if t.data[h].val != 0:
|
|
yield t.data[h].val
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
iterator mvalues*[A](t: CountTableRef[A]): var int =
|
|
## Iterates over any value in the table ``t``. The values can be modified.
|
|
##
|
|
## See also:
|
|
## * `mpairs iterator<#mpairs.i,CountTableRef[A]>`_
|
|
## * `values iterator<#values.i,CountTableRef[A]>`_
|
|
runnableExamples:
|
|
var a = newCountTable("abracadabra")
|
|
for v in mvalues(a):
|
|
v = 2
|
|
doAssert a == newCountTable("aabbccddrr")
|
|
|
|
let L = len(t)
|
|
for h in 0 .. high(t.data):
|
|
if t.data[h].val != 0:
|
|
yield t.data[h].val
|
|
assert(len(t) == L, "the length of the table changed while iterating over it")
|
|
|
|
|
|
|
|
|
|
when isMainModule:
|
|
type
|
|
Person = object
|
|
firstName, lastName: string
|
|
|
|
proc hash(x: Person): Hash =
|
|
## Piggyback on the already available string hash proc.
|
|
##
|
|
## Without this proc nothing works!
|
|
result = x.firstName.hash !& x.lastName.hash
|
|
result = !$result
|
|
|
|
var
|
|
salaries = initTable[Person, int]()
|
|
p1, p2: Person
|
|
p1.firstName = "Jon"
|
|
p1.lastName = "Ross"
|
|
salaries[p1] = 30_000
|
|
p2.firstName = "소진"
|
|
p2.lastName = "박"
|
|
salaries[p2] = 45_000
|
|
var
|
|
s2 = initOrderedTable[Person, int]()
|
|
s3 = initCountTable[Person]()
|
|
s2[p1] = 30_000
|
|
s2[p2] = 45_000
|
|
s3[p1] = 30_000
|
|
s3[p2] = 45_000
|
|
|
|
block: # Ordered table should preserve order after deletion
|
|
var
|
|
s4 = initOrderedTable[int, int]()
|
|
s4[1] = 1
|
|
s4[2] = 2
|
|
s4[3] = 3
|
|
|
|
var prev = 0
|
|
for i in s4.values:
|
|
doAssert(prev < i)
|
|
prev = i
|
|
|
|
s4.del(2)
|
|
doAssert(2 notin s4)
|
|
doAssert(s4.len == 2)
|
|
prev = 0
|
|
for i in s4.values:
|
|
doAssert(prev < i)
|
|
prev = i
|
|
|
|
block: # Deletion from OrderedTable should account for collision groups. See issue #5057.
|
|
# The bug is reproducible only with exact keys
|
|
const key1 = "boy_jackpot.inGamma"
|
|
const key2 = "boy_jackpot.outBlack"
|
|
|
|
var t = {
|
|
key1: 0,
|
|
key2: 0
|
|
}.toOrderedTable()
|
|
|
|
t.del(key1)
|
|
assert(t.len == 1)
|
|
assert(key2 in t)
|
|
|
|
var
|
|
t1 = initCountTable[string]()
|
|
t2 = initCountTable[string]()
|
|
t1.inc("foo")
|
|
t1.inc("bar", 2)
|
|
t1.inc("baz", 3)
|
|
t2.inc("foo", 4)
|
|
t2.inc("bar")
|
|
t2.inc("baz", 11)
|
|
merge(t1, t2)
|
|
assert(t1["foo"] == 5)
|
|
assert(t1["bar"] == 3)
|
|
assert(t1["baz"] == 14)
|
|
|
|
let
|
|
t1r = newCountTable[string]()
|
|
t2r = newCountTable[string]()
|
|
t1r.inc("foo")
|
|
t1r.inc("bar", 2)
|
|
t1r.inc("baz", 3)
|
|
t2r.inc("foo", 4)
|
|
t2r.inc("bar")
|
|
t2r.inc("baz", 11)
|
|
merge(t1r, t2r)
|
|
assert(t1r["foo"] == 5)
|
|
assert(t1r["bar"] == 3)
|
|
assert(t1r["baz"] == 14)
|
|
|
|
var
|
|
t1l = initCountTable[string]()
|
|
t2l = initCountTable[string]()
|
|
t1l.inc("foo")
|
|
t1l.inc("bar", 2)
|
|
t1l.inc("baz", 3)
|
|
t2l.inc("foo", 4)
|
|
t2l.inc("bar")
|
|
t2l.inc("baz", 11)
|
|
|
|
block:
|
|
const testKey = "TESTKEY"
|
|
let t: CountTableRef[string] = newCountTable[string]()
|
|
|
|
# Before, does not compile with error message:
|
|
#test_counttable.nim(7, 43) template/generic instantiation from here
|
|
#lib/pure/collections/tables.nim(117, 21) template/generic instantiation from here
|
|
#lib/pure/collections/tableimpl.nim(32, 27) Error: undeclared field: 'hcode
|
|
doAssert 0 == t[testKey]
|
|
t.inc(testKey, 3)
|
|
doAssert 3 == t[testKey]
|
|
|
|
block:
|
|
# Clear tests
|
|
var clearTable = newTable[int, string]()
|
|
clearTable[42] = "asd"
|
|
clearTable[123123] = "piuyqwb "
|
|
doAssert clearTable[42] == "asd"
|
|
clearTable.clear()
|
|
doAssert(not clearTable.hasKey(123123))
|
|
doAssert clearTable.getOrDefault(42) == ""
|
|
|
|
block: #5482
|
|
var a = [("wrong?", "foo"), ("wrong?", "foo2")].newOrderedTable()
|
|
var b = newOrderedTable[string, string](initialSize = 2)
|
|
b.add("wrong?", "foo")
|
|
b.add("wrong?", "foo2")
|
|
assert a == b
|
|
|
|
block: #5482
|
|
var a = {"wrong?": "foo", "wrong?": "foo2"}.newOrderedTable()
|
|
var b = newOrderedTable[string, string](initialSize = 2)
|
|
b.add("wrong?", "foo")
|
|
b.add("wrong?", "foo2")
|
|
assert a == b
|
|
|
|
block: #5487
|
|
var a = {"wrong?": "foo", "wrong?": "foo2"}.newOrderedTable()
|
|
var b = newOrderedTable[string, string]() # notice, default size!
|
|
b.add("wrong?", "foo")
|
|
b.add("wrong?", "foo2")
|
|
assert a == b
|
|
|
|
block: #5487
|
|
var a = [("wrong?", "foo"), ("wrong?", "foo2")].newOrderedTable()
|
|
var b = newOrderedTable[string, string]() # notice, default size!
|
|
b.add("wrong?", "foo")
|
|
b.add("wrong?", "foo2")
|
|
assert a == b
|
|
|
|
block:
|
|
var a = {"wrong?": "foo", "wrong?": "foo2"}.newOrderedTable()
|
|
var b = [("wrong?", "foo"), ("wrong?", "foo2")].newOrderedTable()
|
|
var c = newOrderedTable[string, string]() # notice, default size!
|
|
c.add("wrong?", "foo")
|
|
c.add("wrong?", "foo2")
|
|
assert a == b
|
|
assert a == c
|
|
|
|
block: #6250
|
|
let
|
|
a = {3: 1}.toOrderedTable
|
|
b = {3: 2}.toOrderedTable
|
|
assert((a == b) == false)
|
|
assert((b == a) == false)
|
|
|
|
block: #6250
|
|
let
|
|
a = {3: 2}.toOrderedTable
|
|
b = {3: 2}.toOrderedTable
|
|
assert((a == b) == true)
|
|
assert((b == a) == true)
|
|
|
|
block: # CountTable.smallest
|
|
let t = toCountTable([0, 0, 5, 5, 5])
|
|
doAssert t.smallest == (0, 2)
|
|
|
|
block: #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: #12813 #13079
|
|
var t = toCountTable("abracadabra")
|
|
doAssert len(t) == 5
|
|
|
|
t['a'] = 0 # remove a key
|
|
doAssert len(t) == 4
|
|
|
|
block:
|
|
var tp: Table[string, string] = initTable[string, string]()
|
|
doAssert "test1" == tp.getOrDefault("test1", "test1")
|
|
tp["test2"] = "test2"
|
|
doAssert "test2" == tp.getOrDefault("test2", "test1")
|
|
var tr: TableRef[string, string] = newTable[string, string]()
|
|
doAssert "test1" == tr.getOrDefault("test1", "test1")
|
|
tr["test2"] = "test2"
|
|
doAssert "test2" == tr.getOrDefault("test2", "test1")
|
|
var op: OrderedTable[string, string] = initOrderedTable[string, string]()
|
|
doAssert "test1" == op.getOrDefault("test1", "test1")
|
|
op["test2"] = "test2"
|
|
doAssert "test2" == op.getOrDefault("test2", "test1")
|
|
var orf: OrderedTableRef[string, string] = newOrderedTable[string, string]()
|
|
doAssert "test1" == orf.getOrDefault("test1", "test1")
|
|
orf["test2"] = "test2"
|
|
doAssert "test2" == orf.getOrDefault("test2", "test1")
|
|
|
|
block tableWithoutInit:
|
|
var
|
|
a: Table[string, int]
|
|
b: Table[string, int]
|
|
c: Table[string, int]
|
|
d: Table[string, int]
|
|
e: Table[string, int]
|
|
|
|
a["a"] = 7
|
|
doAssert a.hasKey("a")
|
|
doAssert a.len == 1
|
|
doAssert a["a"] == 7
|
|
a["a"] = 9
|
|
doAssert a.len == 1
|
|
doAssert a["a"] == 9
|
|
|
|
doAssert b.hasKeyOrPut("b", 5) == false
|
|
doAssert b.hasKey("b")
|
|
doAssert b.hasKeyOrPut("b", 8)
|
|
doAssert b["b"] == 5
|
|
|
|
doAssert c.getOrDefault("a") == 0
|
|
doAssert c.getOrDefault("a", 3) == 3
|
|
c["a"] = 6
|
|
doAssert c.getOrDefault("a", 3) == 6
|
|
|
|
doAssert d.mgetOrPut("a", 3) == 3
|
|
doAssert d.mgetOrPut("a", 6) == 3
|
|
|
|
var x = 99
|
|
doAssert e.pop("a", x) == false
|
|
doAssert x == 99
|
|
e["a"] = 77
|
|
doAssert e.pop("a", x)
|
|
doAssert x == 77
|
|
|
|
block orderedTableWithoutInit:
|
|
var
|
|
a: OrderedTable[string, int]
|
|
b: OrderedTable[string, int]
|
|
c: OrderedTable[string, int]
|
|
d: OrderedTable[string, int]
|
|
|
|
a["a"] = 7
|
|
doAssert a.hasKey("a")
|
|
doAssert a.len == 1
|
|
doAssert a["a"] == 7
|
|
a["a"] = 9
|
|
doAssert a.len == 1
|
|
doAssert a["a"] == 9
|
|
|
|
doAssert b.hasKeyOrPut("b", 5) == false
|
|
doAssert b.hasKey("b")
|
|
doAssert b.hasKeyOrPut("b", 8)
|
|
doAssert b["b"] == 5
|
|
|
|
doAssert c.getOrDefault("a") == 0
|
|
doAssert c.getOrDefault("a", 3) == 3
|
|
c["a"] = 6
|
|
doAssert c.getOrDefault("a", 3) == 6
|
|
|
|
doAssert d.mgetOrPut("a", 3) == 3
|
|
doAssert d.mgetOrPut("a", 6) == 3
|
|
|
|
block countTableWithoutInit:
|
|
var
|
|
a: CountTable[string]
|
|
b: CountTable[string]
|
|
c: CountTable[string]
|
|
d: CountTable[string]
|
|
e: CountTable[string]
|
|
|
|
a["a"] = 7
|
|
doAssert a.hasKey("a")
|
|
doAssert a.len == 1
|
|
doAssert a["a"] == 7
|
|
a["a"] = 9
|
|
doAssert a.len == 1
|
|
doAssert a["a"] == 9
|
|
|
|
doAssert b["b"] == 0
|
|
b.inc("b")
|
|
doAssert b["b"] == 1
|
|
|
|
doAssert c.getOrDefault("a") == 0
|
|
doAssert c.getOrDefault("a", 3) == 3
|
|
c["a"] = 6
|
|
doAssert c.getOrDefault("a", 3) == 6
|
|
|
|
e["f"] = 3
|
|
merge(d, e)
|
|
doAssert d.hasKey("f")
|
|
d.inc("f")
|
|
merge(d, e)
|
|
doAssert d["f"] == 7
|