sorta

SortedTable implementation using B-Tree as an internal data structure.

The BTree algorithm is based on:

  • N. Wirth, J. Gutknecht: Project Oberon, The Design of an Operating System and Compiler; pages 174-190.

Public API tries to mimic API of Nim's built-in Tables as much as possible. The ommission of add procedure is done on purpose.

Types

SortedTable[Key; Val] = object
  root: Node[Key, Val]
  entries: int

Generic sorted table, consisting of key-value pairs.

root and entries are internal implementation details which cannot be directly accessed.

For creating an empty SortedTable, use initSortedTable proc.

Procs

proc initSortedTable[Key, Val](): SortedTable[Key, Val]
Creates a new empty SortedTable.
proc toSortedTable[Key, Val](pairs: openArray[(Key, Val)]): SortedTable[Key, Val]

Creates a new SortedTable which contains the given pairs.

pairs is a container consisting of (key, value) tuples.

proc getOrDefault[Key, Val](b: SortedTable[Key, Val]; x: Key): Val
Retrieves the value at b[key] if key is in b. Otherwise, the default initialization value for type B is returned (e.g. 0 for any integer type).
proc getOrDefault[Key, Val](b: SortedTable[Key, Val]; x: Key; default: Val): Val
Retrieves the value at b[key] if key is in b. Otherwise, default is returned.
proc `[]`[Key, Val](b: SortedTable[Key, Val]; x: Key): Val

Retrieves the value at b[key].

If key is not in b, the KeyError exception is raised.

proc hasKey[Key, Val](b: SortedTable[Key, Val]; x: Key): bool
Returns true if key is in the table b.
proc contains[Key, Val](b: SortedTable[Key, Val]; x: Key): bool
Alias of hasKey proc for use with the in operator.
proc `[]=`[Key, Val](b: var SortedTable[Key, Val]; key: Key; val: Val)
Inserts a (key, value) pair into b.
proc hasKeyOrPut[Key, Val](b: var SortedTable[Key, Val]; key: Key; val: Val): bool
Returns true if key is in the table, otherwise inserts value.
proc del[Key, Val](b: var SortedTable[Key, Val]; key: Key)
Deletes key from table b. Does nothing if the key does not exist.
proc take[Key, Val](b: var SortedTable[Key, Val]; key: Key; val: var Val): 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 `$`[Key, Val](b: SortedTable[Key, Val]): string
The $ operator for tables. Used internally when calling echo on a table.
proc len[Key, Val](b: SortedTable[Key, Val]): int {...}{.inline.}
proc `==`[Key, Val](a, b: SortedTable[Key, Val]): bool

The == operator for SortedTables.

Returns true if the content of both tables contains the same key-value pairs. Insert order does not matter.

Iterators

iterator keys[Key, Val](b: SortedTable[Key, Val]): Key
Iterates over all the keys in the table b.
iterator keysFrom[Key, Val](b: SortedTable[Key, Val]; fromKey: Key): Key
Iterates over keys in the table from fromKey to the end.
iterator keysBetween[Key, Val](b: SortedTable[Key, Val]; fromKey: Key; toKey: Key): Key
Iterates over keys in the table from fromKey to toKey inclusive.
iterator values[Key, Val](b: SortedTable[Key, Val]): Val
Iterates over all the values in the table b.
iterator mvalues[Key, Val](b: var SortedTable[Key, Val]): var Val
Iterates over all the values in the table b. The values can be modified.
iterator valuesFrom[Key, Val](b: SortedTable[Key, Val]; fromKey: Key): Val
Iterates over the values in the table from the given key to the end.
iterator valuesBetween[Key, Val](b: SortedTable[Key, Val]; fromKey: Key; toKey: Key): Val
Iterates over the values in the table from fromKey to toKey inclusive.
iterator pairs[Key, Val](b: SortedTable[Key, Val]): (Key, Val)
Iterates over all (key, value) pairs in the table b.
iterator mpairs[Key, Val](b: var SortedTable[Key, Val]): (Key, var Val)
Iterates over all (key, value) pairs in the table b. The values can be modified.
iterator pairsFrom[Key, Val](b: SortedTable[Key, Val]; fromKey: Key): tuple[key: Key,
    val: Val]
Iterates over (key, value) pairs in the table from the given key to the end.
iterator pairsBetween[Key, Val](b: SortedTable[Key, Val]; fromKey: Key; toKey: Key): tuple[
    key: Key, val: Val]
Iterates over (key, value) pairs in the table from fromKey to toKey inclusive.