goldman.collection.positional
Class DynamicArray<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.DynamicArray<E>
All Implemented Interfaces:
Collection<E>, PositionalCollection<E>, Iterable<E>

public class DynamicArray<E>
extends Array<E>
implements PositionalCollection<E>

This array-based data structure provides space for a fixed number of elements, which are stored in an underlying Java primitive array. However unlike Array and CircularArray, it performs automatic resizing. When the size of the collection is unknown or changing, the support for automatic resizing is important. However, the resizing introduces a small amount of additional computation whenever an element is added or removed, and the resizing method has linear cost (though the amortized cost is constant). On average, the size of the array is roughly 50\% larger than that needed. As with Array and CircularArray, DynamicArray supports user-controlled resizing through ensureCapacity and trimToSize. When the size of the collection matches that of the user-specified capacity, the performance of a dynamic array is almost identical to that of an array. The advantage of using a dynamic array over an array is that when the initial estimate for the size is wrong, then the data structure automatically resizes, versus leaving it to the application program. 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
 
Fields inherited from class goldman.collection.AbstractCollection
comp, DEFAULT_CAPACITY, FORE, NOT_FOUND, size, version
 
Constructor Summary
DynamicArray()
          Creates an underlying array a with a default initial capacity.
DynamicArray(int capacity)
          Creates an underlying array a with the given capacity.
DynamicArray(int capacity, Comparator<? super E> equivalenceTester)
          Creates a dynamic array with the given capacity that uses the provided equivalence tester
 
Method Summary
protected  PositionalCollectionLocator<E> addImpl(int p, Object value)
          Inserts object value at position p and increments the position number for the elements that were at positions p, ..., size-1.
 void ensureCapacity(int capacity)
          Increases the capacity of the underlying array, if needed.
 void removeRange(int fromPos, int toPos)
          Requires 0 ≤ fromPostoPos < size.
protected  void resizeArray(int desiredCapacity)
          Changes the capacity of the underlying array to desiredCapacity while maintaining the same positional collection.
 
Methods inherited from class goldman.collection.positional.Array
add, add, bucketsort, bucketsortImpl, clear, closeGap, contains, createGap, findPosition, get, getCapacity, getLocator, heapsort, heapsort, insertionsort, insertionsort, iterator, iteratorAt, iteratorAtEnd, mergesort, mergesort, moveElementsTo, positionOf, quicksort, quicksort, radixsort, radixsortImpl, read, remove, remove, removeFirst, removeLast, 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
add, addFirst, addLast, bucketsort, get, heapsort, heapsort, insertionsort, insertionsort, iterator, iteratorAtEnd, mergesort, mergesort, positionOf, quicksort, quicksort, radixsort, remove, removeFirst, removeLast, repositionElementByRank, repositionElementByRank, set, swap, treesort, treesort
 
Methods inherited from interface goldman.collection.Collection
accept, add, addAll, checkRep, clear, contains, getCapacity, getComparator, getEquivalentElement, getLocator, getSize, isEmpty, remove, retainAll, toArray, toArray, toString, trimToSize
 

Constructor Detail

DynamicArray

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

DynamicArray

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


DynamicArray

public DynamicArray(int capacity)
Creates an underlying array a with the given capacity.

Parameters:
capacity - the initial capacity for the underlying array a
Throws:
IllegalArgumentException - capacity < 0.
Method Detail

resizeArray

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

Parameters:
desiredCapacity - the desired capacity of the underlying array
Throws:
IllegalArgumentException - executing it would violate the property Capacity

ensureCapacity

public void ensureCapacity(int capacity)
Increases the capacity of the underlying array, if needed.

Specified by:
ensureCapacity in interface Collection<E>
Overrides:
ensureCapacity in class Array<E>
Parameters:
capacity - the desired capacity

addImpl

protected PositionalCollectionLocator<E> addImpl(int p,
                                                 Object value)
Inserts object value 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 object to insert
Returns:
null for an untracked implementations

removeRange

public void removeRange(int fromPos,
                        int toPos)
Requires 0 ≤ fromPostoPos < size. It removes the elements at positions fromPos, ..., toPos, inclusive, from the collection and decrements the positions of the elements at positions toPos+1 to size-1 by toPos-fromPos+1 (the number of elements being removed).

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