goldman.collection.positional
Class TrackedArray<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>
                  extended by goldman.collection.positional.DynamicCircularArray<E>
                      extended by goldman.collection.positional.TrackedArray<E>
All Implemented Interfaces:
Collection<E>, PositionalCollection<E>, Tracked<E>, Iterable<E>

public class TrackedArray<E>
extends DynamicCircularArray<E>
implements PositionalCollection<E>, Tracked<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

TrackedArray

public TrackedArray(int capacity,
                    Comparator<? super E> equivalenceTester)
Creates a tracked 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.

TrackedArray

public TrackedArray()
Creates an underlying array a with a default initial capacity.


TrackedArray

public TrackedArray(int capacity)
Parameters:
capacity - the initial capacity for the underlying array a
Throws:
IllegalArgumentException - capacity < 0.
Method Detail

readElement

protected E readElement(int p)
Parameters:
p - a valid position
REQUIRES: p is a valid position
Returns:
the element held at user position p

writeElement

protected E writeElement(int p,
                         E element)
Parameters:
p - a valid position
element - the element to write at position p
REQUIRES: p is a valid position.
Returns:
the element that was previously at position p

get

public E get(int p)
Description copied from interface: PositionalCollection
Returns the element at position p. It is required that 0 ≤ p ≤ size-1 (i.e., that the position exists in the collection). Otherwise a PositionOutOfBoundsException is thrown.

Specified by:
get in interface PositionalCollection<E>
Overrides:
get in class Array<E>
Parameters:
p - a valid user position
Returns:
the element at the position p
Throws:
PositionOutOfBoundsException - the position is not valid

findPosition

protected int findPosition(E element)
Overrides:
findPosition in class Array<E>
Parameters:
element - the target
Returns:
the first position p in the collection holding an equivalent element, or NOT_FOUND if there is no equivalent element in the collection

updateNodes

protected void updateNodes(int i,
                           int num)
Parameters:
i - the starting index that needs updating
num - the number of nodes to update starting at i, possibly wrapping

shiftLeft

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

Overrides:
shiftLeft in class CircularArray<E>
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.

Overrides:
shiftRight in class CircularArray<E>
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)

resizeArray

protected void resizeArray(int desiredCapacity)
Changes the size of the underlying array to desiredCapacity while maintaining the same positional collection.

Overrides:
resizeArray in class DynamicCircularArray<E>
Parameters:
desiredCapacity - the size to make the underlying array
Throws:
IllegalArgumentException - executing it would make the array capacity too small to hold the current collection

set

public E set(int p,
             E element)
Description copied from interface: PositionalCollection
Replaces the element at position p by the given value, and returns the element that had been in position p. It is required that 0 ≤ psize-1. Otherwise, a PositionOutOfBoundsException is thrown.

Specified by:
set in interface PositionalCollection<E>
Overrides:
set in class Array<E>
Parameters:
p - a valid user position to be updated
element - the element to put at position p
Returns:
the prior element at position p
Throws:
PositionOutOfBoundsException - p is not a valid position

addImpl

public 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

Overrides:
addImpl in class DynamicCircularArray<E>
Parameters:
p - a valid position
element - the element to insert
Returns:
a tracker for the new element.

addTracked

public PositionalCollectionLocator<E> addTracked(E value)
Inserts value it at the end of the collection.

Specified by:
addTracked in interface Tracked<E>
Parameters:
value - the new element

addTracked

public 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.

Parameters:
p - a valid user position
value - the new element
Throws:
PositionOutOfBoundsException - p is neither size nor a valid position

removeRange

public 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.

Specified by:
removeRange in interface PositionalCollection<E>
Overrides:
removeRange in class DynamicCircularArray<E>
Parameters:
fromPos - the first position to be removed
toPos - the last position to be removed
Throws:
PositionOutOfBoundsException - either of the arguments is not a valid position
IllegalArgumentException - fromPos is greater than toPos

clear

public void clear()
Removes all elements from the collection.

Specified by:
clear in interface Collection<E>
Overrides:
clear in class Array<E>

iterator

public PositionalCollectionLocator<E> iterator()
Description copied from class: Array
Creates a new marker that starts at FORE.

