copyonwritearraylist.java

来自「SRI international 发布的OAA框架软件」· Java 代码 · 共 1,179 行 · 第 1/3 页

        if (index > len || index < 0)
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+len);

        Object[] newArray = (Object[]) new Object[len+1];
        System.arraycopy(array, 0, newArray, 0, index);
        newArray[index] = element;
        System.arraycopy(array, index, newArray, index+1, len - index);
        array = newArray;
    }

    /**
     * Removes the element at the specified position in this list.
     * Shifts any subsequent elements to the left (subtracts one from their
     * indices).
     *
     * @param index the index of the element to removed.
     * @return the element that was removed from the list.
     * @throws    IndexOutOfBoundsException if index out of range <tt>(index
     *            &lt; 0 || index &gt;= size())</tt>.
     */
    public synchronized Object remove(int index) {
        int len = array.length;
        rangeCheck(index, len);
        Object oldValue = array[index];
        Object[] newArray = (Object[]) new Object[len-1];
        System.arraycopy(array, 0, newArray, 0, index);
        int numMoved = len - index - 1;
        if (numMoved > 0)
            System.arraycopy(array, index+1, newArray, index, numMoved);
        array = newArray;
        return oldValue;
    }

    /**
     * Removes a single instance of the specified element from this
     * list, if it is present (optional operation).  More formally,
     * removes an element <tt>e</tt> such that <tt>(o==null ? e==null :
     * o.equals(e))</tt>, if the list contains one or more such
     * elements.  Returns <tt>true</tt> if the list contained the
     * specified element (or equivalently, if the list changed as a
     * result of the call).<p>
     *
     * @param o element to be removed from this list, if present.
     * @return <tt>true</tt> if the list contained the specified element.
     */
    public synchronized boolean remove(Object o) {
        int len = array.length;
        if (len == 0) return false;

        // Copy while searching for element to remove
        // This wins in the normal case of element being present

        int newlen = len-1;
        Object[] newArray = (Object[]) new Object[newlen];

        for (int i = 0; i < newlen; ++i) {
            if (o == array[i] ||
            (o != null && o.equals(array[i]))) {
                // found one;  copy remaining and exit
                for (int k = i + 1; k < len; ++k) newArray[k-1] = array[k];
                array = newArray;
                return true;
            } else
                newArray[i] = array[i];
        }
        // special handling for last cell

        if (o == array[newlen] ||
        (o != null && o.equals(array[newlen]))) {
            array = newArray;
            return true;
        } else
            return false; // throw away copy
    }


    /**
     * Removes from this List all of the elements whose index is between
     * fromIndex, inclusive and toIndex, exclusive.  Shifts any succeeding
     * elements to the left (reduces their index).
     * This call shortens the list by <tt>(toIndex - fromIndex)</tt> elements.
     * (If <tt>toIndex==fromIndex</tt>, this operation has no effect.)
     *
     * @param fromIndex index of first element to be removed.
     * @param toIndex index after last element to be removed.
     * @throws IndexOutOfBoundsException fromIndex or toIndex out of
     *              range (fromIndex &lt; 0 || fromIndex &gt;= size() || toIndex
     *              &gt; size() || toIndex &lt; fromIndex).
     */
    private synchronized void removeRange(int fromIndex, int toIndex) {
        int len = array.length;

        if (fromIndex < 0 || fromIndex >= len ||
        toIndex > len || toIndex < fromIndex)
            throw new IndexOutOfBoundsException();

        int numMoved = len - toIndex;
        int newlen = len - (toIndex-fromIndex);
        Object[] newArray = (Object[]) new Object[newlen];
        System.arraycopy(array, 0, newArray, 0, fromIndex);
        System.arraycopy(array, toIndex, newArray, fromIndex, numMoved);
        array = newArray;
    }


    /**
     * Append the element if not present.
     * @param element element to be added to this Collection, if absent.
     * @return true if added
     **/
    public synchronized boolean addIfAbsent(Object element) {
        // Copy while checking if already present.
        // This wins in the most common case where it is not present
        int len = array.length;
        Object[] newArray = (Object[]) new Object[len + 1];
        for (int i = 0; i < len; ++i) {
            if (element == array[i] ||
            (element != null && element.equals(array[i])))
                return false; // exit, throwing away copy
            else
                newArray[i] = array[i];
        }
        newArray[len] = element;
        array = newArray;
        return true;
    }

    /**
     * Returns true if this Collection contains all of the elements in the
     * specified Collection.
     * <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
     * true is returned, otherwise false.
     * @param c the collection
     * @return true if all elements are contained
     */
    public boolean containsAll(Collection c) {
        Object[] elementData = array();
        int len = elementData.length;
        Iterator e = c.iterator();
        while (e.hasNext())
            if (indexOf(e.next(), elementData, len) < 0)
                return false;

        return true;
    }


    /**
     * Removes from this Collection all of its elements that are contained in
     * the specified Collection. This is a particularly expensive operation
     * in this class because of the need for an internal temporary array.
     * <p>
     *
     * @param c the collection
     * @return true if this Collection changed as a result of the call.
     */
    public synchronized boolean removeAll(Collection c) {
        Object[] elementData = array;
        int len = elementData.length;
        if (len == 0) return false;

        // temp array holds those elements we know we want to keep
        Object[] temp = (Object[]) new Object[len];
        int newlen = 0;
        for (int i = 0; i < len; ++i) {
            Object element = elementData[i];
            if (!c.contains(element)) {
                temp[newlen++] = element;
            }
        }

        if (newlen == len) return false;

        //  copy temp as new array
        Object[] newArray = (Object[]) new Object[newlen];
        System.arraycopy(temp, 0, newArray, 0, newlen);
        array = newArray;
        return true;
    }

    /**
     * Retains only the elements in this Collection that are contained in the
     * specified Collection (optional operation).  In other words, removes from
     * this Collection all of its elements that are not contained in the
     * specified Collection.
     * @param c the collection
     * @return true if this Collection changed as a result of the call.
     */
    public synchronized boolean retainAll(Collection c) {
        Object[] elementData = array;
        int len = elementData.length;
        if (len == 0) return false;

        Object[] temp = (Object[]) new Object[len];
        int newlen = 0;
        for (int i = 0; i < len; ++i) {
            Object element = elementData[i];
            if (c.contains(element)) {
                temp[newlen++] = element;
            }
        }

        if (newlen == len) return false;

        Object[] newArray = (Object[]) new Object[newlen];
        System.arraycopy(temp, 0, newArray, 0, newlen);
        array = newArray;
        return true;
    }

    /**
     * Appends all of the elements in the specified Collection that
     * are not already contained in this list, to the end of
     * this list, in the order that they are returned by the
     * specified Collection's Iterator.
     *
     * @param c elements to be added into this list.
     * @return the number of elements added
     */
    public synchronized int addAllAbsent(Collection c) {
        int numNew = c.size();
        if (numNew == 0) return 0;

        Object[] elementData = array;
        int len = elementData.length;

        Object[] temp = (Object[]) new Object[numNew];
        int added = 0;
        Iterator e = c.iterator();
        while (e.hasNext()) {
            Object element = e.next();
            if (indexOf(element, elementData, len) < 0) {
                if (indexOf(element, temp, added) < 0) {
                    temp[added++] = element;
                }
            }
        }

        if (added == 0) return 0;

        Object[] newArray = (Object[]) new Object[len+added];
        System.arraycopy(elementData, 0, newArray, 0, len);
        System.arraycopy(temp, 0, newArray, len, added);
        array = newArray;
        return added;
    }

    /**
     * Removes all of the elements from this list.
     *
     */
    public synchronized void clear() {
        array = (Object[]) new Object[0];
    }

    /**
     * Appends all of the elements in the specified Collection to the end of
     * this list, in the order that they are returned by the
     * specified Collection's Iterator.
     *
     * @param c elements to be inserted into this list.
     * @return true if any elements are added
     */
    public synchronized boolean addAll(Collection c) {
        int numNew = c.size();
        if (numNew == 0) return false;

        int len = array.length;
        Object[] newArray = (Object[]) new Object[len+numNew];
        System.arraycopy(array, 0, newArray, 0, len);
        Iterator e = c.iterator();
        for (int i=0; i<numNew; i++)
            newArray[len++] = e.next();
        array = newArray;

        return true;
    }

    /**
     * Inserts all of the elements in the specified Collection into this
     * list, starting at the specified position.  Shifts the element
     * currently at that position (if any) and any subsequent elements to
     * the right (increases their indices).  The new elements will appear
     * in the list in the order that they are returned by the
     * specified Collection's iterator.
     *
     * @param index index at which to insert first element
     *                from the specified collection.
     * @param c elements to be inserted into this list.
     * @throws IndexOutOfBoundsException index out of range (index
     *              &lt; 0 || index &gt; size()).
     * @return true if any elements are added
     */
    public synchronized boolean addAll(int index, Collection c) {
        int len = array.length;
        if (index > len || index < 0)
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+len);

        int numNew = c.size();
        if (numNew == 0) return false;

        Object[] newArray = (Object[]) new Object[len+numNew];
        System.arraycopy(array, 0, newArray, 0, len);
        int numMoved = len - index;
        if (numMoved > 0)
            System.arraycopy(array, index, newArray, index + numNew, numMoved);
        Iterator e = c.iterator();
        for (int i=0; i<numNew; i++)
            newArray[index++] = e.next();
        array = newArray;

        return true;
    }

    /**
     * Check if the given index is in range.  If not, throw an appropriate
     * runtime exception.
     */
    private void rangeCheck(int index, int length) {
        if (index >= length || index < 0)
            throw new IndexOutOfBoundsException("Index: "+index+", Size: "+ length);
    }

    /**
     * Save the state of the list to a stream (i.e., serialize it).
     *
     * @serialData The length of the array backing the list is emitted
     *               (int), followed by all of its elements (each an Object)
     *               in the proper order.
     * @param s the stream
     */
    private void writeObject(java.io.ObjectOutputStream s)
        throws java.io.IOException{

        // Write out element count, and any hidden stuff
        s.defaultWriteObject();

        Object[] elementData = array();
        // Write out array length
        s.writeInt(elementData.length);

        // Write out all elements in the proper order.
        for (int i=0; i<elementData.length; i++)
            s.writeObject(elementData[i]);
    }

    /**
     * Reconstitute the list from a stream (i.e., deserialize it).
     * @param s the stream
     */
    private void readObject(java.io.ObjectInputStream s)
        throws java.io.IOException, ClassNotFoundException {

        // Read in size, and any hidden stuff
        s.defaultReadObject();

        // Read in array length and allocate array
        int arrayLength = s.readInt();
        Object[] elementData = (Object[]) new Object[arrayLength];

        // Read in all elements in the proper order.
        for (int i=0; i<elementData.length; i++)
            elementData[i] = (Object) s.readObject();
        array = elementData;
    }

    /**
     * Returns a string representation of this Collection, containing
     * the String representation of each element.
     */
    public String toString() {
        StringBuffer buf = new StringBuffer();
        Iterator e = iterator();
        buf.append("[");
        int maxIndex = size() - 1;
        for (int i = 0; i <= maxIndex; i++) {
            buf.append(String.valueOf(e.next()));
            if (i < maxIndex)
                buf.append(", ");
        }
        buf.append("]");
        return buf.toString();
    }


    /**
     * Compares the specified Object with this List for equality.  Returns true
     * if and only if the specified Object is also a List, both Lists have the
     * same size, and all corresponding pairs of elements in the two Lists are
     * <em>equal</em>.  (Two elements <tt>e1</tt> and <tt>e2</tt> are