Implementation:

For this lab, implement the ADT Queue by using a circular array to contain its entries. Expand the array dynamically as necessary to make sure its capacity fits all the entries. Count entries to ascertain whether the queue is empty or full.

Your implementation should differ from the books implementation in the following ways:

Your queue must use all array elements when the array is full use the class variable countOfEntries to determine if the queue is full or empty.

You must implement clear() with O(1) efficiency you cannot use a loop to dequeue/delete entries.

You must implement the currently unimplemented methods in ArrayQueue.java. In addition, you should modify the bodies of the already-implemented methods to account for the new variable countOfEntries. When you modify how many entries are in the queue, change the variables value accordingly.

Testing:

For this lab, some JUnit tests are provided in the edu.wit.cs.comp2000.tests package. You can run these tests to see if your queue implementation is performing correctly. The tests that I have provided make sure that enqueue and isEmpty are behaving as expected.

For the rest of the provided test methods (the ones that have a STUB comment), implement a test that checks if that method works with your queue implementation. You can follow the steps that testIsEmpty takes for each test create a queue, modify it, and then assert it behaves the way you expect.

Be considerate in testing your ADT. Your goal is to test all of the possible cases for each QueueInterface method. For example, you should test dequeue at least twice when an entry is present in the queue and when it is not. Each test method may have several assert method calls depending on how many possibilities you test for.

__________________________________________________________________________________________________________

public final class ArrayQueue implements QueueInterface

{

private T[] queue; // Circular array of queue entries and one unused location

private int frontIndex;

private int backIndex;

private boolean initialized = false;

private int countOfEntries = 0;

private static final int DEFAULT_CAPACITY = 50;

private static final int MAX_CAPACITY = 10000;

public ArrayQueue()

{

this(DEFAULT_CAPACITY);

} // end default constructor

public ArrayQueue(int initialCapacity)

{

checkCapacity(initialCapacity);

// The cast is safe because the new array contains null entries

@SuppressWarnings("unchecked")

T[] tempQueue = ( T[] ) new Object[initialCapacity];

queue = tempQueue;

frontIndex = 0;

backIndex = initialCapacity - 1;

initialized = true;

} // end constructor

private void checkInitialization()

{

// STUB

} // end checkInitialization()

private void checkCapacity(int initialCapacity)

{

// STUB

} // end checkCapacity()

// Doubles the size of the array queue if it is full

// Precondition: checkInitialization has been called.

// Modified

private void ensureCapacity()

{

if (countOfEntries == queue.length) // if array is full,

{ // double size of array

T[] oldQueue = queue;

int oldSize = oldQueue.length;

int newSize = 2 * oldSize;

checkCapacity(newSize);

// The cast is safe because the new array contains null entries

@SuppressWarnings("unchecked")

T[] tempQueue = (T[]) new Object[2 * oldSize];

queue = tempQueue;

for (int index = 0; index < oldSize; index++)

{

queue[index] = oldQueue[frontIndex];

frontIndex = (frontIndex + 1) % oldSize;

} // end for

frontIndex = 0;

backIndex = oldSize - 1;

} // end if

} // end ensureCapacity()

@Override

public void enqueue(T newEntry)

{

checkInitialization();

ensureCapacity();

backIndex = (backIndex + 1) % queue.length;

queue[backIndex] = newEntry;

} // end enqueue()

@Override

public T dequeue()

{

checkInitialization();

if (isEmpty())

throw new EmptyQueueException();

else

{

T front = queue[frontIndex];

queue[frontIndex] = null;

frontIndex = (frontIndex + 1) % queue.length;

return front;

} // end if

} // end dequeue()

@Override

public T getFront()

{

// STUB

return null;

} // end getFront()

@Override

public boolean isEmpty()

{

// STUB

return false;

} // end isEmpty()

@Override

public void clear()

{

// STUB

} // end clear()

} // end class ArrayQueue

__________________________________________________________________________________________________________

public class EmptyQueueException extends RuntimeException

{

private static final long serialVersionUID = 1L;

public EmptyQueueException()

{

this(null);

} // end default constructor

public EmptyQueueException(String message)

{

super(message);

} // end constructor

} // end class EmptyQueueException

__________________________________________________________________________________________________________

public interface QueueInterface

{

/** Adds a new entry to the back of this queue.

@param newEntry An object to be added. */

public void enqueue(T newEntry);

/** Removes and returns the entry at the front of this queue.

@return The object at the front of the queue.

@throws EmptyQueueException if the queue is empty before the operation. */

public T dequeue();

/** Retrieves the entry at the front of this queue.

@return The object at the front of the queue.

@throws EmptyQueueException if the queue is empty. */

public T getFront();

/** Detects whether this queue is empty.

@return True if the queue is empty, or false otherwise. */

public boolean isEmpty();

/** Removes all entries from this queue. */

public void clear();

} // end QueueInterface

__________________________________________________________________________________________________________

import static org.junit.Assert.assertTrue;

import java.security.Permission;

import org.junit.After;

import org.junit.Before;

import org.junit.Rule;

import org.junit.Test;

import org.junit.rules.Timeout;

import edu.wit.cs.comp2000.QueueInterface;

import edu.wit.cs.comp2000.ArrayQueue;

public class LAB4Tests{

@Rule

public Timeout globalTimeout = Timeout.seconds(5);

@SuppressWarnings("serial")

private static class ExitException extends SecurityException {}

private static class NoExitSecurityManager extends SecurityManager

{

@Override

public void checkPermission(Permission perm) {}

@Override

public void checkPermission(Permission perm, Object context) {}

@Override

public void checkExit(int status) { super.checkExit(status); throw new ExitException(); }

}

@Before

public void setUp() throws Exception

{

System.setSecurityManager(new NoExitSecurityManager());

}

@After

public void tearDown() throws Exception

{

System.setSecurityManager(null);

}

/*

* enqueue does not return a value, so we check to make sure

* our implementation doesn't crash and check exceptions

*/

@Test

public void testEnqueue() {

QueueInterface testQueue = null;

testQueue = new ArrayQueue<>(3);

// check that each enqueue call is successful

for (int i = 0; i < 3; i++)

testQueue.enqueue("item " + i);

// check that enqueue works with resizing

testQueue.enqueue("resizing time");

/* exception testing pattern:

*

boolean exceptionDetected = false;

try {

queue.operation("hi");

} catch (ExceptionType e) {

exceptionDetected = true;

}

assertTrue("Performing operation in current state should throw ExceptionType", exceptionDetected);

*/

}

@Test

public void testIsEmpty() {

QueueInterface testQueue = new ArrayQueue<>();

assertTrue("Queue should start out empty", testQueue.isEmpty());

testQueue.enqueue("testing");

assertTrue("Queue should not be empty with 1 entry", !testQueue.isEmpty());

testQueue.enqueue("more testing");

assertTrue("Queue should not be empty with 2 entries", !testQueue.isEmpty());

}

@Test

public void testDequeue() {

assertTrue("Implement this test", false); // STUB

}

@Test

public void testGetFront() {

assertTrue("Implement this test", false); // STUB

}

@Test

public void testClear() {

assertTrue("Implement this test", false); // STUB

}

}