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