Module tables

Search:
Group by:

The tables module implements variants of an efficient hash table (also often named dictionary in other programming languages) that is a mapping from keys to values. Table is the usual hash table, OrderedTable is like Table but remembers insertion order and CountTable is a mapping from a key to its number of occurrences. For consistency with every other data type in Nim these have value semantics, this means that = performs a copy of the hash table. For reference semantics use the Ref variant: TableRef, OrderedTableRef, CountTableRef. To give an example, when a is a Table, then var b = a gives b as a new independent table. b is initialised with the contents of a. Changing b does not affect a and vice versa:

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 reference the same data structure:

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

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 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:

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
An include file for the different table implementations.

Types

Table[A, B] = object
  data: KeyValuePairSeq[A, B]
  counter: int
generic hash table   Source Edit
TableRef[A, B] = ref Table[A, B]
  Source Edit
OrderedTable[A, B] = object
  data: OrderedKeyValuePairSeq[A, B]
  counter, first, last: int
table that remembers insertion order   Source Edit
OrderedTableRef[A, B] = ref OrderedTable[A, B]
  Source Edit
CountTable[A] = object
  data: seq[tuple[key: A, val: int]]
  counter: int
table that counts the number of each key   Source Edit
CountTableRef[A] = ref CountTable[A]
  Source Edit

Procs

proc clear[A, B](t: var Table[A, B])
Resets the table so that it is empty.   Source Edit
proc clear[A, B](t: TableRef[A, B])
Resets the table so that it is empty.   Source Edit
proc rightSize(count: Natural): int {.
inline, raises: [], tags: []
.}

Return the value of initialSize to support count items.

If more items are expected to be added, simply add that expected extra amount to the parameter before calling this.

Internally, we want mustRehash(rightSize(x), x) == false.

  Source Edit
proc len[A, B](t: Table[A, B]): int
returns the number of keys in t.   Source Edit
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 whether the key exists.   Source Edit
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.   Source Edit
proc mget[A, B](t: var Table[A, B]; key: A): var B {.
deprecated
.}
retrieves the value at t[key]. The value can be modified. If key is not in t, the KeyError exception is raised. Use ```[]``` instead.   Source Edit
proc getOrDefault[A, B](t: Table[A, B]; key: A): B
  Source Edit
proc hasKey[A, B](t: Table[A, B]; key: A): bool
returns true iff key is in the table t.   Source Edit
proc contains[A, B](t: Table[A, B]; key: A): bool
alias of hasKey for use with the in operator.   Source Edit
proc del[A, B](t: var Table[A, B]; key: A)
deletes key from hash table t.   Source Edit
proc take[A, B](t: var Table[A, B]; key: A; val: var B): bool
Deletes the key from the table. Returns true, if the key existed, and sets val to the mapping of the key. Otherwise, returns false, and the val is unchanged.   Source Edit
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.   Source Edit
proc hasKeyOrPut[A, B](t: var Table[A, B]; key: A; val: B): bool
returns true iff key is in the table, otherwise inserts value.   Source Edit
proc `[]=`[A, B](t: var Table[A, B]; key: A; val: B)
puts a (key, value)-pair into t.   Source Edit
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.   Source Edit
proc len[A, B](t: TableRef[A, B]): int
returns the number of keys in t.   Source Edit
proc initTable[A, B](initialSize = 64): Table[A, B]

creates a new hash table that is empty.

initialSize needs to be a power of two. If you need to accept runtime values for this you could use the nextPowerOfTwo proc from the math module or the rightSize proc from this module.

  Source Edit
