package algs21;
import stdlib.*;
// Exercise 2.1.14
/**
 * Complete the following method to sort a deck of cards,
 * with the restriction that the only allowed operations are to look
 * at the values of the top two cards, to exchange the top two cards,
 * and to move the top card to the bottom of the deck.
 */
public class MyDeckSort {
  public static void sort (MyDeck d) {
    // TODO
    // You must sort the Deck using only the public methods of Deck.
    // You may not change the Deck class.
    // It should be sufficient to use the following:
    //   d.size ();
    //   d.moveTopToBottom (); 
    //   d.topGreaterThanNext ();
    //   d.swapTopTwo ();
    // While debugging, you will want to print intermediate results.
    // You can use d.toString() for that:
    //   StdOut.format ("i=%-3d %s\n", i, d.toString ());
  }

  private static double time;
  private static void countops (MyDeck d) {
    boolean print = false;
    if (print) StdOut.println (d.toString ());
    Stopwatch sw = new Stopwatch ();
    sort (d);
    time = sw.elapsedTime ();
    if (print) StdOut.println (d.toString ());
    d.isSorted ();
  }
  public static void main (String[] args) {
    int N = 10;
    MyDeck d = new MyDeck (N);
    countops (d);
    //System.exit (0); // Comment this out to do a doubling test!
    double prevOps = d.ops ();
    double prevTime = time;
    for (int i = 0; i < 11; i++) {
      N *= 2;
      d = new MyDeck (N);
      countops (d);
      StdOut.format ("Elapsed count f(%,13d): %,17d: %10.3f [%10.3f : %10.3f]\n", N, d.ops(), d.ops() / prevOps, time, time/prevTime);
      prevOps = d.ops ();
      prevTime = time;
    }
  }
}

/**
 * The Deck class has the following API:
 *
 * <pre>
 * MyDeck (int N)                 // create a randomized Deck of size N
 * int size ()                    // return the size of N
 * int ops ()                     // return the number of operations performed on this Deck
 * boolean topGreaterThanNext ()  // compare top two items
 * void swapTopTwo ()             // swap top two itens
 * void moveTopToBottom ()        // move top item to bottom
 * void isSorted ()               // check if isSorted (throws exception if not)
 * </pre>
 */
class MyDeck {
  private int N;
  private int top;
  private long ops;
  private int[] a;

  public long ops () {
    return ops;
  }
  public int size () {
    return N;
  }
  public MyDeck (int N) {
    this.N = N;
    this.top = 0;
    this.ops = 0;
    this.a = new int[N];
    for (int i = 0; i < N; i++)
      a[i] = i;
    StdRandom.shuffle (a);
  }
  public boolean topGreaterThanNext () {
    int i = a[top];
    int j = a[(top + 1) % N];
    ops += 2;
    return i > j;
  }
  public void swapTopTwo () {
    int i = a[top];
    int j = a[(top + 1) % N];
    a[top] = j;
    a[(top + 1) % N] = i;
    ops += 4;
  }
  public void moveTopToBottom () {
    top = (top + 1) % N;
    ops += 1;
  }
  public String toString() {
    return toStringUnshifted() + toStringShifted();
  }
  public String toStringUnshifted () {
    if (N==0) return "[]";
    StringBuilder b = new StringBuilder ();
    b.append ('[');
    int last = (top + N - 1) % N;
    for (int k = top; ; k = (k + 1) % N) {
      b.append (a[k]);
      if (k == last) return b.append (']').toString();
      b.append (' ');
    } 
  }
  public String toStringShifted () {
    if (N==0) return "()";
    StringBuilder b = new StringBuilder ();
    b.append ('(');
    int last = N-1;
    for (int k = 0; ; k = k + 1) {
      b.append((top==k) ? '^' : ' ');
      b.append (a[k]);
      if (k == last) return b.append (')').toString();
      b.append (' ');
    } 
  }
  public void isSorted () {
    boolean print = false;
    long theOps = ops; // don't count the operations require by isSorted
    for (int i = 1; i < N; i++) {
      if (print) StdOut.format ("i=%-3d %s\n", i, toString ());
      if (topGreaterThanNext ()) throw new Error ();
      moveTopToBottom ();
    }
    if (print) StdOut.format ("i=%-3d %s\n", N, toString ());
    moveTopToBottom ();
    if (print) StdOut.format ("i=%-3d %s\n", N + 1, toString ());
    ops = theOps;
  }
}