1: /* AbstractCollection.java -- Abstract implementation of most of Collection 2: Copyright (C) 1998, 2000, 2001, 2004, 2005 Free Software Foundation, Inc. 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: 39: package java.util; 40: 41: import java.lang.reflect.Array; 42: 43: /** 44: * A basic implementation of most of the methods in the Collection interface to 45: * make it easier to create a collection. To create an unmodifiable Collection, 46: * just subclass AbstractCollection and provide implementations of the 47: * iterator() and size() methods. The Iterator returned by iterator() need only 48: * provide implementations of hasNext() and next() (that is, it may throw an 49: * UnsupportedOperationException if remove() is called). To create a modifiable 50: * Collection, you must in addition provide an implementation of the 51: * add(Object) method and the Iterator returned by iterator() must provide an 52: * implementation of remove(). Other methods should be overridden if the 53: * backing data structure allows for a more efficient implementation. The 54: * precise implementation used by AbstractCollection is documented, so that 55: * subclasses can tell which methods could be implemented more efficiently. 56: * <p> 57: * 58: * The programmer should provide a no-argument constructor, and one that 59: * accepts another Collection, as recommended by the Collection interface. 60: * Unfortunately, there is no way to enforce this in Java. 61: * 62: * @author Original author unknown 63: * @author Bryce McKinlay 64: * @author Eric Blake (ebb9@email.byu.edu) 65: * @author Tom Tromey (tromey@redhat.com) 66: * @author Andrew John Hughes (gnu_andrew@member.fsf.org) 67: * @see Collection 68: * @see AbstractSet 69: * @see AbstractList 70: * @since 1.2 71: * @status updated to 1.4 72: */ 73: public abstract class AbstractCollection<E> 74: implements Collection<E>, Iterable<E> 75: { 76: /** 77: * The main constructor, for use by subclasses. 78: */ 79: protected AbstractCollection() 80: { 81: } 82: 83: /** 84: * Return an Iterator over this collection. The iterator must provide the 85: * hasNext and next methods and should in addition provide remove if the 86: * collection is modifiable. 87: * 88: * @return an iterator 89: */ 90: public abstract Iterator<E> iterator(); 91: 92: /** 93: * Return the number of elements in this collection. If there are more than 94: * Integer.MAX_VALUE elements, return Integer.MAX_VALUE. 95: * 96: * @return the size 97: */ 98: public abstract int size(); 99: 100: /** 101: * Add an object to the collection (optional operation). This implementation 102: * always throws an UnsupportedOperationException - it should be 103: * overridden if the collection is to be modifiable. If the collection 104: * does not accept duplicates, simply return false. Collections may specify 105: * limitations on what may be added. 106: * 107: * @param o the object to add 108: * @return true if the add operation caused the Collection to change 109: * @throws UnsupportedOperationException if the add operation is not 110: * supported on this collection 111: * @throws NullPointerException if the collection does not support null 112: * @throws ClassCastException if the object is of the wrong type 113: * @throws IllegalArgumentException if some aspect of the object prevents 114: * it from being added 115: */ 116: public boolean add(E o) 117: { 118: throw new UnsupportedOperationException(); 119: } 120: 121: /** 122: * Add all the elements of a given collection to this collection (optional 123: * operation). This implementation obtains an Iterator over the given 124: * collection and iterates over it, adding each element with the 125: * add(Object) method (thus this method will fail with an 126: * UnsupportedOperationException if the add method does). The behavior is 127: * unspecified if the specified collection is modified during the iteration, 128: * including the special case of trying addAll(this) on a non-empty 129: * collection. 130: * 131: * @param c the collection to add the elements of to this collection 132: * @return true if the add operation caused the Collection to change 133: * @throws UnsupportedOperationException if the add operation is not 134: * supported on this collection 135: * @throws NullPointerException if the specified collection is null 136: * @throws ClassCastException if the type of any element in c is 137: * not a valid type for addition. 138: * @throws IllegalArgumentException if some aspect of any element 139: * in c prevents it being added. 140: * @throws NullPointerException if any element in c is null and this 141: * collection doesn't allow null values. 142: * @see #add(Object) 143: */ 144: public boolean addAll(Collection<? extends E> c) 145: { 146: Iterator<? extends E> itr = c.iterator(); 147: boolean modified = false; 148: int pos = c.size(); 149: while (--pos >= 0) 150: modified |= add(itr.next()); 151: return modified; 152: } 153: 154: /** 155: * Remove all elements from the collection (optional operation). This 156: * implementation obtains an iterator over the collection and calls next 157: * and remove on it repeatedly (thus this method will fail with an 158: * UnsupportedOperationException if the Iterator's remove method does) 159: * until there are no more elements to remove. 160: * Many implementations will have a faster way of doing this. 161: * 162: * @throws UnsupportedOperationException if the Iterator returned by 163: * iterator does not provide an implementation of remove 164: * @see Iterator#remove() 165: */ 166: public void clear() 167: { 168: Iterator<E> itr = iterator(); 169: int pos = size(); 170: while (--pos >= 0) 171: { 172: itr.next(); 173: itr.remove(); 174: } 175: } 176: 177: /** 178: * Test whether this collection contains a given object. That is, if the 179: * collection has an element e such that (o == null ? e == null : 180: * o.equals(e)). This implementation obtains an iterator over the collection 181: * and iterates over it, testing each element for equality with the given 182: * object. If it is equal, true is returned. Otherwise false is returned when 183: * the end of the collection is reached. 184: * 185: * @param o the object to remove from this collection 186: * @return true if this collection contains an object equal to o 187: */ 188: public boolean contains(Object o) 189: { 190: Iterator<E> itr = iterator(); 191: int pos = size(); 192: while (--pos >= 0) 193: if (equals(o, itr.next())) 194: return true; 195: return false; 196: } 197: 198: /** 199: * Tests whether this collection contains all the elements in a given 200: * collection. This implementation iterates over the given collection, 201: * testing whether each element is contained in this collection. If any one 202: * is not, false is returned. Otherwise true is returned. 203: * 204: * @param c the collection to test against 205: * @return true if this collection contains all the elements in the given 206: * collection 207: * @throws NullPointerException if the given collection is null 208: * @see #contains(Object) 209: */ 210: public boolean containsAll(Collection<?> c) 211: { 212: Iterator<?> itr = c.iterator(); 213: int pos = c.size(); 214: while (--pos >= 0) 215: if (!contains(itr.next())) 216: return false; 217: return true; 218: } 219: 220: /** 221: * Test whether this collection is empty. This implementation returns 222: * size() == 0. 223: * 224: * @return true if this collection is empty. 225: * @see #size() 226: */ 227: public boolean isEmpty() 228: { 229: return size() == 0; 230: } 231: 232: /** 233: * Remove a single instance of an object from this collection (optional 234: * operation). That is, remove one element e such that 235: * <code>(o == null ? e == null : o.equals(e))</code>, if such an element 236: * exists. This implementation obtains an iterator over the collection 237: * and iterates over it, testing each element for equality with the given 238: * object. If it is equal, it is removed by the iterator's remove method 239: * (thus this method will fail with an UnsupportedOperationException if 240: * the Iterator's remove method does). After the first element has been 241: * removed, true is returned; if the end of the collection is reached, false 242: * is returned. 243: * 244: * @param o the object to remove from this collection 245: * @return true if the remove operation caused the Collection to change, or 246: * equivalently if the collection did contain o. 247: * @throws UnsupportedOperationException if this collection's Iterator 248: * does not support the remove method 249: * @see Iterator#remove() 250: */ 251: public boolean remove(Object o) 252: { 253: Iterator<E> itr = iterator(); 254: int pos = size(); 255: while (--pos >= 0) 256: if (equals(o, itr.next())) 257: { 258: itr.remove(); 259: return true; 260: } 261: return false; 262: } 263: 264: /** 265: * Remove from this collection all its elements that are contained in a given 266: * collection (optional operation). This implementation iterates over this 267: * collection, and for each element tests if it is contained in the given 268: * collection. If so, it is removed by the Iterator's remove method (thus 269: * this method will fail with an UnsupportedOperationException if the 270: * Iterator's remove method does). 271: * 272: * @param c the collection to remove the elements of 273: * @return true if the remove operation caused the Collection to change 274: * @throws UnsupportedOperationException if this collection's Iterator 275: * does not support the remove method 276: * @throws NullPointerException if the collection, c, is null. 277: * @see Iterator#remove() 278: */ 279: public boolean removeAll(Collection<?> c) 280: { 281: return removeAllInternal(c); 282: } 283: 284: /** 285: * Remove from this collection all its elements that are contained in a given 286: * collection (optional operation). This implementation iterates over this 287: * collection, and for each element tests if it is contained in the given 288: * collection. If so, it is removed by the Iterator's remove method (thus 289: * this method will fail with an UnsupportedOperationException if the 290: * Iterator's remove method does). This method is necessary for ArrayList, 291: * which cannot publicly override removeAll but can optimize this call. 292: * 293: * @param c the collection to remove the elements of 294: * @return true if the remove operation caused the Collection to change 295: * @throws UnsupportedOperationException if this collection's Iterator 296: * does not support the remove method 297: * @throws NullPointerException if the collection, c, is null. 298: * @see Iterator#remove() 299: */ 300: // Package visible for use throughout java.util. 301: boolean removeAllInternal(Collection<?> c) 302: { 303: Iterator<E> itr = iterator(); 304: boolean modified = false; 305: int pos = size(); 306: while (--pos >= 0) 307: if (c.contains(itr.next())) 308: { 309: itr.remove(); 310: modified = true; 311: } 312: return modified; 313: } 314: 315: /** 316: * Remove from this collection all its elements that are not contained in a 317: * given collection (optional operation). This implementation iterates over 318: * this collection, and for each element tests if it is contained in the 319: * given collection. If not, it is removed by the Iterator's remove method 320: * (thus this method will fail with an UnsupportedOperationException if 321: * the Iterator's remove method does). 322: * 323: * @param c the collection to retain the elements of 324: * @return true if the remove operation caused the Collection to change 325: * @throws UnsupportedOperationException if this collection's Iterator 326: * does not support the remove method 327: * @throws NullPointerException if the collection, c, is null. 328: * @see Iterator#remove() 329: */ 330: public boolean retainAll(Collection<?> c) 331: { 332: return retainAllInternal(c); 333: } 334: 335: /** 336: * Remove from this collection all its elements that are not contained in a 337: * given collection (optional operation). This implementation iterates over 338: * this collection, and for each element tests if it is contained in the 339: * given collection. If not, it is removed by the Iterator's remove method 340: * (thus this method will fail with an UnsupportedOperationException if 341: * the Iterator's remove method does). This method is necessary for 342: * ArrayList, which cannot publicly override retainAll but can optimize 343: * this call. 344: * 345: * @param c the collection to retain the elements of 346: * @return true if the remove operation caused the Collection to change 347: * @throws UnsupportedOperationException if this collection's Iterator 348: * does not support the remove method 349: * @throws NullPointerException if the collection, c, is null. 350: * @see Iterator#remove() 351: */ 352: // Package visible for use throughout java.util. 353: boolean retainAllInternal(Collection<?> c) 354: { 355: Iterator<E> itr = iterator(); 356: boolean modified = false; 357: int pos = size(); 358: while (--pos >= 0) 359: if (!c.contains(itr.next())) 360: { 361: itr.remove(); 362: modified = true; 363: } 364: return modified; 365: } 366: 367: /** 368: * Return an array containing the elements of this collection. This 369: * implementation creates an Object array of size size() and then iterates 370: * over the collection, setting each element of the array from the value 371: * returned by the iterator. The returned array is safe, and is not backed 372: * by the collection. 373: * 374: * @return an array containing the elements of this collection 375: */ 376: public Object[] toArray() 377: { 378: Iterator<E> itr = iterator(); 379: int size = size(); 380: Object[] a = new Object[size]; 381: for (int pos = 0; pos < size; pos++) 382: a[pos] = itr.next(); 383: return a; 384: } 385: 386: /** 387: * Copy the collection into a given array if it will fit, or into a 388: * dynamically created array of the same run-time type as the given array if 389: * not. If there is space remaining in the array, the first element after the 390: * end of the collection is set to null (this is only useful if the 391: * collection is known to contain no null elements, however). This 392: * implementation first tests whether the given array is large enough to hold 393: * all the elements of the collection. If not, the reflection API is used to 394: * allocate a new array of the same run-time type. Next an iterator is 395: * obtained over the collection and the elements are placed in the array as 396: * they are returned by the iterator. Finally the first spare element, if 397: * any, of the array is set to null, and the created array is returned. 398: * The returned array is safe; it is not backed by the collection. Note that 399: * null may not mark the last element, if the collection allows null 400: * elements. 401: * 402: * @param a the array to copy into, or of the correct run-time type 403: * @return the array that was produced 404: * @throws NullPointerException if the given array is null 405: * @throws ArrayStoreException if the type of the array precludes holding 406: * one of the elements of the Collection 407: */ 408: public <T> T[] toArray(T[] a) 409: { 410: int size = size(); 411: if (a.length < size) 412: a = (T[]) Array.newInstance(a.getClass().getComponentType(), 413: size); 414: else if (a.length > size) 415: a[size] = null; 416: 417: Iterator<E> itr = iterator(); 418: for (int pos = 0; pos < size; pos++) 419: a[pos] = (T) (itr.next()); 420: return a; 421: } 422: 423: /** 424: * Creates a String representation of the Collection. The string returned is 425: * of the form "[a, b, ...]" where a and b etc are the results of calling 426: * toString on the elements of the collection. This implementation obtains an 427: * Iterator over the Collection and adds each element to a StringBuffer as it 428: * is returned by the iterator. "<this>" is inserted when the collection 429: * contains itself (only works for direct containment, not for collections 430: * inside collections). 431: * 432: * @return a String representation of the Collection 433: */ 434: public String toString() 435: { 436: Iterator itr = iterator(); 437: StringBuffer r = new StringBuffer("["); 438: boolean hasNext = itr.hasNext(); 439: while (hasNext) 440: { 441: Object o = itr.next(); 442: if (o == this) 443: r.append("<this>"); 444: else 445: r.append(o); 446: hasNext = itr.hasNext(); 447: if (hasNext) 448: r.append(", "); 449: } 450: r.append("]"); 451: return r.toString(); 452: } 453: 454: /** 455: * Compare two objects according to Collection semantics. 456: * 457: * @param o1 the first object 458: * @param o2 the second object 459: * @return o1 == null ? o2 == null : o1.equals(o2) 460: */ 461: // Package visible for use throughout java.util. 462: // It may be inlined since it is final. 463: static final boolean equals(Object o1, Object o2) 464: { 465: return o1 == null ? o2 == null : o1.equals(o2); 466: } 467: 468: /** 469: * Hash an object according to Collection semantics. 470: * 471: * @param o the object to hash 472: * @return o1 == null ? 0 : o1.hashCode() 473: */ 474: // Package visible for use throughout java.util. 475: // It may be inlined since it is final. 476: static final int hashCode(Object o) 477: { 478: return o == null ? 0 : o.hashCode(); 479: } 480: }