CursorableLinkedList.java
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
package org.apache.commons.collections4.list;
import java.io.IOException;
import java.io.ObjectInputStream;
import java.io.ObjectOutputStream;
import java.io.Serializable;
import java.lang.ref.WeakReference;
import java.util.ArrayList;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
/**
* A {@code List} implementation with a {@code ListIterator} that
* allows concurrent modifications to the underlying list.
* <p>
* This implementation supports all of the optional {@link List} operations.
* It extends {@code AbstractLinkedList} and thus provides the
* stack/queue/dequeue operations available in {@link java.util.LinkedList}.
* </p>
* <p>
* The main feature of this class is the ability to modify the list and the
* iterator at the same time. Both the {@link #listIterator()} and {@link #cursor()}
* methods provides access to a {@code Cursor} instance which extends
* {@code ListIterator}. The cursor allows changes to the list concurrent
* with changes to the iterator. Note that the {@link #iterator()} method and
* sublists do <strong>not</strong> provide this cursor behavior.
* </p>
* <p>
* The {@code Cursor} class is provided partly for backwards compatibility
* and partly because it allows the cursor to be directly closed. Closing the
* cursor is optional because references are held via a {@code WeakReference}.
* For most purposes, simply modify the iterator and list at will, and then let
* the garbage collector to the rest.
* </p>
* <p>
* <strong>Note that this implementation is not synchronized.</strong>
* </p>
*
* @param <E> the type of the elements in the list.
* @see java.util.LinkedList
* @since 1.0
* @deprecated parent {@link AbstractLinkedList} is source incompatible with List methods added in Java 21
*/
@Deprecated
public class CursorableLinkedList<E> extends AbstractLinkedList<E> implements Serializable {
/**
* An extended {@code ListIterator} that allows concurrent changes to
* the underlying list.
*
* @param <E> the type of elements in this cursor.
*/
public static class Cursor<E> extends AbstractLinkedList.LinkedListIterator<E> {
/** Is the cursor valid (not closed) */
boolean valid = true;
/** Is the next index valid */
boolean nextIndexValid = true;
/** Flag to indicate if the current element was removed by another object. */
boolean currentRemovedByAnother;
/**
* Constructs a new cursor.
*
* @param parent the parent list
* @param index the index to start from
*/
protected Cursor(final CursorableLinkedList<E> parent, final int index) {
super(parent, index);
valid = true;
}
/**
* Adds an object to the list.
* The object added here will be the new 'previous' in the iterator.
*
* @param obj the object to add
*/
@Override
public void add(final E obj) {
// overridden, as the nodeInserted() method updates the iterator state
super.add(obj);
// matches the (next.previous == node) clause in nodeInserted()
// thus next gets changed - reset it again here
next = next.next;
}
/**
* Override superclass modCount check, and replace it with our valid flag.
*/
@Override
protected void checkModCount() {
if (!valid) {
throw new ConcurrentModificationException("Cursor closed");
}
}
// set is not overridden, as it works ok
// note that we want it to throw an exception if the element being
// set has been removed from the real list (compare this with the
// remove method where we silently ignore this case)
/**
* Mark this cursor as no longer being needed. Any resources
* associated with this cursor are immediately released.
* In previous versions of this class, it was mandatory to close
* all cursor objects to avoid memory leaks. It is <em>no longer</em>
* necessary to call this close method; an instance of this class
* can now be treated exactly like a normal iterator.
*/
public void close() {
if (valid) {
((CursorableLinkedList<E>) parent).unregisterCursor(this);
valid = false;
}
}
/**
* Gets the index of the next element to be returned.
*
* @return the next index
*/
@Override
public int nextIndex() {
if (!nextIndexValid) {
if (next == parent.header) {
nextIndex = parent.size();
} else {
int pos = 0;
Node<E> temp = parent.header.next;
while (temp != next) {
pos++;
temp = temp.next;
}
nextIndex = pos;
}
nextIndexValid = true;
}
return nextIndex;
}
/**
* Handle event from the list when a node has changed.
*
* @param node the node that changed
*/
protected void nodeChanged(final Node<E> node) {
// do nothing
}
/**
* Handle event from the list when a node has been added.
*
* @param node the node that was added
*/
protected void nodeInserted(final Node<E> node) {
if (node.previous == current || next.previous == node) {
next = node;
} else {
nextIndexValid = false;
}
}
/**
* Handle event from the list when a node has been removed.
*
* @param node the node that was removed
*/
protected void nodeRemoved(final Node<E> node) {
if (node == next && node == current) {
// state where next() followed by previous()
next = node.next;
current = null;
currentRemovedByAnother = true;
} else if (node == next) {
// state where next() not followed by previous()
// and we are matching next node
next = node.next;
currentRemovedByAnother = false;
} else if (node == current) {
// state where next() not followed by previous()
// and we are matching current (last returned) node
current = null;
currentRemovedByAnother = true;
nextIndex--;
} else {
nextIndexValid = false;
currentRemovedByAnother = false;
}
}
/**
* Removes the item last returned by this iterator.
* <p>
* There may have been subsequent alterations to the list
* since you obtained this item, however you can still remove it.
* You can even remove it if the item is no longer in the main list.
* However, you can't call this method on the same iterator more
* than once without calling next() or previous().
*
* @throws IllegalStateException if there is no item to remove
*/
@Override
public void remove() {
// overridden, as the nodeRemoved() method updates the iterator
// state in the parent.removeNode() call below
if (current == null && currentRemovedByAnother) { // NOPMD
// quietly ignore, as the last returned node was removed
// by the list or some other iterator
// by ignoring it, we keep this iterator independent of
// other changes as much as possible
} else {
checkModCount();
parent.removeNode(getLastNodeReturned());
}
currentRemovedByAnother = false;
}
}
/**
* A cursor for the sublist based on LinkedSubListIterator.
*
* @param <E> the type of elements in this cursor.
* @since 3.2
*/
protected static class SubCursor<E> extends Cursor<E> {
/** The parent list */
protected final LinkedSubList<E> sub;
/**
* Constructs a new cursor.
*
* @param sub the sub list
* @param index the index to start from
*/
protected SubCursor(final LinkedSubList<E> sub, final int index) {
super((CursorableLinkedList<E>) sub.parent, index + sub.offset);
this.sub = sub;
}
@Override
public void add(final E obj) {
super.add(obj);
sub.expectedModCount = parent.modCount;
sub.size++;
}
@Override
public boolean hasNext() {
return nextIndex() < sub.size;
}
@Override
public boolean hasPrevious() {
return previousIndex() >= 0;
}
@Override
public int nextIndex() {
return super.nextIndex() - sub.offset;
}
@Override
public void remove() {
super.remove();
sub.expectedModCount = parent.modCount;
sub.size--;
}
}
/** Ensure serialization compatibility */
private static final long serialVersionUID = 8836393098519411393L;
/** A list of the cursor currently open on this list */
private transient List<WeakReference<Cursor<E>>> cursors;
/**
* Constructor that creates.
*/
public CursorableLinkedList() {
init(); // must call init() as use super();
}
/**
* Constructor that copies the specified collection
*
* @param coll the collection to copy
*/
public CursorableLinkedList(final Collection<? extends E> coll) {
super(coll);
}
/**
* Inserts a new node into the list.
*
* @param nodeToInsert new node to insert
* @param insertBeforeNode node to insert before
* @throws NullPointerException if either node is null
*/
@Override
protected void addNode(final Node<E> nodeToInsert, final Node<E> insertBeforeNode) {
super.addNode(nodeToInsert, insertBeforeNode);
broadcastNodeInserted(nodeToInsert);
}
/**
* Informs all of my registered cursors that the specified
* element was changed.
*
* @param node the node that was changed
*/
protected void broadcastNodeChanged(final Node<E> node) {
final Iterator<WeakReference<Cursor<E>>> it = cursors.iterator();
while (it.hasNext()) {
final WeakReference<Cursor<E>> ref = it.next();
final Cursor<E> cursor = ref.get();
if (cursor == null) {
it.remove(); // clean up list
} else {
cursor.nodeChanged(node);
}
}
}
/**
* Informs all of my registered cursors that the specified
* element was just added to my list.
*
* @param node the node that was changed
*/
protected void broadcastNodeInserted(final Node<E> node) {
final Iterator<WeakReference<Cursor<E>>> it = cursors.iterator();
while (it.hasNext()) {
final WeakReference<Cursor<E>> ref = it.next();
final Cursor<E> cursor = ref.get();
if (cursor == null) {
it.remove(); // clean up list
} else {
cursor.nodeInserted(node);
}
}
}
/**
* Informs all of my registered cursors that the specified
* element was just removed from my list.
*
* @param node the node that was changed
*/
protected void broadcastNodeRemoved(final Node<E> node) {
final Iterator<WeakReference<Cursor<E>>> it = cursors.iterator();
while (it.hasNext()) {
final WeakReference<Cursor<E>> ref = it.next();
final Cursor<E> cursor = ref.get();
if (cursor == null) {
it.remove(); // clean up list
} else {
cursor.nodeRemoved(node);
}
}
}
/**
* Creates a list iterator for the sublist.
*
* @param subList the sublist to get an iterator for
* @param fromIndex the index to start from, relative to the sublist
* @return the list iterator for the sublist
*/
@Override
protected ListIterator<E> createSubListListIterator(final LinkedSubList<E> subList, final int fromIndex) {
final SubCursor<E> cursor = new SubCursor<>(subList, fromIndex);
registerCursor(cursor);
return cursor;
}
/**
* Returns a {@link Cursor} for iterating through the elements of this list.
* <p>
* A {@code Cursor} is a {@code ListIterator} with an additional
* {@code close()} method. Calling this method immediately discards the
* references to the cursor. If it is not called, then the garbage collector
* will still remove the reference as it is held via a {@code WeakReference}.
* <p>
* The cursor enables iteration and list changes to occur in any order without
* invalidating the iterator (from one thread). When elements are added to the
* list, an event is fired to all active cursors enabling them to adjust to the
* change in the list.
* <p>
* When the "current" (i.e., last returned by {@link ListIterator#next}
* or {@link ListIterator#previous}) element of the list is removed,
* the cursor automatically adjusts to the change (invalidating the
* last returned value such that it cannot be removed).
* <p>
* The {@link #listIterator()} method returns the same as this method, and can
* be cast to a {@code Cursor} if the {@code close} method is required.
*
* @return a new cursor iterator
*/
public CursorableLinkedList.Cursor<E> cursor() {
return cursor(0);
}
/**
* Returns a {@link Cursor} for iterating through the elements of this list
* starting from a specified index.
* <p>
* A {@code Cursor} is a {@code ListIterator} with an additional
* {@code close()} method. Calling this method immediately discards the
* references to the cursor. If it is not called, then the garbage collector
* will still remove the reference as it is held via a {@code WeakReference}.
* <p>
* The cursor enables iteration and list changes to occur in any order without
* invalidating the iterator (from one thread). When elements are added to the
* list, an event is fired to all active cursors enabling them to adjust to the
* change in the list.
* <p>
* When the "current" (i.e., last returned by {@link ListIterator#next}
* or {@link ListIterator#previous}) element of the list is removed,
* the cursor automatically adjusts to the change (invalidating the
* last returned value such that it cannot be removed).
* <p>
* The {@link #listIterator(int)} method returns the same as this method, and can
* be cast to a {@code Cursor} if the {@code close} method is required.
*
* @param fromIndex the index to start from
* @return a new cursor iterator
* @throws IndexOutOfBoundsException if the index is out of range
* (index < 0 || index > size()).
*/
public CursorableLinkedList.Cursor<E> cursor(final int fromIndex) {
final Cursor<E> cursor = new Cursor<>(this, fromIndex);
registerCursor(cursor);
return cursor;
}
/**
* The equivalent of a default constructor called
* by any constructor and by {@code readObject}.
*/
@Override
protected void init() {
super.init();
cursors = new ArrayList<>();
}
/**
* Returns an iterator that does <strong>not</strong> support concurrent modification.
* <p>
* If the underlying list is modified while iterating using this iterator
* a ConcurrentModificationException will occur.
* The cursor behavior is available via {@link #listIterator()}.
*
* @return a new iterator that does <strong>not</strong> support concurrent modification
*/
@Override
public Iterator<E> iterator() {
return super.listIterator(0);
}
/**
* Returns a cursor iterator that allows changes to the underlying list in parallel.
* <p>
* The cursor enables iteration and list changes to occur in any order without
* invalidating the iterator (from one thread). When elements are added to the
* list, an event is fired to all active cursors enabling them to adjust to the
* change in the list.
* <p>
* When the "current" (i.e., last returned by {@link ListIterator#next}
* or {@link ListIterator#previous}) element of the list is removed,
* the cursor automatically adjusts to the change (invalidating the
* last returned value such that it cannot be removed).
*
* @return a new cursor iterator
*/
@Override
public ListIterator<E> listIterator() {
return cursor(0);
}
/**
* Returns a cursor iterator that allows changes to the underlying list in parallel.
* <p>
* The cursor enables iteration and list changes to occur in any order without
* invalidating the iterator (from one thread). When elements are added to the
* list, an event is fired to all active cursors enabling them to adjust to the
* change in the list.
* <p>
* When the "current" (i.e., last returned by {@link ListIterator#next}
* or {@link ListIterator#previous}) element of the list is removed,
* the cursor automatically adjusts to the change (invalidating the
* last returned value such that it cannot be removed).
*
* @param fromIndex the index to start from
* @return a new cursor iterator
*/
@Override
public ListIterator<E> listIterator(final int fromIndex) {
return cursor(fromIndex);
}
/**
* Deserializes the data held in this object to the stream specified.
*
* @param in the input stream
* @throws IOException if an error occurs while reading from the stream
* @throws ClassNotFoundException if an object read from the stream cannot be loaded
*/
private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException {
in.defaultReadObject();
doReadObject(in);
}
/**
* Registers a cursor to be notified of changes to this list.
*
* @param cursor the cursor to register
*/
protected void registerCursor(final Cursor<E> cursor) {
// We take this opportunity to clean the cursors list
// of WeakReference objects to garbage-collected cursors.
cursors.removeIf(ref -> ref.get() == null);
cursors.add(new WeakReference<>(cursor));
}
/**
* Removes all nodes by iteration.
*/
@Override
protected void removeAllNodes() {
if (!isEmpty()) {
// superclass implementation would break all the iterators
final Iterator<E> it = iterator();
while (it.hasNext()) {
it.next();
it.remove();
}
}
}
/**
* Removes the specified node from the list.
*
* @param node the node to remove
* @throws NullPointerException if {@code node} is null
*/
@Override
protected void removeNode(final Node<E> node) {
super.removeNode(node);
broadcastNodeRemoved(node);
}
/**
* Deregisters a cursor from the list to be notified of changes.
*
* @param cursor the cursor to deregister
*/
protected void unregisterCursor(final Cursor<E> cursor) {
for (final Iterator<WeakReference<Cursor<E>>> it = cursors.iterator(); it.hasNext();) {
final WeakReference<Cursor<E>> ref = it.next();
final Cursor<E> cur = ref.get();
if (cur == null) {
// some other unrelated cursor object has been
// garbage-collected; let's take the opportunity to
// clean up the cursors list anyway.
it.remove();
} else if (cur == cursor) {
ref.clear();
it.remove();
break;
}
}
}
/**
* Updates the node with a new value.
* This implementation sets the value on the node.
* Subclasses can override this to record the change.
*
* @param node node to update
* @param value new value of the node
*/
@Override
protected void updateNode(final Node<E> node, final E value) {
super.updateNode(node, value);
broadcastNodeChanged(node);
}
/**
* Serializes this object to an ObjectOutputStream.
*
* @param out the target ObjectOutputStream.
* @throws IOException thrown when an I/O errors occur writing to the target stream.
*/
private void writeObject(final ObjectOutputStream out) throws IOException {
out.defaultWriteObject();
doWriteObject(out);
}
}