Module tables

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.

Imports

hashes, math

Types

Table[A; B] = object
  data: KeyValuePairSeq[A, B]
  counter: int

generic hash table

TableRef[A; B] = ref Table[A, B]

OrderedTable[A; B] = object
  data: OrderedKeyValuePairSeq[A, B]
  counter, first, last: int

table that remembers insertion order

OrderedTableRef[A; B] = ref OrderedTable[A, B]

CountTable[A] = object
  data: seq[tuple[key: A, val: int]]
  counter: int

table that counts the number of each key

CountTableRef[A] = ref CountTable[A]

Procs

proc clear[A, B](t: var Table[A, B])

Resets the table so that it is empty.

proc clear[A, B](t: TableRef[A, B])

Resets the table so that it is empty.

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.

proc len[A, B](t: Table[A, B]): int

returns the number of keys in t.

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.

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.

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.

proc getOrDefault[A, B](t: Table[A, B]; key: A): B

proc hasKey[A, B](t: Table[A, B]; key: A): bool

returns true iff key is in the table t.

proc contains[A, B](t: Table[A, B]; key: A): bool

alias of hasKey for use with the in operator.

proc del[A, B](t: var Table[A, B]; key: A)

deletes key from hash table t.

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.

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.

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.

proc `[]=`[A, B](t: var Table[A, B]; key: A; val: B)

puts a (key, value)-pair into t.

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.

proc len[A, B](t: TableRef[A, B]): int

returns the number of keys in t.

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.

proc toTable[A, B](pairs: openArray[(A, B)]): Table[A, B]

creates a new hash table that contains the given pairs.

proc `$`[A, B](t: Table[A, B]): string

The $ operator for hash tables.

proc hasKey[A, B](t: TableRef[A, B]; key: A): bool

returns true iff key is in the table t.

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.

proc indexBy[A, B, C](collection: A; index: proc (x: B): C): Table[C, B]

Index the collection with the proc provided.

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.

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.

proc getOrDefault[A, B](t: TableRef[A, B]; key: A): B

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.

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.

proc contains[A, B](t: TableRef[A, B]; key: A): bool

alias of hasKey for use with the in operator.

proc `[]=`[A, B](t: TableRef[A, B]; key: A; val: B)

puts a (key, value)-pair into t.

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.

proc del[A, B](t: TableRef[A, B]; key: A)

deletes key from hash table t.

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.

proc newTable[A, B](initialSize = 64): TableRef[A, B]

proc newTable[A, B](pairs: openArray[(A, B)]): TableRef[A, B]

creates a new hash table that contains the given pairs.

proc `$`[A, B](t: TableRef[A, B]): string

The $ operator for hash tables.

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.

proc newTableFrom[A, B, C](collection: A; index: proc (x: B): C): TableRef[C, B]

Index the collection with the proc provided.

proc len[A, B](t: OrderedTable[A, B]): int {.inline.}

returns the number of keys in t.

proc clear[A, B](t: var OrderedTable[A, B])

Resets the table so that it is empty.

proc clear[A, B](t: var OrderedTableRef[A, B])

Resets the table so that is is empty.

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.

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.

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.

proc getOrDefault[A, B](t: OrderedTable[A, B]; key: A): B

proc hasKey[A, B](t: OrderedTable[A, B]; key: A): bool

returns true iff key is in the table t.

proc contains[A, B](t: OrderedTable[A, B]; key: A): bool

alias of hasKey for use with the in operator.

proc `[]=`[A, B](t: var OrderedTable[A, B]; key: A; val: B)

puts a (key, value)-pair into t.

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.

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.

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.

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.

proc toOrderedTable[A, B](pairs: openArray[(A, B)]): OrderedTable[A, B]

creates a new ordered hash table that contains the given pairs.

proc `$`[A, B](t: OrderedTable[A, B]): string

The $ operator for ordered hash tables.

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.

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).

proc len[A, B](t: OrderedTableRef[A, B]): int {.inline.}

returns the number of keys in t.

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.

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.

proc getOrDefault[A, B](t: OrderedTableRef[A, B]; key: A): B

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.

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.

proc hasKey[A, B](t: OrderedTableRef[A, B]; key: A): bool

returns true iff key is in the table t.

proc contains[A, B](t: OrderedTableRef[A, B]; key: A): bool

alias of hasKey for use with the in operator.

proc `[]=`[A, B](t: OrderedTableRef[A, B]; key: A; val: B)

puts a (key, value)-pair into t.

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.

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.

proc newOrderedTable[A, B](pairs: openArray[(A, B)]): OrderedTableRef[A, B]

creates a new ordered hash table that contains the given pairs.

proc `$`[A, B](t: OrderedTableRef[A, B]): string

The $ operator for ordered hash tables.

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.

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).

proc del[A, B](t: var OrderedTable[A, B]; key: A)

deletes key from ordered hash table t. O(n) complexity.

proc del[A, B](t: var OrderedTableRef[A, B]; key: A)

deletes key from ordered hash table t. O(n) complexity.

proc len[A](t: CountTable[A]): int

returns the number of keys in t.

proc clear[A](t: CountTableRef[A])

Resets the table so that it is empty.

proc clear[A](t: var CountTable[A])

Resets the table so that it is empty.

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.

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.

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.

