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>();
	
	/*
	 * get queryIndexCondition from query 
	 * if already index exists, use index 
	 * otherwise traverse tree and create index  
	 *
	 * */
	public PathNodeIterator(Pair<TreeNode,NodePath> pair) {
		this.root = pair.left();
		path = pair.right();
		node = root;
	}

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

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

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

	}

}