Request for review : 7121314 : Behavior mismatch between AbstractCollection.toArray(T[] ) and its spec (original) (raw)

Wed Mar 28 05:01:03 UTC 2012

// 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}
 *
 * <p>This implementation returns <tt>size() == 0</tt>.
 */
public boolean isEmpty() {
    return size() == 0;
}

/**
 * {@inheritDoc}
 *
 * <p>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}
 *
 * <p>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();
    int i = 0;
    while (i < r.length) {
        if (!it.hasNext()) // fewer elements than expected
            return Arrays.copyOf(r, i);
        r[i++] = it.next();
    }
    return finishToArray(r, i, it);
}

/**
 * {@inheritDoc}
 *
 * <p>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}
 */
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();
    int i = 0;
    while (i < r.length) {
        if (!it.hasNext()) { // fewer elements than expected
            if (a == r) {
                a[i] = null; // null-terminate
            } else if (a.length < i) {
                return Arrays.copyOf(r, i);
            } else { // Element r[i+1] is guaranteed to be null from array initialization.
                System.arraycopy(r, 0, a, 0, a.length > i ? i+1 : i); // ensure null-termination
            }
            return a;
        }
        r[i++] = (T)it.next();
    }
    return finishToArray(r, i, it);
}

/**
 * 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 i the current index, likewise capacity of r
 * @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 <T> T[] finishToArray(T[] r, int i, Iterator<E> it) {
    // if more elements than expected
    for (int cap = i; it.hasNext(); i++) {
        if (i == cap) {
            cap = secureArraySize(i, (Math.max(0, size() - i) << 1) + 1);
            //cap = secureArraySize(i, (i >> 4) + 1); // alternative !
            r = Arrays.copyOf(r, cap);
        }
        r[i] = (T)it.next();
    }
    return (i == r.length) ? // trim if overallocated
            r : Arrays.copyOf(r, i);
}

/**
 * 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;

/**
 * @param old the current size of the array
 * @param inc the requested increment
 */
private int secureArraySize(int old, int inc) {
    // overflow-conscious code
    if (old + inc - MAX_ARRAY_SIZE <= 0)
        return old + inc;
    if (++old < 0) // overflow
        throw new OutOfMemoryError
                ("Required array size exceeds VM limit");
    return (old > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE : MAX_ARRAY_SIZE;
}

// Modification Operations

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

/**
 * {@inheritDoc}
 *
 * <p>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
 * <tt>UnsupportedOperationException</tt> if the iterator returned by this
 * collection's iterator method does not implement the <tt>remove</tt>
 * 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}
 *
 * <p>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 <tt>true</tt> is returned, otherwise <tt>false</tt>.
 *
 * @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}
 *
 * <p>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
 * <tt>UnsupportedOperationException</tt> unless <tt>add</tt> 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}
 *
 * <p>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 <tt>remove</tt> method.
 *
 * <p>Note that this implementation will throw an
 * <tt>UnsupportedOperationException</tt> if the iterator returned by the
 * <tt>iterator</tt> method does not implement the <tt>remove</tt> 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}
 *
 * <p>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 <tt>remove</tt> method.
 *
 * <p>Note that this implementation will throw an
 * <tt>UnsupportedOperationException</tt> if the iterator returned by the
 * <tt>iterator</tt> method does not implement the <tt>remove</tt> 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<E> it = iterator();
    while (it.hasNext()) {
        if (!c.contains(it.next())) {
            it.remove();
            modified = true;
        }
    }
    return modified;
}

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