0
\$\begingroup\$

This is a follow-up on my previous post.

I have made modifications based on the feedback received on the previous post, hence I request a third (final?) review on the modified code if ok.

Note: review purpose is just to check good practices (code / performance wise) and see if anything's missing.

I did all updates as proposed by @EngineerDollery in the previous post.

Other than that I separated prototype methods (API) from private methods more clearly;

Thanks to @EngineerDollery for the reviews so far.

/**
 * 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 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: "Construct all children", is: function( mode ){ return ( this === mode ) } }, 
    SHALLOW: { value:1, desc: "Construct only top level", is: function( mode ){ return ( this === mode ) } }
}); 

/**
 * Tree constructor function 
 * @constructor
 * @param {type} Array 
 * @returns {type} Tree 
 */
function Tree( tree ){ 
    tree = tree || []; 
    if( !_isArray( tree ) ) throw "Array is required!"; 

    this.tree = tree; 
    this.index = {}; 
    this._cid = 1; 
    _buildTree.call( this, tree ); 
}; 

var proto = Tree.prototype; 

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

/**
 * Inject node into the tree at specific parent / index 
 * @param {type} Node
 * @param {?number} parent_cid
 * @param {number} idx
 * @returns {Node} node
 */
proto.insertNode = function ( node, parent_cid, idx ){ 
    var parentNode = this.findNode( parent_cid ); 
    _buildTree.call( this, [ node ], null, CONSTRUCT_MODE.DEEP ); 

    if( !parentNode ){ 
        node = this.addRootNode( node, idx ); 

    } else { 
        node = this.addChildNode( node, parent_cid, idx ); 
    }; 

    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, parent_cid, idx ){ 

    var parentNode = this.findNode( parent_cid ); 
    if( parent_cid && !parentNode ) throw "Node insertion failed: Provided parent node doesn't 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; 
} 

/**
 * Removes a node from the tree 
 * @param {number} node__cid
 * @returns {undefined}
 */
proto.removeNode = function( node__cid ){ 

    var node = this.findNode( node__cid ); 
    if ( node ){ 
        var nodes = _hasParent( node ) ? node.parent.children : this.tree; 
        nodes.splice( node.idx, 1 ); 

        _removeNodeFromIndex.call( this, node ); 
        if( node.parent) _buildTree.apply( this, [ nodes, node.parent, CONSTRUCT_MODE.SHALLOW ] ); 

    }; 
}; 

/**
 * Deletes the original node, injects the new node at equal index 
 * @param {number} node__cid
 * @param {Node} newNode
 * @returns {Node} newNode 
 */
proto.replaceNode = function( node_cid, newNode ){ 
    var node = this.findNode( node_cid ); 
    if ( node ){ 
        newNode.idx = node.idx; 
        this.removeNode( node._cid ); 
        newNode = this.insertNode( newNode, node.parent, node.idx ); 

    } else { 
        throw "the node's cid doesn't exist"; 
    }; 
    return newNode; 
}; 

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

function _buildTree( tree, parent = null, constructMode = CONSTRUCT_MODE.DEEP ){ 

    tree.forEach( function (node, idx) { 
        node = _buildNode.apply( this, [ tree, node, parent, idx ] ); 
        _addNodeToIndex.call( this, node ); 

        if( constructMode.is( CONSTRUCT_MODE.DEEP ) ) { 
            if( _hasChildren( node ) ) _buildTree.apply( this, [ node.children, node, CONSTRUCT_MODE.DEEP ] ); 
        }; 

    }, this); 
}; 

function _buildNode( tree, node, parent, idx ){ 
    if( !node._cid ) node._cid = this._cid++; 
    node.parent = parent; 
    node.level = _hasParent( node ) ? parent.level + 1 : 0; 
    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 _hasParent( node ){ 
    return !!node.parent; 
}

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

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

module.exports = Tree; 
\$\endgroup\$
1
\$\begingroup\$

It just keeps getting better, but I suppose we have time for one more iteration :)

