package treecms.proto.test;
import java.util.Iterator;
import java.util.LinkedList;

import treecms.proto.api.NodeAPI;
import treecms.proto.simple.SimpleNodeAPI;

public class PreOrderTreeWalkerRecursive1 implements Iterable<NodeAPI>
{
	private NodeAPI m_root;
	
	public PreOrderTreeWalkerRecursive1(NodeAPI _root)
	{
		m_root = _root;
	}

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

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

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

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

	private boolean findPath(NodeAPI root, NodeAPI node, LinkedList<NodeAPI> list) {
		if (root==node) return true;
		for(NodeAPI child : node.getChildList()){
			if (findPath(child,node,list)) {
				list.addFirst(child);
				return true;
			}
		}
		return false; // backtrack
	}
	
	public NodeAPI cloneTree(LinkedList<NodeAPI> path) {
			NodeAPI old = path.poll();
			NodeAPI node = new SimpleNodeAPI(old.getTitle());
			node.setClassName(old.getClassName());
			for(NodeAPI child: old.getChildList()) {
				if (child==old && !path.isEmpty()) child = cloneTree(path);
				node.getChildList().add(child);
			}
			return node;
		}

}