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}