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.