CODE IN JAVA, the toString() method form the class:

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() { Node cursorNode = getCursor(); // get the node pointed to by the cursor Node lastNode = null;

// If cursorNode is not null, we can start searching from there if (cursorNode != null) { lastNode = cursorNode; } else { lastNode = head; }

// Iterate through the list until we find the last node while (lastNode != null && lastNode.next != null) { lastNode = lastNode.next; }

return lastNode; } private Node getCursor() { Node cursorNode = null;

// If precursor is null, the cursor is not pointing to a node if (precursor != null) { // If precursor is pointing to the last node, the cursor is null if (precursor.next != null) { cursorNode = precursor.next; } } return cursorNode; } 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 if (manyNodes != size()) { report("manyNodes does not equal the size of the list: " + size()); } // 3. Check that precursor is null or a node in the list Node curr = head; while (curr != null && curr != precursor) { curr = curr.next; } if (precursor != null && curr == null) { report("precursor is not null but does not point to a node in the list"); return false; } // 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"; }

@Override public String toString() { StringBuilder sb = new StringBuilder(); sb.append("["); // TODO: implement this method sb.append("]"); return sb.toString();

}