/**
* Implementation of the Queue interface using an array
* Invariants of the class are formally specified
* Assertions are used to ensure that the invariants and contracts hold at run time
* Test cases are are designed and implemented for unit testing using JUnit
* Algorthm is taken from the book:
* Michael Goodrich and Roberto Tamassia, "Algorithm Design: Foundations,
* Analysis, and Internet Examples", Wiley, 2002. (ISBN 0-471-38365-1)
* pages 61-62
* Queue is implemented in a circular view in an array 
* To prevent getting out of bounds (the N = 100 length of an array is set)
* we insisit that queue can never hold more than (N-1) objects
* author Alex Rudniy
*/

/**
* @invariant _wellformed()
*/
public class MyArrayQueue implements ArrayQueue  {
  
  //constructor
  public MyArrayQueue() {
    anArray = new Object[N];
	front = 0;
	rear = 0;
	assert _wellformed();
  }

  //accessors
  //returns the size of the queue
  public int size() {
    int size;
    size = ((N - front + rear) % N);
    return size;
  }

  //reurns the first element
  public Object first() {
     assert size() > 0;
	 Object first = anArray[front];
	 return first;
  }

  //returns the last element
  public Object last() {
    assert size() > 0;
    Object last = anArray[rear];
	return last;
  }
  
  //mutators
  //add element to the rear of the queue
  public void enqueue(Object item) {
    assert size() < N;
    assert _wellformed();
	int size_pre = size();
    if (size() < N - 1) {
      anArray[rear] = item;
	  rear = (rear + 1) % N;
    }
	assert size() == size_pre + 1;
    assert _wellformed();
  }
  
  // remove the first element
  public Object dequeue() {
	assert size() > 0;
    assert _wellformed();
	int size_pre = size();
    Object temp;
	if (size() > 0) {
      temp = anArray[front];
	  front = (front + 1) % N;
    } else {
      temp = "Error! Size of the queue should be less than " + N;  
    }
	
	assert size() == size_pre - 1;
	assert _wellformed();
	return temp;
  }

  //invariant
  protected boolean _wellformed() {
    if (size() == 0) {
      if (front != rear) {
        return false; // if there are no elements in the queue,
		              // front should be equal to rear
      }        
    } else {
      if (size() > (N-1)) {
        return false; //the number of elements in the queue should be less than N
      }  
    }
	int n = 0;
	for (int i = front; i != rear; i++) {
	  n++;  
	}
	return n == size();
  }


  //fields
  private final int N = 100;//number of elements in the array
  private Object[] anArray;	// an array to store the queue
  private int front;		//an index to the cell of anArray storing the first element
  private int rear;			//an index to the next available array cell in anArray
}