fastarraylist.java

初级java程序员如果想要更深一步提高自己的实力

/*
 *  Copyright 2001-2005 The Apache Software Foundation
 *
 *  Licensed under the Apache License, Version 2.0 (the "License");
 *  you may not use this file except in compliance with the License.
 *  You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 *  Unless required by applicable law or agreed to in writing, software
 *  distributed under the License is distributed on an "AS IS" BASIS,
 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 *  See the License for the specific language governing permissions and
 *  limitations under the License.
 */
package org.apache.commons.collections;

import java.util.ArrayList;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

/**
 * <p>A customized implementation of <code>java.util.ArrayList</code> designed
 * to operate in a multithreaded environment where the large majority of
 * method calls are read-only, instead of structural changes.  When operating
 * in "fast" mode, read calls are non-synchronized and write calls perform the
 * following steps:</p>
 * <ul>
 * <li>Clone the existing collection
 * <li>Perform the modification on the clone
 * <li>Replace the existing collection with the (modified) clone
 * </ul>
 * <p>When first created, objects of this class default to "slow" mode, where
 * all accesses of any type are synchronized but no cloning takes place.  This
 * is appropriate for initially populating the collection, followed by a switch
 * to "fast" mode (by calling <code>setFast(true)</code>) after initialization
 * is complete.</p>
 *
 * <p><strong>NOTE</strong>: If you are creating and accessing an
 * <code>ArrayList</code> only within a single thread, you should use
 * <code>java.util.ArrayList</code> directly (with no synchronization), for
 * maximum performance.</p>
 *
 * <p><strong>NOTE</strong>: <i>This class is not cross-platform.
 * Using it may cause unexpected failures on some architectures.</i>
 * It suffers from the same problems as the double-checked locking idiom.  
 * In particular, the instruction that clones the internal collection and the 
 * instruction that sets the internal reference to the clone can be executed 
 * or perceived out-of-order.  This means that any read operation might fail 
 * unexpectedly, as it may be reading the state of the internal collection
 * before the internal collection is fully formed.
 * For more information on the double-checked locking idiom, see the
 * <a href="http://www.cs.umd.edu/~pugh/java/memoryModel/DoubleCheckedLocking.html">
 * Double-Checked Locking Idiom Is Broken Declaration</a>.</p>
 *
 * @since Commons Collections 1.0
 * @version $Revision: 178303 $ $Date: 2005-05-24 23:39:51 +0100 (Tue, 24 May 2005) $
 * 
 * @author Craig R. McClanahan
 * @author Stephen Colebourne
 */
public class FastArrayList extends ArrayList {


    // ----------------------------------------------------------- Constructors


    /**
     * Construct a an empty list.
     */
    public FastArrayList() {

        super();
        this.list = new ArrayList();

    }


    /**
     * Construct an empty list with the specified capacity.
     *
     * @param capacity The initial capacity of the empty list
     */
    public FastArrayList(int capacity) {

        super();
        this.list = new ArrayList(capacity);

    }


    /**
     * Construct a list containing the elements of the specified collection,
     * in the order they are returned by the collection's iterator.
     *
     * @param collection The collection whose elements initialize the contents
     *  of this list
     */
    public FastArrayList(Collection collection) {

        super();
        this.list = new ArrayList(collection);

    }


    // ----------------------------------------------------- Instance Variables


    /**
     * The underlying list we are managing.
     */
    protected ArrayList list = null;


    // ------------------------------------------------------------- Properties


    /**
     * Are we operating in "fast" mode?
     */
    protected boolean fast = false;


    /**
     *  Returns true if this list is operating in fast mode.
     *
     *  @return true if this list is operating in fast mode
     */
    public boolean getFast() {
        return (this.fast);
    }

    /**
     *  Sets whether this list will operate in fast mode.
     *
     *  @param fast true if the list should operate in fast mode
     */
    public void setFast(boolean fast) {
        this.fast = fast;
    }


    // --------------------------------------------------------- Public Methods


    /**
     * Appends the specified element to the end of this list.
     *
     * @param element The element to be appended
     */
    public boolean add(Object element) {

        if (fast) {
            synchronized (this) {
                ArrayList temp = (ArrayList) list.clone();
                boolean result = temp.add(element);
                list = temp;
                return (result);
            }
        } else {
            synchronized (list) {
                return (list.add(element));
            }
        }

    }


    /**
     * Insert the specified element at the specified position in this list,
     * and shift all remaining elements up one position.
     *
     * @param index Index at which to insert this element
     * @param element The element to be inserted
     *
     * @exception IndexOutOfBoundsException if the index is out of range
     */
    public void add(int index, Object element) {

        if (fast) {
            synchronized (this) {
                ArrayList temp = (ArrayList) list.clone();
                temp.add(index, element);
                list = temp;
            }
        } else {
            synchronized (list) {
                list.add(index, element);
            }
        }

    }


    /**
     * Append 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 collection The collection to be appended
     */
    public boolean addAll(Collection collection) {

        if (fast) {
            synchronized (this) {
                ArrayList temp = (ArrayList) list.clone();
                boolean result = temp.addAll(collection);
                list = temp;
                return (result);
            }
        } else {
            synchronized (list) {
                return (list.addAll(collection));
            }
        }

    }


