001: /*
002: * Copyright 2002-2005 The Apache Software Foundation
003: *
004: * Licensed under the Apache License, Version 2.0 (the "License");
005: * you may not use this file except in compliance with the License.
006: * You may obtain a copy of the License at
007: *
008: * http://www.apache.org/licenses/LICENSE-2.0
009: *
010: * Unless required by applicable law or agreed to in writing, software
011: * distributed under the License is distributed on an "AS IS" BASIS,
012: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
013: * See the License for the specific language governing permissions and
014: * limitations under the License.
015: */
016: package org.apache.commons.collections.list;
017:
018: import java.io.IOException;
019: import java.io.ObjectInputStream;
020: import java.io.ObjectOutputStream;
021: import java.io.Serializable;
022: import java.lang.ref.WeakReference;
023: import java.util.ArrayList;
024: import java.util.Collection;
025: import java.util.ConcurrentModificationException;
026: import java.util.Iterator;
027: import java.util.List;
028: import java.util.ListIterator;
029:
030: /**
031: * A <code>List</code> implementation with a <code>ListIterator</code> that
032: * allows concurrent modifications to the underlying list.
033: * <p>
034: * This implementation supports all of the optional {@link List} operations.
035: * It extends <code>AbstractLinkedList</code> and thus provides the
036: * stack/queue/dequeue operations available in {@link java.util.LinkedList}.
037: * <p>
038: * The main feature of this class is the ability to modify the list and the
039: * iterator at the same time. Both the {@link #listIterator()} and {@link #cursor()}
040: * methods provides access to a <code>Cursor</code> instance which extends
041: * <code>ListIterator</code>. The cursor allows changes to the list concurrent
042: * with changes to the iterator. Note that the {@link #iterator()} method and
043: * sublists do <b>not</b> provide this cursor behaviour.
044: * <p>
045: * The <code>Cursor</code> class is provided partly for backwards compatibility
046: * and partly because it allows the cursor to be directly closed. Closing the
047: * cursor is optional because references are held via a <code>WeakReference</code>.
048: * For most purposes, simply modify the iterator and list at will, and then let
049: * the garbage collector to the rest.
050: * <p>
051: * <b>Note that this implementation is not synchronized.</b>
052: *
053: * @see java.util.LinkedList
054: * @since Commons Collections 1.0
055: * @version $Revision: 348013 $ $Date: 2005-11-21 23:24:45 +0000 (Mon, 21 Nov 2005) $
056: *
057: * @author Rodney Waldhoff
058: * @author Janek Bogucki
059: * @author Simon Kitching
060: * @author Stephen Colebourne
061: */
062: public class CursorableLinkedList extends AbstractLinkedList implements
063: 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,
374: ClassNotFoundException {
375: in.defaultReadObject();
376: doReadObject(in);
377: }
378:
379: //-----------------------------------------------------------------------
380: /**
381: * Creates a list iterator for the sublist.
382: *
383: * @param subList the sublist to get an iterator for
384: * @param fromIndex the index to start from, relative to the sublist
385: */
386: protected ListIterator createSubListListIterator(
387: LinkedSubList subList, int fromIndex) {
388: SubCursor cursor = new SubCursor(subList, fromIndex);
389: registerCursor(cursor);
390: return cursor;
391: }
392:
393: //-----------------------------------------------------------------------
394: /**
395: * An extended <code>ListIterator</code> that allows concurrent changes to
396: * the underlying list.
397: */
398: public static class Cursor extends
399: AbstractLinkedList.LinkedListIterator {
400: /** Is the cursor valid (not closed) */
401: boolean valid = true;
402: /** Is the next index valid */
403: boolean nextIndexValid = true;
404: /** Flag to indicate if the current element was removed by another object. */
405: boolean currentRemovedByAnother = false;
406:
407: /**
408: * Constructs a new cursor.
409: *
410: * @param index the index to start from
411: */
412: protected Cursor(CursorableLinkedList parent, int index) {
413: super (parent, index);
414: valid = true;
415: }
416:
417: /**
418: * Removes the item last returned by this iterator.
419: * <p>
420: * There may have been subsequent alterations to the list
421: * since you obtained this item, however you can still remove it.
422: * You can even remove it if the item is no longer in the main list.
423: * However, you can't call this method on the same iterator more
424: * than once without calling next() or previous().
425: *
426: * @throws IllegalStateException if there is no item to remove
427: */
428: public void remove() {
429: // overridden, as the nodeRemoved() method updates the iterator
430: // state in the parent.removeNode() call below
431: if (current == null && currentRemovedByAnother) {
432: // quietly ignore, as the last returned node was removed
433: // by the list or some other iterator
434: // by ignoring it, we keep this iterator independent from
435: // other changes as much as possible
436: } else {
437: checkModCount();
438: parent.removeNode(getLastNodeReturned());
439: }
440: currentRemovedByAnother = false;
441: }
442:
443: /**
444: * Adds an object to the list.
445: * The object added here will be the new 'previous' in the iterator.
446: *
447: * @param obj the object to add
448: */
449: public void add(Object obj) {
450: // overridden, as the nodeInserted() method updates the iterator state
451: super .add(obj);
452: // matches the (next.previous == node) clause in nodeInserted()
453: // thus next gets changed - reset it again here
454: next = next.next;
455: }
456:
457: // set is not overridden, as it works ok
458: // note that we want it to throw an exception if the element being
459: // set has been removed from the real list (compare this with the
460: // remove method where we silently ignore this case)
461:
462: /**
463: * Gets the index of the next element to be returned.
464: *
465: * @return the next index
466: */
467: public int nextIndex() {
468: if (nextIndexValid == false) {
469: if (next == parent.header) {
470: nextIndex = parent.size();
471: } else {
472: int pos = 0;
473: Node temp = parent.header.next;
474: while (temp != next) {
475: pos++;
476: temp = temp.next;
477: }
478: nextIndex = pos;
479: }
480: nextIndexValid = true;
481: }
482: return nextIndex;
483: }
484:
485: /**
486: * Handle event from the list when a node has changed.
487: *
488: * @param node the node that changed
489: */
490: protected void nodeChanged(Node node) {
491: // do nothing
492: }
493:
494: /**
495: * Handle event from the list when a node has been removed.
496: *
497: * @param node the node that was removed
498: */
499: protected void nodeRemoved(Node node) {
500: if (node == next && node == current) {
501: // state where next() followed by previous()
502: next = node.next;
503: current = null;
504: currentRemovedByAnother = true;
505: } else if (node == next) {
506: // state where next() not followed by previous()
507: // and we are matching next node
508: next = node.next;
509: currentRemovedByAnother = false;
510: } else if (node == current) {
511: // state where next() not followed by previous()
512: // and we are matching current (last returned) node
513: current = null;
514: currentRemovedByAnother = true;
515: nextIndex--;
516: } else {
517: nextIndexValid = false;
518: currentRemovedByAnother = false;
519: }
520: }
521:
522: /**
523: * Handle event from the list when a node has been added.
524: *
525: * @param node the node that was added
526: */
527: protected void nodeInserted(Node node) {
528: if (node.previous == current) {
529: next = node;
530: } else if (next.previous == node) {
531: next = node;
532: } else {
533: nextIndexValid = false;
534: }
535: }
536:
537: /**
538: * Override superclass modCount check, and replace it with our valid flag.
539: */
540: protected void checkModCount() {
541: if (!valid) {
542: throw new ConcurrentModificationException(
543: "Cursor closed");
544: }
545: }
546:
547: /**
548: * Mark this cursor as no longer being needed. Any resources
549: * associated with this cursor are immediately released.
550: * In previous versions of this class, it was mandatory to close
551: * all cursor objects to avoid memory leaks. It is <i>no longer</i>
552: * necessary to call this close method; an instance of this class
553: * can now be treated exactly like a normal iterator.
554: */
555: public void close() {
556: if (valid) {
557: ((CursorableLinkedList) parent).unregisterCursor(this );
558: valid = false;
559: }
560: }
561: }
562:
563: //-----------------------------------------------------------------------
564: /**
565: * A cursor for the sublist based on LinkedSubListIterator.
566: *
567: * @since Commons Collections 3.2
568: */
569: protected static class SubCursor extends Cursor {
570:
571: /** The parent list */
572: protected final LinkedSubList sub;
573:
574: /**
575: * Constructs a new cursor.
576: *
577: * @param index the index to start from
578: */
579: protected SubCursor(LinkedSubList sub, int index) {
580: super ((CursorableLinkedList) sub.parent, index + sub.offset);
581: this .sub = sub;
582: }
583:
584: public boolean hasNext() {
585: return (nextIndex() < sub.size);
586: }
587:
588: public boolean hasPrevious() {
589: return (previousIndex() >= 0);
590: }
591:
592: public int nextIndex() {
593: return (super .nextIndex() - sub.offset);
594: }
595:
596: public void add(Object obj) {
597: super .add(obj);
598: sub.expectedModCount = parent.modCount;
599: sub.size++;
600: }
601:
602: public void remove() {
603: super.remove();
604: sub.expectedModCount = parent.modCount;
605: sub.size--;
606: }
607: }
608:
609: }
|