goldman.collection.ordered
Interface OrderedCollection<E>

All Superinterfaces:
Collection<E>, Iterable<E>
All Known Subinterfaces:
DigitizedOrderedCollection<E>
All Known Implementing Classes:
BalancedBinarySearchTree, BinarySearchTree, BPlusTree, BTree, CompactTrie, CompressedTrie, PatriciaTrie, RedBlackTree, SkipList, SortedArray, SplayTree, TernarySearchTrie, TopDownBTree, Trie

public interface OrderedCollection<E>
extends Collection<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

get

E get(int r)
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.


getEquivalentElement

E getEquivalentElement(E target)
Returns an element in the collection that is equivalent to target according to the comparator associated with this collection. It throws a NoSuchElementException when there is no equivalent element.

Specified by:
getEquivalentElement in interface Collection<E>

iteratorAtEnd

Locator<E> iteratorAtEnd()
Returns a locator that has been initialized to AFT.


min

E min()
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.


max

E max()
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.


predecessor

E predecessor(E x)
Returns a greatest element in the ordered collection that is less than 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.)


successor

E successor(E x)
Returns a least element in the ordered collection that is greater than 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.