goldman.collection.positional
Class CircularArray<E>

java.lang.Object
  extended by goldman.collection.AbstractCollection<E>
      extended by goldman.collection.positional.AbstractPositionalCollection<E>
          extended by goldman.collection.positional.Array<E>
              extended by goldman.collection.positional.CircularArray<E>
All Implemented Interfaces:
Collection<E>, PositionalCollection<E>, Iterable<E>
Direct Known Subclasses:
DynamicCircularArray

public class CircularArray<E>
extends Array<E>

This array-based data structure allows element 0 of the positional collection to be in any slot of the underlying array, with the range of underlying indices wrapping around as needed. Managing this introduces a small amount of overhead, but enables efficient insertion and deletion near either the front or end of the collection. Like Array, there is no support for automatic resizing. This is an untracked implementation.


Nested Class Summary
 
Nested classes/interfaces inherited from class goldman.collection.positional.Array
Array.BasicMarker, Array.Marker
 
Nested classes/interfaces inherited from class goldman.collection.AbstractCollection
AbstractCollection.AbstractLocator<T extends E>, AbstractCollection.VisitingIterator
 
Field Summary
protected  int start
           
 
Fields inherited from class goldman.collection.AbstractCollection
comp, DEFAULT_CAPACITY, FORE, NOT_FOUND, size, version
 
Constructor Summary
CircularArray()
          Creates a circular array with a default initial capacity that uses the default equivalence tester.
CircularArray(int capacity)
          Creates a circular array with the given capacity that uses the default equivalence tester
CircularArray(int capacity, Comparator<? super E> equivalenceTester)
          Creates a circular array with the given capacity that uses the provided equivalence tester
 
Method Summary
protected  void closeGap(int fromPos, int toPos)
          Moves elements to decrement the position number for elements that were at positions toPos+1, ..., size-1 to positions fromPos, ..., size-1 - (toPos - fromPos + 1).
protected  void createGap(int p)
          Moves elements in such a way to increment the position number for the elements that were at positions p, ..., size-1 to be at positions p+1, ..., size.
protected  int getIndex(int p)
           
protected  int getPosition(int index)
           
protected  Object[] moveElementsTo(Object[] newArray)
           
protected  int nextIndex(int index)
          The next index is computed without regard to the contents of that slot.
protected  int prevIndex(int index)
          If the parameter is the index of the first element of the collection, then prevIndex returns the index of the slot immediately before the start of the collection (wrapping if required), unless the CircularArray is at capacity, in which case the index returned is that of the last element in the collection.
protected  void setToNull(int pos1, int pos2)
          Sets positions pos1, ..., pos2 to null.
protected  void shiftLeft(int p1, int p2, int num)
          Shifts the elements held in p1, ..., p2 (possibly wrapped) left num slots
protected  void shiftRight(int p1, int p2, int num)
          Shifts the elements held in p1, ..., p2 (possibly wrapped) right num slots.
 
Methods inherited from class goldman.collection.positional.Array
add, add, bucketsort, bucketsortImpl, clear, contains, ensureCapacity, findPosition, get, getCapacity, getLocator, heapsort, heapsort, insertionsort, insertionsort, iterator, iteratorAt, iteratorAtEnd, mergesort, mergesort, positionOf, quicksort, quicksort, radixsort, radixsortImpl, read, remove, remove, removeFirst, removeLast, removeRange, repositionElementByRank, repositionElementByRank, set, swap, traverseForVisitor, treesort, treesort, trimToSize
 
Methods inherited from class goldman.collection.positional.AbstractPositionalCollection
addFirst, addLast, toString
 
Methods inherited from class goldman.collection.AbstractCollection
accept, addAll, checkRep, compare, equivalent, getComparator, getElementAtRank, getElementAtRank, getEquivalentElement, getSize, isEmpty, retainAll, toArray, toArray, writeElements
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface goldman.collection.positional.PositionalCollection
addFirst, addLast
 
