goldman.collection.positional
Class Array<E>

java.lang.Object
  extended by goldman.collection.AbstractCollection<E>
      extended by goldman.collection.positional.AbstractPositionalCollection<E>
          extended by goldman.collection.positional.Array<E>
All Implemented Interfaces:
Collection<E>, PositionalCollection<E>, Iterable<E>
Direct Known Subclasses:
CircularArray, DynamicArray

public class Array<E>
extends AbstractPositionalCollection<E>
implements PositionalCollection<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 ≤ fromPostoPos < 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

Array

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

Array

public Array()
Creates an array with a default initial capacity that uses the default equivalence tester.


Array

public Array(int capacity)
Creates an array with the given capacity that uses the default equivalence tester

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

getCapacity

public int getCapacity()
Description copied from class: AbstractCollection
By default this method returns Integer.MAX_VALUE.

Specified by:
getCapacity in interface Collection<E>
Overrides:
getCapacity in class AbstractCollection<E>
Returns:
the current capacity of the collection

read

protected final E read(int p)
Parameters:
p - a valid user position
REQUIRES: p is a valid position
Returns:
the element at user 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>
Parameters:
p - the desired user position
Returns:
the element at the position p
Throws:
PositionOutOfBoundsException - p is not a valid position

findPosition

protected int findPosition(E value)
Parameters:
value - the element to be located
Returns:
the first position 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.

contains

public boolean contains(E value)
Description copied from class: AbstractCollection
This implementation for contains takes linear time, so it is overridden by a more efficient method in most data structure implementations.

Specified by:
contains in interface Collection<E>
Overrides:
contains in class AbstractCollection<E>
Parameters:
value - the element to be located
Returns:
true if and only if an equivalent element exists in the collection

positionOf

public int positionOf(E value)
Description copied from interface: PositionalCollection
Returns the position of the first occurrence (if any) of an element equivalent to 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.)

Specified by:
positionOf in interface PositionalCollection<E>
Parameters:
value - the element to be located
Returns:
the position in the collection for the first occurrence (if any) of an element equivalent to value.
Throws:
NoSuchElementException - no element in the collection is equivalent to value

moveElementsTo

protected Object[] moveElementsTo(Object[] newArray)
Parameters:
newArray - the array to which the elements should be moved
Returns:
the parameter value for convenience

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 AbstractCollection<E>
Parameters:
capacity - the desired capacity

trimToSize

public void trimToSize()
Reduces the capacity of the array to the current number of elements in the collection

Specified by:
trimToSize in interface Collection<E>
Overrides:
trimToSize in class AbstractCollection<E>

set

public E set(int p,
             E value)
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>
Parameters:
p - a user position to update
value - the element to put at position p
Returns:
the prior element at position p
Throws:
PositionOutOfBoundsException - p is not a valid position

swap

public void swap(int pos1,
                 int pos2)
Swaps the values held in positions pos1 and pos2

Specified by:
swap in interface PositionalCollection<E>
Parameters:
pos1 - a valid position
pos2 - a valid position
Throws:
PositionOutOfBoundsException - either pos1 or pos2 is not a valid position

createGap

protected void createGap(int p)
Moves elements at positions p, ..., size-1 to positions p+1, ..., size.

Parameters:
p - a valid user position where the gap is to be created

add

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

Specified by:
add in interface PositionalCollection<E>
Parameters:
p - a valid user position
value - the new element
Throws:
PositionOutOfBoundsException - p is neither size nor a valid position
AtCapacityException - the underlying array is already at capacity

add

public void add(E value)
Inserts it at the end of the collection.

Specified by:
add in interface Collection<E>
Parameters:
value - the new element
Throws:
AtCapacityException - the underlying array is already at capacity

closeGap

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). We use Arrays.fill to set all slots in the underlying array that are no longer in use to null.

Parameters:
fromPos - the first position in the gap to close
toPos - the last position in the gap to close

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

remove

public E remove(int p)
Removes the element at position p and shifts elements u_{p+1}, ..., u_{size-1} left by one position.

Specified by:
remove in interface PositionalCollection<E>
Parameters:
p - a valid position
Returns:
the removed element
Throws:
PositionOutOfBoundsException - p is not a valid position

