// Program to test solutions to problem #9 on the cse143 final, fall 2012. // Fill in your solution to weave, then compile and run the program import java.util.*; class LinkedIntList { public void weave(LinkedIntList other) { // fill in your solution here } private ListNode front; // first value in the list // this is the sample solution public void weave2(LinkedIntList other) { if (front == null) { front = other.front; other.front = null; } else if (other.front != null) { ListNode current1 = front; ListNode current2 = other.front; while (current1.next != null && current2.next != null) { ListNode temp = current1.next; current1.next = current2; current2 = current2.next; current1.next.next = temp; current1 = temp; } if (current1.next == null) current1.next = current2; else { current2.next = current1.next; current1.next = current2; } other.front = null; } } // post: constructs an empty list public LinkedIntList() { 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 totalFail = 0; private static boolean list2Null = true; public static void main(String[] args) { test(0, 0); test(0, 1); test(0, 4); test(1, 0); test(4, 0); test(1, 1); test(2, 2); test(3, 3); test(1, 2); test(2, 1); test(2, 3); test(3, 2); test(3, 4); test(4, 3); test(6, 9); test(12, 8); if (totalFail > 0) { System.out.println("failed " + totalFail + " tests"); if (!list2Null) System.out.println("and list2 was not empty in all cases"); } else { System.out.println("passed all tests for first list"); if (list2Null) System.out.println("and list2 was empty in all cases"); else System.out.println("but list2 was not empty in all cases"); } } public static void test(int size1, int size2) { LinkedIntList list1 = new LinkedIntList(); LinkedIntList list2 = new LinkedIntList(); LinkedIntList list3 = new LinkedIntList(); LinkedIntList list4 = new LinkedIntList(); for (int i = 0; i < size1; i++) { list1.add(11 + i); list3.add(11 + i); } for (int i = 0; i < size2; i++) { list2.add(21 + i); list4.add(21 + i); } boolean fail = false; System.out.println("testing lengths " + size1 + ", " + size2); System.out.println("list1 = " + list1); System.out.println("list2 = " + list2); list1.weave2(list2); System.out.println("expected = " + list1); try { list3.weave(list4); } catch (RuntimeException e) { int line = e.getStackTrace()[0].getLineNumber(); System.out.println(" threw " + e + " at line #" + line); fail = true; } if (!fail && !list1.toString().equals(list3.toString())) { System.out.println("actual = " + list3); fail = true; } if (fail) { System.out.println("failed"); totalFail++; } else { System.out.println("passed"); if (list4.size() > 0) { System.out.println("but list2 is not empty"); list2Null = false; } } System.out.println(); } } 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; } }