1) findNode() could be a single line function, but you're declaring an unnecessary symbol.

2) There are extra blank lines everywhere. Blank lines are used to show a break in program flow, but aren't usually placed before a close-brace. So, in addRootNode(), for example, there is a blank line before the } else { line (also repeated elsewhere), which is spurious, and in removeNode() there is no blank line before the if statement, but there should be.

3) hasParent() is returning a !! -- that's probably overkill :)

4) buildTree() has this:

if( constructMode.is( CONSTRUCT_MODE.DEEP ) ) { 
    if( _hasChildren( node ) ) _buildTree.apply( this, [ node.children, node, CONSTRUCT_MODE.DEEP ] ); 
}; 

Which could be simplified to:

if (constructMode.is(CONSTRUCT_MODE.DEEP) && _hasChildren(node))
    buildTree.apply(this, [node.children, node, CONSTRUCT_MODE.DEEP] ); 

5) Although it is purely stylistic, the spacing around your parenthesis and braces is non-canonical. Typically we would have no spaces inside parenthesis or braces. The code I have shown in point 4 shows canonical formatting for JS.

Typically, this:

if( !parentNode ){ 

would be written like this:

if (!parentNode)

6) And, although a lot of people (who are wrong) may disagree with me, I don't use braces where I only have a single target statement on each branch of an if statement. So this:

if( !parentNode ){ 
    node = this.addRootNode( node, idx ); 

} else { 
    node = this.addChildNode( node, parent_cid, idx ); 
}; 

Becomes this:

if (!parentNode) 
    node = this.addRootNode(node, idx); 
else
    node = this.addChildNode(node, parent_cid, idx);

7) That last example was about formatting, but now that the code is clear and easy to read we can see that the last bit of code should really have been an assignment with a ternary operator:

node = !parent ? this.addRootNode(node, idx) : this.addChildNode(node, parent_cid, idx);

This is to show 'intent'. Your intent here is not to branch the program flow, but instead to assign a value to node. The if statement approach communicates that it is important to branch here -- so as a reader I focus on that, the condition, etc. The second form, with the ternary operator, communicates that it is important to set a value to a variable here, so I focus on that. Of the two, the latter focus is the correct one, the branch is unimportant in this context.

Notes: Point's 2, 5, and 6, are about writing canonical code, so that the maximum number of people can read your code -- if you follow the same formatting standards as everyone else then people can spend more time figuring out what your code does and admiring its simplicity rather than spending time trying to decipher the way its written.

\$\endgroup\$
  • \$\begingroup\$ Thanks again for the review, I adapted it. I appreciate the detail that you have put into these reviews; it has taught me a great deal and they are what makes the difference for my path of experience. Just one more question. The return !!node.parent is what I did to return a boolean. If not, it would return the actual node's parent, which is not desired. Is that ok, or do you see another way? \$\endgroup\$ – Trace May 6 '16 at 0:01
  • \$\begingroup\$ !!node.parent -- ooh, that's clever. I wasn't paying that much attention. But, if it caught me then it can catch other people too I suppose. I think you should consider node.parent != undefined if it meets all criteria (I think it should be undefined, but I'm not using an ide to review this -- I'm doing it by eye -- so I can't check). \$\endgroup\$ – Software Engineer May 6 '16 at 11:00
  • \$\begingroup\$ And, removeNode() needs to use the hasParent() method, not check node.parent itself. This is to remove duplication so that changes can be made once and only once. \$\endgroup\$ – Software Engineer May 6 '16 at 11:01
  • \$\begingroup\$ Good catch, seems that I missed that one. It seems indeed that some find the use of !! rather obscure, so I changed it to: return node.parent != null; and while building the node added: node.parent = parent || null; to catch falsy values and ensure explicit null. I hope that this makes it less obscure. \$\endgroup\$ – Trace May 6 '16 at 13:05
  • 1
    \$\begingroup\$ That's perfect. Nice one. I think you've passed now ;) \$\endgroup\$ – Software Engineer May 7 '16 at 2:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.