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