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         Iterator it = _cursors.iterator();
893         while (it.hasNext()) {
894             WeakReference ref = (WeakReference ) it.next();
895             Cursor cursor = (Cursor) ref.get();
896             if (cursor == null) {
897                 it.remove(); // clean up list
898 } else {
899                 cursor.listableInserted(elt);
900             }
901         }
902     }
903
904     private void writeObject(ObjectOutputStream out) throws IOException {
905         out.defaultWriteObject();
906         out.writeInt(_size);
907         Listable cur = _head.next();
908         while (cur != null) {
909             out.writeObject(cur.value());
910             cur = cur.next();
911         }
912     }
913
914     private void readObject(ObjectInputStream in) throws IOException , ClassNotFoundException {
915         in.defaultReadObject();
916         _size = 0;
917         _modCount = 0;
918         _cursors = new ArrayList ();
919         _head = new Listable(null,null,null);
920         int size = in.readInt();
921         for (int i=0;i<size;i++) {
922             this.add(in.readObject());
923         }
924     }
925
926     //--- protected attributes ---------------------------------------
927
928     /** The number of elements in me. */
929     protected transient int _size = 0;
930
931     /**
932      * A sentry node.
933      * <p>
934      * <tt>_head.next()</tt> points to the first element in the list,
935      * <tt>_head.prev()</tt> to the last. Note that it is possible for
936      * <tt>_head.next().prev()</tt> and <tt>_head.prev().next()</tt> to be
937      * non-null, as when I am a sublist for some larger list.
938      * Use <tt>== _head.next()</tt> and <tt>== _head.prev()</tt> to determine
939      * if a given
940      * {@link org.apache.commons.collections.CursorableLinkedList.Listable}
941      * is the first or last element in the list.
942      */
943     protected transient Listable _head = new Listable(null,null,null);
944
945     /** Tracks the number of structural modifications to me. */
946     protected transient int _modCount = 0;
947
948     /**
949      * A list of the currently {@link CursorableLinkedList.Cursor}s currently
950      * open in this list.
951      */
952     protected transient List _cursors = new ArrayList ();
953
954     //--- inner classes ----------------------------------------------
955
956     static class Listable implements Serializable {
957         private Listable _prev = null;
958         private Listable _next = null;
959         private Object _val = null;
960
961         Listable(Listable prev, Listable next, Object val) {
962             _prev = prev;
963             _next = next;
964             _val = val;
965         }
966
967         Listable next() {
968             return _next;
969         }
970
971         Listable prev() {
972             return _prev;
973         }
974
975         Object value() {
976             return _val;
977         }
978
979         void setNext(Listable next) {
980             _next = next;
981         }
982
983         void setPrev(Listable prev) {
984             _prev = prev;
985         }
986
987         Object setValue(Object val) {
988             Object temp = _val;
989             _val = val;
990             return temp;
991         }
992     }
993
994     class ListIter implements ListIterator {
995         Listable _cur = null;
996         Listable _lastReturned = null;
997         int _expectedModCount = _modCount;
998         int _nextIndex = 0;
999
1000        ListIter(int index) {
1001            if(index == 0) {
1002                _cur = new Listable(null,_head.next(),null);
1003                _nextIndex = 0;
1004            } else if(index == _size) {
1005                _cur = new Listable(_head.prev(),null,null);
1006                _nextIndex = _size;
1007            } else {
1008                Listable temp = getListableAt(index);
1009                _cur = new Listable(temp.prev(),temp,null);
1010                _nextIndex = index;
1011            }
1012        }
1013
1014        public Object previous() {
1015            checkForComod();
1016            if(!hasPrevious()) {
1017                throw new NoSuchElementException ();
1018            } else {
1019                Object ret = _cur.prev().value();
1020                _lastReturned = _cur.prev();
1021                _cur.setNext(_cur.prev());
1022                _cur.setPrev(_cur.prev().prev());
1023                _nextIndex--;
1024                return ret;
1025            }
1026        }
1027
1028        public boolean hasNext() {
1029            checkForComod();
1030            return(null != _cur.next() && _cur.prev() != _head.prev());
1031        }
1032
1033        public Object next() {
1034            checkForComod();
1035            if(!hasNext()) {
1036                throw new NoSuchElementException ();
1037            } else {
1038                Object ret = _cur.next().value();
1039                _lastReturned = _cur.next();
1040                _cur.setPrev(_cur.next());
1041                _cur.setNext(_cur.next().next());
1042                _nextIndex++;
1043                return ret;
1044            }
1045        }
1046
1047        public int previousIndex() {
1048            checkForComod();
1049            if(!hasPrevious()) {
1050                return -1;
1051            }
1052            return _nextIndex-1;
1053        }
1054
1055        public boolean hasPrevious() {
1056            checkForComod();
1057            return(null != _cur.prev() && _cur.next() != _head.next());
1058        }
1059
1060        public void set(Object o) {
1061            checkForComod();
1062            try {
1063                _lastReturned.setValue(o);
1064            } catch(NullPointerException e) {
1065                throw new IllegalStateException ();
1066            }
1067        }
1068
1069        public int nextIndex() {
1070            checkForComod();
1071            if(!hasNext()) {
1072                return size();
1073            }
1074            return _nextIndex;
1075        }
1076
1077        public void remove() {
1078            checkForComod();
1079            if(null == _lastReturned) {
1080                throw new IllegalStateException ();
1081            } else {
1082                _cur.setNext(_lastReturned == _head.prev() ? null : _lastReturned.next());
1083                _cur.setPrev(_lastReturned == _head.next() ? null : _lastReturned.prev());
1084                removeListable(_lastReturned);
1085                _lastReturned = null;
1086                _nextIndex--;
1087                _expectedModCount++;
1088            }
1089        }
1090
1091        public void add(Object o) {
1092            checkForComod();
1093            _cur.setPrev(insertListable(_cur.prev(),_cur.next(),o));
1094            _lastReturned = null;
1095            _nextIndex++;
1096            _expectedModCount++;
1097        }
1098
1099        protected void checkForComod() {
1100            if(_expectedModCount != _modCount) {
1101                throw new ConcurrentModificationException ();
1102            }
1103        }
1104    }
1105
1106    public class Cursor extends ListIter implements ListIterator {
1107        boolean _valid = false;
1108
1109        Cursor(int index) {
1110            super(index);
1111            _valid = true;
1112            registerCursor(this);
1113        }
1114
1115        public int previousIndex() {
1116            throw new UnsupportedOperationException ();
1117        }
1118
1119        public int nextIndex() {
1120            throw new UnsupportedOperationException ();
1121        }
1122
1123        public void add(Object o) {
1124            checkForComod();
1125            Listable elt = insertListable(_cur.prev(),_cur.next(),o);
1126            _cur.setPrev(elt);
1127            _cur.setNext(elt.next());
1128            _lastReturned = null;
1129            _nextIndex++;
1130            _expectedModCount++;
1131        }
1132
1133        protected void listableRemoved(Listable elt) {
1134            if(null == _head.prev()) {
1135                _cur.setNext(null);
1136            } else if(_cur.next() == elt) {
1137                _cur.setNext(elt.next());
1138            }
1139            if(null == _head.next()) {
1140                _cur.setPrev(null);
1141            } else if(_cur.prev() == elt) {
1142                _cur.setPrev(elt.prev());
1143            }
1144            if(_lastReturned == elt) {
1145                _lastReturned = null;
1146            }
1147        }
1148
1149        protected void listableInserted(Listable elt) {
1150            if(null == _cur.next() && null == _cur.prev()) {
1151                _cur.setNext(elt);
1152            } else if(_cur.prev() == elt.prev()) {
1153                _cur.setNext(elt);
1154            }
1155            if(_cur.next() == elt.next()) {
1156                _cur.setPrev(elt);
1157            }
1158            if(_lastReturned == elt) {
1159                _lastReturned = null;
1160            }
1161        }
1162
1163        protected void listableChanged(Listable elt) {
1164            if(_lastReturned == elt) {
1165                _lastReturned = null;
1166            }
1167        }
1168
1169        protected void checkForComod() {
1170            if(!_valid) {
1171                throw new ConcurrentModificationException ();
1172            }
1173        }
1174
1175        protected void invalidate() {
1176            _valid = false;
1177        }
1178
1179        /**
1180         * Mark this cursor as no longer being needed. Any resources
1181         * associated with this cursor are immediately released.
1182         * In previous versions of this class, it was mandatory to close
1183         * all cursor objects to avoid memory leaks. It is <i>no longer</i>
1184         * necessary to call this close method; an instance of this class
1185         * can now be treated exactly like a normal iterator.
1186         */
1187        public void close() {
1188            if(_valid) {
1189                _valid = false;
1190                unregisterCursor(this);
1191            }
1192        }
1193    }
1194
1195}
1196
1197class CursorableSubList extends CursorableLinkedList implements List {
1198
1199    //--- constructors -----------------------------------------------
1200
1201    CursorableSubList(CursorableLinkedList list, int from, int to) {
1202        if(0 > from || list.size() < to) {
1203            throw new IndexOutOfBoundsException ();
1204        } else if(from > to) {
1205            throw new IllegalArgumentException ();
1206        }
1207        _list = list;
1208        if(from < list.size()) {
1209            _head.setNext(_list.getListableAt(from));
1210            _pre = (null == _head.next()) ? null : _head.next().prev();
1211        } else {
1212            _pre = _list.getListableAt(from-1);
1213        }
1214        if(from == to) {
1215            _head.setNext(null);
1216            _head.setPrev(null);
1217            if(to < list.size()) {
1218                _post = _list.getListableAt(to);
1219            } else {
1220                _post = null;
1221            }
1222        } else {
1223            _head.setPrev(_list.getListableAt(to-1));
1224            _post = _head.prev().next();
1225        }
1226        _size = to - from;
1227        _modCount = _list._modCount;
1228    }
1229
1230    //--- public methods ------------------------------------------
1231
1232    public void clear() {
1233        checkForComod();
1234        Iterator it = iterator();
1235        while(it.hasNext()) {
1236            it.next();
1237            it.remove();
1238        }
1239    }
1240
1241    public Iterator iterator() {
1242        checkForComod();
1243        return super.iterator();
1244    }
1245
1246    public int size() {
1247        checkForComod();
1248        return super.size();
1249    }
1250
1251    public boolean isEmpty() {
1252        checkForComod();
1253        return super.isEmpty();
1254    }
1255
1256    public Object [] toArray() {
1257        checkForComod();
1258        return super.toArray();
1259    }
1260
1261    public Object [] toArray(Object a[]) {
1262        checkForComod();
1263        return super.toArray(a);
1264    }
1265
1266    public boolean contains(Object o) {
1267        checkForComod();
1268        return super.contains(o);
1269    }
1270
1271    public boolean remove(Object o) {
1272        checkForComod();
1273        return super.remove(o);
1274    }
1275
1276    public Object removeFirst() {
1277        checkForComod();
1278        return super.removeFirst();
1279    }
1280
1281    public Object removeLast() {
1282        checkForComod();
1283        return super.removeLast();
1284    }
1285
1286    public boolean addAll(Collection c) {
1287        checkForComod();
1288        return super.addAll(c);
1289    }
1290
1291    public boolean add(Object o) {
1292        checkForComod();
1293        return super.add(o);
1294    }
1295
1296    public boolean addFirst(Object o) {
1297        checkForComod();
1298        return super.addFirst(o);
1299    }
1300
1301    public boolean addLast(Object o) {
1302        checkForComod();
1303        return super.addLast(o);
1304    }
1305
1306    public boolean removeAll(Collection c) {
1307        checkForComod();
1308        return super.removeAll(c);
1309    }
1310
1311    public boolean containsAll(Collection c) {
1312        checkForComod();
1313        return super.containsAll(c);
1314    }
1315
1316    public boolean addAll(int index, Collection c) {
1317        checkForComod();
1318        return super.addAll(index,c);
1319    }
1320
1321    public int hashCode() {
1322        checkForComod();
1323        return super.hashCode();
1324    }
1325
1326    public boolean retainAll(Collection c) {
1327        checkForComod();
1328        return super.retainAll(c);
1329    }
1330
1331    public Object set(int index, Object element) {
1332        checkForComod();
1333        return super.set(index,element);
1334    }
1335
1336    public boolean equals(Object o) {
1337        checkForComod();
1338        return super.equals(o);
1339    }
1340
1341    public Object get(int index) {
1342        checkForComod();
1343        return super.get(index);
1344    }
1345
1346    public Object getFirst() {
1347        checkForComod();
1348        return super.getFirst();
1349    }
1350
1351    public Object getLast() {
1352        checkForComod();
1353        return super.getLast();
1354    }
1355
1356    public void add(int index, Object element) {
1357        checkForComod();
1358        super.add(index,element);
1359    }
1360
1361    public ListIterator listIterator(int index) {
1362        checkForComod();
1363        return super.listIterator(index);
1364    }
1365
1366    public Object remove(int index) {
1367        checkForComod();
1368        return super.remove(index);
1369    }
1370
1371    public int indexOf(Object o) {
1372        checkForComod();
1373        return super.indexOf(o);
1374    }
1375
1376    public int lastIndexOf(Object o) {
1377        checkForComod();
1378        return super.lastIndexOf(o);
1379    }
1380
1381    public ListIterator listIterator() {
1382        checkForComod();
1383        return super.listIterator();
1384    }
1385
1386    public List subList(int fromIndex, int toIndex) {
1387        checkForComod();
1388        return super.subList(fromIndex,toIndex);
1389    }
1390
1391    //--- protected methods ------------------------------------------
1392
1393    /**
1394     * Inserts a new <i>value</i> into my
1395     * list, after the specified <i>before</i> element, and before the
1396     * specified <i>after</i> element
1397     *
1398     * @return the newly created {@link CursorableLinkedList.Listable}
1399     */
1400    protected Listable insertListable(Listable before, Listable after, Object value) {
1401        _modCount++;
1402        _size++;
1403        Listable elt = _list.insertListable((null == before ? _pre : before), (null == after ? _post : after),value);
1404        if(null == _head.next()) {
1405            _head.setNext(elt);
1406            _head.setPrev(elt);
1407        }
1408        if(before == _head.prev()) {
1409            _head.setPrev(elt);
1410        }
1411        if(after == _head.next()) {
1412            _head.setNext(elt);
1413        }
1414        broadcastListableInserted(elt);
1415        return elt;
1416    }
1417
1418    /**
1419     * Removes the given {@link CursorableLinkedList.Listable} from my list.
1420     */
1421    protected void removeListable(Listable elt) {
1422        _modCount++;
1423        _size--;
1424        if(_head.next() == elt && _head.prev() == elt) {
1425            _head.setNext(null);
1426            _head.setPrev(null);
1427        }
1428        if(_head.next() == elt) {
1429            _head.setNext(elt.next());
1430        }
1431        if(_head.prev() == elt) {
1432            _head.setPrev(elt.prev());
1433        }
1434        _list.removeListable(elt);
1435        broadcastListableRemoved(elt);
1436    }
1437
1438    /**
1439     * Test to see if my underlying list has been modified
1440     * by some other process. If it has, throws a
1441     * {@link ConcurrentModificationException}, otherwise
1442     * quietly returns.
1443     *
1444     * @throws ConcurrentModificationException
1445     */
1446    protected void checkForComod() throws ConcurrentModificationException {
1447        if(_modCount != _list._modCount) {
1448            throw new ConcurrentModificationException ();
1449        }
1450    }
1451
1452    //--- protected attributes ---------------------------------------
1453
1454    /** My underlying list */
1455    protected CursorableLinkedList _list = null;
1456
1457    /** The element in my underlying list preceding the first element in my list. */
1458    protected Listable _pre = null;
1459
1460    /** The element in my underlying list following the last element in my list. */
1461    protected Listable _post = null;
1462
1463}
1464

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags