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