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