Attachment 14992 Details for Bug 72358 – o.e.jface patch

Some Eclipse Foundation services are deprecated, or will be soon. Please ensure you've read this important communication.

[patch] o.e.jface patch

jface_patch.txt (text/plain), 92.04 KB, created by Stefan Xenos

on 2004-10-04 22:15:25 EDT

(hide)

Description:

Filename:

MIME Type:

Creator: Stefan Xenos

Created: 2004-10-04 22:15:25 EDT

Size: 92.04 KB

patch

obsolete

>Index: src/org/eclipse/jface/viewers/deferred/AbstractConcurrentContentProvider.java
>===================================================================
>RCS file: src/org/eclipse/jface/viewers/deferred/AbstractConcurrentContentProvider.java
>diff -N src/org/eclipse/jface/viewers/deferred/AbstractConcurrentContentProvider.java
>--- /dev/null	1 Jan 1970 00:00:00 -0000
>+++ src/org/eclipse/jface/viewers/deferred/AbstractConcurrentContentProvider.java	1 Jan 1970 00:00:00 -0000
>@@ -0,0 +1,66 @@
>+/*******************************************************************************
>+ * Copyright (c) 2004 IBM Corporation and others.
>+ * All rights reserved. This program and the accompanying materials 
>+ * are made available under the terms of the Common Public License v1.0
>+ * which accompanies this distribution, and is available at
>+ * http://www.eclipse.org/legal/cpl-v10.html
>+ * 
>+ * Contributors:
>+ * IBM Corporation - initial API and implementation
>+ *******************************************************************************/
>+package org.eclipse.jface.viewers.deferred;
>+
>+import org.eclipse.jface.util.ListenerList;
>+
>+/**
>+ * @since 3.1
>+ */
>+public abstract class AbstractConcurrentContentProvider implements
>+ IConcurrentContentProvider {
>+
>+ private ListenerList listeners = new ListenerList(); 
>+ 
>+ /* (non-Javadoc)
>+ * @see org.eclipse.jface.viewers.deferred.IConcurrentContentProvider#addListener(org.eclipse.jface.viewers.deferred.IConcurrentContentProviderListener)
>+ */
>+ public void addListener(IConcurrentContentProviderListener listener) {
>+ listeners.add(listener);
>+ }
>+ 
>+ protected void fireAdd(Object[] added) {
>+ Object[] listenerArray = listeners.getListeners();
>+ 
>+ for (int i = 0; i < listenerArray.length; i++) {
>+ IConcurrentContentProviderListener next = (IConcurrentContentProviderListener) listenerArray[i];
>+ 
>+ next.add(added);
>+ }
>+ }
>+
>+ protected void fireRemove(Object[] removed) {
>+ Object[] listenerArray = listeners.getListeners();
>+ 
>+ for (int i = 0; i < listenerArray.length; i++) {
>+ IConcurrentContentProviderListener next = (IConcurrentContentProviderListener) listenerArray[i];
>+ 
>+ next.remove(removed);
>+ }
>+ }
>+ 
>+ protected void fireUpdate(Object[] updated) {
>+ Object[] listenerArray = listeners.getListeners();
>+ 
>+ for (int i = 0; i < listenerArray.length; i++) {
>+ IConcurrentContentProviderListener next = (IConcurrentContentProviderListener) listenerArray[i];
>+ 
>+ next.update(updated);
>+ }
>+ }
>+ 
>+ /* (non-Javadoc)
>+ * @see org.eclipse.jface.viewers.deferred.IConcurrentContentProvider#removeListener(org.eclipse.jface.viewers.deferred.IConcurrentContentProviderListener)
>+ */
>+ public void removeListener(IConcurrentContentProviderListener listener) {
>+ listeners.remove(listener);
>+ }
>+}
>Index: src/org/eclipse/jface/viewers/deferred/ConcurrentTableManager.java
>===================================================================
>RCS file: src/org/eclipse/jface/viewers/deferred/ConcurrentTableManager.java
>diff -N src/org/eclipse/jface/viewers/deferred/ConcurrentTableManager.java
>--- /dev/null	1 Jan 1970 00:00:00 -0000
>+++ src/org/eclipse/jface/viewers/deferred/ConcurrentTableManager.java	1 Jan 1970 00:00:00 -0000
>@@ -0,0 +1,305 @@
>+/*******************************************************************************
>+ * Copyright (c) 2004 IBM Corporation and others.
>+ * All rights reserved. This program and the accompanying materials 
>+ * are made available under the terms of the Common Public License v1.0
>+ * which accompanies this distribution, and is available at
>+ * http://www.eclipse.org/legal/cpl-v10.html
>+ * 
>+ * Contributors:
>+ * IBM Corporation - initial API and implementation
>+ *******************************************************************************/
>+package org.eclipse.jface.viewers.deferred;
>+
>+import java.util.Comparator;
>+
>+import org.eclipse.core.runtime.IProgressMonitor;
>+import org.eclipse.core.runtime.IStatus;
>+import org.eclipse.core.runtime.NullProgressMonitor;
>+import org.eclipse.core.runtime.Status;
>+import org.eclipse.core.runtime.jobs.Job;
>+import org.eclipse.swt.widgets.Display;
>+
>+/**
>+ * @since 3.1
>+ */
>+public final class ConcurrentTableManager implements IConcurrentContentProviderListener {
>+ 
>+ private int limit = -1;
>+ private IConcurrentContentProvider content;
>+ private IConcurrentTable table;
>+ private Comparator sortOrder;
>+ private boolean containsUnsorted = false;
>+ private boolean dirty = false;
>+ 
>+ private LazySortedCollection sorter;
>+ private volatile FastProgressReporter searchReporter = null;
>+ 
>+ // Any thread accessing the following objects should synchronize on uiMutex.
>+ // The UI thread will wait on this lock, so it should never be held for anything
>+ // but trivial operations, and threads should never wait for other locks while holding
>+ // uiMutex.
>+ private ConcurrentTableUpdator updator;
>+ private Object sortMutex = new Object();
>+ private int sortStart = -1;
>+ private int sortLength = -1;
>+ 
>+ private Job sortJob = new Job("sorting") {
>+ protected IStatus run(IProgressMonitor monitor) {
>+ doSort(monitor);
>+ return Status.OK_STATUS;
>+ }
>+ };
>+ 
>+ public ConcurrentTableManager(IConcurrentTable table, 
>+ IConcurrentContentProvider contentProvider, Comparator sortOrder, 
>+ Display display) {
>+ 
>+ updator = new ConcurrentTableUpdator(table, display);
>+ content = contentProvider;
>+ this.table = table;
>+ this.sortOrder = sortOrder;
>+ sorter = new LazySortedCollection(sortOrder);
>+ sortJob.setSystem(true);
>+ sortJob.setPriority(Job.SHORT);
>+ contentProvider.addListener(this);
>+ }
>+ 
>+ public void dispose() {
>+ content.removeListener(this);
>+ }
>+ 
>+ public void refresh() {
>+ content.requestUpdate(this);
>+ }
>+
>+ /**
>+ * Called from sortJob. Sorts the elements defined by sortStart and sortLength.
>+ * Schedules a UI update when finished 
>+ * 
>+ * @param mon
>+ * @since 3.1
>+ */
>+ private void doSort(IProgressMonitor mon) { 
>+ LazySortedCollection collection;
>+ 
>+ // Workaround for some weirdness in the Jobs framework: if you cancel a monitor
>+ // for a job that has ended and reschedule that same job, it will start 
>+ // the job with a monitor that is already cancelled. We can workaround this by
>+ // removing all references to the progress monitor whenever the job terminates,
>+ // but this would require additional synchronize blocks (which are slow) and more
>+ // complexity. Instead, we just un-cancel the monitor at the start of each job. 
>+ mon.setCanceled(false);
>+ 
>+ synchronized(sortMutex) {
>+ ConcurrentTableUpdator.Range currentRange = updator.getRange();
>+ sortStart = currentRange.start;
>+ sortLength = currentRange.length;
>+ collection = sorter;
>+ }
>+
>+ mon.beginTask("sorting", 100);
>+ try {
>+ 
>+	 // First, sort the objects that are currently visible in the table
>+	 Object[] objectsOfInterest; 
>+	 int totalElements = 0;
>+	 
>+	 synchronized(collection) {
>+		 FastProgressReporter subMon = new FastProgressReporter(mon, 50);
>+		 searchReporter = subMon;
>+		 totalElements = collection.size();
>+	 if (limit != -1) {
>+	 if (totalElements > limit) {
>+	 totalElements = limit;
>+	 }
>+	 }
>+	 
>+	 // Send the total items to the updator ASAP -- the user may want
>+	 // to scroll to a different section of the table, which would
>+	 // cause our sort range to change and cause this job to get cancelled.
>+		 updator.setTotalItems(totalElements);
>+		 
>+		 if (limit != -1) {
>+		 collection.retainFirst(limit, subMon);
>+		 }
>+		 
>+		 sortLength = Math.min(sortLength, totalElements - sortStart);
>+		 sortLength = Math.max(sortLength, 0);
>+		 
>+		 objectsOfInterest = new Object[sortLength];
>+		 
>+		 collection.getRange(objectsOfInterest, sortStart, true, subMon);
>+		 searchReporter = null;
>+	 }
>+	 
>+	 updator.setElements(objectsOfInterest, sortStart, sortLength);
>+	 
>+	 if (mon.isCanceled()) {
>+	 return;
>+	 }
>+	
>+	 // Finally, sort all objects in the collection
>+	 synchronized(collection) {
>+		 objectsOfInterest = new Object[collection.size()];
>+		 
>+		 FastProgressReporter subMon = new FastProgressReporter(mon, 50);
>+		 searchReporter = subMon;
>+		 collection.getFirst(objectsOfInterest, true, subMon);
>+		 searchReporter = null;
>+	 }
>+	 
>+	 updator.setElements(objectsOfInterest, 0, totalElements);
>+	 containsUnsorted = false;
>+ } catch (InterruptedException e) {
>+ mon.setCanceled(true);
>+ } finally {
>+ searchReporter = null;
>+ mon.done();
>+ }
>+ 
>+ }
>+ 
>+ public void setSortOrder(Comparator sorter) {
>+ this.sortOrder = sorter;
>+ refresh();
>+ }
>+ 
>+ public void setLimit(int limit) {
>+ this.limit = limit;
>+ refresh();
>+ }
>+ 
>+ public int getLimit() {
>+ return limit;
>+ }
>+ 
>+ public void setRangeOfInterest(int start, int length) {
>+ updator.setRangeOfInterest(start, length);
>+ triggerSort();
>+ }
>+ 
>+ private void makeDirty() {
>+ synchronized(sortMutex) {
>+ dirty = true;
>+ containsUnsorted = true;
>+ triggerSort();
>+ }
>+ }
>+ 
>+ private void triggerSort() {
>+ synchronized(sortMutex) {
>+ // If we've already sent everything to the updator, there is nothing to do.
>+ if (!containsUnsorted) {
>+ return;
>+ }
>+ 
>+ ConcurrentTableUpdator.Range range = updator.getRange();
>+ 
>+ if (dirty || sortStart != range.start || sortLength != range.length) {
>+ dirty = false;
>+ cancelSortJob();
>+		 sortJob.schedule();
>+ }
>+ }
>+ }
>+
>+ private void cancelSortJob() {
>+ FastProgressReporter rep = searchReporter;
>+ if (rep != null) {
>+ rep.cancel();
>+ }
>+ sortJob.cancel();
>+ }
>+ 
>+ /* (non-Javadoc)
>+ * @see org.eclipse.jface.viewers.deferred.TableManager#add(java.util.Collection, org.eclipse.core.runtime.IProgressMonitor)
>+ */
>+ public void add(Object[] toAdd) {
>+ cancelSortJob();
>+ LazySortedCollection collection = sorter;
>+ synchronized(collection) {
>+ collection.addAll(toAdd);
>+ makeDirty();
>+ }
>+ }
>+ 
>+ public void setContents(Object[] contents) {
>+ LazySortedCollection collection = sorter;
>+ synchronized(collection) {
>+ // Flush all current items
>+ flush(collection.getItems(false), collection);
>+ 
>+ //LazySortedCollection newCollection = new LazySortedCollection(sortOrder);
>+ //newCollection.addAll(contents);
>+ }
>+
>+ synchronized(sortMutex) {
>+ LazySortedCollection newCollection = new LazySortedCollection(sortOrder);
>+ newCollection.addAll(contents);
>+ this.sorter = newCollection;
>+ makeDirty();
>+ }
>+ }
>+
>+ /* (non-Javadoc)
>+ * @see org.eclipse.jface.viewers.deferred.TableManager#remove(java.util.Collection, org.eclipse.core.runtime.IProgressMonitor)
>+ */
>+ public void remove(Object[] toRemove) {
>+ cancelSortJob();
>+ LazySortedCollection collection = sorter;
>+ synchronized(collection) {
>+ 
>+ try {
>+ collection.removeAll(toRemove, new NullProgressMonitor());
>+ } catch (InterruptedException e) {
>+ }
>+ 
>+ flush(toRemove, collection);
>+ 
>+ makeDirty();
>+ }
>+ refresh();
>+ }
>+
>+ /**
>+ * @param toRemove
>+ * @param collection
>+ * @since 3.1
>+ */
>+ private void flush(Object[] toRemove, LazySortedCollection collection) {
>+ for (int i = 0; i < toRemove.length; i++) {
>+ Object item = toRemove[i];
>+ 
>+ if (collection.contains(item)) {
>+ updator.flushCache(item);
>+ }
>+ }
>+ }
>+
>+ /* (non-Javadoc)
>+ * @see org.eclipse.jface.viewers.deferred.TableManager#update(java.util.Collection, org.eclipse.core.runtime.IProgressMonitor)
>+ */
>+ public void update(Object[] items) {
>+ 
>+ boolean dirty = false;
>+ LazySortedCollection collection = sorter;
>+ synchronized(collection) {
>+	 for (int i = 0; i < items.length; i++) {
>+	 Object item = items[i];
>+	 
>+	 if (collection.contains(item)) {
>+	 // TODO: write a collection.update(...) method
>+	 collection.remove(item);
>+	 collection.add(item);
>+	 updator.flushCache(item);
>+	 
>+	 dirty = true;
>+	 }
>+	 }
>+	 
>+	 if (dirty) {
>+	 makeDirty();
>+	 }
>+ }
>+ }
>+}
>Index: src/org/eclipse/jface/viewers/deferred/ConcurrentTableUpdator.java
>===================================================================
>RCS file: src/org/eclipse/jface/viewers/deferred/ConcurrentTableUpdator.java
>diff -N src/org/eclipse/jface/viewers/deferred/ConcurrentTableUpdator.java
>--- /dev/null	1 Jan 1970 00:00:00 -0000
>+++ src/org/eclipse/jface/viewers/deferred/ConcurrentTableUpdator.java	1 Jan 1970 00:00:00 -0000
>@@ -0,0 +1,326 @@
>+/*******************************************************************************
>+ * Copyright (c) 2004 IBM Corporation and others.
>+ * All rights reserved. This program and the accompanying materials 
>+ * are made available under the terms of the Common Public License v1.0
>+ * which accompanies this distribution, and is available at
>+ * http://www.eclipse.org/legal/cpl-v10.html
>+ * 
>+ * Contributors:
>+ * IBM Corporation - initial API and implementation
>+ *******************************************************************************/
>+package org.eclipse.jface.viewers.deferred;
>+
>+import org.eclipse.swt.widgets.Display;
>+
>+
>+/**
>+ * @since 3.1
>+ */
>+public class ConcurrentTableUpdator {
>+ private IConcurrentTable table;
>+ 
>+ /**
>+ * Set of all non-flushed elements known to this updator. Maps elements
>+ * onto sort positions. 
>+ */
>+ private IntHashMap sentIndices = new IntHashMap();
>+
>+ /**
>+ * The array of objects that has been sent to the UI. Maps indices onto elements.
>+ */
>+ private Object[] sentObjects = new Object[0];
>+ 
>+ private IntHashMap knownIndices = new IntHashMap();
>+ 
>+ private Object[] knownObjects = new Object[0];
>+ 
>+ // Minimum length for the pendingFlushes stack
>+ private static final int MIN_FLUSHLENGTH = 64;
>+ 
>+ // Stack of pending indices to flush
>+ private Object[] pendingFlushes = new Object[MIN_FLUSHLENGTH];
>+ private int lastFlush = 0;
>+ 
>+ private int totalElements = 0;
>+ private Display display;
>+ private int rangeStart;
>+ private int rangeLength;
>+ private boolean updateScheduled;
>+ 
>+ public final static class Range {
>+ int start = 0;
>+ int length = 0;
>+ 
>+ public Range(int s, int l) {
>+ start = s;
>+ length = l;
>+ }
>+ }
>+ 
>+ Runnable uiRunnable = new Runnable() {
>+ public void run() {
>+ synchronized(this) {
>+ updateScheduled = false;
>+ }
>+ updateTable();
>+ }
>+ };
>+ 
>+ public ConcurrentTableUpdator(IConcurrentTable table, Display display) {
>+ this.table = table;
>+ this.display = display;
>+ }
>+ 
>+ public Range getRange() {
>+ synchronized(this) {
>+ return new Range(rangeStart, rangeLength);
>+ }
>+ }
>+ 
>+ /**
>+ * Updates all elements in the given range 
>+ * 
>+ * @param changedElements
>+ * @param rangeStart
>+ * @param rangeLength
>+ * @since 3.1
>+ */
>+ public void setElements(Object[] changedElements, int start, int length) {
>+ int len = Math.min(changedElements.length, length);
>+ boolean visibleDirty = false;
>+ 
>+ synchronized(this) {
>+	 for (int i = 0; i < len; i++) {
>+	 int element = i + start;
>+	 Object object = changedElements[i];
>+
>+ Object oldObject = knownObjects[element];
>+ 
>+ if (oldObject != object && isVisible(element)) {
>+ visibleDirty = true;
>+ }
>+ 
>+ knownObjects[element] = object;
>+	 }
>+	 
>+	 if (visibleDirty) {
>+	 scheduleUIUpdate();
>+	 }
>+ }
>+ 
>+ }
>+ 
>+ /**
>+ * @param element
>+ * @return
>+ * @since 3.1
>+ */
>+ private boolean isVisible(int element) {
>+ return element >= rangeStart && element < rangeStart + rangeLength;
>+ }
>+
>+ public void flushCache(Object toFlush) {
>+ synchronized(this) {
>+ int currentIdx = knownIndices.get(toFlush, -1);
>+ 
>+ // If we've never heard of this object, bail out.
>+ if (currentIdx == -1) {
>+ return;
>+ }
>+ 
>+ knownIndices.remove(toFlush);
>+ knownObjects[currentIdx] = null; 
>+ 
>+ // If we've sent this object to the UI, schedule a flush
>+ int sentIdx = sentIndices.get(toFlush, -1);
>+ if (sentIdx != -1) {
>+ pushFlush(toFlush);
>+ 
>+ sentIndices.remove(toFlush);
>+ sentObjects[sentIdx] = null;
>+ 
>+ scheduleUIUpdate();
>+ }
>+ }
>+ 
>+ }
>+ 
>+ /**
>+ * Sets the size of the table. Called from a background thread.
>+ * 
>+ * @param newTotal
>+ * @since 3.1
>+ */
>+ public void setTotalItems(int newTotal) {
>+ synchronized (this) {
>+ if (newTotal != knownObjects.length) {
>+ if (newTotal < knownObjects.length) {
>+ // Flush any objects that are being removed as a result of the resize
>+ for (int i = newTotal; i < knownObjects.length; i++) {
>+ Object toFlush = knownObjects[i];
>+ 
>+ if (toFlush != null) {
>+ flushCache(toFlush);
>+ }
>+ }
>+ }
>+ 
>+ int minSize = Math.min(knownObjects.length, newTotal);
>+ 
>+	 Object[] newKnownObjects = new Object[newTotal];
>+	 System.arraycopy(knownObjects, 0, newKnownObjects, 0, minSize);
>+	 knownObjects = newKnownObjects;
>+	 	 
>+	 scheduleUIUpdate();
>+ }
>+ }
>+ }
>+ 
>+ /**
>+ * Pushes an object onto the flush stack
>+ * @param toFlush
>+ * @since 3.1
>+ */
>+ private void pushFlush(Object toFlush) {
>+ if (lastFlush >= pendingFlushes.length) {
>+ int newCapacity = Math.min(MIN_FLUSHLENGTH, lastFlush * 2);
>+ Object[] newPendingFlushes = new Object[newCapacity];
>+ System.arraycopy(pendingFlushes, 0, newPendingFlushes, 0, lastFlush);
>+ pendingFlushes = newPendingFlushes;
>+ }
>+ 
>+ pendingFlushes[lastFlush++] = toFlush;
>+ }
>+ 
>+ /**
>+ * 
>+ * @param idx
>+ * @param element
>+ * @since 3.1
>+ */
>+ public void update(int idx, Object value) { 
>+ // Keep the synchronized block as small as possible, since the UI may
>+ // be waiting on it.
>+ synchronized(this) {
>+ Object oldObject = knownObjects[idx];
>+ 
>+ if (oldObject != value && isVisible(idx)) {
>+ knownObjects[idx] = value;
>+ 
>+ scheduleUIUpdate();
>+ }
>+ } 
>+ }
>+ 
>+ /**
>+ * Called whenever the set of visible items in the table changes.
>+ * Must be called from the UI thread. Will ensure that the 
>+ * set of visible items is up-to-date.
>+ * 
>+ * @param start
>+ * @param length
>+ * @since 3.1
>+ */
>+ public void setRangeOfInterest(int start, int length) {
>+ synchronized (this) {
>+ if (rangeStart == start && rangeLength == length) {
>+ return;
>+ }
>+ 
>+ rangeStart = start;
>+ rangeLength = length;
>+ }
>+ 
>+ updateTable();
>+ }
>+
>+ /**
>+ * Schedules a UI update
>+ * 
>+ * @since 3.1
>+ */
>+ private void scheduleUIUpdate() {
>+ synchronized(this) {
>+	 if (!updateScheduled) {
>+	 updateScheduled = true;
>+	 display.asyncExec(uiRunnable);
>+	 }
>+ }
>+ }
>+ 
>+ private boolean hasPendingFlushes() {
>+ return lastFlush != 0;
>+ }
>+ 
>+ /**
>+ * Sends all known items in the given range to the table. Must be called from the
>+ * UI thread. Returns the number of items in the range that haven't been computed yet.
>+ * 
>+ * @param start
>+ * @param length
>+ * @since 3.1
>+ */
>+ private void updateTable() {
>+ int counter = 0;
>+ 
>+ Object[] flushes = null;
>+ int localNumFlushes = 0;
>+ Object[] elementsToSend = null;
>+ int newLength = -1;
>+ int start = 0;
>+ int length = 0;
>+ 
>+ // Copy everything to local variables -- don't make any calls to other
>+ // objects while we're inside our synchronized block.
>+ synchronized (this) {
>+ start = rangeStart;
>+ length = rangeLength;
>+ 
>+ if (lastFlush > 0) {
>+ localNumFlushes = lastFlush;
>+ flushes = pendingFlushes;
>+ pendingFlushes = new Object[MIN_FLUSHLENGTH];
>+ lastFlush = 0;
>+ }
>+ 
>+ // Check if we need to resize the table
>+ if (knownObjects.length != sentObjects.length) {
>+ newLength = knownObjects.length;
>+ 
>+ Object[] newSentObjects = new Object[knownObjects.length];
>+ System.arraycopy(sentObjects, 0, newSentObjects, 0, 
>+ Math.min(knownObjects.length, sentObjects.length));
>+ sentObjects = newSentObjects;
>+ }
>+ 
>+ length = Math.min(length, sentObjects.length - start);
>+
>+ if (length > 0) {
>+	 elementsToSend = new Object[length];
>+	 for (int i = 0; i < elementsToSend.length; i++) {
>+	 int element = i + start;
>+	 
>+	 Object object = knownObjects[element];
>+	 if (object != sentObjects[element]) {
>+	 elementsToSend[i] = object;
>+	 }
>+	 }
>+ }
>+ }
>+ 
>+ for (int idx = 0; idx < localNumFlushes; idx++) {
>+ table.flushCache(flushes[idx]);
>+ }
>+ 
>+ if (newLength != -1) {
>+ table.setTotalItems(newLength);
>+ }
>+ 
>+ for (int idx = 0; idx < length; idx++) {
>+ Object next = elementsToSend[idx];
>+ if (next != null) {
>+ table.update(idx + start, next);
>+ }
>+ }
>+ }
>+}
>Index: src/org/eclipse/jface/viewers/deferred/FastProgressReporter.java
>===================================================================
>RCS file: src/org/eclipse/jface/viewers/deferred/FastProgressReporter.java
>diff -N src/org/eclipse/jface/viewers/deferred/FastProgressReporter.java
>--- /dev/null	1 Jan 1970 00:00:00 -0000
>+++ src/org/eclipse/jface/viewers/deferred/FastProgressReporter.java	1 Jan 1970 00:00:00 -0000
>@@ -0,0 +1,134 @@
>+/*******************************************************************************
>+ * Copyright (c) 2004 IBM Corporation and others.
>+ * All rights reserved. This program and the accompanying materials 
>+ * are made available under the terms of the Common Public License v1.0
>+ * which accompanies this distribution, and is available at
>+ * http://www.eclipse.org/legal/cpl-v10.html
>+ * 
>+ * Contributors:
>+ * IBM Corporation - initial API and implementation
>+ *******************************************************************************/
>+package org.eclipse.jface.viewers.deferred;
>+
>+import org.eclipse.core.runtime.IProgressMonitor;
>+
>+/**
>+ * @since 3.1
>+ */
>+public final class FastProgressReporter {
>+ private IProgressMonitor monitor;
>+ private volatile boolean canceled = false;
>+ private int cancelCheck = 0;
>+ private String taskName;
>+ 
>+ private int taskDepth = 0;
>+ private int subTaskSize = 1;
>+ private int totalWork = 1;
>+ private int parentWork = 1;
>+ private int monitorUnitsRemaining;
>+ 
>+ private static int CANCEL_CHECK_PERIOD = 40;
>+ 
>+ /**
>+ * Constructs a null FastProgressReporter
>+ */
>+ public FastProgressReporter() {
>+ }
>+ 
>+ /**
>+ * Constructs a FastProgressReporter that wraps the given progress monitor
>+ * 
>+ * @param taskName
>+ * @param monitor
>+ */
>+ public FastProgressReporter(IProgressMonitor monitor, int totalProgress) {
>+ this.monitor = monitor;
>+ monitorUnitsRemaining = totalProgress;
>+ canceled = monitor.isCanceled();
>+ }
>+ 
>+// /**
>+// * Every call to beginTask must have a corresponding call to endTask, with the
>+// * same argument.
>+// * 
>+// * @param totalWork
>+// * @since 3.1
>+// */
>+// public void beginTask(int totalWork) {
>+// 
>+// if (monitor == null) {
>+// return;
>+// }
>+// 
>+// taskDepth++;
>+//
>+// if (totalWork == 0) {
>+// return;
>+// }
>+// 
>+// this.totalWork *= totalWork;
>+// }
>+// 
>+// public void beginSubTask(int subTaskWork) {
>+// subTaskSize *= subTaskWork;
>+// }
>+// 
>+// public void endSubTask(int subTaskWork) {
>+// subTaskSize /= subTaskWork;
>+// }
>+// 
>+// public void worked(int amount) {
>+// amount *= subTaskSize;
>+// 
>+// if (amount > totalWork) {
>+// amount = totalWork;
>+// }
>+// 
>+// int consumed = monitorUnitsRemaining * amount / totalWork;
>+// 
>+// if (consumed > 0) {
>+// monitor.worked(consumed);
>+// monitorUnitsRemaining -= consumed;
>+// }
>+// totalWork -= amount;
>+// }
>+// 
>+// public void endTask(int totalWork) { 
>+// taskDepth--;
>+// 
>+// if (taskDepth == 0) {
>+// if (monitor != null && monitorUnitsRemaining > 0) {
>+// monitor.worked(monitorUnitsRemaining);
>+// }
>+// }
>+// 
>+// if (totalWork == 0) {
>+// return;
>+// }
>+// 
>+// this.totalWork /= totalWork;
>+//
>+// }
>+ 
>+ public boolean isCanceled() {
>+ if (monitor == null) {
>+ return canceled;
>+ }
>+ 
>+ cancelCheck++;
>+ if (cancelCheck > CANCEL_CHECK_PERIOD) {
>+ canceled = monitor.isCanceled();
>+ cancelCheck = 0;
>+ }
>+ return canceled;
>+ }
>+ 
>+ public void cancel() { 
>+ canceled = true;
>+ 
>+ if (monitor == null) {
>+ return;
>+ }
>+ monitor.setCanceled(true);
>+ }
>+}
>Index: src/org/eclipse/jface/viewers/deferred/IConcurrentContentProvider.java
>===================================================================
>RCS file: src/org/eclipse/jface/viewers/deferred/IConcurrentContentProvider.java
>diff -N src/org/eclipse/jface/viewers/deferred/IConcurrentContentProvider.java
>--- /dev/null	1 Jan 1970 00:00:00 -0000
>+++ src/org/eclipse/jface/viewers/deferred/IConcurrentContentProvider.java	1 Jan 1970 00:00:00 -0000
>@@ -0,0 +1,33 @@
>+/*******************************************************************************
>+ * Copyright (c) 2004 IBM Corporation and others.
>+ * All rights reserved. This program and the accompanying materials 
>+ * are made available under the terms of the Common Public License v1.0
>+ * which accompanies this distribution, and is available at
>+ * http://www.eclipse.org/legal/cpl-v10.html
>+ * 
>+ * Contributors:
>+ * IBM Corporation - initial API and implementation
>+ *******************************************************************************/
>+package org.eclipse.jface.viewers.deferred;
>+
>+
>+/**
>+ * @since 3.1
>+ */
>+public interface IConcurrentContentProvider {
>+
>+ /**
>+ * Called by a listener to request an update. The receiver should call
>+ * the given listener's setContents(...) method at its earliest convenience.
>+ * The receiver is allowed to compute the elements asynchronously. That is,
>+ * it can compute the result in a background thread and call setContents(...)
>+ * once the result is ready. 
>+ * 
>+ * @param listener
>+ * @since 3.1
>+ */
>+ public void requestUpdate(IConcurrentContentProviderListener listener);
>+ 
>+ public void addListener(IConcurrentContentProviderListener listener);
>+ public void removeListener(IConcurrentContentProviderListener listener);
>+}
>Index: src/org/eclipse/jface/viewers/deferred/IConcurrentContentProviderListener.java
>===================================================================
>RCS file: src/org/eclipse/jface/viewers/deferred/IConcurrentContentProviderListener.java
>diff -N src/org/eclipse/jface/viewers/deferred/IConcurrentContentProviderListener.java
>--- /dev/null	1 Jan 1970 00:00:00 -0000
>+++ src/org/eclipse/jface/viewers/deferred/IConcurrentContentProviderListener.java	1 Jan 1970 00:00:00 -0000
>@@ -0,0 +1,28 @@
>+/*******************************************************************************
>+ * Copyright (c) 2004 IBM Corporation and others.
>+ * All rights reserved. This program and the accompanying materials 
>+ * are made available under the terms of the Common Public License v1.0
>+ * which accompanies this distribution, and is available at
>+ * http://www.eclipse.org/legal/cpl-v10.html
>+ * 
>+ * Contributors:
>+ * IBM Corporation - initial API and implementation
>+ *******************************************************************************/
>+package org.eclipse.jface.viewers.deferred;
>+
>+/**
>+ * @since 3.1
>+ */
>+public interface IConcurrentContentProviderListener {
>+ public void add(Object[] added);
>+ public void remove(Object[] removed);
>+ public void update(Object[] changed);
>+ 
>+ /**
>+ * Sends the complete set of elements in the model.
>+ * 
>+ * @param newContents
>+ * @since 3.1
>+ */
>+ public void setContents(Object[] newContents);
>+}
>Index: src/org/eclipse/jface/viewers/deferred/IConcurrentTable.java
>===================================================================
>RCS file: src/org/eclipse/jface/viewers/deferred/IConcurrentTable.java
>diff -N src/org/eclipse/jface/viewers/deferred/IConcurrentTable.java
>--- /dev/null	1 Jan 1970 00:00:00 -0000
>+++ src/org/eclipse/jface/viewers/deferred/IConcurrentTable.java	1 Jan 1970 00:00:00 -0000
>@@ -0,0 +1,43 @@
>+/*******************************************************************************
>+ * Copyright (c) 2004 IBM Corporation and others.
>+ * All rights reserved. This program and the accompanying materials 
>+ * are made available under the terms of the Common Public License v1.0
>+ * which accompanies this distribution, and is available at
>+ * http://www.eclipse.org/legal/cpl-v10.html
>+ * 
>+ * Contributors:
>+ * IBM Corporation - initial API and implementation
>+ *******************************************************************************/
>+package org.eclipse.jface.viewers.deferred;
>+
>+/**
>+ * @since 3.1
>+ */
>+public interface IConcurrentTable {
>+ /**
>+ * Tells the receiver that it should remove any cached information about the given
>+ * element. Either the element has changed or is about to be removed. The row
>+ * that was previously occupied by the element will be filled by a subsequent call
>+ * to update(...) 
>+ * 
>+ * @param element
>+ * @since 3.1
>+ */
>+ public void flushCache(Object element);
>+ 
>+ /**
>+ * Updates the contents of the item on the itemIndex row. It should be filled
>+ * in using the given element. 
>+ * 
>+ * The receiver is allowed to cache properties of the given object. If a subsequent
>+ * call to update(...) is made moving the object to a new row, the receiver can
>+ * reuse cached values rather than computing them again. A call to flushCache(...)
>+ * will indicate that cached values may have been changed.
>+ * 
>+ * @param itemIndex
>+ * @param element
>+ * @since 3.1
>+ */
>+ public void update(int itemIndex, Object element);
>+ public void setTotalItems(int total);
>+}
>Index: src/org/eclipse/jface/viewers/deferred/IntHashMap.java
>===================================================================
>RCS file: src/org/eclipse/jface/viewers/deferred/IntHashMap.java
>diff -N src/org/eclipse/jface/viewers/deferred/IntHashMap.java
>--- /dev/null	1 Jan 1970 00:00:00 -0000
>+++ src/org/eclipse/jface/viewers/deferred/IntHashMap.java	1 Jan 1970 00:00:00 -0000
>@@ -0,0 +1,59 @@
>+/*******************************************************************************
>+ * Copyright (c) 2004 IBM Corporation and others.
>+ * All rights reserved. This program and the accompanying materials 
>+ * are made available under the terms of the Common Public License v1.0
>+ * which accompanies this distribution, and is available at
>+ * http://www.eclipse.org/legal/cpl-v10.html
>+ * 
>+ * Contributors:
>+ * IBM Corporation - initial API and implementation
>+ *******************************************************************************/
>+package org.eclipse.jface.viewers.deferred;
>+
>+import java.util.HashMap;
>+
>+/**
>+ * Represents a map of objects onto ints. This is intended for future optimization:
>+ * using the concrete int class would allow for an implementation that doesn't require
>+ * additional object allocations for Integers. However, the current implementation
>+ * simply delegates to the Java HashMap class. 
>+ * 
>+ * @since 3.1
>+ */
>+public class IntHashMap {
>+ private HashMap map; 
>+ 
>+ public IntHashMap(int size, float loadFactor) {
>+ map = new HashMap(size, loadFactor);
>+ }
>+ 
>+ public IntHashMap() {
>+ map = new HashMap();
>+ }
>+ 
>+ public void remove(Object key) {
>+ map.remove(key);
>+ }
>+ 
>+ public void put(Object key, int value) {
>+ map.put(key, new Integer(value));
>+ }
>+ 
>+ public int get(Object key) {
>+ return get(key, 0);
>+ }
>+ 
>+ public int get(Object key, int defaultValue) {
>+ Integer result = (Integer)map.get(key);
>+ 
>+ if (result != null) {
>+ return result.intValue();
>+ }
>+ 
>+ return defaultValue;
>+ }
>+ 
>+ public boolean containsKey(Object key) {
>+ return map.containsKey(key);
>+ }
>+}
>Index: src/org/eclipse/jface/viewers/deferred/LazySortedCollection.java
>===================================================================
>RCS file: src/org/eclipse/jface/viewers/deferred/LazySortedCollection.java
>diff -N src/org/eclipse/jface/viewers/deferred/LazySortedCollection.java
>--- /dev/null	1 Jan 1970 00:00:00 -0000
>+++ src/org/eclipse/jface/viewers/deferred/LazySortedCollection.java	1 Jan 1970 00:00:00 -0000
>@@ -0,0 +1,1482 @@
>+/*******************************************************************************
>+ * Copyright (c) 2004 IBM Corporation and others.
>+ * All rights reserved. This program and the accompanying materials 
>+ * are made available under the terms of the Common Public License v1.0
>+ * which accompanies this distribution, and is available at
>+ * http://www.eclipse.org/legal/cpl-v10.html
>+ * 
>+ * Contributors:
>+ * IBM Corporation - initial API and implementation
>+ *******************************************************************************/
>+package org.eclipse.jface.viewers.deferred;
>+
>+import java.util.Collection;
>+import java.util.Comparator;
>+import java.util.Iterator;
>+
>+import org.eclipse.core.runtime.IProgressMonitor;
>+import org.eclipse.jface.util.Assert;
>+
>+/**
>+ * 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
>+ */
>+public class LazySortedCollection {
>+ private final int MIN_CAPACITY = 8;
>+ private Object[] contents = new Object[MIN_CAPACITY];
>+ private int[] leftSubTree = new int[MIN_CAPACITY];
>+ private int[] rightSubTree = new int[MIN_CAPACITY];
>+ private int[] nextUnsorted = new int[MIN_CAPACITY];
>+ private int[] treeSize = new int[MIN_CAPACITY];
>+ private int[] parentTree = new int[MIN_CAPACITY];
>+ private int root = -1;
>+ private int lastNode = 0;
>+ private int firstUnusedNode = -1;
>+ 
>+ 
>+ 
>+ 
>+ private static final float loadFactor = 0.75f;
>+ 
>+ private IntHashMap objectIndices;
>+ private Comparator comparator;
>+ private static int counter = 0;
>+ public boolean enableRandomization = true;
>+ 
>+ // Cancellation support
>+ private IProgressMonitor progressMonitor = null;
>+ // Normally, we return this cached result when determining if
>+ // we're cancelled. However, periodically (whenever cancelCheckCounter reaches 0)
>+ // we will update the cached value by calling progressMonitor.isCancelled().
>+ // The rest of these "cancellation
>+ private boolean cancelled = false;
>+ private int cancelCheckCounter = 0;
>+ // Minimum milliseconds between each call to isCancelled
>+ private static final int CANCEL_CHECK_PERIOD = 50;
>+ // Minimum number of elements to process before calling isCancelled
>+ private static final int MIN_CANCEL_CHECK_FREQUENCY = 10;
>+ // Number of bogus checks before a real 
>+ private int cancelCheckFrequency = MIN_CANCEL_CHECK_FREQUENCY;
>+ // Timestamp of the last call to isCancelled
>+ private long lastCancelCheckTimestamp = 0;
>+
>+ 
>+ // This object is inserted as the value into any node scheduled for lazy removal
>+ private Object lazyRemovalFlag = new Object() {
>+ public String toString() {
>+ return "Lazy removal flag"; 
>+ }
>+ };
>+ 
>+ private final static int DIR_LEFT = 0;
>+ private final static int DIR_RIGHT = 1;
>+ private final static int DIR_UNSORTED = 2;
>+ 
>+ // Direction constants indicating root nodes
>+ private final static int DIR_ROOT = 3;
>+ private final static int DIR_UNUSED = 4;
>+ 
>+ private final class Edge {
>+ private int startNode;
>+ private int direction;
>+ 
>+ private Edge() {
>+ startNode = -1;
>+ direction = -1;
>+ }
>+ 
>+ private Edge(int node, int dir) {
>+ startNode = node;
>+ direction = dir;
>+ }
>+
>+ private void copy(Edge toCopy) {
>+ startNode = toCopy.startNode;
>+ direction = toCopy.direction;
>+ }
>+ 
>+ private int getStart() {
>+ return startNode;
>+ }
>+ 
>+ private int getTarget() {
>+ if (startNode == -1) {
>+ if (direction == DIR_UNSORTED) {
>+ return firstUnusedNode;
>+ } else if (direction == DIR_ROOT) {
>+ return root;
>+ }
>+ return -1;
>+ }
>+ 
>+ if (direction == DIR_LEFT) {
>+ return leftSubTree[startNode];
>+ }
>+ if (direction == DIR_RIGHT) {
>+ return rightSubTree[startNode];
>+ }
>+ return nextUnsorted[startNode];
>+ }
>+ 
>+ private boolean isNull() {
>+ return getTarget() == -1;
>+ }
>+ 
>+ /**
>+ * Redirects this edge to a new node
>+ * @param newNode
>+ * @since 3.1
>+ */
>+ private void setTarget(int newNode) { 
>+ if (direction == DIR_LEFT) {
>+ 	 leftSubTree[startNode] = newNode;
>+ } else if (direction == DIR_RIGHT) {
>+ rightSubTree[startNode] = newNode;
>+ } else if (direction == DIR_UNSORTED) {
>+ nextUnsorted[startNode] = newNode;
>+ } else if (direction == DIR_ROOT) {
>+ root = newNode;
>+ } else if (direction == DIR_UNUSED) {
>+ firstUnusedNode = newNode;
>+ }
>+ 
>+	 if (newNode != -1) {
>+	 parentTree[newNode] = startNode;
>+	 }
>+ }
>+ 
>+ private void advance(int direction) {
>+ startNode = getTarget();
>+ this.direction = direction;
>+ }
>+ }
>+
>+ private void setRootNode(int node) {
>+ root = node;
>+ if (node != -1) {
>+ parentTree[node] = -1;
>+ }
>+ }
>+ 
>+ private void setNextUnsorted(int parent, int next) {
>+ nextUnsorted[parent] = next;
>+ if (next != -1) {
>+ parentTree[next] = parent;
>+ }
>+ recomputeTreeSize(parent);
>+ }
>+ 
>+ public LazySortedCollection(Comparator c) {
>+ this.comparator = c;
>+ }
>+ 
>+ public void print() {
>+ StringBuffer buf = new StringBuffer();
>+ System.out.println("----");
>+ print(0, root);
>+ 
>+ System.out.println(buf.toString());
>+ }
>+ 
>+ private String indent(int indent) {
>+ String output = "";
>+ 
>+ for(int i = 0; i < indent; i++) {
>+ output += " ";
>+ }
>+ 
>+ return output;
>+ }
>+ 
>+ public void print(int indent, int nodeToPrint) {
>+ 
>+ String indentString = indent(indent);
>+ if (nodeToPrint == -1) {
>+ System.out.println("null\n");
>+ return;
>+ }
>+
>+ if (leftSubTree[nodeToPrint] != -1) {
>+	 System.out.println(indentString + "left " + leftSubTree[nodeToPrint]);
>+	 print(indent + 1, leftSubTree[nodeToPrint]);
>+ }
>+
>+ System.out.println(indentString + "value {" + contents[nodeToPrint] + "}");
>+ int next = nextUnsorted[nodeToPrint];
>+ while (next != -1) {
>+ System.out.println(indentString + "unsorted " + next + " {" + contents[next] + "}");
>+ next = nextUnsorted[next];
>+ }
>+ 
>+ if (rightSubTree[nodeToPrint] != -1) {
>+	 System.out.println(indentString + "right " + rightSubTree[nodeToPrint]);
>+	 print(indent + 1, rightSubTree[nodeToPrint]);
>+ }
>+ }
>+ 
>+ public void testInvariants() {
>+ if (enableRandomization) {
>+ return;
>+ }
>+ 
>+ testInvariants(root);
>+ }
>+ 
>+ private void testInvariants(int node) {
>+ if (node == -1) {
>+ return;
>+ }
>+ 
>+ // Get the current tree size (we will later force the tree size
>+ // to be recomputed from scratch -- if everything works properly, then
>+ // there should be no change.
>+ int treeSize = getSubtreeSize(node);
>+
>+ int left = leftSubTree[node];
>+ int right = rightSubTree[node];
>+ int unsorted = nextUnsorted[node];
>+ 
>+ if (isUnsorted(node)) {
>+ Assert.isTrue(left == -1, "unsorted nodes shouldn't have a left subtree");
>+ Assert.isTrue(right == -1, "unsorted nodes shouldn't have a right subtree");
>+ }
>+ 
>+ if (left != -1) {
>+ testInvariants(left);
>+ Assert.isTrue(parentTree[left] == node, "left node has invalid parent pointer");
>+ }
>+ if (right != -1) {
>+ testInvariants(right);
>+ Assert.isTrue(parentTree[right] == node, "right node has invalid parent pointer"); 
>+ }
>+
>+ int previous = node;
>+ while (unsorted != -1) {
>+ int oldTreeSize = this.treeSize[unsorted];
>+ recomputeTreeSize(unsorted);
>+ 
>+ Assert.isTrue(this.treeSize[unsorted] == oldTreeSize, 
>+ "Invalid node size for unsorted node");
>+ Assert.isTrue(leftSubTree[unsorted] == -1, "unsorted nodes shouldn't have left subtrees");
>+ Assert.isTrue(rightSubTree[unsorted] == -1, "unsorted nodes shouldn't have right subtrees");
>+ Assert.isTrue(parentTree[unsorted] == previous, "unsorted node has invalid parent pointer");
>+ Assert.isTrue(contents[unsorted] != lazyRemovalFlag, "unsorted nodes should not be lazily removed");
>+ previous = unsorted;
>+ unsorted = nextUnsorted[unsorted];
>+ }
>+ 
>+ // Note that we've already tested that the child sizes are correct... if our size is
>+ // correct, then recomputing it now should not cause any change.
>+ recomputeTreeSize(node);
>+ 
>+ if (treeSize != getSubtreeSize(node)) {
>+ print();
>+ }
>+ 
>+ Assert.isTrue(treeSize == getSubtreeSize(node), "invalid tree size");
>+ }
>+ 
>+ private boolean isUnsorted(int node) {
>+ int parent = parentTree[node];
>+ 
>+ if (parent != -1) {
>+ return nextUnsorted[parent] == node;
>+ }
>+ 
>+ return false;
>+ }
>+ 
>+ private final boolean isLess(int element1, int element2) {
>+ return comparator.compare(contents[element1], contents[element2]) < 0;
>+ }
>+ 
>+ /**
>+ * Adds the given element to the given subtree. Returns the new
>+ * root of the subtree.
>+ * 
>+ * @param subTree index of the subtree to insert elementToAdd into. If -1, 
>+ * then a new subtree will be created for elementToAdd
>+ * @param idxToAdd index of the element to add to the subtree. If -1, this method
>+ * is a NOP.
>+ * @since 3.1
>+ */
>+ private final int addUnsorted(int subTree, int elementToAdd) {
>+ if (elementToAdd == -1) {
>+ return subTree;
>+ }
>+ 
>+ if (subTree == -1) {
>+ nextUnsorted[elementToAdd] = -1;
>+ treeSize[elementToAdd] = 1;
>+ return elementToAdd;
>+ }
>+ 
>+ // If the subTree is empty (ie: it only contains nodes flagged for lazy removal),
>+ // chop it off.
>+ if (treeSize[subTree] == 0) {
>+ removeSubTree(subTree);
>+ nextUnsorted[elementToAdd] = -1;
>+ treeSize[elementToAdd] = 1;
>+ return elementToAdd;
>+ }
>+ 
>+ int addedTreeSize = treeSize[elementToAdd];
>+ 
>+ // If neither subtree has any children, add a pseudorandom chance of the
>+ // newly added element becoming the new pivot for this node. Note: instead
>+ // of a real pseudorandom generator, we simply use a counter here.
>+ if (enableRandomization && leftSubTree[subTree] == -1 && rightSubTree[subTree] == -1 
>+ && leftSubTree[elementToAdd] == -1 && rightSubTree[elementToAdd] == -1) {
>+	 counter--;
>+	 
>+	 if (counter % treeSize[subTree] == 0) {
>+	 // Make the new node into the new pivot 
>+	 nextUnsorted[elementToAdd] = subTree;
>+	 parentTree[elementToAdd] = parentTree[subTree];
>+	 parentTree[subTree] = elementToAdd;
>+	 treeSize[elementToAdd] = treeSize[subTree] + 1;
>+	 return elementToAdd;
>+	 }
>+ }
>+ 
>+ int oldNextUnsorted = nextUnsorted[subTree];
>+ nextUnsorted[elementToAdd] = oldNextUnsorted;
>+ 
>+ if (oldNextUnsorted == -1) {
>+ treeSize[elementToAdd] = 1;
>+ } else {
>+ treeSize[elementToAdd] = treeSize[oldNextUnsorted] + 1;
>+ parentTree[oldNextUnsorted] = elementToAdd;
>+ }
>+ 
>+ parentTree[elementToAdd] = subTree;
>+ 
>+ nextUnsorted[subTree] = elementToAdd;
>+ treeSize[subTree]++; 
>+ return subTree;
>+ }
>+ 
>+ /**
>+ * Returns the number of elements in the collection
>+ * 
>+ * @return
>+ * @since 3.1
>+ */
>+ public int size() {
>+ int result = getSubtreeSize(root);
>+ 
>+ testInvariants();
>+ 
>+ return result;
>+ }
>+ 
>+ /**
>+ * Given a tree and one of its unsorted children, this sorts the child by moving
>+ * it into the left or right subtrees. Returns the next unsorted child or -1 if none
>+ * 
>+ * @param subTree parent tree
>+ * @param toMove child (unsorted) subtree
>+ * @since 3.1
>+ */
>+ private final int partition(int subTree, int toMove) {
>+ int result = nextUnsorted[toMove];
>+ 
>+ if (isLess(toMove, subTree)) {
>+ int nextLeft = addUnsorted(leftSubTree[subTree], toMove);
>+ leftSubTree[subTree] = nextLeft;
>+ parentTree[nextLeft] = subTree;
>+ } else {
>+ int nextRight = addUnsorted(rightSubTree[subTree], toMove);
>+ rightSubTree[subTree] = nextRight;
>+ parentTree[nextRight] = subTree;
>+ }
>+ 
>+ return result;
>+ }
>+ 
>+ /**
>+ * Partitions the given subtree. Moves all unsorted elements at the given node
>+ * to either the left or right subtrees. If the node itself was scheduled for
>+ * lazy removal, this will force the node to be removed immediately. Returns
>+ * the new subTree.
>+ * 
>+ * @param subTree
>+ * @return the replacement node (this may be different from subTree if the subtree
>+ * was replaced during the removal)
>+ * @since 3.1
>+ */
>+ private final int partition(int subTree, FastProgressReporter mon) throws InterruptedException {
>+ if (subTree == -1) {
>+ return -1;
>+ }
>+ 
>+ if (contents[subTree] == lazyRemovalFlag) {
>+ subTree = removeNode(subTree);
>+ if (subTree == -1) {
>+ return -1;
>+ }
>+ }
>+ 
>+ for (int idx = nextUnsorted[subTree]; idx != -1;) { 
>+ idx = partition(subTree, idx);
>+ nextUnsorted[subTree] = idx;
>+ if (idx != -1) {
>+ parentTree[idx] = subTree;
>+ }
>+ 
>+ if (mon.isCanceled()) {
>+ throw new InterruptedException();
>+ }
>+ }
>+ 
>+ // At this point, there are no remaining unsorted nodes in this subtree
>+ nextUnsorted[subTree] = -1;
>+ 
>+ return subTree;
>+ }
>+ 
>+ private final int getSubtreeSize(int subTree) {
>+ if (subTree == -1) {
>+ return 0;
>+ }
>+ return treeSize[subTree];
>+ }
>+ 
>+ /**
>+ * Increases the capacity of this collection, if necessary, so that it can hold the given number of
>+ * elements. This cannot be used to reduce the amount of memory used by the collection.
>+ *
>+ * @param newSize
>+ * @since 3.1
>+ */
>+ public final void setCapacity(int newSize) {
>+ if (newSize > contents.length) {
>+ setArraySize(newSize);
>+ }
>+ }
>+ 
>+ /**
>+ * Adjusts the capacity of the array.
>+ * 
>+ * @param newCapacity
>+ * @since 3.1
>+ */
>+ private final void setArraySize(int newCapacity) {
>+ Object[] newContents = new Object[newCapacity];
>+ System.arraycopy(contents, 0, newContents, 0, lastNode);
>+ contents = newContents;
>+ 
>+ int[] newLeftSubTree = new int[newCapacity];
>+ System.arraycopy(leftSubTree, 0, newLeftSubTree, 0, lastNode);
>+ leftSubTree = newLeftSubTree;
>+ 
>+ int[] newRightSubTree = new int[newCapacity];
>+ System.arraycopy(rightSubTree, 0, newRightSubTree, 0, lastNode);
>+ rightSubTree = newRightSubTree;
>+ 
>+ int[] newNextUnsorted = new int[newCapacity];
>+ System.arraycopy(nextUnsorted, 0, newNextUnsorted, 0, lastNode);
>+ nextUnsorted = newNextUnsorted;
>+ 
>+ int[] newTreeSize = new int[newCapacity];
>+ System.arraycopy(treeSize, 0, newTreeSize, 0, lastNode);
>+ treeSize = newTreeSize;
>+ 
>+ int[] newParentTree = new int[newCapacity];
>+ System.arraycopy(parentTree, 0, newParentTree, 0, lastNode);
>+ parentTree = newParentTree;
>+ }
>+ 
>+ /**
>+ * Creates a new node with the given value. Returns the index of the newly
>+ * created node.
>+ * 
>+ * @param value
>+ * @return
>+ * @since 3.1
>+ */
>+ private final int createNode(Object value) {
>+ int result = -1;
>+
>+ if (firstUnusedNode == -1) {
>+ // If there are no unused nodes from prior removals, then 
>+ // we add a node at the end
>+ result = lastNode;
>+ 
>+ // If this would cause the array to overflow, reallocate the array 
>+ if (contents.length <= lastNode) {
>+ setCapacity(lastNode * 2);
>+ }
>+ 
>+ lastNode++;
>+ } else {
>+ // Reuse a node from a prior removal
>+ result = firstUnusedNode;
>+ firstUnusedNode = nextUnsorted[result];
>+ }
>+ 
>+ contents[result] = value;
>+ treeSize[result] = 1;
>+ 
>+ // Clear pointers
>+ leftSubTree[result] = -1;
>+ rightSubTree[result] = -1;
>+ nextUnsorted[result] = -1;
>+ 
>+ // As long as we have a hash table of values onto tree indices, incrementally
>+ // update the hash table. Note: the table is only constructed as needed, and it
>+ // is destroyed whenever the arrays are reallocated instead of reallocating it.
>+ if (objectIndices != null) {
>+ objectIndices.put(value, result);
>+ }
>+ 
>+ return result;
>+ }
>+ 
>+ /**
>+ * Returns the current tree index for the given object.
>+ * 
>+ * @param value
>+ * @return
>+ * @since 3.1
>+ */
>+ private int getObjectIndex(Object value) {
>+ // If we don't have a map of values onto tree indices, build the map now.
>+ if (objectIndices == null) {
>+ int result = -1;
>+ 
>+ objectIndices = new IntHashMap((int)(contents.length / loadFactor) + 1, loadFactor);
>+ 
>+ for (int i = 0; i < lastNode; i++) {
>+ Object element = contents[i];
>+ 
>+ if (element != null && element != lazyRemovalFlag) {
>+ objectIndices.put(element, i);
>+ 
>+ if (value == element) {
>+ result = i;
>+ }
>+ }
>+ }
>+ 
>+ return result;
>+ }
>+ 
>+ // If we have a map of values onto tree indices, return the result by looking it up in
>+ // the map
>+ return objectIndices.get(value, -1);
>+ }
>+ 
>+ /**
>+ * Redirects any pointers from the original to the replacement. If the replacement
>+ * causes a change in the number of elements in the parent tree, the changes are
>+ * propogated toward the root.
>+ * 
>+ * @param nodeToReplace
>+ * @param replacementNode
>+ * @since 3.1
>+ */
>+ private void replaceNode(int nodeToReplace, int replacementNode) {
>+ int parent = parentTree[nodeToReplace];
>+ 
>+ if (parent == -1) {
>+ if (root == nodeToReplace) {
>+ setRootNode(replacementNode);
>+ }
>+ } else {
>+ if (leftSubTree[parent] == nodeToReplace) {
>+ leftSubTree[parent] = replacementNode;
>+ } else if (rightSubTree[parent] == nodeToReplace) {
>+ rightSubTree[parent] = replacementNode;
>+ } else if (nextUnsorted[parent] == nodeToReplace) {
>+ nextUnsorted[parent] = replacementNode;
>+ }
>+ if (replacementNode != -1) {
>+ parentTree[replacementNode] = parent;
>+ }
>+ }
>+ }
>+ 
>+ /**
>+ * Returns the Edge whose target is the given node
>+ * @param targetNode
>+ * @return
>+ * @since 3.1
>+ */
>+ private Edge getEdgeTo(int targetNode) {
>+ int parent = parentTree[targetNode];
>+
>+ int direction = DIR_LEFT;
>+ 
>+ if (parent == -1) {
>+ if (root == targetNode) {
>+ direction = DIR_ROOT;
>+ } else if (firstUnusedNode == targetNode){
>+ direction = DIR_UNUSED;
>+ }
>+ } else {
>+ if (leftSubTree[parent] == targetNode) {
>+ direction = DIR_LEFT;
>+ } else if (rightSubTree[parent] == targetNode) {
>+ direction = DIR_RIGHT;
>+ } else if (nextUnsorted[parent] == targetNode) {
>+ direction = DIR_UNSORTED;
>+ }
>+ }
>+ 
>+ return new Edge(parent, direction);
>+ }
>+ 
>+ private void recomputeAncestorTreeSizes(int node) {
>+ while (node != -1) {
>+ int oldSize = treeSize[node];
>+ 
>+ recomputeTreeSize(node);
>+ 
>+ if (treeSize[node] == oldSize) {
>+ break;
>+ }
>+ 
>+ node = parentTree[node];
>+ } 
>+ }
>+ 
>+ /**
>+ * Recomputes the tree size for the given node.
>+ * 
>+ * @param toRecompute
>+ * @param stopAtNode
>+ * @since 3.1
>+ */
>+ private void recomputeTreeSize(int node) {
>+ if (node == -1) {
>+ return;
>+ }
>+ treeSize[node] = getSubtreeSize(leftSubTree[node])
>+ 		+ getSubtreeSize(rightSubTree[node])
>+ 		+ getSubtreeSize(nextUnsorted[node])
>+ 		+ (contents[node] == lazyRemovalFlag ? 0 : 1); 
>+ }
>+ 
>+ /**
>+ * 
>+ * @param toRecompute
>+ * @param whereToStop
>+ * @since 3.1
>+ */
>+ private void forceRecomputeTreeSize(int toRecompute, int whereToStop) {
>+ while (toRecompute != -1 && toRecompute != whereToStop) {
>+	 recomputeTreeSize(toRecompute);
>+	 
>+	 toRecompute = parentTree[toRecompute];
>+ }
>+ }
>+ 
>+ /**
>+ * @param subTree
>+ * @since 3.1
>+ */
>+ private void destroyNode(int nodeToDestroy) {
>+ // If we're maintaining a map of values onto tree indices, remove this entry from
>+ // the map
>+ if (objectIndices != null) {
>+ Object oldContents = contents[nodeToDestroy];
>+ if (oldContents != lazyRemovalFlag) {
>+ objectIndices.remove(oldContents);
>+ }
>+ }
>+ 
>+ contents[nodeToDestroy] = null;
>+ leftSubTree[nodeToDestroy] = -1;
>+ rightSubTree[nodeToDestroy] = -1;
>+ 
>+ if (firstUnusedNode == -1) {
>+ treeSize[nodeToDestroy] = 1;
>+ } else {
>+ treeSize[nodeToDestroy] = treeSize[firstUnusedNode] + 1;
>+ parentTree[firstUnusedNode] = nodeToDestroy;
>+ }
>+ 
>+ nextUnsorted[nodeToDestroy] = firstUnusedNode;
>+ 
>+ firstUnusedNode = nodeToDestroy; 
>+ }
>+ 
>+ /**
>+ * Frees up memory by clearing the list of nodes that have been freed up through removals.
>+ * 
>+ * @since 3.1
>+ */
>+ private final void pack() {
>+ 
>+ // If there are no unused nodes, then there is nothing to do
>+ if (firstUnusedNode == -1) {
>+ return;
>+ }
>+ 
>+ int reusableNodes = getSubtreeSize(firstUnusedNode);
>+ int nonPackableNodes = lastNode - reusableNodes;
>+ 
>+ // Only pack the array if we're utilizing less than 1/4 of the array (note:
>+ // this check is important, or it will change the time bounds for removals)
>+ if (contents.length < MIN_CAPACITY || nonPackableNodes > contents.length / 4) {
>+ return;
>+ }
>+ 
>+ // Rather than update the entire map, just null it out. If it is needed,
>+ // it will be recreated lazily later. This will save some memory if the
>+ // map isn't needed, and it takes a similar amount of time to recreate the
>+ // map as to update all the indices.
>+ objectIndices = null;
>+ 
>+ // Maps old index -> new index
>+ int[] mapNewIdxOntoOld = new int[contents.length];
>+ int[] mapOldIdxOntoNew = new int[contents.length];
>+ 
>+ int nextNewIdx = 0;
>+ // Compute the mapping. Determine the new index for each element 
>+ for (int oldIdx = 0; oldIdx < lastNode; oldIdx++) {
>+ if (contents[oldIdx] != null) {
>+ mapOldIdxOntoNew[oldIdx] = nextNewIdx;
>+ mapNewIdxOntoOld[nextNewIdx] = oldIdx;
>+ nextNewIdx++;
>+ } else {
>+ mapOldIdxOntoNew[oldIdx] = -1;
>+ }
>+ }
>+ 
>+ // Make the actual array size double the number of nodes to allow
>+ // for expansion.
>+ int newNodes = nextNewIdx;
>+ int newCapacity = Math.max(newNodes * 2, MIN_CAPACITY);
>+ 
>+ // Allocate new arrays
>+ Object[] newContents = new Object[newCapacity];
>+ int[] newTreeSize = new int[newCapacity];
>+ int[] newNextUnsorted = new int[newCapacity];
>+ int[] newLeftSubTree = new int[newCapacity];
>+ int[] newRightSubTree = new int[newCapacity];
>+ int[] newParentTree = new int[newCapacity];
>+ 
>+ for (int newIdx = 0; newIdx < newNodes; newIdx++) {
>+ int oldIdx = mapNewIdxOntoOld[newIdx];
>+ newContents[newIdx] = contents[oldIdx];
>+ newTreeSize[newIdx] = treeSize[oldIdx];
>+ 
>+ int left = leftSubTree[oldIdx];
>+ if (left == -1) {
>+ newLeftSubTree[newIdx] = -1;
>+ } else {
>+ newLeftSubTree[newIdx] = mapOldIdxOntoNew[left];
>+ }
>+ 
>+ int right = rightSubTree[oldIdx];
>+ if (right == -1) {
>+ newRightSubTree[newIdx] = -1; 
>+ } else {
>+ newRightSubTree[newIdx] = mapOldIdxOntoNew[right];
>+ }
>+
>+ int unsorted = nextUnsorted[oldIdx];
>+ if (unsorted == -1) {
>+ newNextUnsorted[newIdx] = -1;
>+ } else {
>+ newNextUnsorted[newIdx] = mapOldIdxOntoNew[unsorted];
>+ }
>+ 
>+ int parent = parentTree[oldIdx];
>+ if (parent == -1) {
>+ newParentTree[newIdx] = -1;
>+ } else {
>+ newParentTree[newIdx] = mapOldIdxOntoNew[parent];
>+ }
>+ }
>+ 
>+ contents = newContents;
>+ nextUnsorted = newNextUnsorted;
>+ treeSize = newTreeSize;
>+ leftSubTree = newLeftSubTree;
>+ rightSubTree = newRightSubTree;
>+ parentTree = newParentTree;
>+ 
>+ if (root != -1) {
>+ root = mapOldIdxOntoNew[root];
>+ }
>+ 
>+ // All unused nodes have been removed
>+ firstUnusedNode = -1;
>+ lastNode = newNodes;
>+ }
>+ 
>+ /**
>+ * Adds the given object to the collection. Runs in O(1) amortized time.
>+ * 
>+ * @param toAdd
>+ * @since 3.1
>+ */
>+ public final void add(Object toAdd) {
>+ // Create the new node
>+ int newIdx = createNode(toAdd);
>+ 
>+ // Insert the new node into the root tree
>+ setRootNode(addUnsorted(root, newIdx));
>+ 
>+ testInvariants();
>+ }
>+ 
>+ /**
>+ * Adds all items from the given collection. 
>+ * 
>+ * @param toAdd
>+ * @since 3.1
>+ */
>+ public final void addAll(Collection toAdd) {
>+ Iterator iter = toAdd.iterator();
>+ while (iter.hasNext()) {
>+ add(iter.next());
>+ }
>+ 
>+ testInvariants();
>+ }
>+ 
>+ /**
>+ * Adds all items from the given array to the collection
>+ * @param toAdd
>+ * @since 3.1
>+ */
>+ public final void addAll(Object[] toAdd) {
>+ for (int i = 0; i < toAdd.length; i++) {
>+ Object object = toAdd[i];
>+ 
>+ add(object);
>+ }
>+ 
>+ testInvariants();
>+ }
>+ 
>+ /**
>+ * Returns true iff the collection is empty
>+ * 
>+ * @return
>+ * @since 3.1
>+ */
>+ public final boolean isEmpty() {
>+ boolean result = (root == -1);
>+ 
>+ testInvariants();
>+ 
>+ return result;
>+ }
>+ 
>+ /**
>+ * Removes the given object from the collection
>+ * 
>+ * @param toRemove
>+ * @since 3.1
>+ */
>+ public final void remove(Object toRemove) {
>+ internalRemove(toRemove);
>+ 
>+ pack();
>+ 
>+ testInvariants();
>+ }
>+ 
>+ /**
>+ * @param toRemove
>+ * @since 3.1
>+ */
>+ private void internalRemove(Object toRemove) {
>+ int objectIndex = getObjectIndex(toRemove);
>+ 
>+ if (objectIndex != -1) {
>+ int parent = parentTree[objectIndex];
>+ lazyRemoveNode(objectIndex);
>+ //Edge parentEdge = getEdgeTo(objectIndex);
>+ //parentEdge.setTarget(lazyRemoveNode(objectIndex));
>+ recomputeAncestorTreeSizes(parent);
>+ }
>+ 
>+ //testInvariants();
>+ }
>+
>+ public final void removeAll(Collection toRemove, IProgressMonitor mon) throws InterruptedException {
>+ for (Iterator iter = toRemove.iterator(); iter.hasNext();) {
>+ Object next = (Object) iter.next();
>+
>+ internalRemove(next);
>+ }
>+ 
>+ testInvariants();
>+ 
>+ pack();
>+ 
>+ testInvariants();
>+ }
>+ 
>+ public final void removeAll(Object[] toRemove, IProgressMonitor mon) throws InterruptedException {
>+ for (int i = 0; i < toRemove.length; i++) {
>+ Object object = toRemove[i];
>+ 
>+ internalRemove(object);
>+ }
>+ 
>+ testInvariants();
>+ 
>+ pack();
>+ 
>+ testInvariants();
>+ }
>+ 
>+ /**
>+ * Retains the first n 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.
>+ * 
>+ * @param toRetain
>+ * @return
>+ * @since 3.1
>+ */
>+ public final void retainFirst(int n, FastProgressReporter mon) throws InterruptedException {
>+ int sz = size();
>+ 
>+ if (n >= sz) {
>+ return;
>+ }
>+ 
>+ removeRange(n, sz - n, mon);
>+ 
>+ testInvariants();
>+ }
>+ 
>+ public final void retainFirst(int n) {
>+ try {
>+ retainFirst(n, new FastProgressReporter());
>+ } catch (InterruptedException e) {
>+ }
>+ 
>+ testInvariants();
>+ }
>+ 
>+ public final void removeRange(int first, int length) {
>+ try {
>+ removeRange(first, length, new FastProgressReporter());
>+ } catch (InterruptedException e) {
>+ }
>+ 
>+ testInvariants();
>+ }
>+ 
>+ public final void removeRange(int first, int length, FastProgressReporter mon) throws InterruptedException {
>+ 	removeRange(root, first, length, mon);
>+ 	
>+ 	pack();
>+ 	
>+ 	testInvariants();
>+ }
>+ 
>+ private final void removeRange(int node, int rangeStart, int rangeLength, FastProgressReporter mon) throws InterruptedException {
>+ 	if (rangeLength == 0) {
>+ 		return;
>+ 	}
>+ 	
>+ 	int size = getSubtreeSize(node);
>+ 	
>+ 	if (size <= rangeStart) {
>+ 		return;
>+ 	}
>+ 	
>+ 	// If we can chop off this entire subtree without any sorting, do so.
>+ 	if (rangeStart == 0 && rangeLength >= size) {
>+ 		removeSubTree(node);
>+ 		return;
>+ 	}
>+ 	try {
>+	 	// Partition any unsorted nodes
>+ 	 node = partition(node, mon);
>+	 	
>+	 	int left = leftSubTree[node];
>+	 	int leftSize = getSubtreeSize(left);
>+	 	
>+	 	int toRemoveFromLeft = Math.min(leftSize - rangeStart, rangeLength);
>+	 	
>+	 	// If we're removing anything from the left node
>+	 	if (toRemoveFromLeft >= 0) {
>+	 		removeRange(leftSubTree[node], rangeStart, toRemoveFromLeft, mon);
>+	 		
>+	 		// Check if we're removing from both sides
>+	 		int toRemoveFromRight = rangeStart + rangeLength - leftSize - 1;
>+	 		
>+	 		if (toRemoveFromRight >= 0) {
>+	 			// Remove from right subtree
>+	 			removeRange(rightSubTree[node], 0, toRemoveFromRight, mon);
>+	 			
>+	 			// ... removing from both sides means we need to remove the node itself too
>+	 			removeNode(node);
>+	 			return;
>+	 		}
>+	 	} else {
>+	 		// If removing from the right side only
>+	 		removeRange(rightSubTree[node], rangeStart - leftSize - 1, rangeLength, mon);
>+	 	}
>+ 	} finally {
>+ 	 recomputeTreeSize(node);
>+ 	}
>+ }
>+ 
>+ /**
>+ * Prunes the given subtree (and all child nodes, sorted or unsorted).
>+ * 
>+ * @param subTree
>+ * @since 3.1
>+ */
>+ private final void removeSubTree(int subTree) {
>+ if (subTree == -1) {
>+ return;
>+ }
>+ 
>+ // Destroy all unsorted nodes
>+ for (int next = nextUnsorted[subTree]; next != -1;) {
>+ int current = next;
>+ next = nextUnsorted[next];
>+ 
>+ // Destroy this unsorted node
>+ destroyNode(current);
>+ }
>+ 
>+ // Destroy left subtree
>+ removeSubTree(leftSubTree[subTree]);
>+ 
>+ // Destroy right subtree
>+ removeSubTree(rightSubTree[subTree]);
>+ 
>+ replaceNode(subTree, -1);
>+ // Destroy pivot node
>+ destroyNode(subTree);
>+ }
>+ 
>+ /**
>+ * Schedules the node for removal. If the node can be removed in constant time,
>+ * it is removed immediately.
>+ * 
>+ * @param subTree
>+ * @return the replacement node
>+ * @since 3.1
>+ */
>+ private final int lazyRemoveNode(int subTree) {
>+ int left = leftSubTree[subTree];
>+ int right = rightSubTree[subTree];
>+
>+ // If this is a leaf node, remove it immediately
>+ if (left == -1 && right == -1) {
>+ int result = nextUnsorted[subTree];
>+ replaceNode(subTree, result);
>+ destroyNode(subTree);
>+ return result;
>+ }
>+ 
>+ // Otherwise, flag it for future removal
>+ Object value = contents[subTree];
>+ contents[subTree] = lazyRemovalFlag;
>+ treeSize[subTree]--;
>+ if (objectIndices != null) {
>+ objectIndices.remove(value);
>+ }
>+ 
>+ return subTree;
>+ }
>+ 
>+ /**
>+ * Removes the given subtree, replacing it with one of its children.
>+ * Returns the new root of the subtree
>+ * 
>+ * @param subTree
>+ * @return
>+ * @since 3.1
>+ */
>+ private final int removeNode(int subTree) {
>+ int left = leftSubTree[subTree];
>+ int right = rightSubTree[subTree];
>+ 
>+ if (left == -1 || right == -1) {
>+ int result = -1;
>+ 
>+ if (left == -1 && right == -1) {
>+ // If this is a leaf node, replace it with its first unsorted child
>+ result = nextUnsorted[subTree];
>+ } else {
>+ // Either the left or right child is missing -- replace with the remaining child 
>+ if (left == -1) {
>+ result = right;
>+ } else {
>+ result = left;
>+ }
>+
>+ try {
>+ result = partition(result, new FastProgressReporter());
>+ } catch (InterruptedException e) {
>+ 
>+ }
>+ if (result == -1) {
>+ result = nextUnsorted[subTree];
>+ } else {
>+	 int unsorted = nextUnsorted[subTree];
>+	 nextUnsorted[result] = unsorted;
>+	 int additionalNodes = 0;
>+	 if (unsorted != -1) {
>+	 parentTree[unsorted] = result;
>+	 additionalNodes = treeSize[unsorted];
>+	 }
>+	 treeSize[result] += additionalNodes;
>+ }
>+ }
>+ 
>+ replaceNode(subTree, result);
>+ destroyNode(subTree);
>+ return result;
>+ }
>+ 
>+ // Find the edges that lead to the next-smallest and
>+ // next-largest nodes
>+ Edge nextSmallest = new Edge(subTree, DIR_LEFT);
>+ while (!nextSmallest.isNull()) {
>+ nextSmallest.advance(DIR_RIGHT);
>+ }
>+ 
>+ Edge nextLargest = new Edge(subTree, DIR_RIGHT);
>+ while (!nextLargest.isNull()) {
>+ nextLargest.advance(DIR_LEFT);
>+ }
>+ 
>+ // Index of the replacement node
>+ int replacementNode = -1;
>+ 
>+ // Count of number of nodes moved to the right
>+ 
>+ int leftSize = getSubtreeSize(left);
>+ int rightSize = getSubtreeSize(right);
>+ 
>+ // Swap with a child from the larger subtree
>+ if (leftSize > rightSize) {
>+ replacementNode = nextSmallest.getStart();
>+
>+ // Move any unsorted nodes that are larger than the replacement node into
>+ // the left subtree of the next-largest node
>+ Edge unsorted = new Edge(replacementNode, DIR_UNSORTED);
>+ while (!unsorted.isNull()) {
>+ int target = unsorted.getTarget();
>+ 
>+ if (!isLess(target, replacementNode)) {
>+ unsorted.setTarget(nextUnsorted[target]);
>+ nextLargest.setTarget(addUnsorted(nextLargest.getTarget(), target));
>+ } else {
>+ unsorted.advance(DIR_UNSORTED);
>+ }
>+ }
>+ 
>+ forceRecomputeTreeSize(unsorted.getStart(), replacementNode);
>+ forceRecomputeTreeSize(nextLargest.getStart(), subTree);
>+ } else {
>+ replacementNode = nextLargest.getStart();
>+
>+ // Move any unsorted nodes that are smaller than the replacement node into
>+ // the right subtree of the next-smallest node
>+ Edge unsorted = new Edge(replacementNode, DIR_UNSORTED);
>+ while (!unsorted.isNull()) {
>+ int target = unsorted.getTarget();
>+ 
>+ if (isLess(target, replacementNode)) {
>+ unsorted.setTarget(nextUnsorted[target]);
>+ nextSmallest.setTarget(addUnsorted(nextSmallest.getTarget(), target));
>+ } else {
>+ unsorted.advance(DIR_UNSORTED);
>+ }
>+ }
>+ 
>+ forceRecomputeTreeSize(unsorted.getStart(), replacementNode);
>+ forceRecomputeTreeSize(nextSmallest.getStart(), subTree);
>+ }
>+ 
>+ // Now all the affected treeSize[...] elements should be updated to reflect the
>+ // unsorted nodes that moved. Swap nodes. 
>+ Object replacementContent = contents[replacementNode];
>+ contents[replacementNode] = contents[subTree];
>+ contents[subTree] = replacementContent;
>+ 
>+ if (objectIndices != null) {
>+ objectIndices.put(replacementContent, subTree);
>+ // Note: currently we don't bother updating the index of the replacement
>+ // node since we're going to remove it immediately afterwards and there's
>+ // no good reason to search for the index in a method that was given the
>+ // index as a parameter...
>+ 
>+ // objectIndices.put(contents[replacementNode], replacementNode)
>+ }
>+ 
>+ int replacementParent = parentTree[replacementNode]; 
>+ 
>+ replaceNode(replacementNode, removeNode(replacementNode));
>+ //Edge parentEdge = getEdgeTo(replacementNode);
>+ //parentEdge.setTarget(removeNode(replacementNode));
>+
>+ forceRecomputeTreeSize(replacementParent, subTree);
>+ recomputeTreeSize(subTree);
>+ 
>+ //testInvariants();
>+ 
>+ return subTree;
>+ }
>+ 
>+ /**
>+ * Removes all elements from the collection
>+ * 
>+ * @since 3.1
>+ */
>+ public final void clear() {
>+ lastNode = 0;
>+ setArraySize(MIN_CAPACITY);
>+ root = -1;
>+ firstUnusedNode = -1;
>+ objectIndices = null;
>+ 
>+ testInvariants();
>+ }
>+ 
>+ public Comparator getComparator() {
>+ return comparator;
>+ }
>+ 
>+ /**
>+ * Fills in an array of size n with the n smallest elements from the collection.
>+ * Note that the returned elements are not sorted, however these would be the first
>+ * elements in the list if the collection were sorted. Returns the number of elements
>+ * inserted into the result array (this will always equal the length of the array if
>+ * the array is smaller than the size of the collection).
>+ * 
>+ * 
>+ * When returning a sorted array, the algorithm runs in O(s + n * lg (n)) and when returning
>+ * an unsorted array, the algorithm runs in O(s + n) time, where s is the size of the collection
>+ * and n is the size of the output. The partial sort order computed in previous calls to
>+ * this method is remembered and used to speed up subsequent calls. That is, if this method is
>+ * called twice on the same range, its runtime will be closer to O(n) on subsequent calls (regardless
>+ * of sorting).
>+ * 
>+ * 
>+ * @param result 
>+ * @since 3.1
>+ */
>+ public final int getFirst(Object[] result, boolean sorted, FastProgressReporter mon) throws InterruptedException {
>+ int returnValue = getRange(result, 0, sorted, mon);
>+ 
>+ testInvariants();
>+ 
>+ return returnValue;
>+ }
>+ 
>+ public final int getFirst(Object[] result, boolean sorted) {
>+ int returnValue = 0;
>+ 
>+ try {
>+ returnValue = getFirst(result, sorted, new FastProgressReporter());
>+ } catch (InterruptedException e) {
>+ }
>+ 
>+ testInvariants();
>+ 
>+ return returnValue;
>+ }
>+ 
>+ /**
>+ * Given a position defined by k and an array of size n, this fills in the array with
>+ * the kth smallest element through to the (k+n)th smallest element. For example, 
>+ * getRange(myArray, 10) would fill in myArray starting with the 10th smallest item
>+ * in the collection.
>+ * 
>+ * 
>+ * When returning a sorted array, the algorithm runs in O(s + n * lg (n)) and when returning
>+ * an unsorted array, the algorithm runs in O(s + n) time, where s is the size of the collection
>+ * and n is the size of the output. The partial sort order computed in previous calls to
>+ * this method is remembered and used to speed up subsequent calls. That is, if this method is
>+ * called twice on the same range, its runtime will be closer to O(n) on subsequent calls (regardless
>+ * of sorting).
>+ * 
>+ * 
>+ * Returns the number of elements
>+ * inserted into the result array (this will always equal the length of the array if
>+ * the array is smaller than the size of the collection).
>+ * 
>+ * @param result 
>+ * @since 3.1
>+ */
>+ public final int getRange(Object[] result, int rangeStart, boolean sorted, FastProgressReporter mon) throws InterruptedException {
>+ return getRange(result, 0, rangeStart, root, sorted, mon);
>+ }
>+ 
>+ public final int getRange(Object[] result, int rangeStart, boolean sorted) {
>+ int returnValue = 0;
>+ 
>+ try {
>+ returnValue = getRange(result, rangeStart, sorted, new FastProgressReporter());
>+ } catch (InterruptedException e) {
>+ }
>+ 
>+ testInvariants();
>+ 
>+ return returnValue;
>+ }
>+ 
>+ /**
>+ * Returns the item at the given index
>+ * 
>+ * @param index
>+ * @return
>+ * @since 3.1
>+ */
>+ public final Object getItem(int index) {
>+ Object[] result = new Object[1];
>+ try {
>+ getRange(result, index, false, new FastProgressReporter());
>+ } catch (InterruptedException e) {
>+ // shouldn't happen
>+ }
>+ Object returnValue = result[0];
>+ 
>+ testInvariants();
>+ 
>+ return returnValue;
>+ }
>+ 
>+ public final Object[] getItems(boolean sorted) {
>+ Object[] result = new Object[size()];
>+ 
>+ getRange(result, 0, sorted);
>+ 
>+ return result;
>+ }
>+ 
>+ private final int getRange(Object[] result, int resultIdx, int rangeStart, int node, boolean sorted, FastProgressReporter mon) throws InterruptedException {
>+ if (node == -1) {
>+ return 0;
>+ }
>+
>+ int availableSpace = result.length - resultIdx;
>+ 
>+ // If we're asking for all children of the current node, simply call getChildren
>+ if (rangeStart == 0) {
>+ if (treeSize[node] <= availableSpace) {
>+ return getChildren(result, resultIdx, node, sorted, mon);
>+ }
>+ }
>+ 
>+ node = partition(node, mon);
>+ if (node == -1) {
>+ return 0;
>+ }
>+ 
>+ int inserted = 0;
>+ 
>+ int numberLessThanNode = getSubtreeSize(leftSubTree[node]);
>+ 
>+ if (rangeStart < numberLessThanNode) {
>+ if (inserted < availableSpace) {
>+ inserted += getRange(result, resultIdx, rangeStart, leftSubTree[node], sorted, mon);
>+ }
>+ }
>+ 
>+ if (rangeStart <= numberLessThanNode) {
>+	 if (inserted < availableSpace) {
>+	 result[resultIdx + inserted] = contents[node];
>+	 inserted++;
>+	 }	 
>+ } 
>+ 
>+ if (inserted < availableSpace) {
>+ inserted += getRange(result, resultIdx + inserted,
>+ Math.max(rangeStart - numberLessThanNode - 1, 0), rightSubTree[node], sorted, mon);
>+ }
>+ 
>+ return inserted;
>+ }
>+ 
>+ /**
>+ * Fills in the available space in the given array with all children of the given node.
>+ * 
>+ * @param result 
>+ * @param resultIdx index in the result array where we will begin filling in children
>+ * @param node
>+ * @return the number of children added to the array
>+ * @since 3.1
>+ */
>+ private final int getChildren(Object[] result, int resultIdx, int node, boolean sorted, FastProgressReporter mon) throws InterruptedException {
>+ if (node == -1) {
>+ return 0;
>+ }
>+ 
>+ int tempIdx = resultIdx;
>+ 
>+ if (sorted) {
>+ node = partition(node, mon);
>+ if (node == -1) {
>+ return 0;
>+ }
>+ }
>+ 
>+ // Add child nodes smaller than this one
>+ if (tempIdx < result.length) {
>+ tempIdx += getChildren(result, tempIdx, leftSubTree[node], sorted, mon);
>+ }
>+ 
>+ // Add the pivot
>+ if (tempIdx < result.length) {
>+ Object value = contents[node];
>+ if (value != lazyRemovalFlag) {
>+ result[tempIdx++] = value;
>+ }
>+ }
>+ 
>+ // Add child nodes larger than this one
>+ if (tempIdx < result.length) {
>+ tempIdx += getChildren(result, tempIdx, rightSubTree[node], sorted, mon);
>+ }
>+ 
>+ // Add unsorted children (should be empty if the sorted flag was true)
>+ for (int unsortedNode = nextUnsorted[node]; unsortedNode != -1 && tempIdx < result.length; 
>+ 	unsortedNode = nextUnsorted[unsortedNode]) {
>+ 
>+ result[tempIdx++] = contents[unsortedNode];
>+ }
>+ 
>+ return tempIdx - resultIdx;
>+ }
>+
>+ /**
>+ * @param item
>+ * @return
>+ * @since 3.1
>+ */
>+ public boolean contains(Object item) {
>+ boolean returnValue = (getObjectIndex(item) != -1);
>+ 
>+ testInvariants();
>+ 
>+ return returnValue;
>+ }
>+}
>Index: src/org/eclipse/jface/viewers/deferred/SynchronousTableManager.java
>===================================================================
>RCS file: src/org/eclipse/jface/viewers/deferred/SynchronousTableManager.java
>diff -N src/org/eclipse/jface/viewers/deferred/SynchronousTableManager.java
>--- /dev/null	1 Jan 1970 00:00:00 -0000
>+++ src/org/eclipse/jface/viewers/deferred/SynchronousTableManager.java	1 Jan 1970 00:00:00 -0000
>@@ -0,0 +1,96 @@
>+/*******************************************************************************
>+ * Copyright (c) 2004 IBM Corporation and others.
>+ * All rights reserved. This program and the accompanying materials 
>+ * are made available under the terms of the Common Public License v1.0
>+ * which accompanies this distribution, and is available at
>+ * http://www.eclipse.org/legal/cpl-v10.html
>+ * 
>+ * Contributors:
>+ * IBM Corporation - initial API and implementation
>+ *******************************************************************************/
>+package org.eclipse.jface.viewers.deferred;
>+
>+import java.util.ArrayList;
>+import java.util.Collection;
>+import java.util.Comparator;
>+
>+import org.eclipse.core.runtime.IProgressMonitor;
>+
>+/**
>+ * @since 3.1
>+ */
>+public class SynchronousTableManager extends TableManager {
>+ 
>+ private int limit = 100;
>+ private IConcurrentContentProvider content;
>+ private IConcurrentTable table;
>+ private Comparator sortOrder;
>+ private Collection allElement = new ArrayList();
>+ private Object[] sentElements = new Object[0];
>+ private int rangeStart = 0;
>+ private int rangeLength = 0;
>+ 
>+ public void SynchronousTableManager(IConcurrentTable table, IConcurrentContentProvider contentProvider, Comparator sortOrder) {
>+ content = contentProvider;
>+ this.table = table;
>+ this.sortOrder = sortOrder;
>+ }
>+ 
>+ /* (non-Javadoc)
>+ * @see org.eclipse.jface.viewers.deferred.TableManager#add(java.util.Collection, org.eclipse.core.runtime.IProgressMonitor)
>+ */
>+ public void add(Collection items, IProgressMonitor mon) {
>+ 
>+ }
>+
>+ /* (non-Javadoc)
>+ * @see org.eclipse.jface.viewers.deferred.TableManager#remove(java.util.Collection, org.eclipse.core.runtime.IProgressMonitor)
>+ */
>+ public void remove(Collection items, IProgressMonitor mon) {
>+
>+ }
>+
>+ /* (non-Javadoc)
>+ * @see org.eclipse.jface.viewers.deferred.TableManager#update(java.util.Collection, org.eclipse.core.runtime.IProgressMonitor)
>+ */
>+ public void update(Collection items, IProgressMonitor mon) {
>+
>+ }
>+
>+ /* (non-Javadoc)
>+ * @see org.eclipse.jface.viewers.deferred.TableManager#refresh(org.eclipse.core.runtime.IProgressMonitor)
>+ */
>+ public void refresh(IProgressMonitor monitor) {
>+
>+ }
>+
>+ /* (non-Javadoc)
>+ * @see org.eclipse.jface.viewers.deferred.TableManager#setSortOrder(java.util.Comparator)
>+ */
>+ public void setSortOrder(Comparator sorter) {
>+
>+ }
>+
>+ /* (non-Javadoc)
>+ * @see org.eclipse.jface.viewers.deferred.TableManager#setRangeOfInterest(int, int)
>+ */
>+ public void setRangeOfInterest(int start, int length) {
>+ rangeStart = start;
>+ rangeLength = length;
>+ }
>+
>+ /* (non-Javadoc)
>+ * @see org.eclipse.jface.viewers.deferred.TableManager#setLimit(int)
>+ */
>+ public void setLimit(int maxTableSize) {
>+
>+ }
>+
>+ /* (non-Javadoc)
>+ * @see org.eclipse.jface.viewers.deferred.TableManager#getLimit()
>+ */
>+ public int getLimit() {
>+ return 0;
>+ }
>+
>+}
>Index: src/org/eclipse/jface/viewers/deferred/TableManager.java
>===================================================================
>RCS file: src/org/eclipse/jface/viewers/deferred/TableManager.java
>diff -N src/org/eclipse/jface/viewers/deferred/TableManager.java
>--- /dev/null	1 Jan 1970 00:00:00 -0000
>+++ src/org/eclipse/jface/viewers/deferred/TableManager.java	1 Jan 1970 00:00:00 -0000
>@@ -0,0 +1,32 @@
>+/*******************************************************************************
>+ * Copyright (c) 2004 IBM Corporation and others.
>+ * All rights reserved. This program and the accompanying materials 
>+ * are made available under the terms of the Common Public License v1.0
>+ * which accompanies this distribution, and is available at
>+ * http://www.eclipse.org/legal/cpl-v10.html
>+ * 
>+ * Contributors:
>+ * IBM Corporation - initial API and implementation
>+ *******************************************************************************/
>+package org.eclipse.jface.viewers.deferred;
>+
>+import java.util.Collection;
>+import java.util.Comparator;
>+
>+import org.eclipse.core.runtime.IProgressMonitor;
>+
>+/**
>+ * 
>+ * Not intended to be subclassed by clients
>+ * @since 3.1
>+ */
>+public abstract class TableManager {
>+	public abstract void add(Collection items, IProgressMonitor mon);
>+	public abstract void remove(Collection items, IProgressMonitor mon);	
>+	public abstract void update(Collection items, IProgressMonitor mon);
>+	public abstract void refresh(IProgressMonitor monitor);
>+ public abstract void setSortOrder(Comparator sorter);
>+	public abstract void setRangeOfInterest(int start, int length);	
>+	public abstract void setLimit(int maxTableSize);
>+	public abstract int getLimit();
>+}

Actions: View | Diff

Attachments on bug 72358: 14195 | 14991 | 14992 | 14993 | 15187 | 15205