///////////////////////////////////////////
///
/// File: RBTreeIterable.java
/// Author: Evan Gaul
/// Email: eagaul@wisc.edu
/// Date: 10/14/2025
/// Assignment: P106.Iterator
/// Course: CS400 Lec004 Fall 2025
/// Professor: Ashley Samuelson
///
///////////////////////////////////////////
///
/// Assistance: None
///
///////////////////////////////////////////

import java.util.Iterator;
import java.util.Stack;
import java.util.NoSuchElementException;
import static org.junit.jupiter.api.Assertions.*;

import org.junit.jupiter.api.Nested;
import org.junit.jupiter.api.Test;

/**
 * This class extends RedBlackTree into a tree that supports iterating over the values it
 * stores in sorted, ascending order.
 */
public class RBTreeIterable<T extends Comparable<T>>
        extends RedBlackTree<T> implements IterableSortedCollection<T> {

    private Comparable<T> iteratorMin = null;
    private Comparable<T> iteratorMax = null;
    /**
     * Allows setting the start (minimum) value of the iterator. When this method is called,
     * every iterator created after it will use the minimum set by this method until this method
     * is called again to set a new minimum value.
     *
     * @param min the minimum for iterators created for this tree, or null for no minimum
     */
    public void setIteratorMin(Comparable<T> min) {
        iteratorMin = min;
    }

    /**
     * Allows setting the stop (maximum) value of the iterator. When this method is called,
     * every iterator created after it will use the maximum set by this method until this method
     * is called again to set a new maximum value.
     *
     * @param max the maximum for iterators created for this tree, or null for no maximum
     */
    public void setIteratorMax(Comparable<T> max) {
        iteratorMax = max;
    }

    /**
     * Returns an iterator over the values stored in this tree. The iterator uses the
     * start (minimum) value set by a previous call to setIteratorMin, and the stop (maximum)
     * value set by a previous call to setIteratorMax. If setIteratorMin has not been called
     * before, or if it was called with a null argument, the iterator uses no minimum value
     * and starts with the lowest value that exists in the tree. If setIteratorMax has not been
     * called before, or if it was called with a null argument, the iterator uses no maximum
     * value and finishes with the highest value that exists in the tree.
     */
    public Iterator<T> iterator() {
        return new TreeIterator<>(this.root, iteratorMin, iteratorMax);
    }

    /**
     * Nested class for Iterator objects created for this tree and returned by the iterator method.
     * This iterator follows an in-order traversal of the tree and returns the values in sorted,
     * ascending order.
     */
    protected static class TreeIterator<R extends Comparable<R>> implements Iterator<R> {

        // stores the start point (minimum) for the iterator
        Comparable<R> min = null;
        // stores the stop point (maximum) for the iterator
        Comparable<R> max = null;
        // stores the stack that keeps track of the inorder traversal
        Stack<BinaryNode<R>> stack = null;

        /**
         * Constructor for a new iterator if the tree with root as its root node, and
         * min as the start (minimum) value (or null if no start value) and max as the
         * stop (maximum) value (or null if no stop value) of the new iterator.<br/>
         * Time complexity should be <b>O(log n)</b>
         *
         * @param root root node of the tree to traverse
         * @param min  the minimum value that the iterator will return
         * @param max  the maximum value that the iterator will return
         */
        public TreeIterator(BinaryNode<R> root, Comparable<R> min, Comparable<R> max) {
            this.min = min;
            this.max = max;
            this.stack = new Stack<>();
            updateStack(root);
        }

        /**
         * Helper method for initializing and updating the stack. This method both<br/>
         * - finds the next data value stored in the tree (or subtree) that is between
         * start(minimum) and stop(maximum) point (including start and stop points
         * themselves), and<br/>
         * - builds up the stack of ancestor nodes that contain values between
         * start(minimum) and stop(maximum) values (including start and stop values
         * themselves) so that those nodes can be visited in the future.
         *
         * @param node the root node of the subtree to process
         */
        private void updateStack(BinaryNode<R> node) {
            if (node == null) return; // base case

            // If node value < min, skip left subtree, go right
            if (min != null && node.data.compareTo((R) min) < 0) {
                updateStack(node.right);
            }
            // Otherwise, node.data >= min
            else {
                // Push current node, then go left to find smaller vals
                stack.push(node);
                updateStack(node.left);
            }
        }

        /**
         * Returns true if the iterator has another value to return, and false otherwise.
         */
        public boolean hasNext() {
            // Clean up stack top if past max
            while (!stack.isEmpty()) {
                BinaryNode<R> top = stack.peek();
                if (max != null && top.data.compareTo((R) max) > 0) {
                    stack.pop(); // discard values bigger than max
                    // keep checking lower nodes
                    if (top.right != null) updateStack(top.right);
                } else {
                    return true;
                }
            }
            return false;
        }

        /**
         * Returns the next value of the iterator.<br/>
         * Amortized time complexity should be <b>O(1)</b><br/>
         * Worst case time complexity <b>O(log n)</b><br/>
         * <p><b>Do not</b> implement this method by linearly walking through the
         * entire tree from the smallest element until the start bound is reached.
         * That process should occur <b>only once</b> during construction of the
         * iterator object.</p>
         *
         * @throws NoSuchElementException if the iterator has no more values to return
         */
        public R next() {
            if (!hasNext()) {
                throw new NoSuchElementException("No more elements within range.");
            }

            // Pop next node
            BinaryNode<R> current = stack.pop();
            R result = current.data;

            // If right child exists, process its left path
            if (current.right != null) {
                updateStack(current.right);
            }

            return result;
        }
    }

    @Nested
    class RBTreeIterableTests {

        /**
         * Tests integer iteration with no bounds
         * Also checks that all inserted integers appear in ascending order.
         */
        @Test
        public void testOne() {
            // create tree and insert ints
            RBTreeIterable<Integer> tree = new RBTreeIterable<>();
            tree.insert(10);
            tree.insert(5);
            tree.insert(15);
            tree.insert(2);
            tree.insert(7);

            // make iterator without min or max
            Iterator<Integer> it = tree.iterator();

            // get values in order
            int[] expected = {2, 5, 7, 10, 15};
            int i = 0;
            while (it.hasNext()) {
                assertEquals(expected[i++], it.next());
            }
            assertEquals(expected.length, i);
        }

        /**
         * Tests iteration with duplicates and a start min bound only.
         * Duplicates within range shouldnt be skipped.
         */
        @Test
        public void testTwo() {
            RBTreeIterable<Integer> tree = new RBTreeIterable<>();
            // insert values with duplicates
            int[] values = {5, 5, 3, 7, 9, 1, 9};
            for (int v : values) tree.insert(v);

            // set lower bound to 5
            tree.setIteratorMin(5);

            Iterator<Integer> it = tree.iterator();

            // expected values: 5, 5, 7, 9, 9
            int[] expected = {5, 5, 7, 9, 9};
            int i = 0;
            while (it.hasNext()) {
                assertEquals(expected[i++], it.next());
            }
            assertEquals(expected.length, i);
        }

        /**
         * Tests string iteration with min and max bounds.
         * Only values between “banana” and  “pear” should appear.
         */
        @Test
        public void testThree() {
            RBTreeIterable<String> tree = new RBTreeIterable<>();
            String[] fruits = {"apple", "banana", "cherry", "kiwi", "pear", "plum"};
            for (String f : fruits) tree.insert(f);

            // set bounds, min is "banana", max is "pear"
            tree.setIteratorMin("banana");
            tree.setIteratorMax("pear");

            Iterator<String> it = tree.iterator();

            String[] expected = {"banana", "cherry", "kiwi", "pear"};
            int i = 0;
            while (it.hasNext()) {
                assertEquals(expected[i++], it.next());
            }
            assertEquals(expected.length, i);
        }
}
}