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