// THIS CODE IS MY OWN WORK, IT WAS WRITTEN WITHOUT CONSULTING
// A TUTOR OR CODE WRITTEN BY OTHER STUDENTS - Your Name

// PRedBlackBST: a persistent left-leaning red-black tree.  You only
// do insertion (the "put" method).  Our parent class PBST has defined
// the Node class (with a 'color' field and setColor method), the
// isRed(x) method, and check() which checks red-black structure.

public class PRedBlackBST<Key extends Comparable<Key>, Value>
    extends PBST<Key, Value>
{
    // Two constructors: just call the PBST constructors.
    public PRedBlackBST() { super(); }
    PRedBlackBST(Node r, PBST p) { super(r, p); }

    // Color constants:
    static final boolean RED   = true;
    static final boolean BLACK = false;

    // The setRoot(Node r) method.  Its declared return type is still
    // PBST, but the actual type returned is PRedBlackBST.
    PBST setRoot(Node r) {
        return r==root ? this : new PRedBlackBST(r, this);
    }

    // TODO: PBST put(Key key, Value val) { ... }
    // Like setRoot, the actual type returned is PRedBlackBST.

    // TODO: Node put(Node h, Key key, Value val) { ... }

    // TODO: Node rotateRight(Node h) { ... }

    // TODO: Node rotateLeft(Node h)  { ... }

    // TODO: Node flipColors(Node h)  { ... }

    // EXTRA CREDIT: replace IntIterator with StackIterator.
    //
    // Just like IntIterator, a StackIterator lets us visits the keys
    // in order.  It uses a stack of O(H) nodes [where H=height] to
    // keep track of the parts of the tree that we have yet to visit.
    // It needs O(N) time to visit all N nodes.  Idea: for each node x
    // on the stack, we still need to visit x, to be followed by the
    // x.right subtree.
    /*
    public java.util.Iterator<Key> iterator() { return new StackIterator(); }
    class StackIterator implements java.util.Iterator<Key> {
        java.util.Stack<Node> todo = new java.util.Stack<Node>();
        StackIterator() { ... } // push what on todo?
        // methods next, hasnext, remove
    }
    */
    // NOTE: if you do the extra credit, please send an email letting
    // me know (to mic@mathcs.emory.edu).

}