public class LazySortedCollection extends Object
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.
Modifier and Type  Field and Description 

boolean 
enableDebug
Disables randomization and enables additional runtime error checking.

Constructor and Description 

LazySortedCollection(Comparator c)
Creates a new sorted collection using the given comparator to determine
sort order.

Modifier and Type  Method and Description 

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.

public boolean enableDebug
public LazySortedCollection(Comparator c)
c
 comparator that determines the sort orderpublic void testInvariants()
public int size()
public final void setCapacity(int newSize)
newSize
 capacity for this collectionpublic final void add(Object toAdd)
toAdd
 object to addpublic final void addAll(Collection toAdd)
toAdd
 objects to addpublic final void addAll(Object[] toAdd)
toAdd
 objects to addpublic final boolean isEmpty()
public final void remove(Object toRemove)
toRemove
 element to removepublic final void removeAll(Object[] toRemove)
toRemove
 elements to removepublic final void retainFirst(int n)
n
 number of items to retainpublic final void removeRange(int first, int length)
first
 0based index of the smallest item to removelength
 number of items to removepublic final void clear()
public Comparator getComparator()
public final int getFirst(Object[] result, boolean sorted)
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.public final int getRange(Object[] result, int rangeStart, boolean sorted)
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 orderpublic final Object getItem(int index)
index
 index to testpublic final Object[] getItems(boolean sorted)
sorted
 if true, the result will be in sorted order. If false,
the result may be in unsorted order.public boolean contains(Object item)
item
 item to test
Copyright (c) 2000, 2013 Eclipse Contributors and others. All rights reserved.Guidelines for using Eclipse APIs.