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 private Object _lock=this;
39 private Object[] _elements;
40 private int _nextE;
41 private int _nextSlot;
42 private int _size;
43 private 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 synchronized(_lock)
85 {
86 _size++;
87 _elements[_nextSlot++]=e;
88 if (_nextSlot==_elements.length)
89 _nextSlot=0;
90 if (_nextSlot==_nextE)
91 grow();
92 }
93 return true;
94 }
95
96
97
98
99
100
101 public void addUnsafe(E e)
102 {
103 _size++;
104 _elements[_nextSlot++]=e;
105 if (_nextSlot==_elements.length)
106 _nextSlot=0;
107 if (_nextSlot==_nextE)
108 grow();
109 }
110
111
112 public E element()
113 {
114 synchronized(_lock)
115 {
116 if (_nextSlot==_nextE)
117 throw new NoSuchElementException();
118 return (E)_elements[_nextE];
119 }
120 }
121
122
123 public boolean offer(E e)
124 {
125 synchronized(_lock)
126 {
127 _size++;
128 _elements[_nextSlot++]=e;
129 if (_nextSlot==_elements.length)
130 _nextSlot=0;
131 if (_nextSlot==_nextE)
132 {
133 if (_growCapacity<=0)
134 return false;
135
136 Object[] elements=new Object[_elements.length+_growCapacity];
137
138 int split=_elements.length-_nextE;
139 if (split>0)
140 System.arraycopy(_elements,_nextE,elements,0,split);
141 if (_nextE!=0)
142 System.arraycopy(_elements,0,elements,split,_nextSlot);
143
144 _elements=elements;
145 _nextE=0;
146 _nextSlot=_size;
147 }
148
149 return true;
150 }
151 }
152
153
154 public E peek()
155 {
156 synchronized(_lock)
157 {
158 if (_nextSlot==_nextE)
159 return null;
160 return (E)_elements[_nextE];
161 }
162 }
163
164
165 public E poll()
166 {
167 synchronized(_lock)
168 {
169 if (_size==0)
170 return null;
171 E e = (E)_elements[_nextE];
172 _elements[_nextE]=null;
173 _size--;
174 if (++_nextE==_elements.length)
175 _nextE=0;
176 return e;
177 }
178 }
179
180
181 public E remove()
182 {
183 synchronized(_lock)
184 {
185 if (_nextSlot==_nextE)
186 throw new NoSuchElementException();
187 E e = (E)_elements[_nextE++];
188 if (_nextE==_elements.length)
189 _nextE=0;
190 return e;
191 }
192 }
193
194
195 @Override
196 public void clear()
197 {
198 synchronized(_lock)
199 {
200 _size=0;
201 _nextE=0;
202 _nextSlot=0;
203 }
204 }
205
206
207 public boolean isEmpty()
208 {
209 synchronized(_lock)
210 {
211 return _size==0;
212 }
213 }
214
215
216
217 @Override
218 public int size()
219 {
220 return _size;
221 }
222
223
224 @Override
225 public E get(int index)
226 {
227 synchronized(_lock)
228 {
229 if (index<0 || index>=_size)
230 throw new IndexOutOfBoundsException("!("+0+"<"+index+"<="+_size+")");
231 int i = _nextE+index;
232 if (i>=_elements.length)
233 i-=_elements.length;
234 return (E)_elements[i];
235 }
236 }
237
238
239
240
241
242
243 public E getUnsafe(int index)
244 {
245 int i = _nextE+index;
246 if (i>=_elements.length)
247 i-=_elements.length;
248 return (E)_elements[i];
249 }
250
251
252 public E remove(int index)
253 {
254 synchronized(_lock)
255 {
256 if (index<0 || index>=_size)
257 throw new IndexOutOfBoundsException("!("+0+"<"+index+"<="+_size+")");
258
259 int i = _nextE+index;
260 if (i>=_elements.length)
261 i-=_elements.length;
262 E old=(E)_elements[i];
263
264 if (i<_nextSlot)
265 {
266
267
268 System.arraycopy(_elements,i+1,_elements,i,_nextSlot-i);
269 _nextSlot--;
270 _size--;
271 }
272 else
273 {
274
275
276 System.arraycopy(_elements,i+1,_elements,i,_elements.length-1);
277 if (_nextSlot>0)
278 {
279 _elements[_elements.length]=_elements[0];
280 System.arraycopy(_elements,1,_elements,0,_nextSlot-1);
281 _nextSlot--;
282 }
283 else
284 _nextSlot=_elements.length-1;
285
286 _size--;
287 }
288
289 return old;
290 }
291 }
292
293
294 public E set(int index, E element)
295 {
296 synchronized(_lock)
297 {
298 if (index<0 || index>=_size)
299 throw new IndexOutOfBoundsException("!("+0+"<"+index+"<="+_size+")");
300
301 int i = _nextE+index;
302 if (i>=_elements.length)
303 i-=_elements.length;
304 E old=(E)_elements[i];
305 _elements[i]=element;
306 return old;
307 }
308 }
309
310
311 public void add(int index, E element)
312 {
313 synchronized(_lock)
314 {
315 if (index<0 || index>_size)
316 throw new IndexOutOfBoundsException("!("+0+"<"+index+"<="+_size+")");
317
318 if (index==_size)
319 {
320 add(element);
321 }
322 else
323 {
324 int i = _nextE+index;
325 if (i>=_elements.length)
326 i-=_elements.length;
327
328 _size++;
329 _nextSlot++;
330 if (_nextSlot==_elements.length)
331 _nextSlot=0;
332
333 if (_nextSlot==_nextE)
334 grow();
335
336 if (i<_nextSlot)
337 {
338
339
340
341
342 System.arraycopy(_elements,i,_elements,i+1,_nextSlot-i);
343 _elements[i]=element;
344 }
345 else
346 {
347
348
349 if (_nextSlot>0)
350 {
351 System.arraycopy(_elements,0,_elements,1,_nextSlot);
352 _elements[0]=_elements[_elements.length-1];
353 }
354
355 System.arraycopy(_elements,i,_elements,i+1,_elements.length-i-1);
356 _elements[i]=element;
357 }
358 }
359 }
360 }
361
362 protected void grow()
363 {
364 if (_growCapacity<=0)
365 throw new IllegalStateException("Full");
366
367 Object[] elements=new Object[_elements.length+_growCapacity];
368
369 int split=_elements.length-_nextE;
370 if (split>0)
371 System.arraycopy(_elements,_nextE,elements,0,split);
372 if (_nextE!=0)
373 System.arraycopy(_elements,0,elements,split,_nextSlot);
374
375 _elements=elements;
376 _nextE=0;
377 _nextSlot=_size;
378 }
379
380 }