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