TreeEnumerator

/*
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.data.*;
import playground.classes.data.tree.*;
import org.asapframework.util.debug.Console;

/**
Straightforward enumeration (iterator) class for {@link Tree} objects. TreeEnumerator has one way of iterating: forward ({@link #getNextObject}). . For more options see {@link TraverseTreeEnumerator}.

Important note: the Tree object should not be modified while iterating over it.
@author Arthur Clemens
@version 20 July 2005
@use
<code>
var myTree:Tree = new Tree();
// fill the tree ...

// Create an enumerator and pass the start node to traverse:
var enumerator:TreeEnumerator = new TreeEnumerator(myTree.root);
var node:TreeNode;
while (node = TreeNode(enumerator.getNextObject())) {
    if (node == myTree.root) continue;
    trace(node.name);
}
</code>
*/

class playground.classes.data.tree.TreeEnumerator extends Enumerator {

    private var mRootNode:TreeNode; /**< The root node. May be set to any node. */
    private var mCurrentNode:TreeNode; /**< The current state (node). */
    private var mZeroNode:ZeroNode; /**< Abtract position before the first node. */
    private var mLastNode:TreeNode; /**< Last node of the Tree; for performance reasons searched only once in the constructor. */

    /**
    Creates a TreeEnumerator. 
    @param inRootNode: the root node of the enumerator; you may pass any node of the tree if the enumerator should start at that root - <b>but the enumerator will traverse that branch only</b> and will not traverse upwards to a node with a lower depth.
    */
    public function TreeEnumerator (inRootNode:TreeNode) {
        super();
        if (inRootNode == undefined) {
            Console.ERROR(toString() + "; constructor: root node must be passed.");
            return;
        }
        setRoot(inRootNode);
    }
    
    /**
    Returns the current node. 
    @usageNote When the enumerator is created, the enumerator position is at a virtual node {@link ZeroNode} one place before the first tree node. At this 'null position', calling {@code getCurrentObject} returns an error. Therefore, you must always call {@link #getNextObject} to advance the enumerator to the first node before reading the value of {@code getCurrentObject}.
    The method {@link #reset} brings the enumerator back to the null position.
    @return The current TreeNode node.
    */
    public function getCurrentObject () : TreeNode {
        if (mCurrentNode == mZeroNode) {
            Console.ERROR(toString() + "; getCurrentObject: invalid position.");
            return null;
        }
        // else
        return mCurrentNode;
    }
    
    /**
    Sets the enumerator's current object to another TreeNode.
    @param inTreeNode : the new tree node
    @implementationNote Calls {@link #update}.
    @example
    <code>
    var newNode:TreeNode = mTree.getNode("Help");
    mEnumerator.setCurrentObject(newNode);
    </code>
    */
    public function setCurrentObject (inTreeNode:TreeNode) : Void {
        if (mCurrentNode.owner != inTreeNode.owner) {
            Console.ERROR(toString() + "; setCurrentObject: node is not part of the enumerator tree.");
            return;
        }
        // else
        update(inTreeNode);
    }
    
    /**
    Sets a different node as root node.
    @param inRootNode : the new root node
    @param updateCurrentObjectToRoot : sets the current object to the new root node
    */
    public function setRoot (inRootNode:TreeNode,
                             updateCurrentObjectToRoot:Boolean) : Void {

        mRootNode = inRootNode;
        mZeroNode = new ZeroNode();
        mZeroNode.owner = mRootNode.owner;
        mLastNode = inRootNode.getLastNode();
        mCurrentNode = (updateCurrentObjectToRoot == true) ? mRootNode : mZeroNode;
    }
    
    /**
    Collects all nodes of the iterator's tree, or of a particular branche.
    @param inStartNode : (optional) If a node is passed, {@code getAllObjects} collects all nodes of the current branch, taking {@code inRootNode} as the root node (and setting {@code inRootNode} as the first node of the returned array); when not defined the TreeEnumerator's {@link #mRootNode root node} is used.
    @return An array with all TreeNode objects.
    @example
    The following line creates an array with all the nodes starting with the node named "Games":
    <code>
    var gameNode:TreeNode = tree.getNode("Games");
    var gameNodes:Array = myEnumerator.getAllObjects(gameNode);
    </code>
    */
    public function getAllObjects (inStartNode:TreeNode) : Array {

        var all:Array = new Array();
        var startNode:TreeNode = (inStartNode != undefined) ? inStartNode : mRootNode;
        var e:TreeEnumerator = new TreeEnumerator(startNode);
        var node:TreeNode;
        while (node = e.getNextObject()) {
            all.push(node);
        }
        delete e; e = null;
        return all;
    }

