# Module tables

The `tables` module implements an efficient hash table that is a mapping from keys to values.

Note: The data types declared here have value semantics: This means that `=` performs a copy of the hash table.

# Imports

hashes, math

# Types

    TTable* {.final, myShallow.}[A, B] = object
      data: TKeyValuePairSeq[A, B]
      counter: int

  generic hash table

    TOrderedTable* {.final, myShallow.}[A, B] = object
      data: TOrderedKeyValuePairSeq[A, B]
      counter, first, last: int

  table that remembers insertion order

    TCountTable* {.final, myShallow.}[A] = object
      data: seq[tuple[key: A, val: int]]
      counter: int

  table that counts the number of each key

# Procs

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

  returns the number of keys in t.

    proc `[]`*[A, B](t: TTable[A, B]; key: A): B

  retrieves the value at `t[key]`. If key is not in t, default empty value for the type B is returned and no exception is raised. One can check with `hasKey` whether the key exists.

    proc mget*[A, B](t: var TTable[A, B]; key: A): var B

  retrieves the value at `t[key]`. The value can be modified. If key is not in t, the `EInvalidKey` exception is raised.

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

  returns true iff key is in the table t.

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

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

    proc add*[A, B](t: var TTable[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: var TTable[A, B]; key: A)

  deletes key from hash table t.

    proc initTable*[A, B](initialSize = 64): TTable[A, B]

  creates a new hash table that is empty. initialSize needs to be a power of two.

    proc toTable*[A, B](pairs: openarray[tuple[key: A, val: B]]): TTable[A, B]

  creates a new hash table that contains the given pairs.

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

  The $ operator for hash tables.

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

  returns the number of keys in t.

    proc `[]`*[A, B](t: TOrderedTable[A, B]; key: A): B

  retrieves the value at `t[key]`. If key is not in t, default empty value for the type B is returned and no exception is raised. One can check with `hasKey` whether the key exists.

    proc mget*[A, B](t: var TOrderedTable[A, B]; key: A): var B

  retrieves the value at `t[key]`. The value can be modified. If key is not in t, the `EInvalidKey` exception is raised.

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

  returns true iff key is in the table t.

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

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

    proc add*[A, B](t: var TOrderedTable[A, B]; key: A; val: B)

  puts a new (key, value)-pair into t even if `t[key]` already exists.

    proc initOrderedTable*[A, B](initialSize = 64): TOrderedTable[A, B]

  creates a new ordered hash table that is empty. initialSize needs to be a power of two.

    proc toOrderedTable*[A, B](pairs: openarray[tuple[key: A, val: B]]): TOrderedTable[
        A, B]

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

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

  The $ operator for ordered hash tables.

    proc len*[A](t: TCountTable[A]): int

  returns the number of keys in t.

    proc `[]`*[A](t: TCountTable[A]; key: A): int

  retrieves the value at `t[key]`. If key is not in t, 0 is returned. One can check with `hasKey` whether the key exists.

    proc mget*[A](t: var TCountTable[A]; key: A): var int

  retrieves the value at `t[key]`. The value can be modified. If key is not in t, the `EInvalidKey` exception is raised.

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

  returns true iff key is in the table t.

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

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

    proc initCountTable*[A](initialSize = 64): TCountTable[A]

  creates a new count table that is empty. initialSize needs to be a power of two.

    proc toCountTable*[A](keys: openArray[A]): TCountTable[A]

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

    proc `$`*[A](t: TCountTable[A]): string

  The $ operator for count tables.

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

  increments t[key] by val.

    proc Smallest*[A](t: TCountTable[A]): tuple[key: A, val: int]

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

    proc Largest*[A](t: TCountTable[A]): tuple[key: A, val: int]

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

    proc sort*[A](t: var TCountTable[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.

# Iterators

    iterator pairs*[A, B](t: TTable[A, B]): tuple[key: A, val: B]

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

    iterator mpairs*[A, B](t: var TTable[A, B]): tuple[key: A, val: var B]

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

    iterator keys*[A, B](t: TTable[A, B]): A

  iterates over any key in the table t.

    iterator values*[A, B](t: TTable[A, B]): B

  iterates over any value in the table t.

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

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

    iterator pairs*[A, B](t: TOrderedTable[A, B]): tuple[key: A, val: B]

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

    iterator mpairs*[A, B](t: var TOrderedTable[A, B]): tuple[key: A, val: 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: TOrderedTable[A, B]): A

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

    iterator values*[A, B](t: TOrderedTable[A, B]): B

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

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

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

    iterator pairs*[A](t: TCountTable[A]): tuple[key: A, val: int]

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

    iterator mpairs*[A](t: var TCountTable[A]): tuple[key: A, val: var int]

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

    iterator keys*[A](t: TCountTable[A]): A

  iterates over any key in the table t.

    iterator values*[A](t: TCountTable[A]): int

  iterates over any value in the table t.

    iterator mvalues*[A](t: TCountTable[A]): var int

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

Generated: 2012-09-23 21:47:54 UTC