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