/*
 *  Licensed to the Apache Software Foundation (ASF) under one or more
 *  contributor license agreements.  See the NOTICE file distributed with
 *  this work for additional information regarding copyright ownership.
 *  The ASF licenses this file to You 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$ $Date$
 * 
 * @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;
     *  Iterator i = list.iterator();
     *  while (i.hasNext()) {
     *      Object obj = i.next();
     *      hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
     *  }
     * </pre>
     * This ensures that <tt>list1.equals(list2)</tt> implies that
     * <tt>list1.hashCode()==list2.hashCode()</tt> for any two lists,
     * <tt>list1</tt> and <tt>list2</tt>, as required by the general
     * contract of <tt>Object.hashCode</tt>.
     *
     * @return the hash code value for this list.
     * @see Object#hashCode()
     * @see Object#equals(Object)
     * @see #equals(Object)
     */
    public int hashCode() {
        int hash = 1;
        for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) {
            hash = 31*hash + (null == elt.value() ? 0 : elt.value().hashCode());
        }
        return hash;
    }

    /**
     * Returns the index in this list of the first occurrence of the specified
     * element, or -1 if this list does not contain this element.
     * More formally, returns the lowest index <tt>i</tt> such that
     * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
     * or -1 if there is no such index.
     *
     * @param o element to search for.
     * @return the index in this list of the first occurrence of the specified
     *         element, or -1 if this list does not contain this element.
     */
    public int indexOf(Object o) {
        int ndx = 0;

        // perform the null check outside of the loop to save checking every
        // single time through the loop.
        if (null == o) {
            for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) {
                if (null == elt.value()) {
                    return ndx;
                }
                ndx++;
            }
        } else {

            for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) {
                if (o.equals(elt.value())) {
                    return ndx;
                }
                ndx++;
            }
        }
        return -1;
    }

    /**
     * Returns <tt>true</tt> if this list contains no elements.
     * @return <tt>true</tt> if this list contains no elements.
     */
    public boolean isEmpty() {
        return(0 == _size);
    }

    /**
     * Returns a fail-fast iterator.
     * @see List#iterator
     */
    public Iterator iterator() {
        return listIterator(0);
    }

    /**
     * Returns the index in this list of the last occurrence of the specified
     * element, or -1 if this list does not contain this element.
     * More formally, returns the highest index <tt>i</tt> such that
     * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
     * or -1 if there is no such index.
     *
     * @param o element to search for.
     * @return the index in this list of the last occurrence of the specified
     *            element, or -1 if this list does not contain this element.
     */
    public int lastIndexOf(Object o) {
        int ndx = _size-1;

        // perform the null check outside of the loop to save checking every
        // single time through the loop.
        if (null == o) {
            for(Listable elt = _head.prev(), past = null; null != elt && past != _head.next(); elt = (past = elt).prev()) {
                if (null == elt.value()) {
                    return ndx;
                }
                ndx--;
            }
        } else {
            for(Listable elt = _head.prev(), past = null; null != elt && past != _head.next(); elt = (past = elt).prev()) {
                if (o.equals(elt.value())) {
                    return ndx;
                }
                ndx--;
            }
        }
        return -1;
    }

    /**
     * Returns a fail-fast ListIterator.
     * @see List#listIterator
     */
    public ListIterator listIterator() {
        return listIterator(0);
    }

    /**
     * Returns a fail-fast ListIterator.
     * @see List#listIterator(int)
     */
    public ListIterator listIterator(int index) {
        if(index<0 || index > _size) {
            throw new IndexOutOfBoundsException(index + " < 0 or > " + _size);
        }
        return new ListIter(index);
    }

    /**
     * Removes the first occurrence in this list of the specified element.
     * If this list does not contain the element, it is
     * unchanged.  More formally, removes the element with the lowest index i
     * such that <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> (if
     * such an element exists).
     *
     * @param o element to be removed from this list, if present.
     * @return <tt>true</tt> if this list contained the specified element.
     */
    public boolean remove(Object o) {
        for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) {
            if(null == o && null == elt.value()) {
                removeListable(elt);
                return true;
            } else if(o != null && o.equals(elt.value())) {
                removeListable(elt);
                return true;
            }
        }
        return false;
    }

    /**
     * Removes the element at the specified position in this list (optional
     * operation).  Shifts any subsequent elements to the left (subtracts one
     * from their indices).  Returns the element that was removed from the
     * list.
     *
     * @param index the index of the element to removed.
     * @return the element previously at the specified position.
     *
     * @throws IndexOutOfBoundsException if the index is out of range (index
     *            &lt; 0 || index &gt;= size()).
     */
    public Object remove(int index) {
        Listable elt = getListableAt(index);
        Object ret = elt.value();
        removeListable(elt);
        return ret;
    }

    /**
     * Removes from this list all the elements that are contained in the
     * specified collection.
     *
     * @param c collection that defines which elements will be removed from
     *          this list.
     * @return <tt>true</tt> if this list changed as a result of the call.
     */
    public boolean removeAll(Collection c) {
        if(0 == c.size() || 0 == _size) {
            return false;
        } else {
            boolean changed = false;
            Iterator it = iterator();
            while(it.hasNext()) {
                if(c.contains(it.next())) {
                    it.remove();
                    changed = true;
                }
            }
            return changed;
        }
    }

    /**
     * Removes the first element of this list, if any.
     */
    public Object removeFirst() {
        if(_head.next() != null) {
            Object val = _head.next().value();
            removeListable(_head.next());
            return val;
        } else {
            throw new NoSuchElementException();
        }
    }

    /**
     * Removes the last element of this list, if any.
     */
    public Object removeLast() {
        if(_head.prev() != null) {
            Object val = _head.prev().value();
            removeListable(_head.prev());
            return val;
        } else {
            throw new NoSuchElementException();
        }
    }

    /**
     * Retains only the elements in this list that are contained in the
     * specified collection.  In other words, removes
     * from this list all the elements that are not contained in the specified
     * collection.
     *
     * @param c collection that defines which elements this set will retain.
     *
     * @return <tt>true</tt> if this list changed as a result of the call.
     */
    public boolean retainAll(Collection c) {
        boolean changed = false;
        Iterator it = iterator();
        while(it.hasNext()) {
            if(!c.contains(it.next())) {
                it.remove();
                changed = true;
            }
        }
        return changed;
    }

    /**
     * Replaces the element at the specified position in this list with the
     * specified element.
     *
     * @param index index of element to replace.
     * @param element element to be stored at the specified position.
     * @return the element previously at the specified position.
     *
     * @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 Object set(int index, Object element) {
        Listable elt = getListableAt(index);
        Object val = elt.setValue(element);
        broadcastListableChanged(elt);
        return val;
    }

    /**
     * Returns the number of elements in this list.
     * @return the number of elements in this list.
     */
    public int size() {
        return _size;
    }

    /**
     * Returns an array containing all of the elements in this list in proper
     * sequence.  Obeys the general contract of the {@link Collection#toArray} method.
     *
     * @return an array containing all of the elements in this list in proper
     *         sequence.
     */
    public Object[] toArray() {
        Object[] array = new Object[_size];
        int i = 0;
        for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) {
            array[i++] = elt.value();
        }
        return array;
    }

    /**
     * Returns an array containing all of the elements in this list in proper
     * sequence; the runtime type of the returned array is that of the
     * specified array. Obeys the general contract of the
     * {@link Collection#toArray} method.
     *
     * @param a      the array into which the elements of this list are to
     *               be stored, if it is big enough; otherwise, a new array of the
     *               same runtime type is allocated for this purpose.
     * @return an array containing the elements of this list.
     * @throws ArrayStoreException
     *                   if the runtime type of the specified array
     *                   is not a supertype of the runtime type of every element in
     *                   this list.
     */
    public Object[] toArray(Object a[]) {
        if(a.length < _size) {
            a = (Object[])Array.newInstance(a.getClass().getComponentType(), _size);
        }
        int i = 0;
        for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) {
            a[i++] = elt.value();
        }
        if(a.length > _size) {
            a[_size] = null; // should we null out the rest of the array also? java.util.LinkedList doesn't
        }
        return a;
    }

    /**
     * Returns a {@link String} representation of this list, suitable for debugging.
     * @return a {@link String} representation of this list, suitable for debugging.
     */
    public String toString() {
        StringBuffer buf = new StringBuffer();
        buf.append("[");
        for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) {
            if(_head.next() != elt) {
                buf.append(", ");
            }
            buf.append(elt.value());
        }
        buf.append("]");
        return buf.toString();
    }

    /**
     * Returns a fail-fast sublist.
     * @see List#subList(int,int)
     */
    public List subList(int i, int j) {
        if(i < 0 || j > _size || i > j) {
            throw new IndexOutOfBoundsException();
        } else if(i == 0 && j == _size) {
            return this;
        } else {
            return new CursorableSubList(this,i,j);
        }
    }

    //--- protected methods ------------------------------------------

    /**
     * Inserts a new <i>value</i> into my
     * list, after the specified <i>before</i> element, and before the
     * specified <i>after</i> element
     *
     * @return the newly created 
     * {@link org.apache.commons.collections.CursorableLinkedList.Listable}
     */
    protected Listable insertListable(Listable before, Listable after, Object value) {
        _modCount++;
        _size++;
        Listable elt = new Listable(before,after,value);
        if(null != before) {
            before.setNext(elt);
        } else {
            _head.setNext(elt);
        }

        if(null != after) {
            after.setPrev(elt);
        } else {
            _head.setPrev(elt);
        }
        broadcastListableInserted(elt);
        return elt;
    }

    /**
     * Removes the given 
     * {@link org.apache.commons.collections.CursorableLinkedList.Listable} 
     * from my list.
     */
    protected void removeListable(Listable elt) {
        _modCount++;
        _size--;
        if(_head.next() == elt) {
            _head.setNext(elt.next());
        }
        if(null != elt.next()) {
            elt.next().setPrev(elt.prev());
        }
        if(_head.prev() == elt) {
            _head.setPrev(elt.prev());
        }
        if(null != elt.prev()) {
            elt.prev().setNext(elt.next());
        }
        broadcastListableRemoved(elt);
    }

    /**
     * Returns the 
     * {@link org.apache.commons.collections.CursorableLinkedList.Listable} 
     * at the specified index.
     *
     * @throws IndexOutOfBoundsException if index is less than zero or
     *         greater than or equal to the size of this list.
     */
    protected Listable getListableAt(int index) {
        if(index < 0 || index >= _size) {
            throw new IndexOutOfBoundsException(String.valueOf(index) + " < 0 or " + String.valueOf(index) + " >= " + _size);
        }
        if(index <=_size/2) {
            Listable elt = _head.next();
            for(int i = 0; i < index; i++) {
                elt = elt.next();
            }
            return elt;
        } else {
            Listable elt = _head.prev();
            for(int i = (_size-1); i > index; i--) {
                elt = elt.prev();
            }
            return elt;
        }
    }

    /**
     * Registers a {@link CursorableLinkedList.Cursor} to be notified
     * of changes to this list.
     */
    protected void registerCursor(Cursor cur) {
        // We take this opportunity to clean the _cursors list
        // of WeakReference objects to garbage-collected cursors.
        for (Iterator it = _cursors.iterator(); it.hasNext(); ) {
            WeakReference ref = (WeakReference) it.next();
            if (ref.get() == null) {
                it.remove();
            }
        }
        
        _cursors.add( new WeakReference(cur) );
    }

    /**
     * Removes a {@link CursorableLinkedList.Cursor} from
     * the set of cursors to be notified of changes to this list.
     */
    protected void unregisterCursor(Cursor cur) {
        for (Iterator it = _cursors.iterator(); it.hasNext(); ) {
            WeakReference ref = (WeakReference) it.next();
            Cursor cursor = (Cursor) ref.get();
            if (cursor == null) {
                // some other unrelated cursor object has been 
                // garbage-collected; let's take the opportunity to
                // clean up the cursors list anyway..
                it.remove();
                
            } else if (cursor == cur) {
                ref.clear();
                it.remove();
                break;
            }
        }
    }

    /**
     * Informs all of my registered cursors that they are now
     * invalid.
     */
    protected void invalidateCursors() {
        Iterator it = _cursors.iterator();
        while (it.hasNext()) {
            WeakReference ref = (WeakReference) it.next();
            Cursor cursor = (Cursor) ref.get();
            if (cursor != null) {
                // cursor is null if object has been garbage-collected
                cursor.invalidate();
                ref.clear();
            }
            it.remove();
        }
    }

    /**
     * Informs all of my registered cursors that the specified
     * element was changed.
     * @see #set(int,java.lang.Object)
     */
    protected void broadcastListableChanged(Listable elt) {
        Iterator it = _cursors.iterator();
        while (it.hasNext()) {
            WeakReference ref = (WeakReference) it.next();
            Cursor cursor = (Cursor) ref.get();
            if (cursor == null) {
                it.remove(); // clean up list
            } else {
                cursor.listableChanged(elt);
            }
        }
    }

    /**
     * Informs all of my registered cursors that the specified
     * element was just removed from my list.
     */
    protected void broadcastListableRemoved(Listable elt) {
        Iterator it = _cursors.iterator();
        while (it.hasNext()) {
            WeakReference ref = (WeakReference) it.next();
            Cursor cursor = (Cursor) ref.get();
            if (cursor == null) {
                it.remove(); // clean up list
            } else {
                cursor.listableRemoved(elt);
            }
        }
    }

    /**
     * Informs all of my registered cursors that the specified
     * element was just added to my list.
     */
    protected void broadcastListableInserted(Listable elt) {
        Iterator it = _cursors.iterator();
        while (it.hasNext()) {
            WeakReference ref = (WeakReference) it.next();
            Cursor cursor = (Cursor) ref.get();
            if (cursor == null) {
                it.remove();  // clean up list
            } else {
                cursor.listableInserted(elt);
            }
        }
    }

    private void writeObject(ObjectOutputStream out) throws IOException {
        out.defaultWriteObject();
        out.writeInt(_size);
        Listable cur = _head.next();
        while (cur != null) {
            out.writeObject(cur.value());
            cur = cur.next();
        }
    }

    private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
        in.defaultReadObject();
        _size = 0;
        _modCount = 0;
        _cursors = new ArrayList();
        _head = new Listable(null,null,null);
        int size = in.readInt();
        for (int i=0;i<size;i++) {
            this.add(in.readObject());
        }
    }

    //--- protected attributes ---------------------------------------

    /** The number of elements in me. */
    protected transient int _size = 0;

    /**
     * A sentry node.
     * <p>
     * <tt>_head.next()</tt> points to the first element in the list,
     * <tt>_head.prev()</tt> to the last. Note that it is possible for
     * <tt>_head.next().prev()</tt> and <tt>_head.prev().next()</tt> to be
     * non-null, as when I am a sublist for some larger list.
     * Use <tt>== _head.next()</tt> and <tt>== _head.prev()</tt> to determine
     * if a given 
     * {@link org.apache.commons.collections.CursorableLinkedList.Listable} 
     * is the first or last element in the list.
     */
    protected transient Listable _head = new Listable(null,null,null);

    /** Tracks the number of structural modifications to me. */
    protected transient int _modCount = 0;

    /**
     * A list of the currently {@link CursorableLinkedList.Cursor}s currently
     * open in this list.
     */
    protected transient List _cursors = new ArrayList();

    //--- inner classes ----------------------------------------------

    static class Listable implements Serializable {
        private Listable _prev = null;
        private Listable _next = null;
        private Object _val = null;

        Listable(Listable prev, Listable next, Object val) {
            _prev = prev;
            _next = next;
            _val = val;
        }

        Listable next() {
            return _next;
        }

        Listable prev() {
            return _prev;
        }

        Object value() {
            return _val;
        }

        void setNext(Listable next) {
            _next = next;
        }

        void setPrev(Listable prev) {
            _prev = prev;
        }

        Object setValue(Object val) {
            Object temp = _val;
            _val = val;
            return temp;
        }
    }

    class ListIter implements ListIterator {
        Listable _cur = null;
        Listable _lastReturned = null;
        int _expectedModCount = _modCount;
        int _nextIndex = 0;

        ListIter(int index) {
            if(index == 0) {
                _cur = new Listable(null,_head.next(),null);
                _nextIndex = 0;
            } else if(index == _size) {
                _cur = new Listable(_head.prev(),null,null);
                _nextIndex = _size;
            } else {
                Listable temp = getListableAt(index);
                _cur = new Listable(temp.prev(),temp,null);
                _nextIndex = index;
            }
        }

        public Object previous() {
            checkForComod();
            if(!hasPrevious()) {
                throw new NoSuchElementException();
            } else {
                Object ret = _cur.prev().value();
                _lastReturned = _cur.prev();
                _cur.setNext(_cur.prev());
                _cur.setPrev(_cur.prev().prev());
                _nextIndex--;
                return ret;
            }
        }

        public boolean hasNext() {
            checkForComod();
            return(null != _cur.next() && _cur.prev() != _head.prev());
        }

        public Object next() {
            checkForComod();
            if(!hasNext()) {
                throw new NoSuchElementException();
            } else {
                Object ret = _cur.next().value();
                _lastReturned = _cur.next();
                _cur.setPrev(_cur.next());
                _cur.setNext(_cur.next().next());
                _nextIndex++;
                return ret;
            }
        }

        public int previousIndex() {
            checkForComod();
            if(!hasPrevious()) {
                return -1;
            }
            return _nextIndex-1;
        }

        public boolean hasPrevious() {
            checkForComod();
            return(null != _cur.prev() && _cur.next() != _head.next());
        }

        public void set(Object o) {
            checkForComod();
            try {
                _lastReturned.setValue(o);
            } catch(NullPointerException e) {
                throw new IllegalStateException();
            }
        }

        public int nextIndex() {
            checkForComod();
            if(!hasNext()) {
                return size();
            }
            return _nextIndex;
        }

        public void remove() {
            checkForComod();
            if(null == _lastReturned) {
                throw new IllegalStateException();
            } else {
                _cur.setNext(_lastReturned == _head.prev() ? null : _lastReturned.next());
                _cur.setPrev(_lastReturned == _head.next() ? null : _lastReturned.prev());
                removeListable(_lastReturned);
                _lastReturned = null;
                _nextIndex--;
                _expectedModCount++;
            }
        }

        public void add(Object o) {
            checkForComod();
            _cur.setPrev(insertListable(_cur.prev(),_cur.next(),o));
            _lastReturned = null;
            _nextIndex++;
            _expectedModCount++;
        }

        protected void checkForComod() {
            if(_expectedModCount != _modCount) {
                throw new ConcurrentModificationException();
            }
        }
    }

    public class Cursor extends ListIter implements ListIterator {
        boolean _valid = false;

        Cursor(int index) {
            super(index);
            _valid = true;
            registerCursor(this);
        }

        public int previousIndex() {
            throw new UnsupportedOperationException();
        }

        public int nextIndex() {
            throw new UnsupportedOperationException();
        }

        public void add(Object o) {
            checkForComod();
            Listable elt = insertListable(_cur.prev(),_cur.next(),o);
            _cur.setPrev(elt);
            _cur.setNext(elt.next());
            _lastReturned = null;
            _nextIndex++;
            _expectedModCount++;
        }

        protected void listableRemoved(Listable elt) {
            if(null == _head.prev()) {
                _cur.setNext(null);
            } else if(_cur.next() == elt) {
                _cur.setNext(elt.next());
            }
            if(null == _head.next()) {
                _cur.setPrev(null);
            } else if(_cur.prev() == elt) {
                _cur.setPrev(elt.prev());
            }
            if(_lastReturned == elt) {
                _lastReturned = null;
            }
        }

        protected void listableInserted(Listable elt) {
            if(null == _cur.next() && null == _cur.prev()) {
                _cur.setNext(elt);
            } else if(_cur.prev() == elt.prev()) {
                _cur.setNext(elt);
            }
            if(_cur.next() == elt.next()) {
                _cur.setPrev(elt);
            }
            if(_lastReturned == elt) {
                _lastReturned = null;
            }
        }

        protected void listableChanged(Listable elt) {
            if(_lastReturned == elt) {
                _lastReturned = null;
            }
        }

        protected void checkForComod() {
            if(!_valid) {
                throw new ConcurrentModificationException();
            }
        }

        protected void invalidate() {
            _valid = false;
        }

        /**
         * Mark this cursor as no longer being needed. Any resources
         * associated with this cursor are immediately released.
         * In previous versions of this class, it was mandatory to close
         * all cursor objects to avoid memory leaks. It is <i>no longer</i>
         * necessary to call this close method; an instance of this class
         * can now be treated exactly like a normal iterator.
         */
        public void close() {
            if(_valid) {
                _valid = false;
                unregisterCursor(this);
            }
        }
    }

}

