Java > Open Source Codes > org > apache > commons > collections > list > CursorableLinkedList


1 /*
2  * Copyright 2002-2004 The Apache Software Foundation
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 package org.apache.commons.collections.list;
17
18 import java.io.IOException ;
19 import java.io.ObjectInputStream ;
20 import java.io.ObjectOutputStream ;
21 import java.io.Serializable ;
22 import java.lang.ref.WeakReference ;
23 import java.util.ArrayList ;
24 import java.util.Collection ;
25 import java.util.ConcurrentModificationException ;
26 import java.util.Iterator ;
27 import java.util.List ;
28 import java.util.ListIterator ;
29
30 /**
31  * A <code>List</code> implementation with a <code>ListIterator</code> that
32  * allows concurrent modifications to the underlying list.
33  * <p>
34  * This implementation supports all of the optional {@link List} operations.
35  * It extends <code>AbstractLinkedList</code> and thus provides the
36  * stack/queue/dequeue operations available in {@link java.util.LinkedList}.
37  * <p>
38  * The main feature of this class is the ability to modify the list and the
39  * iterator at the same time. Both the {@link #listIterator()} and {@link #cursor()}
40  * methods provides access to a <code>Cursor</code> instance which extends
41  * <code>ListIterator</code>. The cursor allows changes to the list concurrent
42  * with changes to the iterator. Note that the {@link #iterator()} method and
43  * sublists do <b>not</b> provide this cursor behaviour.
44  * <p>
45  * The <code>Cursor</code> class is provided partly for backwards compatibility
46  * and partly because it allows the cursor to be directly closed. Closing the
47  * cursor is optional because references are held via a <code>WeakReference</code>.
48  * For most purposes, simply modify the iterator and list at will, and then let
49  * the garbage collector to the rest.
50  * <p>
51  * <b>Note that this implementation is not synchronized.</b>
52  *
53  * @see java.util.LinkedList
54  * @since Commons Collections 1.0
55  * @version $Revision: 1.5 $ $Date: 2004/02/18 01:12:26 $
56  *
57  * @author Rodney Waldhoff
58  * @author Janek Bogucki
59  * @author Simon Kitching
60  * @author Stephen Colebourne
61  */
62 public class CursorableLinkedList extends AbstractLinkedList implements Serializable {
63
64     /** Ensure serialization compatibility */
65     private static final long serialVersionUID = 8836393098519411393L;
66
67     /** A list of the cursor currently open on this list */
68     protected transient List cursors = new ArrayList ();
69
70     //-----------------------------------------------------------------------
71 /**
72      * Constructor that creates.
73      */
74     public CursorableLinkedList() {
75         super();
76         init(); // must call init() as use super();
77 }
78
79     /**
80      * Constructor that copies the specified collection
81      *
82      * @param coll the collection to copy
83      */
84     public CursorableLinkedList(Collection coll) {
85         super(coll);
86     }
87
88     /**
89      * The equivalent of a default constructor called
90      * by any constructor and by <code>readObject</code>.
91      */
92     protected void init() {
93         super.init();
94         cursors = new ArrayList ();
95     }
96
97     //-----------------------------------------------------------------------
98 /**
99      * 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     public Iterator iterator() {
108         return super.listIterator(0);
109     }
110
111     /**
112      * Returns a cursor iterator that allows changes to the underlying list in parallel.
113      * <p>
114      * The cursor enables iteration and list changes to occur in any order without
115      * invalidating the iterator (from one thread). When elements are added to the
116      * list, an event is fired to all active cursors enabling them to adjust to the
117      * change in the list.
118      * <p>
119      * When the "current" (i.e., last returned by {@link ListIterator#next}
120      * or {@link ListIterator#previous}) element of the list is removed,
121      * the cursor automatically adjusts to the change (invalidating the
122      * last returned value such that it cannot be removed).
123      *
124      * @return a new cursor iterator
125      */
126     public ListIterator listIterator() {
127         return cursor(0);
128     }
129
130     /**
131      * Returns a cursor iterator that allows changes to the underlying list in parallel.
132      * <p>
133      * The cursor enables iteration and list changes to occur in any order without
134      * invalidating the iterator (from one thread). When elements are added to the
135      * list, an event is fired to all active cursors enabling them to adjust to the
136      * change in the list.
137      * <p>
138      * When the "current" (i.e., last returned by {@link ListIterator#next}
139      * or {@link ListIterator#previous}) element of the list is removed,
140      * the cursor automatically adjusts to the change (invalidating the
141      * last returned value such that it cannot be removed).
142      *
143      * @param fromIndex the index to start from
144      * @return a new cursor iterator
145      */
146     public ListIterator listIterator(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 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 cursor(int fromIndex) {
205         Cursor cursor = new Cursor(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     protected void updateNode(Node node, Object 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     protected void addNode(Node nodeToInsert, Node insertBeforeNode) {
232         super.addNode(nodeToInsert, insertBeforeNode);
233         broadcastNodeInserted(nodeToInsert);
234     }
235     
236     /**
237      * Removes the specified node from the list.
238      *
239      * @param node the node to remove
240      * @throws NullPointerException if <code>node</code> is null
241      */
242     protected void removeNode(Node node) {
243         super.removeNode(node);
244         broadcastNodeRemoved(node);
245     }
246
247     /**
248      * Removes all nodes by iteration.
249      */
250     protected void removeAllNodes() {
251         if (size() > 0) {
252             // superclass implementation would break all the iterators
253 Iterator it = iterator();
254             while (it.hasNext()) {
255                 it.next();
256                 it.remove();
257             }
258         }
259     }
260
261     //-----------------------------------------------------------------------
262 /**
263      * Registers a cursor to be notified of changes to this list.
264      *
265      * @param cursor the cursor to register
266      */
267     protected void registerCursor(Cursor cursor) {
268         // We take this opportunity to clean the cursors list
269 // of WeakReference objects to garbage-collected cursors.
270 for (Iterator it = cursors.iterator(); it.hasNext();) {
271             WeakReference ref = (WeakReference ) it.next();
272             if (ref.get() == null) {
273                 it.remove();
274             }
275         }
276         cursors.add(new WeakReference (cursor));
277     }
278
279     /**
280      * Deregisters a cursor from the list to be notified of changes.
281      *
282      * @param cursor the cursor to deregister
283      */
284     protected void unregisterCursor(Cursor cursor) {
285         for (Iterator it = cursors.iterator(); it.hasNext();) {
286             WeakReference ref = (WeakReference ) it.next();
287             Cursor cur = (Cursor) ref.get();
288             if (cur == null) {
289                 // some other unrelated cursor object has been
290 // garbage-collected; let's take the opportunity to
291 // clean up the cursors list anyway..
292 it.remove();
293
294             } else if (cur == cursor) {
295                 ref.clear();
296                 it.remove();
297                 break;
298             }
299         }
300     }
301
302     //-----------------------------------------------------------------------
303 /**
304      * Informs all of my registered cursors that the specified
305      * element was changed.
306      *
307      * @param node the node that was changed
308      */
309     protected void broadcastNodeChanged(Node node) {
310         Iterator it = cursors.iterator();
311         while (it.hasNext()) {
312             WeakReference ref = (WeakReference ) it.next();
313             Cursor cursor = (Cursor) ref.get();
314             if (cursor == null) {
315                 it.remove(); // clean up list
316 } else {
317                 cursor.nodeChanged(node);
318             }
319         }
320     }
321
322     /**
323      * Informs all of my registered cursors that the specified
324      * element was just removed from my list.
325      *
326      * @param node the node that was changed
327      */
328     protected void broadcastNodeRemoved(Node node) {
329         Iterator it = cursors.iterator();
330         while (it.hasNext()) {
331             WeakReference ref = (WeakReference ) it.next();
332             Cursor cursor = (Cursor) ref.get();
333             if (cursor == null) {
334                 it.remove(); // clean up list
335 } else {
336                 cursor.nodeRemoved(node);
337             }
338         }
339     }
340
341     /**
342      * Informs all of my registered cursors that the specified
343      * element was just added to my list.
344      *
345      * @param node the node that was changed
346      */
347     protected void broadcastNodeInserted(Node node) {
348         Iterator it = cursors.iterator();
349         while (it.hasNext()) {
350             WeakReference ref = (WeakReference ) it.next();
351             Cursor cursor = (Cursor) ref.get();
352             if (cursor == null) {
353                 it.remove(); // clean up list
354 } else {
355                 cursor.nodeInserted(node);
356             }
357         }
358     }
359
360     //-----------------------------------------------------------------------
361 /**
362      * Serializes the data held in this object to the stream specified.
363      */
364     private void writeObject(ObjectOutputStream out) throws IOException {
365         out.defaultWriteObject();
366         doWriteObject(out);
367     }
368
369     /**
370      * Deserializes the data held in this object to the stream specified.
371      */
372     private void readObject(ObjectInputStream in) throws IOException , ClassNotFoundException {
373         in.defaultReadObject();
374         doReadObject(in);
375     }
376
377     //-----------------------------------------------------------------------
378 /**
379      * An extended <code>ListIterator</code> that allows concurrent changes to
380      * the underlying list.
381      */
382     public static class Cursor extends AbstractLinkedList.LinkedListIterator {
383         /** Is the cursor valid (not closed) */
384         boolean valid = true;
385         /** Is the next index valid */
386         boolean nextIndexValid = true;
387         
388         /**
389          * Constructs a new cursor.
390          *
391          * @param index the index to start from
392          */
393         protected Cursor(CursorableLinkedList parent, int index) {
394             super(parent, index);
395             valid = true;
396         }
397         
398         /**
399          * Adds an object to the list.
400          * The object added here will be the new 'previous' in the iterator.
401          *
402          * @param obj the object to add
403          */
404         public void add(Object obj) {
405             super.add(obj);
406             // add on iterator does not return the added element
407 next = next.next;
408         }
409
410         /**
411          * Gets the index of the next element to be returned.
412          *
413          * @return the next index
414          */
415         public int nextIndex() {
416             if (nextIndexValid == false) {
417                 if (next == parent.header) {
418                     nextIndex = parent.size();
419                 } else {
420                     int pos = 0;
421                     Node temp = parent.header.next;
422                     while (temp != next) {
423                         pos++;
424                         temp = temp.next;
425                     }
426                     nextIndex = pos;
427                 }
428                 nextIndexValid = true;
429             }
430             return nextIndex;
431         }
432
433         /**
434          * Handle event from the list when a node has changed.
435          *
436          * @param node the node that changed
437          */
438         protected void nodeChanged(Node node) {
439             // do nothing
440 }
441
442         /**
443          * Handle event from the list when a node has been removed.
444          *
445          * @param node the node that was removed
446          */
447         protected void nodeRemoved(Node node) {
448             if (node == next) {
449                 next = node.next;
450             } else if (node == current) {
451                 current = null;
452                 nextIndex--;
453             } else {
454                 nextIndexValid = false;
455             }
456         }
457
458         /**
459          * Handle event from the list when a node has been added.
460          *
461          * @param node the node that was added
462          */
463         protected void nodeInserted(Node node) {
464             if (node.previous == current) {
465                 next = node;
466             } else if (next.previous == node) {
467                 next = node;
468             } else {
469                 nextIndexValid = false;
470             }
471         }
472
473         /**
474          * Override superclass modCount check, and replace it with our valid flag.
475          */
476         protected void checkModCount() {
477             if (!valid) {
478                 throw new ConcurrentModificationException ("Cursor closed");
479             }
480         }
481
482         /**
483          * Mark this cursor as no longer being needed. Any resources
484          * associated with this cursor are immediately released.
485          * In previous versions of this class, it was mandatory to close
486          * all cursor objects to avoid memory leaks. It is <i>no longer</i>
487          * necessary to call this close method; an instance of this class
488          * can now be treated exactly like a normal iterator.
489          */
490         public void close() {
491             if (valid) {
492                 ((CursorableLinkedList) parent).unregisterCursor(this);
493                 valid = false;
494             }
495         }
496     }
497 }
498

A to Z: JavaDoc & Examples

---

Daily Java News & Articles

---

Open Source Projects

---

Open Source Codes

---

Free Computer Books

---

Remove Frame

---

Popular Tags