001package algs21;
002import stdlib.*;
003// Exercise 2.1.14
004/**
005 * Complete the following method to sort a deck of cards,
006 * with the restriction that the only allowed operations are to look
007 * at the values of the top two cards, to exchange the top two cards,
008 * and to move the top card to the bottom of the deck.
009 */
010public class MyDeckSort {
011        public static void sort (MyDeck d) {
012                // TODO
013                // You must sort the Deck using only the public methods of Deck.
014                // You may not change the Deck class.
015                // It should be sufficient to use the following:
016                //   d.size ();
017                //   d.moveTopToBottom (); 
018                //   d.topGreaterThanNext ();
019                //   d.swapTopTwo ();
020                // While debugging, you will want to print intermediate results.
021                // You can use d.toString() for that:
022                //   StdOut.format ("i=%-3d %s\n", i, d.toString ());
023        }
024
025        private static double time;
026        private static void countops (MyDeck d) {
027                boolean print = false;
028                if (print) StdOut.println (d.toString ());
029                Stopwatch sw = new Stopwatch ();
030                sort (d);
031                time = sw.elapsedTime ();
032                if (print) StdOut.println (d.toString ());
033                d.isSorted ();
034        }
035        public static void main (String[] args) {
036                int N = 10;
037                MyDeck d = new MyDeck (N);
038                countops (d);
039                //System.exit (0); // Comment this out to do a doubling test!
040                double prevOps = d.ops ();
041                double prevTime = time;
042                for (int i = 0; i < 11; i++) {
043                        N *= 2;
044                        d = new MyDeck (N);
045                        countops (d);
046                        StdOut.format ("Elapsed count f(%,13d): %,17d: %10.3f [%10.3f : %10.3f]\n", N, d.ops(), d.ops() / prevOps, time, time/prevTime);
047                        prevOps = d.ops ();
048                        prevTime = time;
049                }
050        }
051}
052
053/**
054 * The Deck class has the following API:
055 *
056 * <pre>
057 * MyDeck (int N)                 // create a randomized Deck of size N
058 * int size ()                    // return the size of N
059 * int ops ()                     // return the number of operations performed on this Deck
060 * boolean topGreaterThanNext ()  // compare top two items
061 * void swapTopTwo ()             // swap top two itens
062 * void moveTopToBottom ()        // move top item to bottom
063 * void isSorted ()               // check if isSorted (throws exception if not)
064 * </pre>
065 */
066class MyDeck {
067        private int N;
068        private int top;
069        private long ops;
070        private int[] a;
071
072        public long ops () {
073                return ops;
074        }
075        public int size () {
076                return N;
077        }
078        public MyDeck (int N) {
079                this.N = N;
080                this.top = 0;
081                this.ops = 0;
082                this.a = new int[N];
083                for (int i = 0; i < N; i++)
084                        a[i] = i;
085                StdRandom.shuffle (a);
086        }
087        public boolean topGreaterThanNext () {
088                int i = a[top];
089                int j = a[(top + 1) % N];
090                ops += 2;
091                return i > j;
092        }
093        public void swapTopTwo () {
094                int i = a[top];
095                int j = a[(top + 1) % N];
096                a[top] = j;
097                a[(top + 1) % N] = i;
098                ops += 4;
099        }
100        public void moveTopToBottom () {
101                top = (top + 1) % N;
102                ops += 1;
103        }
104        public String toString() {
105                return toStringUnshifted() + toStringShifted();
106        }
107        public String toStringUnshifted () {
108                if (N==0) return "[]";
109                StringBuilder b = new StringBuilder ();
110                b.append ('[');
111                int last = (top + N - 1) % N;
112                for (int k = top; ; k = (k + 1) % N) {
113                        b.append (a[k]);
114                        if (k == last) return b.append (']').toString();
115                        b.append (' ');
116                } 
117        }
118        public String toStringShifted () {
119                if (N==0) return "()";
120                StringBuilder b = new StringBuilder ();
121                b.append ('(');
122                int last = N-1;
123                for (int k = 0; ; k = k + 1) {
124                        b.append((top==k) ? '^' : ' ');
125                        b.append (a[k]);
126                        if (k == last) return b.append (')').toString();
127                        b.append (' ');
128                } 
129        }
130        public void isSorted () {
131                boolean print = false;
132                long theOps = ops; // don't count the operations require by isSorted
133                for (int i = 1; i < N; i++) {
134                        if (print) StdOut.format ("i=%-3d %s\n", i, toString ());
135                        if (topGreaterThanNext ()) throw new Error ();
136                        moveTopToBottom ();
137                }
138                if (print) StdOut.format ("i=%-3d %s\n", N, toString ());
139                moveTopToBottom ();
140                if (print) StdOut.format ("i=%-3d %s\n", N + 1, toString ());
141                ops = theOps;
142        }
143}