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