Waiting Array

The objective of this project is to implement a simple container data structure that can store different kinds of elemnets at different times. The data structure follows a specific ordering of elements in its operations.

Overview:

1. Define the interfaces WaitingArrayInterface .

2. Define classes WaitingLoopArrayImpl and VIPWaitingArrayImpl .

3. Define an Exception EmptyWaitingArrayException and use it whenever necessary.

4. Download and use the tester module to ensure that your program is correct.

In this project, you will develop a simple data structure that stores elements according to a specific order. The data structure has one entry point (called entry) and one exit point (called exit). The WaitingArrayInterface specifies the operations supported by the data structure. A waiting array has two indices that indicate the entry and exit points, called entryIndex and exitIndex , respectively. The element can only be added via the entry and can only be removed through the exit. The elements are removed based on the order of their addition; the first one to be added is the first one to be removed from the waiting array. For example, a WaitingLoopArrayImpl can be used in a scenario where you went for an internship interview. You can enter the interview room , according to your turn, through one door and leave the interview via another door.

RULES

1. You may import Java built-in libraries.

2. All data fields should be declared private or protected

3. You may add your own helper methods or data fields, but they should be private or protected . You may add additional constructors which are public.

4. Use of @Override tags on overridden methods is not required but is strongly recommended.

5. When commenting code, use JavaDoc-style comments.

INTERFACE TASK:

Define a generic interface WaitingArrayInterface . The interface has the following generic methods (include the data types where needed):

• void add(element) : Adds an element in the data structure.
• remove() throws EmptyWaitingArrayException removes an element. If the the data structure is empty, it will throw EmptyWaitingArrayException .
• void clear() throws EmptyWaitingArrayException removes all elements in the data structure. If the the data structure is empty, it will throw EmptyWaitingArrayException
• getFirst() throws EmptyWaitingArrayException returns the first element currently waiting in the data structure (i.e., the first elemnet added in the data structure). If the data structure is empty, it will throw EmptyWaitingArrayException
• getLast() throws EmptyWaitingArrayException returns the last element currently waiting in the the data structure (i.e., the last element to be added in the data structure). If the data structure is empty, it will throw EmptyWaitingArrayException
• public boolean isEmpty() returns true if the data structure is empty, false otherwise.
• public boolean isFull() returns true if the data structure is full, false otherwise.
• public String toString()

Note: you need to define your own EmptyWaitingArrayException exception.

CLASS TASK :

Now, lets implement the waiting array using a special kind of array, called Loop array, as an undelying storage structure. A loop array is a first-in-first-out array which has a first index (also the exit index) and a last index, which move as elements are removed or added, respectively. The first index follows the last one initially. The two indices indicate the two ends of loop array, where entryIndex indicates the spot where the most recent new element was added (which is also the current last element), and exitIndex marks the spot of the first element (and thus the location of the first element to be removed from the list). In order to make the data structure efficient, loop array does not shift elements like ArrayList would during add and remove operations. Instead, for each add and remove operation, one of the two indices will be incremented. Accordingly, for each removal, instead of shifting the rest of elements of the array, a loop array's exitIndex will be incremented by one and for each addition, entryIndex will be incremented by one as well. If either of the indices reach the end of the array ( length - 1 ), it will wrap around and start from the beginning. The loop array will leave one space unused to make the detection of empty vs. full simpler. Consider the following loop array of size 9 (i.e., with one unused space, this loop array can store a maximum of 8 elemenets). Initially, the loop array is empty where exitIndex is the first index (0) and the entryIndex is the last index (8). In the case that an element needs to be added to a waiting array which is already full, it should resize itself to fit new elements.

Simulation example: see image.

Define a class called WaitingLoopArrayImpl that implements WaitingArrayInterface using the loop array that is discussed above. WaitingLoopArrayImpl has the following attributes:

• int entryIndex
• int exitIndex
• loopArray : some kind of array of elements that can store generic elements. This array will behave like the loop array we discussed earlier.

Note: generic is a perfect fit for WaitingLoopArrayImpl .

• int initialCapacity : the initial storage capacity of the WaitingLoopArrayImpl (the size of the loop array), which is 100 in the default case.
• public WaitingLoopArrayImpl() A constructor which creates the WaitingArray with the default initial capacity.
• public WaitingLoopArrayImpl(int capacity) A constructor which with creates the WaitingLoopArrayImpl with length of capacity .
• private void resizeCapacity() double the size of WaitingLoopArrayImpl if it is full. The already existing elments should not be lost during the resizing, however some elements might need to be moved and index(es) changed to complete the process successfully.
• @Override public String toString() Returns the WaitingLoopArrayImpl elements in a specific format. For example, if the elements in the WatingLoopArrayImpl are Bill , Adam , and Caroll in that order, toString() will return " [Bill,Adam,Caroll] ". If the data structure is empty, it returns " [] ".

VIPWaitingArrayImpl

Define a datastructure called VIPWaitingArrayImpl that implements WaitingArrayInterface using some kind of array as an underlying storage structure. The remove operation will always remove the first element in the array (i.e., at index 0). This will require the shifting of the rest of the elements one location to the left in order to make the next first element to be removed at index 0. Do not use a built-in method such as ArrayList 's remove method to do this task for you (this will be verified manually). Moreover, we will now require the elements of VIPWaitingArrayImpl to have an ordering that will be reflected in the way the add method is implemented. Elements must be added such that smaller elements (based on their natural ordering) appear first. For example, assume the elements in the VIPWatingArrayImpl are Adam , Bill , and Caroll, with Adam to be processed (removed) first. If we add a new element, Abel , the elements in VIPWatingArrayImpl are now Abel , Adam , Bill , then Caroll in that order, and Abel will be the first to be processed. Note the acending order of elements and each addition should keep this ordering intact (Hint: using Comparable is recommended).

The VIPWaitingArrayImpl has the following attributes:

• int entryIndex : keeps track of the index of the last element added. The initial empty VIPWaitingArrayImpl has a -1 value for entryIndex (Note: there is no need to use an exitIndex as it would always be index 0).
• loopArray array of elements that can store any kind of elements.

Note: generic is a perfect fit for VIPWaitingArrayImpl

• int initialCapacity : the initial strorage capacity of the VIPWaitingArrayImpl , which is 100 in the default case.
• public VIPWaitingArrayImpl() A constructor which creates the VIPWaitingArrayImpl with the default initial capacity.
• public VIPWaitingArrayImpl(int capacity) A constructor which with creates the VIPWaitingArrayImpl with capacity.
• private void resizeCapacity() double the size of VIPWaitingArrayImpl if it is full. The already existing elments should not be lost during the resizing.
• @Override public String toString() Returns the WaitingArrayImpl elements in a specific format. For example, if the elements in the VIPWatingArrayImpl are Adam , Bill , and Caroll , toString() will return " [Adam,Bill,Caroll] ". If the data structure is empty, it reurns " [] ".