libjava/java/util/AbstractCollection.java

   1 /* AbstractCollection.java -- Abstract implementation of most of Collection
   2    Copyright (C) 1998 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 As a special exception, if you link this library with other files to
  22 produce an executable, this library does not by itself cause the
  23 resulting executable to be covered by the GNU General Public License.
  24 This exception does not however invalidate any other reasons why the
  25 executable file might be covered by the GNU General Public License. */
  26
  27
  28 package java.util;
  29
  30 import java.lang.reflect.Array;
  31
  32 /**
  33  * A basic implementation of most of the methods in the Collection interface to
  34  * make it easier to create a collection. To create an unmodifiable Collection,
  35  * just subclass AbstractCollection and provide implementations of the
  36  * iterator() and size() methods. The Iterator returned by iterator() need only
  37  * provide implementations of hasNext() and next() (that is, it may throw an
  38  * UnsupportedOperationException if remove() is called). To create a modifiable
  39  * Collection, you must in addition provide an implementation of the
  40  * add(Object) method and the Iterator returned by iterator() must provide an
  41  * implementation of remove(). Other methods should be overridden if the
  42  * backing data structure allows for a more efficient implementation. The
  43  * precise implementation used by AbstractCollection is documented, so that
  44  * subclasses can tell which methods could be implemented more efficiently.
  45  */
  46 public abstract class AbstractCollection implements Collection {
  47
  48   /**
  49    * Return an Iterator over this collection. The iterator must provide the
  50    * hasNext and next methods and should in addition provide remove if the
  51    * collection is modifiable.
  52    */
  53   public abstract Iterator iterator();
  54
  55   /**
  56    * Return the number of elements in this collection.
  57    */
  58   public abstract int size();
  59
  60   /**
  61    * Add an object to the collection. This implementation always throws an
  62    * UnsupportedOperationException - it should be overridden if the collection
  63    * is to be modifiable.
  64    *
  65    * @param o the object to add
  66    * @return true if the add operation caused the Collection to change
  67    * @exception UnsupportedOperationException if the add operation is not
  68    *   supported on this collection
  69    */
  70   public boolean add(Object o) {
  71     throw new java.lang.UnsupportedOperationException();
  72   }
  73
  74   /**
  75    * Add all the elements of a given collection to this collection. This
  76    * implementation obtains an Iterator over the given collection and iterates
  77    * over it, adding each element with the add(Object) method (thus this method
  78    * will fail with an UnsupportedOperationException if the add method does).
  79    *
  80    * @param c the collection to add the elements of to this collection
  81    * @return true if the add operation caused the Collection to change
  82    * @exception UnsupportedOperationException if the add operation is not
  83    *   supported on this collection
  84    */
  85   public boolean addAll(Collection c) {
  86     Iterator i = c.iterator();
  87     boolean modified = false;
  88     while (i.hasNext()) {
  89       modified |= add(i.next());
  90     }
  91     return modified;
  92   }
  93
  94   /**
  95    * Remove all elements from the collection. This implementation obtains an
  96    * iterator over the collection and calls next and remove on it repeatedly
  97    * (thus this method will fail with an UnsupportedOperationException if the
  98    * Iterator's remove method does) until there are no more elements to remove.
  99    * Many implementations will have a faster way of doing this.
 100    *
 101    * @exception UnsupportedOperationException if the Iterator returned by
 102    *   iterator does not provide an implementation of remove
 103    */
 104   public void clear() {
 105     Iterator i = iterator();
 106     while (i.hasNext()) {
 107       i.next();
 108       i.remove();
 109     }
 110   }
 111
 112   /**
 113    * Test whether this collection contains a given object. That is, if the
 114    * collection has an element e such that (o == null ? e == null :
 115    * o.equals(e)). This implementation obtains an iterator over the collection
 116    * and iterates over it, testing each element for equality with the given
 117    * object. If it is equal, true is returned. Otherwise false is returned when
 118    * the end of the collection is reached.
 119    *
 120    * @param o the object to remove from this collection
 121    * @return true if this collection contains an object equal to o
 122    */
 123   public boolean contains(Object o) {
 124     Iterator i = iterator();
 125
 126     // This looks crazily inefficient, but it takes the test o==null outside
 127     // the loop, saving time, and also saves needing to store the result of
 128     // i.next() each time.
 129     if (o == null) {
 130       while (i.hasNext()) {
 131         if (i.next() == null) {
 132           return true;
 133         }
 134       }
 135     } else {
 136       while (i.hasNext()) {
 137         if (o.equals(i.next())) {
 138           return true;
 139         }
 140       }
 141     }
 142     return false;
 143   }
 144
 145   /**
 146    * Tests whether this collection contains all the elements in a given
 147    * collection. This implementation iterates over the given collection,
 148    * testing whether each element is contained in this collection. If any one
 149    * is not, false is returned. Otherwise true is returned.
 150    *
 151    * @param c the collection to test against
 152    * @return true if this collection contains all the elements in the given
 153    *   collection
 154    */
 155   public boolean containsAll(Collection c) {
 156     Iterator i = c.iterator();
 157     while (i.hasNext()) {
 158       if (!contains(i.next())) {
 159         return false;
 160       }
 161     }
 162     return true;
 163   }
 164
 165   /**
 166    * Test whether this collection is empty. This implementation returns
 167    * size() == 0.
 168    *
 169    * @return true if this collection is empty.
 170    */
 171   public boolean isEmpty() {
 172     return size() == 0;
 173   }
 174
 175   /**
 176    * Remove a single instance of an object from this collection. That is,
 177    * remove one element e such that (o == null ? e == null : o.equals(e)), if
 178    * such an element exists. This implementation obtains an iterator over the
 179    * collection and iterates over it, testing each element for equality with
 180    * the given object. If it is equal, it is removed by the iterator's remove
 181    * method (thus this method will fail with an UnsupportedOperationException
 182    * if the Iterator's remove method does). After the first element has been
 183    * removed, true is returned; if the end of the collection is reached, false
 184    * is returned.
 185    *
 186    * @param o the object to remove from this collection
 187    * @return true if the remove operation caused the Collection to change, or
 188    *   equivalently if the collection did contain o.
 189    * @exception UnsupportedOperationException if this collection's Iterator
 190    *   does not support the remove method
 191    */
 192   public boolean remove(Object o) {
 193     Iterator i = iterator();
 194
 195     // This looks crazily inefficient, but it takes the test o==null outside
 196     // the loop, saving time, and also saves needing to store the result of
 197     // i.next() each time.
 198     if (o == null) {
 199       while (i.hasNext()) {
 200         if (i.next() == null) {
 201           i.remove();
 202           return true;
 203         }
 204       }
 205     } else {
 206       while (i.hasNext()) {
 207         if (o.equals(i.next())) {
 208           i.remove();
 209           return true;
 210         }
 211       }
 212     }
 213     return false;
 214   }
 215
 216   /**
 217    * Remove from this collection all its elements that are contained in a given
 218    * collection. This implementation iterates over this collection, and for
 219    * each element tests if it is contained in the given collection. If so, it
 220    * is removed by the Iterator's remove method (thus this method will fail
 221    * with an UnsupportedOperationException if the Iterator's remove method
 222    * does).
 223    *
 224    * @param c the collection to remove the elements of
 225    * @return true if the remove operation caused the Collection to change
 226    * @exception UnsupportedOperationException if this collection's Iterator
 227    *   does not support the remove method
 228    */
 229   public boolean removeAll(Collection c) {
 230     Iterator i = iterator();
 231     boolean changed = false;
 232     while (i.hasNext()) {
 233       if (c.contains(i.next())) {
 234         i.remove();
 235         changed = true;
 236       }
 237     }
 238     return changed;
 239   }
 240
 241   /**
 242    * Remove from this collection all its elements that are not contained in a
 243    * given collection. This implementation iterates over this collection, and
 244    * for each element tests if it is contained in the given collection. If not,
 245    * it is removed by the Iterator's remove method (thus this method will fail
 246    * with an UnsupportedOperationException if the Iterator's remove method
 247    * does).
 248    *
 249    * @param c the collection to retain the elements of
 250    * @return true if the remove operation caused the Collection to change
 251    * @exception UnsupportedOperationException if this collection's Iterator
 252    *   does not support the remove method
 253    */
 254   public boolean retainAll(Collection c) {
 255     Iterator i = iterator();
 256     boolean changed = false;
 257     while (i.hasNext()) {
 258       if (!c.contains(i.next())) {
 259         i.remove();
 260         changed = true;
 261       }
 262     }
 263     return changed;
 264   }
 265
 266   /**
 267    * Return an array containing the elements of this collection. This
 268    * implementation creates an Object array of size size() and then iterates
 269    * over the collection, setting each element of the array from the value
 270    * returned by the iterator.
 271    *
 272    * @return an array containing the elements of this collection
 273    */
 274   public Object[] toArray() {
 275     Object[] a = new Object[size()];
 276     Iterator i = iterator();
 277     for (int pos = 0; pos < a.length; pos++) {
 278       a[pos] = i.next();
 279     }
 280     return a;
 281   }
 282
 283   /**
 284    * Copy the collection into a given array if it will fit, or into a
 285    * dynamically created array of the same run-time type as the given array if
 286    * not. If there is space remaining in the array, the first element after the
 287    * end of the collection is set to null (this is only useful if the
 288    * collection is known to contain no null elements, however). This
 289    * implementation first tests whether the given array is large enough to hold
 290    * all the elements of the collection. If not, the reflection API is used to
 291    * allocate a new array of the same run-time type. Next an iterator is
 292    * obtained over the collection and the elements are placed in the array as
 293    * they are returned by the iterator. Finally the first spare element, if
 294    * any, of the array is set to null, and the created array is returned.
 295    *
 296    * @param a the array to copy into, or of the correct run-time type
 297    * @return the array that was produced
 298    * @exception ClassCastException if the type of the array precludes holding
 299    *   one of the elements of the Collection
 300    */
 301   public Object[] toArray(Object[] a) {
 302     final int n = size();
 303     if (a.length < n) {
 304       a = (Object[])Array.newInstance(a.getClass().getComponentType(), n);
 305     }
 306     Iterator i = iterator();
 307     for (int pos = 0; pos < n; pos++) {
 308       a[pos] = i.next();
 309     }
 310     if (a.length > n) {
 311       a[n] = null;
 312     }
 313     return a;
 314   }
 315
 316   /**
 317    * Creates a String representation of the Collection. The string returned is
 318    * of the form "[a, b, ...]" where a and b etc are the results of calling
 319    * toString on the elements of the collection. This implementation obtains an
 320    * Iterator over the Collection and adds each element to a StringBuffer as it
 321    * is returned by the iterator.
 322    *
 323    * @return a String representation of the Collection
 324    */
 325   public String toString() {
 326     StringBuffer s = new StringBuffer();
 327     s.append('[');
 328     Iterator i = iterator();
 329     boolean more = i.hasNext();
 330     while(more) {
 331       s.append(i.next());
 332       if (more = i.hasNext()) {
 333         s.append(", ");
 334       }
 335     }
 336     s.append(']');
 337     return s.toString();
 338   }
 339 }