module.exports = (function(){
// Flag bad practises
'use strict';
// ------------------------------------
// Basic Setup
// ------------------------------------
/**
* @class Traverser
* @constructor
* @classdesc Represents a traverser which searches/traverses the tree in BFS and DFS fashion.
* @param tree - {@link Tree} that has to be traversed or search.
*/
function Traverser(tree){
if(!tree)
throw new Error('Could not find a tree that is to be traversed');
/**
* Represents the {@link Tree} which has to be traversed.
*
* @property _tree
* @type {object}
* @default "null"
*/
this._tree = tree;
}
// ------------------------------------
// Methods
// ------------------------------------
/**
* Searches a tree in DFS fashion. Requires a search criteria to be provided.
*
* @method searchDFS
* @memberof Traverser
* @instance
* @param {function} criteria - MUST BE a callback function that specifies the search criteria.
* Criteria callback here receives {@link TreeNode#_data} in parameter and MUST return boolean
* indicating whether that data satisfies your criteria.
* @return {object} - first {@link TreeNode} in tree that matches the given criteria.
* @example
* // Search DFS
* var node = tree.traverser().searchDFS(function(data){
* return data.key === '#greenapple';
* });
*/
Traverser.prototype.searchDFS = function(criteria){
// Hold the node when found
var foundNode = null;
// Find node recursively
(function recur(node){
if(node.matchCriteria(criteria)){
foundNode = node;
return foundNode;
} else {
node._childNodes.some(recur);
}
}(this._tree._rootNode));
return foundNode;
};
/**
* Searches a tree in BFS fashion. Requires a search criteria to be provided.
*
* @method searchBFS
* @memberof Traverser
* @instance
* @param {function} criteria - MUST BE a callback function that specifies the search criteria.
* Criteria callback here receives {@link TreeNode#_data} in parameter and MUST return boolean
* indicating whether that data satisfies your criteria.
* @return {object} - first {@link TreeNode} in tree that matches the given criteria.
* @example
* // Search BFS
* var node = tree.traverser().searchBFS(function(data){
* return data.key === '#greenapple';
* });
*/
Traverser.prototype.searchBFS = function(criteria){
// Hold the node when found
var foundNode = null;
// Find nodes recursively
(function expand(queue){
while(queue.length){
var current = queue.splice(0, 1)[0];
if(current.matchCriteria(criteria)){
foundNode = current;
return;
}
current._childNodes.forEach(function(_child){
queue.push(_child);
});
}
}([this._tree._rootNode]));
return foundNode;
};
/**
* Traverses an entire tree in DFS fashion.
*
* @method traverseDFS
* @memberof Traverser
* @instance
* @param {function} callback - Gets triggered when @{link TreeNode} is explored. Explored node is passed as parameter to callback.
* @example
* // Traverse DFS
* tree.traverser().traverseDFS(function(node){
* console.log(node.data);
* });
*/
Traverser.prototype.traverseDFS = function(callback){
(function recur(node){
callback(node);
node._childNodes.forEach(recur);
}(this._tree._rootNode));
};
/**
* Traverses an entire tree in BFS fashion.
*
* @method traverseBFS
* @memberof Traverser
* @instance
* @param {function} callback - Gets triggered when node is explored. Explored node is passed as parameter to callback.
* @example
* // Traverse BFS
* tree.traverser().traverseBFS(function(node){
* console.log(node.data);
* });
*/
Traverser.prototype.traverseBFS = function(callback){
(function expand(queue){
while(queue.length){
var current = queue.splice(0, 1)[0];
callback(current);
current._childNodes.forEach(function(_child){
queue.push(_child);
});
}
}([this._tree._rootNode]));
};
// ------------------------------------
// Export
// ------------------------------------
return Traverser;
}());