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 }