package treecms.util;

import java.util.Iterator;
import java.util.LinkedList;
import treecms.api.Node;

public class PreOrderTreeWalker implements Iterable<Node>
{
	private Node m_root;
	
	public PreOrderTreeWalker(Node _root)
	{
		m_root = _root;
	}

	@Override
	public Iterator<Node> iterator()
	{
		return new PreOrderRecursiveIterator(m_root);
	}

	class PreOrderRecursiveIterator implements Iterator<Node>
	{
		private LinkedList<Node> nextList;
		
		public PreOrderRecursiveIterator(Node _root)
		{
			nextList = new LinkedList<Node>();
			getChildren(_root, nextList);
		}
		
		void getChildren(Node node, LinkedList<Node>list) {
			list.add(node);
			for(Node child : node.getChildren()){
				getChildren(child,list);
			}
		}
		
		@Override
		public boolean hasNext()
		{
			return !nextList.isEmpty();
		}

		@Override
		public Node next()
		{
			return nextList.poll();
		}

		@Override
		public void remove()
		{
			throw new UnsupportedOperationException("cant remove from itrerator");
		}
	}
	
	public LinkedList<Node> findPath(Node root, Node node) {
		LinkedList<Node> list = new LinkedList<Node>();
		list.addFirst(root);
		findPath(root,node,list);
		return list;
	}

	private boolean findPath(Node root, Node node, LinkedList<Node> list) {
		if (root==node) return true;
		for(Node child : node.getChildren()){
			if (findPath(child,node,list)) {
				list.addFirst(child);
				return true;
			}
		}
		return false; // backtrack
	}
}