goldman.collection.positional
Class DynamicArray<E>
java.lang.Object
goldman.collection.AbstractCollection<E>
goldman.collection.positional.AbstractPositionalCollection<E>
goldman.collection.positional.Array<E>
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.
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 ≤ fromPos ≤ toPos < 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.AbstractCollection |
accept, addAll, checkRep, compare, equivalent, getComparator, getElementAtRank, getElementAtRank, getEquivalentElement, getSize, isEmpty, retainAll, toArray, toArray, writeElements |
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 |
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 arrayequivalenceTester
- 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.
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 positionvalue
- the object to insert
- Returns:
- null for an untracked implementations
removeRange
public void removeRange(int fromPos,
int toPos)
- Requires 0 ≤
fromPos
≤ toPos
< 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 positiontoPos
- a valid position
- Throws:
PositionOutOfBoundsException
- either of the arguments
is not a valid position
IllegalArgumentException
- fromPos
is greater
than toPos