Classes in this File | Line Coverage | Branch Coverage | Complexity | ||||
CursorableLinkedList |
|
| 2.75;2.75 | ||||
CursorableLinkedList$Cursor |
|
| 2.75;2.75 | ||||
CursorableLinkedList$ListIter |
|
| 2.75;2.75 | ||||
CursorableLinkedList$Listable |
|
| 2.75;2.75 | ||||
CursorableSubList |
|
| 2.75;2.75 |
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 | 0 | 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 | 0 | insertListable(_head.prev(),null,o); |
77 | 0 | 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 | 0 | if(index == _size) { |
97 | 0 | add(element); |
98 | } else { | |
99 | 0 | if(index < 0 || index > _size) { |
100 | 0 | throw new IndexOutOfBoundsException(String.valueOf(index) + " < 0 or " + String.valueOf(index) + " > " + _size); |
101 | } | |
102 | 0 | Listable succ = (isEmpty() ? null : getListableAt(index)); |
103 | 0 | Listable pred = (null == succ ? null : succ.prev()); |
104 | 0 | insertListable(pred,succ,element); |
105 | } | |
106 | 0 | } |
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 | 0 | if(c.isEmpty()) { |
127 | 0 | return false; |
128 | } | |
129 | 0 | Iterator it = c.iterator(); |
130 | 0 | while(it.hasNext()) { |
131 | 0 | insertListable(_head.prev(),null,it.next()); |
132 | } | |
133 | 0 | 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 | 0 | if(c.isEmpty()) { |
163 | 0 | return false; |
164 | 0 | } else if(_size == index || _size == 0) { |
165 | 0 | return addAll(c); |
166 | } else { | |
167 | 0 | Listable succ = getListableAt(index); |
168 | 0 | Listable pred = (null == succ) ? null : succ.prev(); |
169 | 0 | Iterator it = c.iterator(); |
170 | 0 | while(it.hasNext()) { |
171 | 0 | pred = insertListable(pred,succ,it.next()); |
172 | } | |
173 | 0 | 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 | 0 | insertListable(null,_head.next(),o); |
186 | 0 | 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 | 0 | insertListable(_head.prev(),null,o); |
198 | 0 | 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 | 0 | Iterator it = iterator(); |
216 | 0 | while(it.hasNext()) { |
217 | 0 | it.next(); |
218 | 0 | it.remove(); |
219 | } | |
220 | 0 | } |
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 | 0 | for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) { |
233 | 0 | if((null == o && null == elt.value()) || |
234 | (o != null && o.equals(elt.value()))) { | |
235 | 0 | return true; |
236 | } | |
237 | } | |
238 | 0 | 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 | 0 | Iterator it = c.iterator(); |
251 | 0 | while(it.hasNext()) { |
252 | 0 | if(!this.contains(it.next())) { |
253 | 0 | return false; |
254 | } | |
255 | } | |
256 | 0 | 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 | 0 | 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 | 0 | 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 | 0 | if(o == this) { |
324 | 0 | return true; |
325 | 0 | } else if(!(o instanceof List)) { |
326 | 0 | return false; |
327 | } | |
328 | 0 | Iterator it = ((List)o).listIterator(); |
329 | 0 | for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) { |
330 | 0 | if(!it.hasNext() || (null == elt.value() ? null != it.next() : !(elt.value().equals(it.next()))) ) { |
331 | 0 | return false; |
332 | } | |
333 | } | |
334 | 0 | 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 | 0 | 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 | 0 | return _head.next().value(); |
356 | 0 | } catch(NullPointerException e) { |
357 | 0 | 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 | 0 | return _head.prev().value(); |
367 | 0 | } catch(NullPointerException e) { |
368 | 0 | 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 | 0 | int hash = 1; |
395 | 0 | for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) { |
396 | 0 | hash = 31*hash + (null == elt.value() ? 0 : elt.value().hashCode()); |
397 | } | |
398 | 0 | 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 | 0 | int ndx = 0; |
414 | ||
415 | // perform the null check outside of the loop to save checking every | |
416 | // single time through the loop. | |
417 | 0 | if (null == o) { |
418 | 0 | for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) { |
419 | 0 | if (null == elt.value()) { |
420 | 0 | return ndx; |
421 | } | |
422 | 0 | ndx++; |
423 | } | |
424 | } else { | |
425 | ||
426 | 0 | for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) { |
427 | 0 | if (o.equals(elt.value())) { |
428 | 0 | return ndx; |
429 | } | |
430 | 0 | ndx++; |
431 | } | |
432 | } | |
433 | 0 | 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 | 0 | return(0 == _size); |
442 | } | |
443 | ||
444 | /** | |
445 | * Returns a fail-fast iterator. | |
446 | * @see List#iterator | |
447 | */ | |
448 | public Iterator iterator() { | |
449 | 0 | 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 | 0 | 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 | 0 | if (null == o) { |
469 | 0 | for(Listable elt = _head.prev(), past = null; null != elt && past != _head.next(); elt = (past = elt).prev()) { |
470 | 0 | if (null == elt.value()) { |
471 | 0 | return ndx; |
472 | } | |
473 | 0 | ndx--; |
474 | } | |
475 | } else { | |
476 | 0 | for(Listable elt = _head.prev(), past = null; null != elt && past != _head.next(); elt = (past = elt).prev()) { |
477 | 0 | if (o.equals(elt.value())) { |
478 | 0 | return ndx; |
479 | } | |
480 | 0 | ndx--; |
481 | } | |
482 | } | |
483 | 0 | return -1; |
484 | } | |
485 | ||
486 | /** | |
487 | * Returns a fail-fast ListIterator. | |
488 | * @see List#listIterator() | |
489 | */ | |
490 | public ListIterator listIterator() { | |
491 | 0 | 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 | 0 | if(index<0 || index > _size) { |
500 | 0 | throw new IndexOutOfBoundsException(index + " < 0 or > " + _size); |
501 | } | |
502 | 0 | 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 | 0 | for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) { |
517 | 0 | if(null == o && null == elt.value()) { |
518 | 0 | removeListable(elt); |
519 | 0 | return true; |
520 | 0 | } else if(o != null && o.equals(elt.value())) { |
521 | 0 | removeListable(elt); |
522 | 0 | return true; |
523 | } | |
524 | } | |
525 | 0 | 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 | 0 | Listable elt = getListableAt(index); |
542 | 0 | Object ret = elt.value(); |
543 | 0 | removeListable(elt); |
544 | 0 | 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 | 0 | if(0 == c.size() || 0 == _size) { |
557 | 0 | return false; |
558 | } else { | |
559 | 0 | boolean changed = false; |
560 | 0 | Iterator it = iterator(); |
561 | 0 | while(it.hasNext()) { |
562 | 0 | if(c.contains(it.next())) { |
563 | 0 | it.remove(); |
564 | 0 | changed = true; |
565 | } | |
566 | } | |
567 | 0 | return changed; |
568 | } | |
569 | } | |
570 | ||
571 | /** | |
572 | * Removes the first element of this list, if any. | |
573 | */ | |
574 | public Object removeFirst() { | |
575 | 0 | if(_head.next() != null) { |
576 | 0 | Object val = _head.next().value(); |
577 | 0 | removeListable(_head.next()); |
578 | 0 | return val; |
579 | } else { | |
580 | 0 | throw new NoSuchElementException(); |
581 | } | |
582 | } | |
583 | ||
584 | /** | |
585 | * Removes the last element of this list, if any. | |
586 | */ | |
587 | public Object removeLast() { | |
588 | 0 | if(_head.prev() != null) { |
589 | 0 | Object val = _head.prev().value(); |
590 | 0 | removeListable(_head.prev()); |
591 | 0 | return val; |
592 | } else { | |
593 | 0 | 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 | 0 | boolean changed = false; |
609 | 0 | Iterator it = iterator(); |
610 | 0 | while(it.hasNext()) { |
611 | 0 | if(!c.contains(it.next())) { |
612 | 0 | it.remove(); |
613 | 0 | changed = true; |
614 | } | |
615 | } | |
616 | 0 | 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 | 0 | Listable elt = getListableAt(index); |
636 | 0 | Object val = elt.setValue(element); |
637 | 0 | broadcastListableChanged(elt); |
638 | 0 | 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 | 0 | 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 | 0 | Object[] array = new Object[_size]; |
658 | 0 | int i = 0; |
659 | 0 | for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) { |
660 | 0 | array[i++] = elt.value(); |
661 | } | |
662 | 0 | 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 | 0 | if(a.length < _size) { |
682 | 0 | a = (Object[])Array.newInstance(a.getClass().getComponentType(), _size); |
683 | } | |
684 | 0 | int i = 0; |
685 | 0 | for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) { |
686 | 0 | a[i++] = elt.value(); |
687 | } | |
688 | 0 | if(a.length > _size) { |
689 | 0 | a[_size] = null; // should we null out the rest of the array also? java.util.LinkedList doesn't |
690 | } | |
691 | 0 | 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 | 0 | StringBuffer buf = new StringBuffer(); |
700 | 0 | buf.append("["); |
701 | 0 | for(Listable elt = _head.next(), past = null; null != elt && past != _head.prev(); elt = (past = elt).next()) { |
702 | 0 | if(_head.next() != elt) { |
703 | 0 | buf.append(", "); |
704 | } | |
705 | 0 | buf.append(elt.value()); |
706 | } | |
707 | 0 | buf.append("]"); |
708 | 0 | 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 | 0 | if(i < 0 || j > _size || i > j) { |
717 | 0 | throw new IndexOutOfBoundsException(); |
718 | 0 | } else if(i == 0 && j == _size) { |
719 | 0 | return this; |
720 | } else { | |
721 | 0 | 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 | 0 | _modCount++; |
737 | 0 | _size++; |
738 | 0 | Listable elt = new Listable(before,after,value); |
739 | 0 | if(null != before) { |
740 | 0 | before.setNext(elt); |
741 | } else { | |
742 | 0 | _head.setNext(elt); |
743 | } | |
744 | ||
745 | 0 | if(null != after) { |
746 | 0 | after.setPrev(elt); |
747 | } else { | |
748 | 0 | _head.setPrev(elt); |
749 | } | |
750 | 0 | broadcastListableInserted(elt); |
751 | 0 | 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 | 0 | _modCount++; |
761 | 0 | _size--; |
762 | 0 | if(_head.next() == elt) { |
763 | 0 | _head.setNext(elt.next()); |
764 | } | |
765 | 0 | if(null != elt.next()) { |
766 | 0 | elt.next().setPrev(elt.prev()); |
767 | } | |
768 | 0 | if(_head.prev() == elt) { |
769 | 0 | _head.setPrev(elt.prev()); |
770 | } | |
771 | 0 | if(null != elt.prev()) { |
772 | 0 | elt.prev().setNext(elt.next()); |
773 | } | |
774 | 0 | broadcastListableRemoved(elt); |
775 | 0 | } |
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 | 0 | if(index < 0 || index >= _size) { |
787 | 0 | throw new IndexOutOfBoundsException(String.valueOf(index) + " < 0 or " + String.valueOf(index) + " >= " + _size); |
788 | } | |
789 | 0 | if(index <=_size/2) { |
790 | 0 | Listable elt = _head.next(); |
791 | 0 | for(int i = 0; i < index; i++) { |
792 | 0 | elt = elt.next(); |
793 | } | |
794 | 0 | return elt; |
795 | } else { | |
796 | 0 | Listable elt = _head.prev(); |
797 | 0 | for(int i = (_size-1); i > index; i--) { |
798 | 0 | elt = elt.prev(); |
799 | } | |
800 | 0 | 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 | 0 | for (Iterator it = _cursors.iterator(); it.hasNext(); ) { |
812 | 0 | WeakReference ref = (WeakReference) it.next(); |
813 | 0 | if (ref.get() == null) { |
814 | 0 | it.remove(); |
815 | } | |
816 | 0 | } |
817 | ||
818 | 0 | _cursors.add( new WeakReference(cur) ); |
819 | 0 | } |
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 | 0 | for (Iterator it = _cursors.iterator(); it.hasNext(); ) { |
827 | 0 | WeakReference ref = (WeakReference) it.next(); |
828 | 0 | Cursor cursor = (Cursor) ref.get(); |
829 | 0 | 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 | 0 | it.remove(); |
834 | ||
835 | 0 | } else if (cursor == cur) { |
836 | 0 | ref.clear(); |
837 | 0 | it.remove(); |
838 | 0 | break; |
839 | } | |
840 | 0 | } |
841 | 0 | } |
842 | ||
843 | /** | |
844 | * Informs all of my registered cursors that they are now | |
845 | * invalid. | |
846 | */ | |
847 | protected void invalidateCursors() { | |
848 | 0 | Iterator it = _cursors.iterator(); |
849 | 0 | while (it.hasNext()) { |
850 | 0 | WeakReference ref = (WeakReference) it.next(); |
851 | 0 | Cursor cursor = (Cursor) ref.get(); |
852 | 0 | if (cursor != null) { |
853 | // cursor is null if object has been garbage-collected | |
854 | 0 | cursor.invalidate(); |
855 | 0 | ref.clear(); |
856 | } | |
857 | 0 | it.remove(); |
858 | 0 | } |
859 | 0 | } |
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 | 0 | Iterator it = _cursors.iterator(); |
868 | 0 | while (it.hasNext()) { |
869 | 0 | WeakReference ref = (WeakReference) it.next(); |
870 | 0 | Cursor cursor = (Cursor) ref.get(); |
871 | 0 | if (cursor == null) { |
872 | 0 | it.remove(); // clean up list |
873 | } else { | |
874 | 0 | cursor.listableChanged(elt); |
875 | } | |
876 | 0 | } |
877 | 0 | } |
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 | 0 | Iterator it = _cursors.iterator(); |
885 | 0 | while (it.hasNext()) { |
886 | 0 | WeakReference ref = (WeakReference) it.next(); |
887 | 0 | Cursor cursor = (Cursor) ref.get(); |
888 | 0 | if (cursor == null) { |
889 | 0 | it.remove(); // clean up list |
890 | } else { | |
891 | 0 | cursor.listableRemoved(elt); |
892 | } | |
893 | 0 | } |
894 | 0 | } |
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 | 0 | Iterator it = _cursors.iterator(); |
902 | 0 | while (it.hasNext()) { |
903 | 0 | WeakReference ref = (WeakReference) it.next(); |
904 | 0 | Cursor cursor = (Cursor) ref.get(); |
905 | 0 | if (cursor == null) { |
906 | 0 | it.remove(); // clean up list |
907 | } else { | |
908 | 0 | cursor.listableInserted(elt); |
909 | } | |
910 | 0 | } |
911 | 0 | } |
912 | ||
913 | private void writeObject(ObjectOutputStream out) throws IOException { | |
914 | 0 | out.defaultWriteObject(); |
915 | 0 | out.writeInt(_size); |
916 | 0 | Listable cur = _head.next(); |
917 | 0 | while (cur != null) { |
918 | 0 | out.writeObject(cur.value()); |
919 | 0 | cur = cur.next(); |
920 | } | |
921 | 0 | } |
922 | ||
923 | private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException { | |
924 | 0 | in.defaultReadObject(); |
925 | 0 | _size = 0; |
926 | 0 | _modCount = 0; |
927 | 0 | _cursors = new ArrayList(); |
928 | 0 | _head = new Listable(null,null,null); |
929 | 0 | int size = in.readInt(); |
930 | 0 | for (int i=0;i<size;i++) { |
931 | 0 | this.add(in.readObject()); |
932 | } | |
933 | 0 | } |
934 | ||
935 | //--- protected attributes --------------------------------------- | |
936 | ||
937 | /** The number of elements in me. */ | |
938 | 0 | 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 | 0 | protected transient Listable _head = new Listable(null,null,null); |
953 | ||
954 | /** Tracks the number of structural modifications to me. */ | |
955 | 0 | 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 | 0 | protected transient List _cursors = new ArrayList(); |
962 | ||
963 | //--- inner classes ---------------------------------------------- | |
964 | ||
965 | static class Listable implements Serializable { | |
966 | 0 | private Listable _prev = null; |
967 | 0 | private Listable _next = null; |
968 | 0 | private Object _val = null; |
969 | ||
970 | 0 | Listable(Listable prev, Listable next, Object val) { |
971 | 0 | _prev = prev; |
972 | 0 | _next = next; |
973 | 0 | _val = val; |
974 | 0 | } |
975 | ||
976 | Listable next() { | |
977 | 0 | return _next; |
978 | } | |
979 | ||
980 | Listable prev() { | |
981 | 0 | return _prev; |
982 | } | |
983 | ||
984 | Object value() { | |
985 | 0 | return _val; |
986 | } | |
987 | ||
988 | void setNext(Listable next) { | |
989 | 0 | _next = next; |
990 | 0 | } |
991 | ||
992 | void setPrev(Listable prev) { | |
993 | 0 | _prev = prev; |
994 | 0 | } |
995 | ||
996 | Object setValue(Object val) { | |
997 | 0 | Object temp = _val; |
998 | 0 | _val = val; |
999 | 0 | return temp; |
1000 | } | |
1001 | } | |
1002 | ||
1003 | class ListIter implements ListIterator { | |
1004 | 0 | Listable _cur = null; |
1005 | 0 | Listable _lastReturned = null; |
1006 | 0 | int _expectedModCount = _modCount; |
1007 | 0 | int _nextIndex = 0; |
1008 | ||
1009 | 0 | ListIter(int index) { |
1010 | 0 | if(index == 0) { |
1011 | 0 | _cur = new Listable(null,_head.next(),null); |
1012 | 0 | _nextIndex = 0; |
1013 | 0 | } else if(index == _size) { |
1014 | 0 | _cur = new Listable(_head.prev(),null,null); |
1015 | 0 | _nextIndex = _size; |
1016 | } else { | |
1017 | 0 | Listable temp = getListableAt(index); |
1018 | 0 | _cur = new Listable(temp.prev(),temp,null); |
1019 | 0 | _nextIndex = index; |
1020 | } | |
1021 | 0 | } |
1022 | ||
1023 | public Object previous() { | |
1024 | 0 | checkForComod(); |
1025 | 0 | if(!hasPrevious()) { |
1026 | 0 | throw new NoSuchElementException(); |
1027 | } else { | |
1028 | 0 | Object ret = _cur.prev().value(); |
1029 | 0 | _lastReturned = _cur.prev(); |
1030 | 0 | _cur.setNext(_cur.prev()); |
1031 | 0 | _cur.setPrev(_cur.prev().prev()); |
1032 | 0 | _nextIndex--; |
1033 | 0 | return ret; |
1034 | } | |
1035 | } | |
1036 | ||
1037 | public boolean hasNext() { | |
1038 | 0 | checkForComod(); |
1039 | 0 | return(null != _cur.next() && _cur.prev() != _head.prev()); |
1040 | } | |
1041 | ||
1042 | public Object next() { | |
1043 | 0 | checkForComod(); |
1044 | 0 | if(!hasNext()) { |
1045 | 0 | throw new NoSuchElementException(); |
1046 | } else { | |
1047 | 0 | Object ret = _cur.next().value(); |
1048 | 0 | _lastReturned = _cur.next(); |
1049 | 0 | _cur.setPrev(_cur.next()); |
1050 | 0 | _cur.setNext(_cur.next().next()); |
1051 | 0 | _nextIndex++; |
1052 | 0 | return ret; |
1053 | } | |
1054 | } | |
1055 | ||
1056 | public int previousIndex() { | |
1057 | 0 | checkForComod(); |
1058 | 0 | if(!hasPrevious()) { |
1059 | 0 | return -1; |
1060 | } | |
1061 | 0 | return _nextIndex-1; |
1062 | } | |
1063 | ||
1064 | public boolean hasPrevious() { | |
1065 | 0 | checkForComod(); |
1066 | 0 | return(null != _cur.prev() && _cur.next() != _head.next()); |
1067 | } | |
1068 | ||
1069 | public void set(Object o) { | |
1070 | 0 | checkForComod(); |
1071 | try { | |
1072 | 0 | _lastReturned.setValue(o); |
1073 | 0 | } catch(NullPointerException e) { |
1074 | 0 | throw new IllegalStateException(); |
1075 | 0 | } |
1076 | 0 | } |
1077 | ||
1078 | public int nextIndex() { | |
1079 | 0 | checkForComod(); |
1080 | 0 | if(!hasNext()) { |
1081 | 0 | return size(); |
1082 | } | |
1083 | 0 | return _nextIndex; |
1084 | } | |
1085 | ||
1086 | public void remove() { | |
1087 | 0 | checkForComod(); |
1088 | 0 | if(null == _lastReturned) { |
1089 | 0 | throw new IllegalStateException(); |
1090 | } else { | |
1091 | 0 | _cur.setNext(_lastReturned == _head.prev() ? null : _lastReturned.next()); |
1092 | 0 | _cur.setPrev(_lastReturned == _head.next() ? null : _lastReturned.prev()); |
1093 | 0 | removeListable(_lastReturned); |
1094 | 0 | _lastReturned = null; |
1095 | 0 | _nextIndex--; |
1096 | 0 | _expectedModCount++; |
1097 | } | |
1098 | 0 | } |
1099 | ||
1100 | public void add(Object o) { | |
1101 | 0 | checkForComod(); |
1102 | 0 | _cur.setPrev(insertListable(_cur.prev(),_cur.next(),o)); |
1103 | 0 | _lastReturned = null; |
1104 | 0 | _nextIndex++; |
1105 | 0 | _expectedModCount++; |
1106 | 0 | } |
1107 | ||
1108 | protected void checkForComod() { | |
1109 | 0 | if(_expectedModCount != _modCount) { |
1110 | 0 | throw new ConcurrentModificationException(); |
1111 | } | |
1112 | 0 | } |
1113 | } | |
1114 | ||
1115 | 0 | public class Cursor extends ListIter implements ListIterator { |
1116 | 0 | boolean _valid = false; |
1117 | ||
1118 | 0 | Cursor(int index) { |
1119 | 0 | super(index); |
1120 | 0 | _valid = true; |
1121 | 0 | registerCursor(this); |
1122 | 0 | } |
1123 | ||
1124 | public int previousIndex() { | |
1125 | 0 | throw new UnsupportedOperationException(); |
1126 | } | |
1127 | ||
1128 | public int nextIndex() { | |
1129 | 0 | throw new UnsupportedOperationException(); |
1130 | } | |
1131 | ||
1132 | public void add(Object o) { | |
1133 | 0 | checkForComod(); |
1134 | 0 | Listable elt = insertListable(_cur.prev(),_cur.next(),o); |
1135 | 0 | _cur.setPrev(elt); |
1136 | 0 | _cur.setNext(elt.next()); |
1137 | 0 | _lastReturned = null; |
1138 | 0 | _nextIndex++; |
1139 | 0 | _expectedModCount++; |
1140 | 0 | } |
1141 | ||
1142 | protected void listableRemoved(Listable elt) { | |
1143 | 0 | if(null == _head.prev()) { |
1144 | 0 | _cur.setNext(null); |
1145 | 0 | } else if(_cur.next() == elt) { |
1146 | 0 | _cur.setNext(elt.next()); |
1147 | } | |
1148 | 0 | if(null == _head.next()) { |
1149 | 0 | _cur.setPrev(null); |
1150 | 0 | } else if(_cur.prev() == elt) { |
1151 | 0 | _cur.setPrev(elt.prev()); |
1152 | } | |
1153 | 0 | if(_lastReturned == elt) { |
1154 | 0 | _lastReturned = null; |
1155 | } | |
1156 | 0 | } |
1157 | ||
1158 | protected void listableInserted(Listable elt) { | |
1159 | 0 | if(null == _cur.next() && null == _cur.prev()) { |
1160 | 0 | _cur.setNext(elt); |
1161 | 0 | } else if(_cur.prev() == elt.prev()) { |
1162 | 0 | _cur.setNext(elt); |
1163 | } | |
1164 | 0 | if(_cur.next() == elt.next()) { |
1165 | 0 | _cur.setPrev(elt); |
1166 | } | |
1167 | 0 | if(_lastReturned == elt) { |
1168 | 0 | _lastReturned = null; |
1169 | } | |
1170 | 0 | } |
1171 | ||
1172 | protected void listableChanged(Listable elt) { | |
1173 | 0 | if(_lastReturned == elt) { |
1174 | 0 | _lastReturned = null; |
1175 | } | |
1176 | 0 | } |
1177 | ||
1178 | protected void checkForComod() { | |
1179 | 0 | if(!_valid) { |
1180 | 0 | throw new ConcurrentModificationException(); |
1181 | } | |
1182 | 0 | } |
1183 | ||
1184 | protected void invalidate() { | |
1185 | 0 | _valid = false; |
1186 | 0 | } |
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 | 0 | if(_valid) { |
1198 | 0 | _valid = false; |
1199 | 0 | unregisterCursor(this); |
1200 | } | |
1201 | 0 | } |
1202 | } | |
1203 | ||
1204 | } | |
1205 | ||
1206 | class CursorableSubList extends CursorableLinkedList implements List { | |
1207 | ||
1208 | //--- constructors ----------------------------------------------- | |
1209 | ||
1210 | 0 | CursorableSubList(CursorableLinkedList list, int from, int to) { |
1211 | 0 | if(0 > from || list.size() < to) { |
1212 | 0 | throw new IndexOutOfBoundsException(); |
1213 | 0 | } else if(from > to) { |
1214 | 0 | throw new IllegalArgumentException(); |
1215 | } | |
1216 | 0 | _list = list; |
1217 | 0 | if(from < list.size()) { |
1218 | 0 | _head.setNext(_list.getListableAt(from)); |
1219 | 0 | _pre = (null == _head.next()) ? null : _head.next().prev(); |
1220 | } else { | |
1221 | 0 | _pre = _list.getListableAt(from-1); |
1222 | } | |
1223 | 0 | if(from == to) { |
1224 | 0 | _head.setNext(null); |
1225 | 0 | _head.setPrev(null); |
1226 | 0 | if(to < list.size()) { |
1227 | 0 | _post = _list.getListableAt(to); |
1228 | } else { | |
1229 | 0 | _post = null; |
1230 | } | |
1231 | } else { | |
1232 | 0 | _head.setPrev(_list.getListableAt(to-1)); |
1233 | 0 | _post = _head.prev().next(); |
1234 | } | |
1235 | 0 | _size = to - from; |
1236 | 0 | _modCount = _list._modCount; |
1237 | 0 | } |
1238 | ||
1239 | //--- public methods ------------------------------------------ | |
1240 | ||
1241 | public void clear() { | |
1242 | 0 | checkForComod(); |
1243 | 0 | Iterator it = iterator(); |
1244 | 0 | while(it.hasNext()) { |
1245 | 0 | it.next(); |
1246 | 0 | it.remove(); |
1247 | } | |
1248 | 0 | } |
1249 | ||
1250 | public Iterator iterator() { | |
1251 | 0 | checkForComod(); |
1252 | 0 | return super.iterator(); |
1253 | } | |
1254 | ||
1255 | public int size() { | |
1256 | 0 | checkForComod(); |
1257 | 0 | return super.size(); |
1258 | } | |
1259 | ||
1260 | public boolean isEmpty() { | |
1261 | 0 | checkForComod(); |
1262 | 0 | return super.isEmpty(); |
1263 | } | |
1264 | ||
1265 | public Object[] toArray() { | |
1266 | 0 | checkForComod(); |
1267 | 0 | return super.toArray(); |
1268 | } | |
1269 | ||
1270 | public Object[] toArray(Object a[]) { | |
1271 | 0 | checkForComod(); |
1272 | 0 | return super.toArray(a); |
1273 | } | |
1274 | ||
1275 | public boolean contains(Object o) { | |
1276 | 0 | checkForComod(); |
1277 | 0 | return super.contains(o); |
1278 | } | |
1279 | ||
1280 | public boolean remove(Object o) { | |
1281 | 0 | checkForComod(); |
1282 | 0 | return super.remove(o); |
1283 | } | |
1284 | ||
1285 | public Object removeFirst() { | |
1286 | 0 | checkForComod(); |
1287 | 0 | return super.removeFirst(); |
1288 | } | |
1289 | ||
1290 | public Object removeLast() { | |
1291 | 0 | checkForComod(); |
1292 | 0 | return super.removeLast(); |
1293 | } | |
1294 | ||
1295 | public boolean addAll(Collection c) { | |
1296 | 0 | checkForComod(); |
1297 | 0 | return super.addAll(c); |
1298 | } | |
1299 | ||
1300 | public boolean add(Object o) { | |
1301 | 0 | checkForComod(); |
1302 | 0 | return super.add(o); |
1303 | } | |
1304 | ||
1305 | public boolean addFirst(Object o) { | |
1306 | 0 | checkForComod(); |
1307 | 0 | return super.addFirst(o); |
1308 | } | |
1309 | ||
1310 | public boolean addLast(Object o) { | |
1311 | 0 | checkForComod(); |
1312 | 0 | return super.addLast(o); |
1313 | } | |
1314 | ||
1315 | public boolean removeAll(Collection c) { | |
1316 | 0 | checkForComod(); |
1317 | 0 | return super.removeAll(c); |
1318 | } | |
1319 | ||
1320 | public boolean containsAll(Collection c) { | |
1321 | 0 | checkForComod(); |
1322 | 0 | return super.containsAll(c); |
1323 | } | |
1324 | ||
1325 | public boolean addAll(int index, Collection c) { | |
1326 | 0 | checkForComod(); |
1327 | 0 | return super.addAll(index,c); |
1328 | } | |
1329 | ||
1330 | public int hashCode() { | |
1331 | 0 | checkForComod(); |
1332 | 0 | return super.hashCode(); |
1333 | } | |
1334 | ||
1335 | public boolean retainAll(Collection c) { | |
1336 | 0 | checkForComod(); |
1337 | 0 | return super.retainAll(c); |
1338 | } | |
1339 | ||
1340 | public Object set(int index, Object element) { | |
1341 | 0 | checkForComod(); |
1342 | 0 | return super.set(index,element); |
1343 | } | |
1344 | ||
1345 | public boolean equals(Object o) { | |
1346 | 0 | checkForComod(); |
1347 | 0 | return super.equals(o); |
1348 | } | |
1349 | ||
1350 | public Object get(int index) { | |
1351 | 0 | checkForComod(); |
1352 | 0 | return super.get(index); |
1353 | } | |
1354 | ||
1355 | public Object getFirst() { | |
1356 | 0 | checkForComod(); |
1357 | 0 | return super.getFirst(); |
1358 | } | |
1359 | ||
1360 | public Object getLast() { | |
1361 | 0 | checkForComod(); |
1362 | 0 | return super.getLast(); |
1363 | } | |
1364 | ||
1365 | public void add(int index, Object element) { | |
1366 | 0 | checkForComod(); |
1367 | 0 | super.add(index,element); |
1368 | 0 | } |
1369 | ||
1370 | public ListIterator listIterator(int index) { | |
1371 | 0 | checkForComod(); |
1372 | 0 | return super.listIterator(index); |
1373 | } | |
1374 | ||
1375 | public Object remove(int index) { | |
1376 | 0 | checkForComod(); |
1377 | 0 | return super.remove(index); |
1378 | } | |
1379 | ||
1380 | public int indexOf(Object o) { | |
1381 | 0 | checkForComod(); |
1382 | 0 | return super.indexOf(o); |
1383 | } | |
1384 | ||
1385 | public int lastIndexOf(Object o) { | |
1386 | 0 | checkForComod(); |
1387 | 0 | return super.lastIndexOf(o); |
1388 | } | |
1389 | ||
1390 | public ListIterator listIterator() { | |
1391 | 0 | checkForComod(); |
1392 | 0 | return super.listIterator(); |
1393 | } | |
1394 | ||
1395 | public List subList(int fromIndex, int toIndex) { | |
1396 | 0 | checkForComod(); |
1397 | 0 | 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 | 0 | _modCount++; |
1411 | 0 | _size++; |
1412 | 0 | Listable elt = _list.insertListable((null == before ? _pre : before), (null == after ? _post : after),value); |
1413 | 0 | if(null == _head.next()) { |
1414 | 0 | _head.setNext(elt); |
1415 | 0 | _head.setPrev(elt); |
1416 | } | |
1417 | 0 | if(before == _head.prev()) { |
1418 | 0 | _head.setPrev(elt); |
1419 | } | |
1420 | 0 | if(after == _head.next()) { |
1421 | 0 | _head.setNext(elt); |
1422 | } | |
1423 | 0 | broadcastListableInserted(elt); |
1424 | 0 | return elt; |
1425 | } | |
1426 | ||
1427 | /** | |
1428 | * Removes the given {@link CursorableLinkedList.Listable} from my list. | |
1429 | */ | |
1430 | protected void removeListable(Listable elt) { | |
1431 | 0 | _modCount++; |
1432 | 0 | _size--; |
1433 | 0 | if(_head.next() == elt && _head.prev() == elt) { |
1434 | 0 | _head.setNext(null); |
1435 | 0 | _head.setPrev(null); |
1436 | } | |
1437 | 0 | if(_head.next() == elt) { |
1438 | 0 | _head.setNext(elt.next()); |
1439 | } | |
1440 | 0 | if(_head.prev() == elt) { |
1441 | 0 | _head.setPrev(elt.prev()); |
1442 | } | |
1443 | 0 | _list.removeListable(elt); |
1444 | 0 | broadcastListableRemoved(elt); |
1445 | 0 | } |
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 | 0 | if(_modCount != _list._modCount) { |
1457 | 0 | throw new ConcurrentModificationException(); |
1458 | } | |
1459 | 0 | } |
1460 | ||
1461 | //--- protected attributes --------------------------------------- | |
1462 | ||
1463 | /** My underlying list */ | |
1464 | 0 | protected CursorableLinkedList _list = null; |
1465 | ||
1466 | /** The element in my underlying list preceding the first element in my list. */ | |
1467 | 0 | protected Listable _pre = null; |
1468 | ||
1469 | /** The element in my underlying list following the last element in my list. */ | |
1470 | 0 | protected Listable _post = null; |
1471 | ||
1472 | } |