/**
 * Queues implemented with arrays using the "loop around to the first" method.
 *
 * @author Yvonne Palm
 * @author Samuel A. Rebelsky
 */
public class LoopedQueue
  implements Queue
{
  // +--------------+---------------------------------------------
  // | Design Notes |
  // +--------------+

/*

We implement queues with arrays that can "wrap around".  When we
delete elements, we update our notion of first.  When we add
elements we put them at the end.  If we reach the end, we move
around to the first.

We keep track of whether the array is full or empty (or anything
in between) with the length field, which keeps track of the number
of elements in the queue.
*/

  // +--------+---------------------------------------------------
  // | Fields |
  // +--------+

  /**
   * The index of the first element of the queue.
   */
  int first;

  /**
   * The index of the first empty space in the queue.
   */
  int back;

  /**
   * The length of the queue.
   */
  int length;
 
 /**
  * the array to be used.
  */
 Object[] queue;

  // +--------------+---------------------------------------------
  // | Constructors |
  // +--------------+

  /**
   * Create a new, empty, queue.
   */
  public LoopedQueue(){
    this.queue = new Object[5];  // All null to begin with.
    this.length = 0;
    this.first = 0;
    this.back = 0;
  } // LoopedQueue()

  // +---------+--------------------------------------------------
  // | Methods |
  // +---------+

  /**
   * Determine if the queue is empty
   */
  public boolean isEmpty() {
    return (0 == this.length);
  } // isEmpty()

  /**
   * Determine if the queue is full
   */
  public boolean isFull() {
    return (this.queue.length == this.length);
  } //isFull()

  /**
   * Add something to the queue.
   */
  public void add(Object thingToAdd){
    if (this.isEmpty()) {
      this.first = 0;
      this.back = 0;
    }
    else if(this.isFull()) {
      // Build a bigger array with more space.
      Object[] newQueue = new Object[this.length * 2];
      // Copy over the elements.
      for (int i = 0; i < this.length; i++) {
        newQueue[i] = this.queue[(this.first + i) % this.length];
      }
      // Set that to our array
      this.queue = newQueue;
      this.first = 0;
      this.back = this.length;
    }

    // We're finally ready to add the thing.  As long as we've made
    // sure that this.back is a valid index for the thing to add,
    // we're set.
    this.queue[this.back] = thingToAdd;
    // Update this.back
    this.back = this.back + 1;
    if (this.back == this.queue.length) {
      this.back = 0;
    }
    length++;
  }//add(Object)
   

  /**
   * Get the least recently added element.
   */
  public Object get(){
    // Sanity check
    if (this.isEmpty()) return null;
    // Remember the value
    Object returnValue = this.queue[this.first];
    this.queue[this.first] = null; // Just for safety
    // Advance first to the next value
    ++this.first;
    if (this.first == this.queue.length)
      this.first = 0;
    // One fewer element
    --this.length;
    // That's it.
    return returnValue;
  }//get()
 
  /**
   * Get the length.
   */
  public int length(){
    return this.length;
  }//length()

  /**
   * Get the first element (non-destructively).
   */
  public Object peek(){
    return this.queue[first];
  }//peek() 

  /**
   * Convert to a string for ease of printing.
   */
  public String toString(){
    String result = "(";
    if(this.isEmpty()) {
      return "()";
    }
    else {
      for(int i = 0; i < this.length; i++) {
        result += " " + this.queue[(i + this.first) % this.queue.length];
      } //for
    }
    return result + ")";
  } // toString()

  /**
   * Dump the thing to the screen (for debugging)
   */
  public void dump() {
    System.out.println("First: " + this.first);
    System.out.println("Back:  " + this.back);
    for (int i = 0; i < this.queue.length; i++) {
      System.out.println("A[" + i + "]: " + this.queue[i]);
    } // for
  } // dump()
} // class LoopedQueue