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