1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 package org.apache.mina.util;
20
21 import java.io.Serializable;
22 import java.util.AbstractList;
23 import java.util.Arrays;
24 import java.util.List;
25 import java.util.NoSuchElementException;
26
27 /***
28 * A unbounded circular queue.
29 *
30 * @author The Apache Directory Project (dev@directory.apache.org)
31 * @version $Rev: 327113 $, $Date: 2005-10-21 15:59:15 +0900 $
32 */
33 public class Queue extends AbstractList implements List, Serializable
34 {
35 private static final long serialVersionUID = 3835151744526464313L;
36
37 private static final int DEFAULT_CAPACITY = 4;
38
39 private static final int DEFAULT_MASK = DEFAULT_CAPACITY - 1;
40
41 private Object[] items;
42
43 private int mask;
44
45 private int first = 0;
46
47 private int last = 0;
48
49 private int size = 0;
50
51 /***
52 * Construct a new, empty queue.
53 */
54 public Queue()
55 {
56 items = new Object[ DEFAULT_CAPACITY ];
57 mask = DEFAULT_MASK;
58 }
59
60 /***
61 * Returns the capacity of this queue.
62 */
63 public int capacity()
64 {
65 return items.length;
66 }
67
68 /***
69 * Clears this queue.
70 */
71 public void clear()
72 {
73 Arrays.fill( items, null );
74 first = 0;
75 last = 0;
76 size = 0;
77 }
78
79 /***
80 * Dequeues from this queue.
81 *
82 * @return <code>null</code>, if this queue is empty or the element is
83 * really <code>null</code>.
84 */
85 public Object pop()
86 {
87 if( size == 0 )
88 {
89 return null;
90 }
91
92 Object ret = items[ first ];
93 items[ first ] = null;
94 decreaseSize();
95
96 return ret;
97 }
98
99 /***
100 * Enqueue into this queue.
101 */
102 public void push( Object obj )
103 {
104 ensureCapacity();
105 items[ last ] = obj;
106 increaseSize();
107 }
108
109 /***
110 * Returns the first element of the queue.
111 *
112 * @return <code>null</code>, if the queue is empty, or the element is
113 * really <code>null</code>.
114 */
115 public Object first()
116 {
117 if( size == 0 )
118 {
119 return null;
120 }
121
122 return items[ first ];
123 }
124
125 /***
126 * Returns the last element of the queue.
127 *
128 * @return <code>null</code>, if the queue is empty, or the element is
129 * really <code>null</code>.
130 */
131 public Object last()
132 {
133 if( size == 0 )
134 {
135 return null;
136 }
137
138 return items[ ( last + items.length - 1 ) & mask ];
139 }
140
141 public Object get( int idx )
142 {
143 checkIndex(idx);
144 return items[ getRealIndex(idx) ];
145 }
146
147 /***
148 * Returns <code>true</code> if the queue is empty.
149 */
150 public boolean isEmpty()
151 {
152 return ( size == 0 );
153 }
154
155 /***
156 * Returns the number of elements in the queue.
157 */
158 public int size()
159 {
160 return size;
161 }
162
163 public String toString()
164 {
165 return "first=" + first + ", last=" + last + ", size=" + size + ", mask = " + mask;
166 }
167
168 private void checkIndex( int idx )
169 {
170 if( idx < 0 || idx >= size )
171 {
172 throw new IndexOutOfBoundsException( String.valueOf( idx ) );
173 }
174 }
175
176 private int getRealIndex( int idx )
177 {
178 return ( first + idx ) & mask;
179 }
180
181 private void increaseSize()
182 {
183 last = ( last + 1 ) & mask;
184 size++;
185 }
186
187 private void decreaseSize() {
188 first = ( first + 1 ) & mask;
189 size--;
190 }
191
192 private void ensureCapacity()
193 {
194 if( size < items.length )
195 {
196 return;
197 }
198
199
200 final int oldLen = items.length;
201 Object[] tmp = new Object[ oldLen * 2 ];
202
203 if( first < last )
204 {
205 System.arraycopy( items, first, tmp, 0, last - first );
206 }
207 else
208 {
209 System.arraycopy( items, first, tmp, 0, oldLen - first );
210 System.arraycopy( items, 0, tmp, oldLen - first, last );
211 }
212
213 first = 0;
214 last = oldLen;
215 items = tmp;
216 mask = tmp.length - 1;
217 }
218
219
220
221
222
223 public boolean add( Object o )
224 {
225 push( o );
226 return true;
227 }
228
229 public Object set(int idx, Object o) {
230 checkIndex(idx);
231
232 int realIdx = getRealIndex(idx);
233 Object old = items[ realIdx ];
234 items[ realIdx ] = o;
235 return old;
236 }
237
238 public void add( int idx, Object o )
239 {
240 if( idx == size )
241 {
242 push( o );
243 return;
244 }
245
246 checkIndex( idx );
247 ensureCapacity();
248
249 int realIdx = getRealIndex( idx );
250
251
252 if( first < last )
253 {
254 System.arraycopy( items, realIdx, items, realIdx + 1, last - realIdx );
255 }
256 else
257 {
258 if( realIdx >= first )
259 {
260 System.arraycopy( items, 0, items, 1, last );
261 items[ 0 ] = items[ items.length - 1 ];
262 System.arraycopy( items, realIdx, items, realIdx + 1, items.length - realIdx - 1 );
263 }
264 else
265 {
266 System.arraycopy( items, realIdx, items, realIdx + 1, last - realIdx );
267 }
268 }
269
270 items[ realIdx ] = o;
271 increaseSize();
272 }
273
274 public Object remove( int idx )
275 {
276 if( idx == 0 )
277 {
278 return pop();
279 }
280
281 checkIndex( idx );
282
283 int realIdx = getRealIndex( idx );
284 Object removed = items[ realIdx ];
285
286
287 if( first < last )
288 {
289 System.arraycopy( items, first, items, first + 1, realIdx - first );
290 }
291 else
292 {
293 if( realIdx >= first )
294 {
295 System.arraycopy( items, first, items, first + 1, realIdx - first );
296 }
297 else
298 {
299 System.arraycopy( items, 0, items, 1, realIdx );
300 items[ 0 ] = items[ items.length - 1 ];
301 System.arraycopy( items, first, items, first + 1, items.length - first - 1 );
302 }
303 }
304
305 items[ first ] = null;
306 decreaseSize();
307
308 return removed;
309 }
310
311
312
313
314
315 public boolean offer( Object o )
316 {
317 push( o );
318 return true;
319 }
320
321 public Object poll()
322 {
323 return pop();
324 }
325
326 public Object remove()
327 {
328 if( size == 0 )
329 {
330 throw new NoSuchElementException();
331 }
332 return pop();
333 }
334
335 public Object peek()
336 {
337 return first();
338 }
339
340 public Object element()
341 {
342 if( size == 0 )
343 {
344 throw new NoSuchElementException();
345 }
346 return first();
347 }
348 }