Class ResizingArrayQueue<E>

java.lang.Object

AQueue<E>

ArrayQueue<E>

ResizingArrayQueue<E>

Type Parameters:

E - the type of the elements in the queue

All Implemented Interfaces:

IQueue<E>

public class ResizingArrayQueue<E>
extends ArrayQueue<E>
implements IQueue<E>

ResizingArrayQueue is a modification to ArrayQueue that is space efficient at various sizes.

A plain ArrayQueue may have a maximum capacity of 1000, but many times it will only use a fraction of that space. Or it may use that entire space for a period of time, but will then drain down to a much smaller number of elements.

A ResizingArrayQueue will dynamically resize as it is used so that it does not waste space. Hence you can have a queue of max capacity 1000, but not pay for that storage unless required. Further, if the queue grows to that max capacity, but then drains down to a much smaller size, a smaller array will be used, reclaiming the extra space not being used by the too-large array.

The trick with all of this is to do it efficiently, so that it is only slightly slower than ArrayQueue.

by cspfrederick and garethhalladay Fall17
inspired by Chris Wilcox

Field Summary

Fields

Modifier and Type	Field and Description
(package private) int	maxSize the maximum size of the queue.
(package private) int	minSize the minimum size that the queue can shrink to.

Fields inherited from class ArrayQueue

added, elements, removed

Constructor Summary

Constructors

Constructor and Description
ResizingArrayQueue(int minSize, int maxSize) Create a new queue with the given constraints on size.

Method Summary

Modifier and Type	Method and Description
static void	main(java.lang.String[] args)
boolean	offer(E e) Adds an element to the queue.
E	poll() Removes the oldest element from the queue.
protected void	resizeArrayTo(int newSize) Replaces the current elements array with an array of size newSize.

Methods inherited from class ArrayQueue

clear, contains, newArray, peek, size

Methods inherited from class AQueue

add, element, isEmpty, remove

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface IQueue

add, clear, contains, element, isEmpty, peek, remove, size, toString

Field Detail

maxSize

final int maxSize

the maximum size of the queue.

minSize

final int minSize

the minimum size that the queue can shrink to.

Constructor Detail

ResizingArrayQueue

public ResizingArrayQueue(int minSize,
                          int maxSize)

Create a new queue with the given constraints on size.

Parameters:

minSize - the minimum size of the queue

maxSize - the maximum size of the queue

Method Detail

resizeArrayTo

protected void resizeArrayTo(int newSize)

Replaces the current elements array with an array of size newSize. All the old elements are mapped to their proper locations in the new array.

First, check that newSize is greater than or equal to ArrayQueue.size(), throw a new RuntimeException if the new size would not hold all the elements.
Next, use ArrayQueue.newArray(int) to create an array of the appropriate size.
Then use a for loop that ranges from ArrayQueue.removed to ArrayQueue.added, and assign values from the old array into the new array.

If the loop variable is i, then the element at elements[i % elements.length] belongs at new_elements[i % new_elements.length]. After copying over all the elements, assign ArrayQueue.elements to be the newly created array.

Parameters:

newSize - the new size for the backing array

Throws:

java.lang.RuntimeException - if newSize is less than the current queue size

offer

public boolean offer(E e)

Adds an element to the queue.
If the queue is at maximum capacity, return false.
If the array is full, grow it by calling resizeArrayTo(int) with either double the length of the current array or maxSize, whichever is smaller.

Whether you had to resize or not, now add the new element in the usual way. Don't forget to increment added.

Specified by:

offer in interface IQueue<E>

Overrides:

offer in class ArrayQueue<E>

Parameters:

e - the element to be added to the queue

Returns:

true if the element was added, false otherwise.

See Also:

ArrayQueue.added

poll

public E poll()

Removes the oldest element from the queue.
If the queue is empty, return null.
Store the oldest element in the queue in a local variable. Increment the removed variable.

If the size of the queue is less than a quarter of the length of the array, and the array is not already at the minimum size, then it is time to shrink the array. Call resizeArrayTo(int) with either half the length of the current array or minSize, whichever is larger.

Specified by:

poll in interface IQueue<E>

Overrides:

poll in class ArrayQueue<E>

Returns:

the item that was removed or null if the queue is empty

See Also:

ArrayQueue.removed

main

public static void main(java.lang.String[] args)