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