TraverseTreeEnumerator

/*
Copyright 2005 by the authors of asapframework

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 data.Enumerator;
import data.tree.*;

// macromedia classes
import mx.events.EventDispatcher;

/**
Enhanced tree enumerator, with traversal options (traverse children, loop and skip root), a delegate to validate new states and dispatching of update events.

About traverse options, see {@link TraverseTreeOptions}.
@author Arthur Clemens
@version 20 July 2005
@todo When setting a new root, should the depths of the containing nodes be relative to root's depth? For instance if I set a node with depth 2 to root, should the next node of depth 3 be regarded as a node of depth 1?
*/

class data.tree.TraverseTreeEnumerator extends TreeEnumerator {

    private var mTraverseOptions:Number = TraverseTreeOptions.TRAVERSE_CHILDREN;
    private var mDelegateObject:Object;
    private var mDelegateMethod:String;
    
    // mix-in EventDispatcher
    private var dispatchEvent:Function;
    public var addEventListener:Function;
    public var removeEventListener:Function;
    
    /**
    Creates a new TraverseTreeEnumerator and initializes it for dispatching events.
    @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.
    @param inTraverseOptions: Tells the enumerator how to do traversing; see {@link TraverseTreeOptions}. Default set to {@link TraverseTreeOptions#TRAVERSE_CHILDREN}.
    */
    public function TraverseTreeEnumerator (inRootNode:TreeNode,
                                            inTraverseOptions:Number)
    {
        super(inRootNode);
        if (inTraverseOptions != undefined) {
            mTraverseOptions = inTraverseOptions;
        }
        EventDispatcher.initialize(this);
    }
    
    /**
    The traversal options; see {@link TraverseTreeOptions}.
    */
    public function set traverseOptions (inTraverseOptions:Number) : Void
    {
        mTraverseOptions = inTraverseOptions;
    }
    
    public function get traverseOptions () : Number
    {
        return mTraverseOptions;
    }
    
    /**
    A delegate validation method is called in {@link #update} when a delegate object is set. The delegate's validation method is called to evaluate the new node before it is set.
    @param inDelegateObject: the owner of the delegate method
    @param inDelegateMethod: node validation method; this method should accept a TreeNode as parameter and return a Boolean to indicate the node's validity.
    */
    public function setDelegate (inDelegateObject:Object,
                                 inDelegateMethod:String) : Void
    {
        mDelegateObject = inDelegateObject;
        mDelegateMethod = inDelegateMethod;
    }

    /**
    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 (inTraverseOptions:Number) : Boolean
    {
        var nextNode:TreeNode = performGetNextObject(inTraverseOptions);
        if (nextNode != null) {
            return true;
        }
        return false;
    }
    
    /**
    Moves the enumerator one position forward and returns that node.
    @param inTraverseOptions (optional): the traversal options (see {@link TraverseTreeOptions}); if not passed, the stored {@code mTraverseOptions} are used
    @return The return value of {@link #update}.
    */
    public function getNextObject (inTraverseOptions:Number) : TreeNode
    {
        var nextNode:TreeNode = performGetNextObject(inTraverseOptions);
        if (nextNode != null) {
            return update(nextNode);
        }
        return null;
    }

    /**
    Moves the enumerator one position backward and returns that node.
@param inTraverseOptions (optional): the traversal options (see {@link TraverseTreeOptions}); if not passed, the stored {@code mTraverseOptions} are used
    @return The return value of {@link #update}.
    */
    public function getPreviousObject (inTraverseOptions:Number) : TreeNode
    {
        var nextNode:TreeNode = performGetPreviousObject(inTraverseOptions);
        if (nextNode != null) {
            return update(nextNode);
        }
        return null;
    }
    
    /**
    Gets the next node with the given depth and set the current node to the found node.
    @param inDepth: the hierarchical depth of the node; see {@link TreeNode#depth}
    @param inTraverseOptions (optional): the traversal options (see {@link TraverseTreeOptions}); if not passed, the stored {@code mTraverseOptions} are used
    @return If found, the return value of {@link #update}; null if not found.
    */
    public function getNextNodeWithDepth (inDepth:Number,
                                          inTraverseOptions:Number) : TreeNode
    {
        var enumerator:TraverseTreeEnumerator = new TraverseTreeEnumerator(mCurrentNode.owner.root);
        enumerator.setCurrentObject(mCurrentNode);
        var nextNode:TreeNode;
        var startNode:TreeNode = mCurrentNode;
        while (nextNode = enumerator.getNextObject(inTraverseOptions)) {
            if (nextNode.depth == inDepth) {
                break;
            }
            if (nextNode == startNode) { // terminate condition, if looping
                return null;
            }
            if (nextNode == null) { // terminate condition
                return null;
            }
        }
        if (nextNode != null) {
            return update(nextNode);
        }
    }
    