/**
 * @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
 */
class CursorableSubList extends CursorableLinkedList implements List {

    //--- constructors -----------------------------------------------

    CursorableSubList(CursorableLinkedList list, int from, int to) {
        if(0 > from || list.size() < to) {
            throw new IndexOutOfBoundsException();
        } else if(from > to) {
            throw new IllegalArgumentException();
        }
        _list = list;
        if(from < list.size()) {
            _head.setNext(_list.getListableAt(from));
            _pre = (null == _head.next()) ? null : _head.next().prev();
        } else {
            _pre = _list.getListableAt(from-1);
        }
        if(from == to) {
            _head.setNext(null);
            _head.setPrev(null);
            if(to < list.size()) {
                _post = _list.getListableAt(to);
            } else {
                _post = null;
            }
        } else {
            _head.setPrev(_list.getListableAt(to-1));
            _post = _head.prev().next();
        }
        _size = to - from;
        _modCount = _list._modCount;
    }

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

    public void clear() {
        checkForComod();
        Iterator it = iterator();
        while(it.hasNext()) {
            it.next();
            it.remove();
        }
    }

    public Iterator iterator() {
        checkForComod();
        return super.iterator();
    }

    public int size() {
        checkForComod();
        return super.size();
    }

    public boolean isEmpty() {
        checkForComod();
        return super.isEmpty();
    }

