rbst-lite
this package will provide a javascript implementation of randomized-binary-search-tree derived from http://kukuruku.co/hub/cpp/randomized-binary-search-trees with zero npm-dependencies
documentation
api-doc
todo
- none
change since 4fb90e68
- npm publish 2016.10.10
- add api-doc
- add testCase_rbst_default
- fix sizeUpdate
- none
build-status
git-branch : | master | beta | alpha |
---|---|---|---|
test-report : | |||
coverage : | |||
build-artifacts : |
master branch
- stable branch
- HEAD should be tagged, npm-published package
beta branch
- semi-stable branch
- HEAD should be latest, npm-published package
alpha branch
- unstable branch
- HEAD is arbitrary
- commit history may be rewritten
quickstart example
/* * rbst-lite.js * https://github.com/kaizhu256/node-rbst-lite * * this package will provide a javascript implementation of randomized-binary-search-tree * derived from http://kukuruku.co/hub/cpp/randomized-binary-search-trees * with zero npm-dependencies * * quickstart example: * copy and paste this entire script into the browser or nodejs console and press <enter> */ /* istanbul instrument in package rbst-lite *//*jslint bitwise: true, browser: true, maxerr: 8, maxlen: 96, node: true, nomen: true, regexp: true, stupid: true*/ { 'use strict'; var local; local = {}; // globally export local /* istanbul ignore next */ if typeof global === 'object' && global globalrbst_lite = local; /* istanbul ignore next */ if typeof module === 'object' && module moduleexports = local; /* istanbul ignore next */ if typeof window === 'object' && window windowrbst_lite = local; // run shared js-env code - lib.rbst.js { var compare create find findInKeyRange insert insertAsRoot join print remove rotateLeft rotateRight sizeUpdate; { /* * this function will compare aa vs bb and return: * -1 if aa < bb * 0 if aa === bb * 1 if aa > bb * the priority for comparing different typeof's is: * number < boolean < string < object < undefined */ var typeof1 typeof2; if aa === bb return 0; // handle undefined case if aa === undefined return 1; if bb === undefined return -1; typeof1 = typeof aa; typeof2 = typeof bb; if typeof1 === typeof2 return typeof1 === 'object' ? 0 : aa < bb ? -1 : 1; if typeof1 === 'number' return -1; if typeof2 === 'number' return 1; if typeof1 === 'boolean' return -1; if typeof2 === 'boolean' return 1; if typeof1 === 'string' return -1; if typeof2 === 'string' return 1; return 0; }; { /* * this function will create a tree with the given key and data */ return key: key data: data left: null right: null size: 1 ; }; { /* * this function will find the node in the tree with the given key */ var node tmp; node = tree; tmp = node && ; while tmp node = tmp === -1 ? noderight : nodeleft; tmp = node && ; return node; }; { /* * this function will iteratively call fnc on all nodes in the tree, * with keys in the inclusive key-range [aa, bb] */ var node sentinel stack tmp traversedList; if !tree return; // find first node with key >= aa node = tree; stack = node; tmp = node && ; while node stack; node = tmp === -1 ? noderight : nodeleft; tmp = node && ; traversedList = stack; // find last node with key <= bb sentinel = null; node = tree; tmp = ; while node sentinel = node; node = tmp === 1 ? nodeleft : noderight; tmp = node && ; sentinel = node || sentinel; // begin traversal with first node with key >= aa while stacklength node = stack; tmp = ; if >= 0 && <= 0 ; // end traversal with last node with key <= bb if node === sentinel return; node = noderight; if traversedList < 0 while node stack; node = nodeleft; }; { /* * this function will insert a new node in the tree with the given key and data, * with random re-balancing */ if !tree return ; if Math % treesize + 1 === 0 && typeof key !== 'object' return ; if === -1 treeleft = ; else treeright = ; ; return tree; }; { /* * this function will insert a new node in the tree with the given key and data, * and rebalance it as the root node */ if !tree return ; if === -1 treeleft = ; return ; treeright = ; return ; }; { /* * this function will join the left and right trees after deleting their parent tree */ if !left return right; if !right return left; // left is heavy, so move it up if leftsize > rightsize leftright = ; ; return left; // right is heavy, so move it up rightleft = ; ; return right; }; { /* * this function will print the tree */ var height ii recurse; { if !tree return; ; ii += 1; if depth > height height = depth; console; ; }; height = ''; ii = -1; console; ; console; }; { /* * this function will remove the node in the tree with the given key */ if !tree return tree; if treekey === key return ; if === -1 treeleft = ; else treeright = ; ; return tree; }; { /* * this function will rotate-left tree.right up to its parent tree's position */ var right; right = treeright; treeright = rightleft; ; rightleft = tree; ; return right; }; { /* * this function will rotate-right tree.left up to its parent tree's position */ var left; left = treeleft; treeleft = leftright; ; leftright = tree; ; return left; }; { /* * this function will update tree.size */ treesize = 1 + treeleft && treeleftsize || 0 + treeright && treerightsize || 0; }; // init local localrbstCompare = compare; localrbstCreate = create; localrbstFind = find; localrbstFindInKeyRange = findInKeyRange; localrbstInsert = insert; localrbstPrint = print; localrbstRemove = remove; }local; // run browser js-env code - test { var assert testCase_rbst_default; { /* * this function will, if passed is falsey, throw an error with the given data */ if !passed throw JSON; }; { options = options || {}; // create tree optionstree = local; -1 -05 0 0 1 2 3 false true '-1' '0' '1' 'a' 'b' null undefined {} // shuffle list ; // find console; optionsdata = local; console; ; console; optionsdata = local; console; ; // findInKeyRange console; optionsdata = ; local; console; ; // print local; // output: // options.tree // (ii,depth) key // (0,3) * * * -1 // (1,2) * * -0.5 // (2,5) * * * * * 0 // (3,4) * * * * 0 // (4,3) * * * 1 // (5,1) * 2 // (6,3) * * * 3 // (7,2) * * false // (8,0) true // (9,3) * * * "-1" // (10,5) * * * * * "0" // (11,4) * * * * "1" // (12,2) * * "a" // (13,1) * "b" // (14,2) * * null // (15,3) * * * [] // (16,4) * * * * null // (17,6) * * * * * * {} // (18,5) * * * * * undefined // height = 6 // remove optionstree = local; // print local; // coverage-hack - assert try ; catch ignore // coverage-hack - compare optionssymbolCreate = Symbol; optionsdata = local; ; // coverage-hack - remove optionstree = local; local; for optionsii = 0; optionsii < 0x100; optionsii += 1 // coverage-hack - insert if Math >= 05 optionstree = local; // coverage-hack - find local; local; optionsdata = ; local; optionsdata; // print // local.rbstPrint(options.tree); ; }; // run test ; }local;};
package.json
internal build-script
- build.sh
# build.sh # this shell script will run the build for this package shBuild