net.sf.zig_project.gpl.common.queue
Class DynamicArrayQueue

java.lang.Object
  net.sf.zig_project.gpl.common.queue.LinearQueueBase
      net.sf.zig_project.gpl.common.queue.ArrayQueue
          net.sf.zig_project.gpl.common.queue.DynamicArrayQueue

All Implemented Interfaces:

LinearQueue, Queue

Direct Known Subclasses:

ArrayQueueTest.CheckedArrayQueue

public class DynamicArrayQueue

extends ArrayQueue

An ArrayQueue that grows to compensate increasing numbers of elements. If an add method is called after the queue has run out of room, elements are copied into a new larger array, and relative indecies are updated to match new physical locations.

Add operations that would require more space in the Queue will force the Queue to grow, which has a complexity of O(n). Otherwise, add operations will operate in the complexity defined by ArrayQueue.

Version:

September 16, 2004

Author:

Frank Ziglar

Nested Class Summary

Nested classes inherited from class net.sf.zig_project.gpl.common.queue.ArrayQueue

ArrayQueue.ArraySequencer

Field Summary

protected ArraySizeSelector

selector

Fields inherited from class net.sf.zig_project.gpl.common.queue.ArrayQueue

begin, end, entries

Constructor Summary

DynamicArrayQueue()
Constructs a new Queue with an initial array size of 24.

DynamicArrayQueue(int sz)
Constructs a new Queue with the specified initial array size.

DynamicArrayQueue(int sz, ArraySizeSelector sel)
Constructs a new Queue.

Method Summary

protected void

overflow(int rm) This implementation moves elements out of the smaller array and into a new larger array.

Methods inherited from class net.sf.zig_project.gpl.common.queue.ArrayQueue

addFirst, addLast, addSet, availableRoom, bulkMoveTest, clear, contains, decIndex, elements, ensureRoom, firstIndexOf, incIndex, insert, isEmpty, peek, peekFirst, peekLast, physicalIndex, remove, remove, removeFirst, removeIndex, removeLast, replace, size, toString, toString

Methods inherited from class net.sf.zig_project.gpl.common.queue.LinearQueueBase

add, appendFlat, appendFlat, appendUnrolled, appendUnrolled, prependFlat, prependFlat, prependUnrolled, prependUnrolled, transferTo

Methods inherited from class java.lang.Object

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

Field Detail

selector

protected ArraySizeSelector selector

Constructor Detail

DynamicArrayQueue

public DynamicArrayQueue(int sz,
                         ArraySizeSelector sel)

Constructs a new Queue.

Parameters:

sz - the initial array size for the new queue

sel - the selector to use for resizing operations

DynamicArrayQueue

public DynamicArrayQueue(int sz)

Constructs a new Queue with the specified initial array size. The default ArraySizeSelector is used for array resizing.

Parameters:

sz - the initial array size to use

DynamicArrayQueue

public DynamicArrayQueue()

Constructs a new Queue with an initial array size of 24.

Method Detail

overflow

protected void overflow(int rm)

This implementation moves elements out of the smaller array and into a new larger array. The new array is based on the recommended size of an ArraySizeSelector. This method is called when the queue is too full to continue an add operation.

Overrides:

overflow in class ArrayQueue

Parameters:

rm - the amount of additional room required