Mercurial > projects > dwt-addons

comparison dwtx/core/internal/jobs/JobQueue.d @ 122:9d0585bcb7aa

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Add core.jobs package
author Frank Benoit <benoit@tionex.de>
date Tue, 12 Aug 2008 02:34:21 +0200
parents
children
comparison
equal deleted inserted replaced
121:c0304616ea23 122:9d0585bcb7aa
1 /*******************************************************************************
2 * Copyright (c) 2003, 2006 IBM Corporation and others.
3 * All rights reserved. This program and the accompanying materials
4 * are made available under the terms of the Eclipse Public License v1.0
5 * which accompanies this distribution, and is available at
6 * http://www.eclipse.org/legal/epl-v10.html
7 *
8 * Contributors:
9 * IBM - Initial API and implementation
10 * Port to the D programming language:
11 * Frank Benoit <benoit@tionex.de>
12 *******************************************************************************/
13 module dwtx.core.internal.jobs.JobQueue;
14
15 import dwt.dwthelper.utils;
16
17 import dwtx.core.runtime.Assert;
18 import dwtx.core.runtime.IProgressMonitor;
19 import dwtx.core.runtime.IStatus;
20 import dwtx.core.runtime.Status;
21
22 import dwtx.core.internal.jobs.InternalJob;
23
24 /**
25 * A linked list based priority queue. Either the elements in the queue must
26 * implement Comparable, or a Comparator must be provided.
27 */
28 public class JobQueue {
29 /**
30 * The dummy entry sits between the head and the tail of the queue.
31 * dummy.previous() is the head, and dummy.next() is the tail.
32 */
33 private final InternalJob dummy;
34
35 /**
36 * If true, conflicting jobs will be allowed to overtake others in the
37 * queue that have lower priority. If false, higher priority jumps can only
38 * move up the queue by overtaking jobs that they don't conflict with.
39 */
40 private bool allowConflictOvertaking;
41
42 /**
43 * Create a new job queue.
44 */
45 public this(bool allowConflictOvertaking) {
46 //compareTo on dummy is never called
47 dummy = new class("Queue-Head") InternalJob {//$NON-NLS-1$
48 this( String name ){
49 super(name);
50 }
51 public IStatus run(IProgressMonitor m) {
52 return Status.OK_STATUS;
53 }
54 };
55 dummy.setNext(dummy);
56 dummy.setPrevious(dummy);
57 this.allowConflictOvertaking = allowConflictOvertaking;
58 }
59
60 /**
61 * remove all elements
62 */
63 public void clear() {
64 dummy.setNext(dummy);
65 dummy.setPrevious(dummy);
66 }
67
68 /**
69 * Return and remove the element with highest priority, or null if empty.
70 */
71 public InternalJob dequeue() {
72 InternalJob toRemove = dummy.previous();
73 if (toRemove is dummy)
74 return null;
75 return toRemove.remove();
76 }
77
78 /**
79 * Adds an item to the queue
80 */
81 public void enqueue(InternalJob newEntry) {
82 //assert new entry is does not already belong to some other data structure
83 Assert.isTrue(newEntry.next() is null);
84 Assert.isTrue(newEntry.previous() is null);
85 InternalJob tail = dummy.next();
86 //overtake lower priority jobs. Only overtake conflicting jobs if allowed to
87 while (canOvertake(newEntry, tail))
88 tail = tail.next();
89 //new entry is smaller than tail
90 final InternalJob tailPrevious = tail.previous();
91 newEntry.setNext(tail);
92 newEntry.setPrevious(tailPrevious);
93 tailPrevious.setNext(newEntry);
94 tail.setPrevious(newEntry);
95 }
96
97 /**
98 * Returns whether the new entry to overtake the existing queue entry.
99 * @param newEntry The entry to be added to the queue
100 * @param queueEntry The existing queue entry
101 */
102 private bool canOvertake(InternalJob newEntry, InternalJob queueEntry) {
103 //can never go past the end of the queue
104 if (queueEntry is dummy)
105 return false;
106 //if the new entry was already in the wait queue, ensure it is re-inserted in correct position (bug 211799)
107 if (newEntry.getWaitQueueStamp() > 0 && newEntry.getWaitQueueStamp() < queueEntry.getWaitQueueStamp())
108 return true;
109 //if the new entry has lower priority, there is no need to overtake the existing entry
110 if (queueEntry.compareTo(newEntry) >= 0)
111 return false;
112 //the new entry has higher priority, but only overtake the existing entry if the queue allows it
113 return allowConflictOvertaking || !newEntry.isConflicting(queueEntry);
114 }
115
116 /**
117 * Removes the given element from the queue.
118 */
119 public void remove(InternalJob toRemove) {
120 toRemove.remove();
121 //previous of toRemove might now bubble up
122 }
123
124 /**
125 * The given object has changed priority. Reshuffle the heap until it is
126 * valid.
127 */
128 public void resort(InternalJob entry) {
129 remove(entry);
130 enqueue(entry);
131 }
132
133 /**
134 * Returns true if the queue is empty, and false otherwise.
135 */
136 public bool isEmpty() {
137 return dummy.next() is dummy;
138 }
139
140 /**
141 * Return greatest element without removing it, or null if empty
142 */
143 public InternalJob peek() {
144 return dummy.previous() is dummy ? null : dummy.previous();
145 }
146 }