cursorablelinkedlist.java

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

/*
 *  Copyright 2002-2004 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.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.lang.ref.WeakReference;

/**
 * A doubly-linked list implementation of the {@link List} interface,
 * supporting a {@link ListIterator} that allows concurrent modifications
 * to the underlying list.
 * <p>
 * Implements all of the optional {@link List} operations, the
 * stack/queue/dequeue operations available in {@link java.util.LinkedList}
 * and supports a {@link ListIterator} that allows concurrent modifications
 * to the underlying list (see {@link #cursor}).
 * <p>
 * <b>Note that this implementation is not synchronized.</b>
 *
 * @deprecated Use new version in list subpackage, which has been rewritten
 *  and now returns the cursor from the listIterator method. Will be removed in v4.0
 * @see java.util.LinkedList
 * @since Commons Collections 1.0
 * @version $Revision: 404858 $ $Date: 2006-05-07 22:40:39 +0100 (Sun, 07 May 2006) $
 * 
 * @author Rodney Waldhoff
 * @author Janek Bogucki
 * @author Simon Kitching
 */
public class CursorableLinkedList implements List, Serializable {
    /** Ensure serialization compatibility */    
    private static final long serialVersionUID = 8836393098519411393L;

    //--- public methods ---------------------------------------------

    /**
     * Appends the specified element to the end of this list.
     *
     * @param o element to be appended to this list.
     * @return <tt>true</tt>
     */
    public boolean add(Object o) {
        insertListable(_head.prev(),null,o);
        return true;
    }

    /**
     * Inserts the specified element at the specified position in this list.
     * Shifts the element currently at that position (if any) and any subsequent
     *  elements to the right (adds one to their indices).
     *
     * @param index index at which the specified element is to be inserted.
     * @param element element to be inserted.
     *
     * @throws ClassCastException if the class of the specified element
     * 		  prevents it from being added to this list.
     * @throws IllegalArgumentException if some aspect of the specified
     *		     element prevents it from being added to this list.
     * @throws IndexOutOfBoundsException if the index is out of range
     *		     (index &lt; 0 || index &gt; size()).
     */
    public void add(int index, Object element) {
        if(index == _size) {
            add(element);
        } else {
            if(index < 0 || index > _size) {
                throw new IndexOutOfBoundsException(String.valueOf(index) + " < 0 or " + String.valueOf(index) + " > " + _size);
            }
            Listable succ = (isEmpty() ? null : getListableAt(index));
            Listable pred = (null == succ ? null : succ.prev());
            insertListable(pred,succ,element);
        }
    }

    /**
     * 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
     * {@link Collection}'s {@link Iterator}.  The behavior of this operation is
     * unspecified if the specified collection is modified while
     * the operation is in progress.  (Note that this will occur if the
     * specified collection is this list, and it's nonempty.)
     *
     * @param c collection whose elements are to be added to this list.
     * @return <tt>true</tt> if this list changed as a result of the call.
     *
     * @throws ClassCastException if the class of an element in the specified
     * 	     collection prevents it from being added to this list.
     * @throws IllegalArgumentException if some aspect of an element in the
     *         specified collection prevents it from being added to this
     *         list.
     */
    public boolean addAll(Collection c) {
        if(c.isEmpty()) {
            return false;
        }
        Iterator it = c.iterator();
        while(it.hasNext()) {
            insertListable(_head.prev(),null,it.next());
        }
        return true;
    }

    /**
     * Inserts all of the elements in the specified collection into this
     * list 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 this
     * list in the order that they are returned by the specified
     * {@link Collection}'s {@link Iterator}.  The behavior of this operation is
     * unspecified if the specified collection is modified while the
     * operation is in progress.  (Note that this will occur if the specified
     * collection is this list, and it's nonempty.)
     *
     * @param index index at which to insert first element from the specified
     *	            collection.
     * @param c elements to be inserted into this list.
     * @return <tt>true</tt> if this list changed as a result of the call.
     *
     * @throws ClassCastException if the class of one of elements of the
     * 		   specified collection prevents it from being added to this
     * 		   list.
     * @throws IllegalArgumentException if some aspect of one of elements of
     *         the specified collection prevents it from being added to
     *         this list.
     * @throws IndexOutOfBoundsException if the index is out of range (index
     *	      &lt; 0 || index &gt; size()).
     */
    public boolean addAll(int index, Collection c) {
        if(c.isEmpty()) {
            return false;
        } else if(_size == index || _size == 0) {
            return addAll(c);
        } else {
            Listable succ = getListableAt(index);
            Listable pred = (null == succ) ? null : succ.prev();
            Iterator it = c.iterator();
            while(it.hasNext()) {
                pred = insertListable(pred,succ,it.next());
            }
            return true;
        }
    }

    /**
     * Inserts the specified element at the beginning of this list.
     * (Equivalent to {@link #add(int,java.lang.Object) <tt>add(0,o)</tt>}).
     *
     * @param o element to be prepended to this list.
     * @return <tt>true</tt>
     */
    public boolean addFirst(Object o) {
        insertListable(null,_head.next(),o);
        return true;
    }

