// Program to test solutions to problem #9 on the cse143 final, winter 2014.
// Fill in your solution to mergeFrom, then compile and run the program


import java.util.*;

class LinkedIntList {
    public void mergeFrom(LinkedIntList other) {
        // fill in your solution here
        // you can also rename the parameter above
    }

    private ListNode front;  // first value in the list

    // this is the sample solution
    public void mergeFrom2(LinkedIntList other) {
        if (other.front != null) {
            if (front == null)
                front = other.front;
            else {
                ListNode current1 = front;
                ListNode current2 = other.front;

                if (front.data <= other.front.data) {
                    current1 = current1.next;
                } else {
                    front = other.front;
                    current2 = current2.next;
                }
                ListNode current3 = front;
                while (current1 != null && current2 != null) {
                    if (current1.data <= current2.data) {
                        current3.next = current1;
                        current1 = current1.next;
                    } else {
                        current3.next = current2;
                        current2 = current2.next;
                    }
                    current3 = current3.next;
                }
                if (current1 != null) {
                    current3.next = current1;
                } else {
                    current3.next = current2;
                }
            }
            other.front = null;
        }
    }

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

    public boolean isSorted() {
        if (front != null) {
            ListNode current = front;
            while (current.next != null) {
                if (current.data > current.next.data)
                    return false;
                current = current.next;
            }
        }
        return true;
    }

    public boolean isEmpty() {
        return front == null;
    }

    // post: returns the current number of elements in the list
    public int size() {
        int count = 0;
        ListNode current = front;
        while (current != null) {
            current = current.next;
            count++;
        }
        return count;
    }

    // pre : 0 <= index < size()
    // post: returns the integer at the given index in the list
    public int get(int index) {
        ListNode current = front;
        for (int i = 0; i < index; i++)
            current = current.next;
        return current.data;
    }

    // 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 : returns the position of the first occurence of the given
    //        value (-1 if not found)
    public int indexOf(int value) {
        int index = 0;
        ListNode current = front;
        while (current !=  null) {
            if (current.data == value)
                return index;
            index++;
            current = current.next;
        }
        return -1;
    }

    // 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);
        }
    }

    // pre: 0 <= index <= size()
    // post: inserts the given value at the given index, shifting subsequent
    //       values right
    public void add(int index, int value) {
        if (index == 0)
            front = new ListNode(value, front);
        else {
            ListNode current = front;
            for (int i = 0; i < index - 1; i++)
                current = current.next;
            current.next = new ListNode(value, current.next);
        }
    }

    // pre : 0 <= index < size()
    // post: removes value at the given index, shifting subsequent values left
    public void remove(int index) {
        if (index == 0)
            front = front.next;
        else {
            ListNode current = front;
            for (int i = 0; i < index - 1; i++)
                current = current.next;
            current.next = current.next.next;
        }
    }
}

public class FinalTest9 {
    private static int[][][] cases = 
    {{{3, 12, 15}, {}}, {{-8}, {15}}, {{0, 15}, {8}}, {{5, 30}, {12, 109}},
     {{0, 3, 6, 9}, {2, 4, 8, 10, 12, 14}},
     {{10, 20, 30, 40, 50, 60, 70, 80, 90, 100},
      {3, 5, 27, 32, 33, 34, 52, 58, 83, 86, 93, 94, 95, 150, 250}},
     {{0, 2, 4}, {0, 1, 2}},
     {{2, 5, 5, 7, 9}, {3, 3, 5, 7, 7, 12, 12}},
     {{3, 3, 3, 5, 5, 5, 5, 14, 15, 15, 15, 42},
      {-4, -1, -1, 5, 5, 12, 12, 12, 12, 28, 28, 28, 28, 28, 28, 42, 55, 55}}};

    private static int count = 0;  // test counter for arrays
    private static int totalFail = 0;
    private static int otherNull = 0;

    public static void main(String[] args) {
        for (int i = 1; i <= cases.length * 2; i++) {
            System.out.println("case #" + i);
            test(i);
        }

        if (totalFail > 0) {
            System.out.println("failed " + totalFail + " of " + count + 
                               " tests");
        } else {
            System.out.println("passed all tests");
        }

        if (otherNull != 0) {
            System.out.println();
            int nullCases = count - 1;
            System.out.println("other.front not set to null in " + otherNull +
                               " of " + nullCases + " cases");
        }
    }

    public static void test(int number) {
        int index = (number - 1) / 2;
        int[] data1 = cases[index][(number - 1) % 2];
        int[] data2 = cases[index][number % 2];
        // list1/list2 for testing sample, list3/list4 for their code
        LinkedIntList list1 = new LinkedIntList();
        LinkedIntList list2 = new LinkedIntList();
        LinkedIntList list3 = new LinkedIntList();
        LinkedIntList list4 = new LinkedIntList();
        for (int n : data1) {
            list1.add(n);
            list3.add(n);
        }
        for (int n : data2) {
            list2.add(n);
            list4.add(n);
        }
        if (!list1.isSorted()) {
            throw new RuntimeException("unsorted list: " + list1);
        }
        if (!list2.isSorted()) {
            throw new RuntimeException("unsorted list: " + list2);
        }
        boolean fail = false;
        System.out.println("list1    = " + list1);
        System.out.println("list2    = " + list2);
        list1.mergeFrom2(list2);
        System.out.println("expected = " + list1);
        boolean threw = false;
        try {
            list3.mergeFrom(list4);
        } catch (RuntimeException e) {
            int line = e.getStackTrace()[0].getLineNumber();
            System.out.println("    threw " + e + " at line #" + line);
            threw = true;
        }
        String str1 = list1.toString();
        String str3 = list3.toString();
        if (!fail && !str1.equals(str3)) {
            fail = true;
            System.out.println("actual   = " + str3);
        }
        if (fail || threw) {
            System.out.println("failed");
            totalFail++;
        } else {
            System.out.println("passed");
        }
        if (!list4.isEmpty()) {
            System.out.println("list4 = " + list4);
            System.out.println("other.front not set to null");
            otherNull++;
        }
        System.out.println();
        count++;  // increment test counter
    }
}

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

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