proc toTable[A, B](pairs: openArray[(A, B)]): Table[A, B]
creates a new hash table that contains the given pairs.   Source Edit
proc `$`[A, B](t: Table[A, B]): string
The $ operator for hash tables.   Source Edit
proc hasKey[A, B](t: TableRef[A, B]; key: A): bool
returns true iff key is in the table t.   Source Edit
proc `==`[A, B](s, t: Table[A, B]): bool
The == operator for hash tables. Returns true iff the content of both tables contains the same key-value pairs. Insert order does not matter.   Source Edit
proc indexBy[A, B, C](collection: A; index: proc (x: B): C): Table[C, B]
Index the collection with the proc provided.   Source Edit
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 whether the key exists.   Source Edit
proc mget[A, B](t: TableRef[A, B]; key: A): var B {.
deprecated
.}
retrieves the value at t[key]. The value can be modified. If key is not in t, the KeyError exception is raised. Use ```[]``` instead.   Source Edit
proc getOrDefault[A, B](t: TableRef[A, B]; key: A): B
  Source Edit
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.   Source Edit
proc hasKeyOrPut[A, B](t: var TableRef[A, B]; key: A; val: B): bool
returns true iff key is in the table, otherwise inserts value.   Source Edit
proc contains[A, B](t: TableRef[A, B]; key: A): bool
alias of hasKey for use with the in operator.   Source Edit
proc `[]=`[A, B](t: TableRef[A, B]; key: A; val: B)
puts a (key, value)-pair into t.   Source Edit
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.   Source Edit
proc del[A, B](t: TableRef[A, B]; key: A)
deletes key from hash table t.   Source Edit
proc take[A, B](t: TableRef[A, B]; key: A; val: var B): bool
Deletes the key from the table. Returns true, if the key existed, and sets val to the mapping of the key. Otherwise, returns false, and the val is unchanged.   Source Edit
proc newTable[A, B](initialSize = 64): TableRef[A, B]
  Source Edit
proc newTable[A, B](pairs: openArray[(A, B)]): TableRef[A, B]
creates a new hash table that contains the given pairs.   Source Edit
proc `$`[A, B](t: TableRef[A, B]): string
The $ operator for hash tables.   Source Edit
proc `==`[A, B](s, t: TableRef[A, B]): bool
The == operator for hash tables. Returns true iff either both tables are nil or none is nil and the content of both tables contains the same key-value pairs. Insert order does not matter.   Source Edit
proc newTableFrom[A, B, C](collection: A; index: proc (x: B): C): TableRef[C, B]
Index the collection with the proc provided.   Source Edit
proc len[A, B](t: OrderedTable[A, B]): int {.
inline
.}
returns the number of keys in t.   Source Edit
proc clear[A, B](t: var OrderedTable[A, B])
Resets the table so that it is empty.   Source Edit
proc clear[A, B](t: var OrderedTableRef[A, B])
Resets the table so that is is empty.   Source Edit
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 whether the key exists.   Source Edit
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.   Source Edit
proc mget[A, B](t: var OrderedTable[A, B]; key: A): var B {.
deprecated
.}
retrieves the value at t[key]. The value can be modified. If key is not in t, the KeyError exception is raised. Use ```[]``` instead.   Source Edit
proc getOrDefault[A, B](t: OrderedTable[A, B]; key: A): B
  Source Edit
proc hasKey[A, B](t: OrderedTable[A, B]; key: A): bool
returns true iff key is in the table t.   Source Edit
proc contains[A, B](t: OrderedTable[A, B]; key: A): bool
alias of hasKey for use with the in operator.   Source Edit
proc `[]=`[A, B](t: var OrderedTable[A, B]; key: A; val: B)
puts a (key, value)-pair into t.   Source Edit
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.   Source Edit
proc mgetOrPut[A, B](t: var OrderedTable[A, B]; key: A; val: B): var B
retrieves value at t[key] or puts value if not present, either way returning a value which can be modified.   Source Edit
proc hasKeyOrPut[A, B](t: var OrderedTable[A, B]; key: A; val: B): bool
returns true iff key is in the table, otherwise inserts value.   Source Edit
proc initOrderedTable[A, B](initialSize = 64): OrderedTable[A, B]

creates a new ordered hash table that is empty.

initialSize needs to be a power of two. If you need to accept runtime values for this you could use the nextPowerOfTwo proc from the math module or the rightSize proc from this module.

  Source Edit
