copyonwritearraylist.java

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

     * <em>equal</em> if <tt>(e1==null ? e2==null : e1.equals(e2))</tt>.)
     * In other words, two Lists are defined to be equal if they contain the
     * same elements in the same order.
     * <p>
     * This implementation first checks if the specified object is this
     * List. If so, it returns true; if not, it checks if the specified
     * object is a List. If not, it returns false; if so, it iterates over
     * both lists, comparing corresponding pairs of elements.  If any
     * comparison returns false, this method returns false.  If either
     * Iterator runs out of elements before the other it returns false
     * (as the Lists are of unequal length); otherwise it returns true when
     * the iterations complete.
     *
     * @param o the Object to be compared for equality with this List.
     * @return true if the specified Object is equal to this List.
     */
    public boolean equals(Object o) {
        if (o == this)
            return true;
        if (!(o instanceof List))
            return false;

        List l2 = (List)(o);
        if (size() != l2.size())
            return false;

        ListIterator e1 = listIterator();
        ListIterator e2 = l2.listIterator();
        while(e1.hasNext()) {
            Object o1 = e1.next();
            Object o2 = e2.next();
            if (!(o1==null ? o2==null : o1.equals(o2)))
                return false;
        }
        return true;
    }

    /**
     * Returns the hash code value for this List.
     *
     * <p> This implementation uses the definition in {@link
     * List#hashCode}.
     * @return the hash code
     */
    public int hashCode() {
        int hashCode = 1;
        Iterator i = iterator();
        while (i.hasNext()) {
            Object obj = i.next();
            hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
        }
        return hashCode;
    }

    /**
     * Returns an Iterator over the elements contained in this collection.
     * The iterator provides a snapshot of the state of the list
     * when the iterator was constructed. No synchronization is
     * needed while traversing the iterator. The iterator does
     * <em>NOT</em> support the <tt>remove</tt> method.
     * @return the iterator
     */
    public Iterator iterator() {
        return new COWIterator(array(), 0);
    }

    /**
     * Returns an Iterator of the elements in this List (in proper sequence).
     * The iterator provides a snapshot of the state of the list
     * when the iterator was constructed. No synchronization is
     * needed while traversing the iterator. The iterator does
     * <em>NOT</em> support the <tt>remove</tt>, <tt>set</tt>,
     * or <tt>add</tt> methods.
     * @return the iterator
     *
     */
    public ListIterator listIterator() {
        return new COWIterator(array(), 0);
    }

    /**
     * Returns a ListIterator of the elements in this List (in proper
     * sequence), starting at the specified position in the List.  The
     * specified index indicates the first element that would be returned by
     * an initial call to nextElement.  An initial call to previousElement
     * would return the element with the specified index minus one.
     * The ListIterator returned by this implementation will throw
     * an UnsupportedOperationException in its remove, set and
     * add methods.
     *
     * @param index index of first element to be returned from the
     *                ListIterator (by a call to getNext).
     * @return the iterator
     * @throws IndexOutOfBoundsException index is out of range
     *              (index &lt; 0 || index &gt; size()).
     */
    public ListIterator listIterator(final int index) {
        Object[] elementData = array();
        int len = elementData.length;
        if (index<0 || index>len)
            throw new IndexOutOfBoundsException("Index: "+index);

        return new COWIterator(array(), index);
    }

    private static class COWIterator implements ListIterator {

        /** Snapshot of the array **/
        private final Object[] array;

        /**
         * Index of element to be returned by subsequent call to next.
         */
        private int cursor;

        private COWIterator(Object[] elementArray, int initialCursor) {
            array = elementArray;
            cursor = initialCursor;
        }

        public boolean hasNext() {
            return cursor < array.length;
        }

        public boolean hasPrevious() {
            return cursor > 0;
        }

        public Object next() {
            try {
                return array[cursor++];
            } catch (IndexOutOfBoundsException ex) {
                throw new NoSuchElementException();
            }
        }

        public Object previous() {
            try {
                return array[--cursor];
            } catch(IndexOutOfBoundsException e) {
                throw new NoSuchElementException();
            }
        }

        public int nextIndex() {
            return cursor;
        }

        public int previousIndex() {
            return cursor-1;
        }

        /**
         * Not supported. Always throws UnsupportedOperationException.
         * @throws UnsupportedOperationException remove is not supported
         *            by this Iterator.
         */

        public void remove() {
            throw new UnsupportedOperationException();
        }

        /**
         * Not supported. Always throws UnsupportedOperationException.
         * @throws UnsupportedOperationException set is not supported
         *            by this Iterator.
         */
        public void set(Object o) {
            throw new UnsupportedOperationException();
        }

        /**
         * Not supported. Always throws UnsupportedOperationException.
         * @throws UnsupportedOperationException add is not supported
         *            by this Iterator.
         */
        public void add(Object o) {
            throw new UnsupportedOperationException();
        }
    }


    /**
     * Returns a view of the portion of this List between fromIndex,
     * inclusive, and toIndex, exclusive.  The returned List is backed by this
     * List, so changes in the returned List are reflected in this List, and
     * vice-versa.  While mutative operations are supported, they are
     * probably not very useful for CopyOnWriteArrayLists.
     * <p>
     * The semantics of the List returned by this method become undefined if
     * the backing list (i.e., this List) is <i>structurally modified</i> in
     * any way other than via the returned List.  (Structural modifications are
     * those that change the size of the List, or otherwise perturb it in such
     * a fashion that iterations in progress may yield incorrect results.)
     *
     * @param fromIndex low endpoint (inclusive) of the subList.
     * @param toIndex high endpoint (exclusive) of the subList.
     * @return a view of the specified range within this List.
     * @throws IndexOutOfBoundsException Illegal endpoint index value
     *     (fromIndex &lt; 0 || toIndex &gt; size || fromIndex &gt; toIndex).
     */
    public synchronized List subList(int fromIndex, int toIndex) {
        // synchronized since sublist constructor depends on it.
        int len = array.length;
        if (fromIndex<0 || toIndex>len  || fromIndex>toIndex)
            throw new IndexOutOfBoundsException();
        return new COWSubList(this, fromIndex, toIndex);
    }

    private static class COWSubList extends AbstractList {

        /*
          This class extends AbstractList merely for convenience, to
          avoid having to define addAll, etc. This doesn't hurt, but
          is wasteful.  This class does not need or use modCount
          mechanics in AbstractList, but does need to check for
          concurrent modification using similar mechanics.  On each
          operation, the array that we expect the backing list to use
          is checked and updated.  Since we do this for all of the
          base operations invoked by those defined in AbstractList,
          all is well.  While inefficient, this is not worth
          improving.  The kinds of list operations inherited from
          AbstractList are already so slow on COW sublists that
          adding a bit more space/time doesn't seem even noticeable.
         */

        private final CopyOnWriteArrayList l;
        private final int offset;
        private int size;
        private Object[] expectedArray;

        private COWSubList(CopyOnWriteArrayList list,
        int fromIndex, int toIndex) {
            l = list;
            expectedArray = l.array();
            offset = fromIndex;
            size = toIndex - fromIndex;
        }

        // only call this holding l's lock
        private void checkForComodification() {
            if (l.array != expectedArray)
                throw new ConcurrentModificationException();
        }

        // only call this holding l's lock
        private void rangeCheck(int index) {
            if (index<0 || index>=size)
                throw new IndexOutOfBoundsException("Index: "+index+ ",Size: "+size);
        }


        public Object set(int index, Object element) {
            synchronized(l) {
                rangeCheck(index);
                checkForComodification();
                Object x = l.set(index+offset, element);
                expectedArray = l.array;
                return x;
            }
        }

        public Object get(int index) {
            synchronized(l) {
                rangeCheck(index);
                checkForComodification();
                return l.get(index+offset);
            }
        }

        public int size() {
            synchronized(l) {
                checkForComodification();
                return size;
            }
        }

        public void add(int index, Object element) {
            synchronized(l) {
                checkForComodification();
                if (index<0 || index>size)
                    throw new IndexOutOfBoundsException();
                l.add(index+offset, element);
                expectedArray = l.array;
                size++;
            }
        }

        public void clear() {
            synchronized(l) {
                checkForComodification();
                l.removeRange(offset, offset+size);
                expectedArray = l.array;
                size = 0;
            }
        }

        public Object remove(int index) {
            synchronized(l) {
                rangeCheck(index);
                checkForComodification();
                Object result = l.remove(index+offset);
                expectedArray = l.array;
                size--;
                return result;
            }
        }

        public Iterator iterator() {
            synchronized(l) {
                checkForComodification();
                return new COWSubListIterator(l, 0, offset, size);
            }
        }

        public ListIterator listIterator(final int index) {
            synchronized(l) {
                checkForComodification();
                if (index<0 || index>size)
                    throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
                return new COWSubListIterator(l, index, offset, size);
            }
        }

        public List subList(int fromIndex, int toIndex) {
            synchronized(l) {
                checkForComodification();
                if (fromIndex<0 || toIndex>size)
                    throw new IndexOutOfBoundsException();
                return new COWSubList(l, fromIndex+offset, toIndex+offset);
            }
        }

    }


    private static class COWSubListIterator implements ListIterator {
        private final ListIterator i;
        private final int index;
        private final int offset;
        private final int size;
        private COWSubListIterator(List l, int index, int offset, int size) {
            this.index = index;
            this.offset = offset;
            this.size = size;
            i = l.listIterator(index+offset);
        }

        public boolean hasNext() {
            return nextIndex() < size;
        }

        public Object next() {
            if (hasNext())
                return i.next();
            else
                throw new NoSuchElementException();
        }

        public boolean hasPrevious() {
            return previousIndex() >= 0;
        }

        public Object previous() {
            if (hasPrevious())
                return i.previous();
            else
                throw new NoSuchElementException();
        }

        public int nextIndex() {
            return i.nextIndex() - offset;
        }

        public int previousIndex() {
            return i.previousIndex() - offset;
        }

        public void remove() {
            throw new UnsupportedOperationException();
        }

        public void set(Object o) {
            throw new UnsupportedOperationException();
        }

        public void add(Object o) {
            throw new UnsupportedOperationException();
        }
    }

}