1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 package net.sf.collections15.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.1 $ $Date: 2005/05/03 22:45:38 $
56 *
57 * @author Rodney Waldhoff
58 * @author Janek Bogucki
59 * @author Simon Kitching
60 * @author Stephen Colebourne
61 */
62 public class CursorableLinkedList<E> extends AbstractLinkedList<E> implements Serializable {
63
64 /*** Ensure serialization compatibility */
65 private static final long serialVersionUID = 3978422503477623093L;
66
67 /*** A list of the cursor currently open on this list */
68 protected transient List< WeakReference<Cursor<E>> > cursors = new ArrayList< WeakReference<Cursor<E>> >();
69
70
71 /***
72 * Constructor that creates.
73 */
74 public CursorableLinkedList() {
75 super();
76 init();
77 }
78
79 /***
80 * Constructor that copies the specified collection
81 *
82 * @param coll the collection to copy
83 */
84 public CursorableLinkedList(Collection<E> 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< WeakReference<Cursor<E>> >();
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<E> 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<E> 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<E> 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<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 < 0 || index > size()).
203 */
204 public CursorableLinkedList.Cursor<E> cursor(int fromIndex) {
205 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 protected void updateNode(Node<E> node, E value) {
220 super.updateNode(node, value);
221 broadcastNodeChanged(node);
222 }
223
224 /***
225 * Inserts a new node into the list.
226 *
227 * @param nodeToInsert new node to insert
228 * @param insertBeforeNode node to insert before
229 * @throws NullPointerException if either node is null
230 */
231 protected void addNode(Node<E> nodeToInsert, Node<E> 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<E> 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
253 Iterator<E> 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<E> cursor) {
268
269
270 for(Iterator< WeakReference<Cursor<E>> > it = cursors.iterator(); it.hasNext();) {
271 WeakReference<Cursor<E>> ref = it.next();
272 if (ref.get() == null) {
273 it.remove();
274 }
275 }
276 cursors.add( new WeakReference<Cursor<E>>(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<E> cursor) {
285 for (Iterator< WeakReference<Cursor<E>> > it = cursors.iterator(); it.hasNext();) {
286 WeakReference<Cursor<E>> ref = it.next();
287 Cursor<E> cur = ref.get();
288 if (cur == null) {
289
290
291
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<E> node) {
310 Iterator< WeakReference<Cursor<E>> > it = cursors.iterator();
311 while (it.hasNext()) {
312 WeakReference<Cursor<E>> ref = it.next();
313 Cursor<E> cursor = ref.get();
314 if (cursor == null) {
315 it.remove();
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<E> node) {
329 Iterator< WeakReference<Cursor<E>> > it = cursors.iterator();
330 while (it.hasNext()) {
331 WeakReference<Cursor<E>> ref = it.next();
332 Cursor<E> cursor = ref.get();
333 if (cursor == null) {
334 it.remove();
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<E> node) {
348 Iterator< WeakReference<Cursor<E>> > it = cursors.iterator();
349 while (it.hasNext()) {
350 WeakReference<Cursor<E>> ref = it.next();
351 Cursor<E> cursor = ref.get();
352 if (cursor == null) {
353 it.remove();
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<T> extends AbstractLinkedList.LinkedListIterator<T> {
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<T> 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(T obj) {
405 super.add(obj);
406
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<T> 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<T> node) {
439
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<T> 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<T> 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<T>) parent).unregisterCursor(this);
493 valid = false;
494 }
495 }
496 }
497 }