monmohan / dsjslib Goto Github PK
View Code? Open in Web Editor NEWA 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
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
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
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>
Provide getSync() for synchronous fetches and get() for async fetches
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.
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.
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");
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);
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?
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
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]
}
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.