adix/ditab

Search:
Group by:
Source   Edit  

This module provides a directly indexed set/table representation via a dense seq[T] with an auxiliary sparse direct index to accelerate searching. "direct" means the same size as the key space or "alphabet". The index says what seq index has each (unique) key. This can do any unordered set op in guaranteed unit time cost per element -- make, insert, delete, member query, iterate, union/intersect/etc. -- all with arbitrarily "aged" sets.

The catch is that the "unit" in said cost will only be small if the key space is small enough to afford allocating index space & if the working set of the index fits into low enough latency memory to not be too slow. Otherwise, other data structures like hash tables & B-trees will outperform this. Iteration is always in insertion order whenever no deletes have occurred. The "unit" is also 2 memory accesses per operation, vs. often 1 for lptabz. So, very large scale can make this guaranteed to be ~2X slower than a good average case for lptabz, all depending upon exact requirements, of course.

The earliest reference I have elaborating this approach is _An Efficient Representation for Sparse Sets by Preston Briggs & Linda Torczon from Rice in 1993 referencing an exercise in Aho, Croft & Ullman 1974. It's simple enough that the idea may date to early 1960s DB work (e.g. by Codd), maybe under another term like "direct indexing". K below must have an available conversion to int. Duplicate keys cannot be allowed for this one.

Below here is pretty standard except for the generic signatures

Types

DISet[K] = DITab[K, void]
DITab specialized to sets Source   Edit   
DITab[K; V] = object
  when V is void:
  else:
Alphabet size determines K; V may be void Source   Edit  

Vars

diDenom = 0
default denominator (unused) Source   Edit   
diGrowPow2 = 0
default growth power of 2 (unused) Source   Edit   
diInitialSize = 0
default numerator (unused) Source   Edit   
diMinFree = 0
default min free slots (unused) Source   Edit   
diNumer = 0
default numerator (unused) Source   Edit   
diRehash = false
default hcode rehashing behavior (unused) Source   Edit   
diRobinHood = false
default to Robin Hood (unused) Source   Edit  

Procs

proc `$`[K, V: not void](t: DITab[K, V]): string
Source   Edit   
proc `$`[K](s: DITab[K, void]): string
Source   Edit   
proc `*`[K](s1, s2: DITab[K, void]): DITab[K, void] {.inline.}
Source   Edit   
proc `+`[K](s1, s2: DITab[K, void]): DITab[K, void] {.inline.}
Source   Edit   
proc `-`[K](s1, s2: DITab[K, void]): DITab[K, void] {.inline.}
Source   Edit   
proc `-+-`[K](s1, s2: DITab[K, void]): DITab[K, void] {.inline.}
Source   Edit   
proc `<`[K](s, t: DITab[K, void]): bool
Source   Edit   
proc `<=`[K](s, t: DITab[K, void]): bool
Source   Edit   
proc `==`[K, V](x, y: DITab[K, V]): bool
Source   Edit   
proc `==`[K](s, t: DITab[K, void]): bool
Source   Edit   
proc `[]`[K, V](t: DITab[K, V]; key: K): V {.inline.}
Source   Edit   
proc `[]`[K, V](t: var DITab[K, V]; key: K): var V {.inline.}
Source   Edit   
proc `[]=`[K, V](t: var DITab[K, V]; key: K; val: V)
Source   Edit   
proc card[K](s: DITab[K, void]): int {.inline.}
Source   Edit   
proc clear[K, V](t: var DITab[K, V]) {.inline.}
Source   Edit   
proc contains[K, V](t: DITab[K, V]; key: K): bool {.inline.}
Source   Edit   
proc containsOrIncl[K](t: var DITab[K, void]; key: K): bool {.inline.}
Source   Edit   
proc debugDump[K, V](t: DITab[K, V]; label = "")
Source   Edit   
proc del[K, V](t: var DITab[K, V]; key: K) {.inline.}
delete one key key from t; If you want to know if it was present then use missingOrExcl, take, or pop instead. Source   Edit   
proc depths[K, V](t: DITab[K, V]): seq[int]
Source   Edit   
proc depthStats[K, V](s: DITab[K, V]): tuple[m1, m2: float, mx: int]
Source   Edit   
proc difference[K](s1, s2: DITab[K, void]): DITab[K, void]
Source   Edit   
proc disjoint[K](s1, s2: DITab[K, void]): bool
Source   Edit   
proc editKey[K, V](t: var DITab[K, V]; old, new: K) {.inline.}
Source   Edit   
proc excl[K](s: var DITab[K, void]; elt: K) {.inline.}
Source   Edit   
proc excl[K](s: var DITab[K, void]; other: DITab[K, void])
Source   Edit   
proc getCap[K, V](t: var DITab[K, V]): int {.inline.}
Source   Edit   
proc getOrDefault[K, V](t: DITab[K, V]; key: K; def = default(V)): V {.inline.}
Source   Edit   
proc hash[K](s: DITab[K, void]): Hash
Source   Edit   
proc hasKey[K, V](t: DITab[K, V]; key: K): bool {.inline.}
Source   Edit   
proc hasKeyOrPut[K, V](t: var DITab[K, V]; key: K; val: V): bool {.inline.}
Source   Edit   
proc inc[K, V: SomeInteger](t: var DITab[K, V]; key: K; amount: SomeInteger = 1) {.
    inline.}
Source   Edit   
proc incl[K](s: var DITab[K, void]; elt: K) {.inline.}
Source   Edit   
proc incl[K](s: var DITab[K, void]; other: DITab[K, void])
Source   Edit   
proc indexBy[A, K, V](collection: A; index: proc (x: V): K): DITab[K, V]
Source   Edit   
proc init[K, V](t: var DITab[K, V]; initialSize = 0; numer = 0; denom = 0;
                minFree = 0; growPow2 = 0; rehash = false; robinhood = false) {.
    inline.}