Specified by:
iterator in interface Collection<E>
Specified by:
iterator in interface PositionalCollection<E>
Specified by:
iterator in interface Iterable<E>
Overrides:
iterator in class Array<E>
Returns:
a new tracker that is initialized to be logically just before the first element in the collection.

iteratorAtEnd

public PositionalCollectionLocator<E> iteratorAtEnd()
Description copied from class: Array
Creates a new marker that starts at AFT.

Specified by:
iteratorAtEnd in interface PositionalCollection<E>
Overrides:
iteratorAtEnd in class Array<E>
Returns:
a new tracker that is initialized to be logically just after the last element in the collection

iteratorAt

public PositionalCollectionLocator<E> iteratorAt(int pos)
Returns a new tracker that is at the given position.

Overrides:
iteratorAt in class Array<E>
Parameters:
pos - the user position of an element
Throws:
NoSuchElementException - the given position is not a valid user position.

getLocator

public PositionalCollectionLocator<E> getLocator(E value)
Description copied from interface: Collection
Returns a locator that has been initialized to an element equivalent to 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.

Specified by:
getLocator in interface Collection<E>
Overrides:
getLocator in class Array<E>
Parameters:
value - the target
Returns:
a tracker initialized to the position of the first element in the collection equivalent to value
Throws:
NoSuchElementException - value does not occur in the collection

buildPriorityQueue

protected void buildPriorityQueue(PriorityQueue<Object> pq)
Parameters:
pq - the priority queue instance to which all elements are to be placed

insertionsort

public void insertionsort(Comparator<? super E> comp)
Description copied from interface: PositionalCollection
Sorts this collection with insertion sort using the default comparator.

Specified by:
insertionsort in interface PositionalCollection<E>
Overrides:
insertionsort in class Array<E>
Parameters:
comp - the comparator to use to order the elements

mergesort

public void mergesort(Comparator<? super E> comp)
Description copied from interface: PositionalCollection
Sorts this collection with merge sort using the default comparator.

Specified by:
mergesort in interface PositionalCollection<E>
Overrides:
mergesort in class Array<E>
Parameters:
comp - the comparator that defines the ordering of the elements

heapsort

public void heapsort(Comparator<? super E> comp)
Description copied from class: Array
Sorts this collection with heap sort using the provided comparator

Specified by:
heapsort in interface PositionalCollection<E>
Overrides:
heapsort in class Array<E>
Parameters:
comp - a comparator

treesort

public void treesort(Comparator<? super E> comp)
Description copied from class: Array
Sorts this collection using the tree sort algorithm and the provided comparator

Specified by:
treesort in interface PositionalCollection<E>
Overrides:
treesort in class Array<E>
Parameters:
comp - a comparator

quicksort

public void quicksort(Comparator<? super E> comp)
Description copied from class: Array
Sorts this collection with quicksort using the provided comparator

Specified by:
quicksort in interface PositionalCollection<E>
Overrides:
quicksort in class Array<E>
Parameters:
comp - a comparator

repositionElementByRank

public E repositionElementByRank(int i,
                                 Comparator<? super E> comp)
Description copied from interface: PositionalCollection
Modifies the positional collection so element in position r is in its proper sorted order when using the provided comparator, and returns this element. This method does not completely sort the collection, but it may mutate it.

Specified by:
repositionElementByRank in interface PositionalCollection<E>
Overrides:
repositionElementByRank in class Array<E>
Parameters:
i - the rank of the desired element in the sorted array
comp - the comparator to use
Returns:
the element at rank r when using the given comparator

radixsort

public void radixsort(Digitizer<? super E> digitizer)
Description copied from class: Array
And sorts the collection with radix sort.

Specified by:
radixsort in interface PositionalCollection<E>
Overrides:
radixsort in class Array<E>
Parameters:
digitizer - the digitizer to use

bucketsort

public void bucketsort(Bucketizer<? super E> bucketizer)
Description copied from interface: PositionalCollection
Sorts this collection using bucket sort with the given bucketizer.

Specified by:
bucketsort in interface PositionalCollection<E>
Overrides:
bucketsort in class Array<E>
Parameters:
bucketizer - the bucketizer to use