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 */ 017package org.apache.commons.collections4.list; 018 019import java.io.IOException; 020import java.io.ObjectInputStream; 021import java.io.ObjectOutputStream; 022import java.io.Serializable; 023import java.lang.ref.WeakReference; 024import java.util.ArrayList; 025import java.util.Collection; 026import java.util.ConcurrentModificationException; 027import java.util.Iterator; 028import java.util.List; 029import 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 * <p> 040 * The main feature of this class is the ability to modify the list and the 041 * iterator at the same time. Both the {@link #listIterator()} and {@link #cursor()} 042 * methods provides access to a <code>Cursor</code> instance which extends 043 * <code>ListIterator</code>. The cursor allows changes to the list concurrent 044 * with changes to the iterator. Note that the {@link #iterator()} method and 045 * sublists do <b>not</b> provide this cursor behaviour. 046 * </p> 047 * <p> 048 * The <code>Cursor</code> class is provided partly for backwards compatibility 049 * and partly because it allows the cursor to be directly closed. Closing the 050 * cursor is optional because references are held via a <code>WeakReference</code>. 051 * For most purposes, simply modify the iterator and list at will, and then let 052 * the garbage collector to the rest. 053 * </p> 054 * <p> 055 * <b>Note that this implementation is not synchronized.</b> 056 * </p> 057 * 058 * @see java.util.LinkedList 059 * @since 1.0 060 */ 061public class CursorableLinkedList<E> extends AbstractLinkedList<E> implements Serializable { 062 063 /** Ensure serialization compatibility */ 064 private static final long serialVersionUID = 8836393098519411393L; 065 066 /** A list of the cursor currently open on this list */ 067 private transient List<WeakReference<Cursor<E>>> cursors; 068 069 //----------------------------------------------------------------------- 070 /** 071 * Constructor that creates. 072 */ 073 public CursorableLinkedList() { 074 super(); 075 init(); // must call init() as use super(); 076 } 077 078 /** 079 * Constructor that copies the specified collection 080 * 081 * @param coll the collection to copy 082 */ 083 public CursorableLinkedList(final Collection<? extends E> coll) { 084 super(coll); 085 } 086 087 /** 088 * The equivalent of a default constructor called 089 * by any constructor and by <code>readObject</code>. 090 */ 091 @Override 092 protected void init() { 093 super.init(); 094 cursors = new ArrayList<>(); 095 } 096 097 //----------------------------------------------------------------------- 098 /** 099 * 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 @Override 108 public Iterator<E> 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 @Override 128 public ListIterator<E> listIterator() { 129 return cursor(0); 130 } 131 132 /** 133 * Returns a cursor iterator that allows changes to the underlying list in parallel. 134 * <p> 135 * The cursor enables iteration and list changes to occur in any order without 136 * invalidating the iterator (from one thread). When elements are added to the 137 * list, an event is fired to all active cursors enabling them to adjust to the 138 * change in the list. 139 * <p> 140 * When the "current" (i.e., last returned by {@link ListIterator#next} 141 * or {@link ListIterator#previous}) element of the list is removed, 142 * the cursor automatically adjusts to the change (invalidating the 143 * last returned value such that it cannot be removed). 144 * 145 * @param fromIndex the index to start from 146 * @return a new cursor iterator 147 */ 148 @Override 149 public ListIterator<E> listIterator(final int fromIndex) { 150 return cursor(fromIndex); 151 } 152 153 /** 154 * Returns a {@link Cursor} for iterating through the elements of this list. 155 * <p> 156 * A <code>Cursor</code> is a <code>ListIterator</code> with an additional 157 * <code>close()</code> method. Calling this method immediately discards the 158 * references to the cursor. If it is not called, then the garbage collector 159 * will still remove the reference as it is held via a <code>WeakReference</code>. 160 * <p> 161 * The cursor enables iteration and list changes to occur in any order without 162 * invalidating the iterator (from one thread). When elements are added to the 163 * list, an event is fired to all active cursors enabling them to adjust to the 164 * change in the list. 165 * <p> 166 * When the "current" (i.e., last returned by {@link ListIterator#next} 167 * or {@link ListIterator#previous}) element of the list is removed, 168 * the cursor automatically adjusts to the change (invalidating the 169 * last returned value such that it cannot be removed). 170 * <p> 171 * The {@link #listIterator()} method returns the same as this method, and can 172 * be cast to a <code>Cursor</code> if the <code>close</code> method is required. 173 * 174 * @return a new cursor iterator 175 */ 176 public CursorableLinkedList.Cursor<E> cursor() { 177 return cursor(0); 178 } 179 180 /** 181 * Returns a {@link Cursor} for iterating through the elements of this list 182 * starting from a specified index. 183 * <p> 184 * A <code>Cursor</code> is a <code>ListIterator</code> with an additional 185 * <code>close()</code> method. Calling this method immediately discards the 186 * references to the cursor. If it is not called, then the garbage collector 187 * will still remove the reference as it is held via a <code>WeakReference</code>. 188 * <p> 189 * The cursor enables iteration and list changes to occur in any order without 190 * invalidating the iterator (from one thread). When elements are added to the 191 * list, an event is fired to all active cursors enabling them to adjust to the 192 * change in the list. 193 * <p> 194 * When the "current" (i.e., last returned by {@link ListIterator#next} 195 * or {@link ListIterator#previous}) element of the list is removed, 196 * the cursor automatically adjusts to the change (invalidating the 197 * last returned value such that it cannot be removed). 198 * <p> 199 * The {@link #listIterator(int)} method returns the same as this method, and can 200 * be cast to a <code>Cursor</code> if the <code>close</code> method is required. 201 * 202 * @param fromIndex the index to start from 203 * @return a new cursor iterator 204 * @throws IndexOutOfBoundsException if the index is out of range 205 * (index < 0 || index > size()). 206 */ 207 public CursorableLinkedList.Cursor<E> cursor(final int fromIndex) { 208 final Cursor<E> cursor = new Cursor<>(this, fromIndex); 209 registerCursor(cursor); 210 return cursor; 211 } 212 213 //----------------------------------------------------------------------- 214 /** 215 * Updates the node with a new value. 216 * This implementation sets the value on the node. 217 * Subclasses can override this to record the change. 218 * 219 * @param node node to update 220 * @param value new value of the node 221 */ 222 @Override 223 protected void updateNode(final Node<E> node, final E value) { 224 super.updateNode(node, value); 225 broadcastNodeChanged(node); 226 } 227 228 /** 229 * Inserts a new node into the list. 230 * 231 * @param nodeToInsert new node to insert 232 * @param insertBeforeNode node to insert before 233 * @throws NullPointerException if either node is null 234 */ 235 @Override 236 protected void addNode(final Node<E> nodeToInsert, final Node<E> insertBeforeNode) { 237 super.addNode(nodeToInsert, insertBeforeNode); 238 broadcastNodeInserted(nodeToInsert); 239 } 240 241 /** 242 * Removes the specified node from the list. 243 * 244 * @param node the node to remove 245 * @throws NullPointerException if <code>node</code> is null 246 */ 247 @Override 248 protected void removeNode(final Node<E> node) { 249 super.removeNode(node); 250 broadcastNodeRemoved(node); 251 } 252 253 /** 254 * Removes all nodes by iteration. 255 */ 256 @Override 257 protected void removeAllNodes() { 258 if (size() > 0) { 259 // superclass implementation would break all the iterators 260 final Iterator<E> it = iterator(); 261 while (it.hasNext()) { 262 it.next(); 263 it.remove(); 264 } 265 } 266 } 267 268 //----------------------------------------------------------------------- 269 /** 270 * Registers a cursor to be notified of changes to this list. 271 * 272 * @param cursor the cursor to register 273 */ 274 protected void registerCursor(final Cursor<E> cursor) { 275 // We take this opportunity to clean the cursors list 276 // of WeakReference objects to garbage-collected cursors. 277 for (final Iterator<WeakReference<Cursor<E>>> it = cursors.iterator(); it.hasNext();) { 278 final WeakReference<Cursor<E>> ref = it.next(); 279 if (ref.get() == null) { 280 it.remove(); 281 } 282 } 283 cursors.add(new WeakReference<>(cursor)); 284 } 285 286 /** 287 * Deregisters a cursor from the list to be notified of changes. 288 * 289 * @param cursor the cursor to deregister 290 */ 291 protected void unregisterCursor(final Cursor<E> cursor) { 292 for (final Iterator<WeakReference<Cursor<E>>> it = cursors.iterator(); it.hasNext();) { 293 final WeakReference<Cursor<E>> ref = it.next(); 294 final Cursor<E> cur = ref.get(); 295 if (cur == null) { 296 // some other unrelated cursor object has been 297 // garbage-collected; let's take the opportunity to 298 // clean up the cursors list anyway.. 299 it.remove(); 300 } else if (cur == cursor) { 301 ref.clear(); 302 it.remove(); 303 break; 304 } 305 } 306 } 307 308 //----------------------------------------------------------------------- 309 /** 310 * Informs all of my registered cursors that the specified 311 * element was changed. 312 * 313 * @param node the node that was changed 314 */ 315 protected void broadcastNodeChanged(final Node<E> node) { 316 final Iterator<WeakReference<Cursor<E>>> it = cursors.iterator(); 317 while (it.hasNext()) { 318 final WeakReference<Cursor<E>> ref = it.next(); 319 final Cursor<E> cursor = ref.get(); 320 if (cursor == null) { 321 it.remove(); // clean up list 322 } else { 323 cursor.nodeChanged(node); 324 } 325 } 326 } 327 328 /** 329 * Informs all of my registered cursors that the specified 330 * element was just removed from my list. 331 * 332 * @param node the node that was changed 333 */ 334 protected void broadcastNodeRemoved(final Node<E> node) { 335 final Iterator<WeakReference<Cursor<E>>> it = cursors.iterator(); 336 while (it.hasNext()) { 337 final WeakReference<Cursor<E>> ref = it.next(); 338 final Cursor<E> cursor = ref.get(); 339 if (cursor == null) { 340 it.remove(); // clean up list 341 } else { 342 cursor.nodeRemoved(node); 343 } 344 } 345 } 346 347 /** 348 * Informs all of my registered cursors that the specified 349 * element was just added to my list. 350 * 351 * @param node the node that was changed 352 */ 353 protected void broadcastNodeInserted(final Node<E> node) { 354 final Iterator<WeakReference<Cursor<E>>> it = cursors.iterator(); 355 while (it.hasNext()) { 356 final WeakReference<Cursor<E>> ref = it.next(); 357 final Cursor<E> cursor = ref.get(); 358 if (cursor == null) { 359 it.remove(); // clean up list 360 } else { 361 cursor.nodeInserted(node); 362 } 363 } 364 } 365 366 //----------------------------------------------------------------------- 367 /** 368 * Serializes the data held in this object to the stream specified. 369 * 370 * @param out the output stream 371 * @throws IOException if an error occurs while writing to the stream 372 */ 373 private void writeObject(final ObjectOutputStream out) throws IOException { 374 out.defaultWriteObject(); 375 doWriteObject(out); 376 } 377 378 /** 379 * Deserializes the data held in this object to the stream specified. 380 * 381 * @param in the input stream 382 * @throws IOException if an error occurs while reading from the stream 383 * @throws ClassNotFoundException if an object read from the stream can not be loaded 384 */ 385 private void readObject(final ObjectInputStream in) throws IOException, ClassNotFoundException { 386 in.defaultReadObject(); 387 doReadObject(in); 388 } 389 390 //----------------------------------------------------------------------- 391 /** 392 * Creates a list iterator for the sublist. 393 * 394 * @param subList the sublist to get an iterator for 395 * @param fromIndex the index to start from, relative to the sublist 396 * @return the list iterator for the sublist 397 */ 398 @Override 399 protected ListIterator<E> createSubListListIterator(final LinkedSubList<E> subList, final int fromIndex) { 400 final SubCursor<E> cursor = new SubCursor<>(subList, fromIndex); 401 registerCursor(cursor); 402 return cursor; 403 } 404 405 //----------------------------------------------------------------------- 406 /** 407 * An extended <code>ListIterator</code> that allows concurrent changes to 408 * the underlying list. 409 */ 410 public static class Cursor<E> extends AbstractLinkedList.LinkedListIterator<E> { 411 /** Is the cursor valid (not closed) */ 412 boolean valid = true; 413 /** Is the next index valid */ 414 boolean nextIndexValid = true; 415 /** Flag to indicate if the current element was removed by another object. */ 416 boolean currentRemovedByAnother = false; 417 418 /** 419 * Constructs a new cursor. 420 * 421 * @param parent the parent list 422 * @param index the index to start from 423 */ 424 protected Cursor(final CursorableLinkedList<E> parent, final int index) { 425 super(parent, index); 426 valid = true; 427 } 428 429 /** 430 * Removes the item last returned by this iterator. 431 * <p> 432 * There may have been subsequent alterations to the list 433 * since you obtained this item, however you can still remove it. 434 * You can even remove it if the item is no longer in the main list. 435 * However, you can't call this method on the same iterator more 436 * than once without calling next() or previous(). 437 * 438 * @throws IllegalStateException if there is no item to remove 439 */ 440 @Override 441 public void remove() { 442 // overridden, as the nodeRemoved() method updates the iterator 443 // state in the parent.removeNode() call below 444 if (current == null && currentRemovedByAnother) { // NOPMD 445 // quietly ignore, as the last returned node was removed 446 // by the list or some other iterator 447 // by ignoring it, we keep this iterator independent from 448 // other changes as much as possible 449 } else { 450 checkModCount(); 451 parent.removeNode(getLastNodeReturned()); 452 } 453 currentRemovedByAnother = false; 454 } 455 456 /** 457 * Adds an object to the list. 458 * The object added here will be the new 'previous' in the iterator. 459 * 460 * @param obj the object to add 461 */ 462 @Override 463 public void add(final E obj) { 464 // overridden, as the nodeInserted() method updates the iterator state 465 super.add(obj); 466 // matches the (next.previous == node) clause in nodeInserted() 467 // thus next gets changed - reset it again here 468 next = next.next; 469 } 470 471 // set is not overridden, as it works ok 472 // note that we want it to throw an exception if the element being 473 // set has been removed from the real list (compare this with the 474 // remove method where we silently ignore this case) 475 476 /** 477 * Gets the index of the next element to be returned. 478 * 479 * @return the next index 480 */ 481 @Override 482 public int nextIndex() { 483 if (nextIndexValid == false) { 484 if (next == parent.header) { 485 nextIndex = parent.size(); 486 } else { 487 int pos = 0; 488 Node<E> temp = parent.header.next; 489 while (temp != next) { 490 pos++; 491 temp = temp.next; 492 } 493 nextIndex = pos; 494 } 495 nextIndexValid = true; 496 } 497 return nextIndex; 498 } 499 500 /** 501 * Handle event from the list when a node has changed. 502 * 503 * @param node the node that changed 504 */ 505 protected void nodeChanged(final Node<E> node) { 506 // do nothing 507 } 508 509 /** 510 * Handle event from the list when a node has been removed. 511 * 512 * @param node the node that was removed 513 */ 514 protected void nodeRemoved(final Node<E> node) { 515 if (node == next && node == current) { 516 // state where next() followed by previous() 517 next = node.next; 518 current = null; 519 currentRemovedByAnother = true; 520 } else if (node == next) { 521 // state where next() not followed by previous() 522 // and we are matching next node 523 next = node.next; 524 currentRemovedByAnother = false; 525 } else if (node == current) { 526 // state where next() not followed by previous() 527 // and we are matching current (last returned) node 528 current = null; 529 currentRemovedByAnother = true; 530 nextIndex--; 531 } else { 532 nextIndexValid = false; 533 currentRemovedByAnother = false; 534 } 535 } 536 537 /** 538 * Handle event from the list when a node has been added. 539 * 540 * @param node the node that was added 541 */ 542 protected void nodeInserted(final Node<E> node) { 543 if (node.previous == current) { 544 next = node; 545 } else if (next.previous == node) { 546 next = node; 547 } else { 548 nextIndexValid = false; 549 } 550 } 551 552 /** 553 * Override superclass modCount check, and replace it with our valid flag. 554 */ 555 @Override 556 protected void checkModCount() { 557 if (!valid) { 558 throw new ConcurrentModificationException("Cursor closed"); 559 } 560 } 561 562 /** 563 * Mark this cursor as no longer being needed. Any resources 564 * associated with this cursor are immediately released. 565 * In previous versions of this class, it was mandatory to close 566 * all cursor objects to avoid memory leaks. It is <i>no longer</i> 567 * necessary to call this close method; an instance of this class 568 * can now be treated exactly like a normal iterator. 569 */ 570 public void close() { 571 if (valid) { 572 ((CursorableLinkedList<E>) parent).unregisterCursor(this); 573 valid = false; 574 } 575 } 576 } 577 578 //----------------------------------------------------------------------- 579 /** 580 * A cursor for the sublist based on LinkedSubListIterator. 581 * 582 * @since 3.2 583 */ 584 protected static class SubCursor<E> extends Cursor<E> { 585 586 /** The parent list */ 587 protected final LinkedSubList<E> sub; 588 589 /** 590 * Constructs a new cursor. 591 * 592 * @param sub the sub list 593 * @param index the index to start from 594 */ 595 protected SubCursor(final LinkedSubList<E> sub, final int index) { 596 super((CursorableLinkedList<E>) sub.parent, index + sub.offset); 597 this.sub = sub; 598 } 599 600 @Override 601 public boolean hasNext() { 602 return nextIndex() < sub.size; 603 } 604 605 @Override 606 public boolean hasPrevious() { 607 return previousIndex() >= 0; 608 } 609 610 @Override 611 public int nextIndex() { 612 return super.nextIndex() - sub.offset; 613 } 614 615 @Override 616 public void add(final E obj) { 617 super.add(obj); 618 sub.expectedModCount = parent.modCount; 619 sub.size++; 620 } 621 622 @Override 623 public void remove() { 624 super.remove(); 625 sub.expectedModCount = parent.modCount; 626 sub.size--; 627 } 628 } 629 630}