YUI.add('tree', function (Y, NAME) {

/*jshint boss:true, expr:true, onevar:false */

/**

Provides a generic tree data structure and related functionality.

A tree has a root node, which may contain any number of child nodes, which may

themselves contain child nodes, ad infinitum.

Child nodes are lightweight function instances which delegate to the tree for

all significant functionality, so trees remain performant and memory-efficient

even with thousands and thousands of nodes.

@module tree

@main tree

**/

/**

The `Tree` class represents a generic tree data structure. A tree has a root

node, which may contain any number of child nodes, which may themselves contain

child nodes, ad infinitum.

This class doesn't expose any UI, but is intended to be used as a data structure

or base class for other components. For example, the SmugMug TreeView gallery

module extends Tree and provides a TreeView UI.

@class Tree

@param {Object} [config] Config options.

    @param {Object[]|Tree.Node[]} [config.nodes] Array of tree node config

        objects or `Tree.Node` instances to add to this tree at initialization

        time.

    @param {Object|Tree.Node} [config.rootNode] Node to use as the root node of

        this tree.

@constructor

@extends Base

**/

var Lang = Y.Lang,

    /**

    Fired when a node is added to this Tree. The `src` property will indicate

    how the node was added ("append", "insert", "prepend", etc.).

    @event add

    @param {Number} index Index at which the node will be added.

    @param {Tree.Node} node Node being added.

    @param {Tree.Node} parent Parent node to which the node will be added.

    @param {String} src Source of the event ("append", "insert", "prepend",

        etc.).

    @preventable _defAddFn

    **/

    EVT_ADD = 'add',

    /**

    Fired when this Tree is cleared.

    @event clear

    @param {Tree.Node} rootNode New root node of this tree (the old root node is

        always destroyed when a tree is cleared).

    @param {String} src Source of the event.

    @preventable _defClearFn

    **/

    EVT_CLEAR = 'clear',

    /**

    Fired when a node is removed from this Tree.

    @event remove

    @param {Boolean} destroy Whether or not the node will be destroyed after

        being removed from this tree.

    @param {Tree.Node} node Node being removed.

    @param {Tree.Node} parent Parent node from which the node will be removed.

    @param {String} src Source of the event.

    @preventable _defRemoveFn

    **/

    EVT_REMOVE = 'remove';

var Tree = Y.Base.create('tree', Y.Base, [], {

    // -- Public Properties ----------------------------------------------------

    /**

    Reference to the `children` array of this Tree's `rootNode`.

    This is a convenience property to allow you to type `tree.children` instead

    of `tree.rootNode.children`.

    @property {Tree.Node[]} children

    @readOnly

    **/

    /**

    The `Tree.Node` class or subclass that should be used for nodes created by

    this tree.

    You may specify an actual class reference or a string that resolves to a

    class reference at runtime.

    @property {String|Tree.Node} nodeClass

    @default Y.Tree.Node

    **/

    nodeClass: Y.Tree.Node,

    /**

    Optional array containing one or more extension classes that should be mixed

    into the `nodeClass` when this Tree is instantiated. The resulting composed

    node class will be unique to this Tree instance and will not affect any

    other instances, nor will it modify the defined `nodeClass` itself.

    This provides a late-binding extension mechanism for nodes that doesn't

    require them to extend `Y.Base`, which would incur a significant performance

    hit.

    @property {Array} nodeExtensions

    @default []

    **/

    nodeExtensions: [],

    /**

    Root node of this Tree.

    @property {Tree.Node} rootNode

    @readOnly

    **/

    // -- Protected Properties -------------------------------------------------

    /**

    Simple way to type-check that this is a Tree instance.

    @property {Boolean} _isYUITree

    @default true

    @protected

    **/

    _isYUITree: true,

    /**

    Composed node class based on `nodeClass` that mixes in any extensions

    specified in `nodeExtensions`. If there are no extensions, this will just be

    a reference to `nodeClass`.

    @property {Tree.Node} _nodeClass

    @protected

    **/

    /**

    Mapping of node ids to node instances for nodes in this tree.

    @property {Object} _nodeMap

    @protected

    **/

    /**

    Default config object for the root node.

    @property {Object} _rootNodeConfig

    @protected

    **/

    _rootNodeConfig: {canHaveChildren: true},

    // -- Lifecycle ------------------------------------------------------------

    initializer: function (config) {

        config || (config = {});

        if (config.nodeClass) {

            this.nodeClass = config.nodeClass;

        }

        if (config.nodeExtensions) {

            this.nodeExtensions = this.nodeExtensions.concat(config.nodeExtensions);

        }

        /**

        Hash of published custom events.

        @property {Object} _published

        @default {}

        @protected

        **/

        this._published || (this._published = {});

        this._nodeMap = {};

        // Allow all extensions to initialize, then finish up.

        this.onceAfter('initializedChange', function () {

            this._composeNodeClass();

            this.clear(config.rootNode, {silent: true});

            if (config.nodes) {

                this.insertNode(this.rootNode, config.nodes, {silent: true});

            }

        });

    },

    destructor: function () {

        this.destroyNode(this.rootNode, {silent: true});

        this.children   = null;

        this.rootNode   = null;

        this._nodeClass = null;

        this._nodeMap   = null;

        this._published = null;

    },

    // -- Public Methods -------------------------------------------------------

    /**

    Appends a node or array of nodes as the last child of the specified parent

    node.

    If a node being appended is from another tree, it and all its children will

    be removed from that tree and moved to this one.

    @method appendNode

    @param {Tree.Node} parent Parent node.

    @param {Object|Object[]|Tree.Node|Tree.Node[]} node Child node, node config

        object, array of child nodes, or array of node config objects to append

        to the given parent. Node config objects will automatically be converted

        into node instances.

    @param {Object} [options] Options.

        @param {Boolean} [options.silent=false] If `true`, the `add` event will

            be suppressed.

    @return {Tree.Node|Tree.Node[]} Node or array of nodes that were

        appended.

    **/

    appendNode: function (parent, node, options) {

        return this.insertNode(parent, node, Y.merge(options, {

            index: parent.children.length,

            src  : 'append'

        }));

    },

    /**

    Clears this tree by destroying the root node and all its children. If a

    `rootNode` argument is provided, that node will become the root node of this

    tree; otherwise, a new root node will be created.

    @method clear

    @param {Object|Tree.Node} [rootNode] If specified, this node will be used as

        the new root node.

    @param {Object} [options] Options.

        @param {Boolean} [options.silent=false] If `true`, the `clear` event

            will be suppressed.

        @param {String} [options.src] Source of the change, to be passed along

            to the event facade of the resulting event. This can be used to

            distinguish between changes triggered by a user and changes

            triggered programmatically, for example.

    @chainable

    **/

    clear: function (rootNode, options) {

        return this._fireTreeEvent(EVT_CLEAR, {

            rootNode: this.createNode(rootNode || this._rootNodeConfig),

            src     : options && options.src

        }, {

            defaultFn: this._defClearFn,

            silent   : options && options.silent

        });

    },

    /**

    Creates and returns a new `Tree.Node` instance associated with (but not

    yet appended to) this tree.

    @method createNode

    @param {Object|Tree.Node} [config] Node configuration. If a `Tree.Node`

        instance is specified instead of a config object, that node will be

        adopted into this tree (if it doesn't already belong to this tree) and

        removed from any other tree to which it belongs.

    @return {Tree.Node|null} New node, or `null` if a node could not be created

        from the given _config_.

    **/

    createNode: function (config) {

        config || (config = {});

        // If `config` is already a node, just ensure it hasn't been destroyed

        // and is in the node map, then return it.

        if (config._isYUITreeNode) {

            if (config.state.destroyed) {

                Y.error('Cannot insert a node that has already been destroyed.', null, 'tree');

                return null;

            }

            this._adoptNode(config);

            return config;

        }

        // First, create nodes for any children of this node.

        if (config.children) {

            var children = [];

            for (var i = 0, len = config.children.length; i < len; i++) {

                children.push(this.createNode(config.children[i]));

            }

            config = Y.merge(config, {children: children});

        }

        var node = new this._nodeClass(this, config);

        return this._nodeMap[node.id] = node;

    },

    /**

    Removes and destroys a node and all its child nodes. Once destroyed, a node

    is eligible for garbage collection and cannot be reused or re-added to the

    tree.

    @method destroyNode

    @param {Tree.Node} node Node to destroy.

    @param {Object} [options] Options.

        @param {Boolean} [options.silent=false] If `true`, `remove` events will

            be suppressed.

        @param {String} [options.src] Source of the change, to be passed along

            to the event facade of the resulting events. This can be used to

            distinguish between changes triggered by a user and changes

            triggered programmatically, for example.

    @chainable

    **/

    destroyNode: function (node, options) {

        var child, i, len;

        options || (options = {});

        for (i = 0, len = node.children.length; i < len; i++) {

            child = node.children[i];

            // Manually remove the child from its parent; this makes destroying

            // all children of the parent much faster since there's no splicing

            // involved.

            child.parent = null;

            // Destroy the child.

            this.destroyNode(child, options);

        }

        if (node.parent) {

            this.removeNode(node, options);

        }

        node.children  = [];

        node.data      = {};

        node.state     = {destroyed: true};

        node.tree      = null;

        node._indexMap = {};

        delete this._nodeMap[node.id];

        return this;

    },

    /**

    Removes all children from the specified node. The removed children will

    still be reusable unless the `destroy` option is truthy.

    @method emptyNode

    @param {Tree.Node} node Node to empty.

    @param {Object} [options] Options.

        @param {Boolean} [options.destroy=false] If `true`, the children will

            also be destroyed, which makes them available for garbage collection

            and means they can't be reused.

        @param {Boolean} [options.silent=false] If `true`, `remove` events will

            be suppressed.

        @param {String} [options.src] Source of the change, to be passed along

            to the event facade of the resulting events. This can be used to

            distinguish between changes triggered by a user and changes

            triggered programmatically, for example.

    @return {Tree.Node[]} Array of removed child nodes.

    **/

    emptyNode: function (node, options) {

        var children = node.children,

            removed  = [];

        for (var i = children.length - 1; i > -1; --i) {

            removed[i] = this.removeNode(children[i], options);

        }

        return removed;

    },

    /**

    Performs a depth-first traversal of _node_, passing it and each of its

    descendants to the specified _callback_, and returning the first node for

    which the callback returns a truthy value.

    Traversal will stop as soon as a truthy value is returned from the callback.

    See `traverseNode()` for more details on how depth-first traversal works.

    @method findNode

    @param {Tree.Node} node Node to traverse.

    @param {Object} [options] Options.

        @param {Number} [options.depth] Depth limit. If specified, descendants

            will only be traversed to this depth before backtracking and moving

            on.

    @param {Function} callback Callback function to call with the traversed

        node and each of its descendants. If this function returns a truthy

        value, traversal will be stopped and the current node will be returned.

        @param {Tree.Node} callback.node Node being traversed.

    @param {Object} [thisObj] `this` object to use when executing _callback_.

    @return {Tree.Node|null} Returns the first node for which the _callback_

        returns a truthy value, or `null` if the callback never returns a truthy

        value.

    **/

    findNode: function (node, options, callback, thisObj) {

        var match = null;

        // Allow callback as second argument.

        if (typeof options === 'function') {

            thisObj  = callback;

            callback = options;

            options  = {};

        }

        this.traverseNode(node, options, function (descendant) {

            if (callback.call(thisObj, descendant)) {

                match = descendant;

                return Tree.STOP_TRAVERSAL;

            }

        });

        return match;

    },

    /**

    Returns the tree node with the specified id, or `undefined` if the node

    doesn't exist in this tree.

    @method getNodeById

    @param {String} id Node id.

    @return {Tree.Node} Node, or `undefined` if not found.

    **/

    getNodeById: function (id) {

        return this._nodeMap[id];

    },