proc toOrderedTable[A, B](pairs: openArray[(A, B)]): OrderedTable[A, B]
creates a new ordered hash table that contains the given pairs.   Source Edit
proc `$`[A, B](t: OrderedTable[A, B]): string
The $ operator for ordered hash tables.   Source Edit
proc `==`[A, B](s, t: OrderedTable[A, B]): bool
The == operator for ordered hash tables. Returns true iff both the content and the order are equal.   Source Edit
proc sort[A, B](t: var OrderedTable[A, B]; cmp: proc (x, y: (A, B)): int)
sorts t according to cmp. This modifies the internal list that kept the insertion order, so insertion order is lost after this call but key lookup and insertions remain possible after sort (in contrast to the sort for count tables).   Source Edit
proc len[A, B](t: OrderedTableRef[A, B]): int {.
inline
.}
returns the number of keys in t.   Source Edit
proc `[]`[A, B](t: OrderedTableRef[A, B]; key: A): var B
retrieves the value at t[key]. If key is not in t, the KeyError exception is raised. One can check with hasKey whether the key exists.   Source Edit
proc mget[A, B](t: OrderedTableRef[A, B]; key: A): var B {.
deprecated
.}
retrieves the value at t[key]. The value can be modified. If key is not in t, the KeyError exception is raised. Use ```[]``` instead.   Source Edit
proc getOrDefault[A, B](t: OrderedTableRef[A, B]; key: A): B
  Source Edit
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.   Source Edit
proc hasKeyOrPut[A, B](t: var OrderedTableRef[A, B]; key: A; val: B): bool
returns true iff key is in the table, otherwise inserts val.   Source Edit
proc hasKey[A, B](t: OrderedTableRef[A, B]; key: A): bool
returns true iff key is in the table t.   Source Edit
proc contains[A, B](t: OrderedTableRef[A, B]; key: A): bool
alias of hasKey for use with the in operator.   Source Edit
proc `[]=`[A, B](t: OrderedTableRef[A, B]; key: A; val: B)
puts a (key, value)-pair into t.   Source Edit
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.   Source Edit
proc newOrderedTable[A, B](initialSize = 64): OrderedTableRef[A, B]

creates a new ordered hash table that is empty.

initialSize needs to be a power of two. If you need to accept runtime values for this you could use the nextPowerOfTwo proc from the math module or the rightSize proc from this module.

  Source Edit
proc newOrderedTable[A, B](pairs: openArray[(A, B)]): OrderedTableRef[A, B]
creates a new ordered hash table that contains the given pairs.   Source Edit
proc `$`[A, B](t: OrderedTableRef[A, B]): string
The $ operator for ordered hash tables.   Source Edit
proc `==`[A, B](s, t: OrderedTableRef[A, B]): bool
The == operator for ordered hash tables. Returns true iff either both tables are nil or none is nil and the content and the order of both are equal.   Source Edit
proc sort[A, B](t: OrderedTableRef[A, B]; cmp: proc (x, y: (A, B)): int)
sorts t according to cmp. This modifies the internal list that kept the insertion order, so insertion order is lost after this call but key lookup and insertions remain possible after sort (in contrast to the sort for count tables).   Source Edit
proc del[A, B](t: var OrderedTable[A, B]; key: A)
deletes key from ordered hash table t. O(n) complexity.   Source Edit
proc del[A, B](t: var OrderedTableRef[A, B]; key: A)
deletes key from ordered hash table t. O(n) complexity.   Source Edit
proc len[A](t: CountTable[A]): int
returns the number of keys in t.   Source Edit
proc clear[A](t: CountTableRef[A])
Resets the table so that it is empty.   Source Edit
proc clear[A](t: var CountTable[A])
Resets the table so that it is empty.   Source Edit
proc `[]`[A](t: CountTable[A]; key: A): int {.
.}
retrieves the value at t[key]. If key is not in t, the KeyError exception is raised. One can check with hasKey whether the key exists.   Source Edit
proc `[]`[A](t: var CountTable[A]; key: A): var int {.
.}
retrieves the value at t[key]. The value can be modified. If key is not in t, the KeyError exception is raised.   Source Edit
proc mget[A](t: var CountTable[A]; key: A): var int {.
deprecated
.}
retrieves the value at t[key]. The value can be modified. If key is not in t, the KeyError exception is raised. Use ```[]``` instead.   Source Edit
proc getOrDefault[A](t: CountTable[A]; key: A): int
  Source Edit
