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