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