Class LazySortedCollection
java.lang.Object
org.eclipse.jface.viewers.deferred.LazySortedCollection
This object maintains a collection of elements, sorted by a comparator
given in the constructor. The collection is lazily sorted, allowing
more efficient runtimes for most methods. There are several methods on this
object that allow objects to be queried by their position in the sorted
collection.
This is a modified binary search tree. Each subtree has a value, a left and right subtree, a count of the number of children, and a set of unsorted children. Insertion happens lazily. When a new node N is inserted into a subtree T, it is initially added to the set of unsorted children for T without actually comparing it with the value for T.
The unsorted children will remain in the unsorted set until some subsequent operation requires us to know the exact set of elements in one of the subtrees. At that time, we partition T by comparing all of its unsorted children with T's value and moving them into the left or right subtrees.
 Since:
 3.1

Field Summary
Modifier and TypeFieldDescriptionboolean
Disables randomization and enables additional runtime error checking. 
Constructor Summary
ConstructorDescriptionCreates a new sorted collection using the given comparator to determine sort order. 
Method Summary
Modifier and TypeMethodDescriptionfinal void
Adds the given object to the collection.final void
Adds all items from the given array to the collectionfinal void
addAll
(Collection toAdd) Adds all items from the given collection to this collectionfinal void
clear()
Removes all elements from the collectionboolean
Returns true iff this collection contains the given itemReturns the comparator that is determining the sort order for this collectionfinal int
Fills in an array of size n with the n smallest elements from the collection.final Object
getItem
(int index) Returns the item at the given index.final Object[]
getItems
(boolean sorted) Returns the contents of this collection as a sorted or unsorted array.final int
Computes the n through n+k items in this collection.final boolean
isEmpty()
Returns true iff the collection is emptyfinal void
Removes the given object from the collection.final void
Removes all elements in the given array from this collection.final void
removeRange
(int first, int length) Removes all elements in the given range from this collection.final void
retainFirst
(int n) Retains the n smallest items in the collection, removing the rest.final void
setCapacity
(int newSize) Increases the capacity of this collection, if necessary, so that it can hold the given number of elements.int
size()
Returns the number of elements in the collectionvoid
Tests if this object's internal state is valid.

Field Details

enableDebug
public boolean enableDebugDisables randomization and enables additional runtime error checking. Severely degrades performance if set to true. Intended for use in test suites only.


Constructor Details

LazySortedCollection
Creates a new sorted collection using the given comparator to determine sort order. Parameters:
c
 comparator that determines the sort order


Method Details

testInvariants
public void testInvariants()Tests if this object's internal state is valid. Throws a runtime exception if the state is invalid, indicating a programming error in this class. This method is intended for use in test suites and should not be called by clients. 
size
public int size()Returns the number of elements in the collection Returns:
 the number of elements in the collection

setCapacity
public final void setCapacity(int newSize) Increases the capacity of this collection, if necessary, so that it can hold the given number of elements. This can be used prior to a sequence of additions to avoid memory reallocation. This cannot be used to reduce the amount of memory used by the collection. Parameters:
newSize
 capacity for this collection

add
Adds the given object to the collection. Runs in O(1) amortized time. Parameters:
toAdd
 object to add

addAll
Adds all items from the given collection to this collection Parameters:
toAdd
 objects to add

addAll
Adds all items from the given array to the collection Parameters:
toAdd
 objects to add

isEmpty
public final boolean isEmpty()Returns true iff the collection is empty Returns:
 true iff the collection contains no elements

remove
Removes the given object from the collection. Has no effect if the element does not exist in this collection. Parameters:
toRemove
 element to remove

removeAll
Removes all elements in the given array from this collection. Parameters:
toRemove
 elements to remove

retainFirst
public final void retainFirst(int n) Retains the n smallest items in the collection, removing the rest. When this method returns, the size of the collection will be n. Note that this is a noop if n > the current size of the collection. Parameters:
n
 number of items to retain

removeRange
public final void removeRange(int first, int length) Removes all elements in the given range from this collection. For example, removeRange(10, 3) would remove the 11th through 13th smallest items from the collection. Parameters:
first
 0based index of the smallest item to removelength
 number of items to remove

clear
public final void clear()Removes all elements from the collection 
getComparator
Returns the comparator that is determining the sort order for this collection Returns:
 comparator for this collection

getFirst
Fills in an array of size n with the n smallest elements from the collection. Can compute the result in sorted or unsorted order. Parameters:
result
 array to be filledsorted
 if true, the result array will be sorted. If false, the result array may be unsorted. This does not affect which elements appear in the result. It only affects their order. Computing an unsorted result is asymptotically faster. Returns:
 the number of items inserted into the result array. This will be equal to the minimum of result.length and container.size()

getRange
Computes the n through n+k items in this collection. Computing the result in unsorted order is more efficient. Sorting the result will not change which elements actually show up in the result. That is, even if the result is unsorted, it will still contain the same elements as would have been at that range in a fully sorted collection. Parameters:
result
 array containing the resultrangeStart
 index of the first element to be inserted into the result arraysorted
 true iff the result will be computed in sorted order Returns:
 the number of items actually inserted into the result array (will be the minimum of result.length and this.size())

getItem
Returns the item at the given index. Indexes are based on sorted order. Parameters:
index
 index to test Returns:
 the item at the given index

getItems
Returns the contents of this collection as a sorted or unsorted array. Computing an unsorted array is more efficient. Parameters:
sorted
 if true, the result will be in sorted order. If false, the result may be in unsorted order. Returns:
 the contents of this collection as an array.

contains
Returns true iff this collection contains the given item Parameters:
item
 item to test Returns:
 true iff this collection contains the given item
