    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.util.AbstractList;
    020import java.util.ArrayDeque;
    021import java.util.Collection;
    022import java.util.ConcurrentModificationException;
    023import java.util.Deque;
    024import java.util.Iterator;
    025import java.util.ListIterator;
    026import java.util.NoSuchElementException;
    027import java.util.Objects;
    028
    029import org.apache.commons.collections4.CollectionUtils;
    030import org.apache.commons.collections4.OrderedIterator;
    031
    032/**
    033 * A {@code List} implementation that is optimized for fast insertions and
    034 * removals at any index in the list.
    035 * <p>
    036 * This list implementation utilises a tree structure internally to ensure that
    037 * all insertions and removals are O(log n). This provides much faster performance
    038 * than both an {@code ArrayList} and a {@code LinkedList} where elements
    039 * are inserted and removed repeatedly from anywhere in the list.
    040 * </p>
    041 * <p>
    042 * The following relative performance statistics are indicative of this class:
    043 * </p>
    044 * <pre>
    045 *              get  add  insert  iterate  remove
    046 * TreeList       3    5       1       2       1
    047 * ArrayList      1    1      40       1      40
    048 * LinkedList  5800    1     350       2     325
    049 * </pre>
    050 * <p>
    051 * {@code ArrayList} is a good general purpose list implementation.
    052 * It is faster than {@code TreeList} for most operations except inserting
    053 * and removing in the middle of the list. {@code ArrayList} also uses less
    054 * memory as {@code TreeList} uses one object per entry.
    055 * </p>
    056 * <p>
    057 * {@code LinkedList} is rarely a good choice of implementation.
    058 * {@code TreeList} is almost always a good replacement for it, although it
    059 * does use slightly more memory.
    060 * </p>
    061 *
    062 * @param <E> the type of the elements in the list.
    063 * @since 3.1
    064 */
    065public class TreeList<E> extends AbstractList<E> {
    066//    add; toArray; iterator; insert; get; indexOf; remove
    067//    TreeList = 1260;7360;3080;  160;   170;3400;  170;
    068//   ArrayList =  220;1480;1760; 6870;    50;1540; 7200;
    069//  LinkedList =  270;7360;3350;55860;290720;2910;55200;
    070
    071    /**
    072     * Implements an AVLNode which keeps the offset updated.
    073     * <p>
    074     * This node contains the real work.
    075     * TreeList is just there to implement {@link java.util.List}.
    076     * The nodes don't know the index of the object they are holding.  They
    077     * do know however their position relative to their parent node.
    078     * This allows to calculate the index of a node while traversing the tree.
    079     * <p>
    080     * The Faedelung calculation stores a flag for both the left and right child
    081     * to indicate if they are a child (false) or a link as in linked list (true).
    082     */
    083    static class AVLNode<E> {
    084        /** The left child node or the predecessor if {@link #leftIsPrevious}.*/
    085        private AVLNode<E> left;
    086        /** Flag indicating that left reference is not a subtree but the predecessor. */
    087        private boolean leftIsPrevious;
    088        /** The right child node or the successor if {@link #rightIsNext}. */
    089        private AVLNode<E> right;
    090        /** Flag indicating that right reference is not a subtree but the successor. */
    091        private boolean rightIsNext;
    092        /** How many levels of left/right are below this one. */
    093        private int height;
    094        /** The relative position, root holds absolute position. */
    095        private int relativePosition;
    096        /** The stored element. */
    097        private E value;
    098
    099        /**
    100         * Constructs a new AVL tree from a collection.
    101         * <p>
    102         * The collection must be nonempty.
    103         *
    104         * @param coll  a nonempty collection
    105         */
    106        private AVLNode(final Collection<? extends E> coll) {
    107            this(coll.iterator(), 0, coll.size() - 1, 0, null, null);
    108        }
    109
    110        /**
    111         * Constructs a new node with a relative position.
    112         *
    113         * @param relativePosition  the relative position of the node
    114         * @param obj  the value for the node
    115         * @param rightFollower the node with the value following this one
    116         * @param leftFollower the node with the value leading this one
    117         */
    118        private AVLNode(final int relativePosition, final E obj,
    119                        final AVLNode<E> rightFollower, final AVLNode<E> leftFollower) {
    120            this.relativePosition = relativePosition;
    121            value = obj;
    122            rightIsNext = true;
    123            leftIsPrevious = true;
    124            right = rightFollower;
    125            left = leftFollower;
    126        }
    127
    128        /**
    129         * Constructs a new AVL tree from a collection.
    130         * <p>
    131         * This is a recursive helper for {@link #AVLNode(Collection)}. A call
    132         * to this method will construct the subtree for elements {@code start}
    133         * through {@code end} of the collection, assuming the iterator
    134         * {@code e} already points at element {@code start}.
    135         *
    136         * @param iterator  an iterator over the collection, which should already point
    137         *          to the element at index {@code start} within the collection
    138         * @param start  the index of the first element in the collection that
    139         *          should be in this subtree
    140         * @param end  the index of the last element in the collection that
    141         *          should be in this subtree
    142         * @param absolutePositionOfParent  absolute position of this node's
    143         *          parent, or 0 if this node is the root
    144         * @param prev  the {@code AVLNode} corresponding to element (start - 1)
    145         *          of the collection, or null if start is 0
    146         * @param next  the {@code AVLNode} corresponding to element (end + 1)
    147         *          of the collection, or null if end is the last element of the collection
    148         */
    149        private AVLNode(final Iterator<? extends E> iterator, final int start, final int end,
    150                        final int absolutePositionOfParent, final AVLNode<E> prev, final AVLNode<E> next) {
    151            final int mid = start + (end - start) / 2;
    152            if (start < mid) {
    153                left = new AVLNode<>(iterator, start, mid - 1, mid, prev, this);
    154            } else {
    155                leftIsPrevious = true;
    156                left = prev;
    157            }
    158            value = iterator.next();
    159            relativePosition = mid - absolutePositionOfParent;
    160            if (mid < end) {
    161                right = new AVLNode<>(iterator, mid + 1, end, mid, this, next);
    162            } else {
    163                rightIsNext = true;
    164                right = next;
    165            }
    166            recalcHeight();
    167        }
    168
    169        /**
    170         * Appends the elements of another tree list to this tree list by efficiently
    171         * merging the two AVL trees. This operation is destructive to both trees and
    172         * runs in O(log(m + n)) time.
    173         *
    174         * @param otherTree
    175         *            the root of the AVL tree to merge with this one
    176         * @param currentSize
    177         *            the number of elements in this AVL tree
    178         * @return the root of the new, merged AVL tree
    179         */
    180        private AVLNode<E> addAll(AVLNode<E> otherTree, final int currentSize) {
    181            final AVLNode<E> maxNode = max();
    182            final AVLNode<E> otherTreeMin = otherTree.min();
    183
    184            // We need to efficiently merge the two AVL trees while keeping them
    185            // balanced (or nearly balanced). To do this, we take the shorter
    186            // tree and combine it with a similar-height subtree of the taller
    187            // tree. There are two symmetric cases:
    188            //   * this tree is taller, or
    189            //   * otherTree is taller.
    190            if (otherTree.height > height) {
    191                // CASE 1: The other tree is taller than this one. We will thus
    192                // merge this tree into otherTree.
    193
    194                // STEP 1: Remove the maximum element from this tree.
    195                final AVLNode<E> leftSubTree = removeMax();
    196
    197                // STEP 2: Navigate left from the root of otherTree until we
    198                // find a subtree, s, that is no taller than me. (While we are
    199                // navigating left, we store the nodes we encounter in a stack
    200                // so that we can re-balance them in step 4.)
    201                final Deque<AVLNode<E>> sAncestors = new ArrayDeque<>();
    202                AVLNode<E> s = otherTree;
    203                int sAbsolutePosition = s.relativePosition + currentSize;
    204                int sParentAbsolutePosition = 0;
    205                while (s != null && s.height > getHeight(leftSubTree)) {
    206                    sParentAbsolutePosition = sAbsolutePosition;
    207                    sAncestors.push(s);
    208                    s = s.left;
    209                    if (s != null) {
    210                        sAbsolutePosition += s.relativePosition;
    211                    }
    212                }
    213
    214                // STEP 3: Replace s with a newly constructed subtree whose root
    215                // is maxNode, whose left subtree is leftSubTree, and whose right
    216                // subtree is s.
    217                maxNode.setLeft(leftSubTree, null);
    218                maxNode.setRight(s, otherTreeMin);
    219                if (leftSubTree != null) {
    220                    leftSubTree.max().setRight(null, maxNode);
    221                    leftSubTree.relativePosition -= currentSize - 1;
    222                }
    223                if (s != null) {
    224                    s.min().setLeft(null, maxNode);
    225                    s.relativePosition = sAbsolutePosition - currentSize + 1;
    226                }
    227                maxNode.relativePosition = currentSize - 1 - sParentAbsolutePosition;
    228                otherTree.relativePosition += currentSize;
    229
    230                // STEP 4: Re-balance the tree and recalculate the heights of s's ancestors.
    231                s = maxNode;
    232                while (!sAncestors.isEmpty()) {
    233                    final AVLNode<E> sAncestor = sAncestors.pop();
    234                    sAncestor.setLeft(s, null);
    235                    s = sAncestor.balance();
    236                }
    237                return s;
    238            }
    239            otherTree = otherTree.removeMin();
    240
    241            final Deque<AVLNode<E>> sAncestors = new ArrayDeque<>();
    242            AVLNode<E> s = this;
    243            int sAbsolutePosition = s.relativePosition;
    244            int sParentAbsolutePosition = 0;
    245            while (s != null && s.height > getHeight(otherTree)) {
    246                sParentAbsolutePosition = sAbsolutePosition;
    247                sAncestors.push(s);
    248                s = s.right;
    249                if (s != null) {
    250                    sAbsolutePosition += s.relativePosition;
    251                }
    252            }
    253
    254            otherTreeMin.setRight(otherTree, null);
    255            otherTreeMin.setLeft(s, maxNode);
    256            if (otherTree != null) {
    257                otherTree.min().setLeft(null, otherTreeMin);
    258                otherTree.relativePosition++;
    259            }
    260            if (s != null) {
    261                s.max().setRight(null, otherTreeMin);
    262                s.relativePosition = sAbsolutePosition - currentSize;
    263            }
    264            otherTreeMin.relativePosition = currentSize - sParentAbsolutePosition;
    265
    266            s = otherTreeMin;
    267            while (!sAncestors.isEmpty()) {
    268                final AVLNode<E> sAncestor = sAncestors.pop();
    269                sAncestor.setRight(s, null);
    270                s = sAncestor.balance();
    271            }
    272            return s;
    273        }
    274
    275        /**
    276         * Balances according to the AVL algorithm.
    277         */
    278        private AVLNode<E> balance() {
    279            switch (heightRightMinusLeft()) {
    280            case 1:
    281            case 0:
    282            case -1:
    283                return this;
    284            case -2:
    285                if (left.heightRightMinusLeft() > 0) {
    286                    setLeft(left.rotateLeft(), null);
    287                }
    288                return rotateRight();
    289            case 2:
    290                if (right.heightRightMinusLeft() < 0) {
    291                    setRight(right.rotateRight(), null);
    292                }
    293                return rotateLeft();
    294            default:
    295                throw new IllegalStateException("tree inconsistent!");
    296            }
    297        }
    298
    299        /**
    300         * Locate the element with the given index relative to the
    301         * offset of the parent of this node.
    302         */
    303        AVLNode<E> get(final int index) {
    304            final int indexRelativeToMe = index - relativePosition;
    305
    306            if (indexRelativeToMe == 0) {
    307                return this;
    308            }
    309
    310            final AVLNode<E> nextNode = indexRelativeToMe < 0 ? getLeftSubTree() : getRightSubTree();
    311            if (nextNode == null) {
    312                return null;
    313            }
    314            return nextNode.get(indexRelativeToMe);
    315        }
    316
    317        /**
    318         * Returns the height of the node or -1 if the node is null.
    319         */
    320        private int getHeight(final AVLNode<E> node) {
    321            return node == null ? -1 : node.height;
    322        }
    323
    324        /**
    325         * Gets the left node, returning null if it's a faedelung.
    326         */
    327        private AVLNode<E> getLeftSubTree() {
    328            return leftIsPrevious ? null : left;
    329        }
    330
    331        /**
    332         * Gets the relative position.
    333         */
    334        private int getOffset(final AVLNode<E> node) {
    335            if (node == null) {
    336                return 0;
    337            }
    338            return node.relativePosition;
    339        }
    340
    341        /**
    342         * Gets the right node, returning null if it's a faedelung.
    343         */
    344        private AVLNode<E> getRightSubTree() {
    345            return rightIsNext ? null : right;
    346        }
    347
    348        /**
    349         * Gets the value.
    350         *
    351         * @return the value of this node
    352         */
    353        E getValue() {
    354            return value;
    355        }
    356
    357        /**
    358         * Returns the height difference right - left
    359         */
    360        private int heightRightMinusLeft() {
    361            return getHeight(getRightSubTree()) - getHeight(getLeftSubTree());
    362        }
    363
    364        /**
    365         * Locate the index that contains the specified object.
    366         */
    367        int indexOf(final Object object, final int index) {
    368            if (getLeftSubTree() != null) {
    369                final int result = left.indexOf(object, index + left.relativePosition);
    370                if (result != -1) {
    371                    return result;
    372                }
    373            }
    374            if (Objects.equals(value, object)) {
    375                return index;
    376            }
    377            if (getRightSubTree() != null) {
    378                return right.indexOf(object, index + right.relativePosition);
    379            }
    380            return -1;
    381        }
    382
    383        /**
    384         * Inserts a node at the position index.
    385         *
    386         * @param index is the index of the position relative to the position of
    387         * the parent node.
    388         * @param obj is the object to be stored in the position.
    389         */
    390        AVLNode<E> insert(final int index, final E obj) {
    391            final int indexRelativeToMe = index - relativePosition;
    392
    393            if (indexRelativeToMe <= 0) {
    394                return insertOnLeft(indexRelativeToMe, obj);
    395            }
    396            return insertOnRight(indexRelativeToMe, obj);
    397        }
    398
    399        private AVLNode<E> insertOnLeft(final int indexRelativeToMe, final E obj) {
    400            if (getLeftSubTree() == null) {
    401                setLeft(new AVLNode<>(-1, obj, this, left), null);
    402            } else {
    403                setLeft(left.insert(indexRelativeToMe, obj), null);
    404            }
    405
    406            if (relativePosition >= 0) {
    407                relativePosition++;
    408            }
    409            final AVLNode<E> ret = balance();
    410            recalcHeight();
    411            return ret;
    412        }
    413
    414        private AVLNode<E> insertOnRight(final int indexRelativeToMe, final E obj) {
    415            if (getRightSubTree() == null) {
    416                setRight(new AVLNode<>(+1, obj, right, this), null);
    417            } else {
    418                setRight(right.insert(indexRelativeToMe, obj), null);
    419            }
    420            if (relativePosition < 0) {
    421                relativePosition--;
    422            }
    423            final AVLNode<E> ret = balance();
    424            recalcHeight();
    425            return ret;
    426        }
    427
    428        /**
    429         * Gets the rightmost child of this node.
    430         *
    431         * @return the rightmost child (greatest index)
    432         */
    433        private AVLNode<E> max() {
    434            return getRightSubTree() == null ? this : right.max();
    435        }
    436
    437        /**
    438         * Gets the leftmost child of this node.
    439         *
    440         * @return the leftmost child (smallest index)
    441         */
    442        private AVLNode<E> min() {
    443            return getLeftSubTree() == null ? this : left.min();
    444        }
    445
    446        /**
    447         * Gets the next node in the list after this one.
    448         *
    449         * @return the next node
    450         */
    451        AVLNode<E> next() {
    452            if (rightIsNext || right == null) {
    453                return right;
    454            }
    455            return right.min();
    456        }
    457
    458        /**
    459         * Gets the node in the list before this one.
    460         *
    461         * @return the previous node
    462         */
    463        AVLNode<E> previous() {
    464            if (leftIsPrevious || left == null) {
    465                return left;
    466            }
    467            return left.max();
    468        }
    469
    470        /**
    471         * Sets the height by calculation.
    472         */
    473        private void recalcHeight() {
    474            height = Math.max(
    475                getLeftSubTree() == null ? -1 : getLeftSubTree().height,
    476                getRightSubTree() == null ? -1 : getRightSubTree().height) + 1;
    477        }
    478
    479        /**
    480         * Removes the node at a given position.
    481         *
    482         * @param index is the index of the element to be removed relative to the position of
    483         * the parent node of the current node.
    484         */
    485        AVLNode<E> remove(final int index) {
    486            final int indexRelativeToMe = index - relativePosition;
    487
    488            if (indexRelativeToMe == 0) {
    489                return removeSelf();
    490            }
    491            if (indexRelativeToMe > 0) {
    492                setRight(right.remove(indexRelativeToMe), right.right);
    493                if (relativePosition < 0) {
    494                    relativePosition++;
    495                }
    496            } else {
    497                setLeft(left.remove(indexRelativeToMe), left.left);
    498                if (relativePosition > 0) {
    499                    relativePosition--;
    500                }
    501            }
    502            recalcHeight();
    503            return balance();
    504        }
    505
    506        private AVLNode<E> removeMax() {
    507            if (getRightSubTree() == null) {
    508                return removeSelf();
    509            }
    510            setRight(right.removeMax(), right.right);
    511            if (relativePosition < 0) {
    512                relativePosition++;
    513            }
    514            recalcHeight();
    515            return balance();
    516        }
    517
    518        private AVLNode<E> removeMin() {
    519            if (getLeftSubTree() == null) {
    520                return removeSelf();
    521            }
    522            setLeft(left.removeMin(), left.left);
    523            if (relativePosition > 0) {
    524                relativePosition--;
    525            }
    526            recalcHeight();
    527            return balance();
    528        }
    529
    530        /**
    531         * Removes this node from the tree.
    532         *
    533         * @return the node that replaces this one in the parent
    534         */
    535        private AVLNode<E> removeSelf() {
    536            if (getRightSubTree() == null && getLeftSubTree() == null) {
    537                return null;
    538            }
    539            if (getRightSubTree() == null) {
    540                if (relativePosition > 0) {
    541                    left.relativePosition += relativePosition;
    542                }
    543                left.max().setRight(null, right);
    544                return left;
    545            }
    546            if (getLeftSubTree() == null) {
    547                right.relativePosition += relativePosition - (relativePosition < 0 ? 0 : 1);
    548                right.min().setLeft(null, left);
    549                return right;
    550            }
    551
    552            if (heightRightMinusLeft() > 0) {
    553                // more on the right, so delete from the right
    554                final AVLNode<E> rightMin = right.min();
    555                value = rightMin.value;
    556                if (leftIsPrevious) {
    557                    left = rightMin.left;
    558                }
    559                right = right.removeMin();
    560                if (relativePosition < 0) {
    561                    relativePosition++;
    562                }
    563            } else {
    564                // more on the left or equal, so delete from the left
    565                final AVLNode<E> leftMax = left.max();
    566                value = leftMax.value;
    567                if (rightIsNext) {
    568                    right = leftMax.right;
    569                }
    570                final AVLNode<E> leftPrevious = left.left;
    571                left = left.removeMax();
    572                if (left == null) {
    573                    // special case where left that was deleted was a double link
    574                    // only occurs when height difference is equal
    575                    left = leftPrevious;
    576                    leftIsPrevious = true;
    577                }
    578                if (relativePosition > 0) {
    579                    relativePosition--;
    580                }
    581            }
    582            recalcHeight();
    583            return this;
    584        }
    585
    586        private AVLNode<E> rotateLeft() {
    587            final AVLNode<E> newTop = right; // can't be faedelung!
    588            final AVLNode<E> movedNode = getRightSubTree().getLeftSubTree();
    589
    590            final int newTopPosition = relativePosition + getOffset(newTop);
    591            final int myNewPosition = -newTop.relativePosition;
    592            final int movedPosition = getOffset(newTop) + getOffset(movedNode);
    593
    594            setRight(movedNode, newTop);
    595            newTop.setLeft(this, null);
    596
    597            setOffset(newTop, newTopPosition);
    598            setOffset(this, myNewPosition);
    599            setOffset(movedNode, movedPosition);
    600            return newTop;
    601        }
    602
    603        private AVLNode<E> rotateRight() {
    604            final AVLNode<E> newTop = left; // can't be faedelung
    605            final AVLNode<E> movedNode = getLeftSubTree().getRightSubTree();
    606
    607            final int newTopPosition = relativePosition + getOffset(newTop);
    608            final int myNewPosition = -newTop.relativePosition;
    609            final int movedPosition = getOffset(newTop) + getOffset(movedNode);
    610
    611            setLeft(movedNode, newTop);
    612            newTop.setRight(this, null);
    613
    614            setOffset(newTop, newTopPosition);
    615            setOffset(this, myNewPosition);
    616            setOffset(movedNode, movedPosition);
    617            return newTop;
    618        }
    619
    620        /**
    621         * Sets the left field to the node, or the previous node if that is null
    622         *
    623         * @param node  the new left subtree node
    624         * @param previous  the previous node in the linked list
    625         */
    626        private void setLeft(final AVLNode<E> node, final AVLNode<E> previous) {
    627            leftIsPrevious = node == null;
    628            left = leftIsPrevious ? previous : node;
    629            recalcHeight();
    630        }
    631
    632        /**
    633         * Sets the relative position.
    634         */
    635        private int setOffset(final AVLNode<E> node, final int newOffset) {
    636            if (node == null) {
    637                return 0;
    638            }
    639            final int oldOffset = getOffset(node);
    640            node.relativePosition = newOffset;
    641            return oldOffset;
    642        }
    643
    644        /**
    645         * Sets the right field to the node, or the next node if that is null
    646         *
    647         * @param node  the new left subtree node
    648         * @param next  the next node in the linked list
    649         */
    650        private void setRight(final AVLNode<E> node, final AVLNode<E> next) {
    651            rightIsNext = node == null;
    652            right = rightIsNext ? next : node;
    653            recalcHeight();
    654        }
    655
    656        /**
    657         * Sets the value.
    658         *
    659         * @param obj  the value to store
    660         */
    661        void setValue(final E obj) {
    662            this.value = obj;
    663        }
    664
    665        /**
    666         * Stores the node and its children into the array specified.
    667         *
    668         * @param array the array to be filled
    669         * @param index the index of this node
    670         */
    671        void toArray(final Object[] array, final int index) {
    672            array[index] = value;
    673            if (getLeftSubTree() != null) {
    674                left.toArray(array, index + left.relativePosition);
    675            }
    676            if (getRightSubTree() != null) {
    677                right.toArray(array, index + right.relativePosition);
    678            }
    679        }
    680
    681//      private void checkFaedelung() {
    682//          AVLNode maxNode = left.max();
    683//          if (!maxNode.rightIsFaedelung || maxNode.right != this) {
    684//              throw new RuntimeException(maxNode + " should right-faedel to " + this);
    685//          }
    686//          AVLNode minNode = right.min();
    687//          if (!minNode.leftIsFaedelung || minNode.left != this) {
    688//              throw new RuntimeException(maxNode + " should left-faedel to " + this);
    689//          }
    690//      }
    691//
    692//        private int checkTreeDepth() {
    693//            int hright = (getRightSubTree() == null ? -1 : getRightSubTree().checkTreeDepth());
    694//            //          System.out.print("checkTreeDepth");
    695//            //          System.out.print(this);
    696//            //          System.out.print(" left: ");
    697//            //          System.out.print(_left);
    698//            //          System.out.print(" right: ");
    699//            //          System.out.println(_right);
    700//
    701//            int hleft = (left == null ? -1 : left.checkTreeDepth());
    702//            if (height != Math.max(hright, hleft) + 1) {
    703//                throw new RuntimeException(
    704//                    "height should be max" + hleft + "," + hright + " but is " + height);
    705//            }
    706//            return height;
    707//        }
    708//
    709//        private int checkLeftSubNode() {
    710//            if (getLeftSubTree() == null) {
    711//                return 0;
    712//            }
    713//            int count = 1 + left.checkRightSubNode();
    714//            if (left.relativePosition != -count) {
    715//                throw new RuntimeException();
    716//            }
    717//            return count + left.checkLeftSubNode();
    718//        }
    719//
    720//        private int checkRightSubNode() {
    721//            AVLNode right = getRightSubTree();
    722//            if (right == null) {
    723//                return 0;
    724//            }
    725//            int count = 1;
    726//            count += right.checkLeftSubNode();
    727//            if (right.relativePosition != count) {
    728//                throw new RuntimeException();
    729//            }
    730//            return count + right.checkRightSubNode();
    731//        }
    732
    733        /**
    734         * Used for debugging.
    735         */
    736        @Override
    737        public String toString() {
    738            return new StringBuilder()
    739                .append("AVLNode(")
    740                .append(relativePosition)
    741                .append(CollectionUtils.COMMA)
    742                .append(left != null)
    743                .append(CollectionUtils.COMMA)
    744                .append(value)
    745                .append(CollectionUtils.COMMA)
    746                .append(getRightSubTree() != null)
    747                .append(rightIsNext)
    748                .append(")")
    749                .toString();
    750        }
    751    }
    752
    753    /**
    754     * A list iterator over the linked list.
    755     */
    756    static class TreeListIterator<E> implements ListIterator<E>, OrderedIterator<E> {
    757        /** The parent list */
    758        private final TreeList<E> parent;
    759        /**
    760         * Cache of the next node that will be returned by {@link #next()}.
    761         */
    762        private AVLNode<E> next;
    763        /**
    764         * The index of the next node to be returned.
    765         */
    766        private int nextIndex;
    767        /**
    768         * Cache of the last node that was returned by {@link #next()}
    769         * or {@link #previous()}.
    770         */
    771        private AVLNode<E> current;
    772        /**
    773         * The index of the last node that was returned.
    774         */
    775        private int currentIndex;
    776        /**
    777         * The modification count that the list is expected to have. If the list
    778         * doesn't have this count, then a
    779         * {@link java.util.ConcurrentModificationException} may be thrown by
    780         * the operations.
    781         */
    782        private int expectedModCount;
    783
    784        /**
    785         * Create a ListIterator for a list.
    786         *
    787         * @param parent  the parent list
    788         * @param fromIndex  the index to start at
    789         */
    790        protected TreeListIterator(final TreeList<E> parent, final int fromIndex) {
    791            this.parent = parent;
    792            this.expectedModCount = parent.modCount;
    793            this.next = parent.root == null ? null : parent.root.get(fromIndex);
    794            this.nextIndex = fromIndex;
    795            this.currentIndex = -1;
    796        }
    797
    798        @Override
    799        public void add(final E obj) {
    800            checkModCount();
    801            parent.add(nextIndex, obj);
    802            current = null;
    803            currentIndex = -1;
    804            nextIndex++;
    805            expectedModCount++;
    806        }
    807
    808        /**
    809         * Checks the modification count of the list is the value that this
    810         * object expects.
    811         *
    812         * @throws ConcurrentModificationException If the list's modification
    813         * count isn't the value that was expected.
    814         */
    815        protected void checkModCount() {
    816            if (parent.modCount != expectedModCount) {
    817                throw new ConcurrentModificationException();
    818            }
    819        }
    820
    821        @Override
    822        public boolean hasNext() {
    823            return nextIndex < parent.size();
    824        }
    825
    826        @Override
    827        public boolean hasPrevious() {
    828            return nextIndex > 0;
    829        }
    830
    831        @Override
    832        public E next() {
    833            checkModCount();
    834            if (!hasNext()) {
    835                throw new NoSuchElementException("No element at index " + nextIndex + ".");
    836            }
    837            if (next == null) {
    838                next = parent.root.get(nextIndex);
    839            }
    840            final E value = next.getValue();
    841            current = next;
    842            currentIndex = nextIndex++;
    843            next = next.next();
    844            return value;
    845        }
    846
    847        @Override
    848        public int nextIndex() {
    849            return nextIndex;
    850        }
    851
    852        @Override
    853        public E previous() {
    854            checkModCount();
    855            if (!hasPrevious()) {
    856                throw new NoSuchElementException("Already at start of list.");
    857            }
    858            if (next == null) {
    859                next = parent.root.get(nextIndex - 1);
    860            } else {
    861                next = next.previous();
    862            }
    863            final E value = next.getValue();
    864            current = next;
    865            currentIndex = --nextIndex;
    866            return value;
    867        }
    868
    869        @Override
    870        public int previousIndex() {
    871            return nextIndex() - 1;
    872        }
    873
    874        @Override
    875        public void remove() {
    876            checkModCount();
    877            if (currentIndex == -1) {
    878                throw new IllegalStateException();
    879            }
    880            parent.remove(currentIndex);
    881            if (nextIndex != currentIndex) {
    882                // remove() following next()
    883                nextIndex--;
    884            }
    885            // the AVL node referenced by next may have become stale after a remove
    886            // reset it now: will be retrieved by next call to next()/previous() via nextIndex
    887            next = null;
    888            current = null;
    889            currentIndex = -1;
    890            expectedModCount++;
    891        }
    892
    893        @Override
    894        public void set(final E obj) {
    895            checkModCount();
    896            if (current == null) {
    897                throw new IllegalStateException();
    898            }
    899            current.setValue(obj);
    900        }
    901    }
    902
    903    /** The root node in the AVL tree */
    904    private AVLNode<E> root;
    905
    906    /** The current size of the list */
    907    private int size;
    908
    909    /**
    910     * Constructs a new empty list.
    911     */
    912    public TreeList() {
    913    }
    914
    915    /**
    916     * Constructs a new empty list that copies the specified collection.
    917     *
    918     * @param coll  the collection to copy
    919     * @throws NullPointerException if the collection is null
    920     */
    921    public TreeList(final Collection<? extends E> coll) {
    922        if (!coll.isEmpty()) {
    923            root = new AVLNode<>(coll);
    924            size = coll.size();
    925        }
    926    }
    927
    928    /**
    929     * Adds a new element to the list.
    930     *
    931     * @param index  the index to add before
    932     * @param obj  the element to add
    933     */
    934    @Override
    935    public void add(final int index, final E obj) {
    936        modCount++;
    937        checkInterval(index, 0, size());
    938        if (root == null) {
    939            root = new AVLNode<>(index, obj, null, null);
    940        } else {
    941            root = root.insert(index, obj);
    942        }
    943        size++;
    944    }
    945
    946    /**
    947     * Appends all the elements in the specified collection to the end of this list,
    948     * in the order that they are returned by the specified collection's Iterator.
    949     * <p>
    950     * This method runs in O(n + log m) time, where m is
    951     * the size of this list and n is the size of {@code c}.
    952     *
    953     * @param c  the collection to be added to this list
    954     * @return {@code true} if this list changed as a result of the call
    955     * @throws NullPointerException if the specified collection contains a
    956     *         null element and this collection does not permit null elements,
    957     *         or if the specified collection is null
    958     */
    959    @Override
    960    public boolean addAll(final Collection<? extends E> c) {
    961        if (c.isEmpty()) {
    962            return false;
    963        }
    964        modCount += c.size();
    965        final AVLNode<E> cTree = new AVLNode<>(c);
    966        root = root == null ? cTree : root.addAll(cTree, size);
    967        size += c.size();
    968        return true;
    969    }
    970
    971    /**
    972     * Checks whether the index is valid.
    973     *
    974     * @param index  the index to check
    975     * @param startIndex  the first allowed index
    976     * @param endIndex  the last allowed index
    977     * @throws IndexOutOfBoundsException if the index is invalid
    978     */
    979    private void checkInterval(final int index, final int startIndex, final int endIndex) {
    980        if (index < startIndex || index > endIndex) {
    981            throw new IndexOutOfBoundsException("Invalid index:" + index + ", size=" + size());
    982        }
    983    }
    984
    985    /**
    986     * Clears the list, removing all entries.
    987     */
    988    @Override
    989    public void clear() {
    990        modCount++;
    991        root = null;
    992        size = 0;
    993    }
    994
    995    /**
    996     * Searches for the presence of an object in the list.
    997     *
    998     * @param object  the object to check
    999     * @return true if the object is found
    1000     */
    1001    @Override
    1002    public boolean contains(final Object object) {
    1003        return indexOf(object) >= 0;
    1004    }
    1005
    1006    /**
    1007     * Gets the element at the specified index.
    1008     *
    1009     * @param index  the index to retrieve
    1010     * @return the element at the specified index
    1011     */
    1012    @Override
    1013    public E get(final int index) {
    1014        checkInterval(index, 0, size() - 1);
    1015        return root.get(index).getValue();
    1016    }
    1017
    1018    /**
    1019     * Searches for the index of an object in the list.
    1020     *
    1021     * @param object  the object to search
    1022     * @return the index of the object, -1 if not found
    1023     */
    1024    @Override
    1025    public int indexOf(final Object object) {
    1026        // override to go 75% faster
    1027        if (root == null) {
    1028            return -1;
    1029        }
    1030        return root.indexOf(object, root.relativePosition);
    1031    }
    1032
    1033    /**
    1034     * Gets an iterator over the list.
    1035     *
    1036     * @return an iterator over the list
    1037     */
    1038    @Override
    1039    public Iterator<E> iterator() {
    1040        // override to go 75% faster
    1041        return listIterator(0);
    1042    }
    1043
    1044    /**
    1045     * Gets a ListIterator over the list.
    1046     *
    1047     * @return the new iterator
    1048     */
    1049    @Override
    1050    public ListIterator<E> listIterator() {
    1051        // override to go 75% faster
    1052        return listIterator(0);
    1053    }
    1054
    1055    /**
    1056     * Gets a ListIterator over the list.
    1057     *
    1058     * @param fromIndex  the index to start from
    1059     * @return the new iterator
    1060     */
    1061    @Override
    1062    public ListIterator<E> listIterator(final int fromIndex) {
    1063        // override to go 75% faster
    1064        // cannot use EmptyIterator as iterator.add() must work
    1065        checkInterval(fromIndex, 0, size());
    1066        return new TreeListIterator<>(this, fromIndex);
    1067    }
    1068
    1069    /**
    1070     * Removes the element at the specified index.
    1071     *
    1072     * @param index  the index to remove
    1073     * @return the previous object at that index
    1074     */
    1075    @Override
    1076    public E remove(final int index) {
    1077        modCount++;
    1078        checkInterval(index, 0, size() - 1);
    1079        final E result = get(index);
    1080        root = root.remove(index);
    1081        size--;
    1082        return result;
    1083    }
    1084
    1085    /**
    1086     * Sets the element at the specified index.
    1087     *
    1088     * @param index  the index to set
    1089     * @param obj  the object to store at the specified index
    1090     * @return the previous object at that index
    1091     * @throws IndexOutOfBoundsException if the index is invalid
    1092     */
    1093    @Override
    1094    public E set(final int index, final E obj) {
    1095        checkInterval(index, 0, size() - 1);
    1096        final AVLNode<E> node = root.get(index);
    1097        final E result = node.value;
    1098        node.setValue(obj);
    1099        return result;
    1100    }
    1101
    1102    /**
    1103     * Gets the current size of the list.
    1104     *
    1105     * @return the current size
    1106     */
    1107    @Override
    1108    public int size() {
    1109        return size;
    1110    }
    1111
    1112    /**
    1113     * Converts the list into an array.
    1114     *
    1115     * @return the list as an array
    1116     */
    1117    @Override
    1118    public Object[] toArray() {
    1119        // override to go 20% faster
    1120        final Object[] array = new Object[size()];
    1121        if (root != null) {
    1122            root.toArray(array, root.relativePosition);
    1123        }
    1124        return array;
    1125    }
    1126
    1127}