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.impl.TreeNode;
import jp.ac.u_ryukyu.ie.cr.shoshi.jungle.store.impl.TreeNodeChildren;

public class PathNodeIterator implements Iterator<TreeNode> {

	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(TreeNode root) {
		this.root = root;
		this.node = root;
	}

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

	@Override
	public TreeNode next() {
		TreeNode now = node;
		if (node.getChildren().size() > 0) { 
			nodeStack.push(node);
			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 now;
		}else if (children != null && children.size() > childNumber) {
			childNumber = searchStack.pop();
			node = children.at(childNumber).b();
			searchStack.push(++childNumber);
		} else {
			node = nodeStack.pop();
			children = node.getChildren();
			childNumber = searchStack.pop();
			for (; children.size() == childNumber;) {
				if (node == root) {
					node = null; // no more node
					children = null;
					return now;
				}
				node = nodeStack.pop();
				children = node.getChildren();
				childNumber = searchStack.pop();
			}
			if (node != null && childNumber < children.size()) {
				nodeStack.push(node);
				node = children.at(childNumber).b();
				searchStack.push(++childNumber);
			}
		}
		return now;
	}

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

	}

}