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 < 0 || index > 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 }