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