package treecms.proto.test;

import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

import treecms.proto.api.NodeAPI;

public class PreOrderTreeWalker implements Iterable<NodeAPI>
{
	private NodeAPI m_root;
	
	public PreOrderTreeWalker(NodeAPI _root)
	{
		m_root = _root;
	}
	
	class NodeState {
		NodeAPI node;
		int position;
		NodeState(NodeAPI n,int p) { node = n; position = p; }
	}
	class IteratorState implements Iterator<NodeAPI> {
		LinkedList<NodeState>nodeStack;
		List<NodeAPI> children;
		int position;
		NodeAPI next;
		
		IteratorState(NodeAPI root) {
			children = root.getChildList();
			nodeStack = new LinkedList<NodeState>();
			nodeStack.addLast(new NodeState(root,0));
			position = 0;
		}

		public boolean hasNext() {
			while (position>=children.size()) {
				if (nodeStack.isEmpty()) return false;
				children = nodeStack.getLast().node.getChildList();
				position = nodeStack.getLast().position;
				nodeStack.removeLast();
			}
			next = children.get(position++);
			if (! next.getChildList().isEmpty()) {
				nodeStack.addLast(new NodeState(next,position));
				children = next.getChildList();
				position = 0;
			}
			return true;
		}
		public NodeAPI next() {
			return next;
		}
		public void remove() {
		}
	}
	
	@Override
	public Iterator<NodeAPI> iterator() {
			return new IteratorState(m_root);
	}

	
}