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      protected Object _lock=this;
39      protected Object[] _elements;
40      protected int _nextE;
41      protected int _nextSlot;
42      protected int _size;
43      protected 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          if (!offer(e))
85              throw new IllegalStateException("Full");
86          return true;
87      }
88  
89      /* ------------------------------------------------------------ */
90      public boolean offer(E e)
91      {
92          synchronized(_lock)
93          {
94              if (_size==_elements.length && !grow())
95                  return false;
96                  
97              _size++;
98              _elements[_nextSlot++]=e;
99              if (_nextSlot==_elements.length)
100                 _nextSlot=0;
101         }
102         return true;
103     }
104 
105     /* ------------------------------------------------------------ */
106     /**
107     * Add without synchronization or bounds checking
108     * @see #add(Object)
109     */
110     public void addUnsafe(E e)
111     {
112         if (_size==_elements.length && !grow())
113             throw new IllegalStateException("Full");
114             
115         _size++;
116         _elements[_nextSlot++]=e;
117         if (_nextSlot==_elements.length)
118             _nextSlot=0;
119     }
120     
121     /* ------------------------------------------------------------ */
122     public E element()
123     {
124         synchronized(_lock)
125         {
126             if (_size==0)
127                 throw new NoSuchElementException();
128             return (E)_elements[_nextE];
129         }
130     }
131 
132     /* ------------------------------------------------------------ */
133     public E peek()
134     {
135         synchronized(_lock)
136         {
137             if (_size==0)
138                 return null;
139             return (E)_elements[_nextE];
140         }
141     }
142 
143     /* ------------------------------------------------------------ */
144     public E poll()
145     {
146         synchronized(_lock)
147         {
148             if (_size==0)
149                 return null;
150             E e = (E)_elements[_nextE];
151             _elements[_nextE]=null;
152             _size--;
153             if (++_nextE==_elements.length)
154                 _nextE=0;
155             return e;
156         }
157     }
158 
159     /* ------------------------------------------------------------ */
160     public E remove()
161     {
162         synchronized(_lock)
163         {
164             if (_size==0)
165                 throw new NoSuchElementException();
166             E e = (E)_elements[_nextE];
167             _elements[_nextE]=null;
168             _size--;
169             if (++_nextE==_elements.length)
170                 _nextE=0;
171             return e;
172         }
173     }
174 
175     /* ------------------------------------------------------------ */
176     @Override
177     public void clear()
178     {
179         synchronized(_lock)
180         {
181             _size=0;
182             _nextE=0;
183             _nextSlot=0;
184         }
185     }
186 
187     /* ------------------------------------------------------------ */
188     public boolean isEmpty()
189     {
190         synchronized(_lock)
191         {
192             return _size==0;
193         }
194     }
195 
196 
197     /* ------------------------------------------------------------ */
198     @Override
199     public int size()
200     {
201         return _size;
202     }
203 
204     /* ------------------------------------------------------------ */
205     @Override
206     public E get(int index)
207     {
208         synchronized(_lock)
209         {
210             if (index<0 || index>=_size)
211                 throw new IndexOutOfBoundsException("!("+0+"<"+index+"<="+_size+")");
212             int i = (_nextE+index)%_elements.length;
213             return (E)_elements[i];
214         }
215     }
216 
217     /* ------------------------------------------------------------ */
218     /**
219      * Get without synchronization or bounds checking.
220      * @see get(int)
221      */
222     public E getUnsafe(int index)
223     {
224         int i = (_nextE+index)%_elements.length;
225         return (E)_elements[i];
226     }
227     
228     /* ------------------------------------------------------------ */
229     public E remove(int index)
230     {
231         synchronized(_lock)
232         {
233             if (index<0 || index>=_size)
234                 throw new IndexOutOfBoundsException("!("+0+"<"+index+"<="+_size+")");
235 
236             int i = (_nextE+index)%_elements.length;
237             E old=(E)_elements[i];
238             
239             if (i<_nextSlot)
240             {
241                 // 0                         _elements.length
242                 //       _nextE........._nextSlot
243                 System.arraycopy(_elements,i+1,_elements,i,_nextSlot-i);
244                 _nextSlot--;
245                 _size--;
246             }
247             else
248             {
249                 // 0                         _elements.length
250                 // ......_nextSlot   _nextE..........
251                 System.arraycopy(_elements,i+1,_elements,i,_elements.length-i-1);
252                 if (_nextSlot>0)
253                 {
254                     _elements[_elements.length-1]=_elements[0];
255                     System.arraycopy(_elements,1,_elements,0,_nextSlot-1);
256                     _nextSlot--;
257                 }
258                 else
259                     _nextSlot=_elements.length-1;
260 
261                 _size--;
262             }
263             
264             return old;
265         }
266     }
267 
268     /* ------------------------------------------------------------ */
269     public E set(int index, E element)
270     {
271         synchronized(_lock)
272         {
273             if (index<0 || index>=_size)
274                 throw new IndexOutOfBoundsException("!("+0+"<"+index+"<="+_size+")");
275 
276             int i = _nextE+index;
277             if (i>=_elements.length)
278                 i-=_elements.length;
279             E old=(E)_elements[i];
280             _elements[i]=element;
281             return old;
282         }
283     }
284     
285     /* ------------------------------------------------------------ */
286     public void add(int index, E element)
287     {
288         synchronized(_lock)
289         {
290             if (index<0 || index>_size)
291                 throw new IndexOutOfBoundsException("!("+0+"<"+index+"<="+_size+")");
292 
293             if (_size==_elements.length && !grow())
294                     throw new IllegalStateException("Full");
295             
296             if (index==_size)
297             {
298                 add(element);
299             }
300             else
301             {
302                 int i = _nextE+index;
303                 if (i>=_elements.length)
304                     i-=_elements.length;
305                 
306                 _size++;
307                 _nextSlot++;
308                 if (_nextSlot==_elements.length)
309                     _nextSlot=0;
310                 
311                 if (i<_nextSlot)
312                 {
313                     // 0                         _elements.length
314                     //       _nextE.....i..._nextSlot
315                     // 0                         _elements.length
316                     // ..i..._nextSlot   _nextE..........
317                     System.arraycopy(_elements,i,_elements,i+1,_nextSlot-i);
318                     _elements[i]=element;
319                 }
320                 else
321                 {
322                     // 0                         _elements.length
323                     // ......_nextSlot   _nextE.....i....
324                     if (_nextSlot>0)
325                     {
326                         System.arraycopy(_elements,0,_elements,1,_nextSlot);
327                         _elements[0]=_elements[_elements.length-1];
328                     }
329 
330                     System.arraycopy(_elements,i,_elements,i+1,_elements.length-i-1);
331                     _elements[i]=element;
332                 }
333             }
334         }
335     }
336 
337     protected boolean grow()
338     {
339         if (_growCapacity<=0)
340             return false;
341 
342         Object[] elements=new Object[_elements.length+_growCapacity];
343 
344         int split=_elements.length-_nextE;
345         if (split>0)
346             System.arraycopy(_elements,_nextE,elements,0,split);
347         if (_nextE!=0)
348             System.arraycopy(_elements,0,elements,split,_nextSlot);
349 
350         _elements=elements;
351         _nextE=0;
352         _nextSlot=_size;
353         return true;
354     }
355 
356 }