Attachment #14992 for bug #72358

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




/*******************************************************************************
 * 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);
    }
}




/*******************************************************************************
 * 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();
	        }
        }
    }
}




/*******************************************************************************
 * 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);
            }
        }
    }
}




/*******************************************************************************
 * 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);
    }
}




/*******************************************************************************
 * 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);
}




/*******************************************************************************
 * 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);
}




/*******************************************************************************
 * 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);
}




/*******************************************************************************
 * 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);
    }
}




/*******************************************************************************
 * 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.
 * 
 * <p>
 * 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. 
 * </p>
 * <p>
 * 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.
 * </p>
 * 
 * @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).
     * 
     * <p>
     * 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).
     * </p>
     * 
     * @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.
     * 
     * <p>
     * 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).
     * </p>
     *   
     * 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;
    }
}




/*******************************************************************************
 * 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;
    }

}




/*******************************************************************************
 * 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();
}

Return to bug 72358

Added Link Here

(-)src/org/eclipse/jface/viewers/deferred/AbstractConcurrentContentProvider.java (+66 lines)
1	/*******************************************************************************
2	* Copyright (c) 2004 IBM Corporation and others.
3	* All rights reserved. This program and the accompanying materials
4	* are made available under the terms of the Common Public License v1.0
5	* which accompanies this distribution, and is available at
6	* http://www.eclipse.org/legal/cpl-v10.html
7	*
8	* Contributors:
9	* IBM Corporation - initial API and implementation
10	*******************************************************************************/
11	package org.eclipse.jface.viewers.deferred;
12
13	import org.eclipse.jface.util.ListenerList;
14
15	/**
16	* @since 3.1
17	*/
18	public abstract class AbstractConcurrentContentProvider implements
19	IConcurrentContentProvider {
20
21	private ListenerList listeners = new ListenerList();
22
23	/* (non-Javadoc)
24	* @see org.eclipse.jface.viewers.deferred.IConcurrentContentProvider#addListener(org.eclipse.jface.viewers.deferred.IConcurrentContentProviderListener)
25	*/
26	public void addListener(IConcurrentContentProviderListener listener) {
27	listeners.add(listener);
28	}
29
30	protected void fireAdd(Object[] added) {
31	Object[] listenerArray = listeners.getListeners();
32
33	for (int i = 0; i < listenerArray.length; i++) {
34	IConcurrentContentProviderListener next = (IConcurrentContentProviderListener) listenerArray[i];
35
36	next.add(added);
37	}
38	}
39
40	protected void fireRemove(Object[] removed) {
41	Object[] listenerArray = listeners.getListeners();
42
43	for (int i = 0; i < listenerArray.length; i++) {
44	IConcurrentContentProviderListener next = (IConcurrentContentProviderListener) listenerArray[i];
45
46	next.remove(removed);
47	}
48	}
49
50	protected void fireUpdate(Object[] updated) {
51	Object[] listenerArray = listeners.getListeners();
52
53	for (int i = 0; i < listenerArray.length; i++) {
54	IConcurrentContentProviderListener next = (IConcurrentContentProviderListener) listenerArray[i];
55
56	next.update(updated);
57	}
58	}
59
60	/* (non-Javadoc)
61	* @see org.eclipse.jface.viewers.deferred.IConcurrentContentProvider#removeListener(org.eclipse.jface.viewers.deferred.IConcurrentContentProviderListener)
62	*/
63	public void removeListener(IConcurrentContentProviderListener listener) {
64	listeners.remove(listener);
65	}
66	}