CODE IN JAVA: The addAll() method

public class BallSeq implements Cloneable { /** * A data class used for the linked structure for the linked list implementation of BallSeq. */ private static class Node { Ball data; Node next;

public Node(Ball data, Node next) { this.data = data; this.next = next; } }

private int manyNodes; private Node head; private Node precursor; // Remember that two of the fields are "model fields" // and will not be declared as real fields. // TODO: Define private getters for the two model fields (cursor and tail). private Node getTail() { if (head == null) { return null; } else { Node current = head; while (current.next != null) { current = current.next; } return current; } } private Node getCursor() { if (precursor == null) { return head; } return precursor.next; } private static boolean doReport = true; // do not edit: used in invariant checking

/** * Used to report an error found when checking the invariant. * By providing a string, this will help debugging the class if the invariant should fail. * @param error string to print to report the exact error found * @return false always */ private boolean report(String error) { if (doReport) System.out.println("Invariant error found: " + error); return false; }

/** * Check the invariant. * Return false if any problem is found. Returning the result * of {@link #report(String)} will make it easier to debug invariant problems. * @return whether invariant is currently true */ private boolean wellFormed() { // Invariant: // 1. list must not include a cycle. // 2. manyNodes is number of nodes in list. // 3. the precursor must be null or point to a node in the list. // 1. check that list is not cyclic if (head != null) { // Floyd's Tortoise and Hare Algorithm Node fast = head.next; for (Node p = head; fast != null && fast.next != null; p = p.next) { if (p == fast) return report("list is cyclic!"); fast = fast.next.next; } }

// 2. check number of nodes int count = 0; Node current = head; while (current != null) { count++; current = current.next; } if (manyNodes != count) { return report("manyNodes does not equal the size of the nodes in the list: " + count); } // 3. Check that precursor is null or a node in the list if (precursor != null) { Node p = head; while (p != null && p != precursor) { p = p.next; } if (p == null) { return report("precursor is not null but does not point to a node in the list"); } } // TODO: Implement conditions 2 and 3 // Hint: condition 2 simply requires counting nodes as we've done // elsewhere in this and the previous lesson. // For condition 3: if precursor isn't null, // go through the list and see if // the precursor is any node in the list. // After you have looked at all nodes, if you never // found the precursor, then report the problem. // If no problems found, then return true: return true; }

/** Private constructor for testing the invariant. Do not modify */ private BallSeq(boolean testInvariant) {} /** * Create an empty sequence. * @param - none * @postcondition * This sequence is empty **/ public BallSeq( ) { manyNodes = 0; head = null; precursor = null; assert wellFormed() : "invariant failed at end of constructor"; } /** * Place the contents of another sequence at the end of this sequence. * @param addend * a sequence whose contents will be placed at the end of this sequence * @precondition * The parameter, addend, is not null. * @postcondition * The elements from addend have been placed at the end of * this sequence. The current element of this sequence remains unchanged, * and the addend is also unchanged (unless it's the same as this). * @exception NullPointerException * Indicates that addend is null. **/ public void addAll(BallSeq addend) { assert wellFormed() : "invariant wrong at start of addAll"; assert addend.wellFormed() : "invariant of parameter wrong at start of addAll";

assert wellFormed() : "invariant wrong at end of addAll"; assert addend.wellFormed() : "invariant of parameter wrong at end of addAll"; }