Thin Tree

search-tree.js

var TT = require('./thin-tree');


var SearchTree = {

    searchTree: function(query, op, source) {
        op = op || 'where';
        source = source || this.preOrderTraverse();
        return _[op](source, query);
    },

    searchFollowing: function(query, wrap) {
        return this.search(query, this.getFollowing(wrap));
    },

    searchPreceding: function(query, wrap) {
        return this.search(query, this.getPreceding(wrap))
    },

    searchSubtree: function(query, op) {
        op = op || 'where';
        return this[op](query) || this.reduce(function(targets, node) {
            return targets.concat(node.searchSubtree(query));
        }, [])
    },

    findTree: function(query, source, op) {
        this.search(query, null, 'find');
    },

    findFollowing: function(query, wrap) {
        return this.find(query, this.getFollowing(wrap));
    },

    findPreceding: function(query, wrap) {
        return this.find(query, this.getPreceding(wrap))
    },

    findSubtree: function(query, op) {
        return this[op](query) || this.reduce(function(target, node) {
            return target || node.findSubtree(query);
        }, null)
    },

    getPreceding: function(wrap) {
        var preorder = this.root.preOrderTraverse().reverse();
        var index = preorder.indexOf(this);
        return preorder.slice(index + 1).concat(
            wrap ? preorder.slice(0, index) : []
        );
    },

    getFollowing:  function(wrap) {
        var preorder = this.root.preOrderTraverse();
        var index = preorder.indexOf(this);
        return preorder.slice(index + 1).concat(
            wrap ? preorder.slice(0, index) : []
        );
    },

    recurse: function(oper, query, iter, callback, acc) {
        var self = this;
        oper = oper || 'noop';
        iter = iter || 'each';
        callback = callback || function(acc, node) {
            return node.recurse(oper, query, iter, callback, acc);
        }
        return (
            (_.isFunction(oper) ? oper : self[oper])(query)
        ||  (_.isFunction(iter) ? iter : self[iter])(callback, acc, query)
        );
    }

}

SearchTree.recurse(function(node){
    return node
})


///////////////////////////////////////////////////////////////////////////////
///
///                         Collection Methods
///
///////////////////////////////////////////////////////////////////////////////


var collectionMethods = [
        'chain',
        /**
         * Collection Methods
         */
        'at', 'contains', 'countBy', 'every', 'filter', 'find', 'findLast',
        'forEach', 'forEachRight', 'groupBy', 'indexBy', 'invoke', 'map',
        'max', 'min', 'pluck', 'reduce', 'reduceRight', 'reject', 'sample',
        'shuffle', 'size', 'some', 'sortBy', 'toArray', 'where',
        /**
         * Object method
         */
        'transform',
        /**
         * Array methods, sorted by type of operation
         */
        'indexOf', 'lastIndexOf',
        'findIndex', 'findLastIndex',
        'first', 'last',
        'initial', 'rest',
        'difference', 'intersection', 'union', 'uniq', 'without', 'xor',
        'sortedIndex',
        /**
         * Not applicable or destructive
            'flatten',
            'range',
            'compact',
            'pull', 'remove',
            'zip', 'zipObject'
         */
    ];

_.each(collectionMethods, function(method) {
    SearchTree[method] = function() {
        var args = _.toArray(arguments);
        args.unshift(this.getChildren());
        return _[method].apply(_, args);
    }
});


///////////////////////////////////////////////////////////////////////////////
///
///                         Attribute Methods
///
///////////////////////////////////////////////////////////////////////////////


_.each(['assign', 'defaults', 'has', 'omit', 'pick'], function(method) {
    SearchTree[method] = function() {
        var args = _.toArray(arguments);
        args.unshift(this);
        return _[method].apply(_, args);
    }
});


///////////////////////////////////////////////////////////////////////////////
///
///                            Exports
///
///////////////////////////////////////////////////////////////////////////////


