// 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) {
    ListNode prev = this.front;
    ListNode curr = prev.next;
    while (curr != null) {
      if (curr.data < other.front.data) {
        prev = prev.next;
        curr = curr.next;
      } else {
        prev.next = other.front;
        other.front = other.front.next;
        prev.next.next = curr;
        prev = prev.next;
      }
    }
    if (curr == null && other.front != null) {
      prev.next = other.front;
      other.front = null;
    }
  }

  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 Test10 {
  private static class TestResult {
    public final boolean pass;
    public final int setOtherToNullCount;
    public final int numTests;
    
    public TestResult(boolean pass, int setOther, int numTests) {
      this.pass = pass;
      this.setOtherToNullCount = setOther;
      this.numTests = numTests;
    }
  }
  
  private static int[][][] nullFront =
  {{{}, {15}}, {{}, {-8}}, {{}, {220}}};
  private static int[][][] nullOther =
  {{{15}, {}}, {{-19}, {}}, {{2}, {}}};

  private static int[][][] case1 =
  {{{-8}, {15}}, {{30}, {0}}, {{0}, {5}}};
  private static int[][][] case2 =
  {{{-8}, {15, 19}}, {{6}, {1, 4}}, {{0, 5}, {3}}};
  private static int[][][] case3 =
  {{{-8, 5}, {15, 19}}, {{5, 30}, {12, 109}}};
  private static int[][][] case4 =
  {
    {{0, 5, 10, 15, 20, 25}, {30, 35, 40, 45}},
    {{-8, 5, 15, 19}, {-15, 15, 18, 19, 25}},
    {{1, 3, 12, 16, 22, 25}, {-15, -8, 23, 105}}
  };
  private static int[][][] case5 =
  {
    {{0, 5, 10, 15, 20, 25, 30, 35, 40, 45},
      {50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100, 105, 110, 115, 120}},
    {{-8, 15, 22, 24, 25, 36, 190, 240, 244, 245, 260, 264, 265, 271, 290},
      {50, 55, 60, 65, 170, 175, 180, 185, 287, 295}},
    {{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}},
  };

  private static int[][][] case6 =
  {
    {{3, 5, 7}, {1, 5, 9}},
    {{5, 6, 10}, {5, 6, 10}},
    {{5, 6, 10}, {5, 6, 45}},
    {{5, 6, 40}, {5, 5, 5}}
  };
  private static int[][][] case7 =
  {
    {{2, 5, 8, 9, 10}, {-8, 2, 5, 6, 9, 10, 12}},
    {{2, 5, 5, 7, 9}, {3, 3, 5, 7, 7, 12, 12}},
    {{2, 5, 8, 9, 10, 12, 15}, {-8, 2, 5, 6, 9}},
    {{2, 2, 2, 9, 10, 12, 15}, {-8, 2, 5, 6, 9}},
  };
  private static int[][][] case8 =
  {
    {
      {2, 5, 8, 9, 10, 15, 16, 19, 20, 25, 26, 29},
      {-8, -5, 1, 2, 5, 8, 9, 10, 13, 14, 15, 19, 20, 21, 22, 26, 27, 28}
    },
    {
      {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[][][] 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) {
    int[][][][] cases = {case1, case2, case3, case4, case5, case6, case7, case8};
    System.out.println("TEST FOR NULL list1 CASE");

    TestResult nullRun = test(nullFront);
    boolean nullPass = nullRun.pass;

    TestResult otherRun = test(nullOther);
    boolean otherPass = otherRun.pass;

    int numSetNull = 0;
    int numTests = 0;
    int numPass = 0;
    for (int i = 0; i < cases.length; i++) {
      System.out.println("TEST FOR CASE " + (i + 1));
      TestResult run = test(cases[i]);
      if (run.pass) {
        numPass++;
      }
      numTests += run.numTests;
      numSetNull += run.setOtherToNullCount;
      System.out.println();
    }
    System.out.println();
    System.out.println("Set null in " + numSetNull + " / " + numTests + " cases");
    System.out.println("Works when front == null? " + (nullPass ? "yes" : "no"));
    System.out.println("Works when other.front == null? " + (otherPass ? "yes" : "no"));
    System.out.println("Score: " + numPass + " / " + cases.length);
  }

  public static TestResult test(int[][][] cases) {
    boolean pass = true;
    int setCount = 0;
    for (int i = 0; i < cases.length; i++) {
      TestResult run = test(cases[i][0], cases[i][1]);
      setCount += run.setOtherToNullCount;
      if (!run.pass) {
        pass = false;
      }
    }
    return new TestResult(pass, setCount, cases.length);
  }

  public static void test(int number) {
    int index = (number - 1) / 2;
    int[] data1 = cases[index][(number - 1) % 2];
    int[] data2 = cases[index][number % 2];
    test(data1, data2);
  }

  public static TestResult test(int[] data1, int[] data2) {
    // list1/list2 for testing sample, list3/list4 for their code
    try {
      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;
      boolean setOther = true;
      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++;
        setOther = false;
      }
      System.out.println();
      count++;  // increment test counter
      return new TestResult(!fail, setOther ? 1 : 0, 1);
    } catch (Exception e) {
      System.out.println("Exception!");
      e.printStackTrace();
      return new TestResult(false, 0, 1);
    }
  }
}

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