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