1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.collections4.list;
18
19 import java.util.AbstractList;
20 import java.util.ArrayDeque;
21 import java.util.Collection;
22 import java.util.ConcurrentModificationException;
23 import java.util.Deque;
24 import java.util.Iterator;
25 import java.util.ListIterator;
26 import java.util.NoSuchElementException;
27 import java.util.Objects;
28
29 import org.apache.commons.collections4.CollectionUtils;
30 import org.apache.commons.collections4.OrderedIterator;
31
32 /**
33 * A {@code List} implementation that is optimized for fast insertions and
34 * removals at any index in the list.
35 * <p>
36 * This list implementation utilises a tree structure internally to ensure that
37 * all insertions and removals are O(log n). This provides much faster performance
38 * than both an {@code ArrayList} and a {@code LinkedList} where elements
39 * are inserted and removed repeatedly from anywhere in the list.
40 * </p>
41 * <p>
42 * The following relative performance statistics are indicative of this class:
43 * </p>
44 * <pre>
45 * get add insert iterate remove
46 * TreeList 3 5 1 2 1
47 * ArrayList 1 1 40 1 40
48 * LinkedList 5800 1 350 2 325
49 * </pre>
50 * <p>
51 * {@code ArrayList} is a good general purpose list implementation.
52 * It is faster than {@code TreeList} for most operations except inserting
53 * and removing in the middle of the list. {@code ArrayList} also uses less
54 * memory as {@code TreeList} uses one object per entry.
55 * </p>
56 * <p>
57 * {@code LinkedList} is rarely a good choice of implementation.
58 * {@code TreeList} is almost always a good replacement for it, although it
59 * does use slightly more memory.
60 * </p>
61 *
62 * @since 3.1
63 */
64 public class TreeList<E> extends AbstractList<E> {
65 // add; toArray; iterator; insert; get; indexOf; remove
66 // TreeList = 1260;7360;3080; 160; 170;3400; 170;
67 // ArrayList = 220;1480;1760; 6870; 50;1540; 7200;
68 // LinkedList = 270;7360;3350;55860;290720;2910;55200;
69
70 /**
71 * Implements an AVLNode which keeps the offset updated.
72 * <p>
73 * This node contains the real work.
74 * TreeList is just there to implement {@link java.util.List}.
75 * The nodes don't know the index of the object they are holding. They
76 * do know however their position relative to their parent node.
77 * This allows to calculate the index of a node while traversing the tree.
78 * <p>
79 * The Faedelung calculation stores a flag for both the left and right child
80 * to indicate if they are a child (false) or a link as in linked list (true).
81 */
82 static class AVLNode<E> {
83 /** The left child node or the predecessor if {@link #leftIsPrevious}.*/
84 private AVLNode<E> left;
85 /** Flag indicating that left reference is not a subtree but the predecessor. */
86 private boolean leftIsPrevious;
87 /** The right child node or the successor if {@link #rightIsNext}. */
88 private AVLNode<E> right;
89 /** Flag indicating that right reference is not a subtree but the successor. */
90 private boolean rightIsNext;
91 /** How many levels of left/right are below this one. */
92 private int height;
93 /** The relative position, root holds absolute position. */
94 private int relativePosition;
95 /** The stored element. */
96 private E value;
97
98 /**
99 * 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 }