The end of the code:
/**
* A flexible queue backed with an array, that resizes if needed.
* This implementation is synchronized.
*
* Let capacity = _content.length.
* Let _endIndex = (_end - 1 + capacity) % capacity
*
* _content[_start] is the start
* _content[_endIndex] is the end
*
* if _start <= _end,
* _content[_start .. _endIndex] contains the Objects in the order they were
* inserted, and _size = _end - _start.
* if _start > _end,
* _content[_start .. _content.length - 1, 0 .. _endIndex] contains the Objects in
* the order they were inserted, and _size = _end - _start + capacity.
*
* Adapted from http://www.cs.toronto.edu/~jepson/148/general/exercises/src/RubberBandQueue/RubberBandQueue.java
*
* @author genepi
* @created May 29, 2003
*/
class FlexibleQueue
{
/**
* The initial number of elements this queue can hold,
*/
private final int _initialSize;
/**
* The increment.
*/
private final int _increment;
/**
* The index of the start of the queue.
*/
private int _start = 0;
/**
* The index of the end of the queue.
*/
private int _end = 0;
/**
* The number of elements in me.
*/
private int _size = 0;
/**
* The items stored in _content[_start .. _end-1],
* with wraparound.
*/
private Object[] _content;
/**
* Constructor
*/
public FlexibleQueue()
{
this(10, 5);
}
/**
* Constructor with parameters
*
* @param size The initial size
* @param increment The size increment when the queue is full
*/
public FlexibleQueue(final int size, final int increment)
{
_content = new Object[size];
_initialSize = size;
_increment = increment;
_start = 0;
_end = 0;
_size = 0;
}
/**
* Add the given element to this queue.
*
* @param object the element to be added.
* @exception QueueFullException the queue cannot be expanded
* this only occurs when the machine is nearly out
* of memory.
*/
public void addElement(final Object object)
{
synchronized (_content)
{
if (_size == _content.length)
{
expandFullQueue();
}
_content[_end] = object;
_end = (_end + 1) % _content.length;
_size += 1;
}
}
/**
* Dequeue the first object in the queue.
* Precondition: The queue cannot be empty.
*
* @return the first object in the queue.
*/
public Object removeElement()
{
synchronized (_content)
{
Object result = _content[_start];
_start = (_start + 1) % _content.length;
_size -= 1;
return result;
}
}
/**
* Reead the first object in the queue.
* Precondition: The queue cannot be empty.
*
* @return the first object in the queue.
*/
public Object readElement()
{
synchronized (_content)
{
return _content[_start];
}
}
/**
* Get the size of the queue (the number of elements queued)
*
* @return the size of the queue.
*/
public int size()
{
synchronized (_content)
{
return _size;
}
}
/**
* Returns the current capacity of the queue.
*
* @return the capacity of the queue.
*/
public int capacity()
{
synchronized (_content)
{
return _content.length;
}
}
/**
* Resets the queue to be empty and of minimal capacity.
*/
public void reset()
{
synchronized (_content)
{
_content = new Object[_initialSize];
_start = 0;
_end = 0;
_size = 0;
}
}
/**
* Returns a string representation of this queue.
*
* @return a string representation of this queue.
*/
public String toString()
{
final StringBuffer buf = new StringBuffer();
buf.append(getClass().getName());
buf.append("[size=");
buf.append(_size);
buf.append(", content={");
if (_start > _end || _size == _content.length)
{
for (int i = _start, size = _content.length; i < size; i++)
{
buf.append(_content[i]);
if (i != _size - 1)
{
buf.append(", ");
}
}
for (int i = 0; i < _end; i++)
{
buf.append(_content[i]);
if (i != _end - 1)
{
buf.append(", ");
}
}
}
else
{
for (int i = _start; i < _end; i++)
{
buf.append(_content[i]);
if (i != _end - 1)
{
buf.append(", ");
}
}
}
buf.append("}]@");
buf.append(hashCode());
return buf.toString();
}
/**
* Make the _content array _increment items larger.
* Precondition: The queue must currently be full!
*/
private void expandFullQueue()
{
// New array for copying queue into.
final Object[] tmpContent;
tmpContent = new Object[_content.length + _increment];
// Copy _content to new array, using wrap around.
if (_start > _end || _size == _content.length)
{
System.arraycopy(_content, _start, tmpContent, 0, _content.length - _start);
System.arraycopy(_content, 0, tmpContent, _content.length - _start, _end);
}
else
{
System.arraycopy(_content, _start, tmpContent, 0, _end - _start + 1);
}
_start = 0;
_end = _content.length;
// one past the last element in the queue.
// Finally, replace old _content array with the new one.
_content = tmpContent;
}
}
