--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/dwtx/core/internal/jobs/JobQueue.d	Tue Aug 12 02:34:21 2008 +0200
@@ -0,0 +1,146 @@
+/*******************************************************************************
+ * Copyright (c) 2003, 2006 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
+ * Port to the D programming language:
+ *     Frank Benoit <benoit@tionex.de>
+ *******************************************************************************/
+module dwtx.core.internal.jobs.JobQueue;
+
+import dwt.dwthelper.utils;
+
+import dwtx.core.runtime.Assert;
+import dwtx.core.runtime.IProgressMonitor;
+import dwtx.core.runtime.IStatus;
+import dwtx.core.runtime.Status;
+
+import dwtx.core.internal.jobs.InternalJob;
+
+/**
+ * A linked list based priority queue. Either the elements in the queue must
+ * implement Comparable, or a Comparator must be provided.
+ */
+public 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.
+     */
+    private 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 bool allowConflictOvertaking;
+
+    /**
+     * Create a new job queue.
+     */
+    public this(bool allowConflictOvertaking) {
+        //compareTo on dummy is never called
+        dummy = new class("Queue-Head") InternalJob {//$NON-NLS-1$
+            this( String name ){
+                super(name);
+            }
+            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 is 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() is null);
+        Assert.isTrue(newEntry.previous() is 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 bool canOvertake(InternalJob newEntry, InternalJob queueEntry) {
+        //can never go past the end of the queue
+        if (queueEntry is 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 (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 bool isEmpty() {
+        return dummy.next() is dummy;
+    }
+
+    /**
+     * Return greatest element without removing it, or null if empty
+     */
+    public InternalJob peek() {
+        return dummy.previous() is dummy ? null : dummy.previous();
+    }
+}