Tree

/*
Copyright 2005-2006 by the authors of asapframework, http://asapframework.org

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/

import org.asapframework.util.debug.Console;
import org.asapframework.data.*;
import playground.classes.data.tree.*;

/**
All sorts of information is hierarchical and can be represented by a tree structure: websites, photo albums, topic knowledge, etcetera.
Tree is a position tree: each tree node has exactly one parent node and can have multiple children. The root node has no parent.

A Tree can contain any kind of node, as long as it is a TreeNode or a subclass thereof, and if it implements its own constructor and {@link TreeNode#createNewNode} method. See {@link BaseTreeNode}.

@author Arthur Clemens
@version 24 July 2005
@implementationNote mUsesCache is default off (false) until all side cases can be catered for.
@todo Update cache when TreeNode changes name (would this happen?). In that case name changes should occur via the Tree, not on the node directly
@todo Clear cache
@todo Removal of nodes (by name and object)
*/

class playground.classes.data.tree.Tree {
    
    private var mName:String = "anonymous Tree"; /**< Identifier name. */
    private var mRoot:TreeNode;
    private var mUsesCache:Boolean = false; /**< Whether Tree uses a cache to store {@code [node name]->node} relations. */
    private var mUsesErrorChecking:Boolean = false; /**< If true, {@link #addChild} checks if a node with the given name already exists in the Tree. */
    private var mNodeNamesCache:Object; /**< Cache; associative array of {@code [node name]:String ->node:TreeNode}, to speed up lookup with {@link #getNode}.*/
    public static var ROOT_NODE_NAME:String = "__root__";
    
    /**
    Creates a Tree object.
    @param inName : (optional) name for this tree; useful for debugging
    */
    function Tree (inName:String) {

        mNodeNamesCache = new Object();
        if (inName != undefined) {
            mName = inName;
        }
    }
    
    /**
    Creates a root node of the default type. The default type is {@link TreeNode}, but that may be other types for Tree subclasses.
    @param inName : (optional) name of the new root node; if no name is passed, a new root node is created with the name {@link #ROOT_NODE_NAME}.
    @return The newly created root node.
    @implementationNote Calls {@link #createNewNode}.
    */
    public function createRootNode (inName:String) : TreeNode {

        var root:TreeNode = (inName != undefined) ? createNewNode(inName) : createNewNode(Tree.ROOT_NODE_NAME);
        root.owner = this;
        root.parent = null;
        root.depth = 0;
        mRoot = root;
        return mRoot;
    }
    
    /**
    Sets an existing node as root node.
    @param inNode: the TreeNode object to set as root node
    @example
    <code>
    mTree = new Tree();
    var rootNode:MyNode = new MyNode(Tree.ROOT_NODE_NAME);
    mTree.setRootNode(rootNode);
    </code>
    */
    public function setRootNode (inNode:TreeNode) : Void {

        mRoot = inNode;
        mRoot.owner = this;
        mRoot.depth = 0;
        mRoot.parent = null;
    }
    
    /**
    The root object of this (sub)tree.
    */
    public function get root () : TreeNode {

        return mRoot;
    }
    
    /**
    The root object of this (sub)tree.
    */
    public function get name () : String {

        return mName;
    }
    
    /**
    Turns cacheing on or off.
    @param inFlag: true: Tree uses a cache to store {@code [node name]->node} relations; false: no cache is used.
    */
    public function setUsesCache (inFlag:Boolean) : Void {

        mUsesCache = inFlag;
    }
    
    /**
    Turns error checking on or off while adding nodes. If on, and a duplicate name is found, the new node is not added to the Tree.
    Use error checking if you plan to use unique node names. Otherwise you can use {@link TreeNode#namePath} to uniquely identify nodes.
    @param inFlag: true: error checking is performed when adding child nodes: if the node name is valid, and if the node name already exists
    */
    public function setUsesErrorChecking (inFlag:Boolean) : Void {

        mUsesErrorChecking = inFlag;
    }
    
    /**
    Adds a child node to a node in the tree structure. If error checking is on and a node with name {@code inNewNode} is already in the Tree, the new node is not added.
    @param inNewNode : (required) the new node to attach to the tree (type TreeNode or String). If a string, a new node is created with the passed name (the identifier name should be without spaces; functions as unique identifier, so no other nodes with this name can exist). If a TreeNode, this node is attached.
    @param inParentNode : (optional) existing tree node to attach the new node to. Type TreeNode or String. If no node is passed, the new node is attached to the Tree's root node. 
    @param inProperties : (optional) a KeyValueList that stores key-value properties of the new node
    @return The newly added TreeNode object.
    @implementationNote Calls {@link TreeNode#addChild}.
    */
    public function addChild (inNewNode:Object,
                              inParentNode:Object,
                              inProperties:KeyValueList) : TreeNode {

        var parentNode:TreeNode;
        if (inParentNode == undefined) {
            parentNode = mRoot;
        } else {
            if (typeof inParentNode == "string") {
                parentNode = getNode(String(inParentNode));
            } else if (TreeNode(inParentNode) instanceof TreeNode) {
                parentNode = TreeNode(inParentNode);
            }
        }
        if (parentNode == null) {
            Console.ERROR("Tree addChild: no node found to attach new node '" + inNewNode + "' to.");
            return null;
        }
        
        if (mUsesErrorChecking) {
            if (typeof inNewNode == "string") {
                var name:String = String(inNewNode);
                if (!TreeNode.isValidName(name)) {
                    Console.ERROR("Tree addChild: '" + name + "' is not a valid node name.");
                    return null;
                }
                if (containsNodeWithName(name)) {
                    Console.ERROR("Tree addChild: node name '" + name + "' already exists in tree.");
                    return null;
                }
            } else if (TreeNode(inNewNode) instanceof TreeNode) {
                //
            } else {
                Console.ERROR("Tree addChild: no valid type passed.");
                return null;
            }
        }
        var newNode:TreeNode = parentNode.addChild(inNewNode, inProperties);
        if (newNode == null) {
            Console.ERROR("Tree addChild: error adding child node: '" + inNewNode + "'");
            return null;
        }
        return newNode;
    }
    
