Goal 1: To design and implement a class MyDeque that will be an efficient, array-based implementation of a modified version of author's DequeInterface. The data within your MyDeque must be stored in a regular Java array (no Java classes may be used for your MyDeque data it must be a regular array). None of your DequeInterface methods should require any shifting of data within the array. I have added a couple of extra methods to the DequeInterface and changed a couple of special cases. Be sure to download the version of DequeInterface posted on the Assignments page for this project. The details of this interface are explained in the file DequeInterface.java and in Lecture 4. Review these items very carefully before implementing your MyDeque class.

Goal 2: To write a subclass of MyDeque called IndexDeque that will have no new instance data but will additionally implement the interface Indexable. The Indexable interface has 5 methods: public T getFront(int i); public T getBack(int i); public void setFront(int i, T item); public void setBack(int i, T item); public int size(); // same size() as in DequeInterface

Goal 3: To write a subclass of IndexDeque called IndexAddRemoveDeque that will have no new instance data but will additionally implement the interface IndexableAddRemove. The IndexableAddRemove interface extends Indexable and adds the following methods: public void addToFront(int i, T item); public void addToBack(int i, T item); public T removeFront(int i); public T removeBack(int i);

Implementation Details: Your MyDeque class should have the following header: public class MyDeque implements DequeInterface Your IndexDeque class should have the following header: public class IndexDeque extends MyDeque implements Indexable Your IndexAddRemoveDeque class should have the following header: public class IndexAddRemoveDeque extends IndexDeque implements IndexableAddRemove Note that each class is extending the previous one. You should not have any additional instance data in your two subclasses the only data you need should be declared in MyDeque. However, you should make the data in MyDeque protected so that it can be accessed from within your subclasses. For example, you may have the following data in MyDeque: protected T [] data; protected int front, back, N; // N is number of items Think carefully about each of the methods you are implementing. Some of them may be easy but some may be more complicated. Also think carefully about special cases. For example, adding to an empty deque may be a special case. Due to the inheritance chain of these classes, you clearly must complete them in the order that they are presented above. The array in your MyDeque class should be initialized of a specific length in a MyDeque constructor that takes an int argument: public MyDeque(int sz) This will create an array of length sz to be used for your MyDeque. If this array fills you should dynamically resize it by creating a new array of double the size, and copying the data into the new array. Be very careful with your array resizing. Because of the circular nature of your array access, you cannot just copy the data in the old array into the same locations in the new array. Think about why this is the case. The important issue is that the deque after you resize the array is logically equivalent to the deque prior to resizing. I recommend writing a protected method in class MyDeque to do the resizing. Then you can also call this method from IndexAddRemoveDeque when needed. To allow for testing and more functionality in your classes, you must also implement the following 3 methods in your MyDeque class: public MyDeque(MyDeque old) public boolean equals(MyDeque rhs) public String toString() The first method is a copy constructor, which should make a new MyDeque that is logically equivalent to the argument. The copy constructor should not be shallow the arrays should not be shared. However, it does not have to be completely deep either (you don't need to make new copies of the individual items in the deque). Note also that the copy does not have to have the same values for front and back as the original the important thing is that both contain the same data in the same relative ordering from front to back. The second method is an equals method that returns true if the deques are logically equivalent. In this case logically equivalent means that the individual items in both deques are equal() and in the same relative positions within the deques (based on front and back). However, they do not have to be located in the same index values in the arrays. The third method is a toString() method which will make a and return single String of all the data in the MyDeque from front to back and return it. This method will assume that a reasonable toString() method exists for whatever type T is being used for the MyDeque. After you have written all of your classes, test them with the following two programs: Assig1A.java this program will test the MyDeque class and its implementation of the DequeInterface. Read over the code in this program carefully so that you understand what all of the methods are doing. This program should compile and run without change using your implementation of the MyDeque class. The output should match that provided in file Assig1A-out.txt. Assig1B.java this program will test the IndexDeque and IndexAddRemove classes. Read over the code in this program carefully so that you also understand that this program is doing. This program should compile and run without change using your implementation of the IndexDeque and IndexAddRemove classes. The output should match that provided in file Assig1B-out.txt

DequeInterface.java

public interface DequeInterface { /** Adds a new entry to the front/back of this deque. @param newEntry An object to be added. */ public void addToFront(T newEntry); public void addToBack(T newEntry); /** Removes and returns the front/back entry of this deque. @return The object at the front/back of the deque. @return null if the deque is empty before the operation. */ public T removeFront(); public T removeBack(); /** Retrieves the front/back entry of this deque. @return The object at the front/back of the deque. @return null if the deque is empty. */ public T getFront(); public T getBack(); /** Detects whether this deque is empty. @return True if the deque is empty, or false otherwise. */ public boolean isEmpty(); /* Removes all entries from this deque. */ public void clear(); /** Returns number of items currently stored in the Deque. @return an int equal to the logical size of the Deque. */ public int size(); /** Returns total capacity of the Deque, counting used and unused locations. Note that this method would NOT typically be part of this interface. It was added solely for testing and grading purposes. @return an int equal to the capacity of the Deque. */ public int capacity(); } // end DequeInterface

-------------------------------------------------

Indexable.java

public interface Indexable { // Get and return the value located at logical location i from the front of the // collection, where the front position is logical index 0. If the collection // has fewer than (i+1) items, or if i < 0, throw an IndexOutOfBoundsException public T getFront(int i); // Get and return the value located at logical location i from the back of the // collection, where the back position is logical index 0. If the collection // has fewer than (i+1) items, or if i < 0, throw an IndexOutOfBoundsException public T getBack(int i); // Set the value located at logical location i from the front of the // collection, where the front position is logical index 0. If the collection // has fewer than (i+1) items, or if i < 0, throw an IndexOutOfBoundsException public void setFront(int i, T item); // Set the value located at logical location i from the back of the // collection, where the back position is logical index 0. If the collection // has fewer than (i+1) items, or if i < 0, throw an IndexOutOfBoundsException public void setBack(int i, T item); // Return the logical size of this Indexable. Note that this is the same method // that is specified in DequeInterface. It is also part of this interface so // that we can iterate through the Indexable using the interface as the reference. public int size();