node package manager
It’s your turn. Help us improve JavaScript. Take the 2017 JavaScript Ecosystem Survey »


Cache [LRU Cache with stats]

[Reference: Google Guava]

In-memory LRU cache implementation for Node, inspired by Google Guava Loading Cache . The cache is much simpler since it doesn't have to deal with concurrent threads, but other functionality of Guava cache are captured e.g auto loader function, removal listener, stats recording etc. For usage and overview see wiki:


//Get value for key,
//Automatically load the value if not present and an auto loader function is configured

//Get value for key as present in cache, not attempt to load the key will be done
//even if a loader is configured


//Add a key value 

//Invalidate a key, If a removal listener is configured, it will be invoked with key value pair
//and removal cause as 'explicit'

//Invalidate all keys in cache, removal listeners are not invoked

//Gets statistics of cache usage
cache.stats returns an object {'hitCount':<number>,'missCount':<number>,'reqeustCount':<number>}

AVL Tree [Map]

Extends BinarySearchTree (see src/BinarySearchTree.js) to provide a Map like functionality backed by a balanced Tree. All functionality of BinarySearchTree is available. In addition Tree is height balanced by rotation whenever an insert is done See rotate(), reBalance() and checkAVLProperty() functions for explanation. Caller doesn't need to invoke these functions, they are internally used when an insert or delete violates the AVL property of the tree

//Create and AVLTree (extends a BinarySearchTree)
var AVLTree = require("dsjslib").AVLTree
var avl=new AVLTree([compareFn]) //optional compare fn to sort the keys

//Insert a key value. It also re-balances the tree

//Get a value for key

//Remove key vallue, also rebalances the tree

//Predecessor and Successor
avl.predecessor(key)  avl.successor(key) 

//Inorder traversal of the tree. callbackfn called for every node visited

//Min and Max - if start node not given, starts at root
avl.min([startAtNode]) avl.max([startAtNode])

// Validates the tree starting at given node (root otherwise). 
// Validates BST as well as AVL proeprties
//Print the tree starting at root (requires util module from Node.js)

SkipList [Map]

[Ref - Lecture on skip-lists]

//Create a Skip List
//Optional compare function to order the keys. If not provided, a natural ordering is

var SkipList = require("dsjslib").SkipList
var skl=new SkipList(compareFn)

//Add a key value

//Search for a key

//delete a key and its associated value

//Get all entries(sorted). They are returned as key value pair objects


[Ref - Introduction to Algorithms By Cormen et al.]

Creates a BTree of degree K .
Any node in the Tree can have a maximum of 2*K-1 keys  and a minimum of K-1 keys.

var BTree = require("dsjslib").BTree

var btree=new BTree(K) 

//Inserts a key and splits nodes as required

//Search by key

//Deletes a key and re-joins nodes and/or reduces the height of tree as required

//Check various BTree invariants -- For sanity testing
1. Except root all nodes have degree -1 <keys<2*degree-1
2. Child keys are less than corresponding parent key 
   (and greater than predecessor parent key)


Known Limitations: Currently only supports Numeric or String keys (uses < > for natural ordering).

RWayTrie [Map optimized for String keys]

[Reference: Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne]

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.

// Creates a RWayTrie of alphabet size R .
//For example if you know that the keys are made of ASCII chars only, R=128. 
//Each node in this trie will have an array of size R. 

var RWayTrie = require("dsjslib").RWayTrie
var rTrie=new RWayTrie(R) 

// Inserts a key and set its value as val

//Search for a key and return associated value or null

//Deletes a key 

//Return a list of all key, value pairs in sorted order (of keys)

//Return a list of all key, value pairs where
//keys start with given prefix_chars

Known Limitations: None

TernarySearchTrie [Map optimized for String keys]

[Reference: Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne]

Data structure supporting String keys, for fast retrieval of values associated with string and provide prefix searches. Functions are same as RWayTrie

//Creates a TernarySearchTrie
var TernarySearchTrie = require("dsjslib").TernarySearchTrie
var tst=new TernarySearchTrie() 

//Insert a key value pair into the Trie

//Search for key and return associated value or null

//Deletes a key and associated value

//Return a list of all key, value pairs where
//keys start with given prefix_chars

Known Limitations: None