removeFirst

public final E removeFirst()
Removes the element at position 0 and decrements the position for the elements that were at positions 1 to size-1.

Specified by:
removeFirst in interface PositionalCollection<E>
Returns:
the element that was removed
Throws:
NoSuchElementException - the collection is empty

removeLast

public final E removeLast()
Removes the element at position size-1

Specified by:
removeLast in interface PositionalCollection<E>
Returns:
the element that was removed
Throws:
NoSuchElementException - the collection is empty

remove

public boolean remove(E value)
Removes the first element in the collection equivalent to value

Specified by:
remove in interface Collection<E>
Parameters:
value - the element to be removed
Returns:
true if and only if an element is removed.

clear

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

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

traverseForVisitor

public void traverseForVisitor(Visitor<? super E> v)
                        throws Exception
Traverses the entire collection on behalf of v.

Overrides:
traverseForVisitor in class AbstractCollection<E>
Parameters:
v - a visitor to apply for each element in the collection
Throws:
Exception - the visitor throws an exception.

iterator

public PositionalCollectionLocator<E> iterator()
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>
Specified by:
iterator in class AbstractPositionalCollection<E>

iteratorAtEnd

public PositionalCollectionLocator<E> iteratorAtEnd()
Creates a new marker that starts at AFT.

Specified by:
iteratorAtEnd in interface PositionalCollection<E>
Specified by:
iteratorAtEnd in class AbstractPositionalCollection<E>

iteratorAt

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

Specified by:
iteratorAt in class AbstractPositionalCollection<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>
Parameters:
value - the target
Returns:
a marker initialized to the position of the first element in the collection equivalent to value
Throws:
NoSuchElementException - value does not occur in the collection

insertionsort

public void insertionsort()
Description copied from interface: PositionalCollection
Sorts this collection with insertion sort using the default comparator.

Specified by:
insertionsort in interface PositionalCollection<E>

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>
Parameters:
comp - the comparator to use to order the elements

mergesort

public void mergesort()
Uses the default comparator to order the elements

Specified by:
mergesort in interface PositionalCollection<E>

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>
Parameters:
comp - the comparator that defines the ordering of the elements

heapsort

public void heapsort()
Sorts this collection with heap sort using the default comparator

Specified by:
heapsort in interface PositionalCollection<E>

heapsort

public void heapsort(Comparator<? super E> comp)
Sorts this collection with heap sort using the provided comparator

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

treesort

public void treesort()
Sorts this collection using the tree sort algorithm and the default comparator

Specified by:
treesort in interface PositionalCollection<E>

treesort

public void treesort(Comparator<? super E> comp)
Sorts this collection using the tree sort algorithm and the provided comparator

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

quicksort

public void quicksort()
Sorts this collection with quicksort using the default comparator

Specified by:
quicksort in interface PositionalCollection<E>

quicksort

public void quicksort(Comparator<? super E> comp)
Sorts this collection with quicksort using the provided comparator

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

radixsort

public void radixsort(Digitizer<? super E> digitizer)
And sorts the collection with radix sort.

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

radixsortImpl

protected void radixsortImpl(Digitizer<? super E> digitizer)
Is the complete implementation of radix sort

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>
Parameters:
bucketizer - the bucketizer to use

bucketsortImpl

protected void bucketsortImpl(Bucketizer<? super E> bucketizer)
And sorts the array using bucket sort

Parameters:
bucketizer - the bucketizer to use

repositionElementByRank

public E repositionElementByRank(int r)
Description copied from interface: PositionalCollection
Modifies the positional collection so element in position r is in its proper sorted order when using the default comparator, and returns that element. This method does not completely sort the collection, but it may mutate it.

Specified by:
repositionElementByRank in interface PositionalCollection<E>
Parameters:
r - the rank of the desired element in the sorted collection
Returns:
the element at rank r when using the default comparator
Throws:
PositionOutOfBoundsException - r is not a valid position

repositionElementByRank

public E repositionElementByRank(int r,
                                 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>
Parameters:
r - 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
Throws:
noSuchElementException - the collection is empty or r is not a valid position