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