/**
* @class Abstract algorithm
* @author Jakub Melezinek
*
* @constructor
* @abstract
* @protected
* @param {btv.BinaryTree} tree
* @param {btv.Visualiser} visualiser
* @param {Boolean} [isSubalgorithm] Set true if this algorithm is part of another algorithm.
*/
btv.AbstractAlgorithm = function(tree, visualiser, isSubalgorithm) {
/**
* @protected
* @type {btv.BinaryTree}
*/
this.tree = tree;
/**
* @protected
* @type {btv.BinaryTree}
*/
this.treeCopy = btv.AbstractAlgorithm.copyTree(this.tree);
// assistant variables; reset for new call
this.tree.selectedNode = undefined;
/**
* @protected
* @type {btv.Visualiser}
*/
this.visualiser = visualiser;
/**
* True if algorithm is called from another algorithm.
*
* @protected
* @type {Boolean}
*/
this.isSubalgorithm = Boolean(isSubalgorithm);
/**
* Listeners that are invoked at the start of animation chain.
*
* @protected
* @type {jsgl.util.ArrayList}
*/
this.startAnimationListeners = new jsgl.util.ArrayList();
/**
* Listeners that are invoked at the end of animation chain.
*
* @protected
* @type {jsgl.util.ArrayList}
*/
this.endAnimationListeners = new jsgl.util.ArrayList();
/**
* @private
* @type {Number}
*/
this.redoCalls = 0;
}
//btv.AbstractAlgorithm.prototype.redoCalls = 0;
/**
* Create a copy of given tree.
*
* @protected
* @param {btv.BinaryTree} tree
* @returns {btv.BinaryTree}
*/
btv.AbstractAlgorithm.copyTree = function(tree) {
if(tree == null) {
return null;
}
var treeCopy = new btv.BinaryTree("copy");
if(tree.getRoot() !== null) { // not null => not an empty tree
// copy of a root node
treeCopy.setRoot(new btv.BinaryTreeNode(tree.getRoot().getValue()));
// recursively copy the rest of tree - preorder
btv.AbstractAlgorithm.copyNodeRec(tree.getRoot().getLeft(), tree.getRoot().getRight(), treeCopy.getRoot());
}
/*
// copy of an inserted node
if(tree.insertedNode != null) { // undefined or null
treeCopy.insertedNode = new btv.BinaryTreeNode(tree.insertedNode.getValue());
} else {
treeCopy.insertedNode = null;
}
*/
// copy of reference to selected node
if(tree.selectedNode != null) { // null or undefined
var index = tree.selectedNode.getIndex();
treeCopy.selectedNode = treeCopy.getNode(index);
} else {
treeCopy.selectedNode = null;
}
return treeCopy;
}
/**
* Copy given node recursively.
*
* @protected
* @param {btv.BinaryTreeNode} leftChildSource
* @param {btv.BinaryTreeNode} rightChildSource
* @param {btv.BinaryTreeNOde} parentCopy
*/
btv.AbstractAlgorithm.copyNodeRec = function(leftChildSource, rightChildSource, parentCopy) {
if(leftChildSource != null) {
// clone/copy
parentCopy.setLeft(new btv.BinaryTreeNode(leftChildSource.getValue()));
// recurse
btv.AbstractAlgorithm.copyNodeRec(leftChildSource.getLeft(), leftChildSource.getRight(), parentCopy.getLeft());
}
if(rightChildSource != null) {
// clone/copy
parentCopy.setRight(new btv.BinaryTreeNode(rightChildSource.getValue()));
// recurse
btv.AbstractAlgorithm.copyNodeRec(rightChildSource.getLeft(), rightChildSource.getRight(), parentCopy.getRight());
}
}
/**
* Routine at start of each redo function.
*
* @protected
*/
btv.AbstractAlgorithm.prototype.redoStart = function() {
this.redoCalls++;
// fire start animation listeners
this.visualiser.animateStart(this);
if(!this.isSubalgorithm) {
// remove arrayElement
this.visualiser.animateRemoveArrayElem();
}
if(this.treeCopy.selectedNode != null) { // select selected node
// get index of selected node
var selectedIndex = this.treeCopy.selectedNode.getIndex();
// get selected node
var selectedNode = this.tree.getNode(selectedIndex);
// if not selected select and show tree, othervise no selection nor showing is needed
if(this.visualiser.selectedNode !== selectedNode) {
this.visualiser.animateShowSelectNode(selectedNode);
}
this.node = selectedNode;
} else { // this algorithm does not have a node as input value
this.visualiser.animateSelectNode(null);
this.node = null;
}
}
/**
* Routine at end of each redo function.
*
* @protected
* @param {Boolean} [show]
*/
btv.AbstractAlgorithm.prototype.redoEnd = function(show) {
if(show == null || show == true) {
// show resultant tree
this.visualiser.animateShowTree();
}
// add animator that fire end animation listeners
this.visualiser.animateEnd(this);
}
/**
* Adds a listener function to be invoked when the chain of animations starts.
*
* @public
* @param {Function}
*/
btv.AbstractAlgorithm.prototype.addStartAnimationListener = function(listener) {
this.startAnimationListeners.add(listener);
}
/**
* Removes a listener function.
*
* @public
* @param {Function}
*/
btv.AbstractAlgorithm.prototype.removeStartAnimationListener = function(listener) {
this.startAnimationListeners.remove(listener);
}
/**
* Invokes all registered listener functions.
*
* @protected
*/
btv.AbstractAlgorithm.prototype.fireStartAnimationListeners = function() {
var count = this.startAnimationListeners.getCount();
for(var i = 0; i < count; i++) {
this.startAnimationListeners.get(i)();
}
}
/**
* Adds a listener function to be invoked when the chain of animations ends.
*
* @public
* @param {Function}
*/
btv.AbstractAlgorithm.prototype.addEndAnimationListener = function(listener) {
this.endAnimationListeners.add(listener);
}
/**
* Removes a listener function.
*
* @public
* @param {Function}
*/
btv.AbstractAlgorithm.prototype.removeEndAnimationListener = function(listener) {
this.endAnimationListeners.remove(listener);
}
/**
* Invokes all registered listener functions.
*
* @protected
*/
btv.AbstractAlgorithm.prototype.fireEndAnimationListeners = function() {
var count = this.endAnimationListeners.getCount();
for(var i = 0; i < count; i++) {
this.endAnimationListeners.get(i)();
}
}
/**
* Makes changes on the tree (do the algoritm) and fill the animatorsArray.
*
* @abstract
* @protected
*/
btv.AbstractAlgorithm.prototype.redo = function() {
throw new btv.AlgorithmException("Abstract function");
}
/**
* Makes changes on the tree (undo the algoritm) - set the tree to state before this algorithm was done (executed).
*
* @protected
*/
btv.AbstractAlgorithm.prototype.undo = function() {
// create copy of treeCopy to set as the tree
var copy = btv.AbstractAlgorithm.copyTree(this.treeCopy);
// set copy of treeCopy as the tree
this.tree.setRoot(copy.getRoot());
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
/**
* @class
* @author Jakub Melezinek
*
* @constructor
* @private
* @param {btv.BinaryTree} tree
* @param {btv.Visualiser} visualiser
* @param {Number} min
* @param {Number} max
* @param {Boolean} [isSubalgorithm]
* @extends btv.AbstractAlgorithm
*/
btv.bst.RandomBSTreeAlg = function(tree, visualiser, min, max, isSubalgorithm) {
/*
* @private
* @type {Number}
*/
this.min = min;
/*
* @private
* @type {Number}
*/
this.max = max;
// parent constructor
btv.AbstractAlgorithm.call(this, tree, visualiser, isSubalgorithm);
}
btv.bst.RandomBSTreeAlg.jsglExtend(btv.AbstractAlgorithm);
/**
* @override
* @public
*/
btv.bst.RandomBSTreeAlg.prototype.redo = function() {
// routine
this.redoStart();
if(this.redoCalls > 1) { // repeated call - dont generate new random tree
var copy = btv.AbstractAlgorithm.copyTree(this.randomtreeCopy);
this.tree.setRoot(copy.getRoot());
} else { // first call
var epsilon = (this.max - this.min)/4;
this.tree.setRoot(new btv.BinaryTreeNode(btv.getRandomInt(Math.floor(this.min+epsilon), Math.ceil(this.max-epsilon))));
this.rec(this.tree.getRoot(), 1, this.min, this.max);
this.randomtreeCopy = btv.AbstractAlgorithm.copyTree(this.tree);
}
this.visualiser.redrawTree(this.tree);
// routine
this.redoEnd();
}
/**
* @private
*/
btv.bst.RandomBSTreeAlg.prototype.rec = function(node, level, min, max) {
if(min >= node.getValue() - 1 || node.getValue() + 1 >= max) { // safety
return;
}
var chance;
if(level <= 3 && Math.random() < 0.5) { // make both child - generated tree is fuller
chance = 1.0;
} else {
switch(level) {
case 1:
chance = 0.95;
break;
case 2:
chance = 0.7;
break;
case 3:
chance = 0.4;
break;
case 4:
chance = 0.2;
break;
default:
chance = 0.0; // no node at higher levels
break;
}
}
var epsilon;
// left child
if(chance > Math.random()) {
//node.setLeft(new btv.BinaryTreeNode(btv.getRandomInt(Math.floor(min + epsilon), Math.ceil(node.getValue() - epsilon))));
epsilon = Math.round((node.getValue() - min)/2);
node.setLeft(new btv.BinaryTreeNode(btv.getRandomInt(min + epsilon, node.getValue() - 1)));
if(node.getLeft().getValue() == min) {
min += 1;
}
this.rec(node.getLeft(), level + 1, min, node.getValue() - 1);
}
// right child
if(chance > Math.random()) {
//node.setRight(new btv.BinaryTreeNode(btv.getRandomInt(Math.floor(node.getValue() + epsilon), Math.ceil(max - epsilon))));
epsilon = Math.round((max - node.getValue())/2);
node.setRight(new btv.BinaryTreeNode(btv.getRandomInt(node.getValue() + 1, max - epsilon )));
if(node.getRight().getValue() == max) {
max -= 1;
}
this.rec(node.getRight(), level + 1, node.getValue() + 1, max);
}
}
/**
* @override
* @public
*/
btv.bst.RandomBSTreeAlg.prototype.toString = function() {
var array = this.tree.toArray();
var str = "randomBSTree(";
for(var i = 0; i < array.length; i++) {
if(i != 0) {
str += ", ";
}
if(array[i] == null) {
str += "n";
} else {
str += array[i].getValue();
}
}
str += ")"
return str;
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
/**
* @class
* @author Jakub Melezinek
*
* @constructor
* @public
* @param {btv.BinaryTree} tree
* @param {btv.Visualiser} visualiser
* @param {Number} value
* @param {Boolean} [isSubalgorithm]
* @extends btv.AbstractAlgorithm
*/
btv.bst.InsertAlg = function(tree, visualiser, value, isSubalgorithm) {
/**
* @private
* @type {Number}
*/
this.value = value;
// parent constructor
btv.AbstractAlgorithm.call(this, tree, visualiser, isSubalgorithm);
}
btv.bst.InsertAlg.jsglExtend(btv.AbstractAlgorithm);
/**
* @override
* @public
*/
btv.bst.InsertAlg.prototype.redo = function() {
// routine
this.redoStart();
// remove grapgic node - necessary if skip backward and the graphic was already added
this.visualiser.animateRemoveNode(this.node);
this.node = new btv.BinaryTreeNode(this.value);
// show the new graphic node
this.visualiser.animateShowNodeElemNextTo(this.node, 0);
var node = this.tree.getRoot();
if(node === null) { // root is null -> empty tree -> insert root
// logic
this.tree.setRoot(this.node);
// move the graphic node
// has no parent, not needed edgeElement
this.visualiser.animateMoveTo(this.node, 0);
} else {
while(true) {
if(this.node.getValue() >= node.getValue()) { // right
// visualisation of comparison
this.visualiser.animateShowComparSign(this.node, true, node);
if(node.getRight() === null) { // insert
node.setRight(this.node);
// move the graphic node
this.visualiser.animateMoveTo(this.node, 2*node.getIndex() + 2);
// show the graphic node parent edge
this.visualiser.animateAddEdgeElem(this.node);
break;
} else { // next comparison
node = node.getRight();
// move the graphic node
this.visualiser.animateMoveNextTo(this.node, node);
}
} else { // left
// visualisation of comparison
this.visualiser.animateShowComparSign(this.node, false, node);
if(node.getLeft() === null) { // insert
node.setLeft(this.node);
// move the graphic node
this.visualiser.animateMoveTo(this.node, 2*node.getIndex() + 1);
// show the graphic node parent edge
this.visualiser.animateAddEdgeElem(this.node);
break;
} else { // next comparison
node = node.getLeft();
// move the graphic node
this.visualiser.animateMoveNextTo(this.node, node);
}
}
}
}
this.visualiser.animateSelectNode(null);
// routine
this.redoEnd();
}
/**
* @override
* @public
*/
btv.bst.InsertAlg.prototype.toString = function() {
return "insert(value: " + this.value + ")";
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
/**
* @class
* @author Jakub Melezinek
*
* @constructor
* @throws {btv.AlgorithmException} Throws an exception if BinaryTreeNode wasn't created - invalid value.
* @param {btv.BinaryTree} tree
* @param {btv.Visualiser} visualiser
* @param {Number} value
* @param {Boolean} [isSubalgorithm]
* @extends btv.AbstractAlgorithm
*/
btv.bst.FindAlg = function(tree, visualiser, value, isSubalgorithm) {
/**
* @private
* @type {Number}
*/
this.value = value;
// parent constructor
btv.AbstractAlgorithm.call(this, tree, visualiser, isSubalgorithm);
}
btv.bst.FindAlg.jsglExtend(btv.AbstractAlgorithm);
/**
* @override
* @public
*/
btv.bst.FindAlg.prototype.redo = function() {
// routine
this.redoStart();
// remove grapgic node - necessary if skip backward and the graphic was already added
this.visualiser.animateRemoveNode(this.node);
this.node = new btv.BinaryTreeNode(this.value);
// show the new graphic node
//this.visualiser.animateShowAssistNodeElemNextTo(this.node, 0);
this.node.selectable = false;
this.visualiser.animateShowNodeElemNextTo(this.node, 0);
var node = this.tree.getRoot();
if(node === null) { // root is null -> empty tree -> not found
this.visualiser.animateShowRemoveNode(this.node);
this.visualiser.animateSelectNode(null); // deselect all
// routine
this.redoEnd();
return null;
} else {
while(true) {
if(this.node.getValue() == node.getValue()) { // found
this.visualiser.animateShowComparSign(this.node, 0, node);
this.visualiser.animateMoveTo(this.node, node.getIndex());
this.visualiser.animateRemoveNode(this.node);
this.visualiser.animateSelectNode(node); // select founded
// routine
this.redoEnd();
return node;
}
if(this.node.getValue() > node.getValue()) { // right
// visualisation of comparison
this.visualiser.animateShowComparSign(this.node, 1, node);
if(node.getRight() === null) { // not found
this.visualiser.animateMoveNextTo(this.node, node.getIndex()*2 + 2);
break;
} else { // next comparison
node = node.getRight();
// move the graphic node
this.visualiser.animateMoveNextTo(this.node, node);
}
} else { // left
// visualisation of comparison
this.visualiser.animateShowComparSign(this.node, -1, node);
if(node.getLeft() === null) { // not found
this.visualiser.animateMoveNextTo(this.node, node.getIndex()*2 + 1);
break;
} else { // next comparison
node = node.getLeft();
// move the graphic node
this.visualiser.animateMoveNextTo(this.node, node);
}
}
}
// after break - not found
this.visualiser.animateShowRemoveNode(this.node);
this.visualiser.animateSelectNode(null); // deselect all
// routine
this.redoEnd();
return null;
}
}
/**
* @override
* @public
*/
btv.bst.FindAlg.prototype.toString = function() {
return "find(value: " + this.value + ")";
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
/**
* @class
* @author Jakub Melezinek
*
* @constructor
* @param {btv.BinaryTree} tree
* @param {btv.Visualiser} visualiser
* @param {btv.BinaryTreeNode} node
* @param {Boolean} [isSubalgorithm]
* @extends btv.AbstractAlgorithm
*/
btv.bst.DeleteAlg = function(tree, visualiser, node, isSubalgorithm) {
/**
* @private
* @type {btv.BinaryTreeNode}
*/
this.node = node;
// copy of this reference will be created in the parent constructor - copy of given tree
tree.selectedNode = this.node;
// parent constructor
btv.AbstractAlgorithm.call(this, tree, visualiser, isSubalgorithm);
}
btv.bst.DeleteAlg.jsglExtend(btv.AbstractAlgorithm);
/**
* @override
* @public
*/
btv.bst.DeleteAlg.prototype.redo = function() {
// routine
this.redoStart();
if(this.node.getLeft() !== null && this.node.getRight() !== null) { // both children
// use getSuccessor() algorithm
var getSuccessorAlg = new btv.bst.GetSuccessorAlg(this.tree, this.visualiser, this.node, true);
var successor = getSuccessorAlg.redo();
// swap this.node with successor
this.tree.swapNodes(this.node, successor);
this.visualiser.animateSwapNodeElems(this.node, successor);
} // continue normally - delete node
// now just one or no child
if(this.node.getLeft() !== null) { // just left child
var leftSubtreeRoot = this.node.getLeft();
// grapgic - delete
this.visualiser.animateShowRemoveNode(this.node);
this.visualiser.animateRemoveElement(leftSubtreeRoot.edgeElement);
if(this.node.isRoot()) {
// logic
this.node.setLeft(null);
this.tree.setRoot(leftSubtreeRoot);
} else {
if(this.node.getParent().getLeft() == this.node) { // left child
// logic
this.node.getParent().setLeft(leftSubtreeRoot);
} else { // right child
// logic
this.node.getParent().setRight(leftSubtreeRoot);
}
}
var leftSubtreePreorderArray = btv.BinaryTree.toInorderArrayRec(leftSubtreeRoot);
// grapgic - move subtree
this.visualiser.animateMoveToIndexLoc(leftSubtreePreorderArray);
// graphic - add edge
this.visualiser.animateAddEdgeElem(leftSubtreeRoot, leftSubtreeRoot.getParent());
}
else if(this.node.getRight() !== null) { // just right child
var rightSubtreeRoot = this.node.getRight();
// grapgic - delete
this.visualiser.animateShowRemoveNode(this.node);
this.visualiser.animateRemoveElement(rightSubtreeRoot.edgeElement);
if(this.node.isRoot()) {
// logic
this.node.setRight(null);
this.tree.setRoot(rightSubtreeRoot);
} else {
if(this.node.getParent().getLeft() == this.node) { // left child
// logic
this.node.getParent().setLeft(rightSubtreeRoot);
} else { // right child
// logic
this.node.getParent().setRight(rightSubtreeRoot);
}
}
var rightSubtreePreorderArray = btv.BinaryTree.toInorderArrayRec(rightSubtreeRoot);
// grapgic - move subtree
this.visualiser.animateMoveToIndexLoc(rightSubtreePreorderArray);
// graphic - add edge
this.visualiser.animateAddEdgeElem(rightSubtreeRoot, rightSubtreeRoot.getParent());
}
else { // no child
if(this.node.isRoot()) {
// logic
this.tree.setRoot(null);
} else {
// logic
if(this.node.getParent().getLeft() === this.node) { // left child
this.node.getParent().setLeft(null);
} else { // right child
this.node.getParent().setRight(null);
}
}
// graphics
this.visualiser.animateShowRemoveNode(this.node);
}
this.visualiser.animateSelectNode(null);
// routine
this.redoEnd();
}
/**
* @override
* @public
*/
btv.bst.DeleteAlg.prototype.toString = function() {
return "delete(value: " + this.treeCopy.selectedNode.getValue() + ", index: " + this.treeCopy.selectedNode.getIndex() + ")";
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
/**
* @class
* @author Jakub Melezinek
*
* @constructor
* @param {btv.BinaryTree} tree
* @param {btv.Visualiser} visualiser
* @param {btv.BinaryTreeNode} node
* @param {Boolean} [isSubalgorithm]
* @extends btv.AbstractAlgorithm
*/
btv.bst.GetMaxAlg = function(tree, visualiser, node, isSubalgorithm) {
/**
* @private
* @type {btv.BinaryTreeNode}
*/
this.node = node;
// copy of this reference will be created in the parent constructor - copy of given tree
tree.selectedNode = this.node;
// parent constructor
btv.AbstractAlgorithm.call(this, tree, visualiser, isSubalgorithm);
}
btv.bst.GetMaxAlg.jsglExtend(btv.AbstractAlgorithm);
/**
* @override
* @public
*
* @returns {btv.BinaryTreeNode} maximum
*/
btv.bst.GetMaxAlg.prototype.redo = function() {
if(!this.isSubalgorithm) {
// routine
this.redoStart();
} else { // is called from another algorithm
this.redoCalls++;
// add animator that fire start animation listeners
this.visualiser.animateStart(this);
// select selected node
// get index of selected node
var selectedIndex = this.treeCopy.selectedNode.getIndex();
// get selected node
var selectedNode = this.tree.getNode(selectedIndex);
this.node = selectedNode;
}
var node;
var searchNode;
searchNode = new btv.BinaryTreeNode(String.fromCharCode(8664));
this.visualiser.animateAddAssistNodeElemNextTo(searchNode, this.node);
// find the most right node - maximum
node = this.node;
if(node.getRight() === null) { // to show that I try ro go right
this.visualiser.animateShowChangeAssistNode(searchNode, String.fromCharCode(8664), false);
}
while(node.getRight() !== null) {
node = node.getRight();
this.visualiser.animateShowChangeAssistNode(searchNode, String.fromCharCode(8664), false);
this.visualiser.animateMoveNextTo(searchNode, node);
}
// no more right children
this.visualiser.animateShowChangeAssistNode(searchNode, String.fromCharCode(8664), false);
this.visualiser.animateShowChangeAssistNode(searchNode, String.fromCharCode(8664), true);
this.visualiser.animateMoveTo(searchNode, node.getIndex());
this.visualiser.animateRemoveNode(searchNode);
// select predecessor
this.visualiser.animateSelectNode(node);
if(!this.isSubalgorithm) {
// routine
this.redoEnd();
} else {
// routine, but not show
this.redoEnd(false);
}
return node; // max found
}
/**
* @override
* @public
*/
btv.bst.GetMaxAlg.prototype.toString = function() {
return "getMax(value: " + this.treeCopy.selectedNode.getValue() + ", index: " + this.treeCopy.selectedNode.getIndex() + ")";
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
/**
* @class
* @author Jakub Melezinek
*
* @constructor
* @param {btv.BinaryTree} tree
* @param {btv.Visualiser} visualiser
* @param {btv.BinaryTreeNode} node
* @param {Boolean} [isSubalgorithm]
* @extends btv.AbstractAlgorithm
*/
btv.bst.GetMinAlg = function(tree, visualiser, node, isSubalgorithm) {
/**
* @private
* @type {btv.BinaryTreeNode}
*/
this.node = node;
// copy of this reference will be created in the parent constructor - copy of given tree
tree.selectedNode = this.node;
// parent constructor
btv.AbstractAlgorithm.call(this, tree, visualiser, isSubalgorithm);
}
btv.bst.GetMinAlg.jsglExtend(btv.AbstractAlgorithm);
/**
* @override
* @public
*
* @returns {btv.BinaryTreeNode} minimum
*/
btv.bst.GetMinAlg.prototype.redo = function() {
if(!this.isSubalgorithm) {
// routine
this.redoStart();
} else { // is called from another algorithm
this.redoCalls++;
// add animator that fire start animation listeners
this.visualiser.animateStart(this);
// select selected node
// get index of selected node
var selectedIndex = this.treeCopy.selectedNode.getIndex();
// get selected node
var selectedNode = this.tree.getNode(selectedIndex);
this.node = selectedNode;
}
var node;
var searchNode;
searchNode = new btv.BinaryTreeNode(String.fromCharCode(8665));
this.visualiser.animateAddAssistNodeElemNextTo(searchNode, this.node);
node = this.node;
if(node.getLeft() === null) { // to show that I try ro go left
this.visualiser.animateShowChangeAssistNode(searchNode, String.fromCharCode(8665), false);
}
while(node.getLeft() !== null) {
node = node.getLeft();
this.visualiser.animateShowChangeAssistNode(searchNode, String.fromCharCode(8665), false);
this.visualiser.animateMoveNextTo(searchNode, node);
}
// no more left children
this.visualiser.animateShowChangeAssistNode(searchNode, String.fromCharCode(8665), false);
this.visualiser.animateShowChangeAssistNode(searchNode, String.fromCharCode(8665), true);
this.visualiser.animateMoveTo(searchNode, node.getIndex());
this.visualiser.animateRemoveNode(searchNode);
// select predecessor
this.visualiser.animateSelectNode(node);
// this.redoEnd(!this.isSubalgorithm);
if(!this.isSubalgorithm) {
// routine
this.redoEnd();
} else {
// routine but not show
this.redoEnd(false);
}
return node; // founded min
}
/**
* @override
* @public
*/
btv.bst.GetMinAlg.prototype.toString = function() {
return "getMin(value: " + this.treeCopy.selectedNode.getValue() + ", index: " + this.treeCopy.selectedNode.getIndex() + ")";
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
/**
* @class
* @author Jakub Melezinek
*
* @constructor
* @param {btv.BinaryTree} tree
* @param {btv.Visualiser} visualiser
* @param {btv.BinaryTreeNode} node
* @param {Boolean} [isSubalgorithm]
* @extends btv.AbstractAlgorithm
*/
btv.bst.GetPredecessorAlg = function(tree, visualiser, node, isSubalgorithm) {
/**
* @private
* @type {btv.BinaryTreeNode}
*/
this.node = node;
// copy of this reference will be created in the parent constructor - copy of given tree
tree.selectedNode = this.node;
// parent constructor
btv.AbstractAlgorithm.call(this, tree, visualiser, isSubalgorithm);
}
btv.bst.GetPredecessorAlg.jsglExtend(btv.AbstractAlgorithm);
/**
* @override
* @public
*
* @returns {btv.BinaryTreeNode} predecessor
*/
btv.bst.GetPredecessorAlg.prototype.redo = function() {
// routine
this.redoStart();
var parent;
var node;
var searchNode = new btv.BinaryTreeNode(String.fromCharCode(8665));
this.visualiser.animateShowAssistNodeElemNextTo(searchNode, this.node);
node = this.node.getLeft();
if(node !== null) { // has left subtree
// move next to left child
this.visualiser.animateMoveNextTo(searchNode, node);
this.visualiser.animateRemoveNode(searchNode);
// use getMax algoritm as part of that algorithm
var getMaxAlg = new btv.bst.GetMaxAlg(this.tree, this.visualiser, node, true);
var returnedValue = getMaxAlg.redo();
// routine
this.redoEnd();
return returnedValue;
}
else {
// no left subtree
this.visualiser.animateShowChangeAssistNode(searchNode, String.fromCharCode(8665), true);
// for first parent to that arrives from right
node = this.node;
parent = this.node.getParent();
while(true) {
if(parent === null) { // no predecessor
// try to go to the top
this.visualiser.animateShowChangeAssistNode(searchNode, String.fromCharCode(8657), false);
this.visualiser.animateShowChangeAssistNode(searchNode, String.fromCharCode(8657), true);
// hide searchNode
this.visualiser.animateShowRemoveNode(searchNode);
// unselect all
this.visualiser.animateSelectNode(null);
// routine
this.redoEnd();
return null; // no predecessor found
}
// have to search at the top
this.visualiser.animateShowChangeAssistNode(searchNode, String.fromCharCode(8657), false);
// move nextTo parent if exists
this.visualiser.animateMoveNextTo(searchNode, parent);
if(parent.getRight() === node) { // arrived from right
// from right
this.visualiser.animateShowChangeAssistNode(searchNode, String.fromCharCode(8598), false);
// moveTo
this.visualiser.animateMoveTo(searchNode, parent.getIndex());
this.visualiser.animateRemoveNode(searchNode);
// select predecessor
this.visualiser.animateSelectNode(parent);
// routine
this.redoEnd();
return parent; // predecessor found
} else {
// not from right
this.visualiser.animateShowChangeAssistNode(searchNode, String.fromCharCode(8598), true);
}
// next loop
node = parent;
parent = parent.getParent();
}
}
}
/**
* @override
* @public
*/
btv.bst.GetPredecessorAlg.prototype.toString = function() {
return "getPredecessor(value: " + this.treeCopy.selectedNode.getValue() + ", index: " + this.treeCopy.selectedNode.getIndex() + ")";
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
/**
* @class
* @author Jakub Melezinek
*
* @constructor
* @param {btv.BinaryTree} tree
* @param {btv.Visualiser} visualiser
* @param {btv.BinaryTreeNode} node
* @param {Boolean} [isSubalgorithm]
* @extends btv.AbstractAlgorithm
*/
btv.bst.GetSuccessorAlg = function(tree, visualiser, node, isSubalgorithm) {
/**
* @private
* @type {btv.BinaryTreeNode}
*/
this.node = node;
// copy of this reference will be created in the parent constructor - copy of given tree
tree.selectedNode = this.node;
// parent constructor
btv.AbstractAlgorithm.call(this, tree, visualiser, isSubalgorithm);
}
btv.bst.GetSuccessorAlg.jsglExtend(btv.AbstractAlgorithm);
/**
* @override
* @public
*
* @returns {btv.BinaryTreeNode} successor
*/
btv.bst.GetSuccessorAlg.prototype.redo = function() {
// routine
this.redoStart();
var parent;
var node;
var searchNode = new btv.BinaryTreeNode(String.fromCharCode(8664));
this.visualiser.animateShowAssistNodeElemNextTo(searchNode, this.node);
node = this.node.getRight();
if(node !== null) { // has right subtree
// move next to left child
this.visualiser.animateMoveNextTo(searchNode, node);
this.visualiser.animateRemoveNode(searchNode);
// use getMin algoritm as part of that algorithm
var getMinAlg = new btv.bst.GetMinAlg(this.tree, this.visualiser, node, true);
// and do it // add EndAnimator
var returnedValue = getMinAlg.redo();
// routine
this.redoEnd();
return returnedValue;
} else {
// no rigt subtree
this.visualiser.animateShowChangeAssistNode(searchNode, String.fromCharCode(8664), true);
// for first parent to that arrives from left
node = this.node;
parent = this.node.getParent();
while (true) {
if(parent === null) { // no parent
// no node at the top
this.visualiser.animateShowChangeAssistNode(searchNode, String.fromCharCode(8657), false);
this.visualiser.animateShowChangeAssistNode(searchNode, String.fromCharCode(8657), true);
// hide searchNode
this.visualiser.animateShowRemoveNode(searchNode);
// unselect all
this.visualiser.animateSelectNode(null);
// routine
this.redoEnd();
return null; // no successor found
}
// have to search at the top
this.visualiser.animateShowChangeAssistNode(searchNode, String.fromCharCode(8657), false);
// move nextTo parent if exists
this.visualiser.animateMoveNextTo(searchNode, parent);
if(parent.getLeft() === node) { // arrived from left
// from left
this.visualiser.animateShowChangeAssistNode(searchNode, String.fromCharCode(8599), false);
// moveTo
this.visualiser.animateMoveTo(searchNode, parent.getIndex());
this.visualiser.animateRemoveNode(searchNode);
// select successor
this.visualiser.animateSelectNode(parent);
// routine
this.redoEnd();
return parent; // successor found
} else {
// not from right
this.visualiser.animateShowChangeAssistNode(searchNode, String.fromCharCode(8599), true);
}
// next loop
node = parent;
parent = parent.getParent();
}
}
}
/**
* @override
* @public
*/
btv.bst.GetSuccessorAlg.prototype.toString = function() {
return "getSuccessor(value: " + this.treeCopy.selectedNode.getValue() + ", index: " + this.treeCopy.selectedNode.getIndex() + ")";
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
/**
* @class
* @author Jakub Melezinek
*
* @constructor
* @param {btv.BinaryTree} tree
* @param {btv.Visualiser} visualiser
* @param {Boolean} [isSubalgorithm]
* @extends btv.AbstractAlgorithm
*/
btv.bst.ToPreorderArrayAlg = function(tree, visualiser, isSubalgorithm) {
/**
* Assistant graphic node acceessable from all functions.
*
* @private
*/
this.moveNode = null;
// parent constructor
btv.AbstractAlgorithm.call(this, tree, visualiser, isSubalgorithm);
}
btv.bst.ToPreorderArrayAlg.jsglExtend(btv.AbstractAlgorithm);
/**
* @override
* @public
*/
btv.bst.ToPreorderArrayAlg.prototype.redo = function() {
var array = new Array();
// routine
this.redoStart();
// add array element
this.visualiser.animateAddArrayElem(this.tree.getCount());
// create moveNode
this.moveNode = new btv.BinaryTreeNode(String.fromCharCode(8659));
this.visualiser.animateShowAssistNodeElemNextTo(this.moveNode, 0);
var node = this.tree.getRoot();
if(node === null) {
// show struck through move node
this.visualiser.animateShowChangeAssistNode(this.moveNode, String.fromCharCode(8659), true);
// hide move node
this.visualiser.animateShowRemoveNode(this.moveNode);
// routine
this.redoEnd();
return array;
}
this.rec(node, array);
// leave tree - change label
this.visualiser.animateShowChangeAssistNode(this.moveNode, String.fromCharCode(8657));
// remove move node
this.visualiser.animateRemoveNode(this.moveNode);
// routine
this.redoEnd();
return array;
}
/**
* @private
*/
btv.bst.ToPreorderArrayAlg.prototype.recLeft = function (node, array) {
// change label
this.visualiser.animateShowChangeAssistNode(this.moveNode, String.fromCharCode(8665));
if(node === null) {
// change label
this.visualiser.animateShowChangeAssistNode(this.moveNode, String.fromCharCode(8665), true);
return;
}
// move
this.visualiser.animateMoveNextTo(this.moveNode, node);
this.rec(node, array);
}
/**
* @private
*/
btv.bst.ToPreorderArrayAlg.prototype.recRight = function (node, array) {
// change label
this.visualiser.animateShowChangeAssistNode(this.moveNode, String.fromCharCode(8664));
if(node === null) {
// change label
this.visualiser.animateShowChangeAssistNode(this.moveNode, String.fromCharCode(8664), true);
return;
}
// move
this.visualiser.animateMoveNextTo(this.moveNode, node);
this.rec(node, array);
}
/**
* @private
*/
btv.bst.ToPreorderArrayAlg.prototype.rec = function (node, array) {
// change label
this.visualiser.animateChangeAssistNode(this.moveNode, "");
// show index node
var toArrayNode = new btv.BinaryTreeNode(node.getValue());
toArrayNode.selectable = false;
this.visualiser.animateShowNodeElemAt(toArrayNode, node);
// move index node to arrayElem
this.visualiser.animateMoveNextToArrayElem(toArrayNode);
// hide index node
this.visualiser.animateShowTree(0.25);
this.visualiser.animateRemoveNode(toArrayNode);
// show in array
array.push(node);
this.visualiser.animateShowInsertToArrayElem(node, array.length - 1);
this.recLeft(node.getLeft(), array);
// go up
if(node.getLeft() !== null) { // only if has left child, otherwise moveNode is still here
// change label
this.visualiser.animateShowChangeAssistNode(this.moveNode, String.fromCharCode(8657));
// move
this.visualiser.animateMoveNextTo(this.moveNode, node);
}
this.recRight(node.getRight(), array);
// go up
if(node.getRight() !== null) { // only if has right child, otherwise moveNode is still here
// change label
this.visualiser.animateShowChangeAssistNode(this.moveNode, String.fromCharCode(8657));
// move
this.visualiser.animateMoveNextTo(this.moveNode, node);
}
}
/**
* @override
* @public
*/
btv.bst.ToPreorderArrayAlg.prototype.toString = function() {
return "toPreorderArray()";
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
/**
* @class
* @author Jakub Melezinek
*
* @constructor
* @param {btv.BinaryTree} tree
* @param {btv.Visualiser} visualiser
* @param {Boolean} [isSubalgorithm]
* @extends btv.AbstractAlgorithm
*/
btv.bst.ToInorderArrayAlg = function(tree, visualiser, isSubalgorithm) {
/**
* Assistant graphic node acceessable from all functions.
*
* @private
*/
this.moveNode = null;
// parent constructor
btv.AbstractAlgorithm.call(this, tree, visualiser, isSubalgorithm);
}
btv.bst.ToInorderArrayAlg.jsglExtend(btv.AbstractAlgorithm);
/**
* @override
* @public
*/
btv.bst.ToInorderArrayAlg.prototype.redo = function() {
// reset states if play again etc
var array = new Array();
// routine
this.redoStart();
// add array element
this.visualiser.animateAddArrayElem(this.tree.getCount());
// create moveNode
this.moveNode = new btv.BinaryTreeNode(String.fromCharCode(8659));
this.visualiser.animateShowAssistNodeElemNextTo(this.moveNode, 0);
var node = this.tree.getRoot();
if(node === null) {
// show struck through move node
this.visualiser.animateShowChangeAssistNode(this.moveNode, String.fromCharCode(8659), true);
// hide move node
this.visualiser.animateShowRemoveNode(this.moveNode);
// routine
this.redoEnd();
return array;
}
this.rec(node, array);
// leave tree - change label
this.visualiser.animateShowChangeAssistNode(this.moveNode, String.fromCharCode(8657));
// remove move node
this.visualiser.animateRemoveNode(this.moveNode);
// routine
this.redoEnd();
return array;
}
/**
* @private
*/
btv.bst.ToInorderArrayAlg.prototype.recLeft = function (node, array) {
// change label
this.visualiser.animateShowChangeAssistNode(this.moveNode, btv.Visualiser.southWestDoubleArrow);
if(node === null) {
// change label
this.visualiser.animateShowChangeAssistNode(this.moveNode, btv.Visualiser.southWestDoubleArrow, true);
return;
}
// move
this.visualiser.animateMoveNextTo(this.moveNode, node);
this.rec(node, array);
}
/**
* @private
*/
btv.bst.ToInorderArrayAlg.prototype.recRight = function (node, array) {
// change label
this.visualiser.animateShowChangeAssistNode(this.moveNode, btv.Visualiser.southEastDoubleArrow);
if(node === null) {
// change label
this.visualiser.animateShowChangeAssistNode(this.moveNode, btv.Visualiser.southEastDoubleArrow, true);
return;
}
// move
this.visualiser.animateMoveNextTo(this.moveNode, node);
this.rec(node, array);
}
/**
* @private
*/
btv.bst.ToInorderArrayAlg.prototype.rec = function (node, array) {
// recursively
this.recLeft(node.getLeft(), array);
// go up
if(node.getLeft() !== null) { // only if has left child, otherwise moveNode is still here
// change label
this.visualiser.animateShowChangeAssistNode(this.moveNode, String.fromCharCode(8657));
// move
this.visualiser.animateMoveNextTo(this.moveNode, node);
}
// change label
this.visualiser.animateChangeAssistNode(this.moveNode, "");
// show index node
var toArrayNode = new btv.BinaryTreeNode(node.getValue());
toArrayNode.selectable = false;
this.visualiser.animateShowNodeElemAt(toArrayNode, node);
// move index node to arrayElem
this.visualiser.animateMoveNextToArrayElem(toArrayNode);
// hide index node
this.visualiser.animateShowTree(0.25);
this.visualiser.animateRemoveNode(toArrayNode);
// show in array
array.push(node);
this.visualiser.animateShowInsertToArrayElem(node, array.length - 1);
this.recRight(node.getRight(), array);
// go up
if(node.getRight() !== null) { // only if has right child, otherwise moveNode is still here
// change label
this.visualiser.animateShowChangeAssistNode(this.moveNode, String.fromCharCode(8657));
// move
this.visualiser.animateMoveNextTo(this.moveNode, node);
}
}
/**
* @override
* @public
*/
btv.bst.ToInorderArrayAlg.prototype.toString = function() {
return "toInorderArray()";
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
/**
* @class
* @author Jakub Melezinek
*
* @constructor
* @param {btv.BinaryTree} tree
* @param {btv.Visualiser} visualiser
* @param {Bolean} [isSubalgorithm]
* @extends btv.AbstractAlgorithm
*/
btv.bst.ToPostorderArrayAlg = function(tree, visualiser, isSubalgorithm) {
/**
* Assistant graphic node acceessable from all functions.
*
* @private
*/
this.moveNode = null;
// parent constructor
btv.AbstractAlgorithm.call(this, tree, visualiser, isSubalgorithm);
}
btv.bst.ToPostorderArrayAlg.jsglExtend(btv.AbstractAlgorithm);
/**
* @override
* @public
*/
btv.bst.ToPostorderArrayAlg.prototype.redo = function() {
var array = new Array();
// routine
this.redoStart();
// add array element
this.visualiser.animateAddArrayElem(this.tree.getCount());
// create moveNode
this.moveNode = new btv.BinaryTreeNode(String.fromCharCode(8659));
this.visualiser.animateShowAssistNodeElemNextTo(this.moveNode, 0);
var node = this.tree.getRoot();
if(node === null) {
// show struck through move node
this.visualiser.animateShowChangeAssistNode(this.moveNode, String.fromCharCode(8659), true);
// hide move node
this.visualiser.animateShowRemoveNode(this.moveNode);
// routine
this.redoEnd();
return array;
}
this.rec(node, array);
// leave tree - change label
this.visualiser.animateShowChangeAssistNode(this.moveNode, String.fromCharCode(8657));
// remove move node
this.visualiser.animateRemoveNode(this.moveNode);
// routine
this.redoEnd();
return array;
}
/**
* @private
*/
btv.bst.ToPostorderArrayAlg.prototype.recLeft = function (node, array) {
// change label
this.visualiser.animateShowChangeAssistNode(this.moveNode, btv.Visualiser.southWestDoubleArrow);
if(node === null) {
// change label
this.visualiser.animateShowChangeAssistNode(this.moveNode, btv.Visualiser.southWestDoubleArrow, true);
return;
}
// move
this.visualiser.animateMoveNextTo(this.moveNode, node);
this.rec(node, array);
}
/**
* @private
*/
btv.bst.ToPostorderArrayAlg.prototype.recRight = function (node, array) {
// change label
this.visualiser.animateShowChangeAssistNode(this.moveNode, btv.Visualiser.southEastDoubleArrow);
if(node === null) {
// change label
this.visualiser.animateShowChangeAssistNode(this.moveNode, btv.Visualiser.southEastDoubleArrow, true);
return;
}
// move
this.visualiser.animateMoveNextTo(this.moveNode, node);
this.rec(node, array);
}
/**
* @private
*/
btv.bst.ToPostorderArrayAlg.prototype.rec = function (node, array) {
// recursively
this.recLeft(node.getLeft(), array);
// go up
if(node.getLeft() !== null) { // only if has left child, otherwise moveNode is still here
// change label
this.visualiser.animateShowChangeAssistNode(this.moveNode, String.fromCharCode(8657));
// move
this.visualiser.animateMoveNextTo(this.moveNode, node);
}
this.recRight(node.getRight(), array);
// go up
if(node.getRight() !== null) { // only if has right child, otherwise moveNode is still here
// change label
this.visualiser.animateShowChangeAssistNode(this.moveNode, String.fromCharCode(8657));
// move
this.visualiser.animateMoveNextTo(this.moveNode, node);
}
// change label
this.visualiser.animateChangeAssistNode(this.moveNode, "");
// show index node
var toArrayNode = new btv.BinaryTreeNode(node.getValue());
toArrayNode.selectable = false;
this.visualiser.animateShowNodeElemAt(toArrayNode, node);
// move index node to arrayElem
this.visualiser.animateMoveNextToArrayElem(toArrayNode);
// hide index node
this.visualiser.animateShowTree(0.25);
this.visualiser.animateRemoveNode(toArrayNode);
// show in array
array.push(node);
this.visualiser.animateShowInsertToArrayElem(node, array.length - 1);
}
/**
* @override
* @public
*/
btv.bst.ToPostorderArrayAlg.prototype.toString = function() {
return "toPostorderArrayAlg()";
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
/**
* @class
* @author Jakub Melezinek
*
* @constructor
* @param {btv.BinaryTree} tree
* @param {btv.Visualiser} visualiser
* @param {btv.BinaryTreeNode} node
* @param {Boolean} [isSubalgorithm]
* @extends btv.AbstractAlgorithm
*/
btv.bh.HeapifyUpAlg = function(tree, visualiser, node, isSubalgorithm) {
/**
* @private
* @type {btv.BinaryTreeNode}
*/
this.node = node;
// copy of this reference will be created in the parent constructor - copy of given tree
tree.selectedNode = this.node;
// parent constructor
btv.AbstractAlgorithm.call(this, tree, visualiser, isSubalgorithm);
}
btv.bh.HeapifyUpAlg.jsglExtend(btv.AbstractAlgorithm);
/**
* @override
* @public
*/
btv.bh.HeapifyUpAlg.prototype.redo = function() {
// routine
this.redoStart(); // označí node
this.rec(this.node);
this.visualiser.animateSelectNode(null);
// routine
this.redoEnd(false); // don't show, always part of other alg
}
/**
* @private
*
* @parama {btv.BinaryTreeNode}
*/
btv.bh.HeapifyUpAlg.prototype.rec = function(node) {
var parent = node.getParent();
if(parent == null) {
return;
}
var difference = parent.getValue() - this.node.getValue();
if(parent.getLeft() === this.node) {
// comparing
this.visualiser.animateShowComparSign(this.node, -difference, parent);
} else {
// comparing
this.visualiser.animateShowComparSign(parent, difference, this.node);
}
if(difference >= 0) {
return;
} else { // swap
this.tree.swapNodes(this.node, parent);
// graphic swap
this.visualiser.animateSwapNodeElems(this.node, parent);
}
this.rec(this.node);
}
/**
* @override
* @public
*/
btv.bh.HeapifyUpAlg.prototype.toString = function() {
return "heapify-up(value: " + this.treeCopy.selectedNode.getValue() + ", index: " + this.treeCopy.selectedNode.getIndex() + ")";
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
/**
* @class
* @author Jakub Melezinek
*
* @constructor
* @param {btv.BinaryTree} tree
* @param {btv.Visualiser} visualiser
* @param {btv.BinaryTreeNode} node
* @param {Boolean} [isSubalgorithm]
* @extends btv.AbstractAlgorithm
*/
btv.bh.HeapifyDownAlg = function(tree, visualiser, node, isSubalgorithm) {
/**
* @private
* @type {btv.BinaryTreeNode}
*/
this.node = node;
// copy of this reference will be created in the parent constructor - copy of given tree
tree.selectedNode = this.node;
// parent constructor
btv.AbstractAlgorithm.call(this, tree, visualiser, isSubalgorithm);
}
btv.bh.HeapifyDownAlg.jsglExtend(btv.AbstractAlgorithm);
/**
* @override
* @public
*/
btv.bh.HeapifyDownAlg.prototype.redo = function() {
// routine
this.redoStart();
this.rec(this.node);
this.visualiser.animateSelectNode(null);
// routine
this.redoEnd(false); // don't show, always part of other alg
}
/**
* @private
*
* @parama {btv.BinaryTreeNode}
*/
btv.bh.HeapifyDownAlg.prototype.rec = function(node) {
var left = node.getLeft();
var right = node.getRight();
var greater;
if(node.isLeaf()) { // no child => end
return;
}
if(left != null && right != null) { // both child => compare child
if(left.getValue() >= right.getValue()) {
greater = left;
this.visualiser.animateShowComparSign(left, true, right);
} else {
greater = right;
this.visualiser.animateShowComparSign(left, false, right);
}
} else { // just left child
greater = left;
}
var difference = node.getValue() - greater.getValue();
if(greater === left) { // compare with left
this.visualiser.animateShowComparSign(greater, -difference, node);
} else { // compare with right
this.visualiser.animateShowComparSign(node, difference, greater);
}
if(difference < 0) {
this.tree.swapNodes(node, greater);
this.visualiser.animateSwapNodeElems(node, greater);
// recursion
this.rec(node);
}
}
/**
* @override
* @public
*/
btv.bh.HeapifyDownAlg.prototype.toString = function() {
return "heapify-down(value: " + this.treeCopy.selectedNode.getValue() + ", index: " + this.treeCopy.selectedNode.getIndex() + ")";
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
/**
* @class
* @author Jakub Melezinek
*
* @constructor
* @param {btv.BinaryTree} tree
* @param {btv.Visualiser} visualiser
* @param {Number} min
* @param {Number} max
* @param {Bolean} [isSubalgorithm]
* @throws {btv.AlgorithmException}
* @extends btv.AbstractAlgorithm
*/
btv.bh.RandomBHeapAlg = function(tree, visualiser, min, max, isSubalgorithm) {
if(min > max) {
throw new btv.AlgorithmException("Given minimum is greather than given maximum.");
}
/*
* @private
* @type {Number}
*/
this.min = min;
/*
* @private
* @type {Number}
*/
this.max = max;
// parent constructor
btv.AbstractAlgorithm.call(this, tree, visualiser, isSubalgorithm);
}
btv.bh.RandomBHeapAlg.jsglExtend(btv.AbstractAlgorithm);
/**
* @override
* @public
*/
btv.bh.RandomBHeapAlg.prototype.redo = function() {
// routine
this.redoStart();
if(this.redoCalls > 1) { // repeated call - dont generate new random tree
var copy = btv.AbstractAlgorithm.copyTree(this.randomHeapCopy);
this.tree.setRoot(copy.getRoot());
} else { // first call
var count = btv.getRandomInt(1, Math.min(this.max - this.min + 1, 31));
// generate array of random non identic numbers of scale
var numbers = new Array(this.max - this.min + 1);
var array = new Array();
for(var i = 0; i < count; i++) {
do{
array[i] = btv.getRandomInt(Math.ceil(this.min), Math.floor(this.max));
} while (numbers[array[i] - this.min] == true);
numbers[array[i] - this.min] = true;
}
// build heap from array
for(i = Math.floor(array.length/2) - 1; i >= 0; i--) {
this.arrayHeapify(array, i);
}
this.tree.build(array);
this.randomHeapCopy = btv.AbstractAlgorithm.copyTree(this.tree);
}
this.visualiser.redrawTree(this.tree);
// routine
this.redoEnd(true);
}
/**
* @private
*
* @param {Number[]} array
* @param {Number} index
*/
btv.bh.RandomBHeapAlg.prototype.arrayHeapify = function (array, index) {
var leftIndex = 2*index + 1;
var rightIndex = 2*index + 2;
var largestIndex;
if(leftIndex < array.length && array[leftIndex] > array[index]) {
largestIndex = leftIndex;
} else {
largestIndex = index;
}
if(rightIndex < array.length && array[rightIndex] > array[largestIndex]) {
largestIndex = rightIndex;
}
if(largestIndex != index) {
var tmp = array[largestIndex];
array[largestIndex] = array[index];
array[index] = tmp;
this.arrayHeapify(array, largestIndex);
}
}
/**
* @private
*
* @param {Number[]} array
* @param {Number} index
*/
btv.bh.RandomBHeapAlg.prototype.buildRec = function (array, index) {
}
/**
* @override
* @public
*/
btv.bh.RandomBHeapAlg.prototype.toString = function() {
var array = this.tree.toArray();
var str = "randomHeap(";
for(var i = 0; i < array.length; i++) {
if(i != 0) {
str += ", ";
}
str += array[i].getValue();
}
str += ")"
return str;
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
/**
* @class
* @author Jakub Melezinek
*
* @constructor
* @param {btv.BinaryTree} tree
* @param {btv.Visualiser} visualiser
* @param {Number[]} array
* @param {Boolean} [isSubalgorithm]
* @extends btv.AbstractAlgorithm
*/
btv.bh.BuildHeapAlg = function(tree, visualiser, array, isSubalgorithm) {
/*
* @private
* @type {Number[]}
*/
this.array = array;
// parent constructor
btv.AbstractAlgorithm.call(this, tree, visualiser, isSubalgorithm);
}
btv.bh.BuildHeapAlg.jsglExtend(btv.AbstractAlgorithm);
/**
* @override
* @public
*/
btv.bh.BuildHeapAlg.prototype.redo = function() {
// routine
this.redoStart();
var array = this.array.slice();
this.tree.build(array);
this.visualiser.redrawTree(this.tree);
this.visualiser.animateShowTree();
// build heap
for(i = Math.floor(array.length/2) - 1; i >= 0; i--) {
// use heapify algoritm as part of that algorithm
var heapifyAlg = new btv.bh.HeapifyDownAlg(this.tree, this.visualiser, this.tree.getNode(i), true);
heapifyAlg.redo();
}
this.visualiser.animateSelectNode(null);
// routine
this.redoEnd(false);
}
/**
* @override
* @public
*/
btv.bh.BuildHeapAlg.prototype.toString = function() {
var array = this.array;
var str = "buildHeap(";
for(var i = 0; i < array.length; i++) {
if(i != 0) {
str += ", ";
}
str += array[i];
}
str += ")"
return str;
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
/**
* @class
* @author Jakub Melezinek
*
* @constructor
* @throws {btv.AlgorithmException} Throws an exception if BinaryTreeNode wasn't created - invalid value.
* @param {btv.BinaryTree} tree
* @param {btv.Visualiser} visualiser
* @param {Number} value
* @param {Boolean} [isSubalgorithm]
* @extends btv.AbstractAlgorithm
*/
btv.bh.InsertAlg = function(tree, visualiser, value, isSubalgorithm) {
/**
* @private
* @type {Number}
*/
this.value = value;
// parent constructor
btv.AbstractAlgorithm.call(this, tree, visualiser, isSubalgorithm);
}
btv.bh.InsertAlg.jsglExtend(btv.AbstractAlgorithm);
/**
* @override
* @public
*/
btv.bh.InsertAlg.prototype.redo = function() {
// routine
this.redoStart();
this.node = new btv.BinaryTreeNode(this.value);
var index = this.tree.getCount();
if(this.tree.getRoot() == null) {
this.tree.setRoot(this.node);
// show the new graphic node
this.visualiser.animateAddNodeElem(this.node);
this.visualiser.animateShowSelectNode(this.node);
this.visualiser.animateSelectNode(null);
// routine
this.redoEnd();
return;
}
// show the new graphic node
this.visualiser.animateAddNodeElemAt(this.node, index);
this.visualiser.animateShowSelectNode(this.node);
// add node
var parentIndex = Math.floor((index-1)/2);
var parent = this.tree.getNode(parentIndex);
if(index % 2 == 1) { // left
parent.setLeft(this.node);
} else { // right
parent.setRight(this.node);
}
// add edge element
this.visualiser.animateAddEdgeElem(this.node);
this.visualiser.animateShowTree();
var alg = new btv.bh.HeapifyUpAlg(this.tree, this.visualiser, this.node, true);
alg.redo();
this.visualiser.animateSelectNode(null);
// routine
this.redoEnd();
return;
}
/**
* @override
* @public
*/
btv.bh.InsertAlg.prototype.toString = function() {
return "insert(value: " + this.value + ")";
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
/**
* @class
* @author Jakub Melezinek
*
* @constructor
* @param {btv.BinaryTree} tree
* @param {btv.Visualiser} visualiser
* @param {btv.BinaryTreeNode} node
* @param {Boolean} [isSubalgorithm]
* @extends btv.AbstractAlgorithm
*/
btv.bh.DeleteAlg = function(tree, visualiser, node, isSubalgorithm) {
/**
* @private
* @type {btv.BinaryTreeNode}
*/
this.node = node;
// copy of this reference will be created in the parent constructor - copy of given tree
tree.selectedNode = this.node;
// parent constructor
btv.AbstractAlgorithm.call(this, tree, visualiser, isSubalgorithm);
}
btv.bh.DeleteAlg.jsglExtend(btv.AbstractAlgorithm);
/**
* @override
* @public
*/
btv.bh.DeleteAlg.prototype.redo = function() {
// routine
this.redoStart();
var length = this.tree.getCount();
if(length == 1) {
this.tree.setRoot(null);
this.visualiser.animateShowRemoveNode(this.node);
// routine
this.redoEnd();
return;
}
// swap selected and last
var last = this.tree.getNode(length - 1);
if(this.node === last) {
if(this.node.getParent().getLeft() === this.node) {
this.node.getParent().setLeft(null);
} else {
this.node.getParent().setRight(null);
}
// hide
this.visualiser.animateShowRemoveNode(this.node);
// routine
this.redoEnd();
return;
}
this.tree.swapNodes(this.node, last);
this.visualiser.animateSwapNodeElems(this.node, last);
if(this.node.getParent().getLeft() === this.node) {
this.node.getParent().setLeft(null);
} else {
this.node.getParent().setRight(null);
}
// hide
this.visualiser.animateShowRemoveNode(this.node);
// heapify up or down (last)
var alg = new btv.bh.HeapifyUpAlg(this.tree, this.visualiser, last, true);
alg.redo();
alg = new btv.bh.HeapifyDownAlg(this.tree, this.visualiser, last, true);
alg.redo();
// routine
this.redoEnd();
return;
}
/**
* @override
* @public
*/
btv.bh.DeleteAlg.prototype.toString = function() {
return "delete(value: " + this.treeCopy.selectedNode.getValue() + ", index: " + this.treeCopy.selectedNode.getIndex() + ")";
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
/**
* @class
* @author Jakub Melezinek
*
* @constructor
* @param {btv.BinaryTree} tree
* @param {btv.Visualiser} visualiser
* @param {Boolean} [isSubalgorithm]
* @extends btv.AbstractAlgorithm
*/
btv.bh.ExtractMaxAlg = function(tree, visualiser, isSubalgorithm) {
// parent constructor
btv.AbstractAlgorithm.call(this, tree, visualiser, isSubalgorithm);
}
btv.bh.ExtractMaxAlg.jsglExtend(btv.AbstractAlgorithm);
/**
* @override
* @public
*/
btv.bh.ExtractMaxAlg.prototype.redo = function() {
var max = this.tree.getRoot();
// routine
this.redoStart();
if(max !== null) {
// use delete algoritm as part of that algorithm
var deleteAlg = new btv.bh.DeleteAlg(this.tree, this.visualiser, max, true);
deleteAlg.redo();
}
// routine
this.redoEnd(false); // dont show, delete alg show
return max;
}
/**
* @override
* @public
*/
btv.bh.ExtractMaxAlg.prototype.toString = function() {
return "extractMax()";
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
/**
* @class
* @author Jakub Melezinek
*
* @constructor
* @param {btv.BinaryTree} tree
* @param {btv.Visualiser} visualiser
* @param {Boolean} [isSubalgorithm]
* @extends btv.AbstractAlgorithm
*/
btv.bh.GetMaxAlg = function(tree, visualiser, isSubalgorithm) {
// parent constructor
btv.AbstractAlgorithm.call(this, tree, visualiser, isSubalgorithm);
}
btv.bh.GetMaxAlg.jsglExtend(btv.AbstractAlgorithm);
/**
* @override
*/
btv.bh.GetMaxAlg.prototype.redo = function() {
var max = this.tree.getRoot();
// routine
this.redoStart();
if(max !== null) {
this.visualiser.animateSelectNode(max);
}
// routine
this.redoEnd();
return max;
}
/**
* @override
* @public
*/
btv.bh.GetMaxAlg.prototype.toString = function() {
return "getMax()";
}
////////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
/**
* @class
* @author Jakub Melezinek
*
* @constructor
* @param {btv.BinaryTree} tree
* @param {btv.Visualiser} visualiser
* @param {Boolean} [isSubalgorithm]
* @extends btv.AbstractAlgorithm
*/
btv.bh.HeapSortAlg = function(tree, visualiser, isSubalgorithm) {
// parent constructor
btv.AbstractAlgorithm.call(this, tree, visualiser, isSubalgorithm);
}
btv.bh.HeapSortAlg.jsglExtend(btv.AbstractAlgorithm);
/**
* @override
* @public
*/
btv.bh.HeapSortAlg.prototype.redo = function() {
var array = new Array();
var length = this.tree.getCount();
// routine
this.redoStart();
// add array element
this.visualiser.animateAddArrayElem(length);
var root;
var node;
for(var i = length - 1; i >= 1; i--) {
root = this.tree.getRoot();
node = this.tree.getNode(i);
this.visualiser.animateSelectNode(node);
this.visualiser.animateShowTree();
/* also work but the other option is simpler
this.tree.swapNodes(root, node);
if(root.getParent().getLeft() === node) {
root.getParent().setLeft(null);
} else {
root.getParent().setRight(null);
}
*/
// swap nodes - parent-child
if(node.getParent() != null) {
if(node.getParent().getLeft() === node) {
node.getParent().setLeft(null);
} else {
node.getParent().setRight(null);
}
}
node.setLeft(root.getLeft());
node.setRight(root.getRight());
this.tree.setRoot(node);
// graphic swap
this.visualiser.animateSwapNodeElems(root, node);
// add to array element
// show assisstant node
var assistant = new btv.BinaryTreeNode(root.getValue());
assistant.selectable = false;
this.visualiser.animateAddNodeElemAt(assistant, i);
// remove root
this.visualiser.animateRemoveNode(root);
// move assistant node to arrayElem
this.visualiser.animateMoveNextToArrayElem(assistant);
// remove asistant
this.visualiser.animateShowTree(0.25);
this.visualiser.animateRemoveNode(assistant);
// show in array
this.visualiser.animateShowInsertToArrayElem(root, i);
array.push(root);
// heapify new root (node)
// use heapify algoritm as part of that algorithm
var heapifyAlg = new btv.bh.HeapifyDownAlg(this.tree, this.visualiser, node, true);
heapifyAlg.redo();
}
// add last to array element
// show assisstant node
var last = new btv.BinaryTreeNode(this.tree.getRoot().getValue());
last.selectable = false;
this.visualiser.animateAddNodeElemAt(last, 0);
// remove root
this.visualiser.animateRemoveNode(this.tree.getRoot());
// move assistant node to arrayElem
this.visualiser.animateMoveNextToArrayElem(last);
// remove root
this.visualiser.animateShowTree(0.25);
this.visualiser.animateRemoveNode(last);
// show in array
this.visualiser.animateShowInsertToArrayElem(this.tree.getRoot(), 0);
array.push(this.tree.getRoot());
// back to heap and redraw;
var copy = btv.AbstractAlgorithm.copyTree(this.treeCopy);
this.tree.setRoot(copy.getRoot());
this.visualiser.animateRedrawTree(this.tree);
//this.visualiser.animateSelectNode(null);
// routine
this.redoEnd();
array.reverse();
return array;
}
/**
* @override
* @public
*/
btv.bh.HeapSortAlg.prototype.toString = function() {
return "heapSort()";
}