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