zp-tree (demo purpose)

zp-tree.js

/**
 * zp-Tree 
 * This Tree constructor is essentially a decorator for an array "tree of nodes" passed in. 
 * Purpose: 
 *  - Enter tree as arrays of nested objects Format 
 *  - Easily find / insert / delete / replace Nodes 
 *  - Find parent / child / next / previous Nodes 
 *  - Respect nodes order: array will provide natural ranking 
 * Inspired by js-tree: https://github.com/wangzuo/js-tree/blob/master/index.js 
 * 
 * @author Kim Gysen 
 */ 

/**
 * @typedef Node 
 * @property{number} _cid The internal id used by zp-Tree
 * @property{?Node} prev The previous Node in the tree 
 * @property{?Node} next The next Node in the tree 
 * @property{?Node} parent The node's parent Node 
 * @property{?Array} children The node's childe nodes 
 * @property{number} level The node's depth level 
 * @property{boolean} isLeaf The node is (not) a leaf
 */

var CONSTRUCT_MODE = Object.freeze({ 
    DEEP: { value: 0, desc: "Include all children", is: function(mode){ return (this === mode); } }, 
    SHALLOW: { value:1, desc: "Include only top level", is: function(mode){ return (this === mode); } }
}); 

/**
 * Tree constructor function 
 * @constructor
 * @param {type} Array 
 * @returns {type} Tree 
 */
function Tree(inputTree){ 
    inputTree = inputTree || []; 
    if(!_isArray(inputTree)) throw new Error("Tree should be an array"); 
    
    this.tree = inputTree; 
    this.index = {}; 
    this._cid = 1; 
    _buildTree.call(this, this.tree); 
}; 

var proto = Tree.prototype; 

/**************** Prototype methods ****************/ 
/**
 * Find node 
 * @param {number} _cid
 * @returns {Node} node 
 */
proto.findNode = function(_cid){
    return this.index[_cid] || null; 
}; 

/**
 * Find nodes between start/end node (bidirectional depending on which comes first) 
 * @param {Node} startNode 
 * @param {Node} endNode 
 * @returns {Array} nodes 
 */
proto.findNodesBetween = function(startNode, endNode, options = {}){ 
    var includeChildren = options.children === undefined || options.children ? CONSTRUCT_MODE.DEEP : CONSTRUCT_MODE.SHALLOW, 
        includeNodes = options.include === undefined || options.include ? true : options.include; //Include start / end nodes to returned array
        
    console.log(startNode); 
    console.log(endNode); 
    
    var flatTree = _getFlattenedTree(this.tree, includeChildren); 
    var idxStartNode = _arrayObjectIndexOf(flatTree, startNode._cid, "_cid"); 
    var idxEndNode = _arrayObjectIndexOf(flatTree, endNode._cid, "_cid"); 
    
    if(idxEndNode < idxStartNode) idxEndNode = [idxStartNode, idxStartNode = idxEndNode][0]; //Swap nodes 
    if(includeNodes) idxEndNode = idxEndNode + 1; 
    return flatTree.slice(idxStartNode, idxEndNode); 
}

/**
 * Inject node into the tree at specific parent / index 
 * @param {type} Node
 * @param {?Node} node
 * @param {number} idx
 * @returns {Node} node
 */
proto.insertNode = function(node, parentNode, idx){ 
    if(_nodeExists(this, parentNode) || parentNode === null){
        _buildTree.call(this, [node], null, CONSTRUCT_MODE.DEEP); 
        node = !parentNode ? this.addRootNode(node, idx) : this.addChildNode(node, parentNode, idx); 
    } else {
        throw new Error("Insertion fail: Parent node with _cid: " + parentNode._cid + " doesn't exist"); 
    }
    
    
    return node; 
}; 
/**
 * Inject as root node at specified index
 * @param {Node} node 
 * @param {number} idx
 * @returns {Node} node
 */
proto.addRootNode = function(node, idx){ 
    if(!_indexWithinTree(this.tree, idx)) 
        this.tree.push(node); 
    else 
        this.tree.splice(idx, 0, node); //Adds a node to the base @ provided index 
    
    _buildTree.apply(this, [this.tree, null, CONSTRUCT_MODE.SHALLOW]); 
    return node; 
}

