// Program to test solutions to problem #9 on the cse143 final, spring 2012.
// Fill in your solution to rearrange, then compile and run the program

import java.util.*;

class LinkedIntList {
    public void rearrange() {
        // fill in your solution here
    }

    private ListNode front;  // first value in the list

    // this is the sample solution
    public void rearrange2() {
        if (front != null && front.next != null) {
            ListNode sub1 = front;
            ListNode sub1Back = front;
            ListNode sub2 = front.next;
            ListNode sub2Back = sub2;
            front.next = null;
            ListNode current = sub2.next;
            boolean list1 = true;
            while (current != null) {
                ListNode temp = current;
                current = current.next;
                if (list1) {
                    temp.next = sub1;
                    sub1 = temp;
                } else {
                    sub2Back.next = temp;
                    sub2Back = temp;
                }
                list1 = !list1;
            }
            front = sub1;
            sub1Back.next = sub2;
            sub2Back.next = null;
        }
    }

    // post: constructs an empty list
    public LinkedIntList() {
        front = null;
    }

    // post: creates a comma-separated, bracketed version of the list
    public String toString() {
        if (front == null)
            return "[]";
        else {
            String result = "[" + front.data;
            ListNode current = front.next;
            while (current != null) {
                result += ", " + current.data;
                current = current.next;
            }
            result += "]";
            return result;
        }
    }

    // post: appends the given value to the end of the list
    public void add(int value) {
        if (front == null)
            front = new ListNode(value);
        else {
            ListNode current = front;
            while (current.next != null)
                current = current.next;
            current.next = new ListNode(value);
        }
    }
}

public class FinalTest9 {
    public static void main(String[] args) {
        int fail = 0;
        fail += test(new int[] {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10});
        fail += test(new int[] {42, 9, 17, 8, -8, 0, 32, 32, 42, 0});
        if (fail > 0)
            System.out.println("failed " + fail + " tests");
        else
            System.out.println("passed all tests");
    }

    public static int test(int[] data) {
        int failCount = 0;
        for (int i = 0; i <= data.length; i++) {
            LinkedIntList list1 = new LinkedIntList();
            LinkedIntList list2 = new LinkedIntList();
            for (int j = 0; j < i; j++) {
                list1.add(data[j]);
                list2.add(data[j]);
            }
            boolean fail = false;
            System.out.println("list     = " + list1);
            list1.rearrange2();
            System.out.println("expected = " + list1);
            int count = ListNode.count;
            try {
                list2.rearrange();
            } catch (RuntimeException e) {
                int line = e.getStackTrace()[0].getLineNumber();
                System.out.println("    threw " + e + " at line #" + line +
                                   " with list = " + list2);
                fail = true;
            }
            if (!fail && (!list1.toString().equals(list2.toString()))) {
                System.out.println("actual   = " + list2);
                fail = true;
            }
            if (count != ListNode.count) {
                System.out.println("extra nodes were constructed");
                fail = true;
            }
            if (fail) {
                System.out.println("failed");
                failCount++;
            } else
                System.out.println("passed");
            System.out.println();
        }
        return failCount;
    }
}

class ListNode {
    public final int data;       // data stored in this node
    public ListNode next;  // link to next node in the list

    public static int count;

    // post: constructs a node with data 0 and null link
    public ListNode() {
        this(0, null);
    }

    // post: constructs a node with given data and null link
    public ListNode(int data) {
        this(data, null);
    }

    // post: constructs a node with given data and given link
    public ListNode(int data, ListNode next) {
        this.data = data;
        this.next = next;
        count++;
    }
}