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