Create A Program to Create a Linked Collection in Java Assignment Solution
- Instructions
- Objective
- Requirements and Specifications
Instructions
Objective
Write a java assignment program to create a linked collection.
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);
}
}
}
Similar Samples
Discover our curated selection of programming homework samples featuring Java, Python, C++, and more. Each sample showcases our expertise in solving intricate coding challenges effectively. Whether you're tackling algorithms, data structures, or software development projects, our samples illustrate our commitment to delivering high-quality solutions tailored to your academic requirements.
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java
Java