// Program to test solutions to problem #5 on the cse14 midterm, winter 2014.
// Fill in your solution to rearrangeDuplicates, then compile and run the program.

import java.util.*;

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

    // this is the sample solution
    public static void rearrangeDuplicates2(Queue<Integer> q) {
        Stack<Integer> s = new Stack<Integer>();
        if (q.size() > 1) {
            int oldSize = q.size();
            int prev = q.remove();
            q.add(prev);
            for (int i = 0; i < oldSize - 1; i++) {
                int n = q.remove();
                if (n != prev)
                    q.add(n);
                else
                    s.push(n);
                prev = n;
            }
            int newCount = q.size();
            while (!s.isEmpty())
                q.add(s.pop());
            for (int i = 0; i < newCount; i++)
                q.add(q.remove());
            for (int i = 0; i < oldSize - newCount; i++)
                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) {
        int[] data = {-13, -13, -13, 5, 5, 13, 20, 20, 20, 20, 20, 20, 50, 50};

        for (int i = 0; i < data.length; i++) {
            Queue<Integer> q = new LinkedList<Integer>();
            for (int j = 0; j <= i; j++) {
                q.add(data[j]);
            }
            test(q);
        }
        Queue<Integer> q = new LinkedList<Integer>();
        test(q);
        for (int i = 0; i < 10; i++) {
            q.add(i * 100 + 15);
            test(q);
        }
        if (failCount == 0) {
            System.out.println("passed all tests");
        } else {
            System.out.println("failed " + failCount + " of " + testCount + 
                               " tests");
        }
    }

    public static void test(Queue<Integer> q) {
        Queue<Integer> q2 = new LinkedList<Integer>(q);
        System.out.println("original = " + q);
        rearrangeDuplicates2(q);
        System.out.println("result   = " + q);
        boolean fail = false;
        try {
            rearrangeDuplicates(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();
    }
}