|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
public interface OrderedCollection<E>
An ordered collection is an untagged algorithmically
positioned collection of comparable elements that
may contain duplicates. That is, order is defined by a comparator
and the collection may
contain multiple "equal" elements and multiple occurrences
of the same element. The primary methods are to
add an element, determine if an element is in the collection,
to remove an element, and to find the previous or next element
in the ordering defined by the comparator.
The iteration order must follow the ordering defined by
the comparator. Data structures
for an ordered collection typically provide logarithmic time
implementations for these methods. However, in some cases
the data structures support constant time implementations, or
require linear time implementations.
An ordered collection supports methods that concern order
such as min
, max
, predecessor
, and
successor
and methods that allow the
user application to efficiently perform queries such as a range search in which one can iterate
through all elements in the collection between a specified range of values.
Method Summary | |
---|---|
E |
get(int r)
Returns the rth element in the sorted order, where r=0 is the minimum element. |
E |
getEquivalentElement(E target)
Returns an element in the collection that is equivalent to target according to the comparator
associated with this collection. |
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 x)
Returns a greatest element in the ordered collection that is less than x . |
E |
successor(E x)
Returns a least element in the ordered collection that is greater than x . |
Methods inherited from interface goldman.collection.Collection |
---|
accept, add, addAll, checkRep, clear, contains, ensureCapacity, getCapacity, getComparator, getLocator, getSize, isEmpty, iterator, remove, retainAll, toArray, toArray, toString, trimToSize |
Method Detail |
---|
E get(int r)
IllegalArgumentException
when r < 0 or r ≥ n.
E getEquivalentElement(E target)
target
according to the comparator
associated with this collection.
It throws a NoSuchElementException
when
there is no equivalent element.
getEquivalentElement
in interface Collection<E>
Locator<E> iteratorAtEnd()
E min()
NoSuchElementException
when the collection is empty.
E max()
NoSuchElementException
when the collection is empty.
E predecessor(E x)
x
.
If x
is in the collection,
the element before the first occurrence of x
in the iteration order is returned.
Note that x
need not be an element
of the collection for predecessor
to return a value. It throws
a NoSuchElementException
when there is no element in the collection
smaller than x
. (The element returned would be the last element in the collection
returned by the method call headSet(x)
in Java's SortedSet
interface.)
E successor(E x)
x
.
If x
is in the collection, the element after the last occurrence of
x
in the iteration order is returned.
Note that x
need not be an element
of the collection for successor
to return a value. It throws
a NoSuchElementException
when there is no element in the collection
larger than x
. (The element returned would be the first element in the collection
returned by the method call tailSet(x)
in Java's SortedSet
interface.
If an application needs to iterate through tailSet(x)
, the
getLocator
method in conjunction with advance
could
be used.
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |