001    package net.sf.tacos.components.tree;
002    
003    import java.util.ArrayList;
004    import java.util.Collection;
005    import java.util.Collections;
006    import java.util.Iterator;
007    import java.util.List;
008    import java.util.Stack;
009    
010    /**
011     * @author phraktle
012     */
013    public abstract class TreeIterator implements Iterator {
014    
015        private final Stack todo = new Stack();
016        private int depth = 0;
017        private int previousDepth = 0;
018        private int markers = 0;
019    
020        /**
021         * New tree
022         * @param rootElement
023         */
024        public TreeIterator(Object rootElement)
025        {
026            todo.push(rootElement);
027        }
028    
029        /**
030         * Tree iterator
031         * @param rootElements
032         */
033        public TreeIterator(Collection rootElements)
034        {
035            push(rootElements);
036        }
037    
038        /**
039         * Depth
040         * @return
041         */
042        public int getDepth()
043        {
044            return depth;
045        }
046    
047        /**
048         * Previous depth
049         * @return
050         */
051        public int getPreviousDepth()
052        {
053            return previousDepth;
054        }
055    
056        /**
057         * 
058         * {@inheritDoc}
059         */
060        public boolean hasNext()
061        {
062            return !todo.isEmpty() && todo.size() != markers;
063        }
064    
065        /**
066         * 
067         * {@inheritDoc}
068         */
069        public Object next()
070        {
071            Object node;
072            do {
073                node = todo.pop();
074                if (node == MARKER) {
075                    markers--;
076                }
077            } while(node == MARKER);
078            previousDepth = depth;
079            depth = markers;
080            Collection children = getChildren(node);
081            if (!children.isEmpty()) {
082                todo.push(MARKER);
083                markers++;
084                push(children);
085            }
086            return node;
087        }
088    
089        /**
090         * Push set of elements
091         * @param elements
092         */
093        private void push(Collection elements)
094        {
095            List rev = new ArrayList(elements);
096            Collections.reverse(rev);
097            todo.addAll(rev);
098        }
099    
100        /**
101         * Gets children
102         * @param node
103         * @return
104         */
105        protected abstract Collection getChildren(Object node);
106    
107        /**
108         * 
109         * {@inheritDoc}
110         */
111        public void remove()
112        {
113            throw new UnsupportedOperationException();
114        }
115    
116        private final static Object MARKER = new Object();
117    
118    }