package treecms.tree.util;

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

/**
 * あるNodeから対象となるNodeまでのパスのイテレータです．
 * @author shoshi
 */
public class NodePathFinder implements Iterable<Node>
{
	private Node m_root;
	private Node m_target;
	private List<Node> m_path;
	
	/**
	 * コンストラクタです．コンストラクタが作成された時点でパスが検索されます．
	 * @param _root 木構造のトップです．
	 * @param _target パス検索の対象となるNodeです．
	 */
	public NodePathFinder(Node _root,Node _target) throws PathNotFoundException
	{
		m_root = _root;
		m_target = _target;
		List<Node> path = findPath(m_root,m_target);
		m_path = Collections.unmodifiableList(path);
	}

	/**
	 * パスまでのイテレータを返します．
	 * イテレータはremoveメソッドをサポートしません．
	 */
	@Override
	public Iterator<Node> iterator()
	{
		return m_path.iterator();
	}
	
	/**
	 * パスのリストを取得します．このパスのリストは編集できません．
	 * @return パスまでのリスト
	 */
	public List<Node> list()
	{
		return m_path;
	}

	/**
	 * _fromから_targetまでのパスを再帰的に取得します
	 * @param _from 取得するパスの始まり
	 * @param _target 取得するパスの終わり
	 * @return _fromから_targetまでのリスト
	 */
	private LinkedList<Node> findPath(Node _from,Node _target)
	{
		if(_from.getID().isFamily(_target.getID())){
			LinkedList<Node> path = new LinkedList<Node>();
			path.addFirst(_from);
			return path;
		}
		
		for(Node child : _from.children()){
			LinkedList<Node> path = findPath(child,_target);
			if(path != null){
				path.addFirst(_from);
			}
		}
		
		return null;
	}
}