Instructions
Requirements and Specifications
Source Code
package edu.uwm.cs351.util;
import java.util.AbstractCollection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.NoSuchElementException;
import edu.uwm.cs.junit.LockedTestCase;
// This is a Homework Assignment for CS 351 at UWM
/**
* A cyclic singly-linked list implementation of the Java Collection interface
* We use {@link java.util.AbstractCollection} to implement most methods.
* You should override {@link #clear()} for efficiency, and {@link #add(E)}
* for functionality. You will also be required to override the abstract methods
* {@link #size()} and {@link #iterator()}. All these methods should be declared
* "@Override".
*
* The data structure is a cyclic singly-linked list with one dummy node.
* The fields should be:
*
*
- tail
The last node in the list.
*
- count
Number of elements in the collection.
*
- version
Version number (used for fail-fast semantics)
*
* It should be cyclicly linked without any null pointers.
* The code should have very few special cases.
* The class should define a private {@link #wellFormed()} method
* and perform assertion checks in each method.
* You should use a version stamp to implement fail-fast semantics
* for the iterator.
*
* @param E type of elements
*/
public class LinkedCollection extends AbstractCollection {
private static class Node {
Node next;
E data;
public Node(E data, Node next) {
this.data = data;
this.next = next;
}
}
private int version;
private int count;
private Node tail;
private LinkedCollection(boolean ignored) {
} // DO NOT CHANGE THIS
private static boolean doReport = true;
private boolean report(String s) {
if (doReport) System.out.println("invariant error: " + s);
return false;
}
/**
* Check the invariant:
*
*
- The "tail" is not null.
*
- We have a cycle from "tail" back around to "tail", in particular
*
*
- There are no null "next" pointers (the list never ends)
*
- We don't cycle back to a node other than the tail.
*
* This can be accomplished by a variant on Floyd's algorithm
* (tortoise and hare), where we stop if we hit null (an error)
* or the hare and tortoise are found on the same node (another error),
* or if the hare hits the tail again (everything is OK).
*
- We check that the node after the tail is a dummy node (data is null).
*
- We check that the number of nodes (including dummy) is one more than "count".
*
*
* @return whether the invariant is true
*/
private boolean wellFormed() {
if (tail == null)
return false;
for (Node n = tail.next; n != tail; n = n.next) {
if (n == null) return false;
}
if (tail.next.data != null) return false;
int num = 0;
for (Node n = tail.next; n != tail; n = n.next) {
num++;
}
if (num != count) {
return false;
}
return true;
}
/**
* Create an empty collection.
*/
public LinkedCollection() {
tail = new Node<>(null, null);
tail.next = tail;
count = 0;
assert wellFormed() : "invariant broken at constructor";
}
public Iterator iterator() {
return new MyIterator();
}
@Override
public int size() {
return count;
}
// You need a nested (not static) class to implement the iterator:
private class MyIterator implements Iterator {
private int myVersion;
private Node cursor, precursor;
MyIterator(boolean ignored) {
} // DO NOT CHANGE THIS
private boolean wellFormed() {
// Invariant for recommended fields:
// 0. The outer invariant holds
// 1. precursor is a node in the cyclic list
// 2. cursor is either the same as precursor or the node after
// 3. cursor is dummy only if it is the same as the precursor
// NB: Don't check 1,2,3 unless the version matches.
if (!LinkedCollection.this.wellFormed()) {
return false;
}
if (this.myVersion != LinkedCollection.this.version) {
return false;
}
if (precursor == null)
return false;
if (precursor != cursor && cursor != precursor.next) {
return false;
}
if (precursor == cursor && count > 0) {
return false;
}
return true;
}
MyIterator() {
precursor = tail;
cursor = tail.next;
assert wellFormed() : "invariant fails in iterator constructor";
}
// TODO: Many things
// Declare methods.
// check for invariant in every method
// check for concurrent modification exception in every method
// (implicitly is OK).
// hasNext/next/remove should not have loops (all constant-time operations).
// (The invariant check will need loops)
@Override
public boolean hasNext() {
assert wellFormed();
return cursor != tail;
}
@Override
public E next() {
assert wellFormed();
if (!hasNext()) {
throw new NoSuchElementException();
}
E result = cursor.data;
cursor = cursor.next;
precursor = precursor.next;
return result;
}
@Override
public void remove() {
assert wellFormed();
if (cursor == tail) {
throw new NoSuchElementException();
}
precursor.next = cursor.next;
cursor = cursor.next;
LinkedCollection.this.count--;
}
}
public static class TestInvariant extends LockedTestCase {
protected LinkedCollection self;
protected LinkedCollection.MyIterator iterator;
protected Node dummy;
protected Node n1, n2, n3, n4, n1a;
@Override
protected void setUp() {
self = new LinkedCollection(false);
self.tail = null;
self.count = 0;
self.version = 0;
iterator = self.new MyIterator(false);
iterator.cursor = iterator.precursor = null;
iterator.myVersion = 0;
dummy = new Node(null, null);
dummy.next = dummy;
n1 = new Node("hello", null);
n2 = new Node("world", null);
n3 = new Node("bye", null);
n4 = new Node(null, null);
n1a = new Node("hello", null);
}
protected void assertWellFormed(boolean b) {
try {
doReport = b;
assertEquals(b, self.wellFormed());
} finally {
doReport = true;
}
}
protected void assertIteratorWellFormed(boolean b) {
try {
doReport = b;
assertEquals(b, iterator.wellFormed());
} finally {
doReport = true;
}
}
public void testA() {
self.tail = null;
assertWellFormed(false);
self.tail = dummy;
dummy.next = null;
assertWellFormed(false);
dummy.next = self.tail;
assertWellFormed(true);
}
public void testB() {
self.version = -1;
self.tail = dummy;
assertWellFormed(true);
self.count = -1;
assertWellFormed(false);
self.count = 1;
assertWellFormed(false);
}
public void testC() {
self.tail = n1;
assertWellFormed(false);
self.tail.next = self.tail;
assertWellFormed(false);
self.count = 1;
assertWellFormed(false);
}
public void testD() {
self.tail = n2;
assertWellFormed(false);
n2.next = dummy;
self.count = 1;
assertWellFormed(false);
dummy.next = n1;
self.count = 2;
assertWellFormed(false);
n1.next = n2;
assertWellFormed(true);
}
public void testE() {
self.tail = n4;
n4.next = dummy;
dummy.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;
self.count = -1;
assertWellFormed(false);
self.count = 0;
assertWellFormed(false);
self.count = 1;
assertWellFormed(false);
self.count = 2;
assertWellFormed(false);
self.count = 3;
assertWellFormed(false);
self.count = 4;
assertWellFormed(true);
self.count = 5;
assertWellFormed(false);
}
public void testF() {
self.tail = n4;
n4.next = dummy;
dummy.next = n1;
n1.next = n2;
n2.next = n3;
n3.next = n4;
self.count = 4;
assertWellFormed(true);
n3.next = n3;
assertWellFormed(false);
n3.next = n2;
assertWellFormed(false);
n3.next = n1;
assertWellFormed(false);
n3.next = dummy;
assertWellFormed(false);
}
public void testG() {
self.tail = n2;
n2.next = dummy;
dummy.next = self.tail;
self.count = 0;
assertWellFormed(false);
iterator.precursor = iterator.cursor = n2;
assertIteratorWellFormed(false);
}
public void testH() {
self.tail = dummy;
iterator.precursor = iterator.cursor = dummy;
assertIteratorWellFormed(true);
self.version = 1617;
assertIteratorWellFormed(true);
iterator.precursor = n1;
assertIteratorWellFormed(true);
iterator.cursor = null;
assertIteratorWellFormed(true);
}
public void testI() {
self.tail = dummy;
iterator.precursor = iterator.cursor = null;
assertIteratorWellFormed(false);
iterator.precursor = iterator.cursor = n4;
n4.next = n4;
assertIteratorWellFormed(false);
}
public void testJ() {
self.tail = n3;
n3.next = dummy;
dummy.next = n1;
n1.next = n4;
n4.next = n2;
n2.next = n3;
self.count = 4;
assertWellFormed(true);
iterator.precursor = iterator.cursor = n1;
assertIteratorWellFormed(true);
iterator.precursor = iterator.cursor = n2;
assertIteratorWellFormed(true);
iterator.precursor = iterator.cursor = n3;
assertIteratorWellFormed(true);
iterator.precursor = iterator.cursor = n4;
assertIteratorWellFormed(true);
iterator.precursor = iterator.cursor = dummy;
assertIteratorWellFormed(true);
}
public void testK() {
self.tail = n3;
n3.next = dummy;
dummy.next = n1;
n1.next = n4;
n4.next = n2;
n2.next = n3;
self.count = 4;
assertWellFormed(true);
iterator.precursor = dummy;
iterator.cursor = n1;
assertIteratorWellFormed(true);
iterator.precursor = n1;
iterator.cursor = n4;
assertIteratorWellFormed(true);
iterator.precursor = n4;
iterator.cursor = n2;
assertIteratorWellFormed(true);
iterator.precursor = n2;
iterator.cursor = n3;
assertIteratorWellFormed(true);
iterator.precursor = n3;
iterator.cursor = dummy;
assertIteratorWellFormed(false);
}
public void testL() {
self.tail = n3;
n3.next = dummy;
dummy.next = n1;
n1.next = n4;
n4.next = n2;
n2.next = n3;
self.count = 4;
assertWellFormed(true);
iterator.precursor = dummy;
iterator.cursor = n2;
assertIteratorWellFormed(false);
iterator.cursor = n3;
assertIteratorWellFormed(false);
iterator.cursor = n4;
assertIteratorWellFormed(false);
iterator.precursor = n1;
iterator.cursor = n2;
assertIteratorWellFormed(false);
iterator.cursor = n3;
assertIteratorWellFormed(false);
iterator.cursor = dummy;
assertIteratorWellFormed(false);
iterator.precursor = n2;
iterator.cursor = n1;
assertIteratorWellFormed(false);
iterator.cursor = n4;
assertIteratorWellFormed(false);
iterator.cursor = dummy;
assertIteratorWellFormed(false);
iterator.precursor = n3;
iterator.cursor = n1;
assertIteratorWellFormed(false);
iterator.cursor = n2;
assertIteratorWellFormed(false);
iterator.cursor = n4;
assertIteratorWellFormed(false);
iterator.precursor = n4;
iterator.cursor = n1;
assertIteratorWellFormed(false);
iterator.cursor = n3;
assertIteratorWellFormed(false);
iterator.cursor = dummy;
assertIteratorWellFormed(false);
}
public void testM() {
self.tail = n3;
n3.next = dummy;
dummy.next = n1;
n1.next = n4;
n1a.next = n4;
n4.next = n2;
n2.next = n3;
self.count = 4;
assertWellFormed(true);
iterator.precursor = n1a;
iterator.cursor = n4;
assertIteratorWellFormed(false);
iterator.precursor = n1;
assertIteratorWellFormed(true);
}
public void testN() {
self.tail = n1;
n1.next = dummy;
n1a.next = dummy;
dummy.next = n4;
n4.next = n3;
n3.next = n2;
n2.next = n1;
self.count = 4;
assertWellFormed(true);
iterator.precursor = n2;
iterator.cursor = n1a;
assertIteratorWellFormed(false);
iterator.cursor = n1;
assertIteratorWellFormed(true);
}
public void testO() {
self.tail = n1;
n1.next = dummy;
n1a.next = dummy;
dummy.next = n4;
n4.next = n3;
n3.next = n2;
n2.next = n1;
self.count = 4;
assertWellFormed(true);
iterator.precursor = n1a;
iterator.cursor = dummy;
assertIteratorWellFormed(false);
iterator.precursor = n1;
assertIteratorWellFormed(false);
iterator.myVersion = 1;
assertIteratorWellFormed(true);
}
}
}