Copyright (c) 2003, 2012 IBM Corporation and others.
 This program and the accompanying materials
 are made available under the terms of the Eclipse Public License 2.0
 which accompanies this distribution, and is available at
 https://www.eclipse.org/legal/epl-2.0/
 SPDX-License-Identifier: EPL-2.0
 Contributors:
    IBM - Initial API and implementation
/*******************************************************************************
 *  Copyright (c) 2003, 2012 IBM Corporation and others.
 *
 *  This program and the accompanying materials
 *  are made available under the terms of the Eclipse Public License 2.0
 *  which accompanies this distribution, and is available at
 *  https://www.eclipse.org/legal/epl-2.0/
 *
 *  SPDX-License-Identifier: EPL-2.0
 *
 *  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.
/**
 * 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.
/**
	 * 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.
/**
	 * 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.
/**
	 * Create a new job queue.
	 */
	public JobQueue(boolean allowConflictOvertaking) {
		this(allowConflictOvertaking, true);
	}

	
Create a new job queue.
/**
	 * 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$
			@Override
			public IStatus run(IProgressMonitor m) {
				return Status.OK_STATUS;
			}
		};
		dummy.setNext(dummy);
		dummy.setPrevious(dummy);
		this.allowConflictOvertaking = allowConflictOvertaking;
	}

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

	
Return and remove the element with highest priority, or null if empty.
/**
	 * 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
/**
	 * 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.
Params:
newEntry – The entry to be added to the queue
queueEntry – The existing queue entry/**
	 * 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.
/**
	 * 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.
/**
	 * 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.
/**
	 * 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
/**
	 * 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;

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

			@Override
			public Object next() {
				return pointer;
			}

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

		};
	}
}