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.lang.reflect.Array; 023import java.util.AbstractList; 024import java.util.Collection; 025import java.util.ConcurrentModificationException; 026import java.util.Iterator; 027import java.util.List; 028import java.util.ListIterator; 029import java.util.NoSuchElementException; 030import java.util.Objects; 031 032import org.apache.commons.collections4.CollectionUtils; 033import org.apache.commons.collections4.OrderedIterator; 034 035/** 036 * An abstract implementation of a linked list which provides numerous points for 037 * subclasses to override. 038 * <p> 039 * Overridable methods are provided to change the storage node and to change how 040 * nodes are added to and removed. Hopefully, all you need for unusual subclasses 041 * is here. 042 * </p> 043 * <p> 044 * This is a copy of AbstractLinkedList, modified to be compatible with Java 21 045 * (see COLLECTIONS-842 for details). 046 * </p> 047 * 048 * @param <E> the type of elements in this list 049 * @see AbstractLinkedList 050 * @since 4.5.0-M3 051 */ 052public abstract class AbstractLinkedListJava21<E> implements List<E> { 053 054 /* 055 * Implementation notes: 056 * - a standard circular doubly-linked list 057 * - a marker node is stored to mark the start and the end of the list 058 * - node creation and removal always occurs through createNode() and 059 * removeNode(). 060 * - a modification count is kept, with the same semantics as 061 * {@link java.util.LinkedList}. 062 * - respects {@link AbstractList#modCount} 063 */ 064 065 /** 066 * A list iterator over the linked list. 067 * 068 * @param <E> the type of elements in this iterator. 069 */ 070 protected static class LinkedListIterator<E> implements ListIterator<E>, OrderedIterator<E> { 071 072 /** The parent list */ 073 protected final AbstractLinkedListJava21<E> parent; 074 075 /** 076 * The node that will be returned by {@link #next()}. If this is equal 077 * to {@link AbstractLinkedListJava21#header} then there are no more values to return. 078 */ 079 protected Node<E> next; 080 081 /** 082 * The index of {@link #next}. 083 */ 084 protected int nextIndex; 085 086 /** 087 * The last node that was returned by {@link #next()} or {@link 088 * #previous()}. Set to {@code null} if {@link #next()} or {@link 089 * #previous()} haven't been called, or if the node has been removed 090 * with {@link #remove()} or a new node added with {@link #add(Object)}. 091 * Should be accessed through {@link #getLastNodeReturned()} to enforce 092 * this behavior. 093 */ 094 protected Node<E> current; 095 096 /** 097 * The modification count that the list is expected to have. If the list 098 * doesn't have this count, then a 099 * {@link java.util.ConcurrentModificationException} may be thrown by 100 * the operations. 101 */ 102 protected int expectedModCount; 103 104 /** 105 * Create a ListIterator for a list. 106 * 107 * @param parent the parent list 108 * @param fromIndex the index to start at 109 * @throws IndexOutOfBoundsException if fromIndex is less than 0 or greater than the size of the list 110 */ 111 protected LinkedListIterator(final AbstractLinkedListJava21<E> parent, final int fromIndex) 112 throws IndexOutOfBoundsException { 113 this.parent = parent; 114 this.expectedModCount = parent.modCount; 115 this.next = parent.getNode(fromIndex, true); 116 this.nextIndex = fromIndex; 117 } 118 119 @Override 120 public void add(final E obj) { 121 checkModCount(); 122 parent.addNodeBefore(next, obj); 123 current = null; 124 nextIndex++; 125 expectedModCount++; 126 } 127 128 /** 129 * Checks the modification count of the list is the value that this 130 * object expects. 131 * 132 * @throws ConcurrentModificationException If the list's modification 133 * count isn't the value that was expected. 134 */ 135 protected void checkModCount() { 136 if (parent.modCount != expectedModCount) { 137 throw new ConcurrentModificationException(); 138 } 139 } 140 141 /** 142 * Gets the last node returned. 143 * 144 * @return the last node returned 145 * @throws IllegalStateException If {@link #next()} or {@link #previous()} haven't been called, 146 * or if the node has been removed with {@link #remove()} or a new node added with {@link #add(Object)}. 147 */ 148 protected Node<E> getLastNodeReturned() throws IllegalStateException { 149 if (current == null) { 150 throw new IllegalStateException(); 151 } 152 return current; 153 } 154 155 @Override 156 public boolean hasNext() { 157 return next != parent.header; 158 } 159 160 @Override 161 public boolean hasPrevious() { 162 return next.previous != parent.header; 163 } 164 165 @Override 166 public E next() { 167 checkModCount(); 168 if (!hasNext()) { 169 throw new NoSuchElementException("No element at index " + nextIndex + "."); 170 } 171 final E value = next.getValue(); 172 current = next; 173 next = next.next; 174 nextIndex++; 175 return value; 176 } 177 178 @Override 179 public int nextIndex() { 180 return nextIndex; 181 } 182 183 @Override 184 public E previous() { 185 checkModCount(); 186 if (!hasPrevious()) { 187 throw new NoSuchElementException("Already at start of list."); 188 } 189 next = next.previous; 190 final E value = next.getValue(); 191 current = next; 192 nextIndex--; 193 return value; 194 } 195 196 @Override 197 public int previousIndex() { 198 // not normally overridden, as relative to nextIndex() 199 return nextIndex() - 1; 200 } 201 202 @Override 203 public void remove() { 204 checkModCount(); 205 if (current == next) { 206 // remove() following previous() 207 next = next.next; 208 parent.removeNode(getLastNodeReturned()); 209 } else { 210 // remove() following next() 211 parent.removeNode(getLastNodeReturned()); 212 nextIndex--; 213 } 214 current = null; 215 expectedModCount++; 216 } 217 218 @Override 219 public void set(final E obj) { 220 checkModCount(); 221 getLastNodeReturned().setValue(obj); 222 } 223 224 } 225 226 /** 227 * The sublist implementation for AbstractLinkedListJava21. 228 * 229 * @param <E> the type of elements in this list. 230 */ 231 protected static class LinkedSubList<E> extends AbstractList<E> { 232 /** The main list */ 233 AbstractLinkedListJava21<E> parent; 234 /** Offset from the main list */ 235 int offset; 236 /** Sublist size */ 237 int size; 238 /** Sublist modCount */ 239 int expectedModCount; 240 241 /** 242 * Constructs a new instance. 243 * 244 * @param parent The parent AbstractLinkedList. 245 * @param fromIndex An index greater or equal to 0 and less than {@code toIndex}. 246 * @param toIndex An index greater than {@code fromIndex}. 247 */ 248 protected LinkedSubList(final AbstractLinkedListJava21<E> parent, final int fromIndex, final int toIndex) { 249 if (fromIndex < 0) { 250 throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); 251 } 252 if (toIndex > parent.size()) { 253 throw new IndexOutOfBoundsException("toIndex = " + toIndex); 254 } 255 if (fromIndex > toIndex) { 256 throw new IllegalArgumentException("fromIndex(" + fromIndex + ") > toIndex(" + toIndex + ")"); 257 } 258 this.parent = parent; 259 this.offset = fromIndex; 260 this.size = toIndex - fromIndex; 261 this.expectedModCount = parent.modCount; 262 } 263 264 @Override 265 public void add(final int index, final E obj) { 266 rangeCheck(index, size + 1); 267 checkModCount(); 268 parent.add(index + offset, obj); 269 expectedModCount = parent.modCount; 270 size++; 271 modCount++; 272 } 273 274 @Override 275 public boolean addAll(final Collection<? extends E> coll) { 276 return addAll(size, coll); 277 } 278 279 @Override 280 public boolean addAll(final int index, final Collection<? extends E> coll) { 281 rangeCheck(index, size + 1); 282 final int cSize = coll.size(); 283 if (cSize == 0) { 284 return false; 285 } 286 287 checkModCount(); 288 parent.addAll(offset + index, coll); 289 expectedModCount = parent.modCount; 290 size += cSize; 291 modCount++; 292 return true; 293 } 294 295 /** 296 * Throws a {@link ConcurrentModificationException} if this instance fails its concurrency check. 297 */ 298 protected void checkModCount() { 299 if (parent.modCount != expectedModCount) { 300 throw new ConcurrentModificationException(); 301 } 302 } 303 304 @Override 305 public void clear() { 306 checkModCount(); 307 final Iterator<E> it = iterator(); 308 while (it.hasNext()) { 309 it.next(); 310 it.remove(); 311 } 312 } 313 314 @Override 315 public E get(final int index) { 316 rangeCheck(index, size); 317 checkModCount(); 318 return parent.get(index + offset); 319 } 320 321 @Override 322 public Iterator<E> iterator() { 323 checkModCount(); 324 return parent.createSubListIterator(this); 325 } 326 327 @Override 328 public ListIterator<E> listIterator(final int index) { 329 rangeCheck(index, size + 1); 330 checkModCount(); 331 return parent.createSubListListIterator(this, index); 332 } 333 334 /** 335 * Throws an {@link IndexOutOfBoundsException} if the given indices are out of bounds. 336 * 337 * @param index lower index. 338 * @param beyond upper index. 339 */ 340 protected void rangeCheck(final int index, final int beyond) { 341 if (index < 0 || index >= beyond) { 342 throw new IndexOutOfBoundsException("Index '" + index + "' out of bounds for size '" + size + "'"); 343 } 344 } 345 346 @Override 347 public E remove(final int index) { 348 rangeCheck(index, size); 349 checkModCount(); 350 final E result = parent.remove(index + offset); 351 expectedModCount = parent.modCount; 352 size--; 353 modCount++; 354 return result; 355 } 356 357 @Override 358 public E set(final int index, final E obj) { 359 rangeCheck(index, size); 360 checkModCount(); 361 return parent.set(index + offset, obj); 362 } 363 364 @Override 365 public int size() { 366 checkModCount(); 367 return size; 368 } 369 370 @Override 371 public List<E> subList(final int fromIndexInclusive, final int toIndexExclusive) { 372 return new LinkedSubList<>(parent, fromIndexInclusive + offset, toIndexExclusive + offset); 373 } 374 } 375 376 /** 377 * A list iterator over the linked sub list. 378 * 379 * @param <E> the type of elements in this iterator. 380 */ 381 protected static class LinkedSubListIterator<E> extends LinkedListIterator<E> { 382 383 /** The sub list */ 384 protected final LinkedSubList<E> sub; 385 386 /** 387 * Constructs a new instance. 388 * 389 * @param sub The sub-list. 390 * @param startIndex The starting index. 391 */ 392 protected LinkedSubListIterator(final LinkedSubList<E> sub, final int startIndex) { 393 super(sub.parent, startIndex + sub.offset); 394 this.sub = sub; 395 } 396 397 @Override 398 public void add(final E obj) { 399 super.add(obj); 400 sub.expectedModCount = parent.modCount; 401 sub.size++; 402 } 403 404 @Override 405 public boolean hasNext() { 406 return nextIndex() < sub.size; 407 } 408 409 @Override 410 public boolean hasPrevious() { 411 return previousIndex() >= 0; 412 } 413 414 @Override 415 public int nextIndex() { 416 return super.nextIndex() - sub.offset; 417 } 418 419 @Override 420 public void remove() { 421 super.remove(); 422 sub.expectedModCount = parent.modCount; 423 sub.size--; 424 } 425 } 426 427 /** 428 * A node within the linked list. 429 * <p> 430 * From Commons Collections 3.1, all access to the {@code value} property 431 * is via the methods on this class. 432 * </p> 433 * 434 * @param <E> the type of the node value. 435 */ 436 protected static class Node<E> { 437 438 /** A pointer to the node before this node */ 439 protected Node<E> previous; 440 /** A pointer to the node after this node */ 441 protected Node<E> next; 442 /** The object contained within this node */ 443 protected E value; 444 445 /** 446 * Constructs a new header node. 447 */ 448 protected Node() { 449 previous = this; 450 next = this; 451 } 452 453 /** 454 * Constructs a new node. 455 * 456 * @param value the value to store 457 */ 458 protected Node(final E value) { 459 this.value = value; 460 } 461 462 /** 463 * Constructs a new node. 464 * 465 * @param previous the previous node in the list 466 * @param next the next node in the list 467 * @param value the value to store 468 */ 469 protected Node(final Node<E> previous, final Node<E> next, final E value) { 470 this.previous = previous; 471 this.next = next; 472 this.value = value; 473 } 474 475 /** 476 * Gets the next node. 477 * 478 * @return the next node 479 * @since 3.1 480 */ 481 protected Node<E> getNextNode() { 482 return next; 483 } 484 485 /** 486 * Gets the previous node. 487 * 488 * @return the previous node 489 * @since 3.1 490 */ 491 protected Node<E> getPreviousNode() { 492 return previous; 493 } 494 495 /** 496 * Gets the value of the node. 497 * 498 * @return the value 499 * @since 3.1 500 */ 501 protected E getValue() { 502 return value; 503 } 504 505 /** 506 * Sets the next node. 507 * 508 * @param next the next node 509 * @since 3.1 510 */ 511 protected void setNextNode(final Node<E> next) { 512 this.next = next; 513 } 514 515 /** 516 * Sets the previous node. 517 * 518 * @param previous the previous node 519 * @since 3.1 520 */ 521 protected void setPreviousNode(final Node<E> previous) { 522 this.previous = previous; 523 } 524 525 /** 526 * Sets the value of the node. 527 * 528 * @param value the value 529 * @since 3.1 530 */ 531 protected void setValue(final E value) { 532 this.value = value; 533 } 534 } 535 536 /** 537 * A {@link Node} which indicates the start and end of the list and does not 538 * hold a value. The value of {@code next} is the first item in the 539 * list. The value of {@code previous} is the last item in the list. 540 */ 541 transient Node<E> header; 542 543 /** The size of the list */ 544 transient int size; 545 546 /** Modification count for iterators */ 547 transient int modCount; 548 549 /** 550 * Constructor that does nothing (intended for deserialization). 551 * <p> 552 * If this constructor is used by a serializable subclass then the init() 553 * method must be called. 554 * </p> 555 */ 556 protected AbstractLinkedListJava21() { 557 } 558 559 /** 560 * Constructs a list copying data from the specified collection. 561 * 562 * @param coll the collection to copy 563 */ 564 protected AbstractLinkedListJava21(final Collection<? extends E> coll) { 565 init(); 566 addAll(coll); 567 } 568 569 @Override 570 public boolean add(final E value) { 571 addLast(value); 572 return true; 573 } 574 575 @Override 576 public void add(final int index, final E value) { 577 final Node<E> node = getNode(index, true); 578 addNodeBefore(node, value); 579 } 580 581 @Override 582 public boolean addAll(final Collection<? extends E> coll) { 583 return addAll(size, coll); 584 } 585 586 @Override 587 public boolean addAll(final int index, final Collection<? extends E> coll) { 588 final Node<E> node = getNode(index, true); 589 for (final E e : coll) { 590 addNodeBefore(node, e); 591 } 592 return true; 593 } 594 595 /** 596 * {@inheritDoc} 597 */ 598 public void addFirst(final E o) { 599 addNodeAfter(header, o); 600 } 601 602 /** 603 * {@inheritDoc} 604 */ 605 public void addLast(final E o) { 606 addNodeBefore(header, o); 607 } 608 609 /** 610 * Inserts a new node into the list. 611 * 612 * @param nodeToInsert new node to insert 613 * @param insertBeforeNode node to insert before 614 * @throws NullPointerException if either node is null 615 */ 616 protected void addNode(final Node<E> nodeToInsert, final Node<E> insertBeforeNode) { 617 Objects.requireNonNull(nodeToInsert, "nodeToInsert"); 618 Objects.requireNonNull(insertBeforeNode, "insertBeforeNode"); 619 nodeToInsert.next = insertBeforeNode; 620 nodeToInsert.previous = insertBeforeNode.previous; 621 insertBeforeNode.previous.next = nodeToInsert; 622 insertBeforeNode.previous = nodeToInsert; 623 size++; 624 modCount++; 625 } 626 627 /** 628 * Creates a new node with the specified object as its 629 * {@code value} and inserts it after {@code node}. 630 * <p> 631 * This implementation uses {@link #createNode(Object)} and 632 * {@link #addNode(AbstractLinkedListJava21.Node,AbstractLinkedListJava21.Node)}. 633 * </p> 634 * 635 * @param node node to insert after 636 * @param value value of the newly added node 637 * @throws NullPointerException if {@code node} is null 638 */ 639 protected void addNodeAfter(final Node<E> node, final E value) { 640 final Node<E> newNode = createNode(value); 641 addNode(newNode, node.next); 642 } 643 644 /** 645 * Creates a new node with the specified object as its 646 * {@code value} and inserts it before {@code node}. 647 * <p> 648 * This implementation uses {@link #createNode(Object)} and 649 * {@link #addNode(AbstractLinkedListJava21.Node,AbstractLinkedListJava21.Node)}. 650 * </p> 651 * 652 * @param node node to insert before 653 * @param value value of the newly added node 654 * @throws NullPointerException if {@code node} is null 655 */ 656 protected void addNodeBefore(final Node<E> node, final E value) { 657 final Node<E> newNode = createNode(value); 658 addNode(newNode, node); 659 } 660 661 @Override 662 public void clear() { 663 removeAllNodes(); 664 } 665 666 @Override 667 public boolean contains(final Object value) { 668 return indexOf(value) != -1; 669 } 670 671 @Override 672 public boolean containsAll(final Collection<?> coll) { 673 for (final Object o : coll) { 674 if (!contains(o)) { 675 return false; 676 } 677 } 678 return true; 679 } 680 681 /** 682 * Creates a new node with previous, next and element all set to null. 683 * This implementation creates a new empty Node. 684 * Subclasses can override this to create a different class. 685 * 686 * @return newly created node 687 */ 688 protected Node<E> createHeaderNode() { 689 return new Node<>(); 690 } 691 692 /** 693 * Creates a new node with the specified properties. 694 * This implementation creates a new Node with data. 695 * Subclasses can override this to create a different class. 696 * 697 * @param value value of the new node 698 * @return a new node containing the value 699 */ 700 protected Node<E> createNode(final E value) { 701 return new Node<>(value); 702 } 703 704 /** 705 * Creates an iterator for the sublist. 706 * 707 * @param subList the sublist to get an iterator for 708 * @return a new iterator on the given sublist 709 */ 710 protected Iterator<E> createSubListIterator(final LinkedSubList<E> subList) { 711 return createSubListListIterator(subList, 0); 712 } 713 714 /** 715 * Creates a list iterator for the sublist. 716 * 717 * @param subList the sublist to get an iterator for 718 * @param fromIndex the index to start from, relative to the sublist 719 * @return a new list iterator on the given sublist 720 */ 721 protected ListIterator<E> createSubListListIterator(final LinkedSubList<E> subList, final int fromIndex) { 722 return new LinkedSubListIterator<>(subList, fromIndex); 723 } 724 725 /** 726 * Deserializes the data held in this object to the stream specified. 727 * <p> 728 * The first serializable subclass must call this method from 729 * {@code readObject}. 730 * </p> 731 * 732 * @param inputStream the stream to read the object from 733 * @throws IOException if any error occurs while reading from the stream 734 * @throws ClassNotFoundException if a class read from the stream cannot be loaded 735 */ 736 @SuppressWarnings("unchecked") 737 protected void doReadObject(final ObjectInputStream inputStream) throws IOException, ClassNotFoundException { 738 init(); 739 final int size = inputStream.readInt(); 740 for (int i = 0; i < size; i++) { 741 add((E) inputStream.readObject()); 742 } 743 } 744 745 /** 746 * Serializes the data held in this object to the stream specified. 747 * <p> 748 * The first serializable subclass must call this method from 749 * {@code writeObject}. 750 * </p> 751 * 752 * @param outputStream the stream to write the object to 753 * @throws IOException if anything goes wrong 754 */ 755 protected void doWriteObject(final ObjectOutputStream outputStream) throws IOException { 756 // Write the size so we know how many nodes to read back 757 outputStream.writeInt(size()); 758 for (final E e : this) { 759 outputStream.writeObject(e); 760 } 761 } 762 763 @Override 764 public boolean equals(final Object obj) { 765 if (obj == this) { 766 return true; 767 } 768 if (!(obj instanceof List)) { 769 return false; 770 } 771 final List<?> other = (List<?>) obj; 772 if (other.size() != size()) { 773 return false; 774 } 775 final ListIterator<?> it1 = listIterator(); 776 final ListIterator<?> it2 = other.listIterator(); 777 while (it1.hasNext() && it2.hasNext()) { 778 if (!Objects.equals(it1.next(), it2.next())) { 779 return false; 780 } 781 } 782 return !(it1.hasNext() || it2.hasNext()); 783 } 784 785 @Override 786 public E get(final int index) { 787 final Node<E> node = getNode(index, false); 788 return node.getValue(); 789 } 790 791 /** 792 * {@inheritDoc} 793 */ 794 public E getFirst() { 795 final Node<E> node = header.next; 796 if (node == header) { 797 throw new NoSuchElementException(); 798 } 799 return node.getValue(); 800 } 801 802 /** 803 * {@inheritDoc} 804 */ 805 public E getLast() { 806 final Node<E> node = header.previous; 807 if (node == header) { 808 throw new NoSuchElementException(); 809 } 810 return node.getValue(); 811 } 812 813 /** 814 * Gets the node at a particular index. 815 * 816 * @param index the index, starting from 0 817 * @param endMarkerAllowed whether or not the end marker can be returned if 818 * startIndex is set to the list's size 819 * @return the node at the given index 820 * @throws IndexOutOfBoundsException if the index is less than 0; equal to 821 * the size of the list and endMakerAllowed is false; or greater than the 822 * size of the list 823 */ 824 protected Node<E> getNode(final int index, final boolean endMarkerAllowed) throws IndexOutOfBoundsException { 825 // Check the index is within the bounds 826 if (index < 0) { 827 throw new IndexOutOfBoundsException("Couldn't get the node: " + 828 "index (" + index + ") less than zero."); 829 } 830 if (!endMarkerAllowed && index == size) { 831 throw new IndexOutOfBoundsException("Couldn't get the node: " + 832 "index (" + index + ") is the size of the list."); 833 } 834 if (index > size) { 835 throw new IndexOutOfBoundsException("Couldn't get the node: " + 836 "index (" + index + ") greater than the size of the " + 837 "list (" + size + ")."); 838 } 839 // Search the list and get the node 840 Node<E> node; 841 if (index < size / 2) { 842 // Search forwards 843 node = header.next; 844 for (int currentIndex = 0; currentIndex < index; currentIndex++) { 845 node = node.next; 846 } 847 } else { 848 // Search backwards 849 node = header; 850 for (int currentIndex = size; currentIndex > index; currentIndex--) { 851 node = node.previous; 852 } 853 } 854 return node; 855 } 856 857 @Override 858 public int hashCode() { 859 int hashCode = 1; 860 for (final E e : this) { 861 hashCode = 31 * hashCode + (e == null ? 0 : e.hashCode()); 862 } 863 return hashCode; 864 } 865 866 @Override 867 public int indexOf(final Object value) { 868 int i = 0; 869 for (Node<E> node = header.next; node != header; node = node.next) { 870 if (isEqualValue(node.getValue(), value)) { 871 return i; 872 } 873 i++; 874 } 875 return CollectionUtils.INDEX_NOT_FOUND; 876 } 877 878 /** 879 * The equivalent of a default constructor, broken out so it can be called 880 * by any constructor and by {@code readObject}. 881 * Subclasses which override this method should make sure they call super, 882 * so the list is initialized properly. 883 */ 884 protected void init() { 885 header = createHeaderNode(); 886 } 887 888 @Override 889 public boolean isEmpty() { 890 return size() == 0; 891 } 892 893 /** 894 * Compares two values for equals. 895 * This implementation uses the equals method. 896 * Subclasses can override this to match differently. 897 * 898 * @param value1 the first value to compare, may be null 899 * @param value2 the second value to compare, may be null 900 * @return true if equal 901 */ 902 protected boolean isEqualValue(final Object value1, final Object value2) { 903 return Objects.equals(value1, value2); 904 } 905 906 @Override 907 public Iterator<E> iterator() { 908 return listIterator(); 909 } 910 911 @Override 912 public int lastIndexOf(final Object value) { 913 int i = size - 1; 914 for (Node<E> node = header.previous; node != header; node = node.previous) { 915 if (isEqualValue(node.getValue(), value)) { 916 return i; 917 } 918 i--; 919 } 920 return CollectionUtils.INDEX_NOT_FOUND; 921 } 922 923 @Override 924 public ListIterator<E> listIterator() { 925 return new LinkedListIterator<>(this, 0); 926 } 927 928 @Override 929 public ListIterator<E> listIterator(final int fromIndex) { 930 return new LinkedListIterator<>(this, fromIndex); 931 } 932 933 @Override 934 public E remove(final int index) { 935 final Node<E> node = getNode(index, false); 936 final E oldValue = node.getValue(); 937 removeNode(node); 938 return oldValue; 939 } 940 941 @Override 942 public boolean remove(final Object value) { 943 for (Node<E> node = header.next; node != header; node = node.next) { 944 if (isEqualValue(node.getValue(), value)) { 945 removeNode(node); 946 return true; 947 } 948 } 949 return false; 950 } 951 952 /** 953 * {@inheritDoc} 954 * <p> 955 * This implementation iterates over the elements of this list, checking each element in 956 * turn to see if it's contained in {@code coll}. If it's contained, it's removed 957 * from this list. As a consequence, it is advised to use a collection type for 958 * {@code coll} that provides a fast (for example O(1)) implementation of 959 * {@link Collection#contains(Object)}. 960 * </p> 961 */ 962 @Override 963 public boolean removeAll(final Collection<?> coll) { 964 boolean modified = false; 965 final Iterator<E> it = iterator(); 966 while (it.hasNext()) { 967 if (coll.contains(it.next())) { 968 it.remove(); 969 modified = true; 970 } 971 } 972 return modified; 973 } 974 975 /** 976 * Removes all nodes by resetting the circular list marker. 977 */ 978 protected void removeAllNodes() { 979 header.next = header; 980 header.previous = header; 981 size = 0; 982 modCount++; 983 } 984 985 /** 986 * {@inheritDoc} 987 */ 988 public E removeFirst() { 989 final Node<E> node = header.next; 990 if (node == header) { 991 throw new NoSuchElementException(); 992 } 993 final E oldValue = node.getValue(); 994 removeNode(node); 995 return oldValue; 996 } 997 998 /** 999 * {@inheritDoc} 1000 */ 1001 public E removeLast() { 1002 final Node<E> node = header.previous; 1003 if (node == header) { 1004 throw new NoSuchElementException(); 1005 } 1006 final E oldValue = node.getValue(); 1007 removeNode(node); 1008 return oldValue; 1009 } 1010 1011 /** 1012 * Removes the specified node from the list. 1013 * 1014 * @param node the node to remove 1015 * @throws NullPointerException if {@code node} is null 1016 */ 1017 protected void removeNode(final Node<E> node) { 1018 Objects.requireNonNull(node, "node"); 1019 node.previous.next = node.next; 1020 node.next.previous = node.previous; 1021 size--; 1022 modCount++; 1023 } 1024 1025 /** 1026 * {@inheritDoc} 1027 * <p> 1028 * This implementation iterates over the elements of this list, checking each element in 1029 * turn to see if it's contained in {@code coll}. If it's not contained, it's removed 1030 * from this list. As a consequence, it is advised to use a collection type for 1031 * {@code coll} that provides a fast (for example O(1)) implementation of 1032 * {@link Collection#contains(Object)}. 1033 * </p> 1034 */ 1035 @Override 1036 public boolean retainAll(final Collection<?> coll) { 1037 boolean modified = false; 1038 final Iterator<E> it = iterator(); 1039 while (it.hasNext()) { 1040 if (!coll.contains(it.next())) { 1041 it.remove(); 1042 modified = true; 1043 } 1044 } 1045 return modified; 1046 } 1047 1048 @Override 1049 public E set(final int index, final E value) { 1050 final Node<E> node = getNode(index, false); 1051 final E oldValue = node.getValue(); 1052 updateNode(node, value); 1053 return oldValue; 1054 } 1055 1056 @Override 1057 public int size() { 1058 return size; 1059 } 1060 1061 /** 1062 * Gets a sublist of the main list. 1063 * 1064 * @param fromIndexInclusive the index to start from 1065 * @param toIndexExclusive the index to end at 1066 * @return the new sublist 1067 */ 1068 @Override 1069 public List<E> subList(final int fromIndexInclusive, final int toIndexExclusive) { 1070 return new LinkedSubList<>(this, fromIndexInclusive, toIndexExclusive); 1071 } 1072 1073 @Override 1074 public Object[] toArray() { 1075 return toArray(new Object[size]); 1076 } 1077 1078 @Override 1079 @SuppressWarnings("unchecked") 1080 public <T> T[] toArray(T[] array) { 1081 // Extend the array if needed 1082 if (array.length < size) { 1083 final Class<?> componentType = array.getClass().getComponentType(); 1084 array = (T[]) Array.newInstance(componentType, size); 1085 } 1086 // Copy the values into the array 1087 int i = 0; 1088 for (Node<E> node = header.next; node != header; node = node.next, i++) { 1089 array[i] = (T) node.getValue(); 1090 } 1091 // Set the value after the last value to null 1092 if (array.length > size) { 1093 array[size] = null; 1094 } 1095 return array; 1096 } 1097 1098 @Override 1099 public String toString() { 1100 if (isEmpty()) { 1101 return "[]"; 1102 } 1103 final StringBuilder buf = new StringBuilder(16 * size()); 1104 buf.append(CollectionUtils.DEFAULT_TOSTRING_PREFIX); 1105 1106 final Iterator<E> it = iterator(); 1107 boolean hasNext = it.hasNext(); 1108 while (hasNext) { 1109 final Object value = it.next(); 1110 buf.append(value == this ? "(this Collection)" : value); 1111 hasNext = it.hasNext(); 1112 if (hasNext) { 1113 buf.append(", "); 1114 } 1115 } 1116 buf.append(CollectionUtils.DEFAULT_TOSTRING_SUFFIX); 1117 return buf.toString(); 1118 } 1119 1120 /** 1121 * Updates the node with a new value. 1122 * This implementation sets the value on the node. 1123 * Subclasses can override this to record the change. 1124 * 1125 * @param node node to update 1126 * @param value new value of the node 1127 */ 1128 protected void updateNode(final Node<E> node, final E value) { 1129 node.setValue(value); 1130 } 1131 1132}