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 }