View Javadoc

1   //========================================================================
2   //Copyright 2004-2008 Mort Bay Consulting Pty. Ltd.
3   //------------------------------------------------------------------------
4   //Licensed under the Apache License, Version 2.0 (the "License");
5   //you may not use this file except in compliance with the License.
6   //You may obtain a copy of the License at 
7   //http://www.apache.org/licenses/LICENSE-2.0
8   //Unless required by applicable law or agreed to in writing, software
9   //distributed under the License is distributed on an "AS IS" BASIS,
10  //WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11  //See the License for the specific language governing permissions and
12  //limitations under the License.
13  //========================================================================
14  
15  package org.mortbay.util;
16  
17  import java.util.AbstractList;
18  import java.util.Collection;
19  import java.util.Iterator;
20  import java.util.List;
21  import java.util.NoSuchElementException;
22  import java.util.Queue;
23  
24  /* ------------------------------------------------------------ */
25  /** Queue backed by circular array.
26   * 
27   * This partial Queue implementation (also with {@link #pop()} for stack operation)
28   * is backed by a growable circular array.
29   * 
30   * @author gregw
31   *
32   * @param <E>
33   */
34  public class ArrayQueue<E> extends AbstractList<E> implements Queue<E>
35  {
36      public final int DEFAULT_CAPACITY=64;
37      public final int DEFAULT_GROWTH=32;
38      private Object _lock=this;
39      private Object[] _elements;
40      private int _nextE;
41      private int _nextSlot;
42      private int _size;
43      private int _growCapacity;
44    
45      /* ------------------------------------------------------------ */
46      public ArrayQueue()
47      {
48          _elements=new Object[64];
49          _growCapacity=32;
50      }
51    
52      /* ------------------------------------------------------------ */
53      public ArrayQueue(int capacity)
54      {
55          _elements=new Object[capacity];
56          _growCapacity=-1;
57      }
58      
59      /* ------------------------------------------------------------ */
60      public ArrayQueue(int initCapacity,int growBy)
61      {
62          _elements=new Object[initCapacity];
63          _growCapacity=growBy;
64      }
65     
66      /* ------------------------------------------------------------ */
67      public ArrayQueue(int initCapacity,int growBy,Object lock)
68      {
69          _elements=new Object[initCapacity];
70          _growCapacity=growBy;
71          _lock=lock;
72      }
73      
74      /* ------------------------------------------------------------ */
75      public int getCapacity()
76      {
77          return _elements.length;
78      }
79      
80      /* ------------------------------------------------------------ */
81      @Override
82      public boolean add(E e)
83      {
84          synchronized(_lock)
85          {
86              _size++;
87              _elements[_nextSlot++]=e;
88              if (_nextSlot==_elements.length)
89                  _nextSlot=0;
90              if (_nextSlot==_nextE)
91                  grow();
92          }
93          return true;
94      }
95  
96      /* ------------------------------------------------------------ */
97      /**
98      * Add without synchronization or bounds checking
99      * @see #add(Object)
100     */
101     public void addUnsafe(E e)
102     {
103         _size++;
104         _elements[_nextSlot++]=e;
105         if (_nextSlot==_elements.length)
106             _nextSlot=0;
107         if (_nextSlot==_nextE)
108             grow();
109     }
110     
111     /* ------------------------------------------------------------ */
112     public E element()
113     {
114         synchronized(_lock)
115         {
116             if (_nextSlot==_nextE)
117                 throw new NoSuchElementException();
118             return (E)_elements[_nextE];
119         }
120     }
121 
122     /* ------------------------------------------------------------ */
123     public boolean offer(E e)
124     {
125         synchronized(_lock)
126         {
127             _size++;
128             _elements[_nextSlot++]=e;
129             if (_nextSlot==_elements.length)
130                 _nextSlot=0;
131             if (_nextSlot==_nextE)
132             {
133                 if (_growCapacity<=0)
134                     return false;
135                 
136                 Object[] elements=new Object[_elements.length+_growCapacity];
137                     
138                 int split=_elements.length-_nextE;
139                 if (split>0)
140                     System.arraycopy(_elements,_nextE,elements,0,split);
141                 if (_nextE!=0)
142                     System.arraycopy(_elements,0,elements,split,_nextSlot);
143                 
144                 _elements=elements;
145                 _nextE=0;
146                 _nextSlot=_size;
147             }
148             
149             return true;
150         }
151     }
152 
153     /* ------------------------------------------------------------ */
154     public E peek()
155     {
156         synchronized(_lock)
157         {
158             if (_nextSlot==_nextE)
159                 return null;
160             return (E)_elements[_nextE];
161         }
162     }
163 
164     /* ------------------------------------------------------------ */
165     public E poll()
166     {
167         synchronized(_lock)
168         {
169             if (_size==0)
170                 return null;
171             E e = (E)_elements[_nextE];
172             _elements[_nextE]=null;
173             _size--;
174             if (++_nextE==_elements.length)
175                 _nextE=0;
176             return e;
177         }
178     }
179 
180     /* ------------------------------------------------------------ */
181     public E remove()
182     {
183         synchronized(_lock)
184         {
185             if (_nextSlot==_nextE)
186                 throw new NoSuchElementException();
187             E e = (E)_elements[_nextE++];
188             if (_nextE==_elements.length)
189                 _nextE=0;
190             return e;
191         }
192     }
193 
194     /* ------------------------------------------------------------ */
195     @Override
196     public void clear()
197     {
198         synchronized(_lock)
199         {
200             _size=0;
201             _nextE=0;
202             _nextSlot=0;
203         }
204     }
205 
206     /* ------------------------------------------------------------ */
207     public boolean isEmpty()
208     {
209         synchronized(_lock)
210         {
211             return _size==0;
212         }
213     }
214 
215 
216     /* ------------------------------------------------------------ */
217     @Override
218     public int size()
219     {
220         return _size;
221     }
222 
223     /* ------------------------------------------------------------ */
224     @Override
225     public E get(int index)
226     {
227         synchronized(_lock)
228         {
229             if (index<0 || index>=_size)
230                 throw new IndexOutOfBoundsException("!("+0+"<"+index+"<="+_size+")");
231             int i = _nextE+index;
232             if (i>=_elements.length)
233                 i-=_elements.length;
234             return (E)_elements[i];
235         }
236     }
237 
238     /* ------------------------------------------------------------ */
239     /**
240      * Get without synchronization or bounds checking.
241      * @see get(int)
242      */
243     public E getUnsafe(int index)
244     {
245         int i = _nextE+index;
246         if (i>=_elements.length)
247             i-=_elements.length;
248         return (E)_elements[i];
249     }
250     
251     /* ------------------------------------------------------------ */
252     public E remove(int index)
253     {
254         synchronized(_lock)
255         {
256             if (index<0 || index>=_size)
257                 throw new IndexOutOfBoundsException("!("+0+"<"+index+"<="+_size+")");
258 
259             int i = _nextE+index;
260             if (i>=_elements.length)
261                 i-=_elements.length;
262             E old=(E)_elements[i];
263             
264             if (i<_nextSlot)
265             {
266                 // 0                         _elements.length
267                 //       _nextE........._nextSlot
268                 System.arraycopy(_elements,i+1,_elements,i,_nextSlot-i);
269                 _nextSlot--;
270                 _size--;
271             }
272             else
273             {
274                 // 0                         _elements.length
275                 // ......_nextSlot   _nextE..........
276                 System.arraycopy(_elements,i+1,_elements,i,_elements.length-1);
277                 if (_nextSlot>0)
278                 {
279                     _elements[_elements.length]=_elements[0];
280                     System.arraycopy(_elements,1,_elements,0,_nextSlot-1);
281                     _nextSlot--;
282                 }
283                 else
284                     _nextSlot=_elements.length-1;
285 
286                 _size--;
287             }
288             
289             return old;
290         }
291     }
292 
293     /* ------------------------------------------------------------ */
294     public E set(int index, E element)
295     {
296         synchronized(_lock)
297         {
298             if (index<0 || index>=_size)
299                 throw new IndexOutOfBoundsException("!("+0+"<"+index+"<="+_size+")");
300 
301             int i = _nextE+index;
302             if (i>=_elements.length)
303                 i-=_elements.length;
304             E old=(E)_elements[i];
305             _elements[i]=element;
306             return old;
307         }
308     }
309     
310     /* ------------------------------------------------------------ */
311     public void add(int index, E element)
312     {
313         synchronized(_lock)
314         {
315             if (index<0 || index>_size)
316                 throw new IndexOutOfBoundsException("!("+0+"<"+index+"<="+_size+")");
317 
318             if (index==_size)
319             {
320                 add(element);
321             }
322             else
323             {
324                 int i = _nextE+index;
325                 if (i>=_elements.length)
326                     i-=_elements.length;
327                 
328                 _size++;
329                 _nextSlot++;
330                 if (_nextSlot==_elements.length)
331                     _nextSlot=0;
332                 
333                 if (_nextSlot==_nextE)
334                     grow();
335 
336                 if (i<_nextSlot)
337                 {
338                     // 0                         _elements.length
339                     //       _nextE.....i..._nextSlot
340                     // 0                         _elements.length
341                     // ..i..._nextSlot   _nextE..........
342                     System.arraycopy(_elements,i,_elements,i+1,_nextSlot-i);
343                     _elements[i]=element;
344                 }
345                 else
346                 {
347                     // 0                         _elements.length
348                     // ......_nextSlot   _nextE.....i....
349                     if (_nextSlot>0)
350                     {
351                         System.arraycopy(_elements,0,_elements,1,_nextSlot);
352                         _elements[0]=_elements[_elements.length-1];
353                     }
354 
355                     System.arraycopy(_elements,i,_elements,i+1,_elements.length-i-1);
356                     _elements[i]=element;
357                 }
358             }
359         }
360     }
361 
362     protected void grow()
363     {
364         if (_growCapacity<=0)
365             throw new IllegalStateException("Full");
366 
367         Object[] elements=new Object[_elements.length+_growCapacity];
368 
369         int split=_elements.length-_nextE;
370         if (split>0)
371             System.arraycopy(_elements,_nextE,elements,0,split);
372         if (_nextE!=0)
373             System.arraycopy(_elements,0,elements,split,_nextSlot);
374 
375         _elements=elements;
376         _nextE=0;
377         _nextSlot=_size;
378     }
379 
380 }