proc getOrDefault[A](t: CountTable[A]; key: A): int

proc hasKey[A](t: CountTable[A]; key: A): bool

returns true iff key is in the table t.

proc contains[A](t: CountTable[A]; key: A): bool

alias of hasKey for use with the in operator.

proc `[]=`[A](t: var CountTable[A]; key: A; val: int)

puts a (key, value)-pair into t.

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.

proc toCountTable[A](keys: openArray[A]): CountTable[A]

creates a new count table with every key in keys having a count of 1.

proc `$`[A](t: CountTable[A]): string

The $ operator for count tables.

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.

proc inc[A](t: var CountTable[A]; key: A; val = 1)

increments t[key] by val.

proc smallest[A](t: CountTable[A]): tuple[key: A, val: int]

returns the (key,val)-pair with the smallest val. Efficiency: O(n)

proc largest[A](t: CountTable[A]): tuple[key: A, val: int]

returns the (key,val)-pair with the largest val. Efficiency: O(n)

proc sort[A](t: var CountTable[A])

sorts the count table so that the entry with the highest counter comes first. This is destructive! You must not modify t afterwards! You can use the iterators pairs, keys, and values to iterate over t in the sorted order.

proc len[A](t: CountTableRef[A]): int

returns the number of keys in t.

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.

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.

proc getOrDefault[A](t: CountTableRef[A]; key: A): int

proc hasKey[A](t: CountTableRef[A]; key: A): bool

returns true iff key is in the table t.

proc contains[A](t: CountTableRef[A]; key: A): bool

alias of hasKey for use with the in operator.

proc `[]=`[A](t: CountTableRef[A]; key: A; val: int)

puts a (key, value)-pair into t. val has to be positive.

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.

proc newCountTable[A](keys: openArray[A]): CountTableRef[A]

creates a new count table with every key in keys having a count of 1.

proc `$`[A](t: CountTableRef[A]): string

The $ operator for count tables.

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.

proc inc[A](t: CountTableRef[A]; key: A; val = 1)

increments t[key] by val.

proc smallest[A](t: CountTableRef[A]): (A, int)

returns the (key,val)-pair with the smallest val. Efficiency: O(n)

proc largest[A](t: CountTableRef[A]): (A, int)

returns the (key,val)-pair with the largest val. Efficiency: O(n)

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.

proc merge[A](s: var CountTable[A]; t: CountTable[A])

merges the second table into the first one

proc merge[A](s, t: CountTable[A]): CountTable[A]

merges the two tables into a new one

proc merge[A](s, t: CountTableRef[A])

merges the second table into the first one

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.

iterator pairs[A, B](t: Table[A, B]): (A, B)

iterates over any (key, value) pair in the table t.

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.

iterator keys[A, B](t: Table[A, B]): A

iterates over any key in the table t.

iterator values[A, B](t: Table[A, B]): B

iterates over any value in the table t.

iterator mvalues[A, B](t: var Table[A, B]): var B

iterates over any value in the table t. The values can be modified.

iterator pairs[A, B](t: TableRef[A, B]): (A, B)

iterates over any (key, value) pair in the table t.

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.

iterator keys[A, B](t: TableRef[A, B]): A

iterates over any key in the table t.

iterator values[A, B](t: TableRef[A, B]): B

iterates over any value in the table t.

iterator mvalues[A, B](t: TableRef[A, B]): var B

iterates over any value in the table t. The values can be modified.

iterator pairs[A, B](t: OrderedTable[A, B]): (A, B)

iterates over any (key, value) pair in the table t in insertion order.

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.

iterator keys[A, B](t: OrderedTable[A, B]): A

iterates over any key in the table t in insertion order.

iterator values[A, B](t: OrderedTable[A, B]): B

iterates over any value in the table t in insertion order.

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.

iterator pairs[A, B](t: OrderedTableRef[A, B]): (A, B)

iterates over any (key, value) pair in the table t in insertion order.

iterator mpairs[A, B](t: OrderedTableRef[A, B]): (A, var B)

iterates over any (key, value) pair in the table t in insertion order. The values can be modified.

iterator keys[A, B](t: OrderedTableRef[A, B]): A

iterates over any key in the table t in insertion order.

iterator values[A, B](t: OrderedTableRef[A, B]): B

iterates over any value in the table t in insertion order.

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.

iterator pairs[A](t: CountTable[A]): (A, int)

iterates over any (key, value) pair in the table t.

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.

iterator keys[A](t: CountTable[A]): A

iterates over any key in the table t.

iterator values[A](t: CountTable[A]): int

iterates over any value in the table t.

iterator mvalues[A](t: CountTable[A]): var int

iterates over any value in the table t. The values can be modified.

iterator pairs[A](t: CountTableRef[A]): (A, int)

iterates over any (key, value) pair in the table t.

iterator mpairs[A](t: CountTableRef[A]): (A, var int)

iterates over any (key, value) pair in the table t. The values can be modified.

iterator keys[A](t: CountTableRef[A]): A

iterates over any key in the table t.

iterator values[A](t: CountTableRef[A]): int

iterates over any value in the table t.

iterator mvalues[A](t: CountTableRef[A]): var int

iterates over any value in the table t. The values can be modified.

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

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")