|
||||||||||
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>
public class Array<E>
The simplest of the positional collections, Array provides space for a fixed number of elements, which are stored in an underlying Java primitive array. Methods are provided for changing the capacity of the collection, but there is no support for automatic resizing. If the approximate size of the collection is known a priori then this is a very good choice for minimizing space usage. However, it can only efficiently support insertions and deletions near the end of the collection. This is an untracked implementation.
Nested Class Summary | |
---|---|
class |
Array.BasicMarker
|
class |
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 | |
---|---|
Array()
Creates an array with a default initial capacity that uses the default equivalence tester. |
|
Array(int capacity)
Creates an array with the given capacity that uses the default equivalence tester |
|
Array(int capacity,
Comparator<? super E> equivalenceTester)
Creates an array with the given capacity that uses the provided equivalence tester |
Method Summary | |
---|---|
void |
add(E value)
Inserts it at the end of the collection. |
void |
add(int p,
E value)
Inserts value 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 |
bucketsortImpl(Bucketizer<? super E> bucketizer)
And sorts the array using bucket sort |
void |
clear()
Removes all elements from the collection. |
protected void |
closeGap(int fromPos,
int toPos)
Moves the elements that were at positions toPos +1, ..., size -1 to positions
fromPos , ...,
size -1 - (toPos - fromPos + 1). |
boolean |
contains(E value)
This implementation for contains takes linear time, so it
is overridden by a more efficient method in most data structure
implementations. |
protected void |
createGap(int p)
Moves elements at positions p , ..., size -1 to positions
p+1 , ..., size . |
void |
ensureCapacity(int capacity)
Increases the capacity of the underlying array if needed |
protected int |
findPosition(E value)
|
E |
get(int p)
Returns the element at position p. |
int |
getCapacity()
By default this method returns Integer.MAX_VALUE . |
PositionalCollectionLocator<E> |
getLocator(E value)
Returns a locator that has been initialized to an element equivalent to target . |
void |
heapsort()
Sorts this collection with heap sort using the default comparator |
void |
heapsort(Comparator<? super E> comp)
Sorts this collection with heap sort using the provided comparator |
void |
insertionsort()
Sorts this collection with insertion sort using the default 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 marker that is at the given position. |
PositionalCollectionLocator<E> |
iteratorAtEnd()
Creates a new marker that starts at AFT. |
void |
mergesort()
Uses the default comparator to order the elements |
void |
mergesort(Comparator<? super E> comp)
Sorts this collection with merge sort using the default comparator. |
protected Object[] |
moveElementsTo(Object[] newArray)
|
int |
positionOf(E value)
Returns the position of the first occurrence (if any) of an element equivalent to value . |
void |
quicksort()
Sorts this collection with quicksort 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 void |
radixsortImpl(Digitizer<? super E> digitizer)
Is the complete implementation of radix sort |
protected E |
read(int p)
|
boolean |
remove(E value)
Removes the first element in the collection equivalent to value |
E |
remove(int p)
Removes the element at position p and shifts elements
u_{p+1}, ..., u_{size -1} left by one position. |
E |
removeFirst()
Removes the element at position 0 and decrements the position for the elements that were at positions 1 to size-1 . |
E |
removeLast()
Removes the element at position size -1 |
void |
removeRange(int fromPos,
int toPos)
Requires 0 ≤ fromPos ≤ toPos < size . |
E |
repositionElementByRank(int r)
Modifies the positional collection so element in position r is in its proper sorted order when using the default comparator, and returns that element. |
E |
repositionElementByRank(int r,
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. |
E |
set(int p,
E value)
Replaces the element at position p by the given value , and
returns the element that had been in position p . |
void |
swap(int pos1,
int pos2)
Swaps the values held in positions pos1 and pos2 |
void |
traverseForVisitor(Visitor<? super E> v)
Traverses the entire collection on behalf of v. |
void |
treesort()
Sorts this collection using the tree sort algorithm and the default comparator |
void |
treesort(Comparator<? super E> comp)
Sorts this collection using the tree sort algorithm and the provided comparator |
void |
trimToSize()
Reduces the capacity of the array to the current number of elements in the collection |
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 |
Constructor Detail |
---|
public Array(int capacity, Comparator<? super E> equivalenceTester)
capacity
- the desired initial capacity for the underlying arrayequivalenceTester
- a user-provided equivalence tester
IllegalArgumentException
- capacity
< 0.public Array()
public Array(int capacity)
capacity
- the desired initial capacity for the underlying array
IllegalArgumentException
- capacity
< 0.Method Detail |
---|
public int getCapacity()
AbstractCollection
Integer.MAX_VALUE
.
getCapacity
in interface Collection<E>
getCapacity
in class AbstractCollection<E>
protected final E read(int p)
p
- a valid user 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>
p
- the desired user position
p
PositionOutOfBoundsException
- p is not a valid positionprotected int findPosition(E value)
value
- the element to be located
p
in the collection
such that value
is equivalent to the element at position
p
, or NOT_FOUND
if there is no equivalent element in the collection.public boolean contains(E value)
AbstractCollection
contains
takes linear time, so it
is overridden by a more efficient method in most data structure
implementations.
contains
in interface Collection<E>
contains
in class AbstractCollection<E>
value
- the element to be located
public int positionOf(E value)
PositionalCollection
value
.
It throws a
NoSuchElementException
if there is no equivalent element.
(The Java collections return -1 when there is no element with
the given value, but throwing an exception will better enable a
problem to be detected if an application program did not consider the possibility of -1
being returned.)
positionOf
in interface PositionalCollection<E>
value
- the element to be located
value
.
NoSuchElementException
- no element in the collection is equivalent
to value
protected Object[] moveElementsTo(Object[] newArray)
newArray
- the array to which the elements should be moved
public void ensureCapacity(int capacity)
ensureCapacity
in interface Collection<E>
ensureCapacity
in class AbstractCollection<E>
capacity
- the desired capacitypublic void trimToSize()
trimToSize
in interface Collection<E>
trimToSize
in class AbstractCollection<E>
public E set(int p, E value)
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>
p
- a user position to updatevalue
- the element to put at position p
p
PositionOutOfBoundsException
- p
is not
a valid positionpublic void swap(int pos1, int pos2)
pos1
and pos2
swap
in interface PositionalCollection<E>
pos1
- a valid positionpos2
- a valid position
PositionOutOfBoundsException
- either pos1
or pos2
is not a valid positionprotected void createGap(int p)
p
, ..., size
-1 to positions
p+1
, ..., size
.
p
- a valid user position where the gap is to be createdpublic final void add(int p, E value)
value
at position p
and increments the position number for the elements that were at
positions p
, ..., size
-1.
add
in interface PositionalCollection<E>
p
- a valid user positionvalue
- the new element
PositionOutOfBoundsException
- p
is neither size
nor a valid position
AtCapacityException
- the underlying array is already at capacitypublic void add(E value)
add
in interface Collection<E>
value
- the new element
AtCapacityException
- the underlying array is already at capacityprotected void closeGap(int fromPos, int toPos)
toPos
+1, ..., size
-1 to positions
fromPos
, ...,
size
-1 - (toPos
- fromPos
+ 1). We use
Arrays.fill
to set all slots in the underlying array that are no
longer in use to null.
fromPos
- the first position in the gap to closetoPos
- the last position in the gap to closepublic void removeRange(int fromPos, int toPos)
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).
removeRange
in interface PositionalCollection<E>
fromPos
- a valid positiontoPos
- a valid position
PositionOutOfBoundsException
- either of the arguments
is not a valid position
IllegalArgumentException
- fromPos
is greater
than toPos
public E remove(int p)
p
and shifts elements
u_{p+1}, ..., u_{size
-1} left by one position.
remove
in interface PositionalCollection<E>
p
- a valid position
PositionOutOfBoundsException
- p
is not a valid
positionpublic final E removeFirst()
1
to size-1
.
removeFirst
in interface PositionalCollection<E>
NoSuchElementException
- the collection is emptypublic final E removeLast()
size
-1
removeLast
in interface PositionalCollection<E>
NoSuchElementException
- the collection is emptypublic boolean remove(E value)
value
remove
in interface Collection<E>
value
- the element to be removed
public void clear()
clear
in interface Collection<E>
clear
in class AbstractCollection<E>
public void traverseForVisitor(Visitor<? super E> v) throws Exception
traverseForVisitor
in class AbstractCollection<E>
v
- a visitor to apply for each element in the collection
Exception
- the visitor throws an exception.public PositionalCollectionLocator<E> iterator()
iterator
in interface Collection<E>
iterator
in interface PositionalCollection<E>
iterator
in interface Iterable<E>
iterator
in class AbstractPositionalCollection<E>
public PositionalCollectionLocator<E> iteratorAtEnd()
iteratorAtEnd
in interface PositionalCollection<E>
iteratorAtEnd
in class AbstractPositionalCollection<E>
public PositionalCollectionLocator<E> iteratorAt(int pos)
iteratorAt
in class AbstractPositionalCollection<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>
value
- the target
value
NoSuchElementException
- value
does not occur in the collectionpublic void insertionsort()
PositionalCollection
insertionsort
in interface PositionalCollection<E>
public void insertionsort(Comparator<? super E> comp)
PositionalCollection
insertionsort
in interface PositionalCollection<E>
comp
- the comparator
to use to order the elementspublic void mergesort()
mergesort
in interface PositionalCollection<E>
public void mergesort(Comparator<? super E> comp)
PositionalCollection
mergesort
in interface PositionalCollection<E>
comp
- the comparator that defines the
ordering of the elementspublic void heapsort()
heapsort
in interface PositionalCollection<E>
public void heapsort(Comparator<? super E> comp)
heapsort
in interface PositionalCollection<E>
comp
- a comparatorpublic void treesort()
treesort
in interface PositionalCollection<E>
public void treesort(Comparator<? super E> comp)
treesort
in interface PositionalCollection<E>
comp
- a comparatorpublic void quicksort()
quicksort
in interface PositionalCollection<E>
public void quicksort(Comparator<? super E> comp)
quicksort
in interface PositionalCollection<E>
comp
- a comparatorpublic void radixsort(Digitizer<? super E> digitizer)
radixsort
in interface PositionalCollection<E>
digitizer
- the digitizer
to useprotected void radixsortImpl(Digitizer<? super E> digitizer)
digitizer
- the digitizer to usepublic void bucketsort(Bucketizer<? super E> bucketizer)
PositionalCollection
bucketsort
in interface PositionalCollection<E>
bucketizer
- the bucketizer
to useprotected void bucketsortImpl(Bucketizer<? super E> bucketizer)
bucketizer
- the bucketizer to usepublic E repositionElementByRank(int r)
PositionalCollection
repositionElementByRank
in interface PositionalCollection<E>
r
- the rank of the desired element in the sorted collection
r
when using the default comparator
PositionOutOfBoundsException
- r
is not a valid positionpublic E repositionElementByRank(int r, Comparator<? super E> comp)
PositionalCollection
repositionElementByRank
in interface PositionalCollection<E>
r
- the rank of the desired element in the sorted arraycomp
- the comparator to use
r
when using the given comparator
noSuchElementException
- the collection is empty
or r
is not a valid position
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |