Java > Open Source Codes > org > apache > commons > collections > CursorableLinkedList


1 /*
2  * Copyright 2002-2004 The Apache Software Foundation
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package org.apache.commons.collections;
17
18 import java.io.IOException ;
19 import java.io.ObjectInputStream ;
20 import java.io.ObjectOutputStream ;
21 import java.io.Serializable ;
22 import java.lang.reflect.Array ;
23 import java.util.ArrayList ;
24 import java.util.Collection ;
25 import java.util.ConcurrentModificationException ;
26 import java.util.Iterator ;
27 import java.util.List ;
28 import java.util.ListIterator ;
29 import java.util.NoSuchElementException ;
30 import java.lang.ref.WeakReference ;
31
32 /**
33  * A doubly-linked list implementation of the {@link List} interface,
34  * supporting a {@link ListIterator} that allows concurrent modifications
35  * to the underlying list.
36  * <p>
37  * Implements all of the optional {@link List} operations, the
38  * stack/queue/dequeue operations available in {@link java.util.LinkedList}
39  * and supports a {@link ListIterator} that allows concurrent modifications
40  * to the underlying list (see {@link #cursor}).
41  * <p>
42  * <b>Note that this implementation is not synchronized.</b>
43  *
44  * @deprecated Use new version in list subpackage, which has been rewritten
45  * and now returns the cursor from the listIterator method. Will be removed in v4.0
46  * @see java.util.LinkedList
47  * @since Commons Collections 1.0
48  * @version $Revision: 1.23 $ $Date: 2004/02/18 01:15:42 $
49  *
50  * @author Rodney Waldhoff
51  * @author Janek Bogucki
52  * @author Simon Kitching
53  */
54 public class CursorableLinkedList implements List , Serializable {
55     /** Ensure serialization compatibility */
56     private static final long serialVersionUID = 8836393098519411393L;
57
58     //--- public methods ---------------------------------------------
59
60     /**
61      * Appends the specified element to the end of this list.
62      *
63      * @param o element to be appended to this list.
64      * @return <tt>true</tt>
65      */
66     public boolean add(Object o) {
67         insertListable(_head.prev(),null,o);
68         return true;
69     }
70
71     /**
72      * Inserts the specified element at the specified position in this list.
73      * Shifts the element currently at that position (if any) and any subsequent
74      * elements to the right (adds one to their indices).
75      *
76      * @param index index at which the specified element is to be inserted.
77      * @param element element to be inserted.
78      *
79      * @throws ClassCastException if the class of the specified element
80      * prevents it from being added to this list.
81      * @throws IllegalArgumentException if some aspect of the specified
82      * element prevents it from being added to this list.
83      * @throws IndexOutOfBoundsException if the index is out of range
84      * (index &lt; 0 || index &gt; size()).
85      */
86     public void add(int index, Object element) {
87         if(index == _size) {
88             add(element);
89         } else {
90             if(index < 0 || index > _size) {
91                 throw new IndexOutOfBoundsException (String.valueOf(index) + " < 0 or " + String.valueOf(index) + " > " + _size);
92             }
93             Listable succ = (isEmpty() ? null : getListableAt(index));
94             Listable pred = (null == succ ? null : succ.prev());
95             insertListable(pred,succ,element);
96         }
97     }
98
99     /**
100      * Appends all of the elements in the specified collection to the end of
101      * this list, in the order that they are returned by the specified
102      * {@link Collection}'s {@link Iterator}. The behavior of this operation is
103      * unspecified if the specified collection is modified while
104      * the operation is in progress. (Note that this will occur if the
105      * specified collection is this list, and it's nonempty.)
106      *
107      * @param c collection whose elements are to be added to this list.
108      * @return <tt>true</tt> if this list changed as a result of the call.
109      *
110      * @throws ClassCastException if the class of an element in the specified
111      * collection prevents it from being added to this list.
112      * @throws IllegalArgumentException if some aspect of an element in the
113      * specified collection prevents it from being added to this
114      * list.
115      */
116     public boolean addAll(Collection c) {
117         if(c.isEmpty()) {
118             return false;
119         }
120         Iterator it = c.iterator();
121         while(it.hasNext()) {
122             insertListable(_head.prev(),null,it.next());
123         }
124         return true;
125     }
126
127     /**
128      * Inserts all of the elements in the specified collection into this
129      * list at the specified position. Shifts the element currently at
130      * that position (if any) and any subsequent elements to the right
131      * (increases their indices). The new elements will appear in this
132      * list in the order that they are returned by the specified
133      * {@link Collection}'s {@link Iterator}. The behavior of this operation is
134      * unspecified if the specified collection is modified while the
135      * operation is in progress. (Note that this will occur if the specified
136      * collection is this list, and it's nonempty.)
137      *
138      * @param index index at which to insert first element from the specified
139      * collection.
140      * @param c elements to be inserted into this list.
141      * @return <tt>true</tt> if this list changed as a result of the call.
142      *
143      * @throws ClassCastException if the class of one of elements of the
144      * specified collection prevents it from being added to this
145      * list.
146      * @throws IllegalArgumentException if some aspect of one of elements of
147      * the specified collection prevents it from being added to
148      * this list.
149      * @throws IndexOutOfBoundsException if the index is out of range (index
150      * &lt; 0 || index &gt; size()).
151      */
152     public boolean addAll(int index, Collection c) {
153         if(c.isEmpty()) {
154             return false;
155         } else if(_size == index || _size == 0) {
156             return addAll(c);
157         } else {
158             Listable succ = getListableAt(index);
159             Listable pred = (null == succ) ? null : succ.prev();
160             Iterator it = c.iterator();
161             while(it.hasNext()) {
162                 pred = insertListable(pred,succ,it.next());
163             }
164             return true;
165         }
166     }
167
168     /**
169      * Inserts the specified element at the beginning of this list.
170      * (Equivalent to {@link #add(int,java.lang.Object) <tt>add(0,o)</tt>}).
171      *
172      * @param o element to be prepended to this list.
173      * @return <tt>true</tt>
174      */
175     public boolean addFirst(Object o) {
176         insertListable(null,_head.next(),o);
177         return true;
178     }
179
180     /**
181      * Inserts the specified element at the end of this list.
182      * (Equivalent to {@link #add(java.lang.Object)}).
183      *
184      * @param o element to be appended to this list.
185      * @return <tt>true</tt>
186      */
187     public boolean addLast(Object o) {
188         insertListable(_head.prev(),null,o);
189         return true;
190     }
191
192     /**
193      * Removes all of the elements from this list. This
194      * list will be empty after this call returns (unless
195      * it throws an exception).
196      */
197     public void clear() {
198         /*
199         // this is the quick way, but would force us
200         // to break all the cursors
201         _modCount++;
202         _head.setNext(null);
203         _head.setPrev(null);
204         _size = 0;
205         */
206         Iterator it = iterator();
207         while(it.hasNext()) {
208             it.next();
209             it.remove();
210         }
211     }
212
213     /**
214      * Returns <tt>true</tt> if this list contains the specified element.
215      * More formally, returns <tt>true</tt> if and only if this list contains
216      * at least one element <tt>e</tt> such that
217      * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
218      *
219      * @param o element whose presence in this list is to be tested.
220      * @return <tt>true</tt> if this list contains the specified element.
221      */
222     public boolean contains(Object o) {
223         for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) {
224             if((null == o && null == elt.value()) ||
225                (o != null && o.equals(elt.value()))) {
226                 return true;
227             }
228         }
229         return false;
230     }
231
232     /**
233      * Returns <tt>true</tt> if this list contains all of the elements of the
234      * specified collection.
235      *
236      * @param c collection to be checked for containment in this list.
237      * @return <tt>true</tt> if this list contains all of the elements of the
238      * specified collection.
239      */
240     public boolean containsAll(Collection c) {
241         Iterator it = c.iterator();
242         while(it.hasNext()) {
243             if(!this.contains(it.next())) {
244                 return false;
245             }
246         }
247         return true;
248     }
249
250     /**
251      * Returns a {@link ListIterator} for iterating through the
252      * elements of this list. Unlike {@link #iterator}, a cursor
253      * is not bothered by concurrent modifications to the
254      * underlying list.
255      * <p>
256      * Specifically, when elements are added to the list before or
257      * after the cursor, the cursor simply picks them up automatically.
258      * When the "current" (i.e., last returned by {@link ListIterator#next}
259      * or {@link ListIterator#previous}) element of the list is removed,
260      * the cursor automatically adjusts to the change (invalidating the
261      * last returned value--i.e., it cannot be removed).
262      * <p>
263      * Note that the returned {@link ListIterator} does not support the
264      * {@link ListIterator#nextIndex} and {@link ListIterator#previousIndex}
265      * methods (they throw {@link UnsupportedOperationException} when invoked.
266      * <p>
267      * Historical Note: In previous versions of this class, the object
268      * returned from this method was required to be explicitly closed. This
269      * is no longer necessary.
270      *
271      * @see #cursor(int)
272      * @see #listIterator
273      * @see CursorableLinkedList.Cursor
274      */
275     public CursorableLinkedList.Cursor cursor() {
276         return new Cursor(0);
277     }
278
279     /**
280      * Returns a {@link ListIterator} for iterating through the
281      * elements of this list, initialized such that
282      * {@link ListIterator#next} will return the element at
283      * the specified index (if any) and {@link ListIterator#previous}
284      * will return the element immediately preceding it (if any).
285      * Unlike {@link #iterator}, a cursor
286      * is not bothered by concurrent modifications to the
287      * underlying list.
288      *
289      * @see #cursor
290      * @see #listIterator(int)
291      * @see CursorableLinkedList.Cursor
292      * @throws IndexOutOfBoundsException if the index is out of range (index
293      * &lt; 0 || index &gt; size()).
294      */
295     public CursorableLinkedList.Cursor cursor(int i) {
296         return new Cursor(i);
297     }
298
299     /**
300      * Compares the specified object with this list for equality. Returns
301      * <tt>true</tt> if and only if the specified object is also a list, both
302      * lists have the same size, and all corresponding pairs of elements in
303      * the two lists are <i>equal</i>. (Two elements <tt>e1</tt> and
304      * <tt>e2</tt> are <i>equal</i> if <tt>(e1==null ? e2==null :
305      * e1.equals(e2))</tt>.) In other words, two lists are defined to be
306      * equal if they contain the same elements in the same order. This
307      * definition ensures that the equals method works properly across
308      * different implementations of the <tt>List</tt> interface.
309      *
310      * @param o the object to be compared for equality with this list.
311      * @return <tt>true</tt> if the specified object is equal to this list.
312      */
313     public boolean equals(Object o) {
314         if(o == this) {
315             return true;
316         } else if(!(o instanceof List )) {
317             return false;
318         }
319         Iterator it = ((List )o).listIterator();
320         for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) {
321             if(!it.hasNext() || (null == elt.value() ? null != it.next() : !(elt.value().equals(it.next()))) ) {
322                 return false;
323             }
324         }
325         return !it.hasNext();
326     }
327
328     /**
329      * Returns the element at the specified position in this list.
330      *
331      * @param index index of element to return.
332      * @return the element at the specified position in this list.
333      *
334      * @throws IndexOutOfBoundsException if the index is out of range (index
335      * &lt; 0 || index &gt;= size()).
336      */
337     public Object get(int index) {
338         return getListableAt(index).value();
339     }
340
341     /**
342      * Returns the element at the beginning of this list.
343      */
344     public Object getFirst() {
345         try {
346             return _head.next().value();
347         } catch(NullPointerException e) {
348             throw new NoSuchElementException ();
349         }
350     }
351
352     /**
353      * Returns the element at the end of this list.
354      */
355     public Object getLast() {
356         try {
357             return _head.prev().value();
358         } catch(NullPointerException e) {
359             throw new NoSuchElementException ();
360         }
361     }
362
363     /**
364      * Returns the hash code value for this list. The hash code of a list
365      * is defined to be the result of the following calculation:
366      * <pre>
367      * hashCode = 1;
368      * Iterator i = list.iterator();
369      * while (i.hasNext()) {
370      * Object obj = i.next();
371      * hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode());
372      * }
373      * </pre>
374      * This ensures that <tt>list1.equals(list2)</tt> implies that
375      * <tt>list1.hashCode()==list2.hashCode()</tt> for any two lists,
376      * <tt>list1</tt> and <tt>list2</tt>, as required by the general
377      * contract of <tt>Object.hashCode</tt>.
378      *
379      * @return the hash code value for this list.
380      * @see Object#hashCode()
381      * @see Object#equals(Object)
382      * @see #equals(Object)
383      */
384     public int hashCode() {
385         int hash = 1;
386         for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) {
387             hash = 31*hash + (null == elt.value() ? 0 : elt.value().hashCode());
388         }
389         return hash;
390     }
391
392     /**
393      * Returns the index in this list of the first occurrence of the specified
394      * element, or -1 if this list does not contain this element.
395      * More formally, returns the lowest index <tt>i</tt> such that
396      * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
397      * or -1 if there is no such index.
398      *
399      * @param o element to search for.
400      * @return 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      */
403     public int indexOf(Object o) {
404         int ndx = 0;
405
406         // perform the null check outside of the loop to save checking every
407 // single time through the loop.
408 if (null == o) {
409             for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) {
410                 if (null == elt.value()) {
411                     return ndx;
412                 }
413                 ndx++;
414             }
415         } else {
416
417             for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) {
418                 if (o.equals(elt.value())) {
419                     return ndx;
420                 }
421                 ndx++;
422             }
423         }
424         return -1;
425     }
426
427     /**
428      * Returns <tt>true</tt> if this list contains no elements.
429      * @return <tt>true</tt> if this list contains no elements.
430      */
431     public boolean isEmpty() {
432         return(0 == _size);
433     }
434
435     /**
436      * Returns a fail-fast iterator.
437      * @see List#iterator
438      */
439     public Iterator iterator() {
440         return listIterator(0);
441     }
442
443     /**
444      * Returns the index in this list of the last occurrence of the specified
445      * element, or -1 if this list does not contain this element.
446      * More formally, returns the highest index <tt>i</tt> such that
447      * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>,
448      * or -1 if there is no such index.
449      *
450      * @param o element to search for.
451      * @return 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      */
454     public int lastIndexOf(Object o) {
455         int ndx = _size-1;
456
457         // perform the null check outside of the loop to save checking every
458 // single time through the loop.
459 if (null == o) {
460             for(Listable elt = _head.prev(), past = null; null != elt && past != _head.next(); elt = (past = elt).prev()) {
461                 if (null == elt.value()) {
462                     return ndx;
463                 }
464                 ndx--;
465             }
466         } else {
467             for(Listable elt = _head.prev(), past = null; null != elt && past != _head.next(); elt = (past = elt).prev()) {
468                 if (o.equals(elt.value())) {
469                     return ndx;
470                 }
471                 ndx--;
472             }
473         }
474         return -1;
475     }
476
477     /**
478      * Returns a fail-fast ListIterator.
479      * @see List#listIterator
480      */
481     public ListIterator listIterator() {
482         return listIterator(0);
483     }
484
485     /**
486      * Returns a fail-fast ListIterator.
487      * @see List#listIterator(int)
488      */
489     public ListIterator listIterator(int index) {
490         if(index<0 || index > _size) {
491             throw new IndexOutOfBoundsException (index + " < 0 or > " + _size);
492         }
493         return new ListIter(index);
494     }
495
496     /**
497      * Removes the first occurrence in this list of the specified element.
498      * If this list does not contain the element, it is
499      * unchanged. More formally, removes the element with the lowest index i
500      * such that <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt> (if
501      * such an element exists).
502      *
503      * @param o element to be removed from this list, if present.
504      * @return <tt>true</tt> if this list contained the specified element.
505      */
506     public boolean remove(Object o) {
507         for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) {
508             if(null == o && null == elt.value()) {
509                 removeListable(elt);
510                 return true;
511             } else if(o != null && o.equals(elt.value())) {
512                 removeListable(elt);
513                 return true;
514             }
515         }
516         return false;
517     }
518
519     /**
520      * Removes the element at the specified position in this list (optional
521      * operation). Shifts any subsequent elements to the left (subtracts one
522      * from their indices). Returns the element that was removed from the
523      * list.
524      *
525      * @param index the index of the element to removed.
526      * @return the element previously at the specified position.
527      *
528      * @throws IndexOutOfBoundsException if the index is out of range (index
529      * &lt; 0 || index &gt;= size()).
530      */
531     public Object remove(int index) {
532         Listable elt = getListableAt(index);
533         Object ret = elt.value();
534         removeListable(elt);
535         return ret;
536     }
537
538     /**
539      * Removes from this list all the elements that are contained in the
540      * specified collection.
541      *
542      * @param c collection that defines which elements will be removed from
543      * this list.
544      * @return <tt>true</tt> if this list changed as a result of the call.
545      */
546     public boolean removeAll(Collection c) {
547         if(0 == c.size() || 0 == _size) {
548             return false;
549         } else {
550             boolean changed = false;
551             Iterator it = iterator();
552             while(it.hasNext()) {
553                 if(c.contains(it.next())) {
554                     it.remove();
555                     changed = true;
556                 }
557             }
558             return changed;
559         }
560     }
561
562     /**
563      * Removes the first element of this list, if any.
564      */
565     public Object removeFirst() {
566         if(_head.next() != null) {
567             Object val = _head.next().value();
568             removeListable(_head.next());
569             return val;
570         } else {
571             throw new NoSuchElementException ();
572         }
573     }
574
575     /**
576      * Removes the last element of this list, if any.
577      */
578     public Object removeLast() {
579         if(_head.prev() != null) {
580             Object val = _head.prev().value();
581             removeListable(_head.prev());
582             return val;
583         } else {
584             throw new NoSuchElementException ();
585         }
586     }
587
588     /**
589      * Retains only the elements in this list that are contained in the
590      * specified collection. In other words, removes
591      * from this list all the elements that are not contained in the specified
592      * collection.
593      *
594      * @param c collection that defines which elements this set will retain.
595      *
596      * @return <tt>true</tt> if this list changed as a result of the call.
597      */
598     public boolean retainAll(Collection c) {
599         boolean changed = false;
600         Iterator it = iterator();
601         while(it.hasNext()) {
602             if(!c.contains(it.next())) {
603                 it.remove();
604                 changed = true;
605             }
606         }
607         return changed;
608     }
609
610     /**
611      * Replaces the element at the specified position in this list with the
612      * specified element.
613      *
614      * @param index index of element to replace.
615      * @param element element to be stored at the specified position.
616      * @return the element previously at the specified position.
617      *
618      * @throws ClassCastException if the class of the specified element
619      * prevents it from being added to this list.
620      * @throws IllegalArgumentException if some aspect of the specified
621      * element prevents it from being added to this list.
622      * @throws IndexOutOfBoundsException if the index is out of range
623      * (index &lt; 0 || index &gt;= size()).
624      */
625     public Object set(int index, Object element) {
626         Listable elt = getListableAt(index);
627         Object val = elt.setValue(element);
628         broadcastListableChanged(elt);
629         return val;
630     }
631
632     /**
633      * Returns the number of elements in this list.
634      * @return the number of elements in this list.
635      */
636     public int size() {
637         return _size;
638     }
639
640     /**
641      * Returns an array containing all of the elements in this list in proper
642      * sequence. Obeys the general contract of the {@link Collection#toArray} method.
643      *
644      * @return an array containing all of the elements in this list in proper
645      * sequence.
646      */
647     public Object [] toArray() {
648         Object [] array = new Object [_size];
649         int i = 0;
650         for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) {
651             array[i++] = elt.value();
652         }
653         return array;
654     }
655
656     /**
657      * Returns an array containing all of the elements in this list in proper
658      * sequence; the runtime type of the returned array is that of the
659      * specified array. Obeys the general contract of the
660      * {@link Collection#toArray} method.
661      *
662      * @param a the array into which the elements of this list are to
663      * be stored, if it is big enough; otherwise, a new array of the
664      * same runtime type is allocated for this purpose.
665      * @return an array containing the elements of this list.
666      * @exception ArrayStoreException
667      * if the runtime type of the specified array
668      * is not a supertype of the runtime type of every element in
669      * this list.
670      */
671     public Object [] toArray(Object a[]) {
672         if(a.length < _size) {
673             a = (Object [])Array.newInstance(a.getClass().getComponentType(), _size);
674         }
675         int i = 0;
676         for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) {
677             a[i++] = elt.value();
678         }
679         if(a.length > _size) {
680             a[_size] = null; // should we null out the rest of the array also? java.util.LinkedList doesn't
681 }
682         return a;
683     }
684
685     /**
686      * Returns a {@link String} representation of this list, suitable for debugging.
687      * @return a {@link String} representation of this list, suitable for debugging.
688      */
689     public String toString() {
690         StringBuffer buf = new StringBuffer ();
691         buf.append("[");
692         for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) {
693             if(_head.next() != elt) {
694                 buf.append(", ");
695             }
696             buf.append(elt.value());
697         }
698         buf.append("]");
699         return buf.toString();
700     }
701
702     /**
703      * Returns a fail-fast sublist.
704      * @see List#subList(int,int)
705      */
706     public List subList(int i, int j) {
707         if(i < 0 || j > _size || i > j) {
708             throw new IndexOutOfBoundsException ();
709         } else if(i == 0 && j == _size) {
710             return this;
711         } else {
712             return new CursorableSubList(this,i,j);
713         }
714     }
715
716     //--- protected methods ------------------------------------------
717
718     /**
719      * Inserts a new <i>value</i> into my
720      * list, after the specified <i>before</i> element, and before the
721      * specified <i>after</i> element
722      *
723      * @return the newly created
724      * {@link org.apache.commons.collections.CursorableLinkedList.Listable}
725      */
726     protected Listable insertListable(Listable before, Listable after, Object value) {
727         _modCount++;
728         _size++;
729         Listable elt = new Listable(before,after,value);
730         if(null != before) {
731             before.setNext(elt);
732         } else {
733             _head.setNext(elt);
734         }
735
736         if(null != after) {
737             after.setPrev(elt);
738         } else {
739             _head.setPrev(elt);
740         }
741         broadcastListableInserted(elt);
742         return elt;
743     }
744
745     /**
746      * Removes the given
747      * {@link org.apache.commons.collections.CursorableLinkedList.Listable}
748      * from my list.
749      */
750     protected void removeListable(Listable elt) {
751         _modCount++;
752         _size--;
753         if(_head.next() == elt) {
754             _head.setNext(elt.next());
755         }
756         if(null != elt.next()) {
757             elt.next().setPrev(elt.prev());
758         }
759         if(_head.prev() == elt) {
760             _head.setPrev(elt.prev());
761         }
762         if(null != elt.prev()) {
763             elt.prev().setNext(elt.next());
764         }
765         broadcastListableRemoved(elt);
766     }
767
768     /**
769      * Returns the
770      * {@link org.apache.commons.collections.CursorableLinkedList.Listable}
771      * at the specified index.
772      *
773      * @throws IndexOutOfBoundsException if index is less than zero or
774      * greater than or equal to the size of this list.
775      */
776     protected Listable getListableAt(int index) {
777         if(index < 0 || index >= _size) {
778             throw new IndexOutOfBoundsException (String.valueOf(index) + " < 0 or " + String.valueOf(index) + " >= " + _size);
779         }
780         if(index <=_size/2) {
781             Listable elt = _head.next();
782             for(int i = 0; i < index; i++) {
783                 elt = elt.next();
784             }
785             return elt;
786         } else {
787             Listable elt = _head.prev();
788             for(int i = (_size-1); i > index; i--) {
789                 elt = elt.prev();
790             }
791             return elt;
792         }
793     }
794
795     /**
796      * Registers a {@link CursorableLinkedList.Cursor} to be notified
797      * of changes to this list.
798      */
799     protected void registerCursor(Cursor cur) {
800         // We take this opportunity to clean the _cursors list
801 // of WeakReference objects to garbage-collected cursors.
802 for (Iterator it = _cursors.iterator(); it.hasNext(); ) {
803             WeakReference ref = (WeakReference ) it.next();
804             if (ref.get() == null) {
805                 it.remove();
806             }
807         }
808         
809         _cursors.add( new WeakReference (cur) );
810     }
811
812     /**
813      * Removes a {@link CursorableLinkedList.Cursor} from
814      * the set of cursors to be notified of changes to this list.
815      */
816     protected void unregisterCursor(Cursor cur) {
817         for (Iterator it = _cursors.iterator(); it.hasNext(); ) {
818             WeakReference ref = (WeakReference ) it.next();
819             Cursor cursor = (Cursor) ref.get();
820             if (cursor == null) {
821                 // some other unrelated cursor object has been
822 // garbage-collected; let's take the opportunity to
823 // clean up the cursors list anyway..
824 it.remove();
825                 
826             } else if (cursor == cur) {
827                 ref.clear();
828                 it.remove();
829                 break;
830             }
831         }
832     }
833
834     /**
835      * Informs all of my registered cursors that they are now
836      * invalid.
837      */
838     protected void invalidateCursors() {
839         Iterator it = _cursors.iterator();
840         while (it.hasNext()) {
841             WeakReference ref = (WeakReference ) it.next();
842             Cursor cursor = (Cursor) ref.get();
843             if (cursor != null) {
844                 // cursor is null if object has been garbage-collected
845 cursor.invalidate();
846                 ref.clear();
847             }
848             it.remove();
849         }
850     }
851
852     /**
853      * Informs all of my registered cursors that the specified
854      * element was changed.
855      * @see #set(int,java.lang.Object)
856      */
857     protected void broadcastListableChanged(Listable elt) {
858         Iterator it = _cursors.iterator();
859         while (it.hasNext()) {
860             WeakReference ref = (WeakReference ) it.next();
861             Cursor cursor = (Cursor) ref.get();
862             if (cursor == null) {
863                 it.remove(); // clean up list
864 } else {
865                 cursor.listableChanged(elt);
866             }
867         }
868     }
869
870     /**
871      * Informs all of my registered cursors that the specified
872      * element was just removed from my list.
873      */
874     protected void broadcastListableRemoved(Listable elt) {
875         Iterator it = _cursors.iterator();
876         while (it.hasNext()) {
877             WeakReference ref = (WeakReference ) it.next();
878             Cursor cursor = (Cursor) ref.get();
879             if (cursor == null) {
880                 it.remove(); // clean up list
881 } else {
882                 cursor.listableRemoved(elt);
883             }
884         }
885     }
886
887     /**
888      * Informs all of my registered cursors that the specified
889      * element was just added to my list.
890      */
891     protected void broadcastListableInserted(Listable elt) {
892       &