/**
 * Inject as child node of a defined parent at specified index
 * @param {Node} node 
 * @param {number} parent_cid
 * @param {number} idx
 * @returns {Node} node
 */
proto.addChildNode = function(node, parentNode, idx){ 
    if(!_nodeExists(this, parentNode)) 
        throw new Error("Insertion failed: Provided parent node does not exist. Use 'addRootNode(node, idx) to create a new root node."); 
    
    if(!_hasChildren(parentNode)){ 
        idx = 0; 
        parentNode.children = []; 
    }; 
    
    parentNode.children.splice(idx, 0, node); 
    _buildTree.apply(this, [parentNode.children, parentNode, CONSTRUCT_MODE.DEEP]); //DEEP required for syncing childNode.level
    
    return node; 
} 

/**
 * Moves a node from one place in the tree to another 
 * @param {Node} node 
 * @param {?Node} node 
 * @param {number} idx
 * @returns {undefined}
 */
proto.moveNode = function(node, parentNode, idx){ 
    if(_nodeExists(this, node)){ 
        this.removeNode(node); 
        this.insertNode(node, parentNode, idx); 
    } else { 
        if(!_nodeExists(this, parent_cid)) throw new Error("Parent node doesn't exist on this tree."); 
    }
}; 

/**
 * Moves multiple nodes from one place in the tree to another as atomic operation 
 * @param {Array<Node>} nodes 
 * @param {Node} node 
 * @param {number} idx
 * @returns {undefined}
 */
proto.moveNodes = function(nodes, parentNode, idx){ 
    if(_allNodesExist(this, nodes) && _nodeExists(this, parentNode)){ 
        nodes.forEach(function(node, index){ 
            this.moveNode(node, parentNode, idx); 
        }); 
    } else { 
        if(!_allNodesExist(this, nodes)) throw new Error("Not all nodes attempted to be moved exist on this tree."); 
        if(!_nodeExists(this, parent_cid)) throw new Error("Parent node doesn't exist on this tree."); 
    }
}

/**
 * Removes a node from the tree 
 * @param {Node} node 
 * @returns {undefined}
 */
proto.removeNode = function(node){ 
    if (_nodeExists(this, node)){ 
        var nodes = _hasParent(node) ? node.parent.children : this.tree; 
        
        nodes.splice(node.idx, 1); 
        _removeNodeFromIndex.call(this, node); 
        
        if(_hasParent(node)) _buildTree.apply(this, [nodes, node.parent, CONSTRUCT_MODE.SHALLOW]); 
    }; 
}; 

/**
 * Removes multiple nodes from the tree as atomic operation 
 * @param {Array<Node>} nodes 
 * @returns {undefined}
 */
proto.removeNodes = function(nodes){ 
    if(_allNodesExist(this, nodes)){ 
        nodes.forEach(function(node, index){ 
            this.removeNode(node, parentNode, idx); 
        }); 
    } else { 
        new Error("Not all nodes attempted to be removed exist on this tree."); 
    } 
} 

/**
 * Deletes the original node, injects the new node at equal index 
 * @param {number} node__cid
 * @param {Node} newNode
 * @returns {Node} newNode 
 */
proto.replaceNode = function(prevNode, newNode){ 
    if (_nodeExists(this, prevNode)){ 
        newNode.idx = node.idx; 
        this.removeNode(prevNode._cid); 
        newNode = this.insertNode(newNode, prevNode.parent, prevNode.idx); 
    } else { 
        throw new Error("Node with _cid " + prevNode._cid + " does not exist on this tree"); 
    }; 
    
    return newNode; 
}; 

/** 
 * Extracts the data from zpTree and returns the data in the original array format 
 * @param {?type} inputTree
 * @param {?Array} newNode
 * @returns {Array} Tree 
 */ 