proc hasKey[A](t: CountTable[A]; key: A): bool
returns true iff key is in the table t.   Source Edit
proc contains[A](t: CountTable[A]; key: A): bool
alias of hasKey for use with the in operator.   Source Edit
proc `[]=`[A](t: var CountTable[A]; key: A; val: int)
puts a (key, value)-pair into t.   Source Edit
proc initCountTable[A](initialSize = 64): CountTable[A]

creates a new count table that is empty.

initialSize needs to be a power of two. If you need to accept runtime values for this you could use the nextPowerOfTwo proc from the math module or the rightSize proc in this module.

  Source Edit
proc toCountTable[A](keys: openArray[A]): CountTable[A]
creates a new count table with every key in keys having a count of 1.   Source Edit
proc `$`[A](t: CountTable[A]): string
The $ operator for count tables.   Source Edit
proc `==`[A](s, t: CountTable[A]): bool
The == operator for count tables. Returns true iff both tables contain the same keys with the same count. Insert order does not matter.   Source Edit
proc inc[A](t: var CountTable[A]; key: A; val = 1)
increments t[key] by val.   Source Edit
proc smallest[A](t: CountTable[A]): tuple[key: A, val: int]
returns the (key,val)-pair with the smallest val. Efficiency: O(n)   Source Edit
proc largest[A](t: CountTable[A]): tuple[key: A, val: int]
returns the (key,val)-pair with the largest val. Efficiency: O(n)   Source Edit
proc sort[A](t: var CountTable[A])
sorts the count table so that the entry with the highest counter comes first. This is destructive! You must not modify t afterwards! You can use the iterators pairs, keys, and values to iterate over t in the sorted order.   Source Edit
proc len[A](t: CountTableRef[A]): int
returns the number of keys in t.   Source Edit
proc `[]`[A](t: CountTableRef[A]; key: A): var int {.
.}
retrieves the value at t[key]. The value can be modified. If key is not in t, the KeyError exception is raised.   Source Edit
proc mget[A](t: CountTableRef[A]; key: A): var int {.
deprecated
.}
retrieves the value at t[key]. The value can be modified. If key is not in t, the KeyError exception is raised. Use ```[]``` instead.   Source Edit
proc getOrDefault[A](t: CountTableRef[A]; key: A): int
  Source Edit
proc hasKey[A](t: CountTableRef[A]; key: A): bool
returns true iff key is in the table t.   Source Edit
proc contains[A](t: CountTableRef[A]; key: A): bool
alias of hasKey for use with the in operator.   Source Edit
proc `[]=`[A](t: CountTableRef[A]; key: A; val: int)
puts a (key, value)-pair into t. val has to be positive.   Source Edit
proc newCountTable[A](initialSize = 64): CountTableRef[A]

creates a new count table that is empty.

initialSize needs to be a power of two. If you need to accept runtime values for this you could use the nextPowerOfTwo proc from the math module or the rightSize method in this module.

  Source Edit
proc newCountTable[A](keys: openArray[A]): CountTableRef[A]
creates a new count table with every key in keys having a count of 1.   Source Edit
proc `$`[A](t: CountTableRef[A]): string
The $ operator for count tables.   Source Edit
proc `==`[A](s, t: CountTableRef[A]): bool
The == operator for count tables. Returns true iff either both tables are nil or none is nil and both contain the same keys with the same count. Insert order does not matter.   Source Edit
proc inc[A](t: CountTableRef[A]; key: A; val = 1)
increments t[key] by val.   Source Edit
proc smallest[A](t: CountTableRef[A]): (A, int)
returns the (key,val)-pair with the smallest val. Efficiency: O(n)   Source Edit
proc largest[A](t: CountTableRef[A]): (A, int)
returns the (key,val)-pair with the largest val. Efficiency: O(n)   Source Edit
proc sort[A](t: CountTableRef[A])
sorts the count table so that the entry with the highest counter comes first. This is destructive! You must not modify t afterwards! You can use the iterators pairs, keys, and values to iterate over t in the sorted order.   Source Edit
proc merge[A](s: var CountTable[A]; t: CountTable[A])
merges the second table into the first one   Source Edit
proc merge[A](s, t: CountTable[A]): CountTable[A]
merges the two tables into a new one   Source Edit
proc merge[A](s, t: CountTableRef[A])
merges the second table into the first one   Source Edit

