KickJava   Java API By Example, From Geeks To Geeks.

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


1 /*******************************************************************************
2  * Copyright (c) 2000, 2005 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 Corporation - initial API and implementation
10  *******************************************************************************/

11 package org.eclipse.core.internal.utils;
12
13 import java.util.Collections JavaDoc;
14 import java.util.Iterator JavaDoc;
15
16 /**
17  * A Queue of objects.
18  */

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

37     public Queue(int size, boolean reuse) {
38         elements = new Object JavaDoc[size];
39         head = tail = 0;
40         this.reuse = reuse;
41     }
42
43     public void add(Object JavaDoc element) {
44         int newTail = increment(tail);
45         if (newTail == head) {
46             grow();
47             newTail = tail + 1;
48         }
49         elements[tail] = element;
50         tail = newTail;
51     }
52
53     /**
54      * This method does not affect the queue itself. It is only a
55      * helper to decrement an index in the queue.
56      */

57     public int decrement(int index) {
58         return (index == 0) ? (elements.length - 1) : index - 1;
59     }
60
61     public Object JavaDoc elementAt(int index) {
62         return elements[index];
63     }
64
65     public Iterator JavaDoc iterator() {
66         /**/
67         if (isEmpty())
68             return Collections.EMPTY_LIST.iterator();
69
70         /* if head < tail we can use the same array */
71         if (head <= tail)
72             return new ArrayIterator(elements, head, tail - 1);
73
74         /* otherwise we need to create a new array */
75         Object JavaDoc[] newElements = new Object JavaDoc[size()];
76         int end = (elements.length - head);
77         System.arraycopy(elements, head, newElements, 0, end);
78         System.arraycopy(elements, 0, newElements, end, tail);
79         return new ArrayIterator(newElements);
80     }
81
82     /**
83      * Returns an object that has been removed from the queue, if any.
84      * The intention is to support reuse of objects that have already
85      * been processed and removed from the queue. Returns null if there
86      * are no available objects.
87      */

88     public Object JavaDoc getNextAvailableObject() {
89         int index = tail;
90         while (index != head) {
91             if (elements[index] != null) {
92                 Object JavaDoc result = elements[index];
93                 elements[index] = null;
94                 return result;
95             }
96             index = increment(index);
97         }
98         return null;
99     }
100
101     protected void grow() {
102         int newSize = (int) (elements.length * 1.5);
103         Object JavaDoc[] newElements = new Object JavaDoc[newSize];
104         if (tail >= head)
105             System.arraycopy(elements, head, newElements, head, size());
106         else {
107             int newHead = newSize - (elements.length - head);
108             System.arraycopy(elements, 0, newElements, 0, tail + 1);
109             System.arraycopy(elements, head, newElements, newHead, (newSize - newHead));
110             head = newHead;
111         }
112         elements = newElements;
113     }
114
115     /**
116      * This method does not affect the queue itself. It is only a
117      * helper to increment an index in the queue.
118      */

119     public int increment(int index) {
120         return (index == (elements.length - 1)) ? 0 : index + 1;
121     }
122
123     public int indexOf(Object JavaDoc target) {
124         if (tail >= head) {
125             for (int i = head; i < tail; i++)
126                 if (target.equals(elements[i]))
127                     return i;
128         } else {
129             for (int i = head; i < elements.length; i++)
130                 if (target.equals(elements[i]))
131                     return i;
132             for (int i = 0; i < tail; i++)
133                 if (target.equals(elements[i]))
134                     return i;
135         }
136         return -1;
137     }
138
139     public boolean isEmpty() {
140         return tail == head;
141     }
142
143     public Object JavaDoc peek() {
144         return elements[head];
145     }
146
147     public Object JavaDoc peekTail() {
148         return elements[decrement(tail)];
149     }
150
151     public Object JavaDoc remove() {
152         if (isEmpty())
153             return null;
154         Object JavaDoc result = peek();
155         if (!reuse)
156             elements[head] = null;
157         head = increment(head);
158         return result;
159     }
160
161     public Object JavaDoc removeTail() {
162         Object JavaDoc result = peekTail();
163         tail = decrement(tail);
164         if (!reuse)
165             elements[tail] = null;
166         return result;
167     }
168
169     public void reset() {
170         tail = head = 0;
171     }
172
173     public int size() {
174         return tail > head ? (tail - head) : ((elements.length - head) + tail);
175     }
176
177     public String JavaDoc toString() {
178         StringBuffer JavaDoc sb = new StringBuffer JavaDoc();
179         sb.append('[');
180         int count = 0;
181         if (!isEmpty()) {
182             Iterator JavaDoc it = iterator();
183             //only print a fixed number of elements to prevent debugger from choking
184
while (count < 100) {
185                 sb.append(it.next());
186                 if (it.hasNext())
187                     sb.append(',').append(' ');
188                 else
189                     break;
190             }
191         }
192         if (count < size())
193             sb.append('.').append('.').append('.');
194         sb.append(']');
195         return sb.toString();
196     }
197 }
198
Popular Tags