jaroslav@557: /*
jaroslav@557:  * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved.
jaroslav@557:  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
jaroslav@557:  *
jaroslav@557:  * This code is free software; you can redistribute it and/or modify it
jaroslav@557:  * under the terms of the GNU General Public License version 2 only, as
jaroslav@557:  * published by the Free Software Foundation.  Oracle designates this
jaroslav@557:  * particular file as subject to the "Classpath" exception as provided
jaroslav@557:  * by Oracle in the LICENSE file that accompanied this code.
jaroslav@557:  *
jaroslav@557:  * This code is distributed in the hope that it will be useful, but WITHOUT
jaroslav@557:  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
jaroslav@557:  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
jaroslav@557:  * version 2 for more details (a copy is included in the LICENSE file that
jaroslav@557:  * accompanied this code).
jaroslav@557:  *
jaroslav@557:  * You should have received a copy of the GNU General Public License version
jaroslav@557:  * 2 along with this work; if not, write to the Free Software Foundation,
jaroslav@557:  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
jaroslav@557:  *
jaroslav@557:  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
jaroslav@557:  * or visit www.oracle.com if you need additional information or have any
jaroslav@557:  * questions.
jaroslav@557:  */
jaroslav@557: 
jaroslav@557: package java.util;
jaroslav@557: 
jaroslav@557: /**
jaroslav@557:  * This class provides a skeletal implementation of the <tt>Collection</tt>
jaroslav@557:  * interface, to minimize the effort required to implement this interface. <p>
jaroslav@557:  *
jaroslav@557:  * To implement an unmodifiable collection, the programmer needs only to
jaroslav@557:  * extend this class and provide implementations for the <tt>iterator</tt> and
jaroslav@557:  * <tt>size</tt> methods.  (The iterator returned by the <tt>iterator</tt>
jaroslav@557:  * method must implement <tt>hasNext</tt> and <tt>next</tt>.)<p>
jaroslav@557:  *
jaroslav@557:  * To implement a modifiable collection, the programmer must additionally
jaroslav@557:  * override this class's <tt>add</tt> method (which otherwise throws an
jaroslav@557:  * <tt>UnsupportedOperationException</tt>), and the iterator returned by the
jaroslav@557:  * <tt>iterator</tt> method must additionally implement its <tt>remove</tt>
jaroslav@557:  * method.<p>
jaroslav@557:  *
jaroslav@557:  * The programmer should generally provide a void (no argument) and
jaroslav@557:  * <tt>Collection</tt> constructor, as per the recommendation in the
jaroslav@557:  * <tt>Collection</tt> interface specification.<p>
jaroslav@557:  *
jaroslav@557:  * The documentation for each non-abstract method in this class describes its
jaroslav@557:  * implementation in detail.  Each of these methods may be overridden if
jaroslav@557:  * the collection being implemented admits a more efficient implementation.<p>
jaroslav@557:  *
jaroslav@557:  * This class is a member of the
jaroslav@557:  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
jaroslav@557:  * Java Collections Framework</a>.
jaroslav@557:  *
jaroslav@557:  * @author  Josh Bloch
jaroslav@557:  * @author  Neal Gafter
jaroslav@557:  * @see Collection
jaroslav@557:  * @since 1.2
jaroslav@557:  */
jaroslav@557: 
jaroslav@557: public abstract class AbstractCollection<E> implements Collection<E> {
jaroslav@557:     /**
jaroslav@557:      * Sole constructor.  (For invocation by subclass constructors, typically
jaroslav@557:      * implicit.)
jaroslav@557:      */
jaroslav@557:     protected AbstractCollection() {
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     // Query Operations
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Returns an iterator over the elements contained in this collection.
jaroslav@557:      *
jaroslav@557:      * @return an iterator over the elements contained in this collection
jaroslav@557:      */
jaroslav@557:     public abstract Iterator<E> iterator();
jaroslav@557: 
jaroslav@557:     public abstract int size();
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * {@inheritDoc}
jaroslav@557:      *
jaroslav@557:      * <p>This implementation returns <tt>size() == 0</tt>.
jaroslav@557:      */
jaroslav@557:     public boolean isEmpty() {
jaroslav@557:         return size() == 0;
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * {@inheritDoc}
jaroslav@557:      *
jaroslav@557:      * <p>This implementation iterates over the elements in the collection,
jaroslav@557:      * checking each element in turn for equality with the specified element.
jaroslav@557:      *
jaroslav@557:      * @throws ClassCastException   {@inheritDoc}
jaroslav@557:      * @throws NullPointerException {@inheritDoc}
jaroslav@557:      */
jaroslav@557:     public boolean contains(Object o) {
jaroslav@557:         Iterator<E> it = iterator();
jaroslav@557:         if (o==null) {
jaroslav@557:             while (it.hasNext())
jaroslav@557:                 if (it.next()==null)
jaroslav@557:                     return true;
jaroslav@557:         } else {
jaroslav@557:             while (it.hasNext())
jaroslav@557:                 if (o.equals(it.next()))
jaroslav@557:                     return true;
jaroslav@557:         }
jaroslav@557:         return false;
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * {@inheritDoc}
jaroslav@557:      *
jaroslav@557:      * <p>This implementation returns an array containing all the elements
jaroslav@557:      * returned by this collection's iterator, in the same order, stored in
jaroslav@557:      * consecutive elements of the array, starting with index {@code 0}.
jaroslav@557:      * The length of the returned array is equal to the number of elements
jaroslav@557:      * returned by the iterator, even if the size of this collection changes
jaroslav@557:      * during iteration, as might happen if the collection permits
jaroslav@557:      * concurrent modification during iteration.  The {@code size} method is
jaroslav@557:      * called only as an optimization hint; the correct result is returned
jaroslav@557:      * even if the iterator returns a different number of elements.
jaroslav@557:      *
jaroslav@557:      * <p>This method is equivalent to:
jaroslav@557:      *
jaroslav@557:      *  <pre> {@code
jaroslav@557:      * List<E> list = new ArrayList<E>(size());
jaroslav@557:      * for (E e : this)
jaroslav@557:      *     list.add(e);
jaroslav@557:      * return list.toArray();
jaroslav@557:      * }</pre>
jaroslav@557:      */
jaroslav@557:     public Object[] toArray() {
jaroslav@557:         // Estimate size of array; be prepared to see more or fewer elements
jaroslav@557:         Object[] r = new Object[size()];
jaroslav@557:         Iterator<E> it = iterator();
jaroslav@557:         for (int i = 0; i < r.length; i++) {
jaroslav@557:             if (! it.hasNext()) // fewer elements than expected
jaroslav@557:                 return Arrays.copyOf(r, i);
jaroslav@557:             r[i] = it.next();
jaroslav@557:         }
jaroslav@557:         return it.hasNext() ? finishToArray(r, it) : r;
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * {@inheritDoc}
jaroslav@557:      *
jaroslav@557:      * <p>This implementation returns an array containing all the elements
jaroslav@557:      * returned by this collection's iterator in the same order, stored in
jaroslav@557:      * consecutive elements of the array, starting with index {@code 0}.
jaroslav@557:      * If the number of elements returned by the iterator is too large to
jaroslav@557:      * fit into the specified array, then the elements are returned in a
jaroslav@557:      * newly allocated array with length equal to the number of elements
jaroslav@557:      * returned by the iterator, even if the size of this collection
jaroslav@557:      * changes during iteration, as might happen if the collection permits
jaroslav@557:      * concurrent modification during iteration.  The {@code size} method is
jaroslav@557:      * called only as an optimization hint; the correct result is returned
jaroslav@557:      * even if the iterator returns a different number of elements.
jaroslav@557:      *
jaroslav@557:      * <p>This method is equivalent to:
jaroslav@557:      *
jaroslav@557:      *  <pre> {@code
jaroslav@557:      * List<E> list = new ArrayList<E>(size());
jaroslav@557:      * for (E e : this)
jaroslav@557:      *     list.add(e);
jaroslav@557:      * return list.toArray(a);
jaroslav@557:      * }</pre>
jaroslav@557:      *
jaroslav@557:      * @throws ArrayStoreException  {@inheritDoc}
jaroslav@557:      * @throws NullPointerException {@inheritDoc}
jaroslav@557:      */
jaroslav@557:     public <T> T[] toArray(T[] a) {
jaroslav@557:         // Estimate size of array; be prepared to see more or fewer elements
jaroslav@557:         int size = size();
jaroslav@557:         T[] r = a.length >= size ? a :
jaroslav@557:                   (T[])java.lang.reflect.Array
jaroslav@557:                   .newInstance(a.getClass().getComponentType(), size);
jaroslav@557:         Iterator<E> it = iterator();
jaroslav@557: 
jaroslav@557:         for (int i = 0; i < r.length; i++) {
jaroslav@557:             if (! it.hasNext()) { // fewer elements than expected
jaroslav@557:                 if (a != r)
jaroslav@557:                     return Arrays.copyOf(r, i);
jaroslav@557:                 r[i] = null; // null-terminate
jaroslav@557:                 return r;
jaroslav@557:             }
jaroslav@557:             r[i] = (T)it.next();
jaroslav@557:         }
jaroslav@557:         return it.hasNext() ? finishToArray(r, it) : r;
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * The maximum size of array to allocate.
jaroslav@557:      * Some VMs reserve some header words in an array.
jaroslav@557:      * Attempts to allocate larger arrays may result in
jaroslav@557:      * OutOfMemoryError: Requested array size exceeds VM limit
jaroslav@557:      */
jaroslav@557:     private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Reallocates the array being used within toArray when the iterator
jaroslav@557:      * returned more elements than expected, and finishes filling it from
jaroslav@557:      * the iterator.
jaroslav@557:      *
jaroslav@557:      * @param r the array, replete with previously stored elements
jaroslav@557:      * @param it the in-progress iterator over this collection
jaroslav@557:      * @return array containing the elements in the given array, plus any
jaroslav@557:      *         further elements returned by the iterator, trimmed to size
jaroslav@557:      */
jaroslav@557:     private static <T> T[] finishToArray(T[] r, Iterator<?> it) {
jaroslav@557:         int i = r.length;
jaroslav@557:         while (it.hasNext()) {
jaroslav@557:             int cap = r.length;
jaroslav@557:             if (i == cap) {
jaroslav@557:                 int newCap = cap + (cap >> 1) + 1;
jaroslav@557:                 // overflow-conscious code
jaroslav@557:                 if (newCap - MAX_ARRAY_SIZE > 0)
jaroslav@557:                     newCap = hugeCapacity(cap + 1);
jaroslav@557:                 r = Arrays.copyOf(r, newCap);
jaroslav@557:             }
jaroslav@557:             r[i++] = (T)it.next();
jaroslav@557:         }
jaroslav@557:         // trim if overallocated
jaroslav@557:         return (i == r.length) ? r : Arrays.copyOf(r, i);
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     private static int hugeCapacity(int minCapacity) {
jaroslav@557:         if (minCapacity < 0) // overflow
jaroslav@557:             throw new OutOfMemoryError
jaroslav@557:                 ("Required array size too large");
jaroslav@557:         return (minCapacity > MAX_ARRAY_SIZE) ?
jaroslav@557:             Integer.MAX_VALUE :
jaroslav@557:             MAX_ARRAY_SIZE;
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     // Modification Operations
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * {@inheritDoc}
jaroslav@557:      *
jaroslav@557:      * <p>This implementation always throws an
jaroslav@557:      * <tt>UnsupportedOperationException</tt>.
jaroslav@557:      *
jaroslav@557:      * @throws UnsupportedOperationException {@inheritDoc}
jaroslav@557:      * @throws ClassCastException            {@inheritDoc}
jaroslav@557:      * @throws NullPointerException          {@inheritDoc}
jaroslav@557:      * @throws IllegalArgumentException      {@inheritDoc}
jaroslav@557:      * @throws IllegalStateException         {@inheritDoc}
jaroslav@557:      */
jaroslav@557:     public boolean add(E e) {
jaroslav@557:         throw new UnsupportedOperationException();
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * {@inheritDoc}
jaroslav@557:      *
jaroslav@557:      * <p>This implementation iterates over the collection looking for the
jaroslav@557:      * specified element.  If it finds the element, it removes the element
jaroslav@557:      * from the collection using the iterator's remove method.
jaroslav@557:      *
jaroslav@557:      * <p>Note that this implementation throws an
jaroslav@557:      * <tt>UnsupportedOperationException</tt> if the iterator returned by this
jaroslav@557:      * collection's iterator method does not implement the <tt>remove</tt>
jaroslav@557:      * method and this collection contains the specified object.
jaroslav@557:      *
jaroslav@557:      * @throws UnsupportedOperationException {@inheritDoc}
jaroslav@557:      * @throws ClassCastException            {@inheritDoc}
jaroslav@557:      * @throws NullPointerException          {@inheritDoc}
jaroslav@557:      */
jaroslav@557:     public boolean remove(Object o) {
jaroslav@557:         Iterator<E> it = iterator();
jaroslav@557:         if (o==null) {
jaroslav@557:             while (it.hasNext()) {
jaroslav@557:                 if (it.next()==null) {
jaroslav@557:                     it.remove();
jaroslav@557:                     return true;
jaroslav@557:                 }
jaroslav@557:             }
jaroslav@557:         } else {
jaroslav@557:             while (it.hasNext()) {
jaroslav@557:                 if (o.equals(it.next())) {
jaroslav@557:                     it.remove();
jaroslav@557:                     return true;
jaroslav@557:                 }
jaroslav@557:             }
jaroslav@557:         }
jaroslav@557:         return false;
jaroslav@557:     }
jaroslav@557: 
jaroslav@557: 
jaroslav@557:     // Bulk Operations
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * {@inheritDoc}
jaroslav@557:      *
jaroslav@557:      * <p>This implementation iterates over the specified collection,
jaroslav@557:      * checking each element returned by the iterator in turn to see
jaroslav@557:      * if it's contained in this collection.  If all elements are so
jaroslav@557:      * contained <tt>true</tt> is returned, otherwise <tt>false</tt>.
jaroslav@557:      *
jaroslav@557:      * @throws ClassCastException            {@inheritDoc}
jaroslav@557:      * @throws NullPointerException          {@inheritDoc}
jaroslav@557:      * @see #contains(Object)
jaroslav@557:      */
jaroslav@557:     public boolean containsAll(Collection<?> c) {
jaroslav@557:         for (Object e : c)
jaroslav@557:             if (!contains(e))
jaroslav@557:                 return false;
jaroslav@557:         return true;
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * {@inheritDoc}
jaroslav@557:      *
jaroslav@557:      * <p>This implementation iterates over the specified collection, and adds
jaroslav@557:      * each object returned by the iterator to this collection, in turn.
jaroslav@557:      *
jaroslav@557:      * <p>Note that this implementation will throw an
jaroslav@557:      * <tt>UnsupportedOperationException</tt> unless <tt>add</tt> is
jaroslav@557:      * overridden (assuming the specified collection is non-empty).
jaroslav@557:      *
jaroslav@557:      * @throws UnsupportedOperationException {@inheritDoc}
jaroslav@557:      * @throws ClassCastException            {@inheritDoc}
jaroslav@557:      * @throws NullPointerException          {@inheritDoc}
jaroslav@557:      * @throws IllegalArgumentException      {@inheritDoc}
jaroslav@557:      * @throws IllegalStateException         {@inheritDoc}
jaroslav@557:      *
jaroslav@557:      * @see #add(Object)
jaroslav@557:      */
jaroslav@557:     public boolean addAll(Collection<? extends E> c) {
jaroslav@557:         boolean modified = false;
jaroslav@557:         for (E e : c)
jaroslav@557:             if (add(e))
jaroslav@557:                 modified = true;
jaroslav@557:         return modified;
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * {@inheritDoc}
jaroslav@557:      *
jaroslav@557:      * <p>This implementation iterates over this collection, checking each
jaroslav@557:      * element returned by the iterator in turn to see if it's contained
jaroslav@557:      * in the specified collection.  If it's so contained, it's removed from
jaroslav@557:      * this collection with the iterator's <tt>remove</tt> method.
jaroslav@557:      *
jaroslav@557:      * <p>Note that this implementation will throw an
jaroslav@557:      * <tt>UnsupportedOperationException</tt> if the iterator returned by the
jaroslav@557:      * <tt>iterator</tt> method does not implement the <tt>remove</tt> method
jaroslav@557:      * and this collection contains one or more elements in common with the
jaroslav@557:      * specified collection.
jaroslav@557:      *
jaroslav@557:      * @throws UnsupportedOperationException {@inheritDoc}
jaroslav@557:      * @throws ClassCastException            {@inheritDoc}
jaroslav@557:      * @throws NullPointerException          {@inheritDoc}
jaroslav@557:      *
jaroslav@557:      * @see #remove(Object)
jaroslav@557:      * @see #contains(Object)
jaroslav@557:      */
jaroslav@557:     public boolean removeAll(Collection<?> c) {
jaroslav@557:         boolean modified = false;
jaroslav@557:         Iterator<?> it = iterator();
jaroslav@557:         while (it.hasNext()) {
jaroslav@557:             if (c.contains(it.next())) {
jaroslav@557:                 it.remove();
jaroslav@557:                 modified = true;
jaroslav@557:             }
jaroslav@557:         }
jaroslav@557:         return modified;
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * {@inheritDoc}
jaroslav@557:      *
jaroslav@557:      * <p>This implementation iterates over this collection, checking each
jaroslav@557:      * element returned by the iterator in turn to see if it's contained
jaroslav@557:      * in the specified collection.  If it's not so contained, it's removed
jaroslav@557:      * from this collection with the iterator's <tt>remove</tt> method.
jaroslav@557:      *
jaroslav@557:      * <p>Note that this implementation will throw an
jaroslav@557:      * <tt>UnsupportedOperationException</tt> if the iterator returned by the
jaroslav@557:      * <tt>iterator</tt> method does not implement the <tt>remove</tt> method
jaroslav@557:      * and this collection contains one or more elements not present in the
jaroslav@557:      * specified collection.
jaroslav@557:      *
jaroslav@557:      * @throws UnsupportedOperationException {@inheritDoc}
jaroslav@557:      * @throws ClassCastException            {@inheritDoc}
jaroslav@557:      * @throws NullPointerException          {@inheritDoc}
jaroslav@557:      *
jaroslav@557:      * @see #remove(Object)
jaroslav@557:      * @see #contains(Object)
jaroslav@557:      */
jaroslav@557:     public boolean retainAll(Collection<?> c) {
jaroslav@557:         boolean modified = false;
jaroslav@557:         Iterator<E> it = iterator();
jaroslav@557:         while (it.hasNext()) {
jaroslav@557:             if (!c.contains(it.next())) {
jaroslav@557:                 it.remove();
jaroslav@557:                 modified = true;
jaroslav@557:             }
jaroslav@557:         }
jaroslav@557:         return modified;
jaroslav@557:     }
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * {@inheritDoc}
jaroslav@557:      *
jaroslav@557:      * <p>This implementation iterates over this collection, removing each
jaroslav@557:      * element using the <tt>Iterator.remove</tt> operation.  Most
jaroslav@557:      * implementations will probably choose to override this method for
jaroslav@557:      * efficiency.
jaroslav@557:      *
jaroslav@557:      * <p>Note that this implementation will throw an
jaroslav@557:      * <tt>UnsupportedOperationException</tt> if the iterator returned by this
jaroslav@557:      * collection's <tt>iterator</tt> method does not implement the
jaroslav@557:      * <tt>remove</tt> method and this collection is non-empty.
jaroslav@557:      *
jaroslav@557:      * @throws UnsupportedOperationException {@inheritDoc}
jaroslav@557:      */
jaroslav@557:     public void clear() {
jaroslav@557:         Iterator<E> it = iterator();
jaroslav@557:         while (it.hasNext()) {
jaroslav@557:             it.next();
jaroslav@557:             it.remove();
jaroslav@557:         }
jaroslav@557:     }
jaroslav@557: 
jaroslav@557: 
jaroslav@557:     //  String conversion
jaroslav@557: 
jaroslav@557:     /**
jaroslav@557:      * Returns a string representation of this collection.  The string
jaroslav@557:      * representation consists of a list of the collection's elements in the
jaroslav@557:      * order they are returned by its iterator, enclosed in square brackets
jaroslav@557:      * (<tt>"[]"</tt>).  Adjacent elements are separated by the characters
jaroslav@557:      * <tt>", "</tt> (comma and space).  Elements are converted to strings as
jaroslav@557:      * by {@link String#valueOf(Object)}.
jaroslav@557:      *
jaroslav@557:      * @return a string representation of this collection
jaroslav@557:      */
jaroslav@557:     public String toString() {
jaroslav@557:         Iterator<E> it = iterator();
jaroslav@557:         if (! it.hasNext())
jaroslav@557:             return "[]";
jaroslav@557: 
jaroslav@557:         StringBuilder sb = new StringBuilder();
jaroslav@557:         sb.append('[');
jaroslav@557:         for (;;) {
jaroslav@557:             E e = it.next();
jaroslav@557:             sb.append(e == this ? "(this Collection)" : e);
jaroslav@557:             if (! it.hasNext())
jaroslav@557:                 return sb.append(']').toString();
jaroslav@557:             sb.append(',').append(' ');
jaroslav@557:         }
jaroslav@557:     }
jaroslav@557: 
jaroslav@557: }