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    }