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