package org.jdesktop.swingx.tree;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Enumeration;
import java.util.NoSuchElementException;
import java.util.Queue;
import java.util.Vector;
import java.util.logging.Logger;

import javax.swing.tree.TreeModel;
import javax.swing.tree.TreeNode;
import javax.swing.tree.TreePath;

/**
 * Contains convenience classes/methods for handling hierarchical Swing structures.
 * 
 * @author Jeanette Winzenburg, Berlin
 */
@SuppressWarnings({ "unchecked", "rawtypes" })
public class TreeUtilities {

    /**
     * An enumeration that is always empty. 
     */
    public static final Enumeration EMPTY_ENUMERATION
        = new Enumeration() {
            @Override
            public boolean hasMoreElements() { return false; }
            @Override
            public Object nextElement() {
                throw new NoSuchElementException("No more elements");
            }
    };

    /**
     * Implementation of a preorder traversal of a TreeModel.
     */
    public static class PreorderModelEnumeration implements Enumeration {
        protected Deque<Enumeration> stack;
        protected TreeModel model;
        // the last component is the current subtree to travers
        private TreePath path;
        
        /**
         * Instantiates a preorder traversal starting from the root of the 
         * TreeModel.
         * 
         * @param model the TreeModel to travers.
         */
        public PreorderModelEnumeration(TreeModel model) {
            this(model, model.getRoot());
        }
        
        /**
         * Instantiates a preorder traversal of the TreeModel which
         * starts at the given node. It iterates over all nodes of the
         * subtree, only.
         * 
         * @param model the TreeModel to travers.
         * @param node the node to start
         */
        public PreorderModelEnumeration(TreeModel model, Object node) {
            this.model = model;
            stack = new ArrayDeque<Enumeration>();
            pushNodeAsEnumeration(node);
        }

        /**
         * Instantiates a preorder traversal of the TreeModel which starts at the
         * last path component of the given TreePath. It iterates over all nodes
         * of the subtree and all of its siblings, with the same end as a traversal
         * starting at the model's roolt would have.
         * 
         * @param model the TreeModel to travers.
         * @param path the TreePath to start from
         */
        public PreorderModelEnumeration(TreeModel model, TreePath path) {
            this(model, path.getLastPathComponent());
            this.path = path;
        }
        
        @Override
        public boolean hasMoreElements() {
            return (!stack.isEmpty() && stack.peek().hasMoreElements());
        }

        @Override
        public Object nextElement() {
            Enumeration enumer = stack.peek();
            Object  node = enumer.nextElement();
            Enumeration children = children(model, node);

            if (!enumer.hasMoreElements()) {
                stack.pop();
            }
            if (children.hasMoreElements()) {
                stack.push(children);
            }
            if (!hasMoreElements()) {
                // check if there are more subtrees to travers
                // and update internal state accordingly
                updateSubtree();
            }
            return node;
        }

        /**
         * 
         */
        private void updateSubtree() {
            if (path == null) return;
            TreePath parentPath = path.getParentPath();
            if (parentPath == null) {
                // root
                path = null;
                return;
            }
            Object parent = parentPath.getLastPathComponent();
            Object currentNode = path.getLastPathComponent();
            int currentIndex = model.getIndexOfChild(parent, currentNode);
            if (currentIndex +1 < model.getChildCount(parent)) {
                // use sibling
                Object child = model.getChild(parent, currentIndex + 1);
                path = parentPath.pathByAddingChild(child);
                pushNodeAsEnumeration(child);
            } else {
                path = parentPath;
                // up one level
                updateSubtree();
            }
        }

        private void pushNodeAsEnumeration(Object node) {
            // single element enum
            Vector v = new Vector(1);
            v.add(node);
            stack.push(v.elements()); //children(model));
        }
        

    }  // End of class PreorderEnumeration

    
    /**
     * Implementation of a breadthFirst traversal of a subtree in a TreeModel.
     */
    public static class BreadthFirstModelEnumeration implements Enumeration {
        protected Queue<Enumeration> queue;
        private TreeModel model;
        
        public BreadthFirstModelEnumeration(TreeModel model) {
            this(model, model.getRoot());
        }
        
        public BreadthFirstModelEnumeration(TreeModel model, Object node) {
            this.model = model;
            // Vector is just used for getting an Enumeration easily
            Vector v = new Vector(1);
            v.addElement(node);    
            queue = new ArrayDeque<Enumeration>();
            queue.offer(v.elements());
        }
        
        @Override
        public boolean hasMoreElements() {
            return !queue.isEmpty() &&
                    queue.peek().hasMoreElements();
        }
        
        @Override
        public Object nextElement() {
            // look at head
            Enumeration enumer = queue.peek();
            Object node = enumer.nextElement();
            Enumeration children = children(model, node);
            
            if (!enumer.hasMoreElements()) {
                // remove head
                queue.poll();
            }
            if (children.hasMoreElements()) {
                // add at tail
                queue.offer(children);
            }
            return node;
        }
        
    }  // End of class BreadthFirstEnumeration
    
    
    /**
     * Implementation of a postorder traversal of a subtree in a TreeModel.
     */
    public static class PostorderModelEnumeration implements Enumeration {
        protected TreeModel model;
        protected Object root;
        protected Enumeration children;
        protected Enumeration subtree;
        