    /**
    @exclude
    */
    public function toString () : String
    {
        return "(TraverseTreeEnumerator) - root node = " + mRootNode + "; current node = " + mCurrentNode;
    }
    
    // PRIVATE METHODS
    
    /**
    @see #getNextObject
    */
    private function performGetNextObject (inTraverseOptions:Number) : TreeNode
    {
        if (mCurrentNode == mZeroNode) {
            mCurrentNode = mRootNode;
            return mCurrentNode;
        }

        var traverseOptions:Number = (inTraverseOptions != undefined) ? inTraverseOptions : mTraverseOptions;

        if (mCurrentNode == mRootNode) {
            // THIS IS ROOT
            if (!(traverseOptions & TraverseTreeOptions.TRAVERSE_CHILDREN)) {
                return null;
            }
        }
        
        if (traverseOptions & TraverseTreeOptions.LOOP) {
            if (mCurrentNode == mCurrentNode.owner.getLastNode() || mCurrentNode == mZeroNode) {
                // THIS IS THE VERY LAST NODE
                if (!(traverseOptions & TraverseTreeOptions.SKIP_ROOT) && (traverseOptions & TraverseTreeOptions.TRAVERSE_CHILDREN)) {
                    return mRootNode;
                }
                if (traverseOptions & TraverseTreeOptions.SKIP_ROOT) {
                    return getFirstChildOfRootFW();
                }
            }
        }
        
        if (traverseOptions & TraverseTreeOptions.TRAVERSE_CHILDREN) {
            if (mCurrentNode.firstChild != undefined) {
                return getFirstChildFW();
            }
            // THIS NODE HAS NO CHILDREN
            var nextSibling:TreeNode = getNextSiblingFW(false);
            // Do no traverse upwards if root node has been set to other node
            if (nextSibling.depth <= mRootNode.depth) {
                nextSibling = null;
            }
            if (nextSibling != undefined) {
                return nextSibling;
            }
            if (nextSibling == null) {
                if (traverseOptions & TraverseTreeOptions.LOOP) {
                    if (!(traverseOptions & TraverseTreeOptions.SKIP_ROOT)) {
                        return mRootNode;
                    }
                    if (traverseOptions & TraverseTreeOptions.SKIP_ROOT) {
                        return getFirstChildOfRootFW();
                    }
                }
            }
        }
        if (!(traverseOptions & TraverseTreeOptions.TRAVERSE_CHILDREN)) {
            var isLastChild:Boolean = (mCurrentNode == mLastNode);
            if (isLastChild) {
                if (traverseOptions & TraverseTreeOptions.LOOP) {
                    return getFirstSiblingFW();
                }
                if (!(traverseOptions & TraverseTreeOptions.LOOP)) {
                    return null;
                }
            }
            if (!isLastChild) {
                return getNextSiblingFW(true);
            }
        }
        return null;
    }
    
