org.eclipse.jface.viewers.deferred
Class LazySortedCollection
java.lang.Object
org.eclipse.jface.viewers.deferred.LazySortedCollection
-
public class LazySortedCollection
- extends
Object
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
|
boolean
|
enableDebug
Disables randomization and enables additional runtime error checking. |
|
Method Summary
|
void
|
add
(
Object toAdd)
Adds the given object to the collection. |
void
|
addAll
(
Collection toAdd)
Adds all items from the given collection to this collection |
void
|
addAll
(
Object[] toAdd)
Adds all items from the given array to the collection |
void
|
clear
()
Removes all elements from the collection |
boolean
|
contains
(
Object item)
Returns true iff this collection contains the given item |
Comparator
|
getComparator
()
Returns the comparator that is determining the sort order for this collection |
int
|
getFirst
(
Object[] result,
boolean sorted)
Fills in an array of size n with the n smallest elements from the collection. |
Object
|
getItem
(int index)
Returns the item at the given index. |
Object[]
|
getItems
(boolean sorted)
Returns the contents of this collection as a sorted or unsorted
array. |
int
|
getRange
(
Object[] result,
int rangeStart,
boolean sorted)
Computes the n through n+k items in this collection. |
boolean
|
isEmpty
()
Returns true iff the collection is empty |
void
|
remove
(
Object toRemove)
Removes the given object from the collection. |
void
|
removeAll
(
Object[] toRemove)
Removes all elements in the given array from this collection. |
void
|
removeRange
(int first,
int length)
Removes all elements in the given range from this collection. |
void
|
retainFirst
(int n)
Retains the n smallest items in the collection, removing the rest. |
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 collection |
void
|
testInvariants
()
Tests if this object's internal state is valid. |
|
Methods inherited from class java.lang.
Object
|
clone,
equals,
finalize,
getClass,
hashCode,
notify,
notifyAll,
toString,
wait,
wait,
wait
|
enableDebug
public boolean enableDebug
- Disables randomization and enables additional runtime error checking.
Severely degrades performance if set to true. Intended for use in test
suites only.
LazySortedCollection
public LazySortedCollection(
Comparator c)
- Creates a new sorted collection using the given comparator to determine
sort order.
-
Parameters:
-
c - comparator that determines the sort order
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
public final void add(
Object toAdd)
- Adds the given object to the collection. Runs in O(1) amortized time.
-
-
Parameters:
-
toAdd - object to add
addAll
public final void addAll(
Collection toAdd)
- Adds all items from the given collection to this collection
-
-
Parameters:
-
toAdd - objects to add
addAll
public final void addAll(
Object[] toAdd)
- 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
public final void remove(
Object toRemove)
- 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
public final void removeAll(
Object[] toRemove)
- 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 no-op 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 - 0-based index of the smallest item to remove -
length - number of items to remove
clear
public final void clear()
- Removes all elements from the collection
-
getComparator
public
Comparator getComparator()
- Returns the comparator that is determining the sort order for this collection
-
-
Returns:
- comparator for this collection
getFirst
public final int getFirst(
Object[] result,
boolean sorted)
- 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 filled -
sorted - 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
public final int getRange(
Object[] result,
int rangeStart,
boolean sorted)
- 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 result -
rangeStart - index of the first element to be inserted into the result array -
sorted - 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
public final
Object getItem(int index)
- 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
public final
Object[] getItems(boolean sorted)
- 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
public boolean contains(
Object item)
- Returns true iff this collection contains the given item
-
-
Parameters:
-
item - item to test
-
Returns:
- true iff this collection contains the given item
Guidelines for using Eclipse APIs.
Copyright (c) Eclipse contributors and others 2000, 2008. All rights reserved.
