goldman.collection.ordered
Class SortedArray<E>

java.lang.Object
  extended by goldman.collection.AbstractCollection<E>
      extended by goldman.collection.ordered.SortedArray<E>
All Implemented Interfaces:
Collection<E>, OrderedCollection<E>, Iterable<E>

public class SortedArray<E>
extends AbstractCollection<E>
implements OrderedCollection<E>

The sorted array provides very efficient use of space and the fastest search time independent of the access pattern. Also, the sorted array provides constant time access to the element at a given rank. However, this data structure has a very significant drawback: adding or removing an element requires shifting all elements that follow it. Thus, this data structure is a good choice only when the elements added or removed are near the maximum, or when there are few mutations after inserting all elements.


Nested Class Summary
 
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
SortedArray()
           
SortedArray(Comparator<? super E> comp)
           
SortedArray(Comparator<? super E> comp, int capacity)
          This constructor should not be used if the array should be automatically resized.
SortedArray(int capacity)
          This constructor should not be used if the array should be automatically resized.
 
Method Summary
 void add(E element)
          Inserts it into the collection.
protected  void add(int pos, E element)
           
 void addAll(Collection<? extends E> c)
          Adds all elements in c to the collection.
 boolean contains(E target)
          This implementation for contains takes linear time, so it is overridden by a more efficient method in most data structure implementations.
 void ensureCapacity(int desiredCapacity)
          Increases the capacity of the collection, if necessary, to ensure that it can hold at least capacity elements.
protected  int findFirstInsertPosition(int left, int right, E target)
           
protected  int findLastInsertPosition(int left, int right, E target)
           
 E get(int r)
          Returns the rth element in the sorted order, where r=0 is the minimum element.
 int getCapacity()
          By default this method returns Integer.MAX_VALUE.
 E getEquivalentElement(E element)
          Returns an element in the collection that is equivalent to target.
 Locator<E> getLocator(E element)
          Returns a locator that has been initialized to an element equivalent to target.
 int getSize()
          Returns the number of elements, size, in this collection.
 boolean isEmpty()
          Returns true if this collection contains no elements, and otherwise returns false.
 Locator<E> iterator()
          Returns a locator that has been initialized to FORE.
 Locator<E> iteratorAtEnd()
          Returns a locator that has been initialized to AFT.
 E max()
          Returns a greatest element in the collection (according to the comparator).
 E min()
          Returns a least element in the collection (according to the comparator).
 E predecessor(E target)
          This method does not require that target be in the collection.
 boolean remove(E element)
          Removes an arbitrary element from the collection equivalent to element, if such an element exists in the collection.
protected  E remove(int pos)
           
 void retainAll(Collection<E> c)
          Updates the current collection to contain only elements that are also in c
protected  void set(int pos, E value)
           
 E successor(E target)
          This method does not require that target be in the collection.
 void trimToSize()
          Trims the capacity of this collection to be its current size.
 
Methods inherited from class goldman.collection.AbstractCollection
accept, checkRep, clear, compare, equivalent, getComparator, getElementAtRank, getElementAtRank, toArray, toArray, toString, traverseForVisitor, writeElements
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface goldman.collection.Collection
accept, checkRep, clear, getComparator, toArray, toArray, toString
 

Constructor Detail

SortedArray

public SortedArray()

SortedArray

public SortedArray(Comparator<? super E> comp)
Parameters:
comp - the comparator to use to order the elements

SortedArray

public SortedArray(int capacity)
This constructor should not be used if the array should be automatically resized.

Parameters:
capacity - the capacity for the array

SortedArray

public SortedArray(Comparator<? super E> comp,
                   int capacity)
This constructor should not be used if the array should be automatically resized.

Parameters:
comp - the user-provided comparator
capacity - the capacity for the array
Method Detail

isEmpty

public boolean isEmpty()
Description copied from interface: Collection
Returns true if this collection contains no elements, and otherwise returns false.

Specified by:
isEmpty in interface Collection<E>
Overrides:
isEmpty in class AbstractCollection<E>
Returns:
true if and only if no elements are stored in the collection

getSize

public int getSize()
Description copied from interface: Collection
Returns the number of elements, size, in this collection.

Specified by:
getSize in interface Collection<E>
Overrides:
getSize in class AbstractCollection<E>
Returns:
the number of elements stored in the collection

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.

ensureCapacity

public void ensureCapacity(int desiredCapacity)
Description copied from class: AbstractCollection
Increases the capacity of the collection, if necessary, to ensure that it can hold at least capacity elements.

Specified by:
ensureCapacity in interface Collection<E>
Overrides:
ensureCapacity in class AbstractCollection<E>
Parameters:
desiredCapacity - the desired capacity for the collection

trimToSize

public void trimToSize()
Description copied from class: AbstractCollection
Trims the capacity of this collection to be its current size. An application can use this operation to minimize space usage.

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

contains

public boolean contains(E target)
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:
target - the element being tested for membership in the collection
Returns:
true if and only if an equivalent element exists in the collection

get

public E get(int r)
Description copied from interface: OrderedCollection
Returns the rth element in the sorted order, where r=0 is the minimum element. It throws an IllegalArgumentException when r < 0 or r ≥ n.

