monmohan / dsjslib Goto Github PK

A library implementing several standard data structures and utilities, in JavaScript. Its written and tested using Node.js which is the target platform.

License: MIT License

Shell 0.15% JavaScript 99.85%

javascript algorithms datastructures

dsjslib's Introduction

dsjslib

This is a collection of different data structures and utilities, implemented in JavaScript. Its written and tested using Node.js which is also the target platform.

API Documentation >>

Overview

New
- Bloom Filter - Probabilistic data structure to test whether an element is a member of a set.
Maps
- Sorted Maps: Maps sorted according to natural ordering of keys or by comparator function provided at creation time. Two different backing stores are available
  - AVLTree
  - Skip List
- Tries Map optimized for prefix searching on string keys
  - Multi Way Trie
  - Ternary Search Trie
- Multi-Valued Map supporting multiple values for a key
  - MultiMap
  - TreeMultiMap - In addition, Map is sorted on keys. Uses AVLTree as backing store
Queues
- Linked Deque - An optionally capacity constrained deque based on linked nodes
- Priority Queue - Priority Queue based on a Binary Heap
- Delay Queue - Queue of 'Delayed' items, item can only be taken when its delay has expired. For example usage see wiki: DelayQueue-for-Scheduled-Task-Management
Utilities
- LRU Cache with Stats Google Guava inspired LRU cache. Reference: Google Guava. In-memory LRU cache implementation for Node, inspired by Google Guava Loading Cache . The cache is simpler since it doesn't have to deal with concurrent threads, but other functionality of Guava cache are captured like - Auto loader function - Removal listener - Auto expiry After Write (TTL) - Max Size and weight - Cache Stats recording For usage and overview see wiki: https://github.com/monmohan/dsjslib/wiki/LRU-Cache-Feature-and-usage-overview
- BitSet - An array of bits with operations to set, examine and clear individual bits
- CircularBuffer - A data structure that uses a single, fixed-size buffer as if it were connected end-to-end. When the buffer is filled, new data is written starting at the beginning of the buffer and overwriting the old.
- Bloom Filter - Probabilistic data structure to test whether an element is a member of a set.
- BTree - Self balancing generalized Search Tree

Installation

    npm install dsjslib

Current version 0.6.14 is stable and thoroughly tested on Node v0.10

dsjslib's People

Contributors

Stargazers

Watchers

dsjslib's Issues

Extend binary trees to search neighbors

One task frequently appears in the binary tree: search neighbors of non-existent key. The following code implements such algorithm for the BinarySearchTree:

(file extend_binary_tree.js)

var dsjslib = require('dsjslib');

dsjslib.BinarySearchTree.prototype.getNeighbors = function (key) {
        if (typeof key === 'undefined' || key === null)return null;
        var node = this.root;
        var compFn = this._compFn;
        var that = this;
        return recFind(key, node);
        function recFind(key, node) {
            if (!node) {
                return null;
            }
            var comp = compFn(node, key);
            if( comp === 0 ) return [{key : node.key, value : node.value}];
            if (comp === -1 && node.leftChild) return recFind(key, node.leftChild);
            if (comp === 1 && node.rightChild) return recFind(key, node.rightChild);
            var ret = [
                {key : node.key, value : node.value}
            ];
            var neighbor = null;
            if(comp === -1) neighbor = that.predecessor(node.key);
            if(comp ===  1) neighbor = that.successor(node.key);
            if( neighbor )
                ret.push(
                    {key : neighbor.key, value : neighbor.value}
                );
            return ret;
        }
};

some test cases are present below:

var _ = require("underscore");
var dsjslib = require('dsjslib');
var assert = require("assert");
var extend_binary_tree = require("./extend_binary_tree.js");

var test = new dsjslib.AVLTree();

var c1 = {id:'c1'}
var c2 = {id:'c2'}
var c5 = {id:'c5'}

test
    .put(c1.id,c1)
    .put(c2.id,c2)
    .put(c5.id,c5)

for(var i=10; i < 100; i++) {
    test.put('c1'+i,{id:'c1'+i});
}

//console.log("DEBUG:",test);

// to the left returns the only one leftmost node
assert.deepEqual(test.getNeighbors('c0'),[{key:'c1',value:{id:'c1'}}]);

// if found, returns the only one found node
assert.deepEqual(test.getNeighbors('c1'),[{key:'c1',value:{id:'c1'}}]);
assert.deepEqual(test.getNeighbors('c2'),[{key:'c2',value:{id:'c2'}}]);

// in the middle returns two nodes, to the left and to the right of non-existent key
assert.equal(test.getNeighbors('c3').length,2);
assert.deepEqual(_.findWhere(test.getNeighbors('c3'),{key:'c2'}),{key:'c2',value:{id:'c2'}});
assert.deepEqual(_.findWhere(test.getNeighbors('c3'),{key:'c5'}),{key:'c5',value:{id:'c5'}});

assert.equal(test.getNeighbors('c4').length,2);
assert.deepEqual(_.findWhere(test.getNeighbors('c4'),{key:'c2'}),{key:'c2',value:{id:'c2'}});
assert.deepEqual(_.findWhere(test.getNeighbors('c4'),{key:'c5'}),{key:'c5',value:{id:'c5'}});

