View Javadoc

1   /*
2    *  Licensed to the Apache Software Foundation (ASF) under one
3    *  or more contributor license agreements.  See the NOTICE file
4    *  distributed with this work for additional information
5    *  regarding copyright ownership.  The ASF licenses this file
6    *  to you under the Apache License, Version 2.0 (the
7    *  "License"); you may not use this file except in compliance
8    *  with the License.  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,
13   *  software distributed under the License is distributed on an
14   *  "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   *  KIND, either express or implied.  See the License for the
16   *  specific language governing permissions and limitations
17   *  under the License. 
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  /**
29   * A unbounded circular queue.
30   * 
31   * @author The Apache Directory Project (mina-dev@directory.apache.org)
32   * @version $Rev: 575603 $, $Date: 2007-09-14 12:04:45 +0200 (Fri, 14 Sep 2007) $
33   */
34  public class Queue extends AbstractList implements List, Serializable {
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          items = new Object[DEFAULT_CAPACITY];
56          mask = DEFAULT_MASK;
57      }
58  
59      /**
60       * Returns the capacity of this queue.
61       */
62      public int capacity() {
63          return items.length;
64      }
65  
66      /**
67       * Clears this queue.
68       */
69      public void clear() {
70          Arrays.fill(items, null);
71          first = 0;
72          last = 0;
73          size = 0;
74      }
75  
76      /**
77       * Dequeues from this queue.
78       * 
79       * @return <code>null</code>, if this queue is empty or the element is
80       *         really <code>null</code>.
81       */
82      public Object pop() {
83          if (size == 0) {
84              return null;
85          }
86  
87          Object ret = items[first];
88          items[first] = null;
89          decreaseSize();
90  
91          return ret;
92      }
93  
94      /**
95       * Enqueue into this queue.
96       */
97      public void push(Object item) {
98          if (item == null) {
99              throw new NullPointerException("item");
100         }
101         ensureCapacity();
102         items[last] = item;
103         increaseSize();
104     }
105 
106     /**
107      * Returns the first element of the queue.
108      * 
109      * @return <code>null</code>, if the queue is empty, or the element is
110      *         really <code>null</code>.
111      */
112     public Object first() {
113         if (size == 0) {
114             return null;
115         }
116 
117         return items[first];
118     }
119 
120     /**
121      * Returns the last element of the queue.
122      * 
123      * @return <code>null</code>, if the queue is empty, or the element is
124      *         really <code>null</code>.
125      */
126     public Object last() {
127         if (size == 0) {
128             return null;
129         }
130 
131         return items[(last + items.length - 1) & mask];
132     }
133 
134     public Object get(int idx) {
135         checkIndex(idx);
136         return items[getRealIndex(idx)];
137     }
138 
139     /**
140      * Returns <code>true</code> if the queue is empty.
141      */
142     public boolean isEmpty() {
143         return (size == 0);
144     }
145 
146     /**
147      * Returns the number of elements in the queue.
148      */
149     public int size() {
150         return size;
151     }
152     
153     public String toString() {
154         return "first=" + first + ", last=" + last + ", size=" + size
155                 + ", mask = " + mask;
156     }
157 
158     private void checkIndex(int idx) {
159         if (idx < 0 || idx >= size) {
160             throw new IndexOutOfBoundsException(String.valueOf(idx));
161         }
162     }
163 
164     private int getRealIndex(int idx) {
165         return (first + idx) & mask;
166     }
167 
168     private void increaseSize() {
169         last = (last + 1) & mask;
170         size++;
171     }
172 
173     private void decreaseSize() {
174         first = (first + 1) & mask;
175         size--;
176     }
177 
178     private void ensureCapacity() {
179         if (size < items.length) {
180             return;
181         }
182 
183         // expand queue
184         final int oldLen = items.length;
185         Object[] tmp = new Object[oldLen * 2];
186 
187         if (first < last) {
188             System.arraycopy(items, first, tmp, 0, last - first);
189         } else {
190             System.arraycopy(items, first, tmp, 0, oldLen - first);
191             System.arraycopy(items, 0, tmp, oldLen - first, last);
192         }
193 
194         first = 0;
195         last = oldLen;
196         items = tmp;
197         mask = tmp.length - 1;
198     }
199 
200     //////////////////////////////////////////
201     // java.util.List compatibility methods //
202     //////////////////////////////////////////
203 
204     public boolean add(Object o) {
205         push(o);
206         return true;
207     }
208 
209     public Object set(int idx, Object o) {
210         checkIndex(idx);
211 
212         int realIdx = getRealIndex(idx);
213         Object old = items[realIdx];
214         items[realIdx] = o;
215         return old;
216     }
217 
218     public void add(int idx, Object o) {
219         if (idx == size) {
220             push(o);
221             return;
222         }
223 
224         checkIndex(idx);
225         ensureCapacity();
226 
227         int realIdx = getRealIndex(idx);
228 
229         // Make a room for a new element.
230         if (first < last) {
231             System
232                     .arraycopy(items, realIdx, items, realIdx + 1, last
233                             - realIdx);
234         } else {
235             if (realIdx >= first) {
236                 System.arraycopy(items, 0, items, 1, last);
237                 items[0] = items[items.length - 1];
238                 System.arraycopy(items, realIdx, items, realIdx + 1,
239                         items.length - realIdx - 1);
240             } else {
241                 System.arraycopy(items, realIdx, items, realIdx + 1, last
242                         - realIdx);
243             }
244         }
245 
246         items[realIdx] = o;
247         increaseSize();
248     }
249 
250     public Object remove(int idx) {
251         if (idx == 0) {
252             return pop();
253         }
254 
255         checkIndex(idx);
256 
257         int realIdx = getRealIndex(idx);
258         Object removed = items[realIdx];
259 
260         // Remove a room for the removed element.
261         if (first < last) {
262             System.arraycopy(items, first, items, first + 1, realIdx - first);
263         } else {
264             if (realIdx >= first) {
265                 System.arraycopy(items, first, items, first + 1, realIdx
266                         - first);
267             } else {
268                 System.arraycopy(items, 0, items, 1, realIdx);
269                 items[0] = items[items.length - 1];
270                 System.arraycopy(items, first, items, first + 1, items.length
271                         - first - 1);
272             }
273         }
274 
275         items[first] = null;
276         decreaseSize();
277 
278         return removed;
279     }
280 
281     ///////////////////////////////////////////
282     // java.util.Queue compatibility methods //
283     ///////////////////////////////////////////
284 
285     public boolean offer(Object o) {
286         push(o);
287         return true;
288     }
289 
290     public Object poll() {
291         return pop();
292     }
293 
294     public Object remove() {
295         if (size == 0) {
296             throw new NoSuchElementException();
297         }
298         return pop();
299     }
300 
301     public Object peek() {
302         return first();
303     }
304 
305     public Object element() {
306         if (size == 0) {
307             throw new NoSuchElementException();
308         }
309         return first();
310     }
311 }