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