// File: LinkedSeq.java based on the package edu.colorado.collections
// This is an assignment for after completion of Chapters 4 and 5
// of "Data Structures and Other Objects Using Java" by Michael Main.
/******************************************************************************
* This class is a homework assignment;
* A LinkedSeq is a collection of objects that are kept in order.
* The sequence can have a special "current element," which is specified and
* accessed through four methods that are not available in the bag class
* (start, getCurrent, advance and isCurrent).
*
* @note
* Beyond Int.MAX_VALUE elements, the size method does not work.
*
* @see
* Based on the sequence with linked list assignment by Michael Main
* in chapter 4 but using generic nodes from chapter 5
*
* @version
* March 2007
*
* @author Implementation by Student name
******************************************************************************/
public class LinkedSeq<E> implements Cloneable
{
// Invariant of the LinkedSeq class:
// 1. the number of items in the sequence is maintained in manyNodes
// 2. head points to the first node, if any, or it is null
// 3. tail points to the last node, if any, or it is null
// 4. if there is a current item, cursor points to it and
// precursor points to the node before it, if any
// 5. if there is no current item, cursor and precursor are both null
private Node<E> head, tail, cursor, precursor;
private int manyNodes;
/**
* Initialize an empty sequence.
* @param - none
* @postcondition:
* This sequence is empty.
**/
public LinkedSeq( )
{
head = null;
tail= null;
cursor = null;
precursor = null;
manyNodes = 0;
}
/**
* Add a new element to this sequence, after the current element.
* @param element
* the new element that is being added
* @postcondition:
* A new copy of the element has been added to this sequence. If there was
* a current element, then the new element is placed after the current
* element. If there was no current element, then the new element is placed
* at the end of the sequence. In all cases, the new element becomes the
* new current element of this sequence.
* @exception OutOfMemoryError
* Indicates insufficient memory for a new node.
**/
public void addAfter(E element)
{
if(isCurrent())
{
Node<E> newNode= new Node<E>(element, cursor.getLink());//create new node
cursor.setLink(newNode);
precursor = cursor;//move precursor
cursor = newNode;//move cursor
if(cursor.getLink() == null)
{
tail = cursor;
}
}
else
{
if(tail == null)
{//when there is not a tail reference, there's no head reference either
tail = new Node<E>(element, null);//create new node and point
// tail to this new node
cursor = tail;//move cursor to the new node
precursor = null;//move precursor to tail
head = tail;//move head to the same node as tail
}
else
{//when tail is not null, there is a head, so do nothing there
//precursor = tail;
Node<E> newNode= new Node<E>(element, tail.getLink());//create new node and point tail to
// this new node
if(cursor == null)
{
cursor = tail;
}
cursor.setLink(newNode);
precursor = tail;
cursor = newNode;
tail = cursor;
}
}
manyNodes++;//update invariant
}
/**
* Add a new element to this sequence, before the current element.
* @param element
* the new element that is being added
* @postcondition:
* A new copy of the element has been added to this sequence. If there was
* a current element, then the new element is placed before the current
* element. If there was no current element, then the new element is placed
* at the start of the sequence. In all cases, the new element becomes the
* new current element of this sequence.
* @exception OutOfMemoryError
* Indicates insufficient memory for a new node.
**/
public void addBefore(E element)
{
if(isCurrent())
{// if there is a current element
if(cursor==head)
{// where cursor is the head
Node<E> newNode = new Node<E>(element, cursor);//add new node
newNode.setLink(cursor);
head = newNode;//move head
cursor = head;
precursor = null;
}
else
{//if cursor is not the head
Node<E> newNode = new Node<E>(element, cursor);//add new node
precursor.setLink(newNode);
cursor = newNode;
head = precursor;
//precursor=head;
}
}
else
{//no current element
if(head == null)
{//if head is null
head = new Node<E>(element, null);
cursor = head;//move cursor
precursor = null;
tail = head;//move tail
}
else
{//otherwise, add the node after the precursor, before cursor
Node<E> newNode = new Node<E>(element, head);//add after precursor
head = newNode;
cursor = head;
precursor = null;
}
}
manyNodes++;//update invariant
}
/**
* 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 where it
* was, and the addend is also unchanged.
* @exception NullPointerException
* Indicates that addend is null.
* @exception OutOfMemoryError
* Indicates insufficient memory to increase the size of this sequence.
**/
public void addAll(LinkedSeq<E> addend)
{
if(addend == null)
{
throw new NullPointerException("addend is null");
}
tail.setLink(addend.head);
//addend.head = this.tail;
tail = addend.tail;
//addend.tail = this.tail;
addend.cursor = null;
manyNodes += addend.manyNodes;
addend.tail = tail;
//if(addend.tail.getLink() != null)
//{
// addend.tail = addend.tail.getLink();
//}
}
/**
* Move forward, so that the current element is now the next element in
* this sequence.
* @param - none
* @precondition:
* isCurrent() returns true.
* @postcondition:
* If the current element was already the end element of this sequence
* (with nothing after it), then there is no longer any current element.
* Otherwise, the new element is the element immediately after the
* original current element.
* @exception IllegalStateException
* Indicates that there is no current element, so
* advance may not be called.
**/
public void advance( )
{
if(isCurrent())
{
if(cursor.getLink() == null)
{
tail = cursor;
cursor = cursor.getLink();
precursor = cursor;
}
else
{
precursor = cursor;
cursor = cursor.getLink();
}
//if(cursor.getLink() == null)
// {
// tail = cursor.getLink();
// }
}
else
{
throw new IllegalStateException("end of the seq, can't advance");
}
}
/**
* Generate a copy of this sequence.
* @param - none
* @return
* The return value is a copy of this sequence. Subsequent changes to the
* copy will not affect the original, nor vice versa. Note that the return
* value must be type cast to a LinkedSeq before it can be used.
* @exception OutOfMemoryError
* Indicates insufficient memory for creating the clone.
* @note
* Refer to discussion on p. 228 of text; there's substantial extra work
* In the generic implementation, you will get an unavoidable warning on
* answer = (LinkedSeq<E>) super.clone( );
* That's okay. The cure is worse than the disease.
**/
@SuppressWarnings("unchecked")
public LinkedSeq<E> clone( ) // DO NOT CHANGE THIS METHOD
{ LinkedSeq<E> answer;
try {
answer = (LinkedSeq<E>) super.clone( ); // causes warning that we have suppressed
}
catch (CloneNotSupportedException e)
{ // This exception should not occur. But if it does, it would probably
// indicate a programming error that made super.clone unavailable.
// The most common error would be forgetting the "Implements Cloneable"
// clause at the start of this class.
throw new RuntimeException
("This class does not implement Cloneable");
}
if (head != null) { // need to copy this sequence into answer
// copy the first node
answer.head = new Node<E>(head.getData(), null);
if (cursor == head) {
answer.cursor = answer.head;
}
if (precursor == head) { // current is next node
answer.precursor = answer.head;
}
// copy the rest of the sequence
Node<E> thisPtr = head.getLink();
Node<E> answerPtr = answer.head;
while (thisPtr != null){
answerPtr.setLink(new Node<E>(thisPtr.getData(), null));
answerPtr = answerPtr.getLink( );
if (cursor == thisPtr) {
answer.cursor = answerPtr;
}
if (precursor == thisPtr) { // current is next node
answer.precursor = answerPtr;
}
thisPtr = thisPtr.getLink( );
}
// set answer's tail to the last node created
answer.tail = answerPtr;
}
return answer;
}
/**
* Create a new sequence that contains all the elements from one sequence
* followed by the other.
* @param s1
* the first of two sequences
* @param s2
* the second of two sequences
* @precondition:
* Neither s1 nor s2 is null.
* @return
* a new sequence that has the elements of s1 followed by the
* elements of s2 (with no current element)
* @exception NullPointerException.
* Indicates that one of the arguments is null.
* @exception OutOfMemoryError
* Indicates insufficient memory for the new sequence.
**/
public static <E> LinkedSeq<E> concatenation(LinkedSeq<E> s1, LinkedSeq<E> s2)
{
if((s1 == null) && (s2 == null))
{
throw new IllegalArgumentException ("concatenation: one argument is null");
}
LinkedSeq<E> answer = new LinkedSeq<E>();
answer.addAll(s1);
answer.addAll(s2);
return answer;
}
/**
* Accessor method to get the current element of this sequence.
* @param - none
* @precondition:
* isCurrent() returns true.
* @return
* the current element of this sequence
* @exception IllegalStateException
* Indicates that there is no current element, so
* getCurrent may not be called.
**/
public E getCurrent( )
{
if(! isCurrent())
{
throw new IllegalStateException("No current element in the sequence");
}
return cursor.getData();
}
/**
* Accessor method to determine whether this sequence has a specified
* current element that can be retrieved with the getCurrent method.
* @param - none
* @return
* true (there is a current element)
* or false (there is no current element at the moment)
**/
public boolean isCurrent( )
{
return cursor != null;
}
/**
* Remove the current element from this sequence.
* @param - none
* @precondition:
* isCurrent() returns true.
* @postcondition:
* The current element has been removed from this sequence, and the
* following element (if there is one) is now the new current element.
* If there was no following element, then there is now no current
* element.
* @exception IllegalStateException
* Indicates that there is no current element, so
* removeCurrent may not be called.
**/
public void removeCurrent( )
{
if(!isCurrent())
{
throw new IllegalStateException("removeCurrent: isCurrent() is null");
}
if(tail == head)//only one node case
{
head = null;
tail = null;
cursor = head;
precursor = head;
manyNodes--;//update invariant
return;
}
else if(cursor == tail)//if cursor is at the last node
{
tail = precursor;
tail.setLink(null);
cursor = tail;
precursor = head;
tail = cursor;//remove last node
while(precursor.getLink() != cursor)
{//and search for a link for precursor
if(precursor.getLink() == null)
break;
precursor = precursor.getLink();
}
cursor = null;
precursor = null;
manyNodes--;//update invariant
}
else if(cursor == head)//if cursor is at first node
{
head = head.getLink();
cursor = head;
precursor = null;
manyNodes--;
}
else//regular case
{
cursor = cursor.getLink();
precursor.setLink(cursor);
manyNodes--;
}
}
/**
* Determine the number of elements in this sequence.
* @param - none
* @return
* the number of elements in this sequence
**/
public int size( )
{
return manyNodes;
}
/**
* Set the current element at the front of this sequence.
* @param - none
* @postcondition:
* The front element of this sequence is now the current element (but
* if this sequence has no elements at all, then there is no current
* element).
**/
public void start( )
{
if(head == null)//if there are no elements in the sequence
{
cursor = null;//no cursor
}
cursor = head;//move cursor to first node
precursor = null;
}
/**
* Provide a string representation of the sequence with current item
* in parentheses
* @param - none
* @postcondition string representation returned but sequence is unchanged
* @return string displaying sequence
**/
public String toString( ) // DO NOT CHANGE THIS METHOD
{
String answer = "";
Node<E> current;
for (current = head; current != null; current = current.getLink( )) {
if (current == cursor) {
answer += "(" + current.getData( ) + ") ";
} else {
answer += current.getData( ) + " ";
}
}
return answer;
}
/**
* verifyInvariant checks some of the properties of the invariant and throws an IllegalStateException if it fails.
* @exception IllegalStateException
*/
public void verifyInvariant() {
if (tail == null && head != null) {
throw new IllegalStateException("Invariant fails: Head is not null, but tail is");
}
if (head == null && tail != null) {
throw new IllegalStateException("Invariant fails: Tail is not null, but head is");
}
if (tail != null && tail.getLink() != null) {
throw new IllegalStateException("The tail node has a non-null link");
}
if (precursor == null && cursor != null && cursor != head) {
throw new IllegalStateException("Invariant fails: precursor is null, but cursor is not null and not head");
}
if (precursor != null) {
if (cursor == null) {
throw new IllegalStateException("Invariant fails: cursor is null and precursor is not");
} else if (precursor.getLink() != cursor) {
throw new IllegalStateException("Invariant fails: cursor and precursor are not null, but precursor does not link to cursor");
}
}
int count = 0;
Node<E> pred = null, curr = head;
while (curr != null && curr != cursor && curr != tail) {
pred = curr;
curr = curr.getLink();
count++;
}
if (cursor != null && cursor != curr) {
throw new IllegalStateException("Invariant fails: Cursor is not null, but not in the list");
}
if (cursor != null && pred != precursor) {
throw new IllegalStateException("Invariant fails: Precursor does not precede cursor in the list");
}
while (curr != null && curr != tail) {
curr = curr.getLink();
count++;
}
if (curr != tail) {
throw new IllegalStateException("Invariant fails: Tail is not null, but not in the list");
}
while (curr != null) {
curr = curr.getLink();
count++;
}
if (count != manyNodes) {
throw new IllegalStateException("manyNodes, " + manyNodes + ", is not equal to the length of the list, " + count);
}
}
}