    public Object[] toArray() {
        checkForComod();
        return super.toArray();
    }

    public Object[] toArray(Object a[]) {
        checkForComod();
        return super.toArray(a);
    }

    public boolean contains(Object o) {
        checkForComod();
        return super.contains(o);
    }

    public boolean remove(Object o) {
        checkForComod();
        return super.remove(o);
    }

    public Object removeFirst() {
        checkForComod();
        return super.removeFirst();
    }

    public Object removeLast() {
        checkForComod();
        return super.removeLast();
    }

    public boolean addAll(Collection c) {
        checkForComod();
        return super.addAll(c);
    }

    public boolean add(Object o) {
        checkForComod();
        return super.add(o);
    }

    public boolean addFirst(Object o) {
        checkForComod();
        return super.addFirst(o);
    }

    public boolean addLast(Object o) {
        checkForComod();
        return super.addLast(o);
    }

    public boolean removeAll(Collection c) {
        checkForComod();
        return super.removeAll(c);
    }

    public boolean containsAll(Collection c) {
        checkForComod();
        return super.containsAll(c);
    }

    public boolean addAll(int index, Collection c) {
        checkForComod();
        return super.addAll(index,c);
    }

    public int hashCode() {
        checkForComod();
        return super.hashCode();
    }

    public boolean retainAll(Collection c) {
        checkForComod();
        return super.retainAll(c);
    }

    public Object set(int index, Object element) {
        checkForComod();
        return super.set(index,element);
    }

    public boolean equals(Object o) {
        checkForComod();
        return super.equals(o);
    }

    public Object get(int index) {
        checkForComod();
        return super.get(index);
    }

    public Object getFirst() {
        checkForComod();
        return super.getFirst();
    }

    public Object getLast() {
        checkForComod();
        return super.getLast();
    }

    public void add(int index, Object element) {
        checkForComod();
        super.add(index,element);
    }

    public ListIterator listIterator(int index) {
        checkForComod();
        return super.listIterator(index);
    }

    public Object remove(int index) {
        checkForComod();
        return super.remove(index);
    }

    public int indexOf(Object o) {
        checkForComod();
        return super.indexOf(o);
    }

    public int lastIndexOf(Object o) {
        checkForComod();
        return super.lastIndexOf(o);
    }

    public ListIterator listIterator() {
        checkForComod();
        return super.listIterator();
    }

    public List subList(int fromIndex, int toIndex) {
        checkForComod();
        return super.subList(fromIndex,toIndex);
    }

    //--- protected methods ------------------------------------------

    /**
     * Inserts a new <i>value</i> into my
     * list, after the specified <i>before</i> element, and before the
     * specified <i>after</i> element
     *
     * @return the newly created {@link CursorableLinkedList.Listable}
     */
    protected Listable insertListable(Listable before, Listable after, Object value) {
        _modCount++;
        _size++;
        Listable elt = _list.insertListable((null == before ? _pre : before), (null == after ? _post : after),value);
        if(null == _head.next()) {
            _head.setNext(elt);
            _head.setPrev(elt);
        }
        if(before == _head.prev()) {
            _head.setPrev(elt);
        }
        if(after == _head.next()) {
            _head.setNext(elt);
        }
        broadcastListableInserted(elt);
        return elt;
    }

    /**
     * Removes the given {@link CursorableLinkedList.Listable} from my list.
     */
    protected void removeListable(Listable elt) {
        _modCount++;
        _size--;
        if(_head.next() == elt && _head.prev() == elt) {
            _head.setNext(null);
            _head.setPrev(null);
        }
        if(_head.next() == elt) {
            _head.setNext(elt.next());
        }
        if(_head.prev() == elt) {
            _head.setPrev(elt.prev());
        }
        _list.removeListable(elt);
        broadcastListableRemoved(elt);
    }

    /**
     * Test to see if my underlying list has been modified
     * by some other process.  If it has, throws a
     * {@link ConcurrentModificationException}, otherwise
     * quietly returns.
     *
     * @throws ConcurrentModificationException
     */
    protected void checkForComod() throws ConcurrentModificationException {
        if(_modCount != _list._modCount) {
            throw new ConcurrentModificationException();
        }
    }

    //--- protected attributes ---------------------------------------

    /** My underlying list */
    protected CursorableLinkedList _list = null;

    /** The element in my underlying list preceding the first element in my list. */
    protected Listable _pre = null;

    /** The element in my underlying list following the last element in my list. */
    protected Listable _post = null;

}