|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectgoldman.collection.AbstractCollection<E>
goldman.collection.positional.AbstractPositionalCollection<E>
goldman.collection.positional.Array<E>
goldman.collection.positional.CircularArray<E>
public class CircularArray<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 |
---|
protected int start
Constructor Detail |
---|
public CircularArray(int capacity, Comparator<? super E> equivalenceTester)
capacity
- the desired initial capacity for the underlying arrayequivalenceTester
- a user-provided equivalence tester
IllegalArgumentException
- capacity
< 0.public CircularArray()
public CircularArray(int capacity)
capacity
- the desired initial capacity
IllegalArgumentException
- capacity
< 0.Method Detail |
---|
protected final int getIndex(int p)
p
- a valid user position
a
protected final int getPosition(int index)
index
- an index of a
that is in use
index
is a valid position
protected final int nextIndex(int index)
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.
index
- an underlying index of a
protected final int prevIndex(int index)
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.
index
- an underlying index
protected Object[] moveElementsTo(Object[] newArray)
moveElementsTo
in class Array<E>
newArray
- the array to which the elements should be moved
protected void shiftLeft(int p1, int p2, int num)
p1, ..., p2
(possibly wrapped) left
num
slots
p1
- the starting position to shiftp2
- the ending position for the shiftnum
- the number of slots to shift
p1
≤ p2
, and
0 < num
≤ a.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.protected void shiftRight(int p1, int p2, int num)
p1, ..., p2
(possibly wrapped) right
num
slots.
p1
- a valid positionp2
- a valid positionnum
- the number of positions to shift
p1
≤ p2
, and
0 < num
≤ a.length
- (p2
-p1
+ 1).
The amount to shift is at least 1, and
the portion of the array being shifted does intersect with itselfprotected void createGap(int p)
p
, ..., size
-1 to be at positions
p+1
, ..., size
.
createGap
in class Array<E>
p
- a valid user position where the gap is to be createdprotected void setToNull(int pos1, int pos2)
pos1
, ..., pos2
to null.
pos1
- a valid positionpos2
- a valid position
pos1
≤ pos2
.protected void closeGap(int fromPos, int toPos)
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.
closeGap
in class Array<E>
fromPos
- the first position in the gap to closetoPos
- the last position in the gap to close
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |