package treecms.tree.util;

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

/**
 * 順序付き深さ優先探索で木構造を走査します．また，走査したイテレータを返します．
 * @author shoshi
 */
public class PreorderTreewalker implements Iterable<Node>
{
	private Node m_root;
	
	/**
	 * コンストラクタです．
	 * @param _root 木構造のルートノード
	 */
	public PreorderTreewalker(Node _root)
	{
		m_root = _root;
	}
	
	
	/**
	 * イテレータを返します．
	 * @return 順序付き深さ優先探索でのイテレータ
	 */
	@Override
	public Iterator<Node> iterator()
	{
		return new IteratorImpl();
	}
	
	private class IteratorImpl implements Iterator<Node>
	{
		private Stack<Pair<Node,Iterator<Node>>> m_depth;
		private Node m_next;
		
		public IteratorImpl()
		{
			m_depth = new Stack<Pair<Node,Iterator<Node>>>();
			m_next = m_root;
			m_depth.add(new Pair<Node,Iterator<Node>>(m_next,m_next.children().iterator())); // ワケがわからないよ！
		}

		@Override
		public boolean hasNext()
		{
			return (m_next != null) ? true : false;
		}

		@Override
		public Node next()
		{
			Node next = m_next;
			
			//forward.
			Pair<Node,Iterator<Node>> context = m_depth.peek();
			Iterator<Node> itr = context.m_right;
			if(itr.hasNext()){
				m_next = itr.next();
				m_depth.add(new Pair<Node,Iterator<Node>>(m_next,m_next.children().iterator())); // ワケがわからないよ！
			}else{
				m_depth.pop();
				while(!m_depth.isEmpty()){
					Pair<Node,Iterator<Node>> back = m_depth.peek();
					if(back.m_right.hasNext()){
						m_next = back.m_right.next();
						break;
					}
					m_depth.pop();
				}
				m_next = null;
			}
			
			return next;
		}

		@Override
		public void remove()
		{
			//not supported.
		}
	}
	
	private class Pair<L,R>
	{
		@SuppressWarnings("unused")
		public L m_left;
		public R m_right;
		
		public Pair(L _left,R _right)
		{
			m_left = _left;
			m_right = _right;
		}
	}
}