1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.collections.list;
18
19 import java.io.IOException;
20 import java.io.ObjectInputStream;
21 import java.io.ObjectOutputStream;
22 import java.io.Serializable;
23 import java.lang.ref.WeakReference;
24 import java.util.ArrayList;
25 import java.util.Collection;
26 import java.util.ConcurrentModificationException;
27 import java.util.Iterator;
28 import java.util.List;
29 import java.util.ListIterator;
30
31 /**
32 * A <code>List</code> implementation with a <code>ListIterator</code> that
33 * allows concurrent modifications to the underlying list.
34 * <p>
35 * This implementation supports all of the optional {@link List} operations.
36 * It extends <code>AbstractLinkedList</code> and thus provides the
37 * stack/queue/dequeue operations available in {@link java.util.LinkedList}.
38 * <p>
39 * The main feature of this class is the ability to modify the list and the
40 * iterator at the same time. Both the {@link #listIterator()} and {@link #cursor()}
41 * methods provides access to a <code>Cursor</code> instance which extends
42 * <code>ListIterator</code>. The cursor allows changes to the list concurrent
43 * with changes to the iterator. Note that the {@link #iterator()} method and
44 * sublists do <b>not</b> provide this cursor behaviour.
45 * <p>
46 * The <code>Cursor</code> class is provided partly for backwards compatibility
47 * and partly because it allows the cursor to be directly closed. Closing the
48 * cursor is optional because references are held via a <code>WeakReference</code>.
49 * For most purposes, simply modify the iterator and list at will, and then let
50 * the garbage collector to the rest.
51 * <p>
52 * <b>Note that this implementation is not synchronized.</b>
53 *
54 * @see java.util.LinkedList
55 * @since 1.0
56 * @version $Id: CursorableLinkedList.java 1429905 2013-01-07 17:15:14Z ggregory $
57 */
58 public class CursorableLinkedList<E> extends AbstractLinkedList<E> implements Serializable {
59
60 /** Ensure serialization compatibility */
61 private static final long serialVersionUID = 8836393098519411393L;
62
63 /** A list of the cursor currently open on this list */
64 protected transient List<WeakReference<Cursor<E>>> cursors;
65
66 //-----------------------------------------------------------------------
67 /**
68 * Constructor that creates.
69 */
70 public CursorableLinkedList() {
71 super();
72 init(); // must call init() as use super();
73 }
74
75 /**
76 * Constructor that copies the specified collection
77 *
78 * @param coll the collection to copy
79 */
80 public CursorableLinkedList(final Collection<E> coll) {
81 super(coll);
82 }
83
84 /**
85 * The equivalent of a default constructor called
86 * by any constructor and by <code>readObject</code>.
87 */
88 @Override
89 protected void init() {
90 super.init();
91 cursors = new ArrayList<WeakReference<Cursor<E>>>();
92 }
93
94 //-----------------------------------------------------------------------
95 /**
96 * Returns an iterator that does <b>not</b> support concurrent modification.
97 * <p>
98 * If the underlying list is modified while iterating using this iterator
99 * a ConcurrentModificationException will occur.
100 * The cursor behaviour is available via {@link #listIterator()}.
101 *
102 * @return a new iterator that does <b>not</b> support concurrent modification
103 */
104 @Override
105 public Iterator<E> iterator() {
106 return super.listIterator(0);
107 }
108
109 /**
110 * Returns a cursor iterator that allows changes to the underlying list in parallel.
111 * <p>
112 * The cursor enables iteration and list changes to occur in any order without
113 * invalidating the iterator (from one thread). When elements are added to the
114 * list, an event is fired to all active cursors enabling them to adjust to the
115 * change in the list.
116 * <p>
117 * When the "current" (i.e., last returned by {@link ListIterator#next}
118 * or {@link ListIterator#previous}) element of the list is removed,
119 * the cursor automatically adjusts to the change (invalidating the
120 * last returned value such that it cannot be removed).
121 *
122 * @return a new cursor iterator
123 */
124 @Override
125 public ListIterator<E> listIterator() {
126 return cursor(0);
127 }
128
129 /**
130 * Returns a cursor iterator that allows changes to the underlying list in parallel.
131 * <p>
132 * The cursor enables iteration and list changes to occur in any order without
133 * invalidating the iterator (from one thread). When elements are added to the
134 * list, an event is fired to all active cursors enabling them to adjust to the
135 * change in the list.
136 * <p>
137 * When the "current" (i.e., last returned by {@link ListIterator#next}
138 * or {@link ListIterator#previous}) element of the list is removed,
139 * the cursor automatically adjusts to the change (invalidating the
140 * last returned value such that it cannot be removed).
141 *
142 * @param fromIndex the index to start from
143 * @return a new cursor iterator
144 */
145 @Override
146 public ListIterator<E> listIterator(final int fromIndex) {
147 return cursor(fromIndex);
148 }
149
150 /**
151 * Returns a {@link Cursor} for iterating through the elements of this list.
152 * <p>
153 * A <code>Cursor</code> is a <code>ListIterator</code> with an additional
154 * <code>close()</code> method. Calling this method immediately discards the
155 * references to the cursor. If it is not called, then the garbage collector
156 * will still remove the reference as it is held via a <code>WeakReference</code>.
157 * <p>
158 * The cursor enables iteration and list changes to occur in any order without
159 * invalidating the iterator (from one thread). When elements are added to the
160 * list, an event is fired to all active cursors enabling them to adjust to the
161 * change in the list.
162 * <p>
163 * When the "current" (i.e., last returned by {@link ListIterator#next}
164 * or {@link ListIterator#previous}) element of the list is removed,
165 * the cursor automatically adjusts to the change (invalidating the
166 * last returned value such that it cannot be removed).
167 * <p>
168 * The {@link #listIterator()} method returns the same as this method, and can
169 * be cast to a <code>Cursor</code> if the <code>close</code> method is required.
170 *
171 * @return a new cursor iterator
172 */
173 public CursorableLinkedList.Cursor<E> cursor() {
174 return cursor(0);
175 }
176
177 /**
178 * Returns a {@link Cursor} for iterating through the elements of this list
179 * starting from a specified index.
180 * <p>
181 * A <code>Cursor</code> is a <code>ListIterator</code> with an additional
182 * <code>close()</code> method. Calling this method immediately discards the
183 * references to the cursor. If it is not called, then the garbage collector
184 * will still remove the reference as it is held via a <code>WeakReference</code>.
185 * <p>
186 * The cursor enables iteration and list changes to occur in any order without
187 * invalidating the iterator (from one thread). When elements are added to the
188 * list, an event is fired to all active cursors enabling them to adjust to the
189 * change in the list.
190 * <p>
191 * When the "current" (i.e., last returned by {@link ListIterator#next}
192 * or {@link ListIterator#previous}) element of the list is removed,
193 * the cursor automatically adjusts to the change (invalidating the
194 * last returned value such that it cannot be removed).
195 * <p>
196 * The {@link #listIterator(int)} method returns the same as this method, and can
197 * be cast to a <code>Cursor</code> if the <code>close</code> method is required.
198 *
199 * @param fromIndex the index to start from
200 * @return a new cursor iterator
201 * @throws IndexOutOfBoundsException if the index is out of range
202 * (index < 0 || index > size()).
203 */
204 public CursorableLinkedList.Cursor<E> cursor(final int fromIndex) {
205 final Cursor<E> cursor = new Cursor<E>(this, fromIndex);
206 registerCursor(cursor);
207 return cursor;
208 }
209
210 //-----------------------------------------------------------------------
211 /**
212 * Updates the node with a new value.
213 * This implementation sets the value on the node.
214 * Subclasses can override this to record the change.
215 *
216 * @param node node to update
217 * @param value new value of the node
218 */
219 @Override
220 protected void updateNode(final Node<E> node, final E value) {
221 super.updateNode(node, value);
222 broadcastNodeChanged(node);
223 }
224
225 /**
226 * Inserts a new node into the list.
227 *
228 * @param nodeToInsert new node to insert
229 * @param insertBeforeNode node to insert before
230 * @throws NullPointerException if either node is null
231 */
232 @Override
233 protected void addNode(final Node<E> nodeToInsert, final Node<E> insertBeforeNode) {
234 super.addNode(nodeToInsert, insertBeforeNode);
235 broadcastNodeInserted(nodeToInsert);
236 }
237
238 /**
239 * Removes the specified node from the list.
240 *
241 * @param node the node to remove
242 * @throws NullPointerException if <code>node</code> is null
243 */
244 @Override
245 protected void removeNode(final Node<E> node) {
246 super.removeNode(node);
247 broadcastNodeRemoved(node);
248 }
249
250 /**
251 * Removes all nodes by iteration.
252 */
253 @Override
254 protected void removeAllNodes() {
255 if (size() > 0) {
256 // superclass implementation would break all the iterators
257 final Iterator<E> it = iterator();
258 while (it.hasNext()) {
259 it.next();
260 it.remove();
261 }
262 }
263 }
264
265 //-----------------------------------------------------------------------
266 /**
267 * Registers a cursor to be notified of changes to this list.
268 *
269 * @param cursor the cursor to register
270 */
271 protected void registerCursor(final Cursor<E> cursor) {
272 // We take this opportunity to clean the cursors list
273 // of WeakReference objects to garbage-collected cursors.
274 for (final Iterator<WeakReference<Cursor<E>>> it = cursors.iterator(); it.hasNext();) {
275 final WeakReference<Cursor<E>> ref = it.next();
276 if (ref.get() == null) {
277 it.remove();
278 }
279 }
280 cursors.add(new WeakReference<Cursor<E>>(cursor));
281 }
282
283 /**
284 * Deregisters a cursor from the list to be notified of changes.
285 *
286 * @param cursor the cursor to deregister
287 */
288 protected void unregisterCursor(final Cursor<E> cursor) {
289 for (final Iterator<WeakReference<Cursor<E>>> it = cursors.iterator(); it.hasNext();) {
290 final WeakReference<Cursor<E>> ref = it.next();
291 final Cursor<E> cur = ref.get();
292 if (cur == null) {
293 // some other unrelated cursor object has been
294 // garbage-collected; let's take the opportunity to
295 // clean up the cursors list anyway..
296 it.remove();
297 } else if (cur == cursor) {
298 ref.clear();
299 it.remove();
300 break;
301 }
302 }
303 }
304
305 //-----------------------------------------------------------------------
306 /**
307 * Informs all of my registered cursors that the specified
308 * element was changed.
309 *
310 * @param node the node that was changed
311 */
312 protected void broadcastNodeChanged(final Node<E> node) {
313 final Iterator<WeakReference<Cursor<E>>> it = cursors.iterator();
314 while (it.hasNext()) {
315 final WeakReference<Cursor<E>> ref = it.next();
316 final Cursor<E> cursor = ref.get();
317 if (cursor == null) {
318 it.remove(); // clean up list
319 } else {
320 cursor.nodeChanged(node);
321 }
322 }
323 }
324
325 /**
326 * Informs all of my registered cursors that the specified
327 * element was just removed from my list.
328 *
329 * @param node the node that was changed
330 */
331 protected void broadcastNodeRemoved(final Node<E> node) {
332 final Iterator<WeakReference<Cursor<E>>> it = cursors.iterator();
333 while (it.hasNext()) {
334 final WeakReference<Cursor<E>> ref = it.next();
335 final Cursor<E> cursor = ref.get();
336 if (cursor == null) {
337 it.remove(); // clean up list
338 } else {
339 cursor.nodeRemoved(node);
340 }
341 }
342 }
343
344 /**
345 * Informs all of my registered cursors that the specified
346 * element was just added to my list.
347 *
348 * @param node the node that was changed
349 */
350 protected void broadcastNodeInserted(final Node<E> node) {
351 final Iterator<WeakReference<Cursor<E>>> it = cursors.iterator();
352 while (it.hasNext()) {
353 final WeakReference<Cursor<E>> ref = it.next();
354 final Cursor<E> cursor = ref.get();
355 if (cursor == null) {
356 it.remove(); // clean up list
357 } else {
358 cursor.nodeInserted(node);
359 }
360 }
361 }
362
363 //-----------------------------------------------------------------------
364 /**
365 * Serializes the data held in this object to the stream specified.
366 */
367 private void writeObject(final ObjectOutputStream out) throws IOException {
368 out.defaultWriteObject();
369 doWriteObject(out);
370 }
371
372 /**
373 * Deserializes the data held in this object to the stream specified.
374 */
375 private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
376 in.defaultReadObject();
377 doReadObject(in);
378 }
379
380 //-----------------------------------------------------------------------
381 /**
382 * Creates a list iterator for the sublist.
383 *
384 * @param subList the sublist to get an iterator for
385 * @param fromIndex the index to start from, relative to the sublist
386 * @return the list iterator for the sublist
387 */
388 @Override
389 protected ListIterator<E> createSubListListIterator(final LinkedSubList<E> subList, final int fromIndex) {
390 final SubCursor<E> cursor = new SubCursor<E>(subList, fromIndex);
391 registerCursor(cursor);
392 return cursor;
393 }
394
395 //-----------------------------------------------------------------------
396 /**
397 * An extended <code>ListIterator</code> that allows concurrent changes to
398 * the underlying list.
399 */
400 public static class Cursor<E> extends AbstractLinkedList.LinkedListIterator<E> {
401 /** Is the cursor valid (not closed) */
402 boolean valid = true;
403 /** Is the next index valid */
404 boolean nextIndexValid = true;
405 /** Flag to indicate if the current element was removed by another object. */
406 boolean currentRemovedByAnother = false;
407
408 /**
409 * Constructs a new cursor.
410 *
411 * @param parent the parent list
412 * @param index the index to start from
413 */
414 protected Cursor(final CursorableLinkedList<E> parent, final int index) {
415 super(parent, index);
416 valid = true;
417 }
418
419 /**
420 * Removes the item last returned by this iterator.
421 * <p>
422 * There may have been subsequent alterations to the list
423 * since you obtained this item, however you can still remove it.
424 * You can even remove it if the item is no longer in the main list.
425 * However, you can't call this method on the same iterator more
426 * than once without calling next() or previous().
427 *
428 * @throws IllegalStateException if there is no item to remove
429 */
430 @Override
431 public void remove() {
432 // overridden, as the nodeRemoved() method updates the iterator
433 // state in the parent.removeNode() call below
434 if (current == null && currentRemovedByAnother) {
435 // quietly ignore, as the last returned node was removed
436 // by the list or some other iterator
437 // by ignoring it, we keep this iterator independent from
438 // other changes as much as possible
439 } else {
440 checkModCount();
441 parent.removeNode(getLastNodeReturned());
442 }
443 currentRemovedByAnother = false;
444 }
445
446 /**
447 * Adds an object to the list.
448 * The object added here will be the new 'previous' in the iterator.
449 *
450 * @param obj the object to add
451 */
452 @Override
453 public void add(final E obj) {
454 // overridden, as the nodeInserted() method updates the iterator state
455 super.add(obj);
456 // matches the (next.previous == node) clause in nodeInserted()
457 // thus next gets changed - reset it again here
458 next = next.next;
459 }
460
461 // set is not overridden, as it works ok
462 // note that we want it to throw an exception if the element being
463 // set has been removed from the real list (compare this with the
464 // remove method where we silently ignore this case)
465
466 /**
467 * Gets the index of the next element to be returned.
468 *
469 * @return the next index
470 */
471 @Override
472 public int nextIndex() {
473 if (nextIndexValid == false) {
474 if (next == parent.header) {
475 nextIndex = parent.size();
476 } else {
477 int pos = 0;
478 Node<E> temp = parent.header.next;
479 while (temp != next) {
480 pos++;
481 temp = temp.next;
482 }
483 nextIndex = pos;
484 }
485 nextIndexValid = true;
486 }
487 return nextIndex;
488 }
489
490 /**
491 * Handle event from the list when a node has changed.
492 *
493 * @param node the node that changed
494 */
495 protected void nodeChanged(final Node<E> node) {
496 // do nothing
497 }
498
499 /**
500 * Handle event from the list when a node has been removed.
501 *
502 * @param node the node that was removed
503 */
504 protected void nodeRemoved(final Node<E> node) {
505 if (node == next && node == current) {
506 // state where next() followed by previous()
507 next = node.next;
508 current = null;
509 currentRemovedByAnother = true;
510 } else if (node == next) {
511 // state where next() not followed by previous()
512 // and we are matching next node
513 next = node.next;
514 currentRemovedByAnother = false;
515 } else if (node == current) {
516 // state where next() not followed by previous()
517 // and we are matching current (last returned) node
518 current = null;
519 currentRemovedByAnother = true;
520 nextIndex--;
521 } else {
522 nextIndexValid = false;
523 currentRemovedByAnother = false;
524 }
525 }
526
527 /**
528 * Handle event from the list when a node has been added.
529 *
530 * @param node the node that was added
531 */
532 protected void nodeInserted(final Node<E> node) {
533 if (node.previous == current) {
534 next = node;
535 } else if (next.previous == node) {
536 next = node;
537 } else {
538 nextIndexValid = false;
539 }
540 }
541
542 /**
543 * Override superclass modCount check, and replace it with our valid flag.
544 */
545 @Override
546 protected void checkModCount() {
547 if (!valid) {
548 throw new ConcurrentModificationException("Cursor closed");
549 }
550 }
551
552 /**
553 * Mark this cursor as no longer being needed. Any resources
554 * associated with this cursor are immediately released.
555 * In previous versions of this class, it was mandatory to close
556 * all cursor objects to avoid memory leaks. It is <i>no longer</i>
557 * necessary to call this close method; an instance of this class
558 * can now be treated exactly like a normal iterator.
559 */
560 public void close() {
561 if (valid) {
562 ((CursorableLinkedList<E>) parent).unregisterCursor(this);
563 valid = false;
564 }
565 }
566 }
567
568 //-----------------------------------------------------------------------
569 /**
570 * A cursor for the sublist based on LinkedSubListIterator.
571 *
572 * @since 3.2
573 */
574 protected static class SubCursor<E> extends Cursor<E> {
575
576 /** The parent list */
577 protected final LinkedSubList<E> sub;
578
579 /**
580 * Constructs a new cursor.
581 *
582 * @param sub the sub list
583 * @param index the index to start from
584 */
585 protected SubCursor(final LinkedSubList<E> sub, final int index) {
586 super((CursorableLinkedList<E>) sub.parent, index + sub.offset);
587 this.sub = sub;
588 }
589
590 @Override
591 public boolean hasNext() {
592 return nextIndex() < sub.size;
593 }
594
595 @Override
596 public boolean hasPrevious() {
597 return previousIndex() >= 0;
598 }
599
600 @Override
601 public int nextIndex() {
602 return super.nextIndex() - sub.offset;
603 }
604
605 @Override
606 public void add(final E obj) {
607 super.add(obj);
608 sub.expectedModCount = parent.modCount;
609 sub.size++;
610 }
611
612 @Override
613 public void remove() {
614 super.remove();
615 sub.expectedModCount = parent.modCount;
616 sub.size--;
617 }
618 }
619
620 }