Methods inherited from interface goldman.collection.Collection
accept, addAll, checkRep, getComparator, getEquivalentElement, getSize, isEmpty, retainAll, toArray, toArray, toString
 

Field Detail

start

protected int start
Constructor Detail

CircularArray

public CircularArray(int capacity,
                     Comparator<? super E> equivalenceTester)
Creates a circular array with the given capacity that uses the provided equivalence tester

Parameters:
capacity - the desired initial capacity for the underlying array
equivalenceTester - a user-provided equivalence tester
Throws:
IllegalArgumentException - capacity < 0.

CircularArray

public CircularArray()
Creates a circular array with a default initial capacity that uses the default equivalence tester.


CircularArray

public CircularArray(int capacity)
Creates a circular array with the given capacity that uses the default equivalence tester

Parameters:
capacity - the desired initial capacity
Throws:
IllegalArgumentException - capacity < 0.
Method Detail

getIndex

protected final int getIndex(int p)
Parameters:
p - a valid user position
Returns:
the corresponding index in the underlying array a

getPosition

protected final int getPosition(int index)
Parameters:
index - an index of a that is in use
REQUIRES: index is a valid position
Returns:
the corresponding user position.

nextIndex

protected final int nextIndex(int index)
The next index is computed without regard to the contents of that slot. If the parameter is the index of the last element of the collection, then nextIndex returns the index of the slot immediately after the end of the collection (wrapping if required), unless the CircularArray is at capacity, in which the index returned is that of the first element in the collection.

Parameters:
index - an underlying index of a
Returns:
the underlying index for the next element in the collection

prevIndex

protected final int prevIndex(int index)
If the parameter is the index of the first element of the collection, then prevIndex returns the index of the slot immediately before the start of the collection (wrapping if required), unless the CircularArray is at capacity, in which case the index returned is that of the last element in the collection.

Parameters:
index - an underlying index
Returns:
the underlying index for the previous element in the collection

moveElementsTo

protected Object[] moveElementsTo(Object[] newArray)
Overrides:
moveElementsTo in class Array<E>
Parameters:
newArray - the array to which the elements should be moved
Returns:
the parameter value for convenience

shiftLeft

protected void shiftLeft(int p1,
                         int p2,
                         int num)
Shifts the elements held in p1, ..., p2 (possibly wrapped) left num slots

Parameters:
p1 - the starting position to shift
p2 - the ending position for the shift
num - the number of slots to shift
REQUIRES: p1p2, and 0 < numa.length - (p2 - p1 + 1). The amount of the shift is at least 1 and is not so much that the portion of the array being shifted would intersect with itself.

shiftRight

protected void shiftRight(int p1,
                          int p2,
                          int num)
Shifts the elements held in p1, ..., p2 (possibly wrapped) right num slots.

Parameters:
p1 - a valid position
p2 - a valid position
num - the number of positions to shift
REQUIRES: that p1p2, and 0 < numa.length - (p2 -p1 + 1). The amount to shift is at least 1, and the portion of the array being shifted does intersect with itself

createGap

protected void createGap(int p)
Moves elements in such a way to increment the position number for the elements that were at positions p, ..., size-1 to be at positions p+1, ..., size.

Overrides:
createGap in class Array<E>
Parameters:
p - a valid user position where the gap is to be created

setToNull

protected void setToNull(int pos1,
                         int pos2)
Sets positions pos1, ..., pos2 to null.

Parameters:
pos1 - a valid position
pos2 - a valid position
REQUIRES: that pos1pos2.

closeGap

protected void closeGap(int fromPos,
                        int toPos)
Moves elements to decrement the position number for elements that were at positions toPos+1, ..., size-1 to positions fromPos, ..., size-1 - (toPos - fromPos + 1). Furthermore, the indices in the underlying array that are no longer in use are set to null.

Overrides:
closeGap in class Array<E>
Parameters:
fromPos - the first position in the gap to close
toPos - the last position in the gap to close