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