Specified by:
get in interface OrderedCollection<E>
Parameters:
r - the desired rank
Returns:
the rth element in the sorted order, where r=0 is the minimum element
Throws:
IllegalArgumentException - r < 0 or r ≥ n

getEquivalentElement

public E getEquivalentElement(E element)
Description copied from interface: Collection
Returns an element in the collection that is equivalent to target. It throws a NoSuchElementException when there is no equivalent element. The contains method should be used to determine if an element is in the collection.

Specified by:
getEquivalentElement in interface Collection<E>
Specified by:
getEquivalentElement in interface OrderedCollection<E>
Overrides:
getEquivalentElement in class AbstractCollection<E>
Parameters:
element - the target
Returns:
an equivalent element from the collection
Throws:
NoSuchElementException - there is no equivalent element in this collection.

min

public E min()
Description copied from interface: OrderedCollection
Returns a least element in the collection (according to the comparator). More specifically, the first element in the iteration order is returned. This method throws a NoSuchElementException when the collection is empty.

Specified by:
min in interface OrderedCollection<E>
Returns:
a smallest element in the collection.
Throws:
NoSuchElementException - the collection is empty.

max

public E max()
Description copied from interface: OrderedCollection
Returns a greatest element in the collection (according to the comparator). More specifically, the last element in the iteration order is returned. This method throws a NoSuchElementException when the collection is empty.

Specified by:
max in interface OrderedCollection<E>
Returns:
a largest element in the collection.
Throws:
NoSuchElementException - the collection is empty.

findFirstInsertPosition

protected int findFirstInsertPosition(int left,
                                      int right,
                                      E target)
Parameters:
left - the beginning index of the portion of the array to search
right - the ending index of the portion of the array to search
target - the value to search for
REQUIRES: that 0 ≤ leftright < size and that a[left-1] < target < a[right+1].
Returns:
the insert position for the element that would place it before any equivalent elements

predecessor

public E predecessor(E target)
This method does not require that target be in the collection.

Specified by:
predecessor in interface OrderedCollection<E>
Parameters:
target - the element for which to find the predecessor
Returns:
the largest element in the ordered collection that is less than target.
Throws:
NoSuchElementException - no element in the collection is smaller than target

findLastInsertPosition

protected int findLastInsertPosition(int left,
                                     int right,
                                     E target)
Parameters:
left - the beginning index of the portion of the array to search
right - the ending index of the portion of the array to search
target - the value to search for
REQUIRES: that 0 ≤ leftright < size and that a[left-1] < target < a[right+1].
Returns:
the last position where the element occurs, or otherwise the insert position

successor

public E successor(E target)
This method does not require that target be in the collection.

Specified by:
successor in interface OrderedCollection<E>
Parameters:
target - the element for which to find the successor
Returns:
the smallest element in the ordered collection that is greater than target
Throws:
NoSuchElementException - no element in the collection is greater than target

add

public void add(E element)
Inserts it into the collection.

Specified by:
add in interface Collection<E>
Parameters:
element - the new element

addAll

public void addAll(Collection<? extends E> c)
Adds all elements in c to the collection.

Specified by:
addAll in interface Collection<E>
Overrides:
addAll in class AbstractCollection<E>
Parameters:
c - the collection to be added

remove

public boolean remove(E element)
Removes an arbitrary element from the collection equivalent to element, if such an element exists in the collection.

Specified by:
remove in interface Collection<E>
Parameters:
element - the element to remove
Returns:
true if an element was removed, and false otherwise.

retainAll

public void retainAll(Collection<E> c)
Updates the current collection to contain only elements that are also in c

Specified by:
retainAll in interface Collection<E>
Overrides:
retainAll in class AbstractCollection<E>
Parameters:
c - a collection

set

protected void set(int pos,
                   E value)
Parameters:
pos - the desired position
value - the value to be added at position pos
Throws:
PositionOutOfBoundsException - pos is not a valid position in a.
IllegalArgumentException - performing this operation would violate the property Ordered

add

protected void add(int pos,
                   E element)
Parameters:
pos - the desired position
element - the element to be added at position pos
Throws:
PositionOutOfBoundsException - pos is not a valid position for adding to a.
IllegalArgumentException - performing this operation would violate the property Ordered

remove

protected E remove(int pos)
Parameters:
pos - the position of the element to removed
Returns:
the removed element
Throws:
PositionOutOfBoundsException - p is not a valid position in a.

iterator

public Locator<E> iterator()
Description copied from interface: Collection
Returns a locator that has been initialized to FORE. The locator returned can be used to navigate within the collection and to remove the element currently associated with the locator. In general, no assumption is made about the iteration order, the order in which the iterator advances through the collection. However, some collection ADTs specify a particular iteration order.

Specified by:
iterator in interface Collection<E>
Specified by:
iterator in interface Iterable<E>

iteratorAtEnd

public Locator<E> iteratorAtEnd()
Description copied from interface: OrderedCollection
Returns a locator that has been initialized to AFT.

Specified by:
iteratorAtEnd in interface OrderedCollection<E>

getLocator

public Locator<E> getLocator(E element)
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>