// File: DoubleLinkedQueue.java from the package edu.colorado.collections
// Complete documentation is available from the DoubleLinkedQueue link in:
// http://www.cs.colorado.edu/~main/docs/
package edu.colorado.collections;
import java.util.NoSuchElementException;
import edu.colorado.nodes.DoubleNode;
/******************************************************************************
* A DoubleLinkedQueue
is a queue of double values.
*
* Limitations:
* Beyond Int.MAX_VALUE
items, size
is wrong.
*
* Java Source Code for this class:
*
* http://www.cs.colorado.edu/~main/edu/colorado/collections/DoubleLinkedQueue.java
*
*
* @author Michael Main
* (main@colorado.edu)
*
* @version Feb 10, 2016
*
* @see DoubleQueue
* @see ObjectLinkedQueue
* @see BooleanLinkedQueue
* @see ByteLinkedQueue
* @see CharLinkedQueue
* @see FloatLinkedQueue
* @see IntLinkedQueue
* @see LongLinkedQueue
* @see ShortLinkedQueue
******************************************************************************/
public class DoubleLinkedQueue implements Cloneable
{
// Invariant of the DoubleLinkedQueue class:
// 1. The number of items in the queue is stored in the instance variable
// manyNodes.
// 2. The items in the queue are stored in a linked list, with the front
// of the queue stored at the head node, and the rear of the queue at
// the final node.
// 3. For a non-empty queue, the instance variable front is the head
// reference of the linked list of items and the instance variable rear
// is the tail reference of the linked list. For an empty queue, both
// front and rear are the null reference.
private int manyNodes;
DoubleNode front;
DoubleNode rear;
/**
* Initialize an empty queue.
* Postcondition:
* This queue is empty.
**/
public DoubleLinkedQueue( )
{
front = null;
rear = null;
}
/**
* Generate a copy of this queue.
* @return
* The return value is a copy of this queue. Subsequent changes to the
* copy will not affect the original, nor vice versa. Note that the return
* value must be type cast to an DoubleLinkedQueue
before it can be used.
* @exception OutOfMemoryError
* Indicates insufficient memory for creating the clone.
**/
public Object clone( )
{ // Clone an DoubleLinkedQueue.
DoubleLinkedQueue answer;
DoubleNode[ ] cloneInfo;
try
{
answer = (DoubleLinkedQueue) super.clone( );
}
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 comon error
// 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");
}
cloneInfo = DoubleNode.listCopyWithTail(front);
answer.front = cloneInfo[0];
answer.rear = cloneInfo[1];
return answer;
}
/**
* Get the front item, removing it from this queue.
* Precondition:
* This queue is not empty.
* @return
* The return value is the front item of this queue, and the item has
* been removed.
* @exception NoSuchElementException
* Indicates that this queue is empty.
**/
public double getFront( )
{
double answer;
if (manyNodes == 0)
// NoSuchElementException is from java.util and its constructor has no argument.
throw new NoSuchElementException("Queue underflow");
answer = front.getData( );
front = front.getLink( );
manyNodes--;
if (manyNodes == 0)
rear = null;
return answer;
}
/**
* Put a new a new item in this queue.
* @param item
* the item to be pushed onto this queue
* Postcondition:
* The item has been pushed onto this queue.
* @exception OutOfMemoryError
* Indicates insufficient memory for increasing the queue's capacity.
* Note:
* An attempt to increase the capacity beyond
* Integer.MAX_VALUE
will cause the queue to fail with an
* arithmetic overflow.
**/
public void insert(double item)
{
if (isEmpty( ))
{ // Insert first item.
front = new DoubleNode(item, null);
rear = front;
}
else
{ // Insert an item that is not the first.
rear.addNodeAfter(item);
rear = rear.getLink( );
}
manyNodes++;
}
/**
* Determine whether this queue is empty.
* @return
* true
if this queue is empty;
* false
otherwise.
**/
public boolean isEmpty( )
{
return (manyNodes == 0);
}
/**
* Accessor method to determine the number of items in this queue.
* @return
* the number of items in this queue
**/
public int size( )
{
return manyNodes;
}
}