libjava/classpath/java/util/AbstractCollection.java

   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 }