cligen/tern

Search:
Group by:

This module implements a Ternary Search Tree which is an efficient container for a sorted set|mapping of strings in the family of digital search trees. Presently, NUL bytes('\0') are not allowed in keys. I have measured it as up to 1.5x faster than CritBitTree (at a cost of a 7x memory footprint) doing things like unique **.nim lines and never more than 1.1x slower. It mostly felt easier for me to extend this variant. It is API-compatible with CritBitTree (except a longestMatch -> longest parameter rename which will be trapped by the compiler if you use kwargs). CritBitTree itself is API-compatible with the union of both HashSet and Table.

Types

Node[T] = ref NodeOb[T]
NodeOb[T] {.acyclic.} = object
  ch*: char
  cnt*: int
  when T isnot void:
    val*: T
  kid*: array[3, ref NodeOb[T]]
Tern[T] = object
  root*: Node[T]
  ## Number of elements
  ## Depth of Tree
A Tern can be used as either a mapping from strings to type T or as a set(strings) if T is void.

Consts

NUL = '\x00'

Procs

proc `$`[T](t: Tern[T]): string
Return string form of t; {A,B,..} if T is void or else {A: valA, B: valB}. 
proc `[]`[T](c: var Tern[T]; key: string): var T {.inline.}
Retrieves modifiable value at t[key] or raises KeyError if missing. 
proc `[]`[T](t: Tern[T]; key: string): T {.inline.}
Retrieves value at t[key] or raises KeyError if missing. 
proc `[]=`[T](t: var Tern[T]; key: string; val: T)
Inserts key, val-pair into t, overwriting if present. 
proc contains[T](t: Tern[T]; key: string): bool {.inline.}
proc containsOrIncl[T](t: var Tern[T]; key: string): bool {.discardable.}
Returns true iff t contains key or inserts into t if missing. 
proc containsOrIncl[T](t: var Tern[T]; key: string; val: T): bool
Returns true iff t contains key or does t[key]=val if missing. 
proc inc[T](t: var Tern[T]; key: string; val: int = 1)
Increments t[key] by val (starting from 0 if missing). 
proc incl(t: var Tern[void]; key: string) {....raises: [], tags: [], forbids: [].}
Includes key in t. 
proc incl[T](t: var Tern[T]; key: string; val: T)
Inserts key with value val into t, overwriting if present 
proc len[T](t: Tern[T]): int {.inline.}
proc mgetOrPut[T](t: var Tern[T]; key: string; val: T): var T
Retrieves modifiable value at t[key] or inserts if missing. 
proc rawGet[T](t: Tern[T]; key: string): Node[T]
Return node for key or nil if not found 
proc rawInsert[T](t: var Tern[T]; key: string): Node[T]
proc rawPfx[T](t: Tern[T]; pfx: string; longest = false): Node[T]
Return sub-tree for all keys starting with prefix or if longest then sub-tree for longest match (which need not be a complete match). 
proc uniquePfxPat[T](t: Tern[T]; key: string; sep = "*"): string
Return shortest unique prefix pattern for key known to be in t. Unlike a shortest unique prefix string, this is well-defined for all sets. The separator character is only used if it can shrink total rendered space. 
proc uniquePfxPats(x: openArray[string]; sep = "*"): seq[string] {....raises: [],
    tags: [], forbids: [].}
Return unique prefixes in x assuming non-empty-string&unique x[i]. 
proc uniqueSfxPats(x: openArray[string]; sep = "*"): seq[string] {....raises: [],
    tags: [], forbids: [].}
Return unique suffixes in x assuming non-empty-string&unique x[i].

Iterators

iterator items[T](t: Tern[T]): string
yields all keys in lexicographical order. 
iterator keys[T](t: Tern[T]): string
yields all keys in lexicographical order. 
iterator keysWithPrefix[T](t: Tern[T]; prefix: string; longest = false): string
Yields all keys starting with prefix. 
iterator mpairs[T](t: var Tern[T]): tuple[key: string, val: var T]
yields all (key, value)-pairs of t. The yielded values can be modified. 
iterator mpairsWithPrefix[T](t: var Tern[T]; prefix: string; longest = false): tuple[
    key: string, val: var T]
Yields all (key, value)-pairs of t starting with prefix. The yielded values can be modified. 
iterator mvalues[T](t: var Tern[T]): var T
yields all values of t in the lexicographical order of the corresponding keys. The values can be modified. 
iterator mvaluesWithPrefix[T](t: var Tern[T]; prefix: string; longest = false): var T
Yields all values of t for keys starting with prefix. The values can be modified. 
iterator pairs[T](t: Tern[T]): tuple[key: string, val: T]
yields all (key, value)-pairs of t. 
iterator pairsWithPrefix[T](t: Tern[T]; prefix: string; longest = false): tuple[
    key: string, val: T]
Yields all (key, value)-pairs of t starting with prefix. 
iterator values[T](t: Tern[T]): T
yields all values of t in the lexicographical order of the corresponding keys. 
iterator valuesWithPrefix[T](t: Tern[T]; prefix: string; longest = false): T
Yields all values of t for keys starting with prefix.

Made with Nim. Generated: 2024-04-09 11:06:24 UTC