        public PostorderModelEnumeration(TreeModel model) {
            this(model, model.getRoot());
        }
        
        public PostorderModelEnumeration(TreeModel model, Object node) {
            this.model = model;
            root = node;
            children = children(model, root);
            subtree = EMPTY_ENUMERATION;
        }
        
        @Override
        public boolean hasMoreElements() {
            return root != null;
        }
        
        @Override
        public Object nextElement() {
            Object retval;
            
            if (subtree.hasMoreElements()) {
                retval = subtree.nextElement();
            } else if (children.hasMoreElements()) {
                subtree = new PostorderModelEnumeration(model,
                        children.nextElement());
                retval = subtree.nextElement();
            } else {
                retval = root;
                root = null;
            }
            
            return retval;
        }
        
    }  // End of class PostorderEnumeration
    
    /**
     * Implementation of a preorder traversal of a subtree with nodes of type TreeNode.
     */
    public static class PreorderNodeEnumeration<M extends TreeNode> implements Enumeration<M> {
        protected Deque<Enumeration<M>> stack;

        public PreorderNodeEnumeration(M rootNode) {
            // Vector is just used for getting an Enumeration easily
            Vector<M> v = new Vector<M>(1);
            v.addElement(rootNode);     
            stack = new ArrayDeque<Enumeration<M>>();
            stack.push(v.elements());
        }

        @Override
        public boolean hasMoreElements() {
            return (!stack.isEmpty() &&
                    stack.peek().hasMoreElements());
        }

        @Override
        public M nextElement() {
            Enumeration<M> enumer = stack.peek();
            M node = enumer.nextElement();
            Enumeration<M> children = node.children();

            if (!enumer.hasMoreElements()) {
                stack.pop();
            }
            if (children.hasMoreElements()) {
                stack.push(children);
            }
            return node;
        }

    }  // End of class PreorderEnumeration

    /**
     * Implementation of a postorder traversal of a subtree with nodes of type TreeNode.
     */
    public static class PostorderNodeEnumeration<M extends TreeNode> implements Enumeration<M> {
        protected M root;
        protected Enumeration<M> children;
        protected Enumeration<M> subtree;

        public PostorderNodeEnumeration(M rootNode) {
            super();
            root = rootNode;
            children = root.children();
            subtree = EMPTY_ENUMERATION;
        }

        @Override
        public boolean hasMoreElements() {
            return root != null;
        }

        @Override
        public M nextElement() {
            M retval;

            if (subtree.hasMoreElements()) {
                retval = subtree.nextElement();
            } else if (children.hasMoreElements()) {
                subtree = new PostorderNodeEnumeration<M>(
                                children.nextElement());
                retval = subtree.nextElement();
            } else {
                retval = root;
                root = null;
            }

            return retval;
        }

    }  // End of class PostorderEnumeration


    /**
     * Implementation of a breadthFirst traversal of a subtree with nodes of type TreeNode.
     */
    public static class BreadthFirstNodeEnumeration<M extends TreeNode> implements Enumeration<M> {
        protected Queue<Enumeration<M>> queue;
        
        public BreadthFirstNodeEnumeration(M rootNode) {
            // Vector is just used for getting an Enumeration easily
            Vector<M> v = new Vector<M>(1);
            v.addElement(rootNode);    
            queue = new ArrayDeque<Enumeration<M>>();
            queue.offer(v.elements());
        }
        
        @Override
        public boolean hasMoreElements() {
            return !queue.isEmpty() &&
                    queue.peek().hasMoreElements();
        }
        
        @Override
        public M nextElement() {
            // look at head
            Enumeration<M> enumer = queue.peek();
            M node = enumer.nextElement();
            Enumeration<M> children = node.children();
            
            if (!enumer.hasMoreElements()) {
                // remove head
                queue.poll();
            }
            if (children.hasMoreElements()) {
                // add at tail
                queue.offer(children);
            }
            return node;
        }
        
        
    }  // End of class BreadthFirstEnumeration

    /**
     * Creates and returns an Enumeration across the direct children of the 
     * rootNode in the given TreeModel. 
     * 
     * @param model the TreeModel which contains parent, must not be null
     * @return an Enumeration across the direct children of the model's root, the enumeration
     *    is empty if the root is null or contains no children
     */
    public static Enumeration children(TreeModel model) {
        return children(model, model.getRoot());
    }
    
    /**
     * Creates and returns an Enumeration across the direct children of parentNode
     * in the given TreeModel. 
     * 
     * @param model the TreeModel which contains parent, must not be null
     * @param parent the parent of the enumerated children
     * @return an Enumeration across the direct children of parent, the enumeration
     *    is empty if the parent is null or contains no children
     */
    public static Enumeration children(final TreeModel model, final Object parent) {
        if (parent == null || model.isLeaf(parent)) {
            return EMPTY_ENUMERATION;
        }
        Enumeration<?> e = new Enumeration() {

            int currentIndex = 0;
            @Override
            public boolean hasMoreElements() {
                return model.getChildCount(parent) > currentIndex;
            }

            @Override
            public Object nextElement() {
                return model.getChild(parent, currentIndex++);
            }
            
        };
        return e;
    }
    
    private TreeUtilities() {}
    
    @SuppressWarnings("unused")
    private static final Logger LOG = Logger.getLogger(TreeUtilities.class
            .getName());
}