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 }