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