package algs33;
import stdlib.*;
/* ***********************************************************************
 *  Compilation:  javac RandomizedQueue.java
 *  Execution:    java RandomizedQueue
 *
 *  Implement a randomized queue in log N time per operation in the
 *  worst case.
 *
 *************************************************************************/

public class XRandomizedQueue<T> {

  private RedBlackBST<Integer, T> st = new RedBlackBST<>();

  public XRandomizedQueue() { }

  // add the item to the randomized queue
  public void enqueue(T item) {
    int N = st.size();
    int r = StdRandom.uniform(N+1);
    // r is between 0 and N, inclusive
    // initially N == r == 0
    //   st.get returns null if item not there
    //   so, initially, the next line does nothing
    st.put(N, st.get(r));
    st.put(r, item);
    // StdOut.format ("N=%d r=%d\n", N, r);
  }

  // delete and return a random item from the queue
  public T dequeue() {
    int N = st.size();
    if (N == 0) throw new Error("Randomized queue underflow");
    T item = st.get(N-1);
    st.delete(N-1);
    return item;
  }


  /* ***********************************************************************
   *  Test client
   *************************************************************************/
  public static void main(String[] args) {
    args = new String[] { "10000", "20" };
    int N = Integer.parseInt(args[0]);
    int k = Integer.parseInt(args[1]);
    XRandomizedQueue<Integer> queue = new XRandomizedQueue<>();
    for (int i = 0; i < N; i++)
      queue.enqueue(i);

    for (int i = 0; i < k; i++)
      StdOut.println(queue.dequeue());
  }
}