/*
 * @(#)SegmentTreePreorderIterator.java  1.0  2010-12-25
 *
 * Copyright (c) 2000-2010 Werner Randelshofer, Immensee, Switzerland.
 * All rights reserved.
 *
 * You may not use, copy or modify this file, except in compliance with the
 * license agreement you entered into with Werner Randelshofer.
 * For details see accompanying license terms.
 */
package ch.randelshofer.segmenttree;

import java.util.Stack;

/**
 * Implementation of segment tree preorder iterator.
 */
public class SegmentTreePreorderIterator implements SegmentTreeIterator {

    Stack<SegmentNode> s = null;

    /**
     * Creates the iterator
     * @param t - segment tree on which to iterate
     * @return iterator
     */
    static public SegmentTreePreorderIterator IteratorInitialize(SegmentTree t) {
        if (t.getRoot() == null) {
            System.err.println("Tree not initialized");
            return null;
        }
        return new SegmentTreePreorderIterator(t.getRoot());
    }

    /**
     * Creates iterator which will start from specific node
     * @param n start node
     * @return iterator
     */
    static public SegmentTreePreorderIterator IteratorInitialize(SegmentNode n) {
        if (n == null) {
            System.err.println("Tree not initialized");
            return null;

        }
        return new SegmentTreePreorderIterator(n);
    }

    /**
     * Create new iterator from start node
     * @param start start node
     */
    SegmentTreePreorderIterator(SegmentNode start) {
        this.s = new Stack<SegmentNode>();
        s.push(start);

    }

    /**
     * Next tree node pointed by iterator
     * @return next tree node
     */
    public SegmentNode next() {
        if (s.empty()) {
            return null;
        }

        SegmentNode res = s.pop();
        if (res.rightSon() != null) {
            s.push(res.rightSon());

        }
        if (res.leftSon() != null) {
            s.push(res.leftSon());
        }

        return res;
    }

    /**
     * Returns true if unvisited node exists
     */
    public boolean hasNext() {
        return !s.isEmpty();
    }
}
