Java基础系列（四十三）：集合之Vector&Stack

public class Vector<E>
        extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    /**
     *  用于存放集合元素的数组对象
     */
    protected Object[] elementData;

    /**
     *  数组中实际数据的长度
     */
    protected int elementCount;

    /**
     *  数组的大小大于其该集合容量时，容量自动增加的量。
     */
    protected int capacityIncrement;

    /**
     *  序列化id
     */
    private static final long serialVersionUID = -2767605614048989439L;

    /**
     * 构造函数
     * @param initialCapacity   初始大小
     * @param capacityIncrement 每次扩容的大小
     */
    public Vector(int initialCapacity, int capacityIncrement) {
        super();
        //如果初始长度小于0，抛出异常
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("Illegal Capacity: "+
                    initialCapacity);
        }
        //new一个Object数组,长度为initialCapacity
        this.elementData = new Object[initialCapacity];
        //将每次扩容大小赋给类capacityIncrement
        this.capacityIncrement = capacityIncrement;
    }

    /**
     * 构造函数
     * @param initialCapacity   初始大小
     */
    public Vector(int initialCapacity) {
        //默认扩容大小为0
        this(initialCapacity, 0);
    }

    /**
     * 无参构造
     */
    public Vector() {
        //默认初始大小为10
        this(10);
    }

    /**
     * 构造函数
     * @param c 参数传入的是一个集合
     */
    public Vector(Collection<? extends E> c) {
        //首先将c转化为数组赋给elementData
        elementData = c.toArray();
        elementCount = elementData.length;
        //如果该数组的类型不为Object[],则转换为Object[]
        if (elementData.getClass() != Object[].class) {
            elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
        }
    }

    /**
     * 将集合复制到某个集合中
     * @param anArray   复制的目标
     */
    public synchronized void copyInto(Object[] anArray) {
        System.arraycopy(elementData, 0, anArray, 0, elementCount);
    }

    /**
     * 这里的意思是将多余的容量(即由于动态扩容导致的数组长度可能会大于数据的长度部分)删除
     */
    public synchronized void trimToSize() {
        modCount++;
        //数组的长度
        int oldCapacity = elementData.length;
        //如果数据的长度小于数组的长度，将动态增长的部分去掉
        if (elementCount < oldCapacity) {
            elementData = Arrays.copyOf(elementData, elementCount);
        }
    }

    /**
     * 扩容方法
     * @param minCapacity   需要的最小容量
     */
    public synchronized void ensureCapacity(int minCapacity) {
        //判断后，将修改值增加1
        if (minCapacity > 0) {
            modCount++;
            ensureCapacityHelper(minCapacity);
        }
    }

    /**
     * 扩容桥方法
     * @param minCapacity 需要的最小容量
     */
    private void ensureCapacityHelper(int minCapacity) {
        //如果需要的最小容量大于当前数组的长度，调用扩容方法
        if (minCapacity - elementData.length > 0) {
            grow(minCapacity);
        }
    }

    /**
     * 集合最大长度为Integer的最大值-8，
     * 因为数组作为一个对象，需要一定的内存存储对象头信息，对象头信息最大占用内存不可超过8 byte
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    /**
     * 扩容方法实现
     * @param minCapacity 需要的最小容量
     */
    private void grow(int minCapacity) {
        //获取当前数组的长度
        int oldCapacity = elementData.length;
        //如果设置了自动扩容的长度，就按照自动扩容的长度，否则翻倍
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                capacityIncrement : oldCapacity);
        //如果新的长度小于该数组需要的最小长度，将该最小长度赋给newCapacity
        if (newCapacity - minCapacity < 0) {
            newCapacity = minCapacity;
        }
        //如果新的长度大于数组最大长度
        if (newCapacity - MAX_ARRAY_SIZE > 0) {
            //调用这个检查是否超过Integer的最大值，这里体现了设计的严谨，实际上这里很少会去调用
            newCapacity = hugeCapacity(minCapacity);
        }
        //最后按照新的长度将数组信息拷贝到一个新的数组对象中后赋给原数组对象
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    /**
     * 用于判断集合的值会不会溢出，一般很少会调用到这个方法
     * @param minCapacity
     * @return
     */
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) {
            throw new OutOfMemoryError();
        }
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }

    /**
     * 给该集合容器设置新的大小
     * @param newSize
     */
    public synchronized void setSize(int newSize) {
        modCount++;
        //如果设置的长度大于该数组的长度，进行扩容
        if (newSize > elementCount) {
            ensureCapacityHelper(newSize);
        } else {
            //反之将超出newSize的部分赋予null
            for (int i = newSize ; i < elementCount ; i++) {
                elementData[i] = null;
            }
        }
        //将新的长度赋给数组的长度
        elementCount = newSize;
    }


    /**
     * 获取当前数组的长度
     * @return  返回的是当前数组对象的长度
     */
    public synchronized int capacity() {
        return elementData.length;
    }


    /**
     * 返回的是数组中数据的长度，因为由于动态扩容，数据的长度可能会小于数组的长度
     * @return  返回的是数组中数组的长度
     */
    @Override
    public synchronized int size() {
        return elementCount;
    }

    

    /**
     * 返回此集合的组件的枚举。返回的 Enumeration 对象将生成此向量中的所有项。生成的第一项为索引0处的项，然后是索引1处的项。
     * @return  此集合的组件的枚举
     */
    public Enumeration<E> elements() {

        //返回的是一个内部类
        return new Enumeration<E>() {

            /**
             * 枚举的索引
             */
            int count = 0;

            /**
             *  是否有下一个枚举项
             */
            @Override
            public boolean hasMoreElements() {
                return count < elementCount;
            }

            /**
             * 获取下一个枚举项
             * @return  返回的是下一位索引的枚举
             */
            @Override
            public E nextElement() {
                synchronized (Vector.this) {
                    if (count < elementCount) {
                        //将索引+1
                        return elementData(count++);
                    }
                }
                throw new NoSuchElementException("Vector Enumeration");
            }
        };
    }

    

    /**
     * 判断某个元素相对于某个索引开始的索引值
     * @param o 用于判断的元素
     * @param index 相对位置的索引
     * @return  返回的是相对于index的索引值
     */
    public synchronized int indexOf(Object o, int index) {
        //分为两种情况进行判断为null和不为null
        if (o == null) {
            for (int i = index ; i < elementCount ; i++) {
                if (elementData[i]==null) {
                    return i;
                }
            }
        } else {
            for (int i = index ; i < elementCount ; i++) {
                if (o.equals(elementData[i])) {
                    return i;
                }
            }
        }
        //如果不存在，返回-1
        return -1;
    }

   

    /**
     * 返回该集合中某个索引位置的元素
     * @param index 索引值
     * @return  位于该集合中索引值的元素
     */
    public synchronized E elementAt(int index) {
        //如果索引值大于数组长度，抛出一个异常
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " + elementCount);
        }
        //返回位于该索引的元素
        return elementData(index);
    }


    /**
     * 返回该集合中的第一个元素
     * @return  该集合中的第一个元素
     */
    public synchronized E firstElement() {
        //如果集合为空，抛出一个异常
        if (elementCount == 0) {
            throw new NoSuchElementException();
        }
        return elementData(0);
    }

    /**
     * 返回该集合中的最后一个元素
     * @return  返回该集合中的最后一个元素
     */
    public synchronized E lastElement() {
        //如果集合为空，抛出一个异常
        if (elementCount == 0) {
            throw new NoSuchElementException();
        }
        return elementData(elementCount - 1);
    }

    /**
     * 将某个对象赋予集合中的某个索引位置
     * @param obj   赋予某个对象
     * @param index 索引值
     */
    public synchronized void setElementAt(E obj, int index) {
        //如果索引值大于数组长度，抛出一个异常
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
                    elementCount);
        }
        //将obj赋给数组中的第index项
        elementData[index] = obj;
    }

    /**
     * 删除位于某个位置的元素
     * @param index 该位置的索引值
     */
    public synchronized void removeElementAt(int index) {
        modCount++;
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index + " >= " +
                    elementCount);
        }
        else if (index < 0) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        int j = elementCount - index - 1;
        if (j > 0) {
            //arraycopy的含义是将elementData数组里从索引为index + 1的元素开始, 复制到数组elementData里的索引为index的位置, 复制的元素个数为j个.
            //相当于用后两个代替了后三个，将位于index位置的元素删除
            System.arraycopy(elementData, index + 1, elementData, index, j);
        }
        elementCount--;
        //删除后，将最后一位置为null
        elementData[elementCount] = null;
    }

    /**
     * 在某个位置添加元素
     * @param obj   需要添加的元素
     * @param index 需要添加的位置
     */
    public synchronized void insertElementAt(E obj, int index) {
        modCount++;
        if (index > elementCount) {
            throw new ArrayIndexOutOfBoundsException(index
                    + " > " + elementCount);
        }
        //将数组的长度扩大一
        ensureCapacityHelper(elementCount + 1);
        //和remove的原理类似，将位于index项后的拷贝到index+1位置，相当于在index位置元素复制一个元素
        System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
        //将obj赋予数组位于index的位置
        elementData[index] = obj;
        elementCount++;
    }

    /**
     * 在元素的末尾添加一个元素
     * @param obj   需要添加的元素
     */
    public synchronized void addElement(E obj) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = obj;
    }


    /**
     * 删除某个元素
     * @param obj   需要删除的元素
     * @return  删除成功返回true，删除失败返回fasle
     */
    public synchronized boolean removeElement(Object obj) {
        modCount++;
        int i = indexOf(obj);
        if (i >= 0) {
            removeElementAt(i);
            return true;
        }
        return false;
    }

    /**
     * 删除所有元素
     */
    public synchronized void removeAllElements() {
        modCount++;
        for (int i = 0; i < elementCount; i++) {
            elementData[i] = null;
        }

        elementCount = 0;
    }

    /**
     * 克隆一个新对象
     * @return  返回的是克隆得到的对象
     */
    @Override
    public synchronized Object clone() {
        try {
            @SuppressWarnings("unchecked")
            Vector<E> v = (Vector<E>) super.clone();
            v.elementData = Arrays.copyOf(elementData, elementCount);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            // this shouldn't happen, since we are Cloneable
            throw new InternalError(e);
        }
    }

    /**
     * 将该集合转化为数组
     * @return  返回的是转化后的数组
     */
    @Override
    public synchronized Object[] toArray() {
        return Arrays.copyOf(elementData, elementCount);
    }

    /**
     * 将该集合转化为某种类型的数组
     * @param a 需要转化的类型
     * @param <T>   返回的数组类型
     * @return  返回的数组
     */
    @Override
    @SuppressWarnings("unchecked")
    public synchronized <T> T[] toArray(T[] a) {
        if (a.length < elementCount) {
            return (T[]) Arrays.copyOf(elementData, elementCount, a.getClass());
        }

        System.arraycopy(elementData, 0, a, 0, elementCount);

        if (a.length > elementCount) {
            a[elementCount] = null;
        }

        return a;
    }

    /**
     * 将某个索引的位置设置为某个元素
     * @param index 索引
     * @param element   将该对象替代该索引位置的元素
     * @return  返回的是被替代的元素
     */
    @Override
    public synchronized E set(int index, E element) {
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index);
        }

        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }


    /**
     * 在合的末尾添加一个元素
     * @param e 需要添加的元素
     * @return  添加成功返回true，添加失败返回false
     */
    @Override
    public synchronized boolean add(E e) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = e;
        return true;
    }

 
    /**
     * 删除位于某个索引位置的元素
     * @param index 索引值
     * @return  删除的元素
     */
    @Override
    public synchronized E remove(int index) {
        modCount++;
        if (index >= elementCount) {
            throw new ArrayIndexOutOfBoundsException(index);
        }
        E oldValue = elementData(index);

        int numMoved = elementCount - index - 1;
        if (numMoved > 0) {
            System.arraycopy(elementData, index+1, elementData, index,
                    numMoved);
        }
        elementData[--elementCount] = null;

        return oldValue;
    }

   
    
    
    /**
     * 在指定位置将指定 Collection 中的所有元素插入到此集合中。
     * 将当前位于该位置的元素（如果有）及所有后续元素右移（增大其索引值）。
     * 新元素在集合中按照其由指定 collection 的迭代器所返回的顺序出现。
     * @param index 要插入指定 collection 的第一个元素的索引
     * @param c 要插入到此集合的元素
     * @return 如果此向量由于调用而更改，则返回 true
     */
    @Override
    public synchronized boolean addAll(int index, Collection<? extends E> c) {
        modCount++;
        //索引越界抛出异常
        if (index < 0 || index > elementCount) {
            throw new ArrayIndexOutOfBoundsException(index);
        }

        Object[] a = c.toArray();
        int numNew = a.length;
        ensureCapacityHelper(elementCount + numNew);

        int numMoved = lementCount - index;
        if (numMoved > 0) {
            System.arraycopy(elementData, index, elementData, index + numNew,
                    numMoved);
        }

        System.arraycopy(a, 0, elementData, index, numNew);
        elementCount += numNew;
        return numNew != 0;
    }

  
    /**
     * 从此 List 中移除其索引位于 fromIndex（包括）与 toIndex（不包括）之间的所有元素
     * @param fromIndex 要移除的第一个元素的索引
     * @param toIndex   要移除的最后一个元素之后的索引
     */
    @Override
    protected synchronized void removeRange(int fromIndex, int toIndex) {
        modCount++;
        int numMoved = elementCount - toIndex;
        System.arraycopy(elementData, toIndex, elementData, fromIndex,
                numMoved);

        int newElementCount = elementCount - (toIndex-fromIndex);
        while (elementCount != newElementCount) {
            elementData[--elementCount] = null;
        }
    }

   
    /**
     * 这里Itr和ListItr的实现和AbstractList中的实现并没有太大的区别，具体的可以参考AbstractList中的实现
     */
      
    /**
     * 遍历集合，这里传入的是一个函数式接口，可以配合lambda表达式来使用
     *      用法如下     c.forEach(cStr -> System.out.prinltn(cStr))
     * @param action    所做的操作
     */
    @Override
    public synchronized void forEach(Consumer<? super E> action) {
        Objects.requireNonNull(action);
        final int expectedModCount = modCount;
        @SuppressWarnings("unchecked")
        final E[] elementData = (E[]) this.elementData;
        final int elementCount = this.elementCount;
        for (int i=0; modCount == expectedModCount && i < elementCount; i++) {
            action.accept(elementData[i]);
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

    /**
     * 这里传入的是同样是一个函数式接口，用于判断条件的过滤器，可以配合lambda表达式来使用，符合条件的会被删除
     * @param filter    过滤条件
     * @return
     */
    @Override
    @SuppressWarnings("unchecked")
    public synchronized boolean removeIf(Predicate<? super E> filter) {
        Objects.requireNonNull(filter);
        int removeCount = 0;
        final int size = elementCount;
        final BitSet removeSet = new BitSet(size);
        final int expectedModCount = modCount;
        for (int i=0; modCount == expectedModCount && i < size; i++) {
            @SuppressWarnings("unchecked")
            final E element = (E) elementData[i];
            if (filter.test(element)) {
                removeSet.set(i);
                removeCount++;
            }
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }


        final boolean anyToRemove = removeCount > 0;
        if (anyToRemove) {
            final int newSize = size - removeCount;
            for (int i=0, j=0; (i < size) && (j < newSize); i++, j++) {
                i = removeSet.nextClearBit(i);
                elementData[j] = elementData[i];
            }
            for (int k=newSize; k < size; k++) {
                elementData[k] = null;
            }
            elementCount = newSize;
            if (modCount != expectedModCount) {
                throw new ConcurrentModificationException();
            }
            modCount++;
        }

        return anyToRemove;
    }

    /**
     * 对集合进行全部进行一元操作后替换原有集合，传入的是一个一元操作的函数式接口
     * @param operator 一元操作
     */
    @Override
    @SuppressWarnings("unchecked")
    public synchronized void replaceAll(UnaryOperator<E> operator) {
        Objects.requireNonNull(operator);
        final int expectedModCount = modCount;
        final int size = elementCount;
        for (int i=0; modCount == expectedModCount && i < size; i++) {
            elementData[i] = operator.apply((E) elementData[i]);
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }

    /**
     * 根据指定的排序函数进行排序，传入的是一个函数式接口，可以配合lambda表达式使用
     * @param c
     */
    @SuppressWarnings("unchecked")
    @Override
    public synchronized void sort(Comparator<? super E> c) {
        final int expectedModCount = modCount;
        Arrays.sort((E[]) elementData, 0, elementCount, c);
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
        modCount++;
    }


    /**
     * 因为字数限制，Spliterator源码部分可以去Github上下载后阅读，或者去其他平台看
     * 
}

public class Stack<E> extends Vector<E> {

    /**
     * Stack的无参构造函数
     */
    public Stack() {
    }

    /**
     * 把项压入堆栈顶部
     */
    public E push(E item) {
        addElement(item);
        return item;
    }

    /**
     * 移除堆栈顶部的对象，并作为此函数的值返回该对象。
     * @return  被移除的对象
     */
    public synchronized E pop() {
        E obj;
        int len = size();

        obj = peek();
        removeElementAt(len - 1);

        return obj;
    }

    /**
     * 查看堆栈顶部的对象
     * @return
     */
    public synchronized E peek() {
        int len = size();
        if (len == 0) {
            throw new EmptyStackException();
        }
        return elementAt(len - 1);
    }

    /**
     * 测试堆栈是否为空
     * @return
     */
    public boolean empty() {
        return size() == 0;
    }

    /**
     * 返回对象在堆栈中的位置，以 1 为基数
     * @param o 需要查找位置的对象
     * @return
     */
    public synchronized int search(Object o) {
        int i = lastIndexOf(o);

        if (i >= 0) {
            return size() - i;
        }
        return -1;
    }

    /**
     * 版本id
     */
    private static final long serialVersionUID = 1224463164541339165L;

}