    /**
    @see #getPreviousObject
    */
    private function performGetPreviousObject (inTraverseOptions:Number) : TreeNode
    {
        var traverseOptions:Number = (inTraverseOptions != undefined) ? inTraverseOptions : mTraverseOptions;
        
        if (mCurrentNode == mRootNode) {
            // THIS IS ROOT
            if (!(traverseOptions & TraverseTreeOptions.LOOP)) {
                // if not looping, root is the end
                return null;
            }
            if (!(traverseOptions & TraverseTreeOptions.TRAVERSE_CHILDREN)) {
                // if not traversing, root is the end
                return null;
            }
            if (traverseOptions & TraverseTreeOptions.TRAVERSE_CHILDREN) {
                // to the last node
                return mLastNode;
            }
        }

        // THIS IS NOT ROOT    
        if (mCurrentNode.position == 0) {
            // THIS IS A PARENT'S FIRST CHILD
            if (traverseOptions & TraverseTreeOptions.TRAVERSE_CHILDREN) {
                if (mCurrentNode.parent == mRootNode) {
                    // THIS IS ROOT'S FIRST CHILD
                    if ((traverseOptions & TraverseTreeOptions.SKIP_ROOT) && (traverseOptions & TraverseTreeOptions.LOOP)) {
                        return mLastNode;
                    } 
                    if (!(traverseOptions & TraverseTreeOptions.SKIP_ROOT)) {
                        return mRootNode;
                    }
                }
                if (mCurrentNode.parent != mRootNode) {
                    return getParentBW();
                }
            }
            if (!(traverseOptions & TraverseTreeOptions.TRAVERSE_CHILDREN)) {
                if (traverseOptions & TraverseTreeOptions.LOOP) {
                    // find the last node of the same depth
                    return getLastSiblingBW();
                }
                if (!(traverseOptions & TraverseTreeOptions.LOOP)) {
                    return null;
                }
            }
            // else
            return null;
        }
        if (mCurrentNode.position > 0) {
            // THIS IS NOT A PARENT'S FIRST CHILD
            if (traverseOptions & TraverseTreeOptions.TRAVERSE_CHILDREN) {
                return getVeryLastNodeOfPreviousSiblingBW();
            }
            if (!(traverseOptions & TraverseTreeOptions.TRAVERSE_CHILDREN)) {
                return getPreviousSiblingBW();
            }
        }        
        return null;
    }
    
    /**
    Updates the current node to the new node. If a delegate object has been set, its validation method is called before setting the new node. If the validation method returns false, no new node is set.
    @param inNewNode: the new node
    @return The new node; if the validation method returned false, the current node is returned.
    @sends TraverseTreeEnumeratorEvent#UPDATE If the delegate validation method exists and only if the delegate method returns true.
    */
    private function update (inNewNode:TreeNode) : TreeNode
    {
        if (mDelegateObject != null) {
            var method:Function = mDelegateObject[mDelegateMethod];
            var isValid:Boolean = method.apply(mDelegateObject, [inNewNode]);
            if (!isValid) {
                return mCurrentNode;
            }
        }
        mCurrentNode = inNewNode;
        dispatchEvent(new TraverseTreeEnumeratorEvent(TraverseTreeEnumeratorEvent.UPDATE, mCurrentNode));
        return mCurrentNode;
    }

    // FORWARD TRAVERSAL METHODS
    
    /**
    Gets the first child node of the root node.
    */
    private function getFirstChildOfRootFW () : TreeNode
    {
        var nextNode:TreeNode = TreeNode(mRootNode.firstChild);
        if (nextNode == null) {
            return null;
        }
        return nextNode;
    }
    
    /**
    Gets the first child of the current node's parent.
    */
    private function getFirstSiblingFW () : TreeNode
    {
        var nextNode:TreeNode = TreeNode(mCurrentNode.parent.firstChild);
        if (nextNode == null) {
            return null;
        }
        return nextNode;
    }
    
    // BACKWARD TRAVERSAL METHODS
    
    /**
    Gets the parent of the current node.
    */
    private function getParentBW () : TreeNode
    {
        var nextNode:TreeNode = TreeNode(mCurrentNode.parent);
        if (nextNode == null) {
            return null;
        }
        return nextNode;
    }
    
    /**
    Gets the very last child of the previous sibling of the current node.
    */
    private function getVeryLastNodeOfPreviousSiblingBW () : TreeNode
    {
        var nextNode:TreeNode = previousSibling().getLastNode();
        if (nextNode == null) {
            return null;
        }
        return nextNode;
    }

    /**
    Gets the last sibling of the current node.
    */
    private function getLastSiblingBW () : TreeNode
    {
        var nextNode:TreeNode = TreeNode(mCurrentNode.parent.children[mCurrentNode.parent.children.length-1]);
        if (nextNode == null) {
            return null;
        }
        return nextNode;
    }

    /**
    Gets the previous sibling of the current node.
    */
    private function getPreviousSiblingBW () : TreeNode
    {
        var nextNode:TreeNode = previousSibling();
        if (nextNode == null) {
            return null;
        }
        return nextNode;
    }
    
    /**
    Utility method called by {@link #getVeryLastNodeOfPreviousSiblingBW} and {@link #getPreviousSiblingBW}. Gets the previous sibling of the current node.
    */
    private function previousSibling () : TreeNode
    {
        return TreeNode(mCurrentNode.parent.children[mCurrentNode.position-1]);
    }

}