|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectgoldman.collection.AbstractCollection<E>
goldman.collection.ordered.SortedArray<E>
public class SortedArray<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 |
---|
public SortedArray()
public SortedArray(Comparator<? super E> comp)
comp
- the comparator to use to
order the elementspublic SortedArray(int capacity)
capacity
- the capacity for
the arraypublic SortedArray(Comparator<? super E> comp, int capacity)
comp
- the user-provided
comparatorcapacity
- the capacity for
the arrayMethod Detail |
---|
public boolean isEmpty()
Collection
isEmpty
in interface Collection<E>
isEmpty
in class AbstractCollection<E>
public int getSize()
Collection
getSize
in interface Collection<E>
getSize
in class AbstractCollection<E>
public int getCapacity()
AbstractCollection
Integer.MAX_VALUE
.
getCapacity
in interface Collection<E>
getCapacity
in class AbstractCollection<E>
public void ensureCapacity(int desiredCapacity)
AbstractCollection
capacity
elements.
ensureCapacity
in interface Collection<E>
ensureCapacity
in class AbstractCollection<E>
desiredCapacity
- the desired capacity for the collectionpublic void trimToSize()
AbstractCollection
trimToSize
in interface Collection<E>
trimToSize
in class AbstractCollection<E>
public boolean contains(E target)
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>
target
- the element being tested for membership in the collection
public E get(int r)
OrderedCollection
IllegalArgumentException
when r < 0 or r ≥ n.
get
in interface OrderedCollection<E>
r
- the desired rank
IllegalArgumentException
- r < 0 or r ≥ npublic E getEquivalentElement(E element)
Collection
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.
getEquivalentElement
in interface Collection<E>
getEquivalentElement
in interface OrderedCollection<E>
getEquivalentElement
in class AbstractCollection<E>
element
- the target
NoSuchElementException
- there is no equivalent element in this
collection.public E min()
OrderedCollection
NoSuchElementException
when the collection is empty.
min
in interface OrderedCollection<E>
NoSuchElementException
- the collection is empty.public E max()
OrderedCollection
NoSuchElementException
when the collection is empty.
max
in interface OrderedCollection<E>
NoSuchElementException
- the collection is empty.protected int findFirstInsertPosition(int left, int right, E target)
left
- the beginning index of the portion of the array to searchright
- the ending index of the portion of the array to searchtarget
- the value to search for
left
≤ right
< size
and that a[left
-1] < target
< a[right
+1].
public E predecessor(E target)
target
be in the collection.
predecessor
in interface OrderedCollection<E>
target
- the element for which to find
the predecessor
target
.
NoSuchElementException
- no element in the collection
is smaller than target
protected int findLastInsertPosition(int left, int right, E target)
left
- the beginning index of the portion of the array to searchright
- the ending index of the portion of the array to searchtarget
- the value to search for
left
≤ right
< size
and that a[left
-1] < target
< a[right
+1].
public E successor(E target)
target
be in the collection.
successor
in interface OrderedCollection<E>
target
- the element for which to find
the successor
target
NoSuchElementException
- no element in the collection
is greater than target
public void add(E element)
add
in interface Collection<E>
element
- the new elementpublic void addAll(Collection<? extends E> c)
c
to the collection.
addAll
in interface Collection<E>
addAll
in class AbstractCollection<E>
c
- the collection to be addedpublic boolean remove(E element)
element
, if such an element exists in the collection.
remove
in interface Collection<E>
element
- the element to remove
true
if an element was removed, and false
otherwise.public void retainAll(Collection<E> c)
c
retainAll
in interface Collection<E>
retainAll
in class AbstractCollection<E>
c
- a collectionprotected void set(int pos, E value)
pos
- the desired positionvalue
- the value to be added at position pos
PositionOutOfBoundsException
- pos
is
not a valid position in a
.
IllegalArgumentException
- performing
this operation would violate the property Orderedprotected void add(int pos, E element)
pos
- the desired positionelement
- the element to be added at position pos
PositionOutOfBoundsException
- pos
is
not a valid position for adding to a
.
IllegalArgumentException
- performing
this operation would violate the property Orderedprotected E remove(int pos)
pos
- the position of the
element to removed
PositionOutOfBoundsException
- p
is
not a valid position in a
.public Locator<E> iterator()
Collection
iterator
in interface Collection<E>
iterator
in interface Iterable<E>
public Locator<E> iteratorAtEnd()
OrderedCollection
iteratorAtEnd
in interface OrderedCollection<E>
public Locator<E> getLocator(E element)
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>
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |