Source for java.util.concurrent.CopyOnWriteArrayList

   1: /* CopyOnWriteArrayList.java
   2:    Copyright (C) 2006 Free Software Foundation
   3: 
   4: This file is part of GNU Classpath.
   5: 
   6: GNU Classpath is free software; you can redistribute it and/or modify
   7: it under the terms of the GNU General Public License as published by
   8: the Free Software Foundation; either version 2, or (at your option)
   9: any later version.
  10: 
  11: GNU Classpath is distributed in the hope that it will be useful, but
  12: WITHOUT ANY WARRANTY; without even the implied warranty of
  13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14: General Public License for more details.
  15: 
  16: You should have received a copy of the GNU General Public License
  17: along with GNU Classpath; see the file COPYING.  If not, write to the
  18: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  19: 02110-1301 USA.
  20: 
  21: Linking this library statically or dynamically with other modules is
  22: making a combined work based on this library.  Thus, the terms and
  23: conditions of the GNU General Public License cover the whole
  24: combination.
  25: 
  26: As a special exception, the copyright holders of this library give you
  27: permission to link this library with independent modules to produce an
  28: executable, regardless of the license terms of these independent
  29: modules, and to copy and distribute the resulting executable under
  30: terms of your choice, provided that you also meet, for each linked
  31: independent module, the terms and conditions of the license of that
  32: module.  An independent module is a module which is not derived from
  33: or based on this library.  If you modify this library, you may extend
  34: this exception to your version of the library, but you are not
  35: obligated to do so.  If you do not wish to do so, delete this
  36: exception statement from your version. */
  37: 
  38: package java.util.concurrent;
  39: 
  40: import java.io.IOException;
  41: import java.io.ObjectInputStream;
  42: import java.io.ObjectOutputStream;
  43: import java.io.Serializable;
  44: 
  45: import java.lang.reflect.Array;
  46: 
  47: import java.util.AbstractList;
  48: import java.util.Arrays;
  49: import java.util.Collection;
  50: import java.util.ConcurrentModificationException;
  51: import java.util.Iterator;
  52: import java.util.List;
  53: import java.util.ListIterator;
  54: import java.util.NoSuchElementException;
  55: import java.util.RandomAccess;
  56: 
  57: /**
  58:  * A thread-safe implementation of an ArrayList. A CopyOnWriteArrayList is
  59:  * as special ArrayList which performs copies of the underlying storage
  60:  * each time a write (<code>remove</code>, <code>add</code> etc..) operation
  61:  * is performed.<br />
  62:  * <br />
  63:  * The update operation in this class run usually in <code>O(n)</code> or worse,
  64:  * but traversal operations are fast and efficient, especially when running in
  65:  * a multi-thread environment without the need to design complex synchronize
  66:  * mechanisms.<br />
  67:  * <br />
  68:  * <code>Iterator</code>s in this class work on a snapshot of the backing store
  69:  * at the moment the iterator itself was created, hence the iterator will not
  70:  * reflect changes in the underlying storage. Thus, update operation on the
  71:  * <code>Iterator</code>s are not supported, but as interferences from other
  72:  * threads are impossible, no <code>ConcurrentModificationException</code>
  73:  * will be ever thrown from within the <code>Iterator</code>.
  74:  * <br /><br />
  75:  * This class is especially useful when used with event handling, like the
  76:  * following code demonstrates:<br />
  77:  * <code><pre>
  78:  * 
  79:  * CopyOnWriteArrayList<EventListener> listeners =
  80:  *   new CopyOnWriteArrayList<EventListener>();
  81:  * 
  82:  * [...]
  83:  * 
  84:  * for (final EventListener listener : listeners)
  85:  *   {
  86:  *     Runnable dispatcher = new Runnable() {
  87:  *       public void run()
  88:  *       {
  89:  *         listener.preferenceChange(event);
  90:  *       }
  91:  *     };
  92:  *         
  93:  *     Executor executor = Executors.newSingleThreadExecutor();
  94:  *     executor.execute(dispatcher);
  95:  *   }
  96:  * </pre></code>
  97:  * 
  98:  * @since 1.5
  99:  */
 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 = 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 = 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: }