|
||||||||||
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>
goldman.collection.positional.DynamicCircularArray<E>
goldman.collection.positional.TrackedArray<E>
public class TrackedArray<E>
This array-based data structure can wrap any of the other array-based data structures to create a tracked implementation of the wrapped data structure. In the provided implementation, TrackedArray wraps DynamicCircularArray. However, the provided implementation could easily be changed to use any of the other array-based data structures. Since the maintenance of the trackers requires some additional structure as compared to that needed for a marker, a tracked array should be used only if it is important to be able to track elements. Observe that the tracker does not reduce the cost of shifting array elements when an element is added or removed, even through a tracker. The tracker would be useful when the application needs to determine the position of a tracked element in constant time.
Nested Class Summary | |
---|---|
protected class |
TrackedArray.Tracker
|
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 |
---|
Fields inherited from class goldman.collection.positional.CircularArray |
---|
start |
Fields inherited from class goldman.collection.AbstractCollection |
---|
comp, DEFAULT_CAPACITY, FORE, NOT_FOUND, size, version |
Constructor Summary | |
---|---|
TrackedArray()
Creates an underlying array a with a default initial capacity. |
|
TrackedArray(int capacity)
|
|
TrackedArray(int capacity,
Comparator<? super E> equivalenceTester)
Creates a tracked array with the given capacity that uses the provided equivalence tester |
Method Summary | |
---|---|
PositionalCollectionLocator<E> |
addImpl(int p,
Object element)
Inserts element at position p ,
incrementing the position for the elements that were at
positions p to size-1 |
PositionalCollectionLocator<E> |
addTracked(E value)
Inserts value it at the end of the collection. |
PositionalCollectionLocator<E> |
addTracked(int p,
E value)
Inserts the new element at position p
and increments the position number for the elements that were at
positions p , ..., size -1. |
void |
bucketsort(Bucketizer<? super E> bucketizer)
Sorts this collection using bucket sort with the given bucketizer. |
protected void |
buildPriorityQueue(PriorityQueue<Object> pq)
|
void |
clear()
Removes all elements from the collection. |
protected int |
findPosition(E element)
|
E |
get(int p)
Returns the element at position p. |
PositionalCollectionLocator<E> |
getLocator(E value)
Returns a locator that has been initialized to an element equivalent to target . |
void |
heapsort(Comparator<? super E> comp)
Sorts this collection with heap sort using the provided comparator |
void |
insertionsort(Comparator<? super E> comp)
Sorts this collection with insertion sort using the default comparator. |
PositionalCollectionLocator<E> |
iterator()
Creates a new marker that starts at FORE. |
PositionalCollectionLocator<E> |
iteratorAt(int pos)
Returns a new tracker that is at the given position. |
PositionalCollectionLocator<E> |
iteratorAtEnd()
Creates a new marker that starts at AFT. |
void |
mergesort(Comparator<? super E> comp)
Sorts this collection with merge sort using the default comparator. |
void |
quicksort(Comparator<? super E> comp)
Sorts this collection with quicksort using the provided comparator |
void |
radixsort(Digitizer<? super E> digitizer)
And sorts the collection with radix sort. |
protected E |
readElement(int p)
|
void |
removeRange(int fromPos,
int toPos)
Removes a[i]...a[j] from the collection moving
the elements at positions j+1 to size-1 to the left
by j-1+1 positions. |
E |
repositionElementByRank(int i,
Comparator<? super E> comp)
Modifies the positional collection so element in position r is in its proper sorted order when using the provided comparator, and returns this element. |
protected void |
resizeArray(int desiredCapacity)
Changes the size of the underlying array to desiredCapacity while maintaining the same positional collection. |
E |
set(int p,
E element)
Replaces the element at position p by the given value , and
returns the element that had been in position p . |
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. |
void |
treesort(Comparator<? super E> comp)
Sorts this collection using the tree sort algorithm and the provided comparator |
protected void |
updateNodes(int i,
int num)
|
protected E |
writeElement(int p,
E element)
|
Methods inherited from class goldman.collection.positional.DynamicCircularArray |
---|
ensureCapacity |
Methods inherited from class goldman.collection.positional.CircularArray |
---|
closeGap, createGap, getIndex, getPosition, moveElementsTo, nextIndex, prevIndex, setToNull |
Methods inherited from class goldman.collection.positional.Array |
---|
add, add, bucketsortImpl, contains, getCapacity, heapsort, insertionsort, mergesort, positionOf, quicksort, radixsortImpl, read, remove, remove, removeFirst, removeLast, repositionElementByRank, swap, traverseForVisitor, 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 |
---|
add, addFirst, addLast, heapsort, insertionsort, mergesort, positionOf, quicksort, remove, removeFirst, removeLast, repositionElementByRank, swap, treesort |
Methods inherited from interface goldman.collection.Collection |
---|
accept, add, addAll, checkRep, contains, ensureCapacity, getCapacity, getComparator, getEquivalentElement, getSize, isEmpty, remove, retainAll, toArray, toArray, toString, trimToSize |
Methods inherited from interface goldman.collection.Collection |
---|
accept, add, addAll, checkRep, contains, ensureCapacity, getCapacity, getComparator, getEquivalentElement, getSize, isEmpty, remove, retainAll, toArray, toArray, toString, trimToSize |
Constructor Detail |
---|
public TrackedArray(int capacity, Comparator<? super E> equivalenceTester)
capacity
- the desired initial capacity for the underlying arrayequivalenceTester
- a user-provided equivalence tester
IllegalArgumentException
- capacity
< 0.public TrackedArray()
a
with a default initial capacity.
public TrackedArray(int capacity)
capacity
- the initial capacity for the underlying array a
IllegalArgumentException
- capacity
< 0.Method Detail |
---|
protected E readElement(int p)
p
- a valid position
p
is a valid position
p
protected E writeElement(int p, E element)
p
- a valid positionelement
- the element to write at position p
p
is a valid position.
p
public E get(int p)
PositionalCollection
size-1
(i.e., that the position exists in the collection).
Otherwise a PositionOutOfBoundsException
is thrown.
get
in interface PositionalCollection<E>
get
in class Array<E>
p
- a valid user position
p
PositionOutOfBoundsException
- the position is not validprotected int findPosition(E element)
findPosition
in class Array<E>
element
- the target
p
in the collection holding
an equivalent element, or NOT_FOUND
if there is no equivalent
element in the collectionprotected void updateNodes(int i, int num)
i
- the starting index that needs updatingnum
- the number of nodes to update starting at i
,
possibly wrappingprotected void shiftLeft(int p1, int p2, int num)
p1, ..., p2
(possibly wrapped) left
num
slots
shiftLeft
in class CircularArray<E>
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.
shiftRight
in class CircularArray<E>
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 itself)protected void resizeArray(int desiredCapacity)
desiredCapacity
while maintaining the same positional collection.
resizeArray
in class DynamicCircularArray<E>
desiredCapacity
- the size to make the underlying array
IllegalArgumentException
- executing it would
make the array capacity too small to hold the current collectionpublic E set(int p, E element)
PositionalCollection
p
by the given value
, and
returns the element that had been in position p
. It is required that 0 ≤
p
≤ size-1
. Otherwise, a PositionOutOfBoundsException
is thrown.
set
in interface PositionalCollection<E>
set
in class Array<E>
p
- a valid user position to be updatedelement
- the element to put at position p
p
PositionOutOfBoundsException
- p
is not
a valid positionpublic PositionalCollectionLocator<E> addImpl(int p, Object element)
element
at position p
,
incrementing the position for the elements that were at
positions p
to size-1
addImpl
in class DynamicCircularArray<E>
p
- a valid positionelement
- the element to insert
public PositionalCollectionLocator<E> addTracked(E value)
value
it at the end of the collection.
addTracked
in interface Tracked<E>
value
- the new elementpublic PositionalCollectionLocator<E> addTracked(int p, E value)
p
and increments the position number for the elements that were at
positions p
, ..., size
-1.
p
- a valid user positionvalue
- the new element
PositionOutOfBoundsException
- p
is neither size
nor a valid positionpublic void removeRange(int fromPos, int toPos)
a[i]...a[j]
from the collection moving
the elements at positions j+1
to size-1
to the left
by j-1+1
positions.
removeRange
in interface PositionalCollection<E>
removeRange
in class DynamicCircularArray<E>
fromPos
- the first position to be removedtoPos
- the last position to be removed
PositionOutOfBoundsException
- either of the arguments
is not a valid position
IllegalArgumentException
- fromPos
is greater
than toPos
public void clear()
clear
in interface Collection<E>
clear
in class Array<E>
public PositionalCollectionLocator<E> iterator()
Array
iterator
in interface Collection<E>
iterator
in interface PositionalCollection<E>
iterator
in interface Iterable<E>
iterator
in class Array<E>
public PositionalCollectionLocator<E> iteratorAtEnd()
Array
iteratorAtEnd
in interface PositionalCollection<E>
iteratorAtEnd
in class Array<E>
public PositionalCollectionLocator<E> iteratorAt(int pos)
iteratorAt
in class Array<E>
pos
- the user position of an element
NoSuchElementException
- the given position is not a valid user position.public PositionalCollectionLocator<E> getLocator(E value)
Collection
target
. Like the iterator
method, this method enables
navigation, but from a specified starting point. This method
throws a NoSuchElementException
if there is no equivalent element
in the collection.
getLocator
in interface Collection<E>
getLocator
in class Array<E>
value
- the target
value
NoSuchElementException
- value
does not occur in the collectionprotected void buildPriorityQueue(PriorityQueue<Object> pq)
pq
- the
priority queue instance to which all elements are to be placedpublic void insertionsort(Comparator<? super E> comp)
PositionalCollection
insertionsort
in interface PositionalCollection<E>
insertionsort
in class Array<E>
comp
- the comparator
to use to order the elementspublic void mergesort(Comparator<? super E> comp)
PositionalCollection
mergesort
in interface PositionalCollection<E>
mergesort
in class Array<E>
comp
- the comparator that defines the
ordering of the elementspublic void heapsort(Comparator<? super E> comp)
Array
heapsort
in interface PositionalCollection<E>
heapsort
in class Array<E>
comp
- a comparatorpublic void treesort(Comparator<? super E> comp)
Array
treesort
in interface PositionalCollection<E>
treesort
in class Array<E>
comp
- a comparatorpublic void quicksort(Comparator<? super E> comp)
Array
quicksort
in interface PositionalCollection<E>
quicksort
in class Array<E>
comp
- a comparatorpublic E repositionElementByRank(int i, Comparator<? super E> comp)
PositionalCollection
repositionElementByRank
in interface PositionalCollection<E>
repositionElementByRank
in class Array<E>
i
- the rank of the desired element in the sorted arraycomp
- the comparator to use
r
when using the given comparatorpublic void radixsort(Digitizer<? super E> digitizer)
Array
radixsort
in interface PositionalCollection<E>
radixsort
in class Array<E>
digitizer
- the digitizer
to usepublic void bucketsort(Bucketizer<? super E> bucketizer)
PositionalCollection
bucketsort
in interface PositionalCollection<E>
bucketsort
in class Array<E>
bucketizer
- the bucketizer
to use
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |