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