CpSc 210, Section 1
                            Assignment #6
                           March 30, 2003


Due:  Wednesday, April 9, at 11:59 p.m.  

The intent of this assignment is to demonstrate inheritance in Java.
The instance variables and methods of QueueArray are inherited by
ArrayList.  The List interface provides another type of inheritance --
inheritance of a required set of method signatures.  All methods should
work as the List interface describes that they work (pp. 99 - 100).


Assignment:  Another data structure for lists will be built on Bailey's
circular array implementation, named QueueArray.  ArrayList will be an
extension of QueueArray and will implement the List methods.  The
header for the class will be:

import structure.List;
import structure.Iterator;
Import structure.QueueArray;
public class ArrayList extends QueueArray implements List
{
   private static final int INITIAL_ARRAY_SIZE = 5;

   public ArrayList ( )
   {
      super ( INITIAL_ARRAY_SIZE );
   }


Total point value of assignment:  100 points
Not accepted late.

This assignment is to be done INDIVIDUALLY.

    The defaultSize of the array is to be 5 (five)
    Use "private static final int INITIAL_ARRAY_SIZE = 5;"

    The method "private void resize()" is to be called only when
    the array becomes full, that is, when isFull() returns true.
    Note the resize method must be private. The worst case time
    complexity of resize() is O(count), where count is the number
    of items in the list.

    The following methods must have time complexity O(1) when
    the method isFull() returns false.  (Use the isFull() method
    in the QueueArray class.)

        public void add ( Object value ) 
        public void addToHead ( Object value )
        public void addToTail ( Object value )

    The following methods must have worst case time complexity O(1):

        public Object peek ( ) 
        public Object tailPeek ( )
        public Object removeFromHead ( )
        public Object removeFromTail ( )
        public int size()
        public boolean isEmpty()
        public void clear()

    The following methods have worst case time complexity O(count).

        public boolean contains ( Object value )
        public Object remove ( Object value )
        public String toString ( )
        public boolean equals ( Object other )
        private void resize ( )

	The equals method requires that this and other contain equal
	Objects in the same order.  The equals method does NOT require that
	subscript [k] of this contain an Object equal to subscript [k] of other.
	The resize method should double the size of the array and make any other
	necessary changes to the instance variables.

     Use the following elements method on this assignment:

     public Iterator elements()
     // post: returns an iterator allowing ordered traversal of elements in List
     {
         return null;
     }


     The following QueueArray methods must be disabled because they are
     not List methods:

        public void enqueue ( Object value );
        public Object dequeue ( );

     If you do not disable these methods and an application program
     attempts to invoke either of them with an ArrayList the corresponding
     method in the base class will be invoked.  You will handle both of
     these exceptions by printing a message to the user that the called
     method is not implemented in the List interface.  The dequeue method
     method must also return a null Object.


Grading Rubric:

	10 points:  ArrayList class that compiles without error submitted by 
	11:59 p.m. Friday night, April 4.  (Not expected to be complete.)

 	Required that all methods are of correct complexity and all methods
	are as specified.

	You must use our specification that the default size of the array is 5.
	You must be careful NOT to call resize unless isFull() returns true.

	Also, the ONLY method that copies the entire array is resize().
	The remove method should only shift a section of the list, either
	from the removePosition toward the head or from the removePosition
	toward the end (tail) of the list.  The remove method should not
	make a copy of the entire list.

 	Make use of QueueArray methods when doing so does not compromise
	time complexity.  

	Code must be correct.  Elegance of code matters, also.