Source for java.util.AbstractCollection

   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.
 427:    *
 428:    * @return a String representation of the Collection
 429:    */
 430:   public String toString()
 431:   {
 432:     Iterator itr = iterator();
 433:     StringBuffer r = new StringBuffer("[");
 434:     for (int pos = size(); pos > 0; pos--)
 435:       {
 436:         r.append(itr.next());
 437:         if (pos > 1)
 438:           r.append(", ");
 439:       }
 440:     r.append("]");
 441:     return r.toString();
 442:   }
 443: 
 444:   /**
 445:    * Compare two objects according to Collection semantics.
 446:    *
 447:    * @param o1 the first object
 448:    * @param o2 the second object
 449:    * @return o1 == null ? o2 == null : o1.equals(o2)
 450:    */
 451:   // Package visible for use throughout java.util.
 452:   // It may be inlined since it is final.
 453:   static final boolean equals(Object o1, Object o2)
 454:   {
 455:     return o1 == null ? o2 == null : o1.equals(o2);
 456:   }
 457: 
 458:   /**
 459:    * Hash an object according to Collection semantics.
 460:    *
 461:    * @param o the object to hash
 462:    * @return o1 == null ? 0 : o1.hashCode()
 463:    */
 464:   // Package visible for use throughout java.util.
 465:   // It may be inlined since it is final.
 466:   static final int hashCode(Object o)
 467:   {
 468:     return o == null ? 0 : o.hashCode();
 469:   }
 470: }