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