// Program to test solutions to problem #6 on the cse143 midterm, winter 2017.
// Fill in your solution to makeSortedSequence, then compile and run the
// program.

import java.util.*;

public class Test6 {
    public static void makeSortedSequence(Queue<Integer> q) {
        // fill in your solution here
        // you can also rename the parameter above
    }

    // this is the sample solution
    public static void makeSortedSequence2(Queue<Integer> q) {
        Stack<Integer> s = new Stack<Integer>();
        if (!q.isEmpty()) {
            int last = q.remove();
            s.push(last);
            int oldSize = q.size();
            for (int i = 0; i < oldSize; i++) {
                int next = q.remove();
                if (next < last) {
                    q.add(next);
                } else {
                    s.push(next);
                    last = next;
                }
            }
            while (!q.isEmpty()) {
                s.push(q.remove());
            }
            while (!s.isEmpty()) {
                q.add(s.pop());
            }
            while (!q.isEmpty()) {
                s.push(q.remove());
            }
            while (!s.isEmpty()) {
                q.add(s.pop());
            }
        }
    }

    private static int testCount;
    private static int failCount;

    public static void main(String[] args) {
        test(new LinkedList<Integer>());
        test(new int[] {3, 1, 2, 6, 5, 7, 9, 8, 12, 4, 3, 4, 12, 11, 14});
        test(new int[] {42});
        test(new int[] {2, 2, 8, 4, 4, 5, 2, 4, 8});
        test(new int[] {100, 1, 200, 2, 300, 3, 400, 4});
        test(new int[] {3, -8, 7, -4, -42, 0});
        test(new int[] {8, 5});
        test(new int[] {3, 8, 4});
        test(new int[] {7, 4, 3, 5});

        if (failCount == 0) {
            System.out.println("passed all tests");
        } else {
            System.out.println("failed " + failCount + " of " + testCount + 
                               " tests");
        }
    }

    public static void test(int[] data) {
        for (int i = 0; i < data.length; i++) {
            Queue<Integer> q = new LinkedList<Integer>();
            for (int j = i; j < i + data.length; j++) {
                q.add(data[j % data.length]);
            }
            test(q);
        }
    }

    public static void test(Queue<Integer> q) {
        Queue<Integer> q2 = new LinkedList<Integer>(q);
        System.out.println("original = " + q);
        makeSortedSequence2(q);
        System.out.println("result   = " + q);
        boolean fail = false;
        try {
            makeSortedSequence(q2);
        } catch (RuntimeException e) {
            int line = e.getStackTrace()[0].getLineNumber();
            System.out.println("    threw " + e + " at line #" + line);
            fail = true;
        }
        if (!fail && !q.equals(q2)) {
            System.out.println("yours    = " + q2);
            fail = true;
        }
        testCount++;
        if (fail) {
            System.out.println("failed");
            failCount++;
        } else {
            System.out.println("passed");
        }
        System.out.println();
    }
}