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