import java.util.Scanner;
/**
* Implementation of homework 7.
*
* @author Cheng Yu
* @assignment ICS211 Homework TA7
* @date Mar 10, 2010
* @bugs None
*/
public class ChengJade7 {
/**
* The main entry point of the program.
*
* @param args The command line arguments (not used).
*/
public static void main(final String[] args) {
// Create a scanner to read from standard input.
final Scanner scanner = new Scanner(System.in);
// Create an array queue used to hold the data.
// final Queue<String> queue = new ArrayQueue<String>();
final Queue<String> queue = new LinkedListQueue<String>();
// Loop until the user quits.
while (true) {
// Display a menu of options.
System.out.println("You may choose one of the following options:\n");
System.out.println(" 1) 'quit' - quits the program.");
System.out.println(" 2) 'null' - adds a null String to the queue.");
System.out.println(" 3) 'poll' - polls the next String from the queue.");
System.out.println(" 4) Anything else is inserted into the queue.");
System.out.print("\nYour option: ");
System.out.flush();
// Get the command from the user.
if (!scanner.hasNextLine())
break;
final String input = scanner.nextLine();
// Check for quit command.
if (input.equals("quit"))
break;
// Check for the poll command. Poll the next String and display it in
// this case.
if (input.equals("poll")) {
System.out.println("Poll returned '" + queue.poll() + "'.");
continue;
}
// Check for the null command. Add a null String in this case.
if (input.equals("null")) {
System.out.println("Offer returned '" + queue.offer(null) + "'.");
continue;
}
// Anything else is offered to the queue.
System.out.println("Offer returned '" + queue.offer(input) + "'.");
}
// Allow the Eclipse debugger to exit happily.
System.exit(0);
}
}
/**
* An array queue, implemented with a circular buffer.
*/
class ArrayQueue<T> implements Queue<T> {
/** The maximum size of the queue. */
public static final int MAX_SIZE = 10;
/** The circular buffer. */
private final T[] myQueue = newArray(MAX_SIZE);
/** The number of items in the queue. */
private int mySize = 0;
/** A pointer to the next available element in the array for adding. */
private int myTail = 0;
/**
* Returns an array of the generic type. It is unclear if this is safe, but
* the general feeling at sun.com is that it is.
*
* @see http://forums.sun.com/thread.jspa?threadID=530823
* @return An array for the generic type.
*/
@SuppressWarnings("unchecked")
public T[] newArray(final int size) {
return (T[])(new Object[size]);
}
/**
* Returns the absolute index based on a virtual index. This simplifies the
* amount of code required to compute the index values in the circular buffer.
*
* @param virtualIndex The virtual index.
* @return The absolute index.
*/
private int at(final int virtualIndex) {
assert virtualIndex >= 0 && virtualIndex <= MAX_SIZE;
return (MAX_SIZE + myTail + virtualIndex - mySize) % MAX_SIZE;
}
/**
* Offers an item to the queue.
*
* @param value The item to add to the queue.
* @return True if the item is added and false otherwise.
*/
public boolean offer(final T value) {
// Return false if the queue is full.
if (mySize == MAX_SIZE)
return false;
// Return false if the value is null.
if (value == null)
return false;
// Loop over each item and return false if the new item already exists.
for (int i = 0; i < mySize; i++)
if (myQueue[at(i)].equals(value))
return false;
// Add the item, and update the pointer and size.
myQueue[at(mySize)] = value;
myTail = at(mySize + 1);
mySize++;
// Return true to indicate the item was added successfully.
return true;
}
/**
* Polls the queue. The first added item is removed if it exists.
*
* @return The first added item if it exists or null otherwise.
*/
public T poll() {
// Return false if there are no items in the queue.
if (mySize == 0)
return null;
// Return the item at the head of the queue, and adjust the size.
final T result = myQueue[at(0)];
mySize--;
// Return the item removed successfully.
return result;
}
}
/**
* The interface to a generic queue.
*/
interface Queue<T> {
/**
* Offers an item to the queue.
*
* @param value The item to add to the queue.
* @return True if the item is added and false otherwise.
*/
boolean offer(T value);
/**
* Polls the queue. The first added item is removed if it exists.
*
* @return The first added item if it exists or null otherwise.
*/
T poll();
}
/**
* A generic linked list class
*/
class LinkedListQueue<T> implements Queue<T> {
/** The head of the linked list. */
private Node<T> myHead;
/**
* Offers an item to the queue.
*
* @param value The item to add to the queue.
* @return True if the item is added and false otherwise.
*/
public boolean offer(final T value) {
// Do not allow null values to be added.
if (value == null)
return false;
// Add the item to the head of the list if it is the first item.
if (myHead == null) {
myHead = new Node<T>(value, myHead);
return true;
}
// Do not add if the item equals the value in the head of the linked list.
if(myHead.value().equals(value))
return false;
// Loop over each item in the linked list to see if the item already exists
// in the collection. If the item exists, return false.
Node<T> node;
for (node = myHead; node.next() != null; node = node.next())
if (node.next().value().equals(value))
return false;
// Add the item to the end of the linked list and return true.
node.setNext(new Node<T>(value, null));
return true;
}
/**
* Polls the queue. The first added item is removed if it exists.
*
* @return The first added item if it exists or null otherwise.
*/
public T poll() {
// Return null if there are no items in the linked list.
if (myHead == null)
return null;
// Return the item at the head, and remove the head.
final T result = myHead.value();
myHead = myHead.next();
return result;
}
}
/**
* A generic node class.
*/
class Node<T> {
/** A pointer to the next node */
private Node<T> myNext;
/** The value in the node. */
private final T myValue;
/**
* Initializes a new instance of the class.
*
* @param value The value stored in this node.
* @param next A pointer to the next node.
*/
public Node(final T value, final Node<T> next) {
assert null != value;
myValue = value;
myNext = next;
}
/**
* Returns the pointer to the next node.
*
* @return The pointer to the next node.
*/
public Node<T> next() {
return myNext;
}
/**
* Returns the value stored in this node.
*
* @return The value stored in this node.
*/
public T value() {
return myValue;
}
/**
* Sets the pointer to the next node.
*
* @param next The pointer to the next node.
*/
public void setNext(final Node<T> next) {
myNext = next;
}
}
