package jp.ac.u_ryukyu.ie.cr.tatsuki.jungle.query;

import java.util.Iterator;
import java.util.Stack;

import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.NodePath;
import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.DefaultNodePath;
import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNode;
import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNodeChildren;
import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.util.Pair;

public class PathNodeIterator implements Iterator<Pair<TreeNode, NodePath>> {

	NodePath path;
	TreeNode root;
	TreeNode node;
	int childNumber;
	private TreeNodeChildren children;
	private Stack<TreeNode> nodeStack = new Stack<TreeNode>();
	private Stack<Integer> searchStack = new Stack<Integer>();

	public PathNodeIterator(TreeNode root) {
		this.root = root;
		path = new DefaultNodePath();
		node = root;

	}

	@Override
	public boolean hasNext() {
		return node != null;
	}

	@Override
	public Pair<TreeNode, NodePath> next() {
		TreeNode now = node;
		NodePath currentPath = path;
		if (node.getChildren().size() > 0) {
			nodeStack.push(node);
			path = path.add(0);
			children = node.getChildren();
			node = children.at(0).b();
			childNumber = 1;
			searchStack.push(childNumber);
		} else if (children != null && children.size() > childNumber) {
			childNumber = searchStack.pop();
			node = children.at(childNumber).b();
			path = path.tail().add(childNumber);
			searchStack.push(++childNumber);
		} else {
			path = path.tail();
			node = nodeStack.pop();
			children = node.getChildren();
			childNumber = searchStack.pop();
			for (; children.size() == childNumber;) {
				path = path.tail();
				node = nodeStack.pop();
				children = node.getChildren();
				childNumber = searchStack.pop();
				if (node == root) {
					node = null; // no more node
					children = null;
					return new Pair<TreeNode, NodePath>(now, currentPath);
				}
			}
			if (node != null && childNumber < children.size()) {
				path = path.add(childNumber);
				nodeStack.push(node);
				node = children.at(childNumber).b();
				searchStack.push(++childNumber);
			}
		}
		System.out.println(path.toString());
		return new Pair<TreeNode, NodePath>(now, currentPath);
	}

	@Override
	public void remove() {
		// TODO Auto-generated method stub

	}

}