Iterators

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.   Source Edit
iterator pairs[A, B](t: Table[A, B]): (A, B)
iterates over any (key, value) pair in the table t.   Source Edit
iterator mpairs[A, B](t: var Table[A, B]): (A, var B)
iterates over any (key, value) pair in the table t. The values can be modified.   Source Edit
iterator keys[A, B](t: Table[A, B]): A
iterates over any key in the table t.   Source Edit
iterator values[A, B](t: Table[A, B]): B
iterates over any value in the table t.   Source Edit
iterator mvalues[A, B](t: var Table[A, B]): var B
iterates over any value in the table t. The values can be modified.   Source Edit
iterator pairs[A, B](t: TableRef[A, B]): (A, B)
iterates over any (key, value) pair in the table t.   Source Edit
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.   Source Edit
iterator keys[A, B](t: TableRef[A, B]): A
iterates over any key in the table t.   Source Edit
iterator values[A, B](t: TableRef[A, B]): B
iterates over any value in the table t.   Source Edit
iterator mvalues[A, B](t: TableRef[A, B]): var B
iterates over any value in the table t. The values can be modified.   Source Edit
iterator pairs[A, B](t: OrderedTable[A, B]): (A, B)
iterates over any (key, value) pair in the table t in insertion order.   Source Edit
iterator mpairs[A, B](t: var OrderedTable[A, B]): (A, var B)
iterates over any (key, value) pair in the table t in insertion order. The values can be modified.   Source Edit
iterator keys[A, B](t: OrderedTable[A, B]): A
iterates over any key in the table t in insertion order.   Source Edit
iterator values[A, B](t: OrderedTable[A, B]): B
iterates over any value in the table t in insertion order.   Source Edit
iterator mvalues[A, B](t: var OrderedTable[A, B]): var B
iterates over any value in the table t in insertion order. The values can be modified.   Source Edit
iterator pairs[A, B](t: OrderedTableRef[A, B]): (A, B)
iterates over any (key, value) pair in the table t in insertion order.   Source Edit
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.   Source Edit
iterator keys[A, B](t: OrderedTableRef[A, B]): A
iterates over any key in the table t in insertion order.   Source Edit
iterator values[A, B](t: OrderedTableRef[A, B]): B
iterates over any value in the table t in insertion order.   Source Edit
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.   Source Edit
iterator pairs[A](t: CountTable[A]): (A, int)
iterates over any (key, value) pair in the table t.   Source Edit
iterator mpairs[A](t: var CountTable[A]): (A, var int)
iterates over any (key, value) pair in the table t. The values can be modified.   Source Edit
iterator keys[A](t: CountTable[A]): A
iterates over any key in the table t.   Source Edit
iterator values[A](t: CountTable[A]): int
iterates over any value in the table t.   Source Edit
iterator mvalues[A](t: CountTable[A]): var int
iterates over any value in the table t. The values can be modified.   Source Edit
iterator pairs[A](t: CountTableRef[A]): (A, int)
iterates over any (key, value) pair in the table t.   Source Edit
iterator mpairs[A](t: CountTableRef[A]): (A, var int)
iterates over any (key, value) pair in the table t. The values can be modified.   Source Edit
iterator keys[A](t: CountTableRef[A]): A
iterates over any key in the table t.   Source Edit
iterator values[A](t: CountTableRef[A]): int
iterates over any value in the table t.   Source Edit
iterator mvalues[A](t: CountTableRef[A]): var int
iterates over any value in the table t. The values can be modified.   Source Edit

Templates

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.
sharedTable.withValue(key, value) do:
  # block is executed only if ``key`` in ``t``
  value.name = "username"
  value.uid = 1000
  Source Edit
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.
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")
  Source Edit