bundles/org.eclipse.ui.ide/src/org/eclipse/ui/views/markers/internal/DeferredQueue.java - platform/eclipse.platform.ui - Git at Google

 /*******************************************************************************
  * Copyright (c) 2000, 2003 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.ui.views.markers.internal;

 import java.util.ArrayList;
 import java.util.Collection;
 import java.util.Comparator;
 import java.util.HashSet;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Set;
 import java.util.TreeSet;

 import org.eclipse.core.runtime.IProgressMonitor;
 import org.eclipse.core.runtime.NullProgressMonitor;
 import org.eclipse.core.runtime.SubProgressMonitor;

 import org.eclipse.swt.widgets.Table;

 import org.eclipse.jface.viewers.TableViewer;

 /**
  * Contains a queue of changes to be applied to a particular TableViewer.
  * This object is not multithread-friendly. The owning object must synchronize
  * its access to this object such that no two threads attempt to access it
  * simultaneously.
  */
 final class DeferredQueue {

 	private static final String SETTING_CONTENTS = Messages.getString("DeferredQueue.setting_contents"); //$NON-NLS-1$
 	/**
 	 * Maximum number of items to be added or removed from the viewer in a single update.
 	 * (Will be used for an initially empty table)
 	 */
 	private static final int MAX_UPDATE = 40;

 	/**
 	 * Minimum number of items to be added or removed from the viewer in a single update
 	 * (Will be used once the table size reaches (GROWTH_LIMIT)
 	 */
 	private static final int MIN_UPDATE = 1;

 	/**
 	 * Table size beyond which all updates will be approximately MIN_UPDATE
 	 */
 	private static final int GROWTH_LIMIT = 20000;

 	// Member variables

 	/**
 	 * Current sort order (note that this object does the sorting -- not the viewer. The
 	 * view contents are sorted by controlling their insertion order and position.)
 	 */
 	private Comparator sortOrder;

 	/**
 	 * Set of items currently visible in the viewer
 	 */
 	private Set visibleItems = new HashSet();

 	/**
 	 * Set of pending insertions that will occur at the end of the table (if the
 	 * viewer is sorted, this will be changed into a sorted collection). This
 	 * will not contain any items currently in the visibleItems set.
 	 */
 	private Set insertionsAtEnd = new HashSet();

 	/**
 	 * Set of pending insertions that will occur in the middle of the table. This
 	 * remains unsorted. Sorting will occur in the UI thread at insertion-time.
 	 * This will not contain any items currently in the visibleItems set.
 	 */
 	private Set insertionsInMiddle = new HashSet();

 	/**
 	 * List of pending removals. This is a subset of visibleItems.
 	 */
 	private Set pendingRemovals = new HashSet();

 	/**
 	 * List of pending changes. This is a subset of visibleItems.
 	 */
 	private Set pendingChanges = new HashSet();

 	/**
 	 * Pointer to the item currently at the end of the table, or null if
 	 * the table is currently empty.
 	 */
 	private Object lastVisible = null;

 	/**
 	 * True iff there may be items inthe insertionsInMiddle queue
 	 * that can be moved to the insertionsAtEnd queue. This is set to
 	 * true when lastVisible is reduced, and set to false when
 	 * insertionsInMiddle is repartitioned.
 	 */
 	private boolean lastDirty = false;

 	/**
 	 * pointer to the viewer being populated.
 	 */
 	private TableViewer viewer;

 	private boolean hasPendingChanges = false;

 	/**
 	 * Constructs a new DeferredQueue.
 	 *
 	 * @param viewer
 	 */
 	public DeferredQueue(TableViewer viewer) {
 		this.viewer = viewer;
 	}

 	/**
 	 * Returns the set of items currently visible in the viewer (read-only)
 	 *
 	 * @return the set of processed items
 	 */
 	public Object[] getVisibleItems() {
 		synchronized(visibleItems) {
 			return visibleItems.toArray();
 		}
 	}

 	/**
 	 * Queues the given set of items to be refreshed in the viewer. If there
 	 * are any items in the viewer (or its queues) that compare as equal(...)
 	 * to one of these items, the new item will replace the old one. Should
 	 * be run in a background thread.
 	 *
 	 * @param changes set if items to be refreshed in the viewer
 	 */
 	public void change(Collection changes) {
 		Iterator iter = changes.iterator();

 		while (iter.hasNext()) {
 			Object next = iter.next();
 			boolean isVisible = false;
 			synchronized(visibleItems) {
 				if (visibleItems.contains(next)) {
 					visibleItems.remove(next);
 					visibleItems.add(next);
 					pendingChanges.add(next);
 					isVisible = true;
 					hasPendingChanges = true;
 				}
 			}

 			if (!isVisible) {
 				if (insertionsInMiddle.contains(next)) {
 					insertionsInMiddle.remove(next);
 					insertionsInMiddle.add(next);
 					hasPendingChanges = true;
 				} else if (insertionsAtEnd.contains(next)) {
 					insertionsAtEnd.remove(next);
 					insertionsAtEnd.add(next);
 					hasPendingChanges = true;
 				}
 			}
 		}
 	}

 	/**
 	 * Sets the desired contents of the viewer, enqueueing any additions and removals
 	 * necessary such that the final contents of the viewer will be as specified.
 	 * Should be run in a background thread. If the given montor is canceled (possibly
 	 * in another thread), the operation will be aborted without modifying the queue.
 	 *
 	 * @param newPendingContents desired contents of the viewer
 	 * @param mon progress monitor
 	 */
 	public void set(Collection newPendingContents, IProgressMonitor mon) {
 		mon.beginTask(SETTING_CONTENTS, 100);

 		// Set of items in newPendingContents that are not currently in visibleItems
 		Set newInsertions = new HashSet();

 		// New pendingRemovals queue
 		Set newPendingRemovals = new HashSet();
 		// New insertionsInMiddle queue
 		Set newInsertionsInMiddle = new HashSet();
 		// New insertionsAtEnd queue
 		Set newInsertionsAtEnd = newEndSet();

 		addWithProgress(newInsertions, newPendingContents, mon, 5);
 		synchronized(visibleItems) {
 			addWithProgress(newPendingRemovals, visibleItems, mon, 5);
 			removeWithProgress(newPendingRemovals, newInsertions, mon, 5);
 			removeWithProgress(newInsertions, visibleItems, mon, 5);
 		}

 		if (newInsertions.isEmpty() && newPendingRemovals.isEmpty()) {
 			return;
 		}

 		SubProgressMonitor sub = new SubProgressMonitor(mon, 80);
 		SortUtil.partition(newInsertionsInMiddle, newInsertionsAtEnd, newInsertionsAtEnd, newInsertions,
 				sortOrder, lastVisible, sub);

 		// Do nothing if the operation was cancelled.
 		if (mon.isCanceled()) {
 			mon.done();
 			return;
 		}

 		// Now we've computed everything. Apply all the computed changes.
 		hasPendingChanges = true;
 		lastDirty = false;
 		insertionsAtEnd.clear();
 		insertionsAtEnd = newInsertionsAtEnd;

 		insertionsInMiddle.clear();
 		insertionsInMiddle = newInsertionsInMiddle;

 		pendingRemovals.clear();
 		pendingRemovals = newPendingRemovals;

 		mon.done();
 	}

 	/**
 	 * Applies the next set of changes to the table. Returns the number of items
 	 * actually refreshed. Must run in the UI thread.
 	 *
 	 * @param maximumToChange maximum number of queued changes to apply
 	 * @return the number of changes actually applied.
 	 */
 	private int nextChange(int maximumToChange) {
 		Collection result = SortUtil.removeFirst(pendingChanges, maximumToChange);

 		viewer.update(result.toArray(), null);

 		return result.size();
 	}

 	/**
 	 * Applies the next set of removals from the table. Must run in the UI thread.
 	 *
 	 * @param maximumToRemove maximum number of items to remove from the table.
 	 * @return the number of items actually removed.
 	 */
 	private int nextRemoval(int maximumToRemove) {
 		ArrayList result = new ArrayList(maximumToRemove);

 		int counter = maximumToRemove;

 		Iterator iter = pendingRemovals.iterator();
 		while (iter.hasNext() && counter > 0) {
 			Object next = iter.next();

 			result.add(next);

 			if (lastVisible != null && lastVisible.equals(next)) {
 				lastDirty = true;
 			}

 			iter.remove();
 			counter--;
 		}

 		synchronized(visibleItems) {
 			visibleItems.removeAll(result);
 		}

 		viewer.remove(result.toArray());

 		if (lastDirty) {
 			lastVisible = viewer.getElementAt(viewer.getTable().getItemCount() - 1);
 		}

 		return result.size();
 	}

 	/**
 	 * Applies the next set of insertions into the middle of the queue.
 	 *
 	 * @param maximumToInsert
 	 * @return
 	 */
 	private int nextInsertionInMiddle(int maximumToInsert) {

 		refreshQueues(new NullProgressMonitor());

 		Collection result = SortUtil.removeFirst(insertionsInMiddle, maximumToInsert);

 		synchronized(visibleItems) {
 			visibleItems.addAll(result);
 		}

 		// We manually compute the insertion position because setting a sorter on
 		// the viewer would force a refresh, which can be very slow with a large number
 		// of items.

 		Iterator iter = result.iterator();
 		while (iter.hasNext()) {
 			Object element = iter.next();

 			int insertionPos = getInsertPosition(element);
 			viewer.insert(element, insertionPos);
 		}

 		return result.size();
 	}

 	/**
 	 * Applies the next insertion at the end of the table. Returns the number of
 	 * items actually inserted.
 	 *
 	 * @param maximumToInsert maximum number of items to insert into the end
 	 * of the table
 	 * @return the number of items actually inserted into the table
 	 */
 	private int nextInsertionAtEnd(int maximumToInsert) {
 		refreshQueues(new NullProgressMonitor());

 		List result = new ArrayList(maximumToInsert);

 		Iterator iter = insertionsAtEnd.iterator();
 		for (int counter = 0; counter < maximumToInsert && iter.hasNext(); counter++) {
 			lastVisible = iter.next();

 			result.add(lastVisible);

 			iter.remove();
 		}

 		synchronized(visibleItems) {
 			visibleItems.addAll(result);
 		}

 		viewer.add(result.toArray());

 		return result.size();
 	}

 	/**
 	 * Clears the set of visible items, and reinserts everything from scratch.
 	 */
 	public void reset() {
 		synchronized(visibleItems) {
 			visibleItems.removeAll(pendingRemovals);

 			insertionsInMiddle.addAll(visibleItems);
 			lastVisible = null;
 			lastDirty = true;

 			visibleItems.clear();
 		}
 		pendingRemovals.clear();
 		hasPendingChanges = true;
 	}

 	/**
 	 * Returns true iff there are pending changes remaining to be applied.
 	 *
 	 * @return true iff there are pending changes to be applied to the table
 	 */
 	public boolean hasPendingChanges() {
 		return hasPendingChanges;
 	}

 	/**
 	 * Returns an estimate of the work remaining (the result is meaningful with respect
 	 * to the return value of nextUpdate())
 	 *
 	 * @return an estimate of the work remaining
 	 */
 	public int workRemaining() {
 		return pendingRemovals.size() + insertionsAtEnd.size() + insertionsInMiddle.size() + pendingChanges.size();
 	}

 	/**
 	 *
 	 * Cancels all pending insertions and removals.
 	 */
 	public void cancelPending() {
 		insertionsAtEnd.clear();
 		insertionsInMiddle.clear();
 		pendingRemovals.clear();
 		hasPendingChanges = false;
 	}

 	public void setComparator(Comparator c) {
 		if (sortOrder == c) {
 			return;
 		}

 		sortOrder = c;

 		lastVisible = null;

 		insertionsInMiddle.addAll(insertionsAtEnd);
 		insertionsAtEnd = newEndSet();
 		lastDirty = true;

 		reset();
 	}

 	/**
 	 * Applies any deferred sorting.
 	 * @param mon
 	 */
 	public void refreshQueues(IProgressMonitor mon) {
 		if (lastDirty) {
 			if (mon.isCanceled()) {
 				return;
 			}
 			HashSet newInsertionsInMiddle = new HashSet();
 			SortUtil.partition(newInsertionsInMiddle, insertionsAtEnd, insertionsAtEnd,
 					insertionsInMiddle, sortOrder, lastVisible, mon);

 			if (mon.isCanceled()) {
 				insertionsInMiddle.removeAll(insertionsAtEnd);
 			} else {
 				insertionsInMiddle = newInsertionsInMiddle;
 				lastDirty = false;
 			}
 		}
 	}

 	/**
 	 * Determines the insertion position for the given element in the table. Note
 	 * that this is essentially the same as TableViewer.getInsertPosition, but we
 	 * need to do it here because if we set a sorter on the TableViewer, this will
 	 * force a refresh of the table which can be extremely slow.
 	 *
 	 * @param element object whose insertion position is being computed.
 	 * @return
 	 */
 	private int getInsertPosition(Object element) {
 		Table table = viewer.getTable();
 		if(sortOrder == null)
 			return table.getItemCount();
 		int count = table.getItemCount();
 		int min = 0, max = count - 1;
 		while (min <= max) {
 			int mid = (min + max) / 2;
 			Object data = table.getItem(mid).getData();
 			int compare = sortOrder.compare(data, element);
 			if (compare == 0) {
 				// find first item > element
 				while (compare == 0) {
 					++mid;
 					if (mid >= count) {
 						break;
 					}
 					data = table.getItem(mid).getData();
 					compare = sortOrder.compare(data, element);
 				}
 				return mid;
 			}
 			if (compare < 0)
 				min = mid + 1;
 			else
 				max = mid - 1;
 		}
 		return min;
 	}

 	/**
 	 * Performs a single update to the viewer. Based on the contents of the pending* queues,
 	 * items will either be removed, added, or refreshed in the viewer (in that order). This
 	 * should only be called within a synchronized block, since the various queues shouldn't
 	 * be modified during an update. This method is invoked repeatedly by jobs to gradually
 	 * apply the pending changes.
 	 */
 	public int nextUpdate() {

 		int pendingRemovalsSize = pendingRemovals.size();

 		if (pendingRemovalsSize > 0) {
 			int currentSize = countVisibleItems();
 			// Determine if we should remove incrementally or rebuild the table from scratch.
 			int finalSize = currentSize - pendingRemovalsSize;

 			if (finalSize * finalSize * 2 <= currentSize * currentSize) {

 				// If we're removing enough items that it would be faster just to rebuild
 				// the table from scratch, do it that way.

 				reset();
 				getViewer().refresh();

 				return 0;
 			}

 			return nextRemoval(nextUpdateSize());
 		} else if (insertionsInMiddle.size() > 0) {
 			return nextInsertionInMiddle(nextUpdateSize());
 		} else if (insertionsAtEnd.size() > 0) {
 			return nextInsertionAtEnd(MAX_UPDATE);
 		} else if (pendingChanges.size() > 0) {
 			return nextChange(MAX_UPDATE);
 		}

 		hasPendingChanges = false;

 		return 0;
 	}

 	/**
 	 * @return
 	 */
 	int countVisibleItems() {
 		synchronized(visibleItems) {
 			return visibleItems.size();
 		}
 	}

 	/**
 	 * Returns the number of items that should be added or removed in the next
 	 * incremental update. This is used for the operations whose runtime increases
 	 * with the size of the visible items.
 	 *
 	 * @return the number of changes that should be applied in the next update
 	 */
 	private int nextUpdateSize() {
 		int size = GROWTH_LIMIT * (MAX_UPDATE - MIN_UPDATE)
 			/ (GROWTH_LIMIT + countVisibleItems()) + MIN_UPDATE;

 		return size;
 	}

 	/**
 	 * Returns the TableViewer that is being populated.
 	 *
 	 * @return the TableViewer that is being modified.
 	 */
 	public TableViewer getViewer() {
 		return viewer;
 	}

 	/**
 	 * Returns a new empty set to be used for insertionsAtEnd
 	 *
 	 * @return
 	 */
 	private Set newEndSet() {
 		if (sortOrder == null) {
 			return new HashSet();
 		} else {
 			return new TreeSet(sortOrder);
 		}
 	}


 	/**
 	 * Removes all the given items from the target collection, and updates
 	 * the given progress monitor by the given amount. If the monitor is cancelled,
 	 * no changes are made to the target collection.
 	 *
 	 * @param target items will be removed from this collection
 	 * @param toRemove items to be removed from the collection
 	 * @param mon progress monitor to be updated
 	 * @param worked amount to update the monitor
 	 */
 	private static void removeWithProgress(Collection target, Collection toRemove,
 										   IProgressMonitor mon, int worked) {
 		if (mon.isCanceled()) {
 			return;
 		}

 		target.removeAll(toRemove);

 		mon.worked(worked);
 	}

 	/**
 	 * Inserts all the given items into the target collection, and updates
 	 * the progress monitor. If the monitor is cancelled, no changes will
 	 * be made to the target.
 	 *
 	 * @param target collection into which items will be inserted
 	 * @param toInsert items to be inserted into the collection
 	 * @param mon progress monitor that will be updated
 	 * @param worked amount to update the progress monitor
 	 */
 	private static void addWithProgress(Collection target, Collection toInsert,
 										IProgressMonitor mon, int worked) {
 		if (mon.isCanceled()) {
 			return;
 		}

 		target.addAll(toInsert);

 		mon.worked(worked);
 	}

 	/**
 	 * @return
 	 */
 	public Comparator getSorter() {
 		return sortOrder;
 	}


 }
	/*******************************************************************************
	* Copyright (c) 2000, 2003 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.ui.views.markers.internal;

	import java.util.ArrayList;
	import java.util.Collection;
	import java.util.Comparator;
	import java.util.HashSet;
	import java.util.Iterator;
	import java.util.List;
	import java.util.Set;
	import java.util.TreeSet;

	import org.eclipse.core.runtime.IProgressMonitor;
	import org.eclipse.core.runtime.NullProgressMonitor;
	import org.eclipse.core.runtime.SubProgressMonitor;

	import org.eclipse.swt.widgets.Table;

	import org.eclipse.jface.viewers.TableViewer;

	/**
	* Contains a queue of changes to be applied to a particular TableViewer.
	* This object is not multithread-friendly. The owning object must synchronize
	* its access to this object such that no two threads attempt to access it
	* simultaneously.
	*/
	final class DeferredQueue {

	private static final String SETTING_CONTENTS = Messages.getString("DeferredQueue.setting_contents"); //$NON-NLS-1$
	/**
	* Maximum number of items to be added or removed from the viewer in a single update.
	* (Will be used for an initially empty table)
	*/
	private static final int MAX_UPDATE = 40;

	/**
	* Minimum number of items to be added or removed from the viewer in a single update
	* (Will be used once the table size reaches (GROWTH_LIMIT)
	*/
	private static final int MIN_UPDATE = 1;

	/**
	* Table size beyond which all updates will be approximately MIN_UPDATE
	*/
	private static final int GROWTH_LIMIT = 20000;

	// Member variables

	/**
	* Current sort order (note that this object does the sorting -- not the viewer. The
	* view contents are sorted by controlling their insertion order and position.)
	*/
	private Comparator sortOrder;

	/**
	* Set of items currently visible in the viewer
	*/
	private Set visibleItems = new HashSet();

	/**
	* Set of pending insertions that will occur at the end of the table (if the
	* viewer is sorted, this will be changed into a sorted collection). This
	* will not contain any items currently in the visibleItems set.
	*/
	private Set insertionsAtEnd = new HashSet();

	/**
	* Set of pending insertions that will occur in the middle of the table. This
	* remains unsorted. Sorting will occur in the UI thread at insertion-time.
	* This will not contain any items currently in the visibleItems set.
	*/
	private Set insertionsInMiddle = new HashSet();

	/**
	* List of pending removals. This is a subset of visibleItems.
	*/
	private Set pendingRemovals = new HashSet();

	/**
	* List of pending changes. This is a subset of visibleItems.
	*/
	private Set pendingChanges = new HashSet();

	/**
	* Pointer to the item currently at the end of the table, or null if
	* the table is currently empty.
	*/
	private Object lastVisible = null;

	/**
	* True iff there may be items inthe insertionsInMiddle queue
	* that can be moved to the insertionsAtEnd queue. This is set to
	* true when lastVisible is reduced, and set to false when
	* insertionsInMiddle is repartitioned.
	*/
	private boolean lastDirty = false;

	/**
	* pointer to the viewer being populated.
	*/
	private TableViewer viewer;

	private boolean hasPendingChanges = false;

	/**
	* Constructs a new DeferredQueue.
	*
	* @param viewer
	*/
	public DeferredQueue(TableViewer viewer) {
	this.viewer = viewer;
	}

	/**
	* Returns the set of items currently visible in the viewer (read-only)
	*
	* @return the set of processed items
	*/
	public Object[] getVisibleItems() {
	synchronized(visibleItems) {
	return visibleItems.toArray();
	}
	}

	/**
	* Queues the given set of items to be refreshed in the viewer. If there
	* are any items in the viewer (or its queues) that compare as equal(...)
	* to one of these items, the new item will replace the old one. Should
	* be run in a background thread.
	*
	* @param changes set if items to be refreshed in the viewer
	*/
	public void change(Collection changes) {
	Iterator iter = changes.iterator();

	while (iter.hasNext()) {
	Object next = iter.next();
	boolean isVisible = false;
	synchronized(visibleItems) {
	if (visibleItems.contains(next)) {
	visibleItems.remove(next);
	visibleItems.add(next);
	pendingChanges.add(next);
	isVisible = true;
	hasPendingChanges = true;
	}
	}

	if (!isVisible) {
	if (insertionsInMiddle.contains(next)) {
	insertionsInMiddle.remove(next);
	insertionsInMiddle.add(next);
	hasPendingChanges = true;
	} else if (insertionsAtEnd.contains(next)) {
	insertionsAtEnd.remove(next);
	insertionsAtEnd.add(next);
	hasPendingChanges = true;
	}
	}
	}
	}

	/**
	* Sets the desired contents of the viewer, enqueueing any additions and removals
	* necessary such that the final contents of the viewer will be as specified.
	* Should be run in a background thread. If the given montor is canceled (possibly
	* in another thread), the operation will be aborted without modifying the queue.
	*
	* @param newPendingContents desired contents of the viewer
	* @param mon progress monitor
	*/
	public void set(Collection newPendingContents, IProgressMonitor mon) {
	mon.beginTask(SETTING_CONTENTS, 100);

	// Set of items in newPendingContents that are not currently in visibleItems
	Set newInsertions = new HashSet();

	// New pendingRemovals queue
	Set newPendingRemovals = new HashSet();
	// New insertionsInMiddle queue
	Set newInsertionsInMiddle = new HashSet();
	// New insertionsAtEnd queue
	Set newInsertionsAtEnd = newEndSet();

	addWithProgress(newInsertions, newPendingContents, mon, 5);
	synchronized(visibleItems) {
	addWithProgress(newPendingRemovals, visibleItems, mon, 5);
	removeWithProgress(newPendingRemovals, newInsertions, mon, 5);
	removeWithProgress(newInsertions, visibleItems, mon, 5);
	}

	if (newInsertions.isEmpty() && newPendingRemovals.isEmpty()) {
	return;
	}

	SubProgressMonitor sub = new SubProgressMonitor(mon, 80);
	SortUtil.partition(newInsertionsInMiddle, newInsertionsAtEnd, newInsertionsAtEnd, newInsertions,
	sortOrder, lastVisible, sub);

	// Do nothing if the operation was cancelled.
	if (mon.isCanceled()) {
	mon.done();
	return;
	}

	// Now we've computed everything. Apply all the computed changes.
	hasPendingChanges = true;
	lastDirty = false;
	insertionsAtEnd.clear();
	insertionsAtEnd = newInsertionsAtEnd;

	insertionsInMiddle.clear();
	insertionsInMiddle = newInsertionsInMiddle;

	pendingRemovals.clear();
	pendingRemovals = newPendingRemovals;

	mon.done();
	}

	/**
	* Applies the next set of changes to the table. Returns the number of items
	* actually refreshed. Must run in the UI thread.
	*
	* @param maximumToChange maximum number of queued changes to apply
	* @return the number of changes actually applied.
	*/
	private int nextChange(int maximumToChange) {
	Collection result = SortUtil.removeFirst(pendingChanges, maximumToChange);

	viewer.update(result.toArray(), null);

	return result.size();
	}

	/**
	* Applies the next set of removals from the table. Must run in the UI thread.
	*
	* @param maximumToRemove maximum number of items to remove from the table.
	* @return the number of items actually removed.
	*/
	private int nextRemoval(int maximumToRemove) {
	ArrayList result = new ArrayList(maximumToRemove);

	int counter = maximumToRemove;

	Iterator iter = pendingRemovals.iterator();
	while (iter.hasNext() && counter > 0) {
	Object next = iter.next();

	result.add(next);

	if (lastVisible != null && lastVisible.equals(next)) {
	lastDirty = true;
	}

	iter.remove();
	counter--;
	}

	synchronized(visibleItems) {
	visibleItems.removeAll(result);
	}

	viewer.remove(result.toArray());

	if (lastDirty) {
	lastVisible = viewer.getElementAt(viewer.getTable().getItemCount() - 1);
	}

	return result.size();
	}

	/**
	* Applies the next set of insertions into the middle of the queue.
	*
	* @param maximumToInsert
	* @return
	*/
	private int nextInsertionInMiddle(int maximumToInsert) {

	refreshQueues(new NullProgressMonitor());

	Collection result = SortUtil.removeFirst(insertionsInMiddle, maximumToInsert);

	synchronized(visibleItems) {
	visibleItems.addAll(result);
	}

	// We manually compute the insertion position because setting a sorter on
	// the viewer would force a refresh, which can be very slow with a large number
	// of items.

	Iterator iter = result.iterator();
	while (iter.hasNext()) {
	Object element = iter.next();

	int insertionPos = getInsertPosition(element);
	viewer.insert(element, insertionPos);
	}

	return result.size();
	}

	/**
	* Applies the next insertion at the end of the table. Returns the number of
	* items actually inserted.
	*
	* @param maximumToInsert maximum number of items to insert into the end
	* of the table
	* @return the number of items actually inserted into the table
	*/
	private int nextInsertionAtEnd(int maximumToInsert) {
	refreshQueues(new NullProgressMonitor());

	List result = new ArrayList(maximumToInsert);

	Iterator iter = insertionsAtEnd.iterator();
	for (int counter = 0; counter < maximumToInsert && iter.hasNext(); counter++) {
	lastVisible = iter.next();

	result.add(lastVisible);

	iter.remove();
	}

	synchronized(visibleItems) {
	visibleItems.addAll(result);
	}

	viewer.add(result.toArray());

	return result.size();
	}

	/**
	* Clears the set of visible items, and reinserts everything from scratch.
	*/
	public void reset() {
	synchronized(visibleItems) {
	visibleItems.removeAll(pendingRemovals);

	insertionsInMiddle.addAll(visibleItems);
	lastVisible = null;
	lastDirty = true;

	visibleItems.clear();
	}
	pendingRemovals.clear();
	hasPendingChanges = true;
	}

	/**
	* Returns true iff there are pending changes remaining to be applied.
	*
	* @return true iff there are pending changes to be applied to the table
	*/
	public boolean hasPendingChanges() {
	return hasPendingChanges;
	}

	/**
	* Returns an estimate of the work remaining (the result is meaningful with respect
	* to the return value of nextUpdate())
	*
	* @return an estimate of the work remaining
	*/
	public int workRemaining() {
	return pendingRemovals.size() + insertionsAtEnd.size() + insertionsInMiddle.size() + pendingChanges.size();
	}

	/**
	*
	* Cancels all pending insertions and removals.
	*/
	public void cancelPending() {
	insertionsAtEnd.clear();
	insertionsInMiddle.clear();
	pendingRemovals.clear();
	hasPendingChanges = false;
	}

	public void setComparator(Comparator c) {
	if (sortOrder == c) {
	return;
	}

	sortOrder = c;

	lastVisible = null;

	insertionsInMiddle.addAll(insertionsAtEnd);
	insertionsAtEnd = newEndSet();
	lastDirty = true;

	reset();
	}

	/**
	* Applies any deferred sorting.
	* @param mon
	*/
	public void refreshQueues(IProgressMonitor mon) {
	if (lastDirty) {
	if (mon.isCanceled()) {
	return;
	}
	HashSet newInsertionsInMiddle = new HashSet();
	SortUtil.partition(newInsertionsInMiddle, insertionsAtEnd, insertionsAtEnd,
	insertionsInMiddle, sortOrder, lastVisible, mon);

	if (mon.isCanceled()) {
	insertionsInMiddle.removeAll(insertionsAtEnd);
	} else {
	insertionsInMiddle = newInsertionsInMiddle;
	lastDirty = false;
	}
	}
	}

	/**
	* Determines the insertion position for the given element in the table. Note
	* that this is essentially the same as TableViewer.getInsertPosition, but we
	* need to do it here because if we set a sorter on the TableViewer, this will
	* force a refresh of the table which can be extremely slow.
	*
	* @param element object whose insertion position is being computed.
	* @return
	*/
	private int getInsertPosition(Object element) {
	Table table = viewer.getTable();
	if(sortOrder == null)
	return table.getItemCount();
	int count = table.getItemCount();
	int min = 0, max = count - 1;
	while (min <= max) {
	int mid = (min + max) / 2;
	Object data = table.getItem(mid).getData();
	int compare = sortOrder.compare(data, element);
	if (compare == 0) {
	// find first item > element
	while (compare == 0) {
	++mid;
	if (mid >= count) {
	break;
	}
	data = table.getItem(mid).getData();
	compare = sortOrder.compare(data, element);
	}
	return mid;
	}
	if (compare < 0)
	min = mid + 1;
	else
	max = mid - 1;
	}
	return min;
	}

	/**
	* Performs a single update to the viewer. Based on the contents of the pending* queues,
	* items will either be removed, added, or refreshed in the viewer (in that order). This
	* should only be called within a synchronized block, since the various queues shouldn't
	* be modified during an update. This method is invoked repeatedly by jobs to gradually
	* apply the pending changes.
	*/
	public int nextUpdate() {

	int pendingRemovalsSize = pendingRemovals.size();

	if (pendingRemovalsSize > 0) {
	int currentSize = countVisibleItems();
	// Determine if we should remove incrementally or rebuild the table from scratch.
	int finalSize = currentSize - pendingRemovalsSize;

	if (finalSize * finalSize * 2 <= currentSize * currentSize) {

	// If we're removing enough items that it would be faster just to rebuild
	// the table from scratch, do it that way.

	reset();
	getViewer().refresh();

	return 0;
	}

	return nextRemoval(nextUpdateSize());
	} else if (insertionsInMiddle.size() > 0) {
	return nextInsertionInMiddle(nextUpdateSize());
	} else if (insertionsAtEnd.size() > 0) {
	return nextInsertionAtEnd(MAX_UPDATE);
	} else if (pendingChanges.size() > 0) {
	return nextChange(MAX_UPDATE);
	}

	hasPendingChanges = false;

	return 0;
	}

	/**
	* @return
	*/
	int countVisibleItems() {
	synchronized(visibleItems) {
	return visibleItems.size();
	}
	}

	/**
	* Returns the number of items that should be added or removed in the next
	* incremental update. This is used for the operations whose runtime increases
	* with the size of the visible items.
	*
	* @return the number of changes that should be applied in the next update
	*/
	private int nextUpdateSize() {
	int size = GROWTH_LIMIT * (MAX_UPDATE - MIN_UPDATE)
	/ (GROWTH_LIMIT + countVisibleItems()) + MIN_UPDATE;

	return size;
	}

	/**
	* Returns the TableViewer that is being populated.
	*
	* @return the TableViewer that is being modified.
	*/
	public TableViewer getViewer() {
	return viewer;
	}

	/**
	* Returns a new empty set to be used for insertionsAtEnd
	*
	* @return
	*/
	private Set newEndSet() {
	if (sortOrder == null) {
	return new HashSet();
	} else {
	return new TreeSet(sortOrder);
	}
	}


	/**
	* Removes all the given items from the target collection, and updates
	* the given progress monitor by the given amount. If the monitor is cancelled,
	* no changes are made to the target collection.
	*
	* @param target items will be removed from this collection
	* @param toRemove items to be removed from the collection
	* @param mon progress monitor to be updated
	* @param worked amount to update the monitor
	*/
	private static void removeWithProgress(Collection target, Collection toRemove,
	IProgressMonitor mon, int worked) {
	if (mon.isCanceled()) {
	return;
	}

	target.removeAll(toRemove);

	mon.worked(worked);
	}

	/**
	* Inserts all the given items into the target collection, and updates
	* the progress monitor. If the monitor is cancelled, no changes will
	* be made to the target.
	*
	* @param target collection into which items will be inserted
	* @param toInsert items to be inserted into the collection
	* @param mon progress monitor that will be updated
	* @param worked amount to update the progress monitor
	*/
	private static void addWithProgress(Collection target, Collection toInsert,
	IProgressMonitor mon, int worked) {
	if (mon.isCanceled()) {
	return;
	}

	target.addAll(toInsert);

	mon.worked(worked);
	}

	/**
	* @return
	*/
	public Comparator getSorter() {
	return sortOrder;
	}


	}