COP 3530
  Data Structures
  Section U03
  M, W : 7:50PM - 9:05PM
  ECS 132

                          A PROGRAM FOR HW #1
                          ===================


  I. The CircularQueue
  --------------------


  import java.util.NoSuchElementException;

  public class CircularQueue<T> implements Queue<T>
  {

        // Instance fields and constants
        private T[] data; // the data array that makes up the queue
        private int f; // first element in the queue
        private int r; // last element in the queue
        private int size; // the size of the queue
        private static final int INITIAL_SIZE = 3; // default initial size of queue

        // Constructors

        // construct a queue with a given size
        public CircularQueue(int queueSize)
        {
            data = (T[]) new Object[queueSize];
            // Since the queue is empty ...
            size = 0;
        }

        // create a queue with the default value
        public CircularQueue()
        {
            this(INITIAL_SIZE);
        }

        // add an item to the queue
        public void add(T item)
        {
            // if the queue is empty
            if (size == 0)
            {
               r = f = 0;
            }
            else // the queue is not empty
            {
                if (size == data.length)
                {
                    // the queue is full, double the array
                    T[] newData = (T[]) new Object[2*data.length];
                    // copy the contents of data onto newData
                    System.arraycopy(data,f,newData,0, data.length - f);
                    System.arraycopy(data, 0, newData, data.length -f, f);

                    // set data to new data and update f and r
                    data = newData;
                    f = 0;
                    r = size;
                }
                else // no overflow
                    r = (r + 1) % data.length;
            }

            // enter item and update the size
            data[r] = item;
            size++;
        }


        // remove the first item in the queue.
        // throw a no such element exception if the queue is empty
        //
        public T remove()
        {
            T removedItem;
            if (isEmpty())
                throw new NoSuchElementException();
            // remove the first item
            removedItem = data[f];
            f = (f + 1) % data.length;
            size--;
            return removedItem;
        }


        // Gets the first element in the queue provided that the queue is not
        // empty. If it is, then a NoSuchElementException is thrown.
        // @return the first element in the queue
        //

        public T getFirst()
        {
            if (isEmpty())
                throw new NoSuchElementException();
            return data[f];
        }

        // return the size of the queue
        public int getSize()
        {
            return size;
        }


        // Returns true if the queue has no elements or false otherwise.
        public boolean isEmpty()
        {
            return size == 0;
        }



        // Empties the queue.
        public void clear()
        {
            size = 0;
        }

        // Returns the size, the front, the rear and the elements of the queue,
        // from the first element to the last one.
        public void display()
        {

             System.out.println("\nsize = " + size + ", f = " + f + ", r = " + r);
             System.out.println("The array capacity is " + data.length);
             // print the contents of the queue

             if (isEmpty())
                System.out.println( "The queue is empty.");
             else
             {
                if (f <= r)
                   for (int i = f; i <= r; i++)
                       System.out.println("queue[" + i + "] = " + data[i]);
                else
                {
                   for (int i = f; i < data.length; i++)
                       System.out.println("queue[" + i + "] = " + data[i]);
                   for (int i = 0; i <= r; i++)
                       System.out.println("queue[" + i + "] = " + data[i]);
                 }
             }
         } // end method
  }

  II. The Driver
  --------------

  import java.util.NoSuchElementException;

  public class Spring16cop3530TestHw1 
  {  
    
     public static void main(String[] args) 
     {
        System.out.println("Testing Queues");
        System.out.println("==============\n\n\n");

        // add 5 numbers
        System.out.println("We form a queue with the integers 1,2,3,4,5.");
        CircularQueue<Integer> numbers = new CircularQueue<>();
        numbers.add(1);
        numbers.add(2);
        numbers.add(3);
        numbers.add(4);
        numbers.add(5);
        
        System.out.println("\nWe print the queue");
        numbers.display();
        System.out.println("We delete 2 numbers.");
        int n = numbers.remove();
        int m = numbers.remove();
        System.out.println("We removed " + n + " and " + m + " in this order.");
        System.out.println("\nWe print the queue");
        numbers.display();
        
        // add 3 more numbers
        System.out.println("\nWe add the numbers 6, 7, 8 to the queue.");
        numbers.add(6);
        numbers.add(7);
        numbers.add(8);
        System.out.println("\nWe print the queue");
        numbers.display();
        
        // add 2 more numbers, 9 and 10
        System.out.println("\nWe add 2 more numbers, 9 and 10, to the queue.");
        numbers.add(9);
        numbers.add(10);
        System.out.println("\nWe print the queue");
        numbers.display();
        
        // test getFirst and getSize
        System.out.println("The first item is " + numbers.getFirst() + ".");
        System.out.println("The queue has " + numbers.getSize() + " numbers.");
        System.out.println("The queue is empty is " + numbers.isEmpty() + ".");
        System.out.println("\nWe print the queue");
        numbers.display();
        
        // clear the queue and attemp to use getFirst and remove
        System.out.println("We clear the queue.");
        numbers.clear();
        System.out.println("\nWe print the queue");
        numbers.display();
        
        // attempt to remove an item
        try
        {
            System.out.println("We attempt to remove a number.");
            int p = numbers.remove();
            System.out.println("We removed " + p + ".");
        }
        catch(NoSuchElementException e)
        {
            System.out.println("We got a no such element exception.");
        }    
        
        // attempt to remove getFirst
        try
        {
            System.out.println("We attempt to see the first  number.");
            int p = numbers.getFirst();
            System.out.println("The first number is " + p + ".");
        }
        catch(NoSuchElementException e)
        {
            System.out.println("We got a no such element exception.");
        }    
        
        System.out.println("The queue is empty is " + numbers.isEmpty() + ".");
        System.out.println("\nWe print the queue");
        numbers.display();
        
     }    
    
  }  


  III. The Output:
  ----------------

  run:
  Testing Queues
  ==============



  We form a queue with the integers 1,2,3,4,5.

  We print the queue

  size = 5, f = 0, r = 4
  The array capacity is 6
  queue[0] = 1
  queue[1] = 2
  queue[2] = 3
  queue[3] = 4
  queue[4] = 5
  We delete 2 numbers.
  We removed 1 and 2 in this order.

  We print the queue

  size = 3, f = 2, r = 4
  The array capacity is 6
  queue[2] = 3
  queue[3] = 4
  queue[4] = 5

  We add the numbers 6, 7, 8 to the queue.

  We print the queue

  size = 6, f = 2, r = 1
  The array capacity is 6
  queue[2] = 3
  queue[3] = 4
  queue[4] = 5
  queue[5] = 6
  queue[0] = 7
  queue[1] = 8

  We add 2 more numbers, 9 and 10, to the queue.

  We print the queue

  size = 8, f = 0, r = 7
  The array capacity is 12
  queue[0] = 3
  queue[1] = 4
  queue[2] = 5
  queue[3] = 6
  queue[4] = 7
  queue[5] = 8
  queue[6] = 9
  queue[7] = 10
  The first item is 3.
  The queue has 8 numbers.
  The queue is empty is false.

  We print the queue

  size = 8, f = 0, r = 7
  The array capacity is 12
  queue[0] = 3
  queue[1] = 4
  queue[2] = 5
  queue[3] = 6
  queue[4] = 7
  queue[5] = 8
  queue[6] = 9
  queue[7] = 10
  We clear the queue.

  We print the queue

  size = 0, f = 0, r = 7
  The array capacity is 12
  The queue is empty.
  We attempt to remove a number.
  We got a no such element exception.
  We attempt to see the first  number.
  We got a no such element exception.
  The queue is empty is true.

  We print the queue

  size = 0, f = 0, r = 7
  The array capacity is 12
  The queue is empty.
  BUILD SUCCESSFUL (total time: 0 seconds)