libjava/java/util/AbstractCollection.java

   1 /* AbstractCollection.java -- Abstract implementation of most of Collection
   2    Copyright (C) 1998, 2000, 2001 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., 59 Temple Place, Suite 330, Boston, MA
  19 02111-1307 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 }