Class: RWayTrie

RWayTrie

Data structure supporting String keys, for fast retrieval of values associated with string keys. In comparison to a Map, has additional (fast) functions like list of keys with prefix and listing all keys in sorted order. For large R the space requirement for this DS is impractical (although in javascript arrays are sparse so its not the same) , TernarySearchTrie can be more practical alternative. [Reference: Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne]

new RWayTrie(R)

Example -

var RWayTrie = require("dsjslib").RWayTrie
var rtrie=new RWayTrie(128)
Parameters:
Name Type Description
R Number

R is the alphabet size. For example when its known that string keys are made of ASCII chars R can be set to 128.
Source:

Methods

delete(key)

Delete a key value pair

Parameters:
Name Type Description
key String
Source:

entrySet() → {Array}

Return a sorted list of all key value pairs

Source:
Returns:

Array of objects {key:,value:}

Type
Array

get(key) → {*}

Get value for a given key

Parameters:
Name Type Description
key
Source:
Returns:

value or null if key is not found

Type
*

keysWithPrefix(prefix) → {Array}

Return a list of all key, value pairs where keys start with given prefix chars

Parameters:
Name Type Description
prefix String
Source:
Returns:

Array of objects {key:,value:}

Type
Array

put(key, val) → {RWayTrie}

Insert a key value pair

Parameters:
Name Type Description
key String
val *
Source:
Returns:

this

Type
RWayTrie