    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 <b>not</b> 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 * <b>Note that this implementation is not synchronized.</b>
    056 * </p>
    057 *
    058 * @see java.util.LinkedList
    059 * @since 1.0
    060 * @deprecated parent {@link AbstractLinkedList} is source incompatible with List methods added in Java 21
    061 */
    062@Deprecated
    063public class CursorableLinkedList<E> extends AbstractLinkedList<E> implements Serializable {
    064
    065    /**
    066     * An extended {@code ListIterator} that allows concurrent changes to
    067     * the underlying list.
    068     *
    069     * @param <E> the type of elements in this cursor.
    070     */
    071    public static class Cursor<E> extends AbstractLinkedList.LinkedListIterator<E> {
    072        /** Is the cursor valid (not closed) */
    073        boolean valid = true;
    074        /** Is the next index valid */
    075        boolean nextIndexValid = true;
    076        /** Flag to indicate if the current element was removed by another object. */
    077        boolean currentRemovedByAnother;
    078
    079        /**
    080         * Constructs a new cursor.
    081         *
    082         * @param parent  the parent list
    083         * @param index  the index to start from
    084         */
    085        protected Cursor(final CursorableLinkedList<E> parent, final int index) {
    086            super(parent, index);
    087            valid = true;
    088        }
    089
    090        /**
    091         * Adds an object to the list.
    092         * The object added here will be the new 'previous' in the iterator.
    093         *
    094         * @param obj  the object to add
    095         */
    096        @Override
    097        public void add(final E obj) {
    098            // overridden, as the nodeInserted() method updates the iterator state
    099            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 &lt; 0 || index &gt; 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}