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