1 | /* |
2 | * @(#) $Id: Queue.java 357871 2005-12-20 01:56:40Z trustin $ |
3 | * |
4 | * Copyright 2004 The Apache Software Foundation |
5 | * |
6 | * Licensed under the Apache License, Version 2.0 (the "License"); |
7 | * you may not use this file except in compliance with the License. |
8 | * You may obtain a copy of the License at |
9 | * |
10 | * http://www.apache.org/licenses/LICENSE-2.0 |
11 | * |
12 | * Unless required by applicable law or agreed to in writing, software |
13 | * distributed under the License is distributed on an "AS IS" BASIS, |
14 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
15 | * See the License for the specific language governing permissions and |
16 | * limitations under the License. |
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: 357871 $, $Date: 2005-12-20 10:56:40 +0900 (Tue, 20 Dec 2005) $ |
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 | // expand queue |
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 | // java.util.List compatibility methods // |
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 | // Make a room for a new element. |
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 | // Remove a room for the removed element. |
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 | // java.util.Queue compatibility methods // |
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 | } |