    /**
    Puts the enumerator just before the first tree node. At this point calling {@link #getCurrentObject} will generate an error; you must first move the enumerator using {@link #getNextObject}.
    @implementationNote Calls {@link #update}.
    */    
    public function reset () : Void {
        update(mZeroNode);
    }
    
    /**
    Checks if there is an object after the current object.
    @return True: there is a next object; false: the current object is the last.
    */
    public function hasNextObject () : Boolean {
        var nextNode:TreeNode = performGetNextObject();
        if (nextNode != null) {
            return true;
        }
        return false;
    }
    
    /**
    Moves the enumerator one position forward and returns that node.
    @return The new current node; when no valid node is found, returns null.
    @example
    <code>
    var e:TreeEnumerator = new TreeEnumerator(mTree.root);
    var node:TreeNode;
    while (node = e.getNextObject()) {
        //
    }
    </code>
    @implementationNote Calls {@link #update}.
    */
    public function getNextObject () : TreeNode {
        var nextNode:TreeNode = performGetNextObject();
        if (nextNode != null) {
            return update(nextNode);
        }
        return null;
    }
    
    /**
    @see #getNextObject
    */
    private function performGetNextObject () : TreeNode {
        if (mCurrentNode == mZeroNode) {
            return mRootNode;
        }
        if (mCurrentNode == mLastNode) {
            return null;
        }
        if (mCurrentNode.firstChild != undefined) {
            return getFirstChildFW();
        }
        // ELSE - THIS NODE HAS NO CHILDREN
        return getNextSiblingFW(false);
    }
    
    /**
    @exclude
    */
    public function toString () : String {

        return "(TreeEnumerator) - root node = " + mRootNode + "; current node = " + mCurrentNode;
    }
    
    // PRIVATE METHODS
    
    /**
    Sets the current node to the passed inNewNode.
    @param inNewNode : the new node
    @return The new current node.
    */
    private function update (inNewNode:TreeNode) : TreeNode {

        mCurrentNode = inNewNode;
        return mCurrentNode;
    }
    
    // FORWARD TRAVERSAL METHODS
    
    /**
    Gets the first child of the current node.
    @return The found node; if no node found, returns null.
    */
    private function getFirstChildFW () : TreeNode {

        var nextNode:TreeNode = TreeNode(mCurrentNode.firstChild);
        if (nextNode == null) {
            return null;
        }
        return nextNode;
    }
    
    /**
    Gets the first sibling (sharing the same parent) of the current node.
    @param inFindSameDepth : (true or false) true: the found node must match the current node's depth; default false
    @return The found node; if no node found, returns null.
    */
    private function getNextSiblingFW (inFindSameDepth:Boolean) : TreeNode {

        var nextNode:TreeNode = getForwardNode(mCurrentNode, inFindSameDepth);
        if (nextNode == null) {
            return null;
        }
        return nextNode;
    }
    
    /**
    Recursive method, initially called by {@link #getNextSiblingFW}.
    @param inTempNode : storage of temporary current node while recursing 
    @param inFindSameDepth : (true or false) true: the found node must match the current node's depth; default false
    @return The found node; if no node found, returns null.
    */
    private function getForwardNode (inTempNode:TreeNode,
                                     inFindSameDepth:Boolean) : TreeNode {

        if (inTempNode.parent == null) { // terminate condition
            return null;
        }
        if ((inTempNode.parent.children.length - 1) > inTempNode.position) {
            // found parent that has a next sibling
            var nextNode:TreeNode = inTempNode.parent.children[inTempNode.position + 1];
            return nextNode;
        }
        // this node is the last child or the only child
        // move up one parent
        if (!inFindSameDepth) {
            return getForwardNode(inTempNode.parent, inFindSameDepth);
        }
    }
    
}