// if found, returns the only one found node
assert.deepEqual(test.getNeighbors('c5'),[{key:'c5',value:{id:'c5'}}]);

// to the right returns the only one rightmost node
assert.deepEqual(test.getNeighbors('c6'),[{key:'c5',value:{id:'c5'}}]);

// check working between deep nodes
for(var i=10; i < 99; i++) {
    assert.deepEqual(_.findWhere(test.getNeighbors('c1'+i+'1'),{key:'c1'+i}),{key:'c1'+i,value:{id:'c1'+i}});
    assert.deepEqual(_.findWhere(test.getNeighbors('c1'+i+'1'),{key:'c1'+(i+1)}),{key:'c1'+(i+1),value:{id:'c1'+(i+1)}});
}

The same might be implemented for other types of tree

UPD: fixed algorithm and testcases have been extended

async loader callbacks are fired only once if multiple requests are issues in quick succession

Return value of BST.put() depends on state

The return value of BinarySearchTree.put() differs depending on the state of the tree and is not
documented.

In case of the first insertion the tree instance is returned whereas for subsequent insertions a
structure like this is returned:

{
  put: [Function],
  node: [Object]
}

cache get() returns synchronously when item found in cache

Provide getSync() for synchronous fetches and get() for async fetches

TernarySearchTrie().delete has bugs.

You forgot it is not a binary-search-trie, the leftmost child of the right trie, suc, may have two children (suc.e and suc.g).

https://github.com/monmohan/dsjslib/blob/master/lib/TernarySearchTrie.js#L89-L100

TypeError in BST successor/predecessor-methods when used at boundaries

Under special circumstances there is a type error thrown when the successor/predecessor methods of BST are invoked at the boundaries (i.e. first or last key):

TypeError: Cannot read property 'leftChild' of null
    at BinarySearchTree.predecessorNode (/Users/aske/Repos/dsjslib/lib/BinarySearchTree.js:161:45)
    at BinarySearchTree.predecessor (/Users/aske/Repos/dsjslib/lib/BinarySearchTree.js:191:25)
    ...

If the values are inserted in chronological order successor() on the last key returns null but predecessor() on the first key provokes the error. If the values are inserted in anti-chronological order the behavior is the other way around.

I will issue a pull request for TestBST.js that reproduces this behavior.

No way to suppress debug output

So far there is no way to suppress debug output as logger.DEBUG is not accessible from the outside and the default is set to true which messes up the console with a lot of messages like:

AVL Height violation at Node <KEY>

Enhance Loading cache

First of all thanks for this nice lib I did not know.

I was looking for an equivalent of Guava's LoadingCache for a while in js.

Browserify

Notice that your lib works fine in the browser (Browserify) and you can mention that on your readme. However it's better to only load the code we need: var Cache = require("dsjslib/lib/Cache");

Suppliers

Guava support a cache for a single object that would be nice to have in this lib.

See Supplier<Animal> singleAnimalCache = Suppliers.memoizeWithExpiration(animalFromDbSupplier(), 365, TimeUnit.DAYS);

This would remove the burden of managing timers like in this code:

function getHashtagSuggestions() {
    setTimeout(function() {
        exports.getHashtagSuggestionsMemoized = _.memoize(getHashtagSuggestions);
    },10000);
    //
    return ApiRequest({
        method: "GET",
        url: "/suggestions/hashtags"
    });
};

exports.getHashtagSuggestionsMemoized = _.memoize(getHashtagSuggestions);

Support promises

Many of us are currently using promise based libraries like Q and it would be nice to support promises in addition to regular callbacks.

See the boilerplate involded in my example:

function getUserSuggestions(categoryId) {
    return ApiRequest({
        method: "GET",
        url: "/suggestions/users/forCategory/" + categoryId
    });
};

var UserSuggestionsCache = new Cache({
    'maximumSize': 10,
    'expiresAfterWrite': 5,
    'loaderFunction': function cacheLoader(key,onCompleteCallback) {
        getUserSuggestions(key)
            .then(function(result) {
                onCompleteCallback(undefined,result);
            })
            .fail(function(err) {
                onCompleteCallback(err);
            })
            .done();
    }
});

exports.getUserSuggestionsMemoized = function getUserSuggestionsMemoized(categoryId) {
    return Q.Promise(function(resolve,reject) {
        UserSuggestionsCache.get(categoryId,function(err,value) {
            if (err) {
                reject(err);
            } else {
                resolve(value);
            }
        })
    });
};

I would like to be able to write

function getUserSuggestions(categoryId) {
    return ApiRequest({
        method: "GET",
        url: "/suggestions/users/forCategory/" + categoryId
    });
};

var UserSuggestionsCache = new Cache({
    'maximumSize': 10,
    'expiresAfterWrite': 5,
    'loaderFunction': getUserSuggestions
});

exports.getUserSuggestionsMemoized = function getUserSuggestionsMemoized(categoryId) {
    return UserSuggestionsCache.getPromise(categoryId);
};

Note that my ApiRequest here is simply a Q promise factory.

I guess you'd rather not introduce dependencies in your lib but maybe this can be put in a separate project or be added as an optional dependency?