1 /*
   2  * Copyright (c) 1997, 2018, 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 {@code Collection}
  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 {@code iterator} and
  34  * {@code size} methods.  (The iterator returned by the {@code iterator}
  35  * method must implement {@code hasNext} and {@code next}.)<p>
  36  *
  37  * To implement a modifiable collection, the programmer must additionally
  38  * override this class's {@code add} method (which otherwise throws an
  39  * {@code UnsupportedOperationException}), and the iterator returned by the
  40  * {@code iterator} method must additionally implement its {@code remove}
  41  * method.<p>
  42  *
  43  * The programmer should generally provide a void (no argument) and
  44  * {@code Collection} constructor, as per the recommendation in the
  45  * {@code Collection} 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}/java.base/java/util/package-summary.html#CollectionsFramework">
  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      * @implSpec
  84      * This implementation returns {@code size() == 0}.
  85      */
  86     public boolean isEmpty() {
  87         return size() == 0;
  88     }
  89 
  90     /**
  91      * {@inheritDoc}
  92      *
  93      * @implSpec
  94      * This implementation iterates over the elements in the collection,
  95      * checking each element in turn for equality with the specified element.
  96      *
  97      * @throws ClassCastException   {@inheritDoc}
  98      * @throws NullPointerException {@inheritDoc}
  99      */
 100     public boolean contains(Object o) {
 101         Iterator<E> it = iterator();
 102         if (o==null) {
 103             while (it.hasNext())
 104                 if (it.next()==null)
 105                     return true;
 106         } else {
 107             while (it.hasNext())
 108                 if (o.equals(it.next()))
 109                     return true;
 110         }
 111         return false;
 112     }
 113 
 114     /**
 115      * {@inheritDoc}
 116      *
 117      * @implSpec
 118      * This implementation returns an array containing all the elements
 119      * returned by this collection's iterator, in the same order, stored in
 120      * consecutive elements of the array, starting with index {@code 0}.
 121      * The length of the returned array is equal to the number of elements
 122      * returned by the iterator, even if the size of this collection changes
 123      * during iteration, as might happen if the collection permits
 124      * concurrent modification during iteration.  The {@code size} method is
 125      * called only as an optimization hint; the correct result is returned
 126      * even if the iterator returns a different number of elements.
 127      *
 128      * <p>This method is equivalent to:
 129      *
 130      *  <pre> {@code
 131      * List<E> list = new ArrayList<E>(size());
 132      * for (E e : this)
 133      *     list.add(e);
 134      * return list.toArray();
 135      * }</pre>
 136      */
 137     public Object[] toArray() {
 138         // Estimate size of array; be prepared to see more or fewer elements
 139         Object[] r = new Object[size()];
 140         Iterator<E> it = iterator();
 141         for (int i = 0; i < r.length; i++) {
 142             if (! it.hasNext()) // fewer elements than expected
 143                 return Arrays.copyOf(r, i);
 144             r[i] = it.next();
 145         }
 146         return it.hasNext() ? finishToArray(r, it) : r;
 147     }
 148 
 149     /**
 150      * {@inheritDoc}
 151      *
 152      * @implSpec
 153      * This implementation returns an array containing all the elements
 154      * returned by this collection's iterator in the same order, stored in
 155      * consecutive elements of the array, starting with index {@code 0}.
 156      * If the number of elements returned by the iterator is too large to
 157      * fit into the specified array, then the elements are returned in a
 158      * newly allocated array with length equal to the number of elements
 159      * returned by the iterator, even if the size of this collection
 160      * changes during iteration, as might happen if the collection permits
 161      * concurrent modification during iteration.  The {@code size} method is
 162      * called only as an optimization hint; the correct result is returned
 163      * even if the iterator returns a different number of elements.
 164      *
 165      * <p>This method is equivalent to:
 166      *
 167      *  <pre> {@code
 168      * List<E> list = new ArrayList<E>(size());
 169      * for (E e : this)
 170      *     list.add(e);
 171      * return list.toArray(a);
 172      * }</pre>
 173      *
 174      * @throws ArrayStoreException  {@inheritDoc}
 175      * @throws NullPointerException {@inheritDoc}
 176      */
 177     @SuppressWarnings("unchecked")
 178     public <T> T[] toArray(T[] a) {
 179         // Estimate size of array; be prepared to see more or fewer elements
 180         int size = size();
 181         T[] r = a.length >= size ? a :
 182                   (T[])java.lang.reflect.Array
 183                   .newInstance(a.getClass().getComponentType(), size);
 184         Iterator<E> it = iterator();
 185 
 186         for (int i = 0; i < r.length; i++) {
 187             if (! it.hasNext()) { // fewer elements than expected
 188                 if (a == r) {
 189                     r[i] = null; // null-terminate
 190                 } else if (a.length < i) {
 191                     return Arrays.copyOf(r, i);
 192                 } else {
 193                     System.arraycopy(r, 0, a, 0, i);
 194                     if (a.length > i) {
 195                         a[i] = null;
 196                     }
 197                 }
 198                 return a;
 199             }
 200             r[i] = (T)it.next();
 201         }
 202         // more elements than expected
 203         return it.hasNext() ? finishToArray(r, it) : r;
 204     }
 205 
 206     /**
 207      * The maximum size of array to allocate.
 208      * Some VMs reserve some header words in an array.
 209      * Attempts to allocate larger arrays may result in
 210      * OutOfMemoryError: Requested array size exceeds VM limit
 211      */
 212     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
 213 
 214     /**
 215      * Reallocates the array being used within toArray when the iterator
 216      * returned more elements than expected, and finishes filling it from
 217      * the iterator.
 218      *
 219      * @param r the array, replete with previously stored elements
 220      * @param it the in-progress iterator over this collection
 221      * @return array containing the elements in the given array, plus any
 222      *         further elements returned by the iterator, trimmed to size
 223      */
 224     @SuppressWarnings("unchecked")
 225     private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
 226         int i = r.length;
 227         while (it.hasNext()) {
 228             int cap = r.length;
 229             if (i == cap) {
 230                 int newCap = cap + (cap >> 1) + 1;
 231                 // overflow-conscious code
 232                 if (newCap - MAX_ARRAY_SIZE > 0)
 233                     newCap = hugeCapacity(cap + 1);
 234                 r = Arrays.copyOf(r, newCap);
 235             }
 236             r[i++] = (T)it.next();
 237         }
 238         // trim if overallocated
 239         return (i == r.length) ? r : Arrays.copyOf(r, i);
 240     }
 241 
 242     private static int hugeCapacity(int minCapacity) {
 243         if (minCapacity < 0) // overflow
 244             throw new OutOfMemoryError
 245                 ("Required array size too large");
 246         return (minCapacity > MAX_ARRAY_SIZE) ?
 247             Integer.MAX_VALUE :
 248             MAX_ARRAY_SIZE;
 249     }
 250 
 251     // Modification Operations
 252 
 253     /**
 254      * {@inheritDoc}
 255      *
 256      * @implSpec
 257      * This implementation always throws an
 258      * {@code UnsupportedOperationException}.
 259      *
 260      * @throws UnsupportedOperationException {@inheritDoc}
 261      * @throws ClassCastException            {@inheritDoc}
 262      * @throws NullPointerException          {@inheritDoc}
 263      * @throws IllegalArgumentException      {@inheritDoc}
 264      * @throws IllegalStateException         {@inheritDoc}
 265      */
 266     public boolean add(E e) {
 267         throw new UnsupportedOperationException();
 268     }
 269 
 270     /**
 271      * {@inheritDoc}
 272      *
 273      * @implSpec
 274      * This implementation iterates over the collection looking for the
 275      * specified element.  If it finds the element, it removes the element
 276      * from the collection using the iterator's remove method.
 277      *
 278      * <p>Note that this implementation throws an
 279      * {@code UnsupportedOperationException} if the iterator returned by this
 280      * collection's iterator method does not implement the {@code remove}
 281      * method and this collection contains the specified object.
 282      *
 283      * @throws UnsupportedOperationException {@inheritDoc}
 284      * @throws ClassCastException            {@inheritDoc}
 285      * @throws NullPointerException          {@inheritDoc}
 286      */
 287     public boolean remove(Object o) {
 288         Iterator<E> it = iterator();
 289         if (o==null) {
 290             while (it.hasNext()) {
 291                 if (it.next()==null) {
 292                     it.remove();
 293                     return true;
 294                 }
 295             }
 296         } else {
 297             while (it.hasNext()) {
 298                 if (o.equals(it.next())) {
 299                     it.remove();
 300                     return true;
 301                 }
 302             }
 303         }
 304         return false;
 305     }
 306 
 307 
 308     // Bulk Operations
 309 
 310     /**
 311      * {@inheritDoc}
 312      *
 313      * @implSpec
 314      * This implementation iterates over the specified collection,
 315      * checking each element returned by the iterator in turn to see
 316      * if it's contained in this collection.  If all elements are so
 317      * contained {@code true} is returned, otherwise {@code false}.
 318      *
 319      * @throws ClassCastException            {@inheritDoc}
 320      * @throws NullPointerException          {@inheritDoc}
 321      * @see #contains(Object)
 322      */
 323     public boolean containsAll(Collection<?> c) {
 324         for (Object e : c)
 325             if (!contains(e))
 326                 return false;
 327         return true;
 328     }
 329 
 330     /**
 331      * {@inheritDoc}
 332      *
 333      * @implSpec
 334      * This implementation iterates over the specified collection, and adds
 335      * each object returned by the iterator to this collection, in turn.
 336      *
 337      * <p>Note that this implementation will throw an
 338      * {@code UnsupportedOperationException} unless {@code add} is
 339      * overridden (assuming the specified collection is non-empty).
 340      *
 341      * @throws UnsupportedOperationException {@inheritDoc}
 342      * @throws ClassCastException            {@inheritDoc}
 343      * @throws NullPointerException          {@inheritDoc}
 344      * @throws IllegalArgumentException      {@inheritDoc}
 345      * @throws IllegalStateException         {@inheritDoc}
 346      *
 347      * @see #add(Object)
 348      */
 349     public boolean addAll(Collection<? extends E> c) {
 350         boolean modified = false;
 351         for (E e : c)
 352             if (add(e))
 353                 modified = true;
 354         return modified;
 355     }
 356 
 357     /**
 358      * {@inheritDoc}
 359      *
 360      * @implSpec
 361      * This implementation iterates over this collection, checking each
 362      * element returned by the iterator in turn to see if it's contained
 363      * in the specified collection.  If it's so contained, it's removed from
 364      * this collection with the iterator's {@code remove} method.
 365      *
 366      * <p>Note that this implementation will throw an
 367      * {@code UnsupportedOperationException} if the iterator returned by the
 368      * {@code iterator} method does not implement the {@code remove} method
 369      * and this collection contains one or more elements in common with the
 370      * specified collection.
 371      *
 372      * @throws UnsupportedOperationException {@inheritDoc}
 373      * @throws ClassCastException            {@inheritDoc}
 374      * @throws NullPointerException          {@inheritDoc}
 375      *
 376      * @see #remove(Object)
 377      * @see #contains(Object)
 378      */
 379     public boolean removeAll(Collection<?> c) {
 380         Objects.requireNonNull(c);
 381         boolean modified = false;
 382         Iterator<?> it = iterator();
 383         while (it.hasNext()) {
 384             if (c.contains(it.next())) {
 385                 it.remove();
 386                 modified = true;
 387             }
 388         }
 389         return modified;
 390     }
 391 
 392     /**
 393      * {@inheritDoc}
 394      *
 395      * @implSpec
 396      * This implementation iterates over this collection, checking each
 397      * element returned by the iterator in turn to see if it's contained
 398      * in the specified collection.  If it's not so contained, it's removed
 399      * from this collection with the iterator's {@code remove} method.
 400      *
 401      * <p>Note that this implementation will throw an
 402      * {@code UnsupportedOperationException} if the iterator returned by the
 403      * {@code iterator} method does not implement the {@code remove} method
 404      * and this collection contains one or more elements not present in the
 405      * specified collection.
 406      *
 407      * @throws UnsupportedOperationException {@inheritDoc}
 408      * @throws ClassCastException            {@inheritDoc}
 409      * @throws NullPointerException          {@inheritDoc}
 410      *
 411      * @see #remove(Object)
 412      * @see #contains(Object)
 413      */
 414     public boolean retainAll(Collection<?> c) {
 415         Objects.requireNonNull(c);
 416         boolean modified = false;
 417         Iterator<E> it = iterator();
 418         while (it.hasNext()) {
 419             if (!c.contains(it.next())) {
 420                 it.remove();
 421                 modified = true;
 422             }
 423         }
 424         return modified;
 425     }
 426 
 427     /**
 428      * {@inheritDoc}
 429      *
 430      * @implSpec
 431      * This implementation iterates over this collection, removing each
 432      * element using the {@code Iterator.remove} operation.  Most
 433      * implementations will probably choose to override this method for
 434      * efficiency.
 435      *
 436      * <p>Note that this implementation will throw an
 437      * {@code UnsupportedOperationException} if the iterator returned by this
 438      * collection's {@code iterator} method does not implement the
 439      * {@code remove} method and this collection is non-empty.
 440      *
 441      * @throws UnsupportedOperationException {@inheritDoc}
 442      */
 443     public void clear() {
 444         Iterator<E> it = iterator();
 445         while (it.hasNext()) {
 446             it.next();
 447             it.remove();
 448         }
 449     }
 450 
 451 
 452     //  String conversion
 453 
 454     /**
 455      * Returns a string representation of this collection.  The string
 456      * representation consists of a list of the collection's elements in the
 457      * order they are returned by its iterator, enclosed in square brackets
 458      * ({@code "[]"}).  Adjacent elements are separated by the characters
 459      * {@code ", "} (comma and space).  Elements are converted to strings as
 460      * by {@link String#valueOf(Object)}.
 461      *
 462      * @return a string representation of this collection
 463      */
 464     public String toString() {
 465         Iterator<E> it = iterator();
 466         if (! it.hasNext())
 467             return "[]";
 468 
 469         StringBuilder sb = new StringBuilder();
 470         sb.append('[');
 471         for (;;) {
 472             E e = it.next();
 473             sb.append(e == this ? "(this Collection)" : e);
 474             if (! it.hasNext())
 475                 return sb.append(']').toString();
 476             sb.append(',').append(' ');
 477         }
 478     }
 479 
 480 }