KickJava   Java API By Example, From Geeks To Geeks.

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


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 java.util.*;
14
15 /**
16  * A Queue of objects.
17  */

18 public class Queue {
19     protected Object JavaDoc[] elements;
20     protected int head;
21     protected boolean reuse;
22     protected int tail;
23
24     public Queue() {
25         this(20, false);
26     }
27
28     /**
29      * The parameter reuse indicates what do you want to happen with
30      * the object reference when you remove it from the queue. If
31      * reuse is false the queue no longer holds a reference to the
32      * object when it is removed. If reuse is true you can use the
33      * method getNextAvailableObject to get an used object, set its
34      * new values and add it again to the queue.
35      */

36     public Queue(int size, boolean reuse) {
37         elements = new Object JavaDoc[size];
38         head = tail = 0;
39         this.reuse = reuse;
40     }
41
42     /**
43      * Adds an object to the tail of the queue.
44      */

45     public void enqueue(Object JavaDoc element) {
46         int newTail = increment(tail);
47         if (newTail == head) {
48             grow();
49             newTail = tail + 1;
50         }
51         elements[tail] = element;
52         tail = newTail;
53     }
54
55     /**
56      * This method does not affect the queue itself. It is only a
57      * helper to decrement an index in the queue.
58      */

59     public int decrement(int index) {
60         return (index == 0) ? (elements.length - 1) : index - 1;
61     }
62
63     public Iterator elements() {
64         /**/
65         if (isEmpty())
66             return new ArrayList(0).iterator();
67
68         /* if head < tail we can use the same array */
69         if (head <= tail)
70             return Arrays.asList(elements).iterator();
71
72         /* otherwise we need to create a new array */
73         Object JavaDoc[] newElements = new Object JavaDoc[size()];
74         int end = (elements.length - head);
75         System.arraycopy(elements, head, newElements, 0, end);
76         System.arraycopy(elements, 0, newElements, end, tail);
77         return Arrays.asList(newElements).iterator();
78     }
79
80     public Object JavaDoc get(Object JavaDoc o) {
81         int index = head;
82         while (index != tail) {
83             if (elements[index].equals(o))
84                 return elements[index];
85             index = increment(index);
86         }
87         return null;
88     }
89
90     /**
91      * Removes the given object from the queue. Shifts the underlying array.
92      */

93     public boolean remove(Object JavaDoc o) {
94         int index = head;
95         //find the object to remove
96
while (index != tail) {
97             if (elements[index].equals(o))
98                 break;
99             index = increment(index);
100         }
101         //if element wasn't found, return
102
if (index == tail)
103             return false;
104         //store a reference to it (needed for reuse of objects)
105
Object JavaDoc toRemove = elements[index];
106         int nextIndex = -1;
107         while (index != tail) {
108             nextIndex = increment(index);
109             if (nextIndex != tail)
110                 elements[index] = elements[nextIndex];
111
112             index = nextIndex;
113         }
114         //decrement tail
115
tail = decrement(tail);
116
117         //if objects are reused, transfer the reference that is removed to the end of the queue
118
//otherwise set the element after the last one to null (to avoid duplicate references)
119
elements[tail] = reuse ? toRemove : null;
120         return true;
121     }
122
123     protected void grow() {
124         int newSize = (int) (elements.length * 1.5);
125         Object JavaDoc[] newElements = new Object JavaDoc[newSize];
126         if (tail >= head)
127             System.arraycopy(elements, head, newElements, head, size());
128         else {
129             int newHead = newSize - (elements.length - head);
130             System.arraycopy(elements, 0, newElements, 0, tail + 1);
131             System.arraycopy(elements, head, newElements, newHead, (newSize - newHead));
132             head = newHead;
133         }
134         elements = newElements;
135     }
136
137     /**
138      * This method does not affect the queue itself. It is only a
139      * helper to increment an index in the queue.
140      */

141     public int increment(int index) {
142         return (index == (elements.length - 1)) ? 0 : index + 1;
143     }
144
145     public boolean isEmpty() {
146         return tail == head;
147     }
148
149     public Object JavaDoc peek() {
150         return elements[head];
151     }
152
153     /**
154      * Removes an returns the item at the head of the queue.
155      */

156     public Object JavaDoc dequeue() {
157         if (isEmpty())
158             return null;
159         Object JavaDoc result = peek();
160         if (!reuse)
161             elements[head] = null;
162         head = increment(head);
163         return result;
164     }
165
166     public int size() {
167         return tail > head ? (tail - head) : ((elements.length - head) + tail);
168     }
169
170     public String JavaDoc toString() {
171         StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
172         sb.append("["); //$NON-NLS-1$
173
if (!isEmpty()) {
174             Iterator it = elements();
175             while (true) {
176                 sb.append(it.next());
177                 if (it.hasNext())
178                     sb.append(", "); //$NON-NLS-1$
179
else
180                     break;
181             }
182         }
183         sb.append("]"); //$NON-NLS-1$
184
return sb.toString();
185     }
186 }
187
Popular Tags