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