(Java) ProperQueue

Files to submit

ProperQueue.java

Create this file and implement the ProperQueue class in it.

ProperQueueTests.java

Provides tests of the correctness of the above class.

5.1 A Better Queue than Last Time

We will revisit the notion of a queue that we introduced in our previous project. There will be two significant changes:

· Queues this time will be built as a class with methods called ProperQueue instead of just using an array itself as the queue. There will still be an array inside of the objects of this class but it will be better encapsulated to hide details of the implementation.

· We are storing Integer objects in the queue instead of primitive-type int values. This implies that null is a possible value in the array.

5.2 int versus Integer

The Integer type is a simple idea: sometimes, we must have an object instead of a primitive type in order to deal with references;Integer is a class that represents individual int values, while also giving us a reasonable place to write methods and to provide constants related to integers. Java has some built-in support for converting between these "boxed types" and the primitive types they mimic. We can almost leave it up to Java to implicitly convert between int and Integer when needed, except in times when different overloaded methods were written for both, as we might see in some of the unit testing code. (This is why there are some casting expressions to turn an int into an Integer). The last thing to consider about them is that, as a class type, variables that should refer to an Integer might actually store the null value. This couldn't happen with the primitive int type.

5.3 Class Structure of ProperQueue

We are borrowing some of the structure from  Java's own Queue  interface and specializing it to a class that only holds Integer values (it's not time yet for generics), and to make an initial and permanent fixed size for any particular ProperQueue object. We want to additems to a queue, we want to remove items and see what was removed, and we want to check what is the element at the head of the queue without actually removing it. But sometimes queues don't have items when we ask to remove or peek at an element; and since our queues have an unchangeable capacity, sometimes we can't add another element. Should the queue just yield null values, or raise exceptions? We will provide both versions of behavior for all three of those actions (just like our source of inspriation, Java's Queueinterface, does). We will also have some simpler functionality that should be very direct to complete.

5.4 Fields

· size: number of elements currently stored in the queue.

· private int size

· elements: an array of Integer values that stores the elements of our queue, just like last time (squashed towards the front of the array).

· private Integer[] elements

5.5 Methods

· constructor. Must initialize all instance variables. When maxCapacity isn't a positive integer, this creates a queue with zero capacity.

· public ProperQueue (int maxCapacity)

· getSize : returns how many elements are currently stored in the queue.

· public int getSize()

· getCapacity : returns the maximum number of elements that can be stored in the queue at once.

· public int getCapacity()

· isFull : indicates if the queue is currently entirely filled with elements or not.

· public boolean isFull()

· isEmpty : indicates if the queue currently holds no elements.

· public boolean isEmpty()

· toString: creates and returns a String representation of the Queue by showing each number in the queue, each separated by an individual space character, but without an extra space at the end.

· public String toString()

· add: attempts to add the element e to the end of the queue. throws a RuntimeException with the message

· "Queue full"

when the queue is full (and can't accept another item). Returns true upon successful addition of the element. Attempting to addnull to the queue raises a RuntimeException with the message

"Cannot add null"

The method prototype is:

public boolean add (Integer e)

· offer: variation of the add method that does not raise an exception when space is unavailable; it would return false instead under those circumstances.

· remove: attempts to remove the front item in the queue and return it. Raises a RuntimeException with the message

· "Queue empty"

when no item is available for removing.

public Integer remove()

· poll: variation of the remove method that does not raise an exception when no element was available for removal. It returnsnull in that circumstance.

· public Integer poll()

· element: this method will copy the front item from the queue and return it, but it does not actually remove the item from the queue (it doesn't modify the queue at all). Raises a RuntimeException with the message

· "Queue empty"

if the queue is empty.

public Integer element()

· peek: variation of the element method that will return null instead of raising an exception when no elements were present in the queue.

· public Integer peek()

5.6 Implementation Notes

As with the queues of the previous project, the intention is for ProperQueues to keep the front element at array index 0 in their internal array. On removing an element, shift all elements to lower indices.

Several methods require RuntimeExceptions to be thrown with specific messages. Review the syntax to create and raise exceptions for these situations.

The string representation of queues is slightly different than in the first project: no trailing whitespace is allowed. Observe:

> ProperQueue q = new ProperQueue(4);

> q.add(15);

> q.offer(25);

> q.add(35);

> q.toString()

"15 25 35"

You will need to structure your toString() differently from the previous project to account for this difference.

It may be worthwhile to write an internal helper method which shifts elements. This method may be utilized in both remove() andpoll() as both require similar functionality.

5.7 Sample Session

The following interactive session in DrJava demonstrates the core functionality of the ProperQueue.

Welcome to DrJava.

> ProperQueue q = new ProperQueue(5);

> q.toString()

""

> q

> q.getSize()

0

> q.getCapacity()

5

> q.isEmpty()

true

> q.isFull()

false

// add() returns true on a successful addition

> boolean result = q.add(20);

> result

true

> q.toString()

"20"

> q

20

> q.isEmpty()

false

> q.isFull()

false

> q.getSize()

1

// element() returns the first element without removing it

> q.element()

20

> q

20

// remove() returns the first element and removes it

> Integer first = q.remove();

> first

20

> q

> q.getSize()

0

// Attempting to remove() from an empty queue raises an exception

> first = q.remove();

java.lang.RuntimeException: Queue empty

at ProperQueue.remove(ProperQueue.java:140)

// Attempting to poll() an empty queue returns null

> first = q.poll();

> first

null

// add() and offer() are identical when the queue has room

> q.add(15)

true

> q.offer(25)

true

> q.add(35)

true

> q.offer(45)

true

> q.add(55)

true

// q is now full (at capacity)

> q.getSize()

5

> q.getCapacity()

5

> q.isFull()

true

// add() on a full queue raises an exception without altering the queue

> q.add(65)

java.lang.RuntimeException: Queue full

at ProperQueue.add(ProperQueue.java:91)

// offer() on a full queue returns false without altering the queue

> q.offer(65)

false

> q

15 25 35 45 55

> q.offer(65)

false

> q

15 25 35 45 55

// remove() and poll() are identical when the queue has elements

> first = q.remove()

15

> q

25 35 45 55

> first = q.poll()

25

> q

35 45 55

5.8 (20%) ProperQueue Manual Inspection Criteria   GRADING

· Methods should be short and sweet

· Provide a few comments to document sections of your code which shift elements around in methods such as poll() andremove()

· Document fields and describe how they are to used within the class

· For methods that involve special behavior for certain inputs or conditions, ensure that the special cases are clearly identified and handled prior to moving on to the general case.

· As there are quite a few methods associated with this class, make sure to organize the methods within the class.

· Document any and all methods, including helper methods, that are not part of the required public methods.