var TreeNode = require('./tree-node');
var Traverser = require('./traverser');
module.exports = (function(){
// Flag bad practises
'use strict';
// ------------------------------------
// Basic Setup
// ------------------------------------
/**
* @class Tree
* @classdesc Represents the tree in which data nodes can be inserted
* @constructor
*/
function Tree(){
/**
* Represents the root node of the tree.
*
* @member
* @type {object}
* @default "null"
*/
this._rootNode = null;
/**
* Represents the current node in question. `_currentNode` points to most recent
* node inserted or parent node of most recent node removed.
*
* @member
* @memberof Tree.
* @type {object}
* @default "null"
*/
this._currentNode = null;
/**
* Represents the traverser which search/traverse a tree in DFS and BFS fashion.
*
* @member
* @memberof Tree
* @type {object}
* @instance
* @default {@link Traverser}
*/
this._traverser = new Traverser(this);
}
// ------------------------------------
// Getters and Setters
// ------------------------------------
/**
* Returns a root node of the tree.
*
* @method rootNode
* @memberof Tree
* @instance
* @return {TreeNode} - root node of the tree.
*/
Tree.prototype.rootNode = function(){
return this._rootNode;
};
/**
* Returns a current node in a tree
*
* @method currentNode
* @memberof Tree
* @instance
* @return {TreeNode} - current node of the tree.
*/
Tree.prototype.currentNode = function(){
return this._currentNode;
};
/**
* Getter function that returns {@link Traverser}.
*
* @method traverser
* @memberof Tree
* @instance
* @return {@link Traverser} for the tree.
*/
Tree.prototype.traverser = function(){
return this._traverser;
};
// ------------------------------------
// Methods
// ------------------------------------
/**
* Checks whether tree is empty.
*
* @method isEmpty
* @memberof Tree
* @instance
* @return {boolean} whether tree is empty.
*/
Tree.prototype.isEmpty = function(){
return this._rootNode === null && this._currentNode === null;
};
/**
* Empties the tree. Removes all nodes from tree.
*
* @method pruneAllNodes
* @memberof Tree
* @instance
* @return {@link Tree} empty tree.
*/
Tree.prototype.pruneAllNodes = function(){
if(this._rootNode && this._currentNode) this.trimBranchFrom(this._rootNode);
return this;
};
/**
* Creates a {@link TreeNode} that contains the data provided and insert it in a tree.
* New node gets inserted to the `_currentNode` which updates itself upon every insertion and deletion.
*
* @method insert
* @memberof Tree
* @instance
* @param {object} data - data that has to be stored in tree-node.
* @return {object} - instance of {@link TreeNode} that represents node inserted.
* @example
*
* // Insert single value
* tree.insert(183);
*
* // Insert array of values
* tree.insert([34, 565, 78]);
*
* // Insert complex data
* tree.insert({
* key: '#berries',
* value: { name: 'Apple', color: 'Red'}
* });
*/
Tree.prototype.insert = function(data){
var node = new TreeNode(data);
if(this._rootNode === null && this._currentNode === null){
node._depth = 1;
this._rootNode = this._currentNode = node;
} else {
node._parentNode = this._currentNode;
this._currentNode._childNodes.push(node);
this._currentNode = node;
node.depth = node._parentNode._depth + 1;
}
return node;
};
/**
* Removes a node from tree and updates `_currentNode` to parent node of node removed.
*
* @method remove
* @memberof Tree
* @instance
* @param {object} node - {@link TreeNode} that has to be removed.
* @param {boolean} trim - indicates whether to remove entire branch from the specified node.
*/
Tree.prototype.remove = function(node, trim){
if(trim || node === this._rootNode){
// Trim Entire branch
this.trimBranchFrom(node);
} else {
// Upate children's parent to grandparent
node._childNodes.forEach(function(_child){
_child._parentNode = node._parentNode;
node._parentNode._childNodes.push(_child);
});
// Delete itslef from parent child array
node._parentNode._childNodes.splice(node._parentNode._childNodes.indexOf(node), 1);
// Update Current Node
this._currentNode = node._parentNode;
// Clear Child Array
node._childNodes = [];
node._parentNode = null;
node._data = null;
}
};
/**
* Remove an entire branch starting with specified node.
*
* @method trimBranchFrom
* @memberof Tree
* @instance
* @param {object} node - {@link TreeNode} from which entire branch has to be removed.
*/
Tree.prototype.trimBranchFrom = function(node){
// Hold `this`
var thiss = this;
// trim brach recursively
(function recur(node){
node._childNodes.forEach(recur);
node._childNodes = [];
node._data = null;
}(node));
// Update Current Node
if(node._parentNode){
node._parentNode._childNodes.splice(node._parentNode._childNodes.indexOf(node), 1);
thiss._currentNode = node._parentNode;
} else {
thiss._rootNode = thiss._currentNode = null;
}
};
/**
* Inserts node to a particular node present in the tree. Particular node here is searched
* in the tree based on the criteria provided.
*
* @method insertTo
* @memberof Tree
* @instance
* @param {function} criteria - Callback function that specifies the search criteria
* for node to which new node is to be inserted. Criteria callback here receives {@link TreeNode#_data}
* in parameter and MUST return boolean indicating whether that data satisfies your criteria.
* @param {object} data - that has to be stored in tree-node.
* @return {object} - instance of {@link TreeNode} that represents node inserted.
* @example
*
* // Insert data
* tree.insert({
* key: '#apple',
* value: { name: 'Apple', color: 'Red'}
* });
*
* // New Data
* var greenApple = {
* key: '#greenapple',
* value: { name: 'Green Apple', color: 'Green' }
* };
*
* // Insert data to node which has `key` = #apple
* tree.insertTo(function(data){
* return data.key === '#apple'
* }, greenApple);
*/
Tree.prototype.insertTo = function(criteria, data){
var node = this.traverser().searchDFS(criteria);
return this.insertToNode(node, data);
};
/**
* Inserts node to a particular node present in the tree. Particular node here is an instance of {@link TreeNode}
*
* @method insertToNode
* @memberof Tree
* @instance
* @param {function} node - {@link TreeNode} to which data node is to be inserted.
* @param {object} data - that has to be stored in tree-node.
* @return {object} - instance of {@link TreeNode} that represents node inserted.
* @example
*
* // Insert data
* var node = tree.insert({
* key: '#apple',
* value: { name: 'Apple', color: 'Red'}
* });
*
* // New Data
* var greenApple = {
* key: '#greenapple',
* value: { name: 'Green Apple', color: 'Green' }
* };
*
* // Insert data to node
* tree.insertToNode(node, greenApple);
*/
Tree.prototype.insertToNode = function(node, data){
var newNode = new TreeNode(data);
newNode._parentNode = node;
newNode._depth = newNode._parentNode._depth + 1;
node._childNodes.push(newNode);
this._currentNode = newNode;
return newNode;
};
/**
* Finds a distance between two nodes
*
* @method distanceBetween
* @memberof Tree
* @instance
* @param {@link TreeNode} fromNode - Node from which distance is to be calculated
* @param {@link TreeNode} toNode - Node to which distance is to be calculated
* @return {Number} - distance(number of hops) between two nodes.
*/
Tree.prototype.distanceBetween = function(fromNode, toNode){
return fromNode.distanceToRoot() + toNode.distanceToRoot() - 2 * this.findCommonParent(fromNode, toNode).distanceToRoot();
};
/**
* Finds a common parent between nodes
*
* @method findCommonParent
* @memberof Tree
* @instance
* @param {@link TreeNode} fromNode
* @param {@link TreeNode} toNode
* @return {@link TreeNode} - common parent
*/
Tree.prototype.findCommonParent = function(fromNode, toNode){
// Get ancestory of both nodes
var fromNodeAncestors = fromNode.getAncestry();
var toNodeAncestors = toNode.getAncestry();
// Find Commont
var common = null;
fromNodeAncestors.some(function(ancestor){
if(toNodeAncestors.indexOf(ancestor) !== -1){
common = ancestor;
return true;
}
});
// Return Common
return common;
};
/**
* Exports the tree data in format specified. It maintains herirachy by adding
* additional "children" property to returned value of `criteria` callback.
*
* @method export
* @memberof Tree
* @instance
* @param {Tree~criteria} criteria - Callback function that receives data in parameter
* and MUST return a formatted data that has to be exported. A new property "children" is added to object returned
* that maintains the heirarchy of nodes.
* @return {object} - {@link TreeNode}.
* @example
*
* var rootNode = tree.insert({
* key: '#apple',
* value: { name: 'Apple', color: 'Red'}
* });
*
* tree.insert({
* key: '#greenapple',
* value: { name: 'Green Apple', color: 'Green'}
* });
*
* tree.insertToNode(rootNode, {
* key: '#someanotherapple',
* value: { name: 'Some Apple', color: 'Some Color' }
* });
*
* // Export the tree
* var exported = tree.export(function(data){
* return { name: data.value.name };
* });
*
* // Result in `exported`
* {
* "name": "Apple",
* "children": [
* {
* "name": "Green Apple",
* "children": []
* },
* {
* "name": "Some Apple",
* "children": []
* }
* ]
*}
*
*/
Tree.prototype.export = function(criteria){
// Check if rootNode is not null
if(!this._rootNode){
return null;
}
return this._rootNode.export(criteria);
};
/**
* Returns a new compressed tree. While compressing it considers nodes that
* satisfies given criteria and skips the rest of the nodes, making tree compressed.
*
* @method compress
* @memberof Tree
* @instance
* @param {Tree~criteria} criteria - Callback function that checks whether node satifies certain criteria. MUST return boolean.
* @return {@link Tree} - A new compressed tree.
*/
Tree.prototype.compress = function(criteria){
// Check if criteria is specified
if(!criteria || typeof criteria !== 'function')
throw new Error('Compress criteria not specified');
// Check if tree is not empty
if(this.isEmpty()){
return null;
}
// Create New Tree
var tree = new Tree();
// Hold `this`
var thiss = this;
// Recur DFS
(function recur(node, parent){
// Check-in
var checkIn = thiss.rootNode() === node || node.matchCriteria(criteria);
// Check if checked-in
if(checkIn){
if(tree.isEmpty()){
parent = tree.insert(node.data());
} else {
parent = tree.insertToNode(parent, node.data());
}
} else {
parent._data.hasCompressedNodes = true;
}
// For all child nodes
node.childNodes().forEach(function(_child){
recur(_child, parent);
});
}(this.rootNode(), null));
return tree;
};
/**
* Imports the JSON data into a tree using the criteria provided.
* A property indicating the nesting of object must be specified.
*
* @method import
* @memberof Tree
* @instance
* @param {object} data - JSON data that has be imported
* @param {string} childProperty - Name of the property that holds the nested data.
* @param {Tree~criteria} criteria - Callback function that receives data in parameter
* and MUST return a formatted data that has to be imported in a tree.
* @return {object} - {@link Tree}.
* @example
*
* var data = {
* "trailId": "h2e67d4ea-f85f40e2ae4a06f4777864de",
* "initiatedAt": 1448393492488,
* "snapshots": {
* "snapshotId": "b3d132131-213c20f156339ea7bdcb6273",
* "capturedAt": 1448393495353,
* "thumbnail": "data:img",
* "children": [
* {
* "snapshotId": "yeb7ab27c-b36ff1b04aefafa9661243de",
* "capturedAt": 1448393499685,
* "thumbnail": "data:image/",
* "children": [
* {
* "snapshotId": "a00c9828f-e2be0fc4732f56471e77947a",
* "capturedAt": 1448393503061,
* "thumbnail": "data:image/png;base64",
* "children": []
* }
* ]
* }
* ]
* }
* };
*
* // Import
* // This will result in a tree having nodes containing `id` and `thumbnail` as data
* tree.import(data, 'children', function(nodeData){
* return {
* id: nodeData.snapshotId,
* thumbnail: nodeData.thumbnail
* }
* });
*
*/
Tree.prototype.import = function(data, childProperty, criteria){
// Empty all tree
if(this._rootNode) this.trimBranchFrom(this._rootNode);
// Set Current Node to root node as null
this._currentNode = this._rootNode = null;
// Hold `this`
var thiss = this;
// Import recursively
(function importRecur(node, recurData){
// Format data from given criteria
var _data = criteria(recurData);
// Create Root Node
if(!node){
node = thiss.insert(_data);
} else {
node = thiss.insertToNode(node, _data);
}
// For Every Child
recurData[childProperty].forEach(function(_child){
importRecur(node, _child);
});
}(this._rootNode, data));
// Set Current Node to root node
this._currentNode = this._rootNode;
return this;
};
/**
* Callback that receives a node data in parameter and expects user to return one of following:
* 1. {@link Traverser#searchBFS} - {boolean} in return indicating whether given node satisfies criteria.
* 2. {@link Traverser#searchDFS} - {boolean} in return indicating whether given node satisfies criteria.
* 3. {@link Tree#export} - {object} in return indicating formatted data object.
* @callback criteria
* @param data {object} - data of particular {@link TreeNode}
*/
// ------------------------------------
// Export
// ------------------------------------
return Tree;
}());