    /**
     * Inserts the specified element at the end of this list.
     * (Equivalent to {@link #add(java.lang.Object)}).
     *
     * @param o element to be appended to this list.
     * @return <tt>true</tt>
     */
    public boolean addLast(Object o) {
        insertListable(_head.prev(),null,o);
        return true;
    }

    /**
     * Removes all of the elements from this list.  This
     * list will be empty after this call returns (unless
     * it throws an exception).
     */
    public void clear() {
        /*
        // this is the quick way, but would force us
        // to break all the cursors
        _modCount++;
        _head.setNext(null);
        _head.setPrev(null);
        _size = 0;
        */
        Iterator it = iterator();
        while(it.hasNext()) {
            it.next();
            it.remove();
        }
    }

    /**
     * Returns <tt>true</tt> if this list contains the specified element.
     * More formally, returns <tt>true</tt> if and only if this list contains
     * at least one element <tt>e</tt> such that
     * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
     *
     * @param o element whose presence in this list is to be tested.
     * @return <tt>true</tt> if this list contains the specified element.
     */
    public boolean contains(Object o) {
        for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) {
            if((null == o && null == elt.value()) || 
               (o != null && o.equals(elt.value()))) {
                return true;
            }
        }
        return false;
    }

    /**
     * Returns <tt>true</tt> if this list contains all of the elements of the
     * specified collection.
     *
     * @param c collection to be checked for containment in this list.
     * @return <tt>true</tt> if this list contains all of the elements of the
     *         specified collection.
     */
    public boolean containsAll(Collection c) {
        Iterator it = c.iterator();
        while(it.hasNext()) {
            if(!this.contains(it.next())) {
                return false;
            }
        }
        return true;
    }

    /**
     * Returns a {@link ListIterator} for iterating through the
     * elements of this list. Unlike {@link #iterator}, a cursor
     * is not bothered by concurrent modifications to the
     * underlying list.
     * <p>
     * Specifically, when elements are added to the list before or
     * after the cursor, the cursor simply picks them up automatically.
     * When the "current" (i.e., last returned by {@link ListIterator#next}
     * or {@link ListIterator#previous}) element of the list is removed,
     * the cursor automatically adjusts to the change (invalidating the
     * last returned value--i.e., it cannot be removed).
     * <p>
     * Note that the returned {@link ListIterator} does not support the
     * {@link ListIterator#nextIndex} and {@link ListIterator#previousIndex}
     * methods (they throw {@link UnsupportedOperationException} when invoked.
     * <p>
     * Historical Note: In previous versions of this class, the object 
     * returned from this method was required to be explicitly closed. This 
     * is no longer necessary.
     *
     * @see #cursor(int)
     * @see #listIterator
     * @see CursorableLinkedList.Cursor
     */
    public CursorableLinkedList.Cursor cursor() {
        return new Cursor(0);
    }

    /**
     * Returns a {@link ListIterator} for iterating through the
     * elements of this list, initialized such that
     * {@link ListIterator#next} will return the element at
     * the specified index (if any) and {@link ListIterator#previous}
     * will return the element immediately preceding it (if any).
     * Unlike {@link #iterator}, a cursor
     * is not bothered by concurrent modifications to the
     * underlying list.
     *
     * @see #cursor
     * @see #listIterator(int)
     * @see CursorableLinkedList.Cursor
     * @throws IndexOutOfBoundsException if the index is out of range (index
     *	        &lt; 0 || index &gt; size()).
     */
    public CursorableLinkedList.Cursor cursor(int i) {
        return new Cursor(i);
    }

    /**
     * Compares the specified object with this list for equality.  Returns
     * <tt>true</tt> 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 <i>equal</i>.  (Two elements <tt>e1</tt> and
     * <tt>e2</tt> are <i>equal</i> 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.  This
     * definition ensures that the equals method works properly across
     * different implementations of the <tt>List</tt> interface.
     *
     * @param o the object to be compared for equality with this list.
     * @return <tt>true</tt> if the specified object is equal to this list.
     */
    public boolean equals(Object o) {
        if(o == this) {
            return true;
        } else if(!(o instanceof List)) {
            return false;
        }
        Iterator it = ((List)o).listIterator();
        for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) {
            if(!it.hasNext() || (null == elt.value() ? null != it.next() : !(elt.value().equals(it.next()))) ) {
                return false;
            }
        }
        return !it.hasNext();
    }

    /**
     * Returns the element at the specified position in this list.
     *
     * @param index index of element to return.
     * @return the element at the specified position in this list.
     *
     * @throws IndexOutOfBoundsException if the index is out of range (index
     * 		  &lt; 0 || index &gt;= size()).
     */
    public Object get(int index) {
        return getListableAt(index).value();
    }

    /**
     * Returns the element at the beginning of this list.
     */
    public Object getFirst() {
        try {
            return _head.next().value();
        } catch(NullPointerException e) {
            throw new NoSuchElementException();
        }
    }

    /**
     * Returns the element at the end of this list.
     */
    public Object getLast() {
        try {
            return _head.prev().value();
        } catch(NullPointerException e) {
            throw new NoSuchElementException();
        }
    }

    /**
     * Returns the hash code value for this list.  The hash code of a list
     * is defined to be the result of the following calculation:
     * <pre>
     *  hashCode = 1;