    /**
     * Insert all of the elements in the specified Collection at the specified
     * position in this list, and shift any previous elements upwards as
     * needed.
     *
     * @param index Index at which insertion takes place
     * @param collection The collection to be added
     *
     * @exception IndexOutOfBoundsException if the index is out of range
     */
    public boolean addAll(int index, Collection collection) {

        if (fast) {
            synchronized (this) {
                ArrayList temp = (ArrayList) list.clone();
                boolean result = temp.addAll(index, collection);
                list = temp;
                return (result);
            }
        } else {
            synchronized (list) {
                return (list.addAll(index, collection));
            }
        }

    }


    /**
     * Remove all of the elements from this list.  The list will be empty
     * after this call returns.
     *
     * @exception UnsupportedOperationException if <code>clear()</code>
     *  is not supported by this list
     */
    public void clear() {

        if (fast) {
            synchronized (this) {
                ArrayList temp = (ArrayList) list.clone();
                temp.clear();
                list = temp;
            }
        } else {
            synchronized (list) {
                list.clear();
            }
        }

    }


    /**
     * Return a shallow copy of this <code>FastArrayList</code> instance.
     * The elements themselves are not copied.
     */
    public Object clone() {

        FastArrayList results = null;
        if (fast) {
            results = new FastArrayList(list);
        } else {
            synchronized (list) {
                results = new FastArrayList(list);
            }
        }
        results.setFast(getFast());
        return (results);

    }


    /**
     * Return <code>true</code> if this list contains the specified element.
     *
     * @param element The element to test for
     */
    public boolean contains(Object element) {

        if (fast) {
            return (list.contains(element));
        } else {
            synchronized (list) {
                return (list.contains(element));
            }
        }

    }


    /**
     * Return <code>true</code> if this list contains all of the elements
     * in the specified Collection.
     *
     * @param collection Collection whose elements are to be checked
     */
    public boolean containsAll(Collection collection) {

        if (fast) {
            return (list.containsAll(collection));
        } else {
            synchronized (list) {
                return (list.containsAll(collection));
            }
        }

    }


    /**
     * Increase the capacity of this <code>ArrayList</code> instance, if
     * necessary, to ensure that it can hold at least the number of elements
     * specified by the minimum capacity argument.
     *
     * @param capacity The new minimum capacity
     */
    public void ensureCapacity(int capacity) {

        if (fast) {
            synchronized (this) {
                ArrayList temp = (ArrayList) list.clone();
                temp.ensureCapacity(capacity);
                list = temp;
            }
        } else {
            synchronized (list) {
                list.ensureCapacity(capacity);
            }
        }

    }


    /**
     * Compare the specified object with this list for equality.  This
     * implementation uses exactly the code that is used to define the
     * list equals function in the documentation for the
     * <code>List.equals</code> method.
     *
     * @param o Object to be compared to this list
     */
    public boolean equals(Object o) {

        // Simple tests that require no synchronization
        if (o == this)
            return (true);
        else if (!(o instanceof List))
            return (false);
        List lo = (List) o;

        // Compare the sets of elements for equality
        if (fast) {
            ListIterator li1 = list.listIterator();
            ListIterator li2 = lo.listIterator();
            while (li1.hasNext() && li2.hasNext()) {
                Object o1 = li1.next();
                Object o2 = li2.next();
                if (!(o1 == null ? o2 == null : o1.equals(o2)))
                    return (false);
            }
            return (!(li1.hasNext() || li2.hasNext()));
        } else {
            synchronized (list) {
                ListIterator li1 = list.listIterator();
                ListIterator li2 = lo.listIterator();
                while (li1.hasNext() && li2.hasNext()) {
                    Object o1 = li1.next();
                    Object o2 = li2.next();
                    if (!(o1 == null ? o2 == null : o1.equals(o2)))
                        return (false);
                }
                return (!(li1.hasNext() || li2.hasNext()));
            }
        }

    }


    /**
     * Return the element at the specified position in the list.
     *
     * @param index The index of the element to return
     *
     * @exception IndexOutOfBoundsException if the index is out of range
     */
    public Object get(int index) {

        if (fast) {
            return (list.get(index));
        } else {
            synchronized (list) {
                return (list.get(index));
            }
        }

    }


    /**
     * Return the hash code value for this list.  This implementation uses
     * exactly the code that is used to define the list hash function in the
     * documentation for the <code>List.hashCode</code> method.
     */
    public int hashCode() {

        if (fast) {
            int hashCode = 1;
            java.util.Iterator i = list.iterator();
            while (i.hasNext()) {
                Object o = i.next();
                hashCode = 31 * hashCode + (o == null ? 0 : o.hashCode());
            }
            return (hashCode);
        } else {
            synchronized (list) {
                int hashCode = 1;
                java.util.Iterator i = list.iterator();
                while (i.hasNext()) {
                    Object o = i.next();
                    hashCode = 31 * hashCode + (o == null ? 0 : o.hashCode());
                }
                return (hashCode);