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

import java.util.*;

public class Test5 {
    public static boolean equals(Stack<Integer> s1, Stack<Integer> s2) {
        // fill in your solution here
        // you can also rename the parameters above
    }

    // this is the sample solution
    public static boolean equals2(Stack<Integer> s1, Stack<Integer> s2) {
        if (s1.size() != s2.size()) {
            return false;
        } else {
            Stack<Integer> s3 = new ArrayStack<Integer>();
            boolean same = true;
            while (same && !s1.isEmpty()) {
                int num1 = s1.pop();
                int num2 = s2.pop();
                if (num1 != num2)
                    same = false;
                s3.push(num1);
                s3.push(num2);
            }
            while (!s3.isEmpty()) {
                s2.push(s3.pop());
                s1.push(s3.pop());
            }
            return same;
        }
    }

    public static void main(String[] args) {
        List<Stack<Integer>> stacks = new ArrayList<Stack<Integer>>();
        stacks.add(makeStack(new int[] {}));
        stacks.add(makeStack(new int[] {}));
        stacks.add(makeStack(new int[] {3}));
        stacks.add(makeStack(new int[] {3}));
        stacks.add(makeStack(new int[] {1}));
        stacks.add(makeStack(new int[] {3, 18}));
        stacks.add(makeStack(new int[] {3, 18}));
        stacks.add(makeStack(new int[] {1, 2}));
        stacks.add(makeStack(new int[] {3, 18, 9}));
        stacks.add(makeStack(new int[] {3, 18, 9}));
        stacks.add(makeStack(new int[] {7, 18, 9}));
        stacks.add(makeStack(new int[] {3, 18, 9, 42}));
        stacks.add(makeStack(new int[] {3, 18, 9, 42}));
        stacks.add(makeStack(new int[] {3, 17, 9, 42}));
        for (int i = 0; i < stacks.size(); i++)
            for (int j = i + 1; j < stacks.size(); j++)
                test(stacks.get(i), stacks.get(j));
    }

    public static void test(Stack<Integer> s1, Stack<Integer> s2) {
        System.out.println("s1 = " + s1);
        System.out.println("s2 = " + s2);
        boolean ok = test(s1, s2, "s1", "s2");
        ok = test(s2, s1, "s2", "s1") && ok;
        if (ok) {
            System.out.println("passed");
        } else {
            System.out.println("failed");
        }
        System.out.println();
    }

    public static boolean test(Stack<Integer> s1, Stack<Integer> s2,
                               String str1, String str2) {
        Stack<Integer> s3 = copyStack(s1);
        Stack<Integer> s4 = copyStack(s2);
        boolean result1 = equals2(s1, s2);
        try {
            boolean result2 = equals(s3, s4);
            if (result1 != result2 || !equals2(s1, s3) || !equals(s2, s4)) {
                System.out.println("equals(" + str1 + ", " + str2 +") fails:");
                if (result1 != result2)
                    System.out.println("    should return " + result1 +
                                       ", yours returns " + result2);
                if (!equals2(s1, s3))
                    System.out.println("    yours left " + str1 + " = " + s3);
                if (!equals2(s2, s4))
                    System.out.println("    yours left " + str2 + " = " + s4);
                return false;
            }
        } catch (RuntimeException e) {
            System.out.println("threw " + e);
            return false;
        }
        return true;
    }
        
    public static Stack<Integer> makeStack(int[] data) {
        Stack<Integer> s = new ArrayStack<Integer>();
        for (int x : data)
            s.push(x);
        return s;
    }

    public static Stack<Integer> copyStack(Stack<Integer> s) {
        Stack<Integer> s2 = new ArrayStack<Integer>();
        Queue<Integer> q = new LinkedQueue<Integer>();
        while (!s.isEmpty())
            s2.push(s.pop());
        while(!s2.isEmpty())
            q.enqueue(s2.pop());
        while (!q.isEmpty()) {
            int n = q.dequeue();
            s.push(n);
            s2.push(n);
        }
        return s2;
    }
}

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";
    }
}