    /**
    Checks whether a node with given name is already attached to the Tree. Called when {@link #setUsesErrorChecking} is set to true.
    @return True: a node exists; false: no node exists with that name.
    */
    public function containsNodeWithName (inNodeName:String) : Boolean {

        return (getNode(inNodeName) != null);
    }
    
    /**
    Gets the node by looking up its name.
    @param inNodeName : name of node
    @return The found TreeNode object; if no node is found, returns null.
    @implementationNote Because the lookup of the node can be time costly, found nodes are stored in the (cached) associative array {@link #mNodeNamesCache}. When {@code getNode} is called, {@code mNodeNamesCache} is first consulted.
    @implementationNote Calls {@link TreeNode#getNode}.
    */
    public function getNode (inNodeName:String) : TreeNode {

        if (inNodeName == undefined) {
            Console.ERROR("Tree getNode: inNodeName is undefined.");
            return null;
        }
        var node:TreeNode = null;
        if (mUsesCache) {
            // first try if already cached
            node = mNodeNamesCache[inNodeName];
        }
        if (node != undefined) {
            return node;
        } else {
            // else not cached yet, or cache is set to off
            // find the node recursively, starting with fixed root
            node = mRoot.getNode(inNodeName);
            if (node != undefined) {
                if (mUsesCache) {
                    // store for future use
                    mNodeNamesCache[inNodeName] = node;
                }
                return node;
            }
        }
        // Nothing found - but do not report an error here: this method is also called by containsNodeWithName (when addChild is called) so it is normal that this method returns null.
        return null;
    }
    
    /**
    Gets the node by looking up its name path.
    @param inNodeNamePath : name path of node (see {@link TreeNode#namePath})
    @return The found TreeNode object; if no node is found, returns null.
    @implementationNote Because the lookup of the node can be time costly, found nodes are stored in the (cached) associative array {@link #mNodeNamesCache}. When {@code getNodeWithPath} is called, {@code mNodeNamesCache} is first consulted.
    @implementationNote Calls {@link TreeNode#getNodeWithAbsolutePath}.
    */
    public function getNodeWithPath (inNodeNamePath:String) : TreeNode {

        if (inNodeNamePath == undefined) {
            Console.ERROR("Tree getNodeWithPath: inNodeNamePath is undefined.");
            return null;
        }
        var node:TreeNode = null;
        if (mUsesCache) {
            // first try if already cached
            node = mNodeNamesCache[inNodeNamePath];
        }
        if (node != undefined) {
            return node;
        } else {
            // else not cached yet, or cache is set to off
            // find the node recursively, starting with fixed root
            node = mRoot.getNodeWithAbsolutePath(inNodeNamePath);
            if (node != undefined) {
                if (mUsesCache) {
                    // store for future use
                    mNodeNamesCache[inNodeNamePath] = node;
                }
                return node;
            }
        }
        return null;
    }
    
    /**
    Counts the number of nodes from the root node.
    */
    public function getCount () : Number {

        return mRoot.count;
    }
    
    /**
    Finds the last node in current branch of the tree.
    @return The last node (TreeNode).
    @implementationNote Calls {@link TreeNode#getLastNode}.
    */
    public function getLastNode () : TreeNode {

        return mRoot.getLastNode();
    }
    
    /**
    Deletes all nodes from the tree, including the root node.
    */
    public function clear () : Void {

        mRoot.deleteChildren(true);
        mRoot.kill();
        delete mRoot; mRoot = null;
    }
    
    /**
    Prints the node structure by calling {@link TreeNode#printNodes} recursively.
    */
    public function printNodes () : Void {

        mRoot.printNodes("");
    }
    
    /**
    @exclude
    */
    public function toString () : String {

        return "(Tree) " + mName;
    }
    
    // PRIVATE METHODS
    
    /**
    Creates a new node of the default type TreeNode. Called by {@link #createRootNode}.
    */
    private function createNewNode (inName:String) : TreeNode {

        return new TreeNode(inName);
    }
    
}