Source for java.util.AbstractCollection

   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: }