/* DequeViaArray.java
** An instance of this class represents a deque ("Double Ended QUEue"),
** which combines the capabilities of a stack and a queue.  That is, in 
** a deque, elements can be inserted at both the front and the rear, and 
** likewise removed from both the front and the rear.  Only the elements 
** at the front and at the rear can be retrieved.
**
** A wrap-around array representation is employed.
**
** Authors: R. McCloskey and < STUDENTS' names >
** Date: October 2025
*/
public class DequeViaArray<T> implements Deque<T> {

   // instance variables
   // ------------------

   private T[] contents;  // holds the items occupying this deque
   private int numItems;  // how many items occupy this deque
   private int frontLoc;  // location in contents[] where the deque's
                          // front element is stored


   // constructor
   // -----------

   /* Initializes this deque to be empty and to have the specifed capacity.
   ** An attempt to place more items into this deque when it is filled to
   ** capacity will be ignored.
   ** pre: capacity > 0
   */
   public DequeViaArray(int capacity) {
      contents = (T[])(new Object[capacity]);
      numItems = 0;
      frontLoc = 0;
   }

   // observers
   // ---------

   /* Reports whether or not this deque is empty (i.e. has no elements in it).
   */
   public boolean isEmpty() { return sizeOf() == 0; }

   /* Reports whether or not this deque is full, meaning that an attempt
   ** to insert an item may fail.
   */
   public boolean isFull() { return sizeOf() == contents.length; }

   /* Reports how many items occupy this deque.
   */
   public int sizeOf() { return numItems; }

   /* Returns (a reference to) the item at the front of this deque.
   ** pre: !isEmpty()
   */
   public T frontOf() { 
      return contents[frontLoc];
   }

   /* Returns (a reference to) the item at the rear of this deque.
   ** pre: !isEmpty()
   */
   public T rearOf() {       // STUB
      return contents[-1];   //Clearly -1 isn't right!
   }

   /* Returns a list of the (images of the) items in the deque, 
   ** going from front to rear, enclosed in square brackets.
   */
   public String toString() {
      StringBuilder result = new StringBuilder("[ ");
      int k = frontLoc;
      for (int i=0; i != numItems; i++) {
         result.append(contents[k] + " ");
         k = successorLoc(k);
      }
      result.append(']');
      return result.toString();
   }


   // mutators
   // --------

   /* Removes the item at the front of this deque.
   ** pre: !isEmpty()
   */
   public void removeFront() {  
      // The following statement is not necessary, but it may aid 
      // "garbage collection" to ensure that every logically meaningless
      // array element has 'null' in it.
      contents[frontLoc] = null; 
      
      frontLoc = successorLoc(frontLoc);
      numItems--;
   }

   /* Removes the item at the rear of this deque.
   ** pre: !isEmpty()
   */
   public void removeRear() {   // STUB
      // The following statement is not necessary, but it may aid 
      // "garbage collection" to ensure that every logically meaningless
      // array element has 'null' in it.
      contents[rearLoc()] = null; 

      // CODE NEEDED HERE (to change value of one instance variable )

   }

   /* Inserts the specified item at the front of this deque.
   */
   public void insertAtFront(T elem) {
      if (isFull()) {
         // In case this deque is full, do nothing (except print a warning).
         System.out.println("WARNING: deque is full, so no insertion can occur.");
      }          
      else if (isEmpty()) {
         // use method designed for inserting when this deque is empty
         insertWhenEmpty(elem);
      }
      else {
         // STUB  (code needed here)
      }
   }

   /* Inserts the specified item at the rear of this deque.
   */
   public void insertAtRear(T elem) {  // STUB!
      if (isFull()) { 
         // In case this deque is full, do nothing (except print a warning).
         System.out.println("WARNING: deque is full, so no insertion can occur.");
      }
      else if (isEmpty()) {
         // use method designed for inserting when this deque is empty
         insertWhenEmpty(elem);
      }
      else {
         // MISSING CODE
      }
   }

   // private utility methods   (USE THEM!!!!)
   // -----------------------

   /* Inserts the specified element into this deque, assumed to be empty.
   ** pre: isEmpty()
   */ 
   private void insertWhenEmpty(T elem) {
      contents[frontLoc] = elem;
      numItems = 1;
   }

   /* Returns the location within contents[] at which the rear item 
   ** in the deque is stored.
   ** pre: !isEmpty()
   */
   private int rearLoc() { 
      return (frontLoc + numItems - 1) % contents.length;
   }


   /* Returns the location (within contents[], interpreted to be a
   ** circular/wraparound structure) that immediately follows location k
   */
   private int successorLoc(int k) { 
      // STUB
      return k+1;  // This is sometimes WRONG!!
   }

   /* Returns the location (within contents[], interpreted to be a
   ** circular/wraparound structure) that immediately precedes location k
   */
   private int predecessorLoc(int k) { 
      // STUB
      return k-1;  // This is sometimes WRONG!!
   }

}