// Program to test solutions to problem #5 on the cse143 midterm, spring 2008
// Fill in your solution to interleave, then compile and run the program

import java.util.*;

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

    public static void main(String[] args) {
        test(new int[] {});
        test(new int[] {1, 2});
        test(new int[] {1, 2, 3, 4});
        test(new int[] {1, 2, 3, 4, 5, 6});
        test(new int[] {1, 2, 3, 4, 5, 6, 7, 8});
        test(new int[] {2, 8, -5, 19, 7, 3, 24, 42});
        test(new int[] {14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1});
    }

    public static void test(int[] data) {
        Queue<Integer> q1 = new LinkedQueue<Integer>();
        Queue<Integer> q2 = new LinkedQueue<Integer>();
        for (int n : data) {
            q1.enqueue(n);
            q2.enqueue(n);
        }
        System.out.println("Testing interleave on " + q1);
        interleave2(q1);
        System.out.println("    correct result = " + q1);
        boolean fail = false;
        try {
            interleave(q2);
        } catch (RuntimeException e) {
            System.out.println("    threw " + e);
            fail = true;
        }
        if (!fail)
            System.out.println("    test result    = " + q2);
        if (!fail && q1.toString().equals(q2.toString()))
            System.out.println("passed");
        else
            System.out.println("failed");
        System.out.println();
    }

    // this is the sample solution
    public static void interleave2(Queue<Integer> q) {
        if (q.size() % 2 != 0)
            throw new IllegalArgumentException();
        Stack<Integer> s = new ArrayStack<Integer>();
        int halfSize = q.size() / 2;
        for (int i = 0; i < halfSize; i++)
            s.push(q.dequeue());
        while (!s.isEmpty())
            q.enqueue(s.pop());
        for (int i = 0; i < halfSize; i++)
            q.enqueue(q.dequeue());
        for (int i = 0; i < halfSize; i++)
            s.push(q.dequeue());
        while (!s.isEmpty()) {
            q.enqueue(s.pop());
            q.enqueue(q.dequeue());
        }
    }
}

interface Stack<E> {
    // post: given value is pushed onto the top of the stack
    public void push(E value);

    // pre : !isEmpty()
    // post: removes and returns the value at the top of the stack
    public E pop();

    // post: returns true if the stack is empty, false otherwise
    public boolean isEmpty();

    // post: returns the current number of elements in the stack
    public int size();
}

class ArrayStack<E> implements Stack<E> {
    private ArrayList<E> elements;

    // post: constructs an empty stack
    public ArrayStack() {
        elements = new ArrayList<E>();
    }

    // post: given value is pushed onto the top of the stack
    public void push(E value) {
        elements.add(value);
    }

    // pre : !isEmpty()
    // post: removes and returns the value at the top of the stack
    public E pop() {
        if (isEmpty())
            throw new IllegalStateException("attempt to pop empty stack");
        return elements.remove(elements.size() - 1);
    }

    // post: returns true if the stack is empty, false otherwise
    public boolean isEmpty() {
        return elements.isEmpty();
    }

    // post: returns the current number of elements in the stack
    public int size() {
        return elements.size();
    }

    // post: returns a String representation of the stack contents
    public String toString() {
        return "bottom " + elements + " top";
    }
}

interface Queue<E> {
    // post: given value inserted at the end of the queue
    public void enqueue(E value);

    // pre : !isEmpty()
    // post: removes and returns the value at the front of the queue
    public E dequeue();

    // post: returns true if the queue is empty, false otherwise
    public boolean isEmpty();

    // post: returns the current number of elements in the queue
    public int size();
}

class LinkedQueue<E> implements Queue<E> {
    private LinkedList<E> elements;

    // post: constructs an empty queue
    public LinkedQueue() {
        elements = new LinkedList<E>();
    }

    // post: given value inserted at the end of the queue
    public void enqueue(E value) {
        elements.addLast(value);
    }

    // pre : !isEmpty()
    // post: removes and returns the value at the front of the queue
    public E dequeue() {
        if (isEmpty())
            throw new IllegalStateException("attempt to dequeue empty queue");
        return elements.removeFirst();
    }

    // post: returns true if the queue is empty, false otherwise
    public boolean isEmpty() {
        return elements.isEmpty();
    }

    // post: returns the current number of elements in the queue
    public int size() {
        return elements.size();
    }

    // post: returns a String representation of the queue contents
    public String toString() {
        return "front " + elements + " back";
    }
}