proto.unwrap = function(inputTree, arrTree = []){ 
    var tree = inputTree || this.tree; 
    
    tree.forEach(function(node, idx){ 
        arrTree.push(node.data); 
        
        if(_hasChildren(node)){ 
            node.data.children = []; 
            this.unwrap(node.children, node.data.children); 
        } 
        
    }, this); 
    
    return arrTree; 
}

proto.getFlattenedTree = function(options = {}){ 
    var includeChildren = options.children ? CONSTRUCT_MODE.DEEP : CONSTRUCT_MODE.SHALLOW; 
    return _getFlattenedTree(this.tree, includeChildren, level); 
} 

/**************** Private methods ****************/ 

function _buildTree(tree, parent = null, constructMode = CONSTRUCT_MODE.DEEP){ 
    tree.forEach(function (node, idx) { 
        if(!_isObject(node)) throw new Error("Tree nodes should be objects."); 
        
        node = _initNode(node, idx); 
        node = _buildNode.apply(this, [tree, node, parent, idx]); 
        _addNodeToIndex.call(this, node); 
        
        if(constructMode.is(CONSTRUCT_MODE.DEEP) && _hasChildren(node)) { 
            _buildTree.apply(this, [node.children, node, CONSTRUCT_MODE.DEEP]); 
        }; 
        
    }, this); 
    
    return tree; 
} 

function _initNode(node, idx){ 
    node.data = {}; 
    for(var key in node){ 
        if(key !== "children" && key !== "data"){ 
            node.data[key] = node[key]; 
            delete node[key]; 
        }; 
    }; 
    return node; 
} 

function _buildNode(tree, node, parent, idx){ 
    if(!node._cid) node._cid = this._cid++; 
    node.parent = parent || null; 
    node.level = _hasParent(node) ? parent.level + 1 : 1; 
    node.prev = idx > 0 ? tree[idx - 1] : null; 
    node.next = _indexWithinTree(tree, idx + 1) ? tree[idx + 1] : null; 
    node.idx = idx; 
    node.isLeaf = !_hasChildren(node); 
    node.isBase = !_hasParent(node); 
    return node; 
} 

function _addNodeToIndex(node){ 
    this.index[node._cid] = node; 
    return node; 
} 

function _removeNodeFromIndex(node){ 
    delete this.index[node._cid]; 
    
    if(_hasChildren(node)){ 
        node.children.forEach(function(childNode, idx){ 
            
            delete this.index[childNode._cid]; 
            if(_hasChildren(childNode)) _removeNodeFromIndex.call(this, childNode); 
            
        }, this); 
    }; 
}

function _indexWithinTree(tree, idx) { 
    return !(idx >= tree.length || idx < 0); 
} 

function _allNodesExist(Tree, nodes){
    var bAllNodesExist = true; 
    
    nodes.forEach(function(nodes, idx){ 
        if(!_nodeExists(Tree, node))
            bAllNodesExist = false; 
    }); 
    
    return bAllNodesExist; 
} 

function _nodeExists(Tree, node){
    return Tree.findNode(node._cid) != null; 
}

function _hasParent(node){ 
    return node.parent != null; 
}

function _hasChildren(node){ 
    return (node.children && node.children.length); 
} 

function _getFlattenedTree(tree, constructMode = CONSTRUCT_MODE.DEEP, flattenedTree = []){
    tree.forEach(function(node, idx){ 
        flattenedTree.push(node); 
        if(_hasChildren(node) && constructMode === CONSTRUCT_MODE.DEEP){ 
            _getFlattenedTree(node.children, CONSTRUCT_MODE.DEEP, flattenedTree); 
        }; 
    }); 
    return flattenedTree; 
}

/**************** Convenience methods ****************/ 

function _isObject(val){ 
    if (val === null) { return false;} 
    return ((typeof val === 'function') || (typeof val === 'object')); 
} 

function _isArray(val){
    return (val.constructor === Array); 
} 

function _arrayObjectIndexOf(arr, searchTerm, property){
    for(var i = 0, len = arr.length; i < len; i++) {
        if (arr[i][property] === searchTerm) return i;
    }; 
    return -1; 
}

module.exports = Tree;