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