KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > org > eclipse > core > internal > jobs > JobQueue


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  *******************************************************************************/
11 package org.eclipse.core.internal.jobs;
12
13 import org.eclipse.core.runtime.*;
14
15 /**
16  * A linked list based priority queue. Either the elements in the queue must
17  * implement Comparable, or a Comparator must be provided.
18  */
19 public class JobQueue {
20     /**
21      * The dummy entry sits between the head and the tail of the queue.
22      * dummy.previous() is the head, and dummy.next() is the tail.
23      */
24     private final InternalJob dummy;
25
26     /**
27      * If true, conflicting jobs will be allowed to overtake others in the
28      * queue that have lower priority. If false, higher priority jumps can only
29      * move up the queue by overtaking jobs that they don't conflict with.
30      */
31     private boolean allowConflictOvertaking;
32
33     /**
34      * Create a new job queue.
35      */
36     public JobQueue(boolean allowConflictOvertaking) {
37         //compareTo on dummy is never called
38 dummy = new InternalJob("Queue-Head") {//$NON-NLS-1$
39 public IStatus run(IProgressMonitor m) {
40                 return Status.OK_STATUS;
41             }
42         };
43         dummy.setNext(dummy);
44         dummy.setPrevious(dummy);
45         this.allowConflictOvertaking = allowConflictOvertaking;
46     }
47
48     /**
49      * remove all elements
50      */
51     public void clear() {
52         dummy.setNext(dummy);
53         dummy.setPrevious(dummy);
54     }
55
56     /**
57      * Return and remove the element with highest priority, or null if empty.
58      */
59     public InternalJob dequeue() {
60         InternalJob toRemove = dummy.previous();
61         if (toRemove == dummy)
62             return null;
63         return toRemove.remove();
64     }
65
66     /**
67      * Adds an item to the queue
68      */
69     public void enqueue(InternalJob newEntry) {
70         //assert new entry is does not already belong to some other data structure
71 Assert.isTrue(newEntry.next() == null);
72         Assert.isTrue(newEntry.previous() == null);
73         InternalJob tail = dummy.next();
74         //overtake lower priority jobs. Only overtake conflicting jobs if allowed to
75 while (tail != dummy && tail.compareTo(newEntry) < 0 && (allowConflictOvertaking || !newEntry.isConflicting(tail)))
76             tail = tail.next();
77         //new entry is smaller than tail
78 final InternalJob tailPrevious = tail.previous();
79         newEntry.setNext(tail);
80         newEntry.setPrevious(tailPrevious);
81         tailPrevious.setNext(newEntry);
82         tail.setPrevious(newEntry);
83     }
84
85     /**
86      * Removes the given element from the queue.
87      */
88     public void remove(InternalJob toRemove) {
89         toRemove.remove();
90         //previous of toRemove might now bubble up
91 }
92
93     /**
94      * The given object has changed priority. Reshuffle the heap until it is
95      * valid.
96      */
97     public void resort(InternalJob entry) {
98         remove(entry);
99         enqueue(entry);
100     }
101
102     /**
103      * Returns true if the queue is empty, and false otherwise.
104      */
105     public boolean isEmpty() {
106         return dummy.next() == dummy;
107     }
108
109     /**
110      * Return greatest element without removing it, or null if empty
111      */
112     public InternalJob peek() {
113         return dummy.previous() == dummy ? null : dummy.previous();
114     }
115 }
116
Popular Tags