001    /* CopyOnWriteArrayList.java
002       Copyright (C) 2006 Free Software Foundation
003    
004    This file is part of GNU Classpath.
005    
006    GNU Classpath is free software; you can redistribute it and/or modify
007    it under the terms of the GNU General Public License as published by
008    the Free Software Foundation; either version 2, or (at your option)
009    any later version.
010    
011    GNU Classpath is distributed in the hope that it will be useful, but
012    WITHOUT ANY WARRANTY; without even the implied warranty of
013    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
014    General Public License for more details.
015    
016    You should have received a copy of the GNU General Public License
017    along with GNU Classpath; see the file COPYING.  If not, write to the
018    Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
019    02110-1301 USA.
020    
021    Linking this library statically or dynamically with other modules is
022    making a combined work based on this library.  Thus, the terms and
023    conditions of the GNU General Public License cover the whole
024    combination.
025    
026    As a special exception, the copyright holders of this library give you
027    permission to link this library with independent modules to produce an
028    executable, regardless of the license terms of these independent
029    modules, and to copy and distribute the resulting executable under
030    terms of your choice, provided that you also meet, for each linked
031    independent module, the terms and conditions of the license of that
032    module.  An independent module is a module which is not derived from
033    or based on this library.  If you modify this library, you may extend
034    this exception to your version of the library, but you are not
035    obligated to do so.  If you do not wish to do so, delete this
036    exception statement from your version. */
037    
038    package java.util.concurrent;
039    
040    import java.io.IOException;
041    import java.io.ObjectInputStream;
042    import java.io.ObjectOutputStream;
043    import java.io.Serializable;
044    
045    import java.lang.reflect.Array;
046    
047    import java.util.AbstractList;
048    import java.util.Arrays;
049    import java.util.Collection;
050    import java.util.ConcurrentModificationException;
051    import java.util.Iterator;
052    import java.util.List;
053    import java.util.ListIterator;
054    import java.util.NoSuchElementException;
055    import java.util.RandomAccess;
056    
057    /**
058     * A thread-safe implementation of an ArrayList. A CopyOnWriteArrayList is
059     * as special ArrayList which performs copies of the underlying storage
060     * each time a write (<code>remove</code>, <code>add</code> etc..) operation
061     * is performed.<br />
062     * <br />
063     * The update operation in this class run usually in <code>O(n)</code> or worse,
064     * but traversal operations are fast and efficient, especially when running in
065     * a multi-thread environment without the need to design complex synchronize
066     * mechanisms.<br />
067     * <br />
068     * <code>Iterator</code>s in this class work on a snapshot of the backing store
069     * at the moment the iterator itself was created, hence the iterator will not
070     * reflect changes in the underlying storage. Thus, update operation on the
071     * <code>Iterator</code>s are not supported, but as interferences from other
072     * threads are impossible, no <code>ConcurrentModificationException</code>
073     * will be ever thrown from within the <code>Iterator</code>.
074     * <br /><br />
075     * This class is especially useful when used with event handling, like the
076     * following code demonstrates:<br />
077     * <code><pre>
078     * 
079     * CopyOnWriteArrayList<EventListener> listeners =
080     *   new CopyOnWriteArrayList<EventListener>();
081     * 
082     * [...]
083     * 
084     * for (final EventListener listener : listeners)
085     *   {
086     *     Runnable dispatcher = new Runnable() {
087     *       public void run()
088     *       {
089     *         listener.preferenceChange(event);
090     *       }
091     *     };
092     *         
093     *     Executor executor = Executors.newSingleThreadExecutor();
094     *     executor.execute(dispatcher);
095     *   }
096     * </pre></code>
097     * 
098     * @since 1.5
099     */
100    public class CopyOnWriteArrayList<E> 
101      implements List<E>, RandomAccess, Cloneable, Serializable
102    {
103      /**
104       * 
105       */
106      private static final long serialVersionUID = 8673264195747942595L;
107      
108      /**
109       * Where the data is stored.
110       */
111      private transient E[] data;
112    
113      /**
114       * Construct a new ArrayList with the default capacity (16).
115       */
116      public CopyOnWriteArrayList()
117      {
118        data = (E[]) new Object[0];
119      }
120    
121      /**
122       * Construct a new ArrayList, and initialize it with the elements in the
123       * supplied Collection. The initial capacity is 110% of the Collection's size.
124       * 
125       * @param c
126       *          the collection whose elements will initialize this list
127       * @throws NullPointerException
128       *           if c is null
129       */
130      public CopyOnWriteArrayList(Collection< ? extends E> c)
131      {
132        // FIXME ... correct?  use c.toArray()
133        data = (E[]) new Object[c.size()];
134        int index = 0;
135        for (E value : c)
136          data[index++] = value;
137      }
138    
139      /**
140       * Construct a new ArrayList, and initialize it with the elements in the
141       * supplied array.
142       * 
143       * @param array
144       *          the array used to initialize this list
145       * @throws NullPointerException
146       *           if array is null
147       */
148      public CopyOnWriteArrayList(E[] array)
149      {
150        data = (E[]) array.clone();
151      }
152    
153      /**
154       * Returns the number of elements in this list.
155       * 
156       * @return the list size
157       */
158      public int size()
159      {
160        return data.length;
161      }
162    
163      /**
164       * Checks if the list is empty.
165       * 
166       * @return true if there are no elements
167       */
168      public boolean isEmpty()
169      {
170        return data.length == 0;
171      }
172    
173      /**
174       * Returns true if element is in this ArrayList.
175       * 
176       * @param e
177       *          the element whose inclusion in the List is being tested
178       * @return true if the list contains e
179       */
180      public boolean contains(Object e)
181      {
182        return indexOf(e) != -1;
183      }
184    
185      /**
186       * Tests whether this collection contains all the elements in a given
187       * collection. This implementation iterates over the given collection,
188       * testing whether each element is contained in this collection. If any one
189       * is not, false is returned. Otherwise true is returned.
190       *
191       * @param c the collection to test against
192       * @return true if this collection contains all the elements in the given
193       *         collection
194       * @throws NullPointerException if the given collection is null
195       * @see #contains(Object)
196       */
197      public boolean containsAll(Collection<?> c)
198      {
199        Iterator<?> itr = c.iterator();
200        int pos = c.size();
201        while (--pos >= 0)
202          if (!contains(itr.next()))
203            return false;
204        return true;
205      }
206    
207      /**
208       * Returns the lowest index at which element appears in this List, or -1 if it
209       * does not appear.
210       * 
211       * @param e
212       *          the element whose inclusion in the List is being tested
213       * @return the index where e was found
214       */
215      public int indexOf(Object e)
216      {
217        E[] data = this.data;
218        for (int i = 0; i < data.length; i++)
219          if (equals(e, data[i]))
220            return i;
221        return -1;
222      }
223    
224      /**
225       * Return the lowest index greater equal <code>index</code> at which
226       * <code>e</code> appears in this List, or -1 if it does not
227       * appear.
228       *
229       * @param e the element whose inclusion in the list is being tested
230       * @param index the index at which the search begins
231       * @return the index where <code>e</code> was found
232       */
233      public int indexOf(E e, int index)
234      {
235        E[] data = this.data;
236    
237        for (int i = index; i < data.length; i++)
238          if (equals(e, data[i]))
239            return i;
240        return -1;
241      }
242    
243      /**
244       * Returns the highest index at which element appears in this List, or -1 if
245       * it does not appear.
246       * 
247       * @param e
248       *          the element whose inclusion in the List is being tested
249       * @return the index where e was found
250       */
251      public int lastIndexOf(Object e)
252      {
253        E[] data = this.data;
254        for (int i = data.length - 1; i >= 0; i--)
255          if (equals(e, data[i]))
256            return i;
257        return -1;
258      }
259    
260      /**
261       * Returns the highest index lesser equal <code>index</code> at
262       * which <code>e</code> appears in this List, or -1 if it does not
263       * appear.
264       *
265       * @param e the element whose inclusion in the list is being tested
266       * @param index the index at which the search begins
267       * @return the index where <code>e</code> was found
268       */
269      public int lastIndexOf(E e, int index)
270      {
271        E[] data = this.data;
272    
273        for (int i = index; i >= 0; i--)
274          if (equals(e, data[i]))
275            return i;
276        return -1;
277      }
278    
279      /**
280       * Creates a shallow copy of this ArrayList (elements are not cloned).
281       * 
282       * @return the cloned object
283       */
284      public Object clone()
285      {
286        CopyOnWriteArrayList<E> clone = null;
287        try
288          {
289            clone = (CopyOnWriteArrayList<E>) super.clone();
290          }
291        catch (CloneNotSupportedException e)
292          {
293            // Impossible to get here.
294          }
295        return clone;
296      }
297    
298      /**
299       * Returns an Object array containing all of the elements in this ArrayList.
300       * The array is independent of this list.
301       * 
302       * @return an array representation of this list
303       */
304      public Object[] toArray()
305      {
306        E[] data = this.data;
307        E[] array = (E[]) new Object[data.length];
308        System.arraycopy(data, 0, array, 0, data.length);
309        return array;
310      }
311    
312      /**
313       * Returns an Array whose component type is the runtime component type of the
314       * passed-in Array. The returned Array is populated with all of the elements
315       * in this ArrayList. If the passed-in Array is not large enough to store all
316       * of the elements in this List, a new Array will be created and returned; if
317       * the passed-in Array is <i>larger</i> than the size of this List, then
318       * size() index will be set to null.
319       * 
320       * @param a
321       *          the passed-in Array
322       * @return an array representation of this list
323       * @throws ArrayStoreException
324       *           if the runtime type of a does not allow an element in this list
325       * @throws NullPointerException
326       *           if a is null
327       */
328      public <T> T[] toArray(T[] a)
329      {
330        E[] data = this.data;
331        if (a.length < data.length)
332          a = (T[]) Array.newInstance(a.getClass().getComponentType(), data.length);
333        else if (a.length > data.length)
334          a[data.length] = null;
335        System.arraycopy(data, 0, a, 0, data.length);
336        return a;
337      }
338    
339      /**
340       * Retrieves the element at the user-supplied index.
341       * 
342       * @param index
343       *          the index of the element we are fetching
344       * @throws IndexOutOfBoundsException
345       *           if index &lt; 0 || index &gt;= size()
346       */
347      public E get(int index)
348      {
349        return data[index];
350      }
351    
352      /**
353       * Sets the element at the specified index. The new element, e, can be an
354       * object of any type or null.
355       * 
356       * @param index
357       *          the index at which the element is being set
358       * @param e
359       *          the element to be set
360       * @return the element previously at the specified index
361       * @throws IndexOutOfBoundsException
362       *           if index &lt; 0 || index &gt;= 0
363       */
364      public synchronized E set(int index, E e)
365      {
366        E result = data[index];
367        E[] newData = (E[]) data.clone();
368        newData[index] = e;
369        data = newData;
370        return result;
371      }
372    
373      /**
374       * Appends the supplied element to the end of this list. The element, e, can
375       * be an object of any type or null.
376       * 
377       * @param e
378       *          the element to be appended to this list
379       * @return true, the add will always succeed
380       */
381      public synchronized boolean add(E e)
382      {
383        E[] data = this.data;
384        E[] newData = (E[]) new Object[data.length + 1];
385        System.arraycopy(data, 0, newData, 0, data.length);
386        newData[data.length] = e;
387        this.data = newData;
388        return true;
389      }
390    
391      /**
392       * Adds the supplied element at the specified index, shifting all elements
393       * currently at that index or higher one to the right. The element, e, can be
394       * an object of any type or null.
395       * 
396       * @param index
397       *          the index at which the element is being added
398       * @param e
399       *          the item being added
400       * @throws IndexOutOfBoundsException
401       *           if index &lt; 0 || index &gt; size()
402       */
403      public synchronized void add(int index, E e)
404      {
405        E[] data = this.data;
406        E[] newData = (E[]) new Object[data.length + 1];
407        System.arraycopy(data, 0, newData, 0, index);
408        newData[index] = e;
409        System.arraycopy(data, index, newData, index + 1, data.length - index);
410        this.data = newData;
411      }
412    
413      /**
414       * Removes the element at the user-supplied index.
415       * 
416       * @param index
417       *          the index of the element to be removed
418       * @return the removed Object
419       * @throws IndexOutOfBoundsException
420       *           if index &lt; 0 || index &gt;= size()
421       */
422      public synchronized E remove(int index)
423      {
424        if (index < 0 || index >= this.size())
425          throw new IndexOutOfBoundsException("index = " +  index);
426        
427        E[] snapshot = this.data;
428        E[] newData = (E[]) new Object[snapshot.length - 1];
429        
430        E result = snapshot[index];
431        
432        if (index > 0)
433          System.arraycopy(snapshot, 0, newData, 0, index);
434        
435        System.arraycopy(snapshot, index + 1, newData, index,
436                         snapshot.length - index - 1);
437        
438        this.data = newData;
439        
440        return result;
441      }
442    
443      /**
444       * Remove the first occurrence, if any, of the given object from this list,
445       * returning <code>true</code> if the object was removed, <code>false</code>
446       * otherwise.
447       * 
448       * @param element the object to be removed.
449       * @return true if element was removed, false otherwise. false means also that
450       * the underlying storage was unchanged after this operation concluded.
451       */
452      public synchronized boolean remove(Object element)
453      {
454        E[] snapshot = this.data;
455        E[] newData = (E[]) new Object[snapshot.length - 1];
456        
457        // search the element to remove while filling the backup array
458        // this way we can run this method in O(n)
459        int elementIndex = -1;
460        for (int i = 0; i < snapshot.length; i++)
461          {
462            if (equals(element, snapshot[i]))
463              {
464                elementIndex = i;
465                break;
466              }
467            
468            if (i < newData.length)
469              newData[i] = snapshot[i];
470          }
471        
472        if (elementIndex < 0)
473          return false;
474         
475        System.arraycopy(snapshot, elementIndex + 1, newData, elementIndex,
476                         snapshot.length - elementIndex - 1);
477        this.data = newData;
478        
479        return true;
480      }
481      
482      /**
483       * Removes all the elements contained in the given collection.
484       * This method removes the elements that are contained in both
485       * this list and in the given collection.
486       * 
487       * @param c the collection containing the elements to be removed from this
488       * list.
489       * @return true if at least one element was removed, indicating that
490       * the list internal storage changed as a result, false otherwise. 
491       */
492      public synchronized boolean removeAll(Collection<?> c)
493      {
494        if (c.size() == 0)
495          return false;
496        
497        E [] snapshot = this.data;
498        E [] storage = (E[]) new Object[this.data.length]; 
499        boolean changed = false;
500        
501        int length = 0;
502        for (E element : snapshot)
503          {
504            // copy all the elements, including null values
505            // if the collection can hold it
506            // FIXME: slow operation
507            if (c.contains(element))
508              changed = true;
509            else
510              storage[length++] = element;
511          }
512        
513        if (!changed)
514          return false;
515        
516        E[] newData = (E[]) new Object[length];
517        System.arraycopy(storage, 0, newData, 0, length);
518        
519        this.data = newData;
520        
521        return true;
522      }
523      
524      /**
525       * Removes all the elements that are not in the passed collection.
526       * If the collection is void, this method has the same effect of
527       * <code>clear()</code>.
528       * Please, note that this method is extremely slow (unless the argument has
529       * <code>size == 0</code>) and has bad performance is both space and time
530       * usage.
531       * 
532       * @param c the collection containing the elements to be retained by this
533       * list.
534       * @return true the list internal storage changed as a result of this
535       * operation, false otherwise.
536       */
537      public synchronized boolean retainAll(Collection<?> c)
538      {
539        // if the given collection does not contain elements
540        // we remove all the elements from our storage
541        if (c.size() == 0)
542          {
543            this.clear();
544            return true;
545          }
546        
547        E [] snapshot = this.data;
548        E [] storage = (E[]) new Object[this.data.length]; 
549        
550        int length = 0;
551        for (E element : snapshot)
552          {
553            if (c.contains(element))
554              storage[length++] = element;
555          }
556        
557        // means we retained all the elements previously in our storage
558        // we are running already slow here, but at least we avoid copying
559        // another array and changing the internal storage
560        if (length == snapshot.length)
561          return false;
562        
563        E[] newData = (E[]) new Object[length];
564        System.arraycopy(storage, 0, newData, 0, length);
565        
566        this.data = newData;
567        
568        return true;
569      }
570      
571      /**
572       * Removes all elements from this List
573       */
574      public synchronized void clear()
575      {
576        data = (E[]) new Object[0];
577      }
578    
579      /**
580       * Add each element in the supplied Collection to this List. It is undefined
581       * what happens if you modify the list while this is taking place; for
582       * example, if the collection contains this list. c can contain objects of any
583       * type, as well as null values.
584       * 
585       * @param c
586       *          a Collection containing elements to be added to this List
587       * @return true if the list was modified, in other words c is not empty
588       * @throws NullPointerException
589       *           if c is null
590       */
591      public synchronized boolean addAll(Collection< ? extends E> c)
592      {
593        return addAll(data.length, c);
594      }
595    
596      /**
597       * Add all elements in the supplied collection, inserting them beginning at
598       * the specified index. c can contain objects of any type, as well as null
599       * values.
600       * 
601       * @param index
602       *          the index at which the elements will be inserted
603       * @param c
604       *          the Collection containing the elements to be inserted
605       * @throws IndexOutOfBoundsException
606       *           if index &lt; 0 || index &gt; 0
607       * @throws NullPointerException
608       *           if c is null
609       */
610      public synchronized boolean addAll(int index, Collection< ? extends E> c)
611      {
612        if (index < 0 || index > this.size())
613          throw new IndexOutOfBoundsException("index = " +  index);
614        
615        int csize = c.size();
616        if (csize == 0)
617          return false;
618        
619        E[] data = this.data;
620        Iterator<? extends E> itr = c.iterator();
621        
622        E[] newData = (E[]) new Object[data.length + csize];
623        
624        // avoid this call at all if we were asked to put the elements at the
625        // beginning of our storage
626        if (index != 0)
627          System.arraycopy(data, 0, newData, 0, index);
628        
629        int itemsLeft = index;
630        
631        for (E value : c)
632          newData[index++] = value;
633        
634        // now copy the remaining elements
635        System.arraycopy(data, itemsLeft, newData, 0, data.length - itemsLeft);
636        
637        this.data = newData;
638        
639        return true;
640      }
641      
642      /**
643       * Adds an element if the list does not contains it already.
644       * 
645       * @param val the element to add to the list.
646       * @return true if the element was added, false otherwise.
647       */
648      public synchronized boolean addIfAbsent(E val)
649      {
650        if (contains(val))
651          return false;
652        add(val);
653        return true;
654      }
655    
656      /**
657       * Adds all the element from the given collection that are not already
658       * in this list.
659       * 
660       * @param c the Collection containing the elements to be inserted
661       * @return true the list internal storage changed as a result of this
662       * operation, false otherwise.
663       */
664      public synchronized int addAllAbsent(Collection<? extends E> c)
665      {
666        int size = c.size();
667        if (size == 0)
668          return 0;
669        
670        E [] snapshot = this.data;
671        E [] storage = (E[]) new Object[size];
672        
673        size = 0;
674        for (E val : c)
675          {
676            if (!this.contains(val))
677              storage[size++] = val;
678          }
679        
680        if (size == 0)
681          return 0;
682        
683        // append storage to data
684        E [] newData = (E[]) new Object[snapshot.length + size];
685        
686        System.arraycopy(snapshot, 0, newData, 0, snapshot.length);
687        System.arraycopy(storage, 0, newData, snapshot.length, size);
688        
689        this.data = newData;
690        
691        return size;
692      }
693    
694      public String toString()
695      {
696        return Arrays.toString(this.data);
697      }
698    
699      public boolean equals(Object o)
700      {
701        if (o == null)
702          return false;
703        
704        if (this == o)
705          return true;
706        
707        // let's see if 'o' is a list, if so, we need to compare the elements
708        // as returned by the iterator
709        if (o instanceof List)
710          {
711            List<?> source = (List<?>) o;
712            
713            if (source.size() != this.size())
714              return false;
715            
716            Iterator<?> sourceIterator = source.iterator();
717            for (E element : this)
718              {
719                if (!element.equals(sourceIterator.next()))
720                  return false;
721              }
722    
723            return true;
724          }
725        
726        return false;
727      }
728      
729      public int hashCode()
730      {
731        // see http://java.sun.com/6/docs/api/java/util/List.html#hashcode()
732        int hashcode = 1;
733        for (E element : this)
734          {
735            hashcode = 31 * hashcode + (element == null ? 0 : element.hashCode());
736          }
737        return hashcode;
738      }
739      
740      /**
741       * Return an Iterator containing the elements of this list.
742       * The Iterator uses a snapshot of the state of the internal storage
743       * at the moment this method is called and does <strong>not</strong> support
744       * update operations, so no synchronization is needed to traverse the
745       * iterator.
746       * 
747       * @return an Iterator containing the elements of this list in sequence.
748       */
749      public Iterator<E> iterator()
750      {
751        return new Iterator<E>()
752        {
753          E [] iteratorData = CopyOnWriteArrayList.this.data;
754          int currentElement = 0;
755          
756          public boolean hasNext()
757          {
758            return (currentElement < iteratorData.length);
759          }
760    
761          public E next()
762          {
763            return iteratorData[currentElement++];
764          }
765    
766          public void remove()
767          {
768            throw new UnsupportedOperationException("updating of elements in " +
769                                                    "iterators is not supported " +
770                                                    "by this class");
771          }
772        };
773      }
774      
775      /**
776       * Return a ListIterator containing the elements of this list.
777       * The Iterator uses a snapshot of the state of the internal storage
778       * at the moment this method is called and does <strong>not</strong> support
779       * update operations, so no synchronization is needed to traverse the
780       * iterator.
781       * 
782       * @return a ListIterator containing the elements of this list in sequence.
783       */
784      public ListIterator<E> listIterator()
785      {
786        return listIterator(0);
787      }
788    
789      /**
790       * Return a ListIterator over the elements of this list starting at
791       * the specified index.  An initial call to {@code next()} will thus
792       * return the element at {@code index}, while an initial call to
793       * {@code previous()} will return the element at {@code index-1}.  The
794       * Iterator uses a snapshot of the state of the internal storage
795       * at the moment this method is called and does <strong>not</strong> support
796       * update operations, so no synchronization is needed to traverse the
797       * iterator.
798       * 
799       * @param index the index at which to start iterating.
800       * @return a ListIterator containing the elements of this list in sequence.
801       */
802      public ListIterator<E> listIterator(final int index)
803      {
804        if (index < 0 || index > size())
805          throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
806                                              + size());
807    
808        return new ListIterator<E>()
809        {
810          E [] iteratorData = CopyOnWriteArrayList.this.data;
811          int currentElement = index;
812          
813          public void add(E o)
814          {
815            throw new UnsupportedOperationException("updating of elements in " +
816                                                    "iterators is not supported " +
817                                                    "by this class");
818          }
819    
820          public boolean hasNext()
821          {
822            return (currentElement < iteratorData.length);
823          }
824    
825          public boolean hasPrevious()
826          {
827            return (currentElement > 0);
828          }
829    
830          public E next()
831          {
832            if (hasNext() == false)
833              throw new java.util.NoSuchElementException();
834            
835            return iteratorData[currentElement++];
836          }
837    
838          public int nextIndex()
839          {
840            return (currentElement + 1);
841          }
842    
843          public E previous()
844          {
845            if (hasPrevious() == false)
846              throw new java.util.NoSuchElementException();
847            
848            return iteratorData[--currentElement];
849          }
850    
851          public int previousIndex()
852          {
853            return (currentElement - 1);
854          }
855    
856          public void remove()
857          {
858            throw new UnsupportedOperationException("updating of elements in " +
859                                                    "iterators is not supported " +
860                                                    "by this class");
861          }
862    
863          public void set(E o)
864          {
865            throw new UnsupportedOperationException("updating of elements in " +
866                                                    "iterators is not supported " +
867                                                    "by this class");
868          }
869          
870        };
871      }
872      
873      /**
874       * Obtain a List view of a subsection of this list, from fromIndex
875       * (inclusive) to toIndex (exclusive). If the two indices are equal, the
876       * sublist is empty. The returned list should be modifiable if and only
877       * if this list is modifiable. Changes to the returned list should be
878       * reflected in this list. If this list is structurally modified in
879       * any way other than through the returned list, the result of any subsequent
880       * operations on the returned list is undefined.
881       * <p>
882       *
883       * This implementation returns a subclass of AbstractList. It stores, in
884       * private fields, the offset and size of the sublist, and the expected
885       * modCount of the backing list. If the backing list implements RandomAccess,
886       * the sublist will also.
887       * <p>
888       *
889       * The subclass's <code>set(int, Object)</code>, <code>get(int)</code>,
890       * <code>add(int, Object)</code>, <code>remove(int)</code>,
891       * <code>addAll(int, Collection)</code> and
892       * <code>removeRange(int, int)</code> methods all delegate to the
893       * corresponding methods on the backing abstract list, after
894       * bounds-checking the index and adjusting for the offset. The
895       * <code>addAll(Collection c)</code> method merely returns addAll(size, c).
896       * The <code>listIterator(int)</code> method returns a "wrapper object"
897       * over a list iterator on the backing list, which is created with the
898       * corresponding method on the backing list. The <code>iterator()</code>
899       * method merely returns listIterator(), and the <code>size()</code> method
900       * merely returns the subclass's size field.
901       * <p>
902       *
903       * All methods first check to see if the actual modCount of the backing
904       * list is equal to its expected value, and throw a
905       * ConcurrentModificationException if it is not. 
906       *
907       * @param fromIndex the index that the returned list should start from
908       *        (inclusive)
909       * @param toIndex the index that the returned list should go to (exclusive)
910       * @return a List backed by a subsection of this list
911       * @throws IndexOutOfBoundsException if fromIndex &lt; 0
912       *         || toIndex &gt; size()
913       * @throws IndexOutOfBoundsException if fromIndex &gt; toIndex
914       * @see ConcurrentModificationException
915       * @see RandomAccess
916       */
917      public synchronized List<E> subList(int fromIndex, int toIndex)
918      {
919        // This follows the specification of AbstractList, but is inconsistent
920        // with the one in List. Don't you love Sun's inconsistencies?
921        if (fromIndex > toIndex)
922          throw new IndexOutOfBoundsException(fromIndex + " > " + toIndex);
923        if (fromIndex < 0 || toIndex > size())
924          throw new IndexOutOfBoundsException();
925    
926        if (this instanceof RandomAccess)
927          return new RandomAccessSubList<E>(this, fromIndex, toIndex);
928        return new SubList<E>(this, fromIndex, toIndex);
929      }
930    
931      /**
932       * This class follows the implementation requirements set forth in
933       * {@link AbstractList#subList(int, int)}. It matches Sun's implementation
934       * by using a non-public top-level class in the same package.
935       *
936       * @author Original author unknown
937       * @author Eric Blake (ebb9@email.byu.edu)
938       */
939      private static class SubList<E> 
940        extends AbstractList<E>
941      {
942        // Package visible, for use by iterator.
943        /** The original list. */
944        final CopyOnWriteArrayList<E> backingList;
945        /** The index of the first element of the sublist. */
946        final int offset;
947        /** The size of the sublist. */
948        int size;
949        /** The backing data */
950        E[] data;
951    
952        /**
953         * Construct the sublist.
954         *
955         * @param backing the list this comes from
956         * @param fromIndex the lower bound, inclusive
957         * @param toIndex the upper bound, exclusive
958         */
959        SubList(CopyOnWriteArrayList<E> backing, int fromIndex, int toIndex)
960        {
961          backingList = backing;
962          data = backing.data;
963          offset = fromIndex;
964          size = toIndex - fromIndex;
965        }
966        
967        /**
968         * This method checks the two modCount fields to ensure that there has
969         * not been a concurrent modification, returning if all is okay.
970         *
971         * @throws ConcurrentModificationException if the backing list has been
972         *         modified externally to this sublist
973         */
974        // This can be inlined. Package visible, for use by iterator.
975        void checkMod()
976        {
977          if (data != backingList.data)
978            throw new ConcurrentModificationException();
979        }
980        
981        /**
982         * This method checks that a value is between 0 and size (inclusive). If
983         * it is not, an exception is thrown.
984         *
985         * @param index the value to check
986         * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
987         */
988        // This will get inlined, since it is private.
989        private void checkBoundsInclusive(int index)
990        {
991          if (index < 0 || index > size)
992            throw new IndexOutOfBoundsException("Index: " + index +
993                                                ", Size:" + size);
994        }
995        
996        /**
997         * This method checks that a value is between 0 (inclusive) and size
998         * (exclusive). If it is not, an exception is thrown.
999         *
1000         * @param index the value to check
1001         * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
1002         */
1003        // This will get inlined, since it is private.
1004        private void checkBoundsExclusive(int index)
1005        {
1006          if (index < 0 || index >= size)
1007            throw new IndexOutOfBoundsException("Index: " + index +
1008                                                ", Size:" + size);
1009        }
1010        
1011        /**
1012         * Specified by AbstractList.subList to return the private field size.
1013         *
1014         * @return the sublist size
1015         * @throws ConcurrentModificationException if the backing list has been
1016         *         modified externally to this sublist
1017         */
1018        public int size()
1019        {
1020          synchronized (backingList)
1021            {
1022              checkMod();
1023              return size;
1024            }
1025        }
1026        
1027        public void clear()
1028        {
1029          synchronized (backingList)
1030            {
1031              E[] snapshot = backingList.data;
1032              E[] newData = (E[]) new Object[snapshot.length - size];
1033    
1034              int toIndex = size + offset;
1035              
1036              System.arraycopy(snapshot, 0, newData, 0, offset);
1037              System.arraycopy(snapshot, toIndex, newData, offset,
1038                               snapshot.length - toIndex);
1039              
1040              backingList.data = newData;
1041              this.data = backingList.data;
1042              this.size = 0;
1043            }
1044        }
1045        
1046        /**
1047         * Specified by AbstractList.subList to delegate to the backing list.
1048         *
1049         * @param index the location to modify
1050         * @param o the new value
1051         * @return the old value
1052         * @throws ConcurrentModificationException if the backing list has been
1053         *         modified externally to this sublist
1054         * @throws UnsupportedOperationException if the backing list does not
1055         *         support the set operation
1056         * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
1057         * @throws ClassCastException if o cannot be added to the backing list due
1058         *         to its type
1059         * @throws IllegalArgumentException if o cannot be added to the backing list
1060         *         for some other reason
1061         */
1062        public E set(int index, E o)
1063        {
1064          synchronized (backingList)
1065            {
1066              checkMod();
1067              checkBoundsExclusive(index);
1068              
1069              E el =  backingList.set(index + offset, o);
1070              this.data = backingList.data;
1071              
1072              return el;
1073            }
1074        }
1075        
1076        /**
1077         * Specified by AbstractList.subList to delegate to the backing list.
1078         *
1079         * @param index the location to get from
1080         * @return the object at that location
1081         * @throws ConcurrentModificationException if the backing list has been
1082         *         modified externally to this sublist
1083         * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
1084         */
1085        public E get(int index)
1086        {
1087          synchronized (backingList)
1088          {
1089            checkMod();
1090            checkBoundsExclusive(index);
1091            
1092            return backingList.get(index + offset);
1093          }
1094        }
1095        
1096        /**
1097         * Specified by AbstractList.subList to delegate to the backing list.
1098         *
1099         * @param index the index to insert at
1100         * @param o the object to add
1101         * @throws ConcurrentModificationException if the backing list has been
1102         *         modified externally to this sublist
1103         * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
1104         * @throws UnsupportedOperationException if the backing list does not
1105         *         support the add operation.
1106         * @throws ClassCastException if o cannot be added to the backing list due
1107         *         to its type.
1108         * @throws IllegalArgumentException if o cannot be added to the backing
1109         *         list for some other reason.
1110         */
1111        public void add(int index, E o)
1112        {
1113          synchronized (backingList)
1114          {
1115            checkMod();
1116            checkBoundsInclusive(index);
1117          
1118            backingList.add(index + offset, o);
1119            
1120            this.data = backingList.data;
1121            size++;
1122          }
1123        }
1124        
1125        /**
1126         * Specified by AbstractList.subList to delegate to the backing list.
1127         *
1128         * @param index the index to remove
1129         * @return the removed object
1130         * @throws ConcurrentModificationException if the backing list has been
1131         *         modified externally to this sublist
1132         * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
1133         * @throws UnsupportedOperationException if the backing list does not
1134         *         support the remove operation
1135         */
1136        public E remove(int index)
1137        {
1138          synchronized (backingList)
1139          {
1140            checkMod();
1141            checkBoundsExclusive(index);
1142            E o = backingList.remove(index + offset);
1143            
1144            this.data = backingList.data;
1145            size--;
1146            
1147            return o;
1148          }
1149        }
1150        
1151        /**
1152         * Specified by AbstractList.subList to delegate to the backing list.
1153         *
1154         * @param index the location to insert at
1155         * @param c the collection to insert
1156         * @return true if this list was modified, in other words, c is non-empty
1157         * @throws ConcurrentModificationException if the backing list has been
1158         *         modified externally to this sublist
1159         * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
1160         * @throws UnsupportedOperationException if this list does not support the
1161         *         addAll operation
1162         * @throws ClassCastException if some element of c cannot be added to this
1163         *         list due to its type
1164         * @throws IllegalArgumentException if some element of c cannot be added
1165         *         to this list for some other reason
1166         * @throws NullPointerException if the specified collection is null
1167         */
1168        public boolean addAll(int index, Collection<? extends E> c)
1169        {
1170          synchronized (backingList)
1171          {
1172            checkMod();
1173            checkBoundsInclusive(index);
1174            int csize = c.size();
1175            boolean result = backingList.addAll(offset + index, c);
1176            
1177            this.data = backingList.data;
1178            size += csize;
1179            
1180            return result;
1181          }
1182        }
1183        
1184        /**
1185         * Specified by AbstractList.subList to return addAll(size, c).
1186         *
1187         * @param c the collection to insert
1188         * @return true if this list was modified, in other words, c is non-empty
1189         * @throws ConcurrentModificationException if the backing list has been
1190         *         modified externally to this sublist
1191         * @throws UnsupportedOperationException if this list does not support the
1192         *         addAll operation
1193         * @throws ClassCastException if some element of c cannot be added to this
1194         *         list due to its type
1195         * @throws IllegalArgumentException if some element of c cannot be added
1196         *         to this list for some other reason
1197         * @throws NullPointerException if the specified collection is null
1198         */
1199        public boolean addAll(Collection<? extends E> c)
1200        {
1201          synchronized (backingList)
1202          {
1203            return addAll(size, c);
1204          }
1205        }
1206        
1207        /**
1208         * Specified by AbstractList.subList to return listIterator().
1209         *
1210         * @return an iterator over the sublist
1211         */
1212        public Iterator<E> iterator()
1213        {
1214          return listIterator();
1215        }
1216        
1217        /**
1218         * Specified by AbstractList.subList to return a wrapper around the
1219         * backing list's iterator.
1220         *
1221         * @param index the start location of the iterator
1222         * @return a list iterator over the sublist
1223         * @throws ConcurrentModificationException if the backing list has been
1224         *         modified externally to this sublist
1225         * @throws IndexOutOfBoundsException if the value is out of range
1226         */
1227        public ListIterator<E> listIterator(final int index)
1228        {
1229          checkMod();
1230          checkBoundsInclusive(index);
1231    
1232          return new ListIterator<E>()
1233          {
1234            private final ListIterator<E> i =
1235              backingList.listIterator(index + offset);
1236            private int position = index;
1237    
1238            /**
1239             * Tests to see if there are any more objects to
1240             * return.
1241             *
1242             * @return True if the end of the list has not yet been
1243             *         reached.
1244             */
1245            public boolean hasNext()
1246            {
1247              return position < size;
1248            }
1249    
1250            /**
1251             * Tests to see if there are objects prior to the
1252             * current position in the list.
1253             *
1254             * @return True if objects exist prior to the current
1255             *         position of the iterator.
1256             */
1257            public boolean hasPrevious()
1258            {
1259              return position > 0;
1260            }
1261    
1262            /**
1263             * Retrieves the next object from the list.
1264             *
1265             * @return The next object.
1266             * @throws NoSuchElementException if there are no
1267             *         more objects to retrieve.
1268             * @throws ConcurrentModificationException if the
1269             *         list has been modified elsewhere.
1270             */
1271            public E next()
1272            {
1273              if (position == size)
1274                throw new NoSuchElementException();
1275              position++;
1276              return i.next();
1277            }
1278    
1279            /**
1280             * Retrieves the previous object from the list.
1281             *
1282             * @return The next object.
1283             * @throws NoSuchElementException if there are no
1284             *         previous objects to retrieve.
1285             * @throws ConcurrentModificationException if the
1286             *         list has been modified elsewhere.
1287             */
1288            public E previous()
1289            {
1290              if (position == 0)
1291                throw new NoSuchElementException();
1292              position--;
1293              return i.previous();
1294            }
1295    
1296            /**
1297             * Returns the index of the next element in the
1298             * list, which will be retrieved by <code>next()</code>
1299             *
1300             * @return The index of the next element.
1301             */
1302            public int nextIndex()
1303            {
1304              return i.nextIndex() - offset;
1305            }
1306    
1307            /**
1308             * Returns the index of the previous element in the
1309             * list, which will be retrieved by <code>previous()</code>
1310             *
1311             * @return The index of the previous element.
1312             */
1313            public int previousIndex()
1314            {
1315              return i.previousIndex() - offset;
1316            }
1317    
1318            /**
1319             * Removes the last object retrieved by <code>next()</code>
1320             * from the list, if the list supports object removal.
1321             *
1322             * @throws IllegalStateException if the iterator is positioned
1323             *         before the start of the list or the last object has already
1324             *         been removed.
1325             * @throws UnsupportedOperationException if the list does
1326             *         not support removing elements.
1327             */
1328            public void remove()
1329            {
1330              throw new UnsupportedOperationException("Modification not supported " +
1331                  "on CopyOnWriteArrayList iterators");
1332            }
1333    
1334            /**
1335             * Replaces the last object retrieved by <code>next()</code>
1336             * or <code>previous</code> with o, if the list supports object
1337             * replacement and an add or remove operation has not already
1338             * been performed.
1339             *
1340             * @throws IllegalStateException if the iterator is positioned
1341             *         before the start of the list or the last object has already
1342             *         been removed.
1343             * @throws UnsupportedOperationException if the list doesn't support
1344             *         the addition or removal of elements.
1345             * @throws ClassCastException if the type of o is not a valid type
1346             *         for this list.
1347             * @throws IllegalArgumentException if something else related to o
1348             *         prevents its addition.
1349             * @throws ConcurrentModificationException if the list
1350             *         has been modified elsewhere.
1351             */
1352            public void set(E o)
1353            {
1354              throw new UnsupportedOperationException("Modification not supported " +
1355                  "on CopyOnWriteArrayList iterators");
1356            }
1357    
1358            /**
1359             * Adds the supplied object before the element that would be returned
1360             * by a call to <code>next()</code>, if the list supports addition.
1361             * 
1362             * @param o The object to add to the list.
1363             * @throws UnsupportedOperationException if the list doesn't support
1364             *         the addition of new elements.
1365             * @throws ClassCastException if the type of o is not a valid type
1366             *         for this list.
1367             * @throws IllegalArgumentException if something else related to o
1368             *         prevents its addition.
1369             * @throws ConcurrentModificationException if the list
1370             *         has been modified elsewhere.
1371             */
1372            public void add(E o)
1373            {
1374              throw new UnsupportedOperationException("Modification not supported " +
1375                  "on CopyOnWriteArrayList iterators");
1376            } 
1377          };
1378        }
1379      } // class SubList
1380    
1381      /**
1382       * This class is a RandomAccess version of SubList, as required by
1383       * {@link AbstractList#subList(int, int)}.
1384       *
1385       * @author Eric Blake (ebb9@email.byu.edu)
1386       */
1387      private static final class RandomAccessSubList<E> extends SubList<E>
1388        implements RandomAccess
1389      {
1390        /**
1391         * Construct the sublist.
1392         *
1393         * @param backing the list this comes from
1394         * @param fromIndex the lower bound, inclusive
1395         * @param toIndex the upper bound, exclusive
1396         */
1397        RandomAccessSubList(CopyOnWriteArrayList<E> backing, int fromIndex, int toIndex)
1398        {
1399          super(backing, fromIndex, toIndex);
1400        }
1401      } // class RandomAccessSubList
1402    
1403      /**
1404       * Serializes this object to the given stream.
1405       * 
1406       * @param s
1407       *          the stream to write to
1408       * @throws IOException
1409       *           if the underlying stream fails
1410       * @serialData the size field (int), the length of the backing array (int),
1411       *             followed by its elements (Objects) in proper order.
1412       */
1413      private void writeObject(ObjectOutputStream s) throws IOException
1414      {
1415        // The 'size' field.
1416        s.defaultWriteObject();
1417        // We serialize unused list entries to preserve capacity.
1418        int len = data.length;
1419        s.writeInt(len);
1420        // it would be more efficient to just write "size" items,
1421        // this need readObject read "size" items too.
1422        for (int i = 0; i < data.length; i++)
1423          s.writeObject(data[i]);
1424      }
1425    
1426      /**
1427       * Deserializes this object from the given stream.
1428       * 
1429       * @param s
1430       *          the stream to read from
1431       * @throws ClassNotFoundException
1432       *           if the underlying stream fails
1433       * @throws IOException
1434       *           if the underlying stream fails
1435       * @serialData the size field (int), the length of the backing array (int),
1436       *             followed by its elements (Objects) in proper order.
1437       */
1438      private void readObject(ObjectInputStream s) throws IOException,
1439          ClassNotFoundException
1440      {
1441        // the `size' field.
1442        s.defaultReadObject();
1443        int capacity = s.readInt();
1444        data = (E[]) new Object[capacity];
1445        for (int i = 0; i < capacity; i++)
1446          data[i] = (E) s.readObject();
1447      }
1448    
1449      static final boolean equals(Object o1, Object o2)
1450      {
1451        return o1 == null ? o2 == null : o1.equals(o2);
1452      }
1453      
1454      Object[] getArray()
1455      {
1456        return data;
1457      }
1458    }