1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 package org.mortbay.util;
16
17 import java.util.AbstractList;
18 import java.util.Collection;
19 import java.util.Iterator;
20 import java.util.List;
21 import java.util.NoSuchElementException;
22 import java.util.Queue;
23
24
25
26
27
28
29
30
31
32
33
34 public class ArrayQueue<E> extends AbstractList<E> implements Queue<E>
35 {
36 public final int DEFAULT_CAPACITY=64;
37 public final int DEFAULT_GROWTH=32;
38 protected Object _lock=this;
39 protected Object[] _elements;
40 protected int _nextE;
41 protected int _nextSlot;
42 protected int _size;
43 protected int _growCapacity;
44
45
46 public ArrayQueue()
47 {
48 _elements=new Object[64];
49 _growCapacity=32;
50 }
51
52
53 public ArrayQueue(int capacity)
54 {
55 _elements=new Object[capacity];
56 _growCapacity=-1;
57 }
58
59
60 public ArrayQueue(int initCapacity,int growBy)
61 {
62 _elements=new Object[initCapacity];
63 _growCapacity=growBy;
64 }
65
66
67 public ArrayQueue(int initCapacity,int growBy,Object lock)
68 {
69 _elements=new Object[initCapacity];
70 _growCapacity=growBy;
71 _lock=lock;
72 }
73
74
75 public int getCapacity()
76 {
77 return _elements.length;
78 }
79
80
81 @Override
82 public boolean add(E e)
83 {
84 if (!offer(e))
85 throw new IllegalStateException("Full");
86 return true;
87 }
88
89
90 public boolean offer(E e)
91 {
92 synchronized(_lock)
93 {
94 if (_size==_elements.length && !grow())
95 return false;
96
97 _size++;
98 _elements[_nextSlot++]=e;
99 if (_nextSlot==_elements.length)
100 _nextSlot=0;
101 }
102 return true;
103 }
104
105
106
107
108
109
110 public void addUnsafe(E e)
111 {
112 if (_size==_elements.length && !grow())
113 throw new IllegalStateException("Full");
114
115 _size++;
116 _elements[_nextSlot++]=e;
117 if (_nextSlot==_elements.length)
118 _nextSlot=0;
119 }
120
121
122 public E element()
123 {
124 synchronized(_lock)
125 {
126 if (_size==0)
127 throw new NoSuchElementException();
128 return (E)_elements[_nextE];
129 }
130 }
131
132
133 public E peek()
134 {
135 synchronized(_lock)
136 {
137 if (_size==0)
138 return null;
139 return (E)_elements[_nextE];
140 }
141 }
142
143
144 public E poll()
145 {
146 synchronized(_lock)
147 {
148 if (_size==0)
149 return null;
150 E e = (E)_elements[_nextE];
151 _elements[_nextE]=null;
152 _size--;
153 if (++_nextE==_elements.length)
154 _nextE=0;
155 return e;
156 }
157 }
158
159
160 public E remove()
161 {
162 synchronized(_lock)
163 {
164 if (_size==0)
165 throw new NoSuchElementException();
166 E e = (E)_elements[_nextE];
167 _elements[_nextE]=null;
168 _size--;
169 if (++_nextE==_elements.length)
170 _nextE=0;
171 return e;
172 }
173 }
174
175
176 @Override
177 public void clear()
178 {
179 synchronized(_lock)
180 {
181 _size=0;
182 _nextE=0;
183 _nextSlot=0;
184 }
185 }
186
187
188 public boolean isEmpty()
189 {
190 synchronized(_lock)
191 {
192 return _size==0;
193 }
194 }
195
196
197
198 @Override
199 public int size()
200 {
201 return _size;
202 }
203
204
205 @Override
206 public E get(int index)
207 {
208 synchronized(_lock)
209 {
210 if (index<0 || index>=_size)
211 throw new IndexOutOfBoundsException("!("+0+"<"+index+"<="+_size+")");
212 int i = (_nextE+index)%_elements.length;
213 return (E)_elements[i];
214 }
215 }
216
217
218
219
220
221
222 public E getUnsafe(int index)
223 {
224 int i = (_nextE+index)%_elements.length;
225 return (E)_elements[i];
226 }
227
228
229 public E remove(int index)
230 {
231 synchronized(_lock)
232 {
233 if (index<0 || index>=_size)
234 throw new IndexOutOfBoundsException("!("+0+"<"+index+"<="+_size+")");
235
236 int i = (_nextE+index)%_elements.length;
237 E old=(E)_elements[i];
238
239 if (i<_nextSlot)
240 {
241
242
243 System.arraycopy(_elements,i+1,_elements,i,_nextSlot-i);
244 _nextSlot--;
245 _size--;
246 }
247 else
248 {
249
250
251 System.arraycopy(_elements,i+1,_elements,i,_elements.length-i-1);
252 if (_nextSlot>0)
253 {
254 _elements[_elements.length-1]=_elements[0];
255 System.arraycopy(_elements,1,_elements,0,_nextSlot-1);
256 _nextSlot--;
257 }
258 else
259 _nextSlot=_elements.length-1;
260
261 _size--;
262 }
263
264 return old;
265 }
266 }
267
268
269 public E set(int index, E element)
270 {
271 synchronized(_lock)
272 {
273 if (index<0 || index>=_size)
274 throw new IndexOutOfBoundsException("!("+0+"<"+index+"<="+_size+")");
275
276 int i = _nextE+index;
277 if (i>=_elements.length)
278 i-=_elements.length;
279 E old=(E)_elements[i];
280 _elements[i]=element;
281 return old;
282 }
283 }
284
285
286 public void add(int index, E element)
287 {
288 synchronized(_lock)
289 {
290 if (index<0 || index>_size)
291 throw new IndexOutOfBoundsException("!("+0+"<"+index+"<="+_size+")");
292
293 if (_size==_elements.length && !grow())
294 throw new IllegalStateException("Full");
295
296 if (index==_size)
297 {
298 add(element);
299 }
300 else
301 {
302 int i = _nextE+index;
303 if (i>=_elements.length)
304 i-=_elements.length;
305
306 _size++;
307 _nextSlot++;
308 if (_nextSlot==_elements.length)
309 _nextSlot=0;
310
311 if (i<_nextSlot)
312 {
313
314
315
316
317 System.arraycopy(_elements,i,_elements,i+1,_nextSlot-i);
318 _elements[i]=element;
319 }
320 else
321 {
322
323
324 if (_nextSlot>0)
325 {
326 System.arraycopy(_elements,0,_elements,1,_nextSlot);
327 _elements[0]=_elements[_elements.length-1];
328 }
329
330 System.arraycopy(_elements,i,_elements,i+1,_elements.length-i-1);
331 _elements[i]=element;
332 }
333 }
334 }
335 }
336
337 protected boolean grow()
338 {
339 if (_growCapacity<=0)
340 return false;
341
342 Object[] elements=new Object[_elements.length+_growCapacity];
343
344 int split=_elements.length-_nextE;
345 if (split>0)
346 System.arraycopy(_elements,_nextE,elements,0,split);
347 if (_nextE!=0)
348 System.arraycopy(_elements,0,elements,split,_nextSlot);
349
350 _elements=elements;
351 _nextE=0;
352 _nextSlot=_size;
353 return true;
354 }
355
356 }