/*
 * Copyright (c) 1997, 2018, Oracle and/or its affiliates. All rights reserved.
 * ORACLE PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

package java.util;

/**
 * This class provides a skeletal implementation of the {@code Collection}
 * interface, to minimize the effort required to implement this interface. <p>
 *
 * To implement an unmodifiable collection, the programmer needs only to
 * extend this class and provide implementations for the {@code iterator} and
 * {@code size} methods. (The iterator returned by the {@code iterator}
 * method must implement {@code hasNext} and {@code next}.)<p>
 *
 * To implement a modifiable collection, the programmer must additionally
 * override this class's {@code add} method (which otherwise throws an
 * {@code UnsupportedOperationException}), and the iterator returned by the
 * {@code iterator} method must additionally implement its {@code remove}
 * method.<p>
 *
 * The programmer should generally provide a void (no argument) and
 * {@code Collection} constructor, as per the recommendation in the
 * {@code Collection} interface specification.<p>
 *
 * 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.<p>
 *
 * This class is a member of the
 * <a href="{@docRoot}/java.base/java/util/package-summary.html#CollectionsFramework">
 * Java Collections Framework</a>.
 *
 * @author Josh Bloch
 * @author Neal Gafter
 * @see Collection
 * @since 1.2
 */

public abstract class AbstractCollection<E> implements Collection<E> {
 /**
 * 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<E> iterator();

 public abstract int size();

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

 /**
 * {@inheritDoc}
 *
 * @implSpec
 * 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<E> 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}
 *
 * @implSpec
 * 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.
 *
 * <p>This method is equivalent to:
 *
 * <pre> {@code
 * List<E> list = new ArrayList<E>(size());
 * for (E e : this)
 * list.add(e);
 * return list.toArray();
 * }</pre>
 */
 public Object[] toArray() {
 // Estimate size of array; be prepared to see more or fewer elements
 Object[] r = new Object[size()];
 Iterator<E> 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}
 *
 * @implSpec
 * 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.
 *
 * <p>This method is equivalent to:
 *
 * <pre> {@code
 * List<E> list = new ArrayList<E>(size());
 * for (E e : this)
 * list.add(e);
 * return list.toArray(a);
 * }</pre>
 *
 * @throws ArrayStoreException {@inheritDoc}
 * @throws NullPointerException {@inheritDoc}
 */
 @SuppressWarnings("unchecked")
 public <T> 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<E> 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
 */
 @SuppressWarnings("unchecked")
 private static <T> 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}
 *
 * @implSpec
 * This implementation always throws an
 * {@code 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}
 *
 * @implSpec
 * 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.
 *
 * <p>Note that this implementation throws an
 * {@code UnsupportedOperationException} if the iterator returned by this
 * collection's iterator method does not implement the {@code remove}
 * method and this collection contains the specified object.
 *
 * @throws UnsupportedOperationException {@inheritDoc}
 * @throws ClassCastException {@inheritDoc}
 * @throws NullPointerException {@inheritDoc}
 */
 public boolean remove(Object o) {
 Iterator<E> 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}
 *
 * @implSpec
 * 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 {@code true} is returned, otherwise {@code 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}
 *
 * @implSpec
 * This implementation iterates over the specified collection, and adds
 * each object returned by the iterator to this collection, in turn.
 *
 * <p>Note that this implementation will throw an
 * {@code UnsupportedOperationException} unless {@code 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<? extends E> c) {
 boolean modified = false;
 for (E e : c)
 if (add(e))
 modified = true;
 return modified;
 }

 /**
 * {@inheritDoc}
 *
 * @implSpec
 * 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 {@code remove} method.
 *
 * <p>Note that this implementation will throw an
 * {@code UnsupportedOperationException} if the iterator returned by the
 * {@code iterator} method does not implement the {@code 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) {
 Objects.requireNonNull(c);
 boolean modified = false;
 Iterator<?> it = iterator();
 while (it.hasNext()) {
 if (c.contains(it.next())) {
 it.remove();
 modified = true;
 }
 }
 return modified;
 }

 /**
 * {@inheritDoc}
 *
 * @implSpec
 * 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 {@code remove} method.
 *
 * <p>Note that this implementation will throw an
 * {@code UnsupportedOperationException} if the iterator returned by the
 * {@code iterator} method does not implement the {@code 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) {
 Objects.requireNonNull(c);
 boolean modified = false;
 Iterator<E> it = iterator();
 while (it.hasNext()) {
 if (!c.contains(it.next())) {
 it.remove();
 modified = true;
 }
 }
 return modified;
 }

 /**
 * {@inheritDoc}
 *
 * @implSpec
 * This implementation iterates over this collection, removing each
 * element using the {@code Iterator.remove} operation. Most
 * implementations will probably choose to override this method for
 * efficiency.
 *
 * <p>Note that this implementation will throw an
 * {@code UnsupportedOperationException} if the iterator returned by this
 * collection's {@code iterator} method does not implement the
 * {@code remove} method and this collection is non-empty.
 *
 * @throws UnsupportedOperationException {@inheritDoc}
 */
 public void clear() {
 Iterator<E> 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
 * ({@code "[]"}). Adjacent elements are separated by the characters
 * {@code ", "} (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<E> 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(' ');
 }
 }

}