module.exports = TT.extend(SearchTree);

thin-tree.js

var _ = require('lodash');


/**
 * Initializes ThinTree and creates tree with root and children
 * @param {Object} options {root?, parent?}
 */
var ThinTree = function(node) {
    // Makes for better inheritance.
    this.initialize(node);
};


ThinTree.prototype.initialize = function(node) {
    // Assigns element, other options and defaults
    _.assign(this, node);

    // Initializes root
    if (_.isEmpty(this.parent)) {
        this.root = this;
    }

    this.setChildren();
    this._memo = {};
}


ThinTree.prototype.flatten = function() {
    return _.isUndefined(this._memo.flattened) ?
        this._memo.flattened = _.reduce(this.children,
            function(accumulator, node) {
                return accumulator.concat(node.flatten()); }, [this])
    :   this._memo.flattened;
}


ThinTree.prototype.setChildren = function() {
    var self = this;
    var properties = {
        root: this.root,
        parent: this
    }
    if(_.isArray(this.children)){
        // Creates node for each child element
        this.children = _.map(this.children, function (node) {
            // Pass new object with current node properties, set the parent and root
            return new self.constructor( _.assign({}, node, properties));
        });
    }
}


ThinTree.prototype.toJSON = function() {
    var self = this;
    var obj = _(this)
        .omit('parent', 'root')
        .omit(function(value, key){
            return !_.has(self, key);
        })
    .value();

    obj.parent = this.parent ? this.parent.uuid : null;
    if (_.isEmpty(obj.children))
        obj.children = null;

    return obj;
};


ThinTree.extend = function(proto) {
    var Fn = __extends(proto, ThinTree);
    return Fn;
}


module.exports = ThinTree;


var __hasProp = {}.hasOwnProperty;
var __extends = function(protoTripe, Parent) {
    function Child() {
        Child.__super__.constructor.apply(this, arguments);
    };
    _.assign(Child.prototype, protoTripe);

    for (var key in Parent) {
        if (__hasProp.call(Parent, key)) Child[key] = Parent[key];
    }

    function Ctor() {
        this.constructor = Child;
    }
    Ctor.prototype = Parent.prototype;
    Child.prototype = new Ctor();
    Child.__super__ = Parent.prototype;

    return Child;
};

tree-recurse.js

    firstSubtree: function(query, op, iterator, callback, acc) {
        return this[op](query) || this[iterator](callback, acc)
    },

    everySubtree: function(query, op, iterator, callback) {
        return this[iterator](callback, this[op](query))
    },

    recurse: function(recurse) {
        var satisfied = recurse.satisfied;
        var iterable = recurse.iterable;
        var iterator = recurse.iterator;
        var next = recurse.next
        var result = iterator(iterable(this));
        return satisfied(result) ? result : next(result, this);
    },

    findTree: function(query) {
        this.recurse({
            satisfied: _.identity,
            iterator: _.partialRight(_.find, query),
            iterable: function (node) { return node.getChildren(); },
            next: function(result, node){
                return _.reduce(iterable, function(acc, node) {
                    return result || node.recurse
                }, result)
            },
        });
    }
    findParent: function(query) {
        this.recurse({
            next: function(result){
                if result
                _.each(result, function(node) {
                    node.recurse(next, iterable, iterator)
                })
            },
            iterator: function(iterable) {
                return _.find(iterable, query);
            },
            iterable: function (node) {
                return node.getChildren();
            }
        });
    }
    // recurse: function(oper, query, iter, callback, acc) {
    //     var self = this;
    //     oper = oper || 'noop';
    //     iter = iter || 'each';
    //     callback = callback || function(acc, node) {
    //         return node.recurse(oper, query, iter, callback, acc);
    //     }
    //     return (
    //         (_.isFunction(oper) ? oper : self[oper])(query)
    //     ||  (_.isFunction(iter) ? iter : self[iter])(callback, acc, query)
    //     );
    // }