Source   Edit   
proc initDISet[K](initialSize = 0; numer = diNumer; denom = diDenom;
                  minFree = diMinFree; growPow2 = diGrowPow2; rehash = diRehash;
                  robinhood = diRobinHood): DISet[K] {.inline.}
Return an DITab specialized to sets operations. See initDITab for parameter details. Source   Edit   
proc initDITab[K, V](initialSize = 0; numer = 0; denom = 0; minFree = 0;
                     growPow2 = 0; rehash = false; robinhood = false): DITab[K,
    V] {.inline.}
Source   Edit   
proc intersection[K](s1, s2: DITab[K, void]): DITab[K, void]
Source   Edit   
proc len[K, V](t: DITab[K, V]): int {.inline.}
Source   Edit   
proc map[K, A](data: DITab[K, void]; op: proc (x: K): A {.closure.}): DITab[A,
    void]
Source   Edit   
proc merge[K, V: SomeInteger](c: var DITab[K, V]; b: DITab[K, V])
Source   Edit   
proc mgetOrPut[K, V](t: var DITab[K, V]; key: K; val: V): var V {.inline.}
Source   Edit   
proc mgetOrPut[K, V](t: var DITab[K, V]; key: K; val: V; had: var bool): var V {.
    inline.}
Source   Edit   
proc missingOrExcl[K, V](t: var DITab[K, V]; key: K): bool
Source   Edit   
proc nthKey[K](t: DITab[K, void]; n: int): K {.inline.}
Source   Edit   
proc nthPair[K, V: not void](t: DITab[K, V]; n: int): (K, V) {.inline.}
Insertion-ordered tables support 0-origin nth-in-order pair. Source   Edit   
proc nthPair[K, V: not void](t: var DITab[K, V]; n: int): (K, ptr V) {.inline.}
Insertion-ordered tables support 0-origin nth-in-order pair w/editable val. Source   Edit   
proc pop[K, V: not void](t: var DITab[K, V]): (K, V) {.inline.}
Source   Edit   
proc pop[K, V: not void](t: var DITab[K, V]; key: K; val: var V): bool {.inline.}
Source   Edit   
proc pop[K](s: var DITab[K, void]; key: var K): bool {.inline.}
Source   Edit   
proc pop[K](t: var DITab[K, void]): K {.inline.}
Source   Edit   
proc rightSize(count: int; numer = 0; denom = 0; minFree = 0): int {.inline,
    ...deprecated: "Deprecated since 0.2; identity function", raises: [], tags: [],
    forbids: [].}
Deprecated: Deprecated since 0.2; identity function
Source   Edit   
proc setCap[K, V](t: var DITab[K, V]; newSize = -1)
Source   Edit   
proc setOrIncl[K](t: var DITab[K, void]; key: K): bool {.inline.}
Source   Edit   
proc setPolicy[K, V](t: var DITab[K, V]; numer = 0; denom = 0; minFree = 0;
                     growPow2 = 0; rehash = 0; robinhood = 0) {.inline.}
Source   Edit   
proc symmetricDifference[K](s1, s2: DITab[K, void]): DITab[K, void]
Source   Edit   
proc take[K, V: not void](t: var DITab[K, V]; key: K; val: var V): bool {.inline.}
Source   Edit   
proc take[K](t: var DITab[K, void]; key: var K): bool {.inline.}
Source   Edit   
proc toDITab[K, V: not void](pairs: openArray[(K, V)]; dups = false): DITab[K, V]
Source   Edit   
proc toDITab[K](keys: openArray[K]; dups = false): DITab[K, void]
Source   Edit   
proc union[K](s1, s2: DITab[K, void]): DITab[K, void]
Source   Edit   
proc `{}`[K, V](t: DITab[K, V]; key: K): V {.inline.}
Source   Edit   
proc `{}`[K, V](t: var DITab[K, V]; key: K): var V {.inline.}
Source   Edit   
proc `{}=`[K, V](t: var DITab[K, V]; key: K; val: V) {.inline.}
Source   Edit  

Iterators

iterator hcodes[K, V](t: DITab[K, V]): (int, Hash)
Source   Edit   
iterator items[K](t: DITab[K, void]): K
Source   Edit   
iterator keys[K, V](t: DITab[K, V]): K
Source   Edit   
iterator mitems[K](t: var DITab[K, void]): var K
Source   Edit   
iterator mpairs[K, V: not void](t: DITab[K, V]): (K, var V)
Source   Edit   
iterator mvalues[K, V](t: var DITab[K, V]): var V
Source   Edit   
iterator pairs[K, V: not void](t: DITab[K, V]): (K, V)
Source   Edit   
iterator pairs[K](t: DITab[K, void]): (int, K)
Source   Edit   
iterator topByVal[K, V](c: DITab[K, V]; n = 10; min = V.low; order = Cheap): (K,
    V)
Source   Edit   
iterator values[K, V](t: DITab[K, V]): V
Source   Edit  

Templates

template editOrInit[K, V](t: var DITab[K, V]; key: K; v, body1, body2: untyped)
Source   Edit   
template withValue[K, V](t: var DITab[K, V]; key: K;
                         value, body1, body2: untyped)
Source   Edit   
template withValue[K, V](t: var DITab[K, V]; key: K; value, body: untyped)
Source   Edit  

Made with Nim. Generated: 2025-06-22 12:33:37 UTC