001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one
003: * or more contributor license agreements. See the NOTICE file
004: * distributed with this work for additional information
005: * regarding copyright ownership. The ASF licenses this file
006: * to you under the Apache License, Version 2.0 (the
007: * "License"); you may not use this file except in compliance
008: * with the License. You may obtain a copy of the License at
009: *
010: * http://www.apache.org/licenses/LICENSE-2.0
011: *
012: * Unless required by applicable law or agreed to in writing,
013: * software distributed under the License is distributed on an
014: * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
015: * KIND, either express or implied. See the License for the
016: * specific language governing permissions and limitations
017: * under the License.
018: *
019: */
020: package org.apache.mina.util;
021:
022: import java.io.Serializable;
023: import java.util.AbstractList;
024: import java.util.Arrays;
025: import java.util.List;
026: import java.util.NoSuchElementException;
027: import java.util.Queue;
028:
029: /**
030: * A unbounded circular queue based on array.
031: *
032: * @author The Apache Directory Project (mina-dev@directory.apache.org)
033: * @version $Rev: 593416 $, $Date: 2007-11-08 20:42:48 -0700 (Thu, 08 Nov 2007) $
034: */
035: public class CircularQueue<E> extends AbstractList<E> implements
036: List<E>, Queue<E>, Serializable {
037:
038: private static final long serialVersionUID = 3993421269224511264L;
039:
040: private static final int DEFAULT_CAPACITY = 4;
041:
042: private final int initialCapacity;
043: private Object[] items;
044: private int mask;
045: private int first = 0;
046: private int last = 0;
047: private boolean full;
048: private int shrinkThreshold;
049:
050: /**
051: * Construct a new, empty queue.
052: */
053: public CircularQueue() {
054: this (DEFAULT_CAPACITY);
055: }
056:
057: public CircularQueue(int initialCapacity) {
058: int actualCapacity = normalizeCapacity(initialCapacity);
059: items = new Object[actualCapacity];
060: mask = actualCapacity - 1;
061: this .initialCapacity = actualCapacity;
062: this .shrinkThreshold = 0;
063: }
064:
065: private static int normalizeCapacity(int initialCapacity) {
066: int actualCapacity = 1;
067: while (actualCapacity < initialCapacity) {
068: actualCapacity <<= 1;
069: if (actualCapacity < 0) {
070: actualCapacity = 1 << 30;
071: break;
072: }
073: }
074: return actualCapacity;
075: }
076:
077: /**
078: * Returns the capacity of this queue.
079: */
080: public int capacity() {
081: return items.length;
082: }
083:
084: @Override
085: public void clear() {
086: if (!isEmpty()) {
087: Arrays.fill(items, null);
088: first = 0;
089: last = 0;
090: full = false;
091: shrinkIfNeeded();
092: }
093: }
094:
095: @SuppressWarnings("unchecked")
096: public E poll() {
097: if (isEmpty()) {
098: return null;
099: }
100:
101: Object ret = items[first];
102: items[first] = null;
103: decreaseSize();
104:
105: if (first == last) {
106: first = last = 0;
107: }
108:
109: shrinkIfNeeded();
110: return (E) ret;
111: }
112:
113: public boolean offer(E item) {
114: if (item == null) {
115: throw new NullPointerException("item");
116: }
117: expandIfNeeded();
118: items[last] = item;
119: increaseSize();
120: return true;
121: }
122:
123: @SuppressWarnings("unchecked")
124: public E peek() {
125: if (isEmpty()) {
126: return null;
127: }
128:
129: return (E) items[first];
130: }
131:
132: @SuppressWarnings("unchecked")
133: @Override
134: public E get(int idx) {
135: checkIndex(idx);
136: return (E) items[getRealIndex(idx)];
137: }
138:
139: @Override
140: public boolean isEmpty() {
141: return (first == last) && !full;
142: }
143:
144: @Override
145: public int size() {
146: if (full) {
147: return capacity();
148: }
149:
150: if (last >= first) {
151: return last - first;
152: } else {
153: return last - first + capacity();
154: }
155: }
156:
157: @Override
158: public String toString() {
159: return "first=" + first + ", last=" + last + ", size=" + size()
160: + ", mask = " + mask;
161: }
162:
163: private void checkIndex(int idx) {
164: if (idx < 0 || idx >= size()) {
165: throw new IndexOutOfBoundsException(String.valueOf(idx));
166: }
167: }
168:
169: private int getRealIndex(int idx) {
170: return (first + idx) & mask;
171: }
172:
173: private void increaseSize() {
174: last = (last + 1) & mask;
175: full = first == last;
176: }
177:
178: private void decreaseSize() {
179: first = (first + 1) & mask;
180: full = false;
181: }
182:
183: private void expandIfNeeded() {
184: if (full) {
185: // expand queue
186: final int oldLen = items.length;
187: final int newLen = oldLen << 1;
188: Object[] tmp = new Object[newLen];
189:
190: if (first < last) {
191: System.arraycopy(items, first, tmp, 0, last - first);
192: } else {
193: System.arraycopy(items, first, tmp, 0, oldLen - first);
194: System.arraycopy(items, 0, tmp, oldLen - first, last);
195: }
196:
197: first = 0;
198: last = oldLen;
199: items = tmp;
200: mask = tmp.length - 1;
201: if (newLen >>> 3 > initialCapacity) {
202: shrinkThreshold = newLen >>> 3;
203: }
204: }
205: }
206:
207: private void shrinkIfNeeded() {
208: int size = size();
209: if (size < shrinkThreshold) {
210: // shrink queue
211: final int oldLen = items.length;
212: int newLen = normalizeCapacity(size);
213: if (size == newLen) {
214: newLen <<= 1;
215: }
216:
217: if (newLen >= oldLen) {
218: return;
219: }
220:
221: if (newLen < initialCapacity) {
222: if (oldLen == initialCapacity) {
223: return;
224: } else {
225: newLen = initialCapacity;
226: }
227: }
228:
229: Object[] tmp = new Object[newLen];
230:
231: if (first < last) {
232: System.arraycopy(items, first, tmp, 0, last - first);
233: } else {
234: System.arraycopy(items, first, tmp, 0, oldLen - first);
235: System.arraycopy(items, 0, tmp, oldLen - first, last);
236: }
237:
238: first = 0;
239: last = size;
240: items = tmp;
241: mask = tmp.length - 1;
242: shrinkThreshold = 0;
243: }
244: }
245:
246: @Override
247: public boolean add(E o) {
248: return offer(o);
249: }
250:
251: @SuppressWarnings("unchecked")
252: @Override
253: public E set(int idx, E o) {
254: checkIndex(idx);
255:
256: int realIdx = getRealIndex(idx);
257: Object old = items[realIdx];
258: items[realIdx] = o;
259: return (E) old;
260: }
261:
262: @Override
263: public void add(int idx, E o) {
264: if (idx == size()) {
265: offer(o);
266: return;
267: }
268:
269: checkIndex(idx);
270: expandIfNeeded();
271:
272: int realIdx = getRealIndex(idx);
273:
274: // Make a room for a new element.
275: if (first < last) {
276: System.arraycopy(items, realIdx, items, realIdx + 1, last
277: - realIdx);
278: } else {
279: if (realIdx >= first) {
280: System.arraycopy(items, 0, items, 1, last);
281: items[0] = items[items.length - 1];
282: System.arraycopy(items, realIdx, items, realIdx + 1,
283: items.length - realIdx - 1);
284: } else {
285: System.arraycopy(items, realIdx, items, realIdx + 1,
286: last - realIdx);
287: }
288: }
289:
290: items[realIdx] = o;
291: increaseSize();
292: }
293:
294: @SuppressWarnings("unchecked")
295: @Override
296: public E remove(int idx) {
297: if (idx == 0) {
298: return poll();
299: }
300:
301: checkIndex(idx);
302:
303: int realIdx = getRealIndex(idx);
304: Object removed = items[realIdx];
305:
306: // Remove a room for the removed element.
307: if (first < last) {
308: System.arraycopy(items, first, items, first + 1, realIdx
309: - first);
310: } else {
311: if (realIdx >= first) {
312: System.arraycopy(items, first, items, first + 1,
313: realIdx - first);
314: } else {
315: System.arraycopy(items, 0, items, 1, realIdx);
316: items[0] = items[items.length - 1];
317: System.arraycopy(items, first, items, first + 1,
318: items.length - first - 1);
319: }
320: }
321:
322: items[first] = null;
323: decreaseSize();
324:
325: shrinkIfNeeded();
326: return (E) removed;
327: }
328:
329: public E remove() {
330: if (isEmpty()) {
331: throw new NoSuchElementException();
332: }
333: return poll();
334: }
335:
336: public E element() {
337: if (isEmpty()) {
338: throw new NoSuchElementException();
339: }
340: return peek();
341: }
342: }
|