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 }