rbstCompare = function (aa,
bb) {
/*
* 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;
}
...
// coverage-hack - assert
try {
assert(false);
} catch (ignore) {
}
// coverage-hack - compare
options.symbolCreate = Symbol;
options.data = local.rbstCompare({}, options.symbolCreate());
assert(options.data === 0, options.data);
// coverage-hack - remove
options.tree = local.rbstRemove();
local.rbstFindInKeyRange(null, null, null, console.log);
for (options.ii = 0; options.ii < 0x100; options.ii += 1) {
// coverage-hack - insert
if (Math.random() >= 0.5) {
...
rbstCreate = function (key,
data) {
/*
* this function will create a tree with the given key and data
*/
return {
key: key,
data: data,
left: null,
right: null,
size: 1
};
}
...
throw new Error(JSON.stringify(data));
}
};
testCase_rbst_default = function (options, onError) {
options = options || {};
// create tree
options.tree = local.rbstCreate(null, null);
[
-1, -0.5, 0, 0, 1, 2, 3,
false, true,
'-1', '0', '1', 'a', 'b',
null, undefined, {}, []
]
// shuffle list
...
rbstFind = function (tree,
key) {
/*
* this function will find the node in the tree with the given key
*/
var node, tmp;
node = tree;
tmp = node && compare(node.key, key);
while (tmp) {
node = tmp === -1
? node.right
: node.left;
tmp = node && compare(node.key, key);
}
return node;
}
...
})
.forEach(function (key, data) {
// insert
options.tree = local.rbstInsert(options.tree, key, data);
});
// find
console.log('\nfind 0');
options.data = local.rbstFind(options.tree, 0);
console.log(options.data);
assert(options.data.key === 0, options.data);
console.log('\nfind undefined');
options.data = local.rbstFind(options.tree, 'undefined');
console.log(options.data);
assert(options.data === null, options.data);
// findInKeyRange
...
rbstFindInKeyRange = function (tree,
aa,
bb,
fnc) {
/*
* 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 && compare(node.key, aa);
while (node) {
stack.push(node);
node = tmp === -1
? node.right
: node.left;
tmp = node && compare(node.key, aa);
}
traversedList = stack.slice();
// find last node with key <= bb
sentinel = null;
node = tree;
tmp = compare(node.key, bb);
while (node) {
sentinel = node;
node = tmp === 1
? node.left
: node.right;
tmp = node && compare(node.key, bb);
}
sentinel = node || sentinel;
// begin traversal with first node with key >= aa
while (stack.length) {
node = stack.pop();
tmp = compare(node.key, bb);
if (compare(node.key, aa) >= 0 && compare(node.key, bb) <= 0) {
fnc(node);
}
// end traversal with last node with key <= bb
if (node === sentinel) {
return;
}
node = node.right;
if (traversedList.indexOf(node) < 0) {
while (node) {
stack.push(node);
node = node.left;
}
}
}
}
...
console.log('\nfind undefined');
options.data = local.rbstFind(options.tree, 'undefined');
console.log(options.data);
assert(options.data === null, options.data);
// findInKeyRange
console.log('\nfindInKeyRange [0, Infinity]');
options.data = [];
local.rbstFindInKeyRange(options.tree, 0, Infinity, function (node) {
options.data.push(node.key);
});
console.log(options.data);
assert(JSON.stringify(options.data) === '[0,0,1,2,3]', options.data);
// print
local.rbstPrint(options.tree);
// output:
...
rbstInsert = function (tree,
key,
data) {
/*
* this function will insert a new node in the tree with the given key and data,
* with random re-balancing
*/
if (!tree) {
return create(key, data);
}
if (Math.floor(Math.random() * 0x10000000000000) % (tree.size + 1) === 0 &&
typeof key !== 'object') {
return insertAsRoot(tree, key, data);
}
if (compare(key, tree.key) === -1) {
tree.left = insert(tree.left, key, data);
} else {
tree.right = insert(tree.right, key, data);
}
sizeUpdate(tree);
return tree;
}
...
]
// shuffle list
.sort(function () {
return Math.floor(Math.random() * 3) - 1;
})
.forEach(function (key, data) {
// insert
options.tree = local.rbstInsert(options.tree, key, data);
});
// find
console.log('\nfind 0');
options.data = local.rbstFind(options.tree, 0);
console.log(options.data);
assert(options.data.key === 0, options.data);
console.log('\nfind undefined');
...
rbstPrint = function (tree) {
/*
* this function will print the tree
*/
var height, ii, recurse;
recurse = function (tree, depth) {
if (!tree) {
return;
}
recurse(tree.left, depth + '* ');
ii += 1;
if (depth > height) {
height = depth;
}
console.log('(' + ii + ',' + (depth.length / 2) + ',' + tree.size + ') ' +
depth + JSON.stringify(tree.key));
recurse(tree.right, depth + '* ');
};
height = '';
ii = -1;
console.log('\ntree\n(ii,depth,size) key');
recurse(tree, '');
console.log('height = ' + height.length / 2);
}
...
options.data = [];
local.rbstFindInKeyRange(options.tree, 0, Infinity, function (node) {
options.data.push(node.key);
});
console.log(options.data);
assert(JSON.stringify(options.data) === '[0,0,1,2,3]', options.data);
// print
local.rbstPrint(options.tree);
// output:
// options.tree
// (ii,depth) key
// (0,3) * * * -1
// (1,2) * * -0.5
// (2,5) * * * * * 0
// (3,4) * * * * 0
...
rbstRemove = function (tree,
key) {
/*
* this function will remove the node in the tree with the given key
*/
if (!tree) {
return tree;
}
if (tree.key === key) {
return join(tree.left, tree.right);
}
if (compare(key, tree.key) === -1) {
tree.left = remove(tree.left, key);
} else {
tree.right = remove(tree.right, key);
}
sizeUpdate(tree);
return tree;
}
...
// (14,2) * * null
// (15,3) * * * []
// (16,4) * * * * null
// (17,6) * * * * * * {}
// (18,5) * * * * * undefined
// height = 6
// remove
options.tree = local.rbstRemove(options.tree, true);
// print
local.rbstPrint(options.tree);
// coverage-hack - assert
try {
assert(false);
} catch (ignore) {
}
...