bundles/org.eclipse.core.jobs/src/org/eclipse/core/internal/jobs/JobQueue.java

/*******************************************************************************
 *  Copyright (c) 2003, 2012 IBM Corporation and others.
 *  All rights reserved. This program and the accompanying materials
 *  are made available under the terms of the Eclipse Public License v1.0
 *  which accompanies this distribution, and is available at
 *  http://www.eclipse.org/legal/epl-v10.html
 * 
 *  Contributors:
 *     IBM - Initial API and implementation
 *******************************************************************************/
package org.eclipse.core.internal.jobs;

import java.util.Iterator;
import org.eclipse.core.runtime.*;

/**
 * A linked list based priority queue. 
 */
public final class JobQueue {
	/**
	 * The dummy entry sits between the head and the tail of the queue.
	 * dummy.previous() is the head, and dummy.next() is the tail.
	 */
	protected final InternalJob dummy;

	/**
	 * If true, conflicting jobs will be allowed to overtake others in the
	 * queue that have lower priority. If false, higher priority jumps can only
	 * move up the queue by overtaking jobs that they don't conflict with.
	 */
	private final boolean allowConflictOvertaking;

	private final boolean allowPriorityOvertaking;

	/**
	 * Create a new job queue. 
	 */
	public JobQueue(boolean allowConflictOvertaking) {
		this(allowConflictOvertaking, true);
	}

	/**
	 * Create a new job queue. 
	 */
	public JobQueue(boolean allowConflictOvertaking, boolean allowPriorityOvertaking) {
		this.allowPriorityOvertaking = allowPriorityOvertaking;
		//compareTo on dummy is never called
		dummy = new InternalJob("Queue-Head") {//$NON-NLS-1$
			public IStatus run(IProgressMonitor m) {
				return Status.OK_STATUS;
			}
		};
		dummy.setNext(dummy);
		dummy.setPrevious(dummy);
		this.allowConflictOvertaking = allowConflictOvertaking;
	}

	/** 
	 * remove all elements 
	 */
	public void clear() {
		dummy.setNext(dummy);
		dummy.setPrevious(dummy);
	}

	/**
	 * Return and remove the element with highest priority, or null if empty. 
	 */
	public InternalJob dequeue() {
		InternalJob toRemove = dummy.previous();
		if (toRemove == dummy)
			return null;
		return toRemove.remove();
	}

	/**
	 * Adds an item to the queue 
	 */
	public void enqueue(InternalJob newEntry) {
		//assert new entry is does not already belong to some other data structure
		Assert.isTrue(newEntry.next() == null);
		Assert.isTrue(newEntry.previous() == null);
		InternalJob tail = dummy.next();
		//overtake lower priority jobs. Only overtake conflicting jobs if allowed to
		while (canOvertake(newEntry, tail))
			tail = tail.next();
		//new entry is smaller than tail
		final InternalJob tailPrevious = tail.previous();
		newEntry.setNext(tail);
		newEntry.setPrevious(tailPrevious);
		tailPrevious.setNext(newEntry);
		tail.setPrevious(newEntry);
	}

	/**
	 * Returns whether the new entry to overtake the existing queue entry.
	 * @param newEntry The entry to be added to the queue
	 * @param queueEntry The existing queue entry
	 */
	private boolean canOvertake(InternalJob newEntry, InternalJob queueEntry) {
		//can never go past the end of the queue
		if (queueEntry == dummy)
			return false;
		//if the new entry was already in the wait queue, ensure it is re-inserted in correct position (bug 211799)
		if (newEntry.getWaitQueueStamp() > 0 && newEntry.getWaitQueueStamp() < queueEntry.getWaitQueueStamp())
			return true;
		//if the new entry has lower priority, there is no need to overtake the existing entry
		if (allowPriorityOvertaking && queueEntry.compareTo(newEntry) >= 0)
			return false;
		//the new entry has higher priority, but only overtake the existing entry if the queue allows it
		return allowConflictOvertaking || !newEntry.isConflicting(queueEntry);
	}

	/**
	 * Removes the given element from the queue. 
	 */
	public void remove(InternalJob toRemove) {
		toRemove.remove();
		//previous of toRemove might now bubble up
	}

	/**
	 * The given object has changed priority. Reshuffle the heap until it is
	 * valid.
	 */
	public void resort(InternalJob entry) {
		remove(entry);
		enqueue(entry);
	}

	/**
	 * Returns true if the queue is empty, and false otherwise. 
	 */
	public boolean isEmpty() {
		return dummy.next() == dummy;
	}

	/** 
	 * Return greatest element without removing it, or null if empty 
	 */
	public InternalJob peek() {
		return dummy.previous() == dummy ? null : dummy.previous();
	}

	public Iterator iterator() {
		return new Iterator() {
			InternalJob pointer = dummy;

			public boolean hasNext() {
				if (pointer.previous() == dummy)
					pointer = null;
				else
					pointer = pointer.previous();
				return pointer != null;
			}

			public Object next() {
				return pointer;
			}

			public void remove() {
				throw new UnsupportedOperationException();
			}

		};
	}
}