ChengJade7.java

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;
  }
}
 
Valid HTML 4.01 Valid CSS