001    /*
002     *  Licensed to the Apache Software Foundation (ASF) under one or more
003     *  contributor license agreements.  See the NOTICE file distributed with
004     *  this work for additional information regarding copyright ownership.
005     *  The ASF licenses this file to You under the Apache License, Version 2.0
006     *  (the "License"); you may not use this file except in compliance with
007     *  the License.  You may obtain a copy of the License at
008     *
009     *      http://www.apache.org/licenses/LICENSE-2.0
010     *
011     *  Unless required by applicable law or agreed to in writing, software
012     *  distributed under the License is distributed on an "AS IS" BASIS,
013     *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014     *  See the License for the specific language governing permissions and
015     *  limitations under the License.
016     */
017    package org.apache.commons.collections;
018    
019    import java.io.IOException;
020    import java.io.ObjectInputStream;
021    import java.io.ObjectOutputStream;
022    import java.io.Serializable;
023    import java.lang.reflect.Array;
024    import java.util.ArrayList;
025    import java.util.Collection;
026    import java.util.ConcurrentModificationException;
027    import java.util.Iterator;
028    import java.util.List;
029    import java.util.ListIterator;
030    import java.util.NoSuchElementException;
031    import java.lang.ref.WeakReference;
032    
033    /**
034     * A doubly-linked list implementation of the {@link List} interface,
035     * supporting a {@link ListIterator} that allows concurrent modifications
036     * to the underlying list.
037     * <p>
038     * Implements all of the optional {@link List} operations, the
039     * stack/queue/dequeue operations available in {@link java.util.LinkedList}
040     * and supports a {@link ListIterator} that allows concurrent modifications
041     * to the underlying list (see {@link #cursor}).
042     * <p>
043     * <b>Note that this implementation is not synchronized.</b>
044     *
045     * @deprecated Use new version in list subpackage, which has been rewritten
046     *  and now returns the cursor from the listIterator method. Will be removed in v4.0
047     * @see java.util.LinkedList
048     * @since Commons Collections 1.0
049     * @version $Revision: 647116 $ $Date: 2008-04-11 12:23:08 +0100 (Fri, 11 Apr 2008) $
050     * 
051     * @author Rodney Waldhoff
052     * @author Janek Bogucki
053     * @author Simon Kitching
054     */
055    public class CursorableLinkedList implements List, Serializable {
056        /** Ensure serialization compatibility */    
057        private static final long serialVersionUID = 8836393098519411393L;
058    
059        //--- public methods ---------------------------------------------
060    
061        /**
062         * Appends the specified element to the end of this list.
063         *
064         * @param o element to be appended to this list.
065         * @return <tt>true</tt>
066         */
067        public boolean add(Object o) {
068            insertListable(_head.prev(),null,o);
069            return true;
070        }
071    
072        /**
073         * Inserts the specified element at the specified position in this list.
074         * Shifts the element currently at that position (if any) and any subsequent
075         *  elements to the right (adds one to their indices).
076         *
077         * @param index index at which the specified element is to be inserted.
078         * @param element element to be inserted.
079         *
080         * @throws ClassCastException if the class of the specified element
081         *           prevents it from being added to this list.
082         * @throws IllegalArgumentException if some aspect of the specified
083         *             element prevents it from being added to this list.
084         * @throws IndexOutOfBoundsException if the index is out of range
085         *             (index &lt; 0 || index &gt; size()).
086         */
087        public void add(int index, Object element) {
088            if(index == _size) {
089                add(element);
090            } else {
091                if(index < 0 || index > _size) {
092                    throw new IndexOutOfBoundsException(String.valueOf(index) + " < 0 or " + String.valueOf(index) + " > " + _size);
093                }
094                Listable succ = (isEmpty() ? null : getListableAt(index));
095                Listable pred = (null == succ ? null : succ.prev());
096                insertListable(pred,succ,element);
097            }
098        }
099    
100        /**
101         * Appends all of the elements in the specified collection to the end of
102         * this list, in the order that they are returned by the specified
103         * {@link Collection}'s {@link Iterator}.  The behavior of this operation is
104         * unspecified if the specified collection is modified while
105         * the operation is in progress.  (Note that this will occur if the
106         * specified collection is this list, and it's nonempty.)
107         *
108         * @param c collection whose elements are to be added to this list.
109         * @return <tt>true</tt> if this list changed as a result of the call.
110         *
111         * @throws ClassCastException if the class of an element in the specified
112         *          collection prevents it from being added to this list.
113         * @throws IllegalArgumentException if some aspect of an element in the
114         *         specified collection prevents it from being added to this
115         *         list.
116         */
117        public boolean addAll(Collection c) {
118            if(c.isEmpty()) {
119                return false;
120            }
121            Iterator it = c.iterator();
122            while(it.hasNext()) {
123                insertListable(_head.prev(),null,it.next());
124            }
125            return true;
126        }
127    
128        /**
129         * Inserts all of the elements in the specified collection into this
130         * list at the specified position.  Shifts the element currently at
131         * that position (if any) and any subsequent elements to the right
132         * (increases their indices).  The new elements will appear in this
133         * list in the order that they are returned by the specified
134         * {@link Collection}'s {@link Iterator}.  The behavior of this operation is
135         * unspecified if the specified collection is modified while the
136         * operation is in progress.  (Note that this will occur if the specified
137         * collection is this list, and it's nonempty.)
138         *
139         * @param index index at which to insert first element from the specified
140         *                collection.
141         * @param c elements to be inserted into this list.
142         * @return <tt>true</tt> if this list changed as a result of the call.
143         *
144         * @throws ClassCastException if the class of one of elements of the
145         *            specified collection prevents it from being added to this
146         *            list.
147         * @throws IllegalArgumentException if some aspect of one of elements of
148         *         the specified collection prevents it from being added to
149         *         this list.
150         * @throws IndexOutOfBoundsException if the index is out of range (index
151         *          &lt; 0 || index &gt; size()).
152         */
153        public boolean addAll(int index, Collection c) {
154            if(c.isEmpty()) {
155                return false;
156            } else if(_size == index || _size == 0) {
157                return addAll(c);
158            } else {
159                Listable succ = getListableAt(index);
160                Listable pred = (null == succ) ? null : succ.prev();
161                Iterator it = c.iterator();
162                while(it.hasNext()) {
163                    pred = insertListable(pred,succ,it.next());
164                }
165                return true;
166            }
167        }
168    
169        /**
170         * Inserts the specified element at the beginning of this list.
171         * (Equivalent to {@link #add(int,java.lang.Object) <tt>add(0,o)</tt>}).
172         *
173         * @param o element to be prepended to this list.
174         * @return <tt>true</tt>
175         */
176        public boolean addFirst(Object o) {
177            insertListable(null,_head.next(),o);
178            return true;
179        }
180    
181        /**
182         * Inserts the specified element at the end of this list.
183         * (Equivalent to {@link #add(java.lang.Object)}).
184         *
185         * @param o element to be appended to this list.
186         * @return <tt>true</tt>
187         */
188        public boolean addLast(Object o) {
189            insertListable(_head.prev(),null,o);
190            return true;
191        }
192    
193        /**
194         * Removes all of the elements from this list.  This
195         * list will be empty after this call returns (unless
196         * it throws an exception).
197         */
198        public void clear() {
199            /*
200            // this is the quick way, but would force us
201            // to break all the cursors
202            _modCount++;
203            _head.setNext(null);
204            _head.setPrev(null);
205            _size = 0;
206            */
207            Iterator it = iterator();
208            while(it.hasNext()) {
209                it.next();
210                it.remove();
211            }
212        }
213    
214        /**
215         * Returns <tt>true</tt> if this list contains the specified element.
216         * More formally, returns <tt>true</tt> if and only if this list contains
217         * at least one element <tt>e</tt> such that
218         * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
219         *
220         * @param o element whose presence in this list is to be tested.
221         * @return <tt>true</tt> if this list contains the specified element.
222         */
223        public boolean contains(Object o) {
224            for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) {
225                if((null == o && null == elt.value()) || 
226                   (o != null && o.equals(elt.value()))) {
227                    return true;
228                }
229            }
230            return false;
231        }
232    
233        /**
234         * Returns <tt>true</tt> if this list contains all of the elements of the
235         * specified collection.
236         *
237         * @param c collection to be checked for containment in this list.
238         * @return <tt>true</tt> if this list contains all of the elements of the
239         *         specified collection.
240         */
241        public boolean containsAll(Collection c) {
242            Iterator it = c.iterator();
243            while(it.hasNext()) {
244                if(!this.contains(it.next())) {
245                    return false;
246                }
247            }
248            return true;
249        }
250    
251        /**
252         * Returns a {@link ListIterator} for iterating through the
253         * elements of this list. Unlike {@link #iterator}, a cursor
254         * is not bothered by concurrent modifications to the
255         * underlying list.
256         * <p>
257         * Specifically, when elements are added to the list before or
258         * after the cursor, the cursor simply picks them up automatically.
259         * When the "current" (i.e., last returned by {@link ListIterator#next}
260         * or {@link ListIterator#previous}) element of the list is removed,
261         * the cursor automatically adjusts to the change (invalidating the
262         * last returned value--i.e., it cannot be removed).
263         * <p>
264         * Note that the returned {@link ListIterator} does not support the
265         * {@link ListIterator#nextIndex} and {@link ListIterator#previousIndex}
266         * methods (they throw {@link UnsupportedOperationException} when invoked.
267         * <p>
268         * Historical Note: In previous versions of this class, the object 
269         * returned from this method was required to be explicitly closed. This 
270         * is no longer necessary.
271         *
272         * @see #cursor(int)
273         * @see #listIterator
274         * @see CursorableLinkedList.Cursor
275         */
276        public CursorableLinkedList.Cursor cursor() {
277            return new Cursor(0);
278        }
279    
280        /**
281         * Returns a {@link ListIterator} for iterating through the
282         * elements of this list, initialized such that
283         * {@link ListIterator#next} will return the element at
284         * the specified index (if any) and {@link ListIterator#previous}
285         * will return the element immediately preceding it (if any).
286         * Unlike {@link #iterator}, a cursor
287         * is not bothered by concurrent modifications to the
288         * underlying list.
289         *
290         * @see #cursor
291         * @see #listIterator(int)
292         * @see CursorableLinkedList.Cursor
293         * @throws IndexOutOfBoundsException if the index is out of range (index
294         *            &lt; 0 || index &gt; size()).
295         */
296        public CursorableLinkedList.Cursor cursor(int i) {
297            return new Cursor(i);
298        }
299    
300        /**
301         * Compares the specified object with this list for equality.  Returns
302         * <tt>true</tt> if and only if the specified object is also a list, both
303         * lists have the same size, and all corresponding pairs of elements in
304         * the two lists are <i>equal</i>.  (Two elements <tt>e1</tt> and
305         * <tt>e2</tt> are <i>equal</i> if <tt>(e1==null ? e2==null :
306         * e1.equals(e2))</tt>.)  In other words, two lists are defined to be
307         * equal if they contain the same elements in the same order.  This
308         * definition ensures that the equals method works properly across
309         * different implementations of the <tt>List</tt> interface.
310         *
311         * @param o the object to be compared for equality with this list.
312         * @return <tt>true</tt> if the specified object is equal to this list.
313         */
314        public boolean equals(Object o) {
315            if(o == this) {
316                return true;
317            } else if(!(o instanceof List)) {
318                return false;
319            }
320            Iterator it = ((List)o).listIterator();
321            for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) {
322                if(!it.hasNext() || (null == elt.value() ? null != it.next() : !(elt.value().equals(it.next()))) ) {
323                    return false;
324                }
325            }
326            return !it.hasNext();
327        }
328    
329        /**
330         * Returns the element at the specified position in this list.
331         *
332         * @param index index of element to return.
333         * @return the element at the specified position in this list.
334         *
335         * @throws IndexOutOfBoundsException if the index is out of range (index
336         *           &lt; 0 || index &gt;= size()).
337         */
338        public Object get(int index) {
339            return getListableAt(index).value();
340        }
341    
342        /**
343         * Returns the element at the beginning of this list.
344         */
345        public Object getFirst() {
346            try {
347                return _head.next().value();
348            } catch(NullPointerException e) {
349                throw new NoSuchElementException();
350            }
351        }
352    
353        /**
354         * Returns the element at the end of this list.
355         */
356        public Object getLast() {
357            try {
358                return _head.prev().value();
359            } catch(NullPointerException e) {
360                throw new NoSuchElementException();
361            }
362        }
363    
364        /**
365         * Returns the hash code value for this list.  The hash code of a list
366         * is defined to be the result of the following calculation:
367         * <pre>
368         *  hashCode = 1;
369         *  Iterator i = list.iterator();
370         *  while (i.hasNext()) {
371         *      Object obj = i.next();
372         *      hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
373         *  }
374         * </pre>
375         * This ensures that <tt>list1.equals(list2)</tt> implies that
376         * <tt>list1.hashCode()==list2.hashCode()</tt> for any two lists,
377         * <tt>list1</tt> and <tt>list2</tt>, as required by the general
378         * contract of <tt>Object.hashCode</tt>.
379         *
380         * @return the hash code value for this list.
381         * @see Object#hashCode()
382         * @see Object#equals(Object)
383         * @see #equals(Object)
384         */
385        public int hashCode() {
386            int hash = 1;
387            for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) {
388                hash = 31*hash + (null == elt.value() ? 0 : elt.value().hashCode());
389            }
390            return hash;
391        }
392    
393        /**
394         * Returns the index in this list of the first occurrence of the specified
395         * element, or -1 if this list does not contain this element.
396         * More formally, returns the lowest index <tt>i</tt> such that
397         * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
398         * or -1 if there is no such index.
399         *
400         * @param o element to search for.
401         * @return the index in this list of the first occurrence of the specified
402         *         element, or -1 if this list does not contain this element.
403         */
404        public int indexOf(Object o) {
405            int ndx = 0;
406    
407            // perform the null check outside of the loop to save checking every
408            // single time through the loop.
409            if (null == o) {
410                for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) {
411                    if (null == elt.value()) {
412                        return ndx;
413                    }
414                    ndx++;
415                }
416            } else {
417    
418                for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) {
419                    if (o.equals(elt.value())) {
420                        return ndx;
421                    }
422                    ndx++;
423                }
424            }
425            return -1;
426        }
427    
428        /**
429         * Returns <tt>true</tt> if this list contains no elements.
430         * @return <tt>true</tt> if this list contains no elements.
431         */
432        public boolean isEmpty() {
433            return(0 == _size);
434        }
435    
436        /**
437         * Returns a fail-fast iterator.
438         * @see List#iterator
439         */
440        public Iterator iterator() {
441            return listIterator(0);
442        }
443    
444        /**
445         * Returns the index in this list of the last occurrence of the specified
446         * element, or -1 if this list does not contain this element.
447         * More formally, returns the highest index <tt>i</tt> such that
448         * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
449         * or -1 if there is no such index.
450         *
451         * @param o element to search for.
452         * @return the index in this list of the last occurrence of the specified
453         *            element, or -1 if this list does not contain this element.
454         */
455        public int lastIndexOf(Object o) {
456            int ndx = _size-1;
457    
458            // perform the null check outside of the loop to save checking every
459            // single time through the loop.
460            if (null == o) {
461                for(Listable elt = _head.prev(), past = null; null != elt && past != _head.next(); elt = (past = elt).prev()) {
462                    if (null == elt.value()) {
463                        return ndx;
464                    }
465                    ndx--;
466                }
467            } else {
468                for(Listable elt = _head.prev(), past = null; null != elt && past != _head.next(); elt = (past = elt).prev()) {
469                    if (o.equals(elt.value())) {
470                        return ndx;
471                    }
472                    ndx--;
473                }
474            }
475            return -1;
476        }
477    
478        /**
479         * Returns a fail-fast ListIterator.
480         * @see List#listIterator
481         */
482        public ListIterator listIterator() {
483            return listIterator(0);
484        }
485    
486        /**
487         * Returns a fail-fast ListIterator.
488         * @see List#listIterator(int)
489         */
490        public ListIterator listIterator(int index) {
491            if(index<0 || index > _size) {
492                throw new IndexOutOfBoundsException(index + " < 0 or > " + _size);
493            }
494            return new ListIter(index);
495        }
496    
497        /**
498         * Removes the first occurrence in this list of the specified element.
499         * If this list does not contain the element, it is
500         * unchanged.  More formally, removes the element with the lowest index i
501         * such that <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> (if
502         * such an element exists).
503         *
504         * @param o element to be removed from this list, if present.
505         * @return <tt>true</tt> if this list contained the specified element.
506         */
507        public boolean remove(Object o) {
508            for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) {
509                if(null == o && null == elt.value()) {
510                    removeListable(elt);
511                    return true;
512                } else if(o != null && o.equals(elt.value())) {
513                    removeListable(elt);
514                    return true;
515                }
516            }
517            return false;
518        }
519    
520        /**
521         * Removes the element at the specified position in this list (optional
522         * operation).  Shifts any subsequent elements to the left (subtracts one
523         * from their indices).  Returns the element that was removed from the
524         * list.
525         *
526         * @param index the index of the element to removed.
527         * @return the element previously at the specified position.
528         *
529         * @throws IndexOutOfBoundsException if the index is out of range (index
530         *            &lt; 0 || index &gt;= size()).
531         */
532        public Object remove(int index) {
533            Listable elt = getListableAt(index);
534            Object ret = elt.value();
535            removeListable(elt);
536            return ret;
537        }
538    
539        /**
540         * Removes from this list all the elements that are contained in the
541         * specified collection.
542         *
543         * @param c collection that defines which elements will be removed from
544         *          this list.
545         * @return <tt>true</tt> if this list changed as a result of the call.
546         */
547        public boolean removeAll(Collection c) {
548            if(0 == c.size() || 0 == _size) {
549                return false;
550            } else {
551                boolean changed = false;
552                Iterator it = iterator();
553                while(it.hasNext()) {
554                    if(c.contains(it.next())) {
555                        it.remove();
556                        changed = true;
557                    }
558                }
559                return changed;
560            }
561        }
562    
563        /**
564         * Removes the first element of this list, if any.
565         */
566        public Object removeFirst() {
567            if(_head.next() != null) {
568                Object val = _head.next().value();
569                removeListable(_head.next());
570                return val;
571            } else {
572                throw new NoSuchElementException();
573            }
574        }
575    
576        /**
577         * Removes the last element of this list, if any.
578         */
579        public Object removeLast() {
580            if(_head.prev() != null) {
581                Object val = _head.prev().value();
582                removeListable(_head.prev());
583                return val;
584            } else {
585                throw new NoSuchElementException();
586            }
587        }
588    
589        /**
590         * Retains only the elements in this list that are contained in the
591         * specified collection.  In other words, removes
592         * from this list all the elements that are not contained in the specified
593         * collection.
594         *
595         * @param c collection that defines which elements this set will retain.
596         *
597         * @return <tt>true</tt> if this list changed as a result of the call.
598         */
599        public boolean retainAll(Collection c) {
600            boolean changed = false;
601            Iterator it = iterator();
602            while(it.hasNext()) {
603                if(!c.contains(it.next())) {
604                    it.remove();
605                    changed = true;
606                }
607            }
608            return changed;
609        }
610    
611        /**
612         * Replaces the element at the specified position in this list with the
613         * specified element.
614         *
615         * @param index index of element to replace.
616         * @param element element to be stored at the specified position.
617         * @return the element previously at the specified position.
618         *
619         * @throws ClassCastException if the class of the specified element
620         *           prevents it from being added to this list.
621         * @throws IllegalArgumentException if some aspect of the specified
622         *            element prevents it from being added to this list.
623         * @throws IndexOutOfBoundsException if the index is out of range
624         *             (index &lt; 0 || index &gt;= size()).
625         */
626        public Object set(int index, Object element) {
627            Listable elt = getListableAt(index);
628            Object val = elt.setValue(element);
629            broadcastListableChanged(elt);
630            return val;
631        }
632    
633        /**
634         * Returns the number of elements in this list.
635         * @return the number of elements in this list.
636         */
637        public int size() {
638            return _size;
639        }
640    
641        /**
642         * Returns an array containing all of the elements in this list in proper
643         * sequence.  Obeys the general contract of the {@link Collection#toArray} method.
644         *
645         * @return an array containing all of the elements in this list in proper
646         *         sequence.
647         */
648        public Object[] toArray() {
649            Object[] array = new Object[_size];
650            int i = 0;
651            for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) {
652                array[i++] = elt.value();
653            }
654            return array;
655        }
656    
657        /**
658         * Returns an array containing all of the elements in this list in proper
659         * sequence; the runtime type of the returned array is that of the
660         * specified array. Obeys the general contract of the
661         * {@link Collection#toArray} method.
662         *
663         * @param a      the array into which the elements of this list are to
664         *               be stored, if it is big enough; otherwise, a new array of the
665         *               same runtime type is allocated for this purpose.
666         * @return an array containing the elements of this list.
667         * @exception ArrayStoreException
668         *                   if the runtime type of the specified array
669         *                   is not a supertype of the runtime type of every element in
670         *                   this list.
671         */
672        public Object[] toArray(Object a[]) {
673            if(a.length < _size) {
674                a = (Object[])Array.newInstance(a.getClass().getComponentType(), _size);
675            }
676            int i = 0;
677            for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) {
678                a[i++] = elt.value();
679            }
680            if(a.length > _size) {
681                a[_size] = null; // should we null out the rest of the array also? java.util.LinkedList doesn't
682            }
683            return a;
684        }
685    
686        /**
687         * Returns a {@link String} representation of this list, suitable for debugging.
688         * @return a {@link String} representation of this list, suitable for debugging.
689         */
690        public String toString() {
691            StringBuffer buf = new StringBuffer();
692            buf.append("[");
693            for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) {
694                if(_head.next() != elt) {
695                    buf.append(", ");
696                }
697                buf.append(elt.value());
698            }
699            buf.append("]");
700            return buf.toString();
701        }
702    
703        /**
704         * Returns a fail-fast sublist.
705         * @see List#subList(int,int)
706         */
707        public List subList(int i, int j) {
708            if(i < 0 || j > _size || i > j) {
709                throw new IndexOutOfBoundsException();
710            } else if(i == 0 && j == _size) {
711                return this;
712            } else {
713                return new CursorableSubList(this,i,j);
714            }
715        }
716    
717        //--- protected methods ------------------------------------------
718    
719        /**
720         * Inserts a new <i>value</i> into my
721         * list, after the specified <i>before</i> element, and before the
722         * specified <i>after</i> element
723         *
724         * @return the newly created 
725         * {@link org.apache.commons.collections.CursorableLinkedList.Listable}
726         */
727        protected Listable insertListable(Listable before, Listable after, Object value) {
728            _modCount++;
729            _size++;
730            Listable elt = new Listable(before,after,value);
731            if(null != before) {
732                before.setNext(elt);
733            } else {
734                _head.setNext(elt);
735            }
736    
737            if(null != after) {
738                after.setPrev(elt);
739            } else {
740                _head.setPrev(elt);
741            }
742            broadcastListableInserted(elt);
743            return elt;
744        }
745    
746        /**
747         * Removes the given 
748         * {@link org.apache.commons.collections.CursorableLinkedList.Listable} 
749         * from my list.
750         */
751        protected void removeListable(Listable elt) {
752            _modCount++;
753            _size--;
754            if(_head.next() == elt) {
755                _head.setNext(elt.next());
756            }
757            if(null != elt.next()) {
758                elt.next().setPrev(elt.prev());
759            }
760            if(_head.prev() == elt) {
761                _head.setPrev(elt.prev());
762            }
763            if(null != elt.prev()) {
764                elt.prev().setNext(elt.next());
765            }
766            broadcastListableRemoved(elt);
767        }
768    
769        /**
770         * Returns the 
771         * {@link org.apache.commons.collections.CursorableLinkedList.Listable} 
772         * at the specified index.
773         *
774         * @throws IndexOutOfBoundsException if index is less than zero or
775         *         greater than or equal to the size of this list.
776         */
777        protected Listable getListableAt(int index) {
778            if(index < 0 || index >= _size) {
779                throw new IndexOutOfBoundsException(String.valueOf(index) + " < 0 or " + String.valueOf(index) + " >= " + _size);
780            }
781            if(index <=_size/2) {
782                Listable elt = _head.next();
783                for(int i = 0; i < index; i++) {
784                    elt = elt.next();
785                }
786                return elt;
787            } else {
788                Listable elt = _head.prev();
789                for(int i = (_size-1); i > index; i--) {
790                    elt = elt.prev();
791                }
792                return elt;
793            }
794        }
795    
796        /**
797         * Registers a {@link CursorableLinkedList.Cursor} to be notified
798         * of changes to this list.
799         */
800        protected void registerCursor(Cursor cur) {
801            // We take this opportunity to clean the _cursors list
802            // of WeakReference objects to garbage-collected cursors.
803            for (Iterator it = _cursors.iterator(); it.hasNext(); ) {
804                WeakReference ref = (WeakReference) it.next();
805                if (ref.get() == null) {
806                    it.remove();
807                }
808            }
809            
810            _cursors.add( new WeakReference(cur) );
811        }
812    
813        /**
814         * Removes a {@link CursorableLinkedList.Cursor} from
815         * the set of cursors to be notified of changes to this list.
816         */
817        protected void unregisterCursor(Cursor cur) {
818            for (Iterator it = _cursors.iterator(); it.hasNext(); ) {
819                WeakReference ref = (WeakReference) it.next();
820                Cursor cursor = (Cursor) ref.get();
821                if (cursor == null) {
822                    // some other unrelated cursor object has been 
823                    // garbage-collected; let's take the opportunity to
824                    // clean up the cursors list anyway..
825                    it.remove();
826                    
827                } else if (cursor == cur) {
828                    ref.clear();
829                    it.remove();
830                    break;
831                }
832            }
833        }
834    
835        /**
836         * Informs all of my registered cursors that they are now
837         * invalid.
838         */
839        protected void invalidateCursors() {
840            Iterator it = _cursors.iterator();
841            while (it.hasNext()) {
842                WeakReference ref = (WeakReference) it.next();
843                Cursor cursor = (Cursor) ref.get();
844                if (cursor != null) {
845                    // cursor is null if object has been garbage-collected
846                    cursor.invalidate();
847                    ref.clear();
848                }
849                it.remove();
850            }
851        }
852    
853        /**
854         * Informs all of my registered cursors that the specified
855         * element was changed.
856         * @see #set(int,java.lang.Object)
857         */
858        protected void broadcastListableChanged(Listable elt) {
859            Iterator it = _cursors.iterator();
860            while (it.hasNext()) {
861                WeakReference ref = (WeakReference) it.next();
862                Cursor cursor = (Cursor) ref.get();
863                if (cursor == null) {
864                    it.remove(); // clean up list
865                } else {
866                    cursor.listableChanged(elt);
867                }
868            }
869        }
870    
871        /**
872         * Informs all of my registered cursors that the specified
873         * element was just removed from my list.
874         */
875        protected void broadcastListableRemoved(Listable elt) {
876            Iterator it = _cursors.iterator();
877            while (it.hasNext()) {
878                WeakReference ref = (WeakReference) it.next();
879                Cursor cursor = (Cursor) ref.get();
880                if (cursor == null) {
881                    it.remove(); // clean up list
882                } else {
883                    cursor.listableRemoved(elt);
884                }
885            }
886        }
887    
888        /**
889         * Informs all of my registered cursors that the specified
890         * element was just added to my list.
891         */
892        protected void broadcastListableInserted(Listable elt) {
893            Iterator it = _cursors.iterator();
894            while (it.hasNext()) {
895                WeakReference ref = (WeakReference) it.next();
896                Cursor cursor = (Cursor) ref.get();
897                if (cursor == null) {
898                    it.remove();  // clean up list
899                } else {
900                    cursor.listableInserted(elt);
901                }
902            }
903        }
904    
905        private void writeObject(ObjectOutputStream out) throws IOException {
906            out.defaultWriteObject();
907            out.writeInt(_size);
908            Listable cur = _head.next();
909            while (cur != null) {
910                out.writeObject(cur.value());
911                cur = cur.next();
912            }
913        }
914    
915        private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
916            in.defaultReadObject();
917            _size = 0;
918            _modCount = 0;
919            _cursors = new ArrayList();
920            _head = new Listable(null,null,null);
921            int size = in.readInt();
922            for (int i=0;i<size;i++) {
923                this.add(in.readObject());
924            }
925        }
926    
927        //--- protected attributes ---------------------------------------
928    
929        /** The number of elements in me. */
930        protected transient int _size = 0;
931    
932        /**
933         * A sentry node.
934         * <p>
935         * <tt>_head.next()</tt> points to the first element in the list,
936         * <tt>_head.prev()</tt> to the last. Note that it is possible for
937         * <tt>_head.next().prev()</tt> and <tt>_head.prev().next()</tt> to be
938         * non-null, as when I am a sublist for some larger list.
939         * Use <tt>== _head.next()</tt> and <tt>== _head.prev()</tt> to determine
940         * if a given 
941         * {@link org.apache.commons.collections.CursorableLinkedList.Listable} 
942         * is the first or last element in the list.
943         */
944        protected transient Listable _head = new Listable(null,null,null);
945    
946        /** Tracks the number of structural modifications to me. */
947        protected transient int _modCount = 0;
948    
949        /**
950         * A list of the currently {@link CursorableLinkedList.Cursor}s currently
951         * open in this list.
952         */
953        protected transient List _cursors = new ArrayList();
954    
955        //--- inner classes ----------------------------------------------
956    
957        static class Listable implements Serializable {
958            private Listable _prev = null;
959            private Listable _next = null;
960            private Object _val = null;
961    
962            Listable(Listable prev, Listable next, Object val) {
963                _prev = prev;
964                _next = next;
965                _val = val;
966            }
967    
968            Listable next() {
969                return _next;
970            }
971    
972            Listable prev() {
973                return _prev;
974            }
975    
976            Object value() {
977                return _val;
978            }
979    
980            void setNext(Listable next) {
981                _next = next;
982            }
983    
984            void setPrev(Listable prev) {
985                _prev = prev;
986            }
987    
988            Object setValue(Object val) {
989                Object temp = _val;
990                _val = val;
991                return temp;
992            }
993        }
994    
995        class ListIter implements ListIterator {
996            Listable _cur = null;
997            Listable _lastReturned = null;
998            int _expectedModCount = _modCount;
999            int _nextIndex = 0;
1000    
1001            ListIter(int index) {
1002                if(index == 0) {
1003                    _cur = new Listable(null,_head.next(),null);
1004                    _nextIndex = 0;
1005                } else if(index == _size) {
1006                    _cur = new Listable(_head.prev(),null,null);
1007                    _nextIndex = _size;
1008                } else {
1009                    Listable temp = getListableAt(index);
1010                    _cur = new Listable(temp.prev(),temp,null);
1011                    _nextIndex = index;
1012                }
1013            }
1014    
1015            public Object previous() {
1016                checkForComod();
1017                if(!hasPrevious()) {
1018                    throw new NoSuchElementException();
1019                } else {
1020                    Object ret = _cur.prev().value();
1021                    _lastReturned = _cur.prev();
1022                    _cur.setNext(_cur.prev());
1023                    _cur.setPrev(_cur.prev().prev());
1024                    _nextIndex--;
1025                    return ret;
1026                }
1027            }
1028    
1029            public boolean hasNext() {
1030                checkForComod();
1031                return(null != _cur.next() && _cur.prev() != _head.prev());
1032            }
1033    
1034            public Object next() {
1035                checkForComod();
1036                if(!hasNext()) {
1037                    throw new NoSuchElementException();
1038                } else {
1039                    Object ret = _cur.next().value();
1040                    _lastReturned = _cur.next();
1041                    _cur.setPrev(_cur.next());
1042                    _cur.setNext(_cur.next().next());
1043                    _nextIndex++;
1044                    return ret;
1045                }
1046            }
1047    
1048            public int previousIndex() {
1049                checkForComod();
1050                if(!hasPrevious()) {
1051                    return -1;
1052                }
1053                return _nextIndex-1;
1054            }
1055    
1056            public boolean hasPrevious() {
1057                checkForComod();
1058                return(null != _cur.prev() && _cur.next() != _head.next());
1059            }
1060    
1061            public void set(Object o) {
1062                checkForComod();
1063                try {
1064                    _lastReturned.setValue(o);
1065                } catch(NullPointerException e) {
1066                    throw new IllegalStateException();
1067                }
1068            }
1069    
1070            public int nextIndex() {
1071                checkForComod();
1072                if(!hasNext()) {
1073                    return size();
1074                }
1075                return _nextIndex;
1076            }
1077    
1078            public void remove() {
1079                checkForComod();
1080                if(null == _lastReturned) {
1081                    throw new IllegalStateException();
1082                } else {
1083                    _cur.setNext(_lastReturned == _head.prev() ? null : _lastReturned.next());
1084                    _cur.setPrev(_lastReturned == _head.next() ? null : _lastReturned.prev());
1085                    removeListable(_lastReturned);
1086                    _lastReturned = null;
1087                    _nextIndex--;
1088                    _expectedModCount++;
1089                }
1090            }
1091    
1092            public void add(Object o) {
1093                checkForComod();
1094                _cur.setPrev(insertListable(_cur.prev(),_cur.next(),o));
1095                _lastReturned = null;
1096                _nextIndex++;
1097                _expectedModCount++;
1098            }
1099    
1100            protected void checkForComod() {
1101                if(_expectedModCount != _modCount) {
1102                    throw new ConcurrentModificationException();
1103                }
1104            }
1105        }
1106    
1107        public class Cursor extends ListIter implements ListIterator {
1108            boolean _valid = false;
1109    
1110            Cursor(int index) {
1111                super(index);
1112                _valid = true;
1113                registerCursor(this);
1114            }
1115    
1116            public int previousIndex() {
1117                throw new UnsupportedOperationException();
1118            }
1119    
1120            public int nextIndex() {
1121                throw new UnsupportedOperationException();
1122            }
1123    
1124            public void add(Object o) {
1125                checkForComod();
1126                Listable elt = insertListable(_cur.prev(),_cur.next(),o);
1127                _cur.setPrev(elt);
1128                _cur.setNext(elt.next());
1129                _lastReturned = null;
1130                _nextIndex++;
1131                _expectedModCount++;
1132            }
1133    
1134            protected void listableRemoved(Listable elt) {
1135                if(null == _head.prev()) {
1136                    _cur.setNext(null);
1137                } else if(_cur.next() == elt) {
1138                    _cur.setNext(elt.next());
1139                }
1140                if(null == _head.next()) {
1141                    _cur.setPrev(null);
1142                } else if(_cur.prev() == elt) {
1143                    _cur.setPrev(elt.prev());
1144                }
1145                if(_lastReturned == elt) {
1146                    _lastReturned = null;
1147                }
1148            }
1149    
1150            protected void listableInserted(Listable elt) {
1151                if(null == _cur.next() && null == _cur.prev()) {
1152                    _cur.setNext(elt);
1153                } else if(_cur.prev() == elt.prev()) {
1154                    _cur.setNext(elt);
1155                }
1156                if(_cur.next() == elt.next()) {
1157                    _cur.setPrev(elt);
1158                }
1159                if(_lastReturned == elt) {
1160                    _lastReturned = null;
1161                }
1162            }
1163    
1164            protected void listableChanged(Listable elt) {
1165                if(_lastReturned == elt) {
1166                    _lastReturned = null;
1167                }
1168            }
1169    
1170            protected void checkForComod() {
1171                if(!_valid) {
1172                    throw new ConcurrentModificationException();
1173                }
1174            }
1175    
1176            protected void invalidate() {
1177                _valid = false;
1178            }
1179    
1180            /**
1181             * Mark this cursor as no longer being needed. Any resources
1182             * associated with this cursor are immediately released.
1183             * In previous versions of this class, it was mandatory to close
1184             * all cursor objects to avoid memory leaks. It is <i>no longer</i>
1185             * necessary to call this close method; an instance of this class
1186             * can now be treated exactly like a normal iterator.
1187             */
1188            public void close() {
1189                if(_valid) {
1190                    _valid = false;
1191                    unregisterCursor(this);
1192                }
1193            }
1194        }
1195    
1196    }
1197    
1198    /**
1199     * @deprecated Use new version in list subpackage, which has been rewritten
1200     *  and now returns the cursor from the listIterator method. Will be removed in v4.0
1201     */
1202    class CursorableSubList extends CursorableLinkedList implements List {
1203    
1204        //--- constructors -----------------------------------------------
1205    
1206        CursorableSubList(CursorableLinkedList list, int from, int to) {
1207            if(0 > from || list.size() < to) {
1208                throw new IndexOutOfBoundsException();
1209            } else if(from > to) {
1210                throw new IllegalArgumentException();
1211            }
1212            _list = list;
1213            if(from < list.size()) {
1214                _head.setNext(_list.getListableAt(from));
1215                _pre = (null == _head.next()) ? null : _head.next().prev();
1216            } else {
1217                _pre = _list.getListableAt(from-1);
1218            }
1219            if(from == to) {
1220                _head.setNext(null);
1221                _head.setPrev(null);
1222                if(to < list.size()) {
1223                    _post = _list.getListableAt(to);
1224                } else {
1225                    _post = null;
1226                }
1227            } else {
1228                _head.setPrev(_list.getListableAt(to-1));
1229                _post = _head.prev().next();
1230            }
1231            _size = to - from;
1232            _modCount = _list._modCount;
1233        }
1234    
1235        //--- public methods ------------------------------------------
1236    
1237        public void clear() {
1238            checkForComod();
1239            Iterator it = iterator();
1240            while(it.hasNext()) {
1241                it.next();
1242                it.remove();
1243            }
1244        }
1245    
1246        public Iterator iterator() {
1247            checkForComod();
1248            return super.iterator();
1249        }
1250    
1251        public int size() {
1252            checkForComod();
1253            return super.size();
1254        }
1255    
1256        public boolean isEmpty() {
1257            checkForComod();
1258            return super.isEmpty();
1259        }
1260    
1261        public Object[] toArray() {
1262            checkForComod();
1263            return super.toArray();
1264        }
1265    
1266        public Object[] toArray(Object a[]) {
1267            checkForComod();
1268            return super.toArray(a);
1269        }
1270    
1271        public boolean contains(Object o) {
1272            checkForComod();
1273            return super.contains(o);
1274        }
1275    
1276        public boolean remove(Object o) {
1277            checkForComod();
1278            return super.remove(o);
1279        }
1280    
1281        public Object removeFirst() {
1282            checkForComod();
1283            return super.removeFirst();
1284        }
1285    
1286        public Object removeLast() {
1287            checkForComod();
1288            return super.removeLast();
1289        }
1290    
1291        public boolean addAll(Collection c) {
1292            checkForComod();
1293            return super.addAll(c);
1294        }
1295    
1296        public boolean add(Object o) {
1297            checkForComod();
1298            return super.add(o);
1299        }
1300    
1301        public boolean addFirst(Object o) {
1302            checkForComod();
1303            return super.addFirst(o);
1304        }
1305    
1306        public boolean addLast(Object o) {
1307            checkForComod();
1308            return super.addLast(o);
1309        }
1310    
1311        public boolean removeAll(Collection c) {
1312            checkForComod();
1313            return super.removeAll(c);
1314        }
1315    
1316        public boolean containsAll(Collection c) {
1317            checkForComod();
1318            return super.containsAll(c);
1319        }
1320    
1321        public boolean addAll(int index, Collection c) {
1322            checkForComod();
1323            return super.addAll(index,c);
1324        }
1325    
1326        public int hashCode() {
1327            checkForComod();
1328            return super.hashCode();
1329        }
1330    
1331        public boolean retainAll(Collection c) {
1332            checkForComod();
1333            return super.retainAll(c);
1334        }
1335    
1336        public Object set(int index, Object element) {
1337            checkForComod();
1338            return super.set(index,element);
1339        }
1340    
1341        public boolean equals(Object o) {
1342            checkForComod();
1343            return super.equals(o);
1344        }
1345    
1346        public Object get(int index) {
1347            checkForComod();
1348            return super.get(index);
1349        }
1350    
1351        public Object getFirst() {
1352            checkForComod();
1353            return super.getFirst();
1354        }
1355    
1356        public Object getLast() {
1357            checkForComod();
1358            return super.getLast();
1359        }
1360    
1361        public void add(int index, Object element) {
1362            checkForComod();
1363            super.add(index,element);
1364        }
1365    
1366        public ListIterator listIterator(int index) {
1367            checkForComod();
1368            return super.listIterator(index);
1369        }
1370    
1371        public Object remove(int index) {
1372            checkForComod();
1373            return super.remove(index);
1374        }
1375    
1376        public int indexOf(Object o) {
1377            checkForComod();
1378            return super.indexOf(o);
1379        }
1380    
1381        public int lastIndexOf(Object o) {
1382            checkForComod();
1383            return super.lastIndexOf(o);
1384        }
1385    
1386        public ListIterator listIterator() {
1387            checkForComod();
1388            return super.listIterator();
1389        }
1390    
1391        public List subList(int fromIndex, int toIndex) {
1392            checkForComod();
1393            return super.subList(fromIndex,toIndex);
1394        }
1395    
1396        //--- protected methods ------------------------------------------
1397    
1398        /**
1399         * Inserts a new <i>value</i> into my
1400         * list, after the specified <i>before</i> element, and before the
1401         * specified <i>after</i> element
1402         *
1403         * @return the newly created {@link CursorableLinkedList.Listable}
1404         */
1405        protected Listable insertListable(Listable before, Listable after, Object value) {
1406            _modCount++;
1407            _size++;
1408            Listable elt = _list.insertListable((null == before ? _pre : before), (null == after ? _post : after),value);
1409            if(null == _head.next()) {
1410                _head.setNext(elt);
1411                _head.setPrev(elt);
1412            }
1413            if(before == _head.prev()) {
1414                _head.setPrev(elt);
1415            }
1416            if(after == _head.next()) {
1417                _head.setNext(elt);
1418            }
1419            broadcastListableInserted(elt);
1420            return elt;
1421        }
1422    
1423        /**
1424         * Removes the given {@link CursorableLinkedList.Listable} from my list.
1425         */
1426        protected void removeListable(Listable elt) {
1427            _modCount++;
1428            _size--;
1429            if(_head.next() == elt && _head.prev() == elt) {
1430                _head.setNext(null);
1431                _head.setPrev(null);
1432            }
1433            if(_head.next() == elt) {
1434                _head.setNext(elt.next());
1435            }
1436            if(_head.prev() == elt) {
1437                _head.setPrev(elt.prev());
1438            }
1439            _list.removeListable(elt);
1440            broadcastListableRemoved(elt);
1441        }
1442    
1443        /**
1444         * Test to see if my underlying list has been modified
1445         * by some other process.  If it has, throws a
1446         * {@link ConcurrentModificationException}, otherwise
1447         * quietly returns.
1448         *
1449         * @throws ConcurrentModificationException
1450         */
1451        protected void checkForComod() throws ConcurrentModificationException {
1452            if(_modCount != _list._modCount) {
1453                throw new ConcurrentModificationException();
1454            }
1455        }
1456    
1457        //--- protected attributes ---------------------------------------
1458    
1459        /** My underlying list */
1460        protected CursorableLinkedList _list = null;
1461    
1462        /** The element in my underlying list preceding the first element in my list. */
1463        protected Listable _pre = null;
1464    
1465        /** The element in my underlying list following the last element in my list. */
1466        protected Listable _post = null;
1467    
1468    }