/* * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. Oracle designates this * particular file as subject to the "Classpath" exception as provided * by Oracle in the LICENSE file that accompanied this code. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. */ package java.util; /** * This class provides a skeletal implementation of the Collection * interface, to minimize the effort required to implement this interface.

* * To implement an unmodifiable collection, the programmer needs only to * extend this class and provide implementations for the iterator and * size methods. (The iterator returned by the iterator * method must implement hasNext and next.)

* * To implement a modifiable collection, the programmer must additionally * override this class's add method (which otherwise throws an * UnsupportedOperationException), and the iterator returned by the * iterator method must additionally implement its remove * method.

* * The programmer should generally provide a void (no argument) and * Collection constructor, as per the recommendation in the * Collection interface specification.

* * The documentation for each non-abstract method in this class describes its * implementation in detail. Each of these methods may be overridden if * the collection being implemented admits a more efficient implementation.

* * This class is a member of the * * Java Collections Framework. * * @author Josh Bloch * @author Neal Gafter * @see Collection * @since 1.2 */ public abstract class AbstractCollection implements Collection { /** * Sole constructor. (For invocation by subclass constructors, typically * implicit.) */ protected AbstractCollection() { } // Query Operations /** * Returns an iterator over the elements contained in this collection. * * @return an iterator over the elements contained in this collection */ public abstract Iterator iterator(); public abstract int size(); /** * {@inheritDoc} * *

This implementation returns size() == 0. */ public boolean isEmpty() { return size() == 0; } /** * {@inheritDoc} * *

This implementation iterates over the elements in the collection, * checking each element in turn for equality with the specified element. * * @throws ClassCastException {@inheritDoc} * @throws NullPointerException {@inheritDoc} */ public boolean contains(Object o) { Iterator it = iterator(); if (o==null) { while (it.hasNext()) if (it.next()==null) return true; } else { while (it.hasNext()) if (o.equals(it.next())) return true; } return false; } /** * {@inheritDoc} * *

This implementation returns an array containing all the elements * returned by this collection's iterator, in the same order, stored in * consecutive elements of the array, starting with index {@code 0}. * The length of the returned array is equal to the number of elements * returned by the iterator, even if the size of this collection changes * during iteration, as might happen if the collection permits * concurrent modification during iteration. The {@code size} method is * called only as an optimization hint; the correct result is returned * even if the iterator returns a different number of elements. * *

This method is equivalent to: * *

 {@code
     * List list = new ArrayList(size());
     * for (E e : this)
     *     list.add(e);
     * return list.toArray();
     * }
*/ public Object[] toArray() { // Estimate size of array; be prepared to see more or fewer elements Object[] r = new Object[size()]; Iterator it = iterator(); for (int i = 0; i < r.length; i++) { if (! it.hasNext()) // fewer elements than expected return Arrays.copyOf(r, i); r[i] = it.next(); } return it.hasNext() ? finishToArray(r, it) : r; } /** * {@inheritDoc} * *

This implementation returns an array containing all the elements * returned by this collection's iterator in the same order, stored in * consecutive elements of the array, starting with index {@code 0}. * If the number of elements returned by the iterator is too large to * fit into the specified array, then the elements are returned in a * newly allocated array with length equal to the number of elements * returned by the iterator, even if the size of this collection * changes during iteration, as might happen if the collection permits * concurrent modification during iteration. The {@code size} method is * called only as an optimization hint; the correct result is returned * even if the iterator returns a different number of elements. * *

This method is equivalent to: * *

 {@code
     * List list = new ArrayList(size());
     * for (E e : this)
     *     list.add(e);
     * return list.toArray(a);
     * }
* * @throws ArrayStoreException {@inheritDoc} * @throws NullPointerException {@inheritDoc} */ public T[] toArray(T[] a) { // Estimate size of array; be prepared to see more or fewer elements int size = size(); T[] r = a.length >= size ? a : (T[])java.lang.reflect.Array .newInstance(a.getClass().getComponentType(), size); Iterator it = iterator(); for (int i = 0; i < r.length; i++) { if (! it.hasNext()) { // fewer elements than expected if (a == r) { r[i] = null; // null-terminate } else if (a.length < i) { return Arrays.copyOf(r, i); } else { System.arraycopy(r, 0, a, 0, i); if (a.length > i) { a[i] = null; } } return a; } r[i] = (T)it.next(); } // more elements than expected return it.hasNext() ? finishToArray(r, it) : r; } /** * The maximum size of array to allocate. * Some VMs reserve some header words in an array. * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit */ private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; /** * Reallocates the array being used within toArray when the iterator * returned more elements than expected, and finishes filling it from * the iterator. * * @param r the array, replete with previously stored elements * @param it the in-progress iterator over this collection * @return array containing the elements in the given array, plus any * further elements returned by the iterator, trimmed to size */ private static T[] finishToArray(T[] r, Iterator it) { int i = r.length; while (it.hasNext()) { int cap = r.length; if (i == cap) { int newCap = cap + (cap >> 1) + 1; // overflow-conscious code if (newCap - MAX_ARRAY_SIZE > 0) newCap = hugeCapacity(cap + 1); r = Arrays.copyOf(r, newCap); } r[i++] = (T)it.next(); } // trim if overallocated return (i == r.length) ? r : Arrays.copyOf(r, i); } private static int hugeCapacity(int minCapacity) { if (minCapacity < 0) // overflow throw new OutOfMemoryError ("Required array size too large"); return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } // Modification Operations /** * {@inheritDoc} * *

This implementation always throws an * UnsupportedOperationException. * * @throws UnsupportedOperationException {@inheritDoc} * @throws ClassCastException {@inheritDoc} * @throws NullPointerException {@inheritDoc} * @throws IllegalArgumentException {@inheritDoc} * @throws IllegalStateException {@inheritDoc} */ public boolean add(E e) { throw new UnsupportedOperationException(); } /** * {@inheritDoc} * *

This implementation iterates over the collection looking for the * specified element. If it finds the element, it removes the element * from the collection using the iterator's remove method. * *

Note that this implementation throws an * UnsupportedOperationException if the iterator returned by this * collection's iterator method does not implement the remove * method and this collection contains the specified object. * * @throws UnsupportedOperationException {@inheritDoc} * @throws ClassCastException {@inheritDoc} * @throws NullPointerException {@inheritDoc} */ public boolean remove(Object o) { Iterator it = iterator(); if (o==null) { while (it.hasNext()) { if (it.next()==null) { it.remove(); return true; } } } else { while (it.hasNext()) { if (o.equals(it.next())) { it.remove(); return true; } } } return false; } // Bulk Operations /** * {@inheritDoc} * *

This implementation iterates over the specified collection, * checking each element returned by the iterator in turn to see * if it's contained in this collection. If all elements are so * contained true is returned, otherwise false. * * @throws ClassCastException {@inheritDoc} * @throws NullPointerException {@inheritDoc} * @see #contains(Object) */ public boolean containsAll(Collection c) { for (Object e : c) if (!contains(e)) return false; return true; } /** * {@inheritDoc} * *

This implementation iterates over the specified collection, and adds * each object returned by the iterator to this collection, in turn. * *

Note that this implementation will throw an * UnsupportedOperationException unless add is * overridden (assuming the specified collection is non-empty). * * @throws UnsupportedOperationException {@inheritDoc} * @throws ClassCastException {@inheritDoc} * @throws NullPointerException {@inheritDoc} * @throws IllegalArgumentException {@inheritDoc} * @throws IllegalStateException {@inheritDoc} * * @see #add(Object) */ public boolean addAll(Collection c) { boolean modified = false; for (E e : c) if (add(e)) modified = true; return modified; } /** * {@inheritDoc} * *

This implementation iterates over this collection, checking each * element returned by the iterator in turn to see if it's contained * in the specified collection. If it's so contained, it's removed from * this collection with the iterator's remove method. * *

Note that this implementation will throw an * UnsupportedOperationException if the iterator returned by the * iterator method does not implement the remove method * and this collection contains one or more elements in common with the * specified collection. * * @throws UnsupportedOperationException {@inheritDoc} * @throws ClassCastException {@inheritDoc} * @throws NullPointerException {@inheritDoc} * * @see #remove(Object) * @see #contains(Object) */ public boolean removeAll(Collection c) { boolean modified = false; Iterator it = iterator(); while (it.hasNext()) { if (c.contains(it.next())) { it.remove(); modified = true; } } return modified; } /** * {@inheritDoc} * *

This implementation iterates over this collection, checking each * element returned by the iterator in turn to see if it's contained * in the specified collection. If it's not so contained, it's removed * from this collection with the iterator's remove method. * *

Note that this implementation will throw an * UnsupportedOperationException if the iterator returned by the * iterator method does not implement the remove method * and this collection contains one or more elements not present in the * specified collection. * * @throws UnsupportedOperationException {@inheritDoc} * @throws ClassCastException {@inheritDoc} * @throws NullPointerException {@inheritDoc} * * @see #remove(Object) * @see #contains(Object) */ public boolean retainAll(Collection c) { boolean modified = false; Iterator it = iterator(); while (it.hasNext()) { if (!c.contains(it.next())) { it.remove(); modified = true; } } return modified; } /** * {@inheritDoc} * *

This implementation iterates over this collection, removing each * element using the Iterator.remove operation. Most * implementations will probably choose to override this method for * efficiency. * *

Note that this implementation will throw an * UnsupportedOperationException if the iterator returned by this * collection's iterator method does not implement the * remove method and this collection is non-empty. * * @throws UnsupportedOperationException {@inheritDoc} */ public void clear() { Iterator it = iterator(); while (it.hasNext()) { it.next(); it.remove(); } } // String conversion /** * Returns a string representation of this collection. The string * representation consists of a list of the collection's elements in the * order they are returned by its iterator, enclosed in square brackets * ("[]"). Adjacent elements are separated by the characters * ", " (comma and space). Elements are converted to strings as * by {@link String#valueOf(Object)}. * * @return a string representation of this collection */ public String toString() { Iterator it = iterator(); if (! it.hasNext()) return "[]"; StringBuilder sb = new StringBuilder(); sb.append('['); for (;;) { E e = it.next(); sb.append(e == this ? "(this Collection)" : e); if (! it.hasNext()) return sb.append(']').toString(); sb.append(',').append(' '); } } }