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