UnboundedArrayQueue_B

package csc143.data_structures;

/**
 * @author Vita Wiebe
 * @version PA5
 */
public class UnboundedArrayQueue implements UnboundedQueue {

   // Fields:

   // unbAQueue is our underlying array object.
   // O(n)
   Object[] unbAQueue;

   // Capacity is the number of elements that can be
   // contained in UnbAQueue in its current incarnation.
   private int capacity;

   /**
    * O(n)
    * A default constructor, creates underlying array
    * with 10 elements.
    * @param None
    */
   public UnboundedArrayQueue() {
      unbAQueue = new Object[10];
   }

   /**
    * O(n)
    * Capacity-specific constructor, creates underlying array
    * with "capacity" elements.
    * @param None
    */
   public UnboundedArrayQueue(int capacity) {
      unbAQueue = new Object[capacity];
   }

   /**
     * Add adds the object in question, o, to the queue
     * in a FIFO manner.
     * O(n^2)
     * @param Object o
     */
    public void add(Object o) {

      Object[] tempQueue;

      if(hasSpace()) {
         // New temp array.
         tempQueue = new Object[unbAQueue.length];

      }else {
         // New temp array with twice the number of elements.
         tempQueue = new Object[unbAQueue.length * 2];
      }
      // Copy all the elements from the initial array
      // to new temp array, and at 1 index value ahead of original
      // index.
      for(int i = 0; i < unbAQueue.length - 1; i++){
         tempQueue[i + 1] = unbAQueue[i];
      }

      // Assign the new element to the last index position,
      // which was the first element added.
      tempQueue[0] = o;

      // Set the new array to the inital array while disposing
      // of the inital array.
      unbAQueue = tempQueue;
    }

    /**
     * Remove removes first object added to the queue.
     * O(n^2)
     * (Elements are removed in the order they are added, FIFO).
     * @throws NullPointerException
     */
    public Object remove() {

      // New array with one less element.
      Object[] tempQueue = new Object[unbAQueue.length - 1];

      // Copy all the elements from the initial array
      // to new array.
      for(int i = 0; i < unbAQueue.length - 2; i++){
         if(unbAQueue[i] == null) {
            throw new NullPointerException();
         }else{
            tempQueue[i] = unbAQueue[i];
         }
      // Remove the element first added to the queue,
      // i.e. the last element in array.
      tempQueue[tempQueue.length - 1] = null;

      // Set the new array to the inital array while disposing
      // of the inital array.
      unbAQueue = tempQueue;
      }
      return unbAQueue;
    }

    /**
     * O(k)
     * @param None
     * @return The first element added to the queue (
     * i.e. the last element; null if empty.
     */
    public Object peek() {

      if (unbAQueue.length == 0) {
         return null;
      }else{
         return unbAQueue[unbAQueue.length - 1];
      }
    }

    /**
     * O(n^2)
     * Checks to see whether the queue has capacity to add more elements.
     * @param None
     * @return boolean
     */
    public boolean hasSpace() {

      for (int i=0; i < unbAQueue.length; i++){
         if (unbAQueue[i] == null) {
            return true;
         }
      }
      return false;
    }

    /**
     * O(n^2)
     * Checks to see whether the queue has had any elements added to it.
     * @param None
     * @return boolean
     */
    public boolean hasContents() {

      for (int i = 0; i < unbAQueue.length; i++){
         if(unbAQueue[i] != null) {
            return true;
         }
      }
      return false;
    }

    /**
     * O(n^2)
     * @param None
     * @return The number of elements that are currently stored in the structure.
     */
    public int size() {

      // Tracks the number of elements that aren't null (empty).
      int count = 0;

      for(int i = 0; i < unbAQueue.length; i++) {
         if(unbAQueue[i] != null){
            count++;
         }
      }
      return count;
    }

}