Hash table extension with on-the-fly sorter for uint64 keys.

This module works as a TableRef (see the table module) unless order relations are needed, for instance:

import hlst

var h = newHLst64[string](nil,5)     # nil: return as void value

h[2] = "two"
h[4] = "four"
h[5] = "five"

doAssert h[2] == "two"
doAssert h[6].isNil                  # nil was initialised as void value

If order relations come into play, the underlying TableRef will be ad-hoc extended by a sorter index. This enables simple queries ge(), lt(), etc. Example:

doAssert h.ge(8).isNil
doAssert h.gt(0) == "two"

Once activated, the sorter index will stay in the background to be readily available. For repeated add/delete operations, the sorter inxed sould be flushed as it slows down these operations. This might not be a problem for sporadic add/delete use after order relation usage.

To flush the sorter index use unSort() as in the example:

h.unSort()

or combined with other operations

h.unSort().del(5)

Although the ad-hoc nature of the sorter index does not perform uniformly, with C projects I observed better performance with the on-the-fly hash table sorters than with red-black trees under the following conditions:

collect data first, rarely use order relations at this stage

pretty print sorted collected data when finished

Imports

algorithm, math, sequtils, tables

Types

HLst64*[T] = ref HLst64Obj[T]: table object reference Source Edit

Procs

proc newHlst64*[T](ifFail: T; tabInit = 64): Hlst64[T]: new hashed tab with on-the-fly sorter, the ifFail argument is returned as a valie when table lookup fails (see also HLst64VoidKey()) Source Edit
proc unSort*[T](st: Hlst64[T]): Hlst64[T] {. discardable .}: remove sorter and free resources, useful if order relations are not needed anymore Source Edit
proc sort*[T](st: Hlst64[T]): Hlst64[T] {. discardable, inline .}: explicitely force sorter, not needed under mormal circumstances Source Edit
proc len*[T](st: Hlst64[T]): int: returns the number of keys in the list Source Edit
proc clear*[T](st: Hlst64[T]): Hlst64[T] {. discardable .}: resets the list so that it becomes empty Source Edit
proc HLstVoidKey*[T](st: Hlst64[T]): uint64 {. inline .}: pseudo constant, void key Source Edit
proc HLstMaxKey*[T](st: Hlst64[T]): uint64 {. inline .}: pseudo constant, one less than void key Source Edit
proc HLstVoidVal*[T](st: Hlst64[T]): T {. inline .}: pseudo constant, void value Source Edit
proc `[]=`*[T](st: Hlst64[T]; key: uint64; data: T): add or update a value; the key argument must be smaller than high(K) which is -- in the case of int keys -- the C equivalent of INTMAX Source Edit
proc del*[T](st: Hlst64[T]; key: uint64): Hlst64[T] {. discardable .}: delete item in table with key == argument key Source Edit
proc hasKey*[T](st: Hlst64[T]; key: uint64): bool: Returns true key if it exists Source Edit
proc eqKey*[T](st: Hlst64[T]; key: uint64): uint64: Returns argument key if it exists, HLstVoidKey otherwise Source Edit
proc leKey*[T](st: Hlst64[T]; key: uint64): uint64: find maximum key less or equal argument (or HLatVoidKey) Source Edit
proc geKey*[K, T](st: Hlst64[T]; key: uint64): uint64: find minimum key greater or equal argument (or HLatVoidKey) Source Edit
proc ltKey*[T](st: Hlst64[T]; key: uint64): uint64 {. inline .}: ltKey(st,key-1) is an alias for leKey(st,key-1) Source Edit
proc gtKey*[T](st: Hlst64[T]; key: uint64): uint64 {. inline .}: gtKey(st,key-1) is an alias for geKey(st,key+1) Source Edit
proc minKey*[T](st: HLst64[T]): uint64 {. inline .}: retrieve mimimum key Source Edit
proc unqueue*[T](st: Hlst64[T]): T: retrieve/fetch item with mimimum key (or HLstVoidVal) Source Edit
proc pop*[T](st: Hlst64[T]): T: retrieve/fetch item with maximum key (or HLstVoidVal) Source Edit
proc eq*[T](st: Hlst64[T]; key: uint64): T: find value in table with key == argument, returns HLstVoidVal if there is no such key Source Edit
proc `[]`*[T](st: Hlst64[T]; key: uint64): T {. inline .}: st[key] is an alias for eq(st,key) Source Edit
proc le*[T](st: Hlst64[T]; key: uint64): T: find value in table where key is maximum <= argument, returns HLstVoidVal if there is no such key Source Edit
proc ge*[T](st: Hlst64[T]; key: uint64): T: find value in table where key is minimum >= argument, returns HLstVoidVal if there is no such key Source Edit
proc lt*[T](st: Hlst64[T]; key: uint64): T {. inline .}: lt(st,key) is an alias for le(st,key-1) Source Edit
proc gt*[T](st: Hlst64[T]; key: uint64): T {. inline .}: gt(st,key) is an alias for ge(st,key+1) Source Edit

Iterators

iterator pairs*[T](st: Hlst64[T]): (uint64, T) {. inline .}: iterates over any (key,value) pair in the table st Source Edit
iterator mpairs*[T](st: Hlst64[T]): (uint64, var T) {. inline .}: iterates over any (key,value) pair in the table st, the values can be modified Source Edit
iterator keys*[T](st: Hlst64[T]): uint64 {. inline .}: iterates over any key in the table st Source Edit
iterator values*[T](st: Hlst64[T]): T {. inline .}: iterates over any value in the table st Source Edit
iterator mvalues*[T](st: Hlst64[T]): var T {. inline .}: iterates over any value in the table st, the values can be modified Source Edit
iterator sortedKeys*[T](st: Hlst64[T]): uint64 {. inline .}: like keys() but over sorted table Source Edit
iterator sortedPairs*[T](st: Hlst64[T]): (uint64, T) {. inline .}: like pairs() but over sorted table Source Edit

Module hlst64

Imports

Types

Procs

Iterators