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