package java.util;

/**
 * 这个类提供了几个实现了<tt>Collection</tt>接口的骨架，将实现这个接口的工作量最小化
 *
 * 当实现一个不可修改的集合时，开发者只需要去继承这个类并且实现<tt>iterator</tt>
 * 和<tt>size</tt>方法。(iterator方法将返回一个iterator对象，它必须实现 <tt>hasNext</tt> 
 * 和 <tt>next</tt>方法)
 *
 * 当实现一个可修改的集合时，开发者必须对这个类的<tt>add</tt>方法进行重写（否则将
 * 会抛出一个<tt>UnsupportedOperationException</tt>）,并且<tt>iterator</tt> 方法返回
 * 的iterator必须重写他的 <tt>remove</tt>方法
 *
 * 我们推荐开发者在<tt>Collection</tt>接口中，应提供一个无参数以及一个<tt>Collection</tt>
 * 构造器。
 *
 * 说明文档中需要详细描述这个类中的非抽象方法的实现。这个集合的每一个方法的重
 * 写，并且出现多个不同的实现
 *
 * 这个类是
 * <a href="{@docRoot}/../technotes/guides/collections/index.html">
 * Java Collections Framework中的成员</a>.
 *
 * @author  Josh Bloch
 * @author  Neal Gafter
 * @see Collection
 * @since 1.2
 */

public abstract class AbstractCollection<E> implements Collection<E> {
    /**
     * 唯一构造其。  (用于子类调用，典型的如隐式调用。)
     */
    protected AbstractCollection() {
    }

    // 查询操作

    /**
     * 返回一个迭代器，覆盖当前集合的元素。
     *
     * @return 一个覆盖了当前集合中的元素的迭代其
     */
    public abstract Iterator<E> iterator();

    public abstract int size();

    /**
     * {@inheritDoc}
     *
     * <p>这个实现返回 <tt>size() == 0</tt>.
     */
    public boolean isEmpty() {
        return size() == 0;
    }

    /**
     * {@inheritDoc}
     *
     * <p>使用迭代其覆盖当前集合中的元素，使用指定的元素与迭代中的每个元素比较是否相同。
     *
     * @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>即使当前结合在迭代期间发生了修改，例如这个集合允许并发修改时。返回
     * 数组的长度与迭代器返回元素的数量也将相同。 {@code size}方法仅作为优化点
     * 进行调用。即使迭代器返回了不同数量的元素，结果也将是正确的。
     *
     * <p>这个方法等同于:
     *
     *  <pre> {@code
     * List<E> list = new ArrayList<E>(size());
     * for (E e : this)
     *     list.add(e);
     * return list.toArray();
     * }</pre>
     */
    public Object[] toArray() {
        // 预估数组的大小;准备去查看多或少的元素
        Object[] r = new Object[size()];
        Iterator<E> it = iterator();
        for (int i = 0; i < r.length; i++) {
            if (! it.hasNext()) // 比预计的元素少
                return Arrays.copyOf(r, i);
            r[i] = it.next();
        }
        return it.hasNext() ? finishToArray(r, it) : r;
    }

    /**
     * {@inheritDoc}
     *
     * <p>这个实现返回一个包含了当前集合迭代器返回的全部元素与顺序，并且在数组
     * 中进行连续保存，起始索引为{@code 0}。及时当前集合的大小在迭代期间改变
     * 了，如当前集合允许并发修改，当迭代器返回的元素数量大于指定的数组时，这些
     * 元素将在一个长度与迭代器返回元素长度相同的新数组中返回;{@code size}方法的
     * 调用只用于优化;当迭代器返回了不同的数量，也将返回正确结果。
     *
     * <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) {
        // 预估数组大小;可能观察到的多或少的元素
        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()) { // 比预计的元素少
                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();
        }
        // 比预计的元素多
        return it.hasNext() ? finishToArray(r, it) : r;
    }

    /**
     * 数组可分配的最大大小。
     * 一些虚拟机会在数组中保存一些头字段。
     * 尝试去分配大数组可能会返回下面的结果
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * 当迭代器返回了过多的元素，以及数组被填满时，则重新分配
     *
     * @param r 已经被装满的数组
     * @param it 正在运行汇总的迭代器
     * @return 包含了给予数组的全部元素与从迭代器中取出的全部元素，并且数组长度与元素数量相同
     */
    @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;
    }

    // 修改操作

    /**
     * {@inheritDoc}
     *
     * <p>这个实现只会抛出<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>这个实现使用迭代遍历集合，并找出指定的元素。如果找到了这个元素，它将会被
     * 使用iterator的remove方法从集合中删除。
     *
     * <p>注意，如果当前集合的iterator方法返回的迭代器没有实现<tt>remove</tt>方法，当这个集合包含指定的元素时，这个实现将会抛出一个 <tt>UnsupportedOperationException</tt>。
     *
     * @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;
    }


    // 扩展方法

    /**
     * {@inheritDoc}
     *
     * <p>这个实现通过迭代指定的集合，检查每一个是否在当前集合中。如果全部元素都包
     * 含在当前集合集合中，则返回<tt>true</tt>。否则返回<tt>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}
     *
     * <p>这个实现迭代指定集合，并将迭代器返回的所有对象依次添加到当前集合中。
     *
     * <p>注意，这个实现将会<tt>add</tt>方法没有被重写时抛出<tt>UnsupportedOperationException</tt>(例如当指定集合非空时)。
     *
     * @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>这个实现通过迭代，检查指定集合中的每一个元素是否包含在当前集合中。如
     * 果包含，它将通过迭代器的<tt>remove</tt>方法从集合中删除
     *
     * <p>注意，这个实现将会在<tt>iterator</tt>方法返回的迭代器没有实现<tt>remove</tt>方法
     * 并且当前集合中有一个或多个元素存在与指定集合中时抛
     * 出<tt>UnsupportedOperationException</tt> 。
     *
     * @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}
     *
     * <p>这个实现通过迭代当前集合，依次检查每个元素，判断是否包含在制定
     * 集合中。如果不包含，它将通过迭代器的 <tt>remove</tt>方法删除。
     *
     * <p>注意，这个实现将会在<tt>iterator</tt>方法返回的迭代器没有实现 <tt>remove</tt> 
     * 方法并且当前集合有一个或多个元素不存在与指定的集合中时抛出
     * <tt>UnsupportedOperationException</tt> 。
     *
     * @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}
     *
     * <p>这个实现通过迭代结合，使用<tt>Iterator.remove</tt>操作删除所有的元素。大多
     * 数实现会使用更高效的方式重写这个方法。
     *
     * <p>注意，这个实现将会在<tt>iterator</tt> 方法返回的迭代器没有实现<tt>remove</tt>
     * 方法名且集合非空时抛出<tt>UnsupportedOperationException</tt> 
     *
     * @throws UnsupportedOperationException {@inheritDoc}
     */
    public void clear() {
        Iterator<E> it = iterator();
        while (it.hasNext()) {
            it.next();
            it.remove();
        }
    }


    //  字符串转换

    /**
     * 返回一个代表当前集合的字符串。这个字符串由当前集合的迭代器返回的元素按顺序
     * 组成，并使放括号包围(<tt>"[]"</tt>).  相邻的元素使用字符 <tt>", "</tt>(逗号与一个空格)
     * 分割。所有的元素将使用{@link String#valueOf(Object)}转换为字符串。
     *
     * @return a 代表当前集合的字符串
     */
    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(' ');
        }
    }

}

`