Hash table extension with on-the-fly sorter for signed integer keys (see Hlst64 for uint64 keys).

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

import hlst

var h = newHLst[int,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

HLst*[K, T] = ref HLstObj[K, T]: table object reference Source Edit

Procs

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

Iterators

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

Module hlst

Imports

Types

Procs

Iterators