1 /*

     2  * Copyright 1997-2006 Sun Microsystems, Inc.  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.  Sun designates this

     8  * particular file as subject to the "Classpath" exception as provided

     9  * by Sun 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

    22  * CA 95054 USA or visit www.sun.com if you need additional information or

    23  * have any 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> e = iterator();

   100         if (o==null) {

   101             while (e.hasNext())

   102                 if (e.next()==null)

   103                     return true;

   104         } else {

   105             while (e.hasNext())

   106                 if (o.equals(e.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     public <T> T[] toArray(T[] a) {

   174         // Estimate size of array; be prepared to see more or fewer elements

   175         int size = size();

   176         T[] r = a.length >= size ? a :

   177                   (T[])java.lang.reflect.Array

   178                   .newInstance(a.getClass().getComponentType(), size);

   179         Iterator<E> it = iterator();

   180 

   181         for (int i = 0; i < r.length; i++) {

   182             if (! it.hasNext()) { // fewer elements than expected

   183                 if (a != r)

   184                     return Arrays.copyOf(r, i);

   185                 r[i] = null; // null-terminate

   186                 return r;

   187             }

   188             r[i] = (T)it.next();

   189         }

   190         return it.hasNext() ? finishToArray(r, it) : r;

   191     }

   192 

   193     /**

   194      * Reallocates the array being used within toArray when the iterator

   195      * returned more elements than expected, and finishes filling it from

   196      * the iterator.

   197      *

   198      * @param r the array, replete with previously stored elements

   199      * @param it the in-progress iterator over this collection

   200      * @return array containing the elements in the given array, plus any

   201      *         further elements returned by the iterator, trimmed to size

   202      */

   203     private static <T> T[] finishToArray(T[] r, Iterator<?> it) {

   204         int i = r.length;

   205         while (it.hasNext()) {

   206             int cap = r.length;

   207             if (i == cap) {

   208                 int newCap = ((cap / 2) + 1) * 3;

   209                 if (newCap <= cap) { // integer overflow

   210                     if (cap == Integer.MAX_VALUE)

   211                         throw new OutOfMemoryError

   212                             ("Required array size too large");

   213                     newCap = Integer.MAX_VALUE;

   214                 }

   215                 r = Arrays.copyOf(r, newCap);

   216             }

   217             r[i++] = (T)it.next();

   218         }

   219         // trim if overallocated

   220         return (i == r.length) ? r : Arrays.copyOf(r, i);

   221     }

   222 

   223     // Modification Operations

   224 

   225     /**

   226      * {@inheritDoc}

   227      *

   228      * <p>This implementation always throws an

   229      * <tt>UnsupportedOperationException</tt>.

   230      *

   231      * @throws UnsupportedOperationException {@inheritDoc}

   232      * @throws ClassCastException            {@inheritDoc}

   233      * @throws NullPointerException          {@inheritDoc}

   234      * @throws IllegalArgumentException      {@inheritDoc}

   235      * @throws IllegalStateException         {@inheritDoc}

   236      */

   237     public boolean add(E e) {

   238         throw new UnsupportedOperationException();

   239     }

   240 

   241     /**

   242      * {@inheritDoc}

   243      *

   244      * <p>This implementation iterates over the collection looking for the

   245      * specified element.  If it finds the element, it removes the element

   246      * from the collection using the iterator's remove method.

   247      *

   248      * <p>Note that this implementation throws an

   249      * <tt>UnsupportedOperationException</tt> if the iterator returned by this

   250      * collection's iterator method does not implement the <tt>remove</tt>

   251      * method and this collection contains the specified object.

   252      *

   253      * @throws UnsupportedOperationException {@inheritDoc}

   254      * @throws ClassCastException            {@inheritDoc}

   255      * @throws NullPointerException          {@inheritDoc}

   256      */

   257     public boolean remove(Object o) {

   258         Iterator<E> e = iterator();

   259         if (o==null) {

   260             while (e.hasNext()) {

   261                 if (e.next()==null) {

   262                     e.remove();

   263                     return true;

   264                 }

   265             }

   266         } else {

   267             while (e.hasNext()) {

   268                 if (o.equals(e.next())) {

   269                     e.remove();

   270                     return true;

   271                 }

   272             }

   273         }

   274         return false;

   275     }

   276 

   277 

   278     // Bulk Operations

   279 

   280     /**

   281      * {@inheritDoc}

   282      *

   283      * <p>This implementation iterates over the specified collection,

   284      * checking each element returned by the iterator in turn to see

   285      * if it's contained in this collection.  If all elements are so

   286      * contained <tt>true</tt> is returned, otherwise <tt>false</tt>.

   287      *

   288      * @throws ClassCastException            {@inheritDoc}

   289      * @throws NullPointerException          {@inheritDoc}

   290      * @see #contains(Object)

   291      */

   292     public boolean containsAll(Collection<?> c) {

   293         Iterator<?> e = c.iterator();

   294         while (e.hasNext())

   295             if (!contains(e.next()))

   296                 return false;

   297         return true;

   298     }

   299 

   300     /**

   301      * {@inheritDoc}

   302      *

   303      * <p>This implementation iterates over the specified collection, and adds

   304      * each object returned by the iterator to this collection, in turn.

   305      *

   306      * <p>Note that this implementation will throw an

   307      * <tt>UnsupportedOperationException</tt> unless <tt>add</tt> is

   308      * overridden (assuming the specified collection is non-empty).

   309      *

   310      * @throws UnsupportedOperationException {@inheritDoc}

   311      * @throws ClassCastException            {@inheritDoc}

   312      * @throws NullPointerException          {@inheritDoc}

   313      * @throws IllegalArgumentException      {@inheritDoc}

   314      * @throws IllegalStateException         {@inheritDoc}

   315      *

   316      * @see #add(Object)

   317      */

   318     public boolean addAll(Collection<? extends E> c) {

   319         boolean modified = false;

   320         Iterator<? extends E> e = c.iterator();

   321         while (e.hasNext()) {

   322             if (add(e.next()))

   323                 modified = true;

   324         }

   325         return modified;

   326     }

   327 

   328     /**

   329      * {@inheritDoc}

   330      *

   331      * <p>This implementation iterates over this collection, checking each

   332      * element returned by the iterator in turn to see if it's contained

   333      * in the specified collection.  If it's so contained, it's removed from

   334      * this collection with the iterator's <tt>remove</tt> method.

   335      *

   336      * <p>Note that this implementation will throw an

   337      * <tt>UnsupportedOperationException</tt> if the iterator returned by the

   338      * <tt>iterator</tt> method does not implement the <tt>remove</tt> method

   339      * and this collection contains one or more elements in common with the

   340      * specified collection.

   341      *

   342      * @throws UnsupportedOperationException {@inheritDoc}

   343      * @throws ClassCastException            {@inheritDoc}

   344      * @throws NullPointerException          {@inheritDoc}

   345      *

   346      * @see #remove(Object)

   347      * @see #contains(Object)

   348      */

   349     public boolean removeAll(Collection<?> c) {

   350         boolean modified = false;

   351         Iterator<?> e = iterator();

   352         while (e.hasNext()) {

   353             if (c.contains(e.next())) {

   354                 e.remove();

   355                 modified = true;

   356             }

   357         }

   358         return modified;

   359     }

   360 

   361     /**

   362      * {@inheritDoc}

   363      *

   364      * <p>This implementation iterates over this collection, checking each

   365      * element returned by the iterator in turn to see if it's contained

   366      * in the specified collection.  If it's not so contained, it's removed

   367      * from this collection with the iterator's <tt>remove</tt> method.

   368      *

   369      * <p>Note that this implementation will throw an

   370      * <tt>UnsupportedOperationException</tt> if the iterator returned by the

   371      * <tt>iterator</tt> method does not implement the <tt>remove</tt> method

   372      * and this collection contains one or more elements not present in the

   373      * specified collection.

   374      *

   375      * @throws UnsupportedOperationException {@inheritDoc}

   376      * @throws ClassCastException            {@inheritDoc}

   377      * @throws NullPointerException          {@inheritDoc}

   378      *

   379      * @see #remove(Object)

   380      * @see #contains(Object)

   381      */

   382     public boolean retainAll(Collection<?> c) {

   383         boolean modified = false;

   384         Iterator<E> e = iterator();

   385         while (e.hasNext()) {

   386             if (!c.contains(e.next())) {

   387                 e.remove();

   388                 modified = true;

   389             }

   390         }

   391         return modified;

   392     }

   393 

   394     /**

   395      * {@inheritDoc}

   396      *

   397      * <p>This implementation iterates over this collection, removing each

   398      * element using the <tt>Iterator.remove</tt> operation.  Most

   399      * implementations will probably choose to override this method for

   400      * efficiency.

   401      *

   402      * <p>Note that this implementation will throw an

   403      * <tt>UnsupportedOperationException</tt> if the iterator returned by this

   404      * collection's <tt>iterator</tt> method does not implement the

   405      * <tt>remove</tt> method and this collection is non-empty.

   406      *

   407      * @throws UnsupportedOperationException {@inheritDoc}

   408      */

   409     public void clear() {

   410         Iterator<E> e = iterator();

   411         while (e.hasNext()) {

   412             e.next();

   413             e.remove();

   414         }

   415     }

   416 

   417 

   418     //  String conversion

   419 

   420     /**

   421      * Returns a string representation of this collection.  The string

   422      * representation consists of a list of the collection's elements in the

   423      * order they are returned by its iterator, enclosed in square brackets

   424      * (<tt>"[]"</tt>).  Adjacent elements are separated by the characters

   425      * <tt>", "</tt> (comma and space).  Elements are converted to strings as

   426      * by {@link String#valueOf(Object)}.

   427      *

   428      * @return a string representation of this collection

   429      */

   430     public String toString() {

   431         Iterator<E> i = iterator();

   432         if (! i.hasNext())

   433             return "[]";

   434 

   435         StringBuilder sb = new StringBuilder();

   436         sb.append('[');

   437         for (;;) {

   438             E e = i.next();

   439             sb.append(e == this ? "(this Collection)" : e);

   440             if (! i.hasNext())

   441                 return sb.append(']').toString();

   442             sb.append(", ");

   443         }

   444     }

   445 

   446 }