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        int len = snapshot.length;
456    
457        if (len == 0)
458          return false;
459    
460        E[] newData = (E[]) new Object[len - 1];
461    
462        // search the element to remove while filling the backup array
463        // this way we can run this method in O(n)
464        int elementIndex = -1;
465        for (int i = 0; i < snapshot.length; i++)
466          {
467            if (equals(element, snapshot[i]))
468              {
469                elementIndex = i;
470                break;
471              }
472    
473            if (i < newData.length)
474              newData[i] = snapshot[i];
475          }
476    
477        if (elementIndex < 0)
478          return false;
479    
480        System.arraycopy(snapshot, elementIndex + 1, newData, elementIndex,
481                         snapshot.length - elementIndex - 1);
482        this.data = newData;
483    
484        return true;
485      }
486    
487      /**
488       * Removes all the elements contained in the given collection.
489       * This method removes the elements that are contained in both
490       * this list and in the given collection.
491       *
492       * @param c the collection containing the elements to be removed from this
493       * list.
494       * @return true if at least one element was removed, indicating that
495       * the list internal storage changed as a result, false otherwise.
496       */
497      public synchronized boolean removeAll(Collection<?> c)
498      {
499        if (c.size() == 0)
500          return false;
501    
502        E [] snapshot = this.data;
503        E [] storage = (E[]) new Object[this.data.length];
504        boolean changed = false;
505    
506        int length = 0;
507        for (E element : snapshot)
508          {
509            // copy all the elements, including null values
510            // if the collection can hold it
511            // FIXME: slow operation
512            if (c.contains(element))
513              changed = true;
514            else
515              storage[length++] = element;
516          }
517    
518        if (!changed)
519          return false;
520    
521        E[] newData = (E[]) new Object[length];
522        System.arraycopy(storage, 0, newData, 0, length);
523    
524        this.data = newData;
525    
526        return true;
527      }
528    
529      /**
530       * Removes all the elements that are not in the passed collection.
531       * If the collection is void, this method has the same effect of
532       * <code>clear()</code>.
533       * Please, note that this method is extremely slow (unless the argument has
534       * <code>size == 0</code>) and has bad performance is both space and time
535       * usage.
536       *
537       * @param c the collection containing the elements to be retained by this
538       * list.
539       * @return true the list internal storage changed as a result of this
540       * operation, false otherwise.
541       */
542      public synchronized boolean retainAll(Collection<?> c)
543      {
544        // if the given collection does not contain elements
545        // we remove all the elements from our storage
546        if (c.size() == 0)
547          {
548            this.clear();
549            return true;
550          }
551    
552        E [] snapshot = this.data;
553        E [] storage = (E[]) new Object[this.data.length];
554    
555        int length = 0;
556        for (E element : snapshot)
557          {
558            if (c.contains(element))
559              storage[length++] = element;
560          }
561    
562        // means we retained all the elements previously in our storage
563        // we are running already slow here, but at least we avoid copying
564        // another array and changing the internal storage
565        if (length == snapshot.length)
566          return false;
567    
568        E[] newData = (E[]) new Object[length];
569        System.arraycopy(storage, 0, newData, 0, length);
570    
571        this.data = newData;
572    
573        return true;
574      }
575    
576      /**
577       * Removes all elements from this List
578       */
579      public synchronized void clear()
580      {
581        data = (E[]) new Object[0];
582      }
583    
584      /**
585       * Add each element in the supplied Collection to this List. It is undefined
586       * what happens if you modify the list while this is taking place; for
587       * example, if the collection contains this list. c can contain objects of any
588       * type, as well as null values.
589       *
590       * @param c
591       *          a Collection containing elements to be added to this List
592       * @return true if the list was modified, in other words c is not empty
593       * @throws NullPointerException
594       *           if c is null
595       */
596      public synchronized boolean addAll(Collection< ? extends E> c)
597      {
598        return addAll(data.length, c);
599      }
600    
601      /**
602       * Add all elements in the supplied collection, inserting them beginning at
603       * the specified index. c can contain objects of any type, as well as null
604       * values.
605       *
606       * @param index
607       *          the index at which the elements will be inserted
608       * @param c
609       *          the Collection containing the elements to be inserted
610       * @throws IndexOutOfBoundsException
611       *           if index &lt; 0 || index &gt; 0
612       * @throws NullPointerException
613       *           if c is null
614       */
615      public synchronized boolean addAll(int index, Collection< ? extends E> c)
616      {
617        if (index < 0 || index > this.size())
618          throw new IndexOutOfBoundsException("index = " +  index);
619    
620        int csize = c.size();
621        if (csize == 0)
622          return false;
623    
624        E[] data = this.data;
625        Iterator<? extends E> itr = c.iterator();
626    
627        E[] newData = (E[]) new Object[data.length + csize];
628    
629        // avoid this call at all if we were asked to put the elements at the
630        // beginning of our storage
631        if (index != 0)
632          System.arraycopy(data, 0, newData, 0, index);
633    
634        int itemsLeft = index;
635    
636        for (E value : c)
637          newData[index++] = value;
638    
639        // now copy the remaining elements
640        System.arraycopy(data, itemsLeft, newData, 0, data.length - itemsLeft);
641    
642        this.data = newData;
643    
644        return true;
645      }
646    
647      /**
648       * Adds an element if the list does not contains it already.
649       *
650       * @param val the element to add to the list.
651       * @return true if the element was added, false otherwise.
652       */
653      public synchronized boolean addIfAbsent(E val)
654      {
655        if (contains(val))
656          return false;
657        add(val);
658        return true;
659      }
660    
661      /**
662       * Adds all the element from the given collection that are not already
663       * in this list.
664       *
665       * @param c the Collection containing the elements to be inserted
666       * @return true the list internal storage changed as a result of this
667       * operation, false otherwise.
668       */
669      public synchronized int addAllAbsent(Collection<? extends E> c)
670      {
671        int size = c.size();
672        if (size == 0)
673          return 0;
674    
675        E [] snapshot = this.data;
676        E [] storage = (E[]) new Object[size];
677    
678        size = 0;
679        for (E val : c)
680          {
681            if (!this.contains(val))
682              storage[size++] = val;
683          }
684    
685        if (size == 0)
686          return 0;
687    
688        // append storage to data
689        E [] newData = (E[]) new Object[snapshot.length + size];
690    
691        System.arraycopy(snapshot, 0, newData, 0, snapshot.length);
692        System.arraycopy(storage, 0, newData, snapshot.length, size);
693    
694        this.data = newData;
695    
696        return size;
697      }
698    
699      public String toString()
700      {
701        return Arrays.toString(this.data);
702      }
703    
704      public boolean equals(Object o)
705      {
706        if (o == null)
707          return false;
708    
709        if (this == o)
710          return true;
711    
712        // let's see if 'o' is a list, if so, we need to compare the elements
713        // as returned by the iterator
714        if (o instanceof List)
715          {
716            List<?> source = (List<?>) o;
717    
718            if (source.size() != this.size())
719              return false;
720    
721            Iterator<?> sourceIterator = source.iterator();
722            for (E element : this)
723              {
724                if (!element.equals(sourceIterator.next()))
725                  return false;
726              }
727    
728            return true;
729          }
730    
731        return false;
732      }
733    
734      public int hashCode()
735      {
736        // see http://java.sun.com/6/docs/api/java/util/List.html#hashcode()
737        int hashcode = 1;
738        for (E element : this)
739          {
740            hashcode = 31 * hashcode + (element == null ? 0 : element.hashCode());
741          }
742        return hashcode;
743      }
744    
745      /**
746       * Return an Iterator containing the elements of this list.
747       * The Iterator uses a snapshot of the state of the internal storage
748       * at the moment this method is called and does <strong>not</strong> support
749       * update operations, so no synchronization is needed to traverse the
750       * iterator.
751       *
752       * @return an Iterator containing the elements of this list in sequence.
753       */
754      public Iterator<E> iterator()
755      {
756        return new Iterator<E>()
757        {
758          E [] iteratorData = CopyOnWriteArrayList.this.data;
759          int currentElement = 0;
760    
761          public boolean hasNext()
762          {
763            return (currentElement < iteratorData.length);
764          }
765    
766          public E next()
767          {
768            return iteratorData[currentElement++];
769          }
770    
771          public void remove()
772          {
773            throw new UnsupportedOperationException("updating of elements in " +
774                                                    "iterators is not supported " +
775                                                    "by this class");
776          }
777        };
778      }
779    
780      /**
781       * Return a ListIterator containing the elements of this list.
782       * The Iterator uses a snapshot of the state of the internal storage
783       * at the moment this method is called and does <strong>not</strong> support
784       * update operations, so no synchronization is needed to traverse the
785       * iterator.
786       *
787       * @return a ListIterator containing the elements of this list in sequence.
788       */
789      public ListIterator<E> listIterator()
790      {
791        return listIterator(0);
792      }
793    
794      /**
795       * Return a ListIterator over the elements of this list starting at
796       * the specified index.  An initial call to {@code next()} will thus
797       * return the element at {@code index}, while an initial call to
798       * {@code previous()} will return the element at {@code index-1}.  The
799       * Iterator uses a snapshot of the state of the internal storage
800       * at the moment this method is called and does <strong>not</strong> support
801       * update operations, so no synchronization is needed to traverse the
802       * iterator.
803       *
804       * @param index the index at which to start iterating.
805       * @return a ListIterator containing the elements of this list in sequence.
806       */
807      public ListIterator<E> listIterator(final int index)
808      {
809        if (index < 0 || index > size())
810          throw new IndexOutOfBoundsException("Index: " + index + ", Size:"
811                                              + size());
812    
813        return new ListIterator<E>()
814        {
815          E [] iteratorData = CopyOnWriteArrayList.this.data;
816          int currentElement = index;
817    
818          public void add(E o)
819          {
820            throw new UnsupportedOperationException("updating of elements in " +
821                                                    "iterators is not supported " +
822                                                    "by this class");
823          }
824    
825          public boolean hasNext()
826          {
827            return (currentElement < iteratorData.length);
828          }
829    
830          public boolean hasPrevious()
831          {
832            return (currentElement > 0);
833          }
834    
835          public E next()
836          {
837            if (hasNext() == false)
838              throw new java.util.NoSuchElementException();
839    
840            return iteratorData[currentElement++];
841          }
842    
843          public int nextIndex()
844          {
845            return (currentElement + 1);
846          }
847    
848          public E previous()
849          {
850            if (hasPrevious() == false)
851              throw new java.util.NoSuchElementException();
852    
853            return iteratorData[--currentElement];
854          }
855    
856          public int previousIndex()
857          {
858            return (currentElement - 1);
859          }
860    
861          public void remove()
862          {
863            throw new UnsupportedOperationException("updating of elements in " +
864                                                    "iterators is not supported " +
865                                                    "by this class");
866          }
867    
868          public void set(E o)
869          {
870            throw new UnsupportedOperationException("updating of elements in " +
871                                                    "iterators is not supported " +
872                                                    "by this class");
873          }
874    
875        };
876      }
877    
878      /**
879       * Obtain a List view of a subsection of this list, from fromIndex
880       * (inclusive) to toIndex (exclusive). If the two indices are equal, the
881       * sublist is empty. The returned list should be modifiable if and only
882       * if this list is modifiable. Changes to the returned list should be
883       * reflected in this list. If this list is structurally modified in
884       * any way other than through the returned list, the result of any subsequent
885       * operations on the returned list is undefined.
886       * <p>
887       *
888       * This implementation returns a subclass of AbstractList. It stores, in
889       * private fields, the offset and size of the sublist, and the expected
890       * modCount of the backing list. If the backing list implements RandomAccess,
891       * the sublist will also.
892       * <p>
893       *
894       * The subclass's <code>set(int, Object)</code>, <code>get(int)</code>,
895       * <code>add(int, Object)</code>, <code>remove(int)</code>,
896       * <code>addAll(int, Collection)</code> and
897       * <code>removeRange(int, int)</code> methods all delegate to the
898       * corresponding methods on the backing abstract list, after
899       * bounds-checking the index and adjusting for the offset. The
900       * <code>addAll(Collection c)</code> method merely returns addAll(size, c).
901       * The <code>listIterator(int)</code> method returns a "wrapper object"
902       * over a list iterator on the backing list, which is created with the
903       * corresponding method on the backing list. The <code>iterator()</code>
904       * method merely returns listIterator(), and the <code>size()</code> method
905       * merely returns the subclass's size field.
906       * <p>
907       *
908       * All methods first check to see if the actual modCount of the backing
909       * list is equal to its expected value, and throw a
910       * ConcurrentModificationException if it is not.
911       *
912       * @param fromIndex the index that the returned list should start from
913       *        (inclusive)
914       * @param toIndex the index that the returned list should go to (exclusive)
915       * @return a List backed by a subsection of this list
916       * @throws IndexOutOfBoundsException if fromIndex &lt; 0
917       *         || toIndex &gt; size()
918       * @throws IndexOutOfBoundsException if fromIndex &gt; toIndex
919       * @see ConcurrentModificationException
920       * @see RandomAccess
921       */
922      public synchronized List<E> subList(int fromIndex, int toIndex)
923      {
924        // This follows the specification of AbstractList, but is inconsistent
925        // with the one in List. Don't you love Sun's inconsistencies?
926        if (fromIndex > toIndex)
927          throw new IndexOutOfBoundsException(fromIndex + " > " + toIndex);
928        if (fromIndex < 0 || toIndex > size())
929          throw new IndexOutOfBoundsException();
930    
931        if (this instanceof RandomAccess)
932          return new RandomAccessSubList<E>(this, fromIndex, toIndex);
933        return new SubList<E>(this, fromIndex, toIndex);
934      }
935    
936      /**
937       * This class follows the implementation requirements set forth in
938       * {@link AbstractList#subList(int, int)}. It matches Sun's implementation
939       * by using a non-public top-level class in the same package.
940       *
941       * @author Original author unknown
942       * @author Eric Blake (ebb9@email.byu.edu)
943       */
944      private static class SubList<E>
945        extends AbstractList<E>
946      {
947        // Package visible, for use by iterator.
948        /** The original list. */
949        final CopyOnWriteArrayList<E> backingList;
950        /** The index of the first element of the sublist. */
951        final int offset;
952        /** The size of the sublist. */
953        int size;
954        /** The backing data */
955        E[] data;
956    
957        /**
958         * Construct the sublist.
959         *
960         * @param backing the list this comes from
961         * @param fromIndex the lower bound, inclusive
962         * @param toIndex the upper bound, exclusive
963         */
964        SubList(CopyOnWriteArrayList<E> backing, int fromIndex, int toIndex)
965        {
966          backingList = backing;
967          data = backing.data;
968          offset = fromIndex;
969          size = toIndex - fromIndex;
970        }
971    
972        /**
973         * This method checks the two modCount fields to ensure that there has
974         * not been a concurrent modification, returning if all is okay.
975         *
976         * @throws ConcurrentModificationException if the backing list has been
977         *         modified externally to this sublist
978         */
979        // This can be inlined. Package visible, for use by iterator.
980        void checkMod()
981        {
982          if (data != backingList.data)
983            throw new ConcurrentModificationException();
984        }
985    
986        /**
987         * This method checks that a value is between 0 and size (inclusive). If
988         * it is not, an exception is thrown.
989         *
990         * @param index the value to check
991         * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
992         */
993        // This will get inlined, since it is private.
994        private void checkBoundsInclusive(int index)
995        {
996          if (index < 0 || index > size)
997            throw new IndexOutOfBoundsException("Index: " + index +
998                                                ", Size:" + size);
999        }
1000    
1001        /**
1002         * This method checks that a value is between 0 (inclusive) and size
1003         * (exclusive). If it is not, an exception is thrown.
1004         *
1005         * @param index the value to check
1006         * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
1007         */
1008        // This will get inlined, since it is private.
1009        private void checkBoundsExclusive(int index)
1010        {
1011          if (index < 0 || index >= size)
1012            throw new IndexOutOfBoundsException("Index: " + index +
1013                                                ", Size:" + size);
1014        }
1015    
1016        /**
1017         * Specified by AbstractList.subList to return the private field size.
1018         *
1019         * @return the sublist size
1020         * @throws ConcurrentModificationException if the backing list has been
1021         *         modified externally to this sublist
1022         */
1023        public int size()
1024        {
1025          synchronized (backingList)
1026            {
1027              checkMod();
1028              return size;
1029            }
1030        }
1031    
1032        public void clear()
1033        {
1034          synchronized (backingList)
1035            {
1036              E[] snapshot = backingList.data;
1037              E[] newData = (E[]) new Object[snapshot.length - size];
1038    
1039              int toIndex = size + offset;
1040    
1041              System.arraycopy(snapshot, 0, newData, 0, offset);
1042              System.arraycopy(snapshot, toIndex, newData, offset,
1043                               snapshot.length - toIndex);
1044    
1045              backingList.data = newData;
1046              this.data = backingList.data;
1047              this.size = 0;
1048            }
1049        }
1050    
1051        /**
1052         * Specified by AbstractList.subList to delegate to the backing list.
1053         *
1054         * @param index the location to modify
1055         * @param o the new value
1056         * @return the old value
1057         * @throws ConcurrentModificationException if the backing list has been
1058         *         modified externally to this sublist
1059         * @throws UnsupportedOperationException if the backing list does not
1060         *         support the set operation
1061         * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
1062         * @throws ClassCastException if o cannot be added to the backing list due
1063         *         to its type
1064         * @throws IllegalArgumentException if o cannot be added to the backing list
1065         *         for some other reason
1066         */
1067        public E set(int index, E o)
1068        {
1069          synchronized (backingList)
1070            {
1071              checkMod();
1072              checkBoundsExclusive(index);
1073    
1074              E el =  backingList.set(index + offset, o);
1075              this.data = backingList.data;
1076    
1077              return el;
1078            }
1079        }
1080    
1081        /**
1082         * Specified by AbstractList.subList to delegate to the backing list.
1083         *
1084         * @param index the location to get from
1085         * @return the object at that location
1086         * @throws ConcurrentModificationException if the backing list has been
1087         *         modified externally to this sublist
1088         * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
1089         */
1090        public E get(int index)
1091        {
1092          synchronized (backingList)
1093          {
1094            checkMod();
1095            checkBoundsExclusive(index);
1096    
1097            return backingList.get(index + offset);
1098          }
1099        }
1100    
1101        /**
1102         * Specified by AbstractList.subList to delegate to the backing list.
1103         *
1104         * @param index the index to insert at
1105         * @param o the object to add
1106         * @throws ConcurrentModificationException if the backing list has been
1107         *         modified externally to this sublist
1108         * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
1109         * @throws UnsupportedOperationException if the backing list does not
1110         *         support the add operation.
1111         * @throws ClassCastException if o cannot be added to the backing list due
1112         *         to its type.
1113         * @throws IllegalArgumentException if o cannot be added to the backing
1114         *         list for some other reason.
1115         */
1116        public void add(int index, E o)
1117        {
1118          synchronized (backingList)
1119          {
1120            checkMod();
1121            checkBoundsInclusive(index);
1122    
1123            backingList.add(index + offset, o);
1124    
1125            this.data = backingList.data;
1126            size++;
1127          }
1128        }
1129    
1130        /**
1131         * Specified by AbstractList.subList to delegate to the backing list.
1132         *
1133         * @param index the index to remove
1134         * @return the removed object
1135         * @throws ConcurrentModificationException if the backing list has been
1136         *         modified externally to this sublist
1137         * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt;= size()
1138         * @throws UnsupportedOperationException if the backing list does not
1139         *         support the remove operation
1140         */
1141        public E remove(int index)
1142        {
1143          synchronized (backingList)
1144          {
1145            checkMod();
1146            checkBoundsExclusive(index);
1147            E o = backingList.remove(index + offset);
1148    
1149            this.data = backingList.data;
1150            size--;
1151    
1152            return o;
1153          }
1154        }
1155    
1156        /**
1157         * Specified by AbstractList.subList to delegate to the backing list.
1158         *
1159         * @param index the location to insert at
1160         * @param c the collection to insert
1161         * @return true if this list was modified, in other words, c is non-empty
1162         * @throws ConcurrentModificationException if the backing list has been
1163         *         modified externally to this sublist
1164         * @throws IndexOutOfBoundsException if index &lt; 0 || index &gt; size()
1165         * @throws UnsupportedOperationException if this list does not support the
1166         *         addAll operation
1167         * @throws ClassCastException if some element of c cannot be added to this
1168         *         list due to its type
1169         * @throws IllegalArgumentException if some element of c cannot be added
1170         *         to this list for some other reason
1171         * @throws NullPointerException if the specified collection is null
1172         */
1173        public boolean addAll(int index, Collection<? extends E> c)
1174        {
1175          synchronized (backingList)
1176          {
1177            checkMod();
1178            checkBoundsInclusive(index);
1179            int csize = c.size();
1180            boolean result = backingList.addAll(offset + index, c);
1181    
1182            this.data = backingList.data;
1183            size += csize;
1184    
1185            return result;
1186          }
1187        }
1188    
1189        /**
1190         * Specified by AbstractList.subList to return addAll(size, c).
1191         *
1192         * @param c the collection to insert
1193         * @return true if this list was modified, in other words, c is non-empty
1194         * @throws ConcurrentModificationException if the backing list has been
1195         *         modified externally to this sublist
1196         * @throws UnsupportedOperationException if this list does not support the
1197         *         addAll operation
1198         * @throws ClassCastException if some element of c cannot be added to this
1199         *         list due to its type
1200         * @throws IllegalArgumentException if some element of c cannot be added
1201         *         to this list for some other reason
1202         * @throws NullPointerException if the specified collection is null
1203         */
1204        public boolean addAll(Collection<? extends E> c)
1205        {
1206          synchronized (backingList)
1207          {
1208            return addAll(size, c);
1209          }
1210        }
1211    
1212        /**
1213         * Specified by AbstractList.subList to return listIterator().
1214         *
1215         * @return an iterator over the sublist
1216         */
1217        public Iterator<E> iterator()
1218        {
1219          return listIterator();
1220        }
1221    
1222        /**
1223         * Specified by AbstractList.subList to return a wrapper around the
1224         * backing list's iterator.
1225         *
1226         * @param index the start location of the iterator
1227         * @return a list iterator over the sublist
1228         * @throws ConcurrentModificationException if the backing list has been
1229         *         modified externally to this sublist
1230         * @throws IndexOutOfBoundsException if the value is out of range
1231         */
1232        public ListIterator<E> listIterator(final int index)
1233        {
1234          checkMod();
1235          checkBoundsInclusive(index);
1236    
1237          return new ListIterator<E>()
1238          {
1239            private final ListIterator<E> i =
1240              backingList.listIterator(index + offset);
1241            private int position = index;
1242    
1243            /**
1244             * Tests to see if there are any more objects to
1245             * return.
1246             *
1247             * @return True if the end of the list has not yet been
1248             *         reached.
1249             */
1250            public boolean hasNext()
1251            {
1252              return position < size;
1253            }
1254    
1255            /**
1256             * Tests to see if there are objects prior to the
1257             * current position in the list.
1258             *
1259             * @return True if objects exist prior to the current
1260             *         position of the iterator.
1261             */
1262            public boolean hasPrevious()
1263            {
1264              return position > 0;
1265            }
1266    
1267            /**
1268             * Retrieves the next object from the list.
1269             *
1270             * @return The next object.
1271             * @throws NoSuchElementException if there are no
1272             *         more objects to retrieve.
1273             * @throws ConcurrentModificationException if the
1274             *         list has been modified elsewhere.
1275             */
1276            public E next()
1277            {
1278              if (position == size)
1279                throw new NoSuchElementException();
1280              position++;
1281              return i.next();
1282            }
1283    
1284            /**
1285             * Retrieves the previous object from the list.
1286             *
1287             * @return The next object.
1288             * @throws NoSuchElementException if there are no
1289             *         previous objects to retrieve.
1290             * @throws ConcurrentModificationException if the
1291             *         list has been modified elsewhere.
1292             */
1293            public E previous()
1294            {
1295              if (position == 0)
1296                throw new NoSuchElementException();
1297              position--;
1298              return i.previous();
1299            }
1300    
1301            /**
1302             * Returns the index of the next element in the
1303             * list, which will be retrieved by <code>next()</code>
1304             *
1305             * @return The index of the next element.
1306             */
1307            public int nextIndex()
1308            {
1309              return i.nextIndex() - offset;
1310            }
1311    
1312            /**
1313             * Returns the index of the previous element in the
1314             * list, which will be retrieved by <code>previous()</code>
1315             *
1316             * @return The index of the previous element.
1317             */
1318            public int previousIndex()
1319            {
1320              return i.previousIndex() - offset;
1321            }
1322    
1323            /**
1324             * Removes the last object retrieved by <code>next()</code>
1325             * from the list, if the list supports object removal.
1326             *
1327             * @throws IllegalStateException if the iterator is positioned
1328             *         before the start of the list or the last object has already
1329             *         been removed.
1330             * @throws UnsupportedOperationException if the list does
1331             *         not support removing elements.
1332             */
1333            public void remove()
1334            {
1335              throw new UnsupportedOperationException("Modification not supported " +
1336                  "on CopyOnWriteArrayList iterators");
1337            }
1338    
1339            /**
1340             * Replaces the last object retrieved by <code>next()</code>
1341             * or <code>previous</code> with o, if the list supports object
1342             * replacement and an add or remove operation has not already
1343             * been performed.
1344             *
1345             * @throws IllegalStateException if the iterator is positioned
1346             *         before the start of the list or the last object has already
1347             *         been removed.
1348             * @throws UnsupportedOperationException if the list doesn't support
1349             *         the addition or removal of elements.
1350             * @throws ClassCastException if the type of o is not a valid type
1351             *         for this list.
1352             * @throws IllegalArgumentException if something else related to o
1353             *         prevents its addition.
1354             * @throws ConcurrentModificationException if the list
1355             *         has been modified elsewhere.
1356             */
1357            public void set(E o)
1358            {
1359              throw new UnsupportedOperationException("Modification not supported " +
1360                  "on CopyOnWriteArrayList iterators");
1361            }
1362    
1363            /**
1364             * Adds the supplied object before the element that would be returned
1365             * by a call to <code>next()</code>, if the list supports addition.
1366             *
1367             * @param o The object to add to the list.
1368             * @throws UnsupportedOperationException if the list doesn't support
1369             *         the addition of new elements.
1370             * @throws ClassCastException if the type of o is not a valid type
1371             *         for this list.
1372             * @throws IllegalArgumentException if something else related to o
1373             *         prevents its addition.
1374             * @throws ConcurrentModificationException if the list
1375             *         has been modified elsewhere.
1376             */
1377            public void add(E o)
1378            {
1379              throw new UnsupportedOperationException("Modification not supported " +
1380                  "on CopyOnWriteArrayList iterators");
1381            }
1382          };
1383        }
1384      } // class SubList
1385    
1386      /**
1387       * This class is a RandomAccess version of SubList, as required by
1388       * {@link AbstractList#subList(int, int)}.
1389       *
1390       * @author Eric Blake (ebb9@email.byu.edu)
1391       */
1392      private static final class RandomAccessSubList<E> extends SubList<E>
1393        implements RandomAccess
1394      {
1395        /**
1396         * Construct the sublist.
1397         *
1398         * @param backing the list this comes from
1399         * @param fromIndex the lower bound, inclusive
1400         * @param toIndex the upper bound, exclusive
1401         */
1402        RandomAccessSubList(CopyOnWriteArrayList<E> backing, int fromIndex, int toIndex)
1403        {
1404          super(backing, fromIndex, toIndex);
1405        }
1406      } // class RandomAccessSubList
1407    
1408      /**
1409       * Serializes this object to the given stream.
1410       *
1411       * @param s
1412       *          the stream to write to
1413       * @throws IOException
1414       *           if the underlying stream fails
1415       * @serialData the size field (int), the length of the backing array (int),
1416       *             followed by its elements (Objects) in proper order.
1417       */
1418      private void writeObject(ObjectOutputStream s) throws IOException
1419      {
1420        // The 'size' field.
1421        s.defaultWriteObject();
1422        // We serialize unused list entries to preserve capacity.
1423        int len = data.length;
1424        s.writeInt(len);
1425        // it would be more efficient to just write "size" items,
1426        // this need readObject read "size" items too.
1427        for (int i = 0; i < data.length; i++)
1428          s.writeObject(data[i]);
1429      }
1430    
1431      /**
1432       * Deserializes this object from the given stream.
1433       *
1434       * @param s
1435       *          the stream to read from
1436       * @throws ClassNotFoundException
1437       *           if the underlying stream fails
1438       * @throws IOException
1439       *           if the underlying stream fails
1440       * @serialData the size field (int), the length of the backing array (int),
1441       *             followed by its elements (Objects) in proper order.
1442       */
1443      private void readObject(ObjectInputStream s) throws IOException,
1444          ClassNotFoundException
1445      {
1446        // the `size' field.
1447        s.defaultReadObject();
1448        int capacity = s.readInt();
1449        data = (E[]) new Object[capacity];
1450        for (int i = 0; i < capacity; i++)
1451          data[i] = (E) s.readObject();
1452      }
1453    
1454      static final boolean equals(Object o1, Object o2)
1455      {
1456        return o1 == null ? o2 == null : o1.equals(o2);
1457      }
1458    
1459      Object[] getArray()
1460      {
1461        return data;
1462      }
1463    }