1 /*
   2  * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package java.util;
  27 
  28 /**
  29  * This class provides a skeletal implementation of the <tt>Collection</tt>
  30  * interface, to minimize the effort required to implement this interface. <p>
  31  *
  32  * To implement an unmodifiable collection, the programmer needs only to
  33  * extend this class and provide implementations for the <tt>iterator</tt> and
  34  * <tt>size</tt> methods.  (The iterator returned by the <tt>iterator</tt>
  35  * method must implement <tt>hasNext</tt> and <tt>next</tt>.)<p>
  36  *
  37  * To implement a modifiable collection, the programmer must additionally
  38  * override this class's <tt>add</tt> method (which otherwise throws an
  39  * <tt>UnsupportedOperationException</tt>), and the iterator returned by the
  40  * <tt>iterator</tt> method must additionally implement its <tt>remove</tt>
  41  * method.<p>
  42  *
  43  * The programmer should generally provide a void (no argument) and
  44  * <tt>Collection</tt> constructor, as per the recommendation in the
  45  * <tt>Collection</tt> interface specification.<p>
  46  *
  47  * The documentation for each non-abstract method in this class describes its
  48  * implementation in detail.  Each of these methods may be overridden if
  49  * the collection being implemented admits a more efficient implementation.<p>
  50  *
  51  * This class is a member of the
  52  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  53  * Java Collections Framework</a>.
  54  *
  55  * @author  Josh Bloch
  56  * @author  Neal Gafter
  57  * @see Collection
  58  * @since 1.2
  59  */
  60 
  61 public abstract class AbstractCollection<E> implements Collection<E> {
  62     /**
  63      * Sole constructor.  (For invocation by subclass constructors, typically
  64      * implicit.)
  65      */
  66     protected AbstractCollection() {
  67     }
  68 
  69     // Query Operations
  70 
  71     /**
  72      * Returns an iterator over the elements contained in this collection.
  73      *
  74      * @return an iterator over the elements contained in this collection
  75      */
  76     public abstract Iterator<E> iterator();
  77 
  78     public abstract int size();
  79 
  80     /**
  81      * {@inheritDoc}
  82      *
  83      * <p>This implementation returns <tt>size() == 0</tt>.
  84      */
  85     public boolean isEmpty() {
  86         return size() == 0;
  87     }
  88 
  89     /**
  90      * {@inheritDoc}
  91      *
  92      * <p>This implementation iterates over the elements in the collection,
  93      * checking each element in turn for equality with the specified element.
  94      *
  95      * @throws ClassCastException   {@inheritDoc}
  96      * @throws NullPointerException {@inheritDoc}
  97      */
  98     public boolean contains(Object o) {
  99         Iterator<E> it = iterator();
 100         if (o==null) {
 101             while (it.hasNext())
 102                 if (it.next()==null)
 103                     return true;
 104         } else {
 105             while (it.hasNext())
 106                 if (o.equals(it.next()))
 107                     return true;
 108         }
 109         return false;
 110     }
 111 
 112     /**
 113      * {@inheritDoc}
 114      *
 115      * <p>This implementation returns an array containing all the elements
 116      * returned by this collection's iterator, in the same order, stored in
 117      * consecutive elements of the array, starting with index {@code 0}.
 118      * The length of the returned array is equal to the number of elements
 119      * returned by the iterator, even if the size of this collection changes
 120      * during iteration, as might happen if the collection permits
 121      * concurrent modification during iteration.  The {@code size} method is
 122      * called only as an optimization hint; the correct result is returned
 123      * even if the iterator returns a different number of elements.
 124      *
 125      * <p>This method is equivalent to:
 126      *
 127      *  <pre> {@code
 128      * List<E> list = new ArrayList<E>(size());
 129      * for (E e : this)
 130      *     list.add(e);
 131      * return list.toArray();
 132      * }</pre>
 133      */
 134     public Object[] toArray() {
 135         // Estimate size of array; be prepared to see more or fewer elements
 136         Object[] r = new Object[size()];
 137         Iterator<E> it = iterator();
 138         for (int i = 0; i < r.length; i++) {
 139             if (! it.hasNext()) // fewer elements than expected
 140                 return Arrays.copyOf(r, i);
 141             r[i] = it.next();
 142         }
 143         return it.hasNext() ? finishToArray(r, it) : r;
 144     }
 145 
 146     /**
 147      * {@inheritDoc}
 148      *
 149      * <p>This implementation returns an array containing all the elements
 150      * returned by this collection's iterator in the same order, stored in
 151      * consecutive elements of the array, starting with index {@code 0}.
 152      * If the number of elements returned by the iterator is too large to
 153      * fit into the specified array, then the elements are returned in a
 154      * newly allocated array with length equal to the number of elements
 155      * returned by the iterator, even if the size of this collection
 156      * changes during iteration, as might happen if the collection permits
 157      * concurrent modification during iteration.  The {@code size} method is
 158      * called only as an optimization hint; the correct result is returned
 159      * even if the iterator returns a different number of elements.
 160      *
 161      * <p>This method is equivalent to:
 162      *
 163      *  <pre> {@code
 164      * List<E> list = new ArrayList<E>(size());
 165      * for (E e : this)
 166      *     list.add(e);
 167      * return list.toArray(a);
 168      * }</pre>
 169      *
 170      * @throws ArrayStoreException  {@inheritDoc}
 171      * @throws NullPointerException {@inheritDoc}
 172      */
 173     @SuppressWarnings("unchecked")
 174     public <T> T[] toArray(T[] a) {
 175         // Estimate size of array; be prepared to see more or fewer elements
 176         int size = size();
 177         T[] r = a.length >= size ? a :
 178                   (T[])java.lang.reflect.Array
 179                   .newInstance(a.getClass().getComponentType(), size);
 180         Iterator<E> it = iterator();
 181 
 182         for (int i = 0; i < r.length; i++) {
 183             if (! it.hasNext()) { // fewer elements than expected
 184                 if (a == r) {
 185                     r[i] = null; // null-terminate
 186                 } else if (a.length < i) {
 187                     return Arrays.copyOf(r, i);
 188                 } else {
 189                     System.arraycopy(r, 0, a, 0, i);
 190                     if (a.length > i) {
 191                         a[i] = null;
 192                     }
 193                 }
 194                 return a;
 195             }
 196             r[i] = (T)it.next();
 197         }
 198         // more elements than expected
 199         return it.hasNext() ? finishToArray(r, it) : r;
 200     }
 201 
 202     /**
 203      * The maximum size of array to allocate.
 204      * Some VMs reserve some header words in an array.
 205      * Attempts to allocate larger arrays may result in
 206      * OutOfMemoryError: Requested array size exceeds VM limit
 207      */
 208     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 209 
 210     /**
 211      * Reallocates the array being used within toArray when the iterator
 212      * returned more elements than expected, and finishes filling it from
 213      * the iterator.
 214      *
 215      * @param r the array, replete with previously stored elements
 216      * @param it the in-progress iterator over this collection
 217      * @return array containing the elements in the given array, plus any
 218      *         further elements returned by the iterator, trimmed to size
 219      */
 220     @SuppressWarnings("unchecked")
 221     private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
 222         int i = r.length;
 223         while (it.hasNext()) {
 224             int cap = r.length;
 225             if (i == cap) {
 226                 int newCap = cap + (cap >> 1) + 1;
 227                 // overflow-conscious code
 228                 if (newCap - MAX_ARRAY_SIZE > 0)
 229                     newCap = hugeCapacity(cap + 1);
 230                 r = Arrays.copyOf(r, newCap);
 231             }
 232             r[i++] = (T)it.next();
 233         }
 234         // trim if overallocated
 235         return (i == r.length) ? r : Arrays.copyOf(r, i);
 236     }
 237 
 238     private static int hugeCapacity(int minCapacity) {
 239         if (minCapacity < 0) // overflow
 240             throw new OutOfMemoryError
 241                 ("Required array size too large");
 242         return (minCapacity > MAX_ARRAY_SIZE) ?
 243             Integer.MAX_VALUE :
 244             MAX_ARRAY_SIZE;
 245     }
 246 
 247     // Modification Operations
 248 
 249     /**
 250      * {@inheritDoc}
 251      *
 252      * <p>This implementation always throws an
 253      * <tt>UnsupportedOperationException</tt>.
 254      *
 255      * @throws UnsupportedOperationException {@inheritDoc}
 256      * @throws ClassCastException            {@inheritDoc}
 257      * @throws NullPointerException          {@inheritDoc}
 258      * @throws IllegalArgumentException      {@inheritDoc}
 259      * @throws IllegalStateException         {@inheritDoc}
 260      */
 261     public boolean add(E e) {
 262         throw new UnsupportedOperationException();
 263     }
 264 
 265     /**
 266      * {@inheritDoc}
 267      *
 268      * <p>This implementation iterates over the collection looking for the
 269      * specified element.  If it finds the element, it removes the element
 270      * from the collection using the iterator's remove method.
 271      *
 272      * <p>Note that this implementation throws an
 273      * <tt>UnsupportedOperationException</tt> if the iterator returned by this
 274      * collection's iterator method does not implement the <tt>remove</tt>
 275      * method and this collection contains the specified object.
 276      *
 277      * @throws UnsupportedOperationException {@inheritDoc}
 278      * @throws ClassCastException            {@inheritDoc}
 279      * @throws NullPointerException          {@inheritDoc}
 280      */
 281     public boolean remove(Object o) {
 282         Iterator<E> it = iterator();
 283         if (o==null) {
 284             while (it.hasNext()) {
 285                 if (it.next()==null) {
 286                     it.remove();
 287                     return true;
 288                 }
 289             }
 290         } else {
 291             while (it.hasNext()) {
 292                 if (o.equals(it.next())) {
 293                     it.remove();
 294                     return true;
 295                 }
 296             }
 297         }
 298         return false;
 299     }
 300 
 301 
 302     // Bulk Operations
 303 
 304     /**
 305      * {@inheritDoc}
 306      *
 307      * <p>This implementation iterates over the specified collection,
 308      * checking each element returned by the iterator in turn to see
 309      * if it's contained in this collection.  If all elements are so
 310      * contained <tt>true</tt> is returned, otherwise <tt>false</tt>.
 311      *
 312      * @throws ClassCastException            {@inheritDoc}
 313      * @throws NullPointerException          {@inheritDoc}
 314      * @see #contains(Object)
 315      */
 316     public boolean containsAll(Collection<?> c) {
 317         for (Object e : c)
 318             if (!contains(e))
 319                 return false;
 320         return true;
 321     }
 322 
 323     /**
 324      * {@inheritDoc}
 325      *
 326      * <p>This implementation iterates over the specified collection, and adds
 327      * each object returned by the iterator to this collection, in turn.
 328      *
 329      * <p>Note that this implementation will throw an
 330      * <tt>UnsupportedOperationException</tt> unless <tt>add</tt> is
 331      * overridden (assuming the specified collection is non-empty).
 332      *
 333      * @throws UnsupportedOperationException {@inheritDoc}
 334      * @throws ClassCastException            {@inheritDoc}
 335      * @throws NullPointerException          {@inheritDoc}
 336      * @throws IllegalArgumentException      {@inheritDoc}
 337      * @throws IllegalStateException         {@inheritDoc}
 338      *
 339      * @see #add(Object)
 340      */
 341     public boolean addAll(Collection<? extends E> c) {
 342         boolean modified = false;
 343         for (E e : c)
 344             if (add(e))
 345                 modified = true;
 346         return modified;
 347     }
 348 
 349     /**
 350      * {@inheritDoc}
 351      *
 352      * <p>This implementation iterates over this collection, checking each
 353      * element returned by the iterator in turn to see if it's contained
 354      * in the specified collection.  If it's so contained, it's removed from
 355      * this collection with the iterator's <tt>remove</tt> method.
 356      *
 357      * <p>Note that this implementation will throw an
 358      * <tt>UnsupportedOperationException</tt> if the iterator returned by the
 359      * <tt>iterator</tt> method does not implement the <tt>remove</tt> method
 360      * and this collection contains one or more elements in common with the
 361      * specified collection.
 362      *
 363      * @throws UnsupportedOperationException {@inheritDoc}
 364      * @throws ClassCastException            {@inheritDoc}
 365      * @throws NullPointerException          {@inheritDoc}
 366      *
 367      * @see #remove(Object)
 368      * @see #contains(Object)
 369      */
 370     public boolean removeAll(Collection<?> c) {
 371         boolean modified = false;
 372         Iterator<?> it = iterator();
 373         while (it.hasNext()) {
 374             if (c.contains(it.next())) {
 375                 it.remove();
 376                 modified = true;
 377             }
 378         }
 379         return modified;
 380     }
 381 
 382     /**
 383      * {@inheritDoc}
 384      *
 385      * <p>This implementation iterates over this collection, checking each
 386      * element returned by the iterator in turn to see if it's contained
 387      * in the specified collection.  If it's not so contained, it's removed
 388      * from this collection with the iterator's <tt>remove</tt> method.
 389      *
 390      * <p>Note that this implementation will throw an
 391      * <tt>UnsupportedOperationException</tt> if the iterator returned by the
 392      * <tt>iterator</tt> method does not implement the <tt>remove</tt> method
 393      * and this collection contains one or more elements not present in the
 394      * specified collection.
 395      *
 396      * @throws UnsupportedOperationException {@inheritDoc}
 397      * @throws ClassCastException            {@inheritDoc}
 398      * @throws NullPointerException          {@inheritDoc}
 399      *
 400      * @see #remove(Object)
 401      * @see #contains(Object)
 402      */
 403     public boolean retainAll(Collection<?> c) {
 404         boolean modified = false;
 405         Iterator<E> it = iterator();
 406         while (it.hasNext()) {
 407             if (!c.contains(it.next())) {
 408                 it.remove();
 409                 modified = true;
 410             }
 411         }
 412         return modified;
 413     }
 414 
 415     /**
 416      * {@inheritDoc}
 417      *
 418      * <p>This implementation iterates over this collection, removing each
 419      * element using the <tt>Iterator.remove</tt> operation.  Most
 420      * implementations will probably choose to override this method for
 421      * efficiency.
 422      *
 423      * <p>Note that this implementation will throw an
 424      * <tt>UnsupportedOperationException</tt> if the iterator returned by this
 425      * collection's <tt>iterator</tt> method does not implement the
 426      * <tt>remove</tt> method and this collection is non-empty.
 427      *
 428      * @throws UnsupportedOperationException {@inheritDoc}
 429      */
 430     public void clear() {
 431         Iterator<E> it = iterator();
 432         while (it.hasNext()) {
 433             it.next();
 434             it.remove();
 435         }
 436     }
 437 
 438 
 439     //  String conversion
 440 
 441     /**
 442      * Returns a string representation of this collection.  The string
 443      * representation consists of a list of the collection's elements in the
 444      * order they are returned by its iterator, enclosed in square brackets
 445      * (<tt>"[]"</tt>).  Adjacent elements are separated by the characters
 446      * <tt>", "</tt> (comma and space).  Elements are converted to strings as
 447      * by {@link String#valueOf(Object)}.
 448      *
 449      * @return a string representation of this collection
 450      */
 451     public String toString() {
 452         Iterator<E> it = iterator();
 453         if (! it.hasNext())
 454             return "[]";
 455 
 456         StringBuilder sb = new StringBuilder();
 457         sb.append('[');
 458         for (;;) {
 459             E e = it.next();
 460             sb.append(e == this ? "(this Collection)" : e);
 461             if (! it.hasNext())
 462                 return sb.append(']').toString();
 463             sb.append(',').append(' ');
 464         }
 465     }
 466 
 467 }