Follow Techotopia on Twitter

On-line Guides
All Guides
eBook Store
iOS / Android
Linux for Beginners
Office Productivity
Linux Installation
Linux Security
Linux Utilities
Linux Virtualization
Linux Kernel
System/Network Admin
Programming
Scripting Languages
Development Tools
Web Development
GUI Toolkits/Desktop
Databases
Mail Systems
openSolaris
Eclipse Documentation
Techotopia.com
Virtuatopia.com

How To Guides
Virtualization
General System Admin
Linux Security
Linux Filesystems
Web Servers
Graphics & Desktop
PC Hardware
Windows
Problem Solutions
Privacy Policy

  




 

 


Eclipse Platform
Release 3.5

org.eclipse.jface.viewers.deferred
Class LazySortedCollection

java.lang.Object
  extended by 
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.
 
Constructor Summary
LazySortedCollection ( Comparator c)
          Creates a new sorted collection using the given comparator to determine sort order.
 
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
 

Field Detail

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.

Constructor Detail

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
Method Detail

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

Eclipse Platform
Release 3.5

Guidelines for using Eclipse APIs.

Copyright (c) Eclipse contributors and others 2000, 2008. All rights reserved.


 
 
  Published under the terms of the Eclipse Public License Version 1.0 ("EPL") Design by Interspire