View Javadoc

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