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