GNU Classpath (0.97.2) | |
Frames | No Frames |
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 < 0 || index >= 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 < 0 || index >= 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 < 0 || index > 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 < 0 || index >= 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 < 0 || index > 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 < 0 912: * || toIndex > size() 913: * @throws IndexOutOfBoundsException if fromIndex > 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 < 0 || index > 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 < 0 || index >= 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 < 0 || index >= 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 < 0 || index >= 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 < 0 || index > 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 < 0 || index >= 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 < 0 || index > 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: }
GNU Classpath (0.97.2) |