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.collections.list;
18
19 import java.util.AbstractList;
20 import java.util.Collection;
21 import java.util.ConcurrentModificationException;
22 import java.util.Iterator;
23 import java.util.ListIterator;
24 import java.util.NoSuchElementException;
25
26 import org.apache.commons.collections.OrderedIterator;
27
28 /**
29 * A <code>List</code> implementation that is optimised for fast insertions and
30 * removals at any index in the list.
31 * <p>
32 * This list implementation utilises a tree structure internally to ensure that
33 * all insertions and removals are O(log n). This provides much faster performance
34 * than both an <code>ArrayList</code> and a <code>LinkedList</code> where elements
35 * are inserted and removed repeatedly from anywhere in the list.
36 * <p>
37 * The following relative performance statistics are indicative of this class:
38 * <pre>
39 * get add insert iterate remove
40 * TreeList 3 5 1 2 1
41 * ArrayList 1 1 40 1 40
42 * LinkedList 5800 1 350 2 325
43 * </pre>
44 * <code>ArrayList</code> is a good general purpose list implementation.
45 * It is faster than <code>TreeList</code> for most operations except inserting
46 * and removing in the middle of the list. <code>ArrayList</code> also uses less
47 * memory as <code>TreeList</code> uses one object per entry.
48 * <p>
49 * <code>LinkedList</code> is rarely a good choice of implementation.
50 * <code>TreeList</code> is almost always a good replacement for it, although it
51 * does use slightly more memory.
52 *
53 * @since 3.1
54 * @version $Id: TreeList.java 1443602 2013-02-07 17:00:23Z tn $
55 */
56 public class TreeList<E> extends AbstractList<E> {
57 // add; toArray; iterator; insert; get; indexOf; remove
58 // TreeList = 1260;7360;3080; 160; 170;3400; 170;
59 // ArrayList = 220;1480;1760; 6870; 50;1540; 7200;
60 // LinkedList = 270;7360;3350;55860;290720;2910;55200;
61
62 /** The root node in the AVL tree */
63 private AVLNode<E> root;
64
65 /** The current size of the list */
66 private int size;
67
68 //-----------------------------------------------------------------------
69 /**
70 * Constructs a new empty list.
71 */
72 public TreeList() {
73 super();
74 }
75
76 /**
77 * Constructs a new empty list that copies the specified list.
78 *
79 * @param coll the collection to copy
80 * @throws NullPointerException if the collection is null
81 */
82 public TreeList(final Collection<E> coll) {
83 super();
84 addAll(coll);
85 }
86
87 //-----------------------------------------------------------------------
88 /**
89 * Gets the element at the specified index.
90 *
91 * @param index the index to retrieve
92 * @return the element at the specified index
93 */
94 @Override
95 public E get(final int index) {
96 checkInterval(index, 0, size() - 1);
97 return root.get(index).getValue();
98 }
99
100 /**
101 * Gets the current size of the list.
102 *
103 * @return the current size
104 */
105 @Override
106 public int size() {
107 return size;
108 }
109
110 /**
111 * Gets an iterator over the list.
112 *
113 * @return an iterator over the list
114 */
115 @Override
116 public Iterator<E> iterator() {
117 // override to go 75% faster
118 return listIterator(0);
119 }
120
121 /**
122 * Gets a ListIterator over the list.
123 *
124 * @return the new iterator
125 */
126 @Override
127 public ListIterator<E> listIterator() {
128 // override to go 75% faster
129 return listIterator(0);
130 }
131
132 /**
133 * Gets a ListIterator over the list.
134 *
135 * @param fromIndex the index to start from
136 * @return the new iterator
137 */
138 @Override
139 public ListIterator<E> listIterator(final int fromIndex) {
140 // override to go 75% faster
141 // cannot use EmptyIterator as iterator.add() must work
142 checkInterval(fromIndex, 0, size());
143 return new TreeListIterator<E>(this, fromIndex);
144 }
145
146 /**
147 * Searches for the index of an object in the list.
148 *
149 * @param object the object to search
150 * @return the index of the object, -1 if not found
151 */
152 @Override
153 public int indexOf(final Object object) {
154 // override to go 75% faster
155 if (root == null) {
156 return -1;
157 }
158 return root.indexOf(object, root.relativePosition);
159 }
160
161 /**
162 * Searches for the presence of an object in the list.
163 *
164 * @param object the object to check
165 * @return true if the object is found
166 */
167 @Override
168 public boolean contains(final Object object) {
169 return indexOf(object) >= 0;
170 }
171
172 /**
173 * Converts the list into an array.
174 *
175 * @return the list as an array
176 */
177 @Override
178 public Object[] toArray() {
179 // override to go 20% faster
180 final Object[] array = new Object[size()];
181 if (root != null) {
182 root.toArray(array, root.relativePosition);
183 }
184 return array;
185 }
186
187 //-----------------------------------------------------------------------
188 /**
189 * Adds a new element to the list.
190 *
191 * @param index the index to add before
192 * @param obj the element to add
193 */
194 @Override
195 public void add(final int index, final E obj) {
196 modCount++;
197 checkInterval(index, 0, size());
198 if (root == null) {
199 root = new AVLNode<E>(index, obj, null, null);
200 } else {
201 root = root.insert(index, obj);
202 }
203 size++;
204 }
205
206 /**
207 * Sets the element at the specified index.
208 *
209 * @param index the index to set
210 * @param obj the object to store at the specified index
211 * @return the previous object at that index
212 * @throws IndexOutOfBoundsException if the index is invalid
213 */
214 @Override
215 public E set(final int index, final E obj) {
216 checkInterval(index, 0, size() - 1);
217 final AVLNode<E> node = root.get(index);
218 final E result = node.value;
219 node.setValue(obj);
220 return result;
221 }
222
223 /**
224 * Removes the element at the specified index.
225 *
226 * @param index the index to remove
227 * @return the previous object at that index
228 */
229 @Override
230 public E remove(final int index) {
231 modCount++;
232 checkInterval(index, 0, size() - 1);
233 final E result = get(index);
234 root = root.remove(index);
235 size--;
236 return result;
237 }
238
239 /**
240 * Clears the list, removing all entries.
241 */
242 @Override
243 public void clear() {
244 modCount++;
245 root = null;
246 size = 0;
247 }
248
249 //-----------------------------------------------------------------------
250 /**
251 * Checks whether the index is valid.
252 *
253 * @param index the index to check
254 * @param startIndex the first allowed index
255 * @param endIndex the last allowed index
256 * @throws IndexOutOfBoundsException if the index is invalid
257 */
258 private void checkInterval(final int index, final int startIndex, final int endIndex) {
259 if (index < startIndex || index > endIndex) {
260 throw new IndexOutOfBoundsException("Invalid index:" + index + ", size=" + size());
261 }
262 }
263
264 //-----------------------------------------------------------------------
265 /**
266 * Implements an AVLNode which keeps the offset updated.
267 * <p>
268 * This node contains the real work.
269 * TreeList is just there to implement {@link java.util.List}.
270 * The nodes don't know the index of the object they are holding. They
271 * do know however their position relative to their parent node.
272 * This allows to calculate the index of a node while traversing the tree.
273 * <p>
274 * The Faedelung calculation stores a flag for both the left and right child
275 * to indicate if they are a child (false) or a link as in linked list (true).
276 */
277 static class AVLNode<E> {
278 /** The left child node or the predecessor if {@link #leftIsPrevious}.*/
279 private AVLNode<E> left;
280 /** Flag indicating that left reference is not a subtree but the predecessor. */
281 private boolean leftIsPrevious;
282 /** The right child node or the successor if {@link #rightIsNext}. */
283 private AVLNode<E> right;
284 /** Flag indicating that right reference is not a subtree but the successor. */
285 private boolean rightIsNext;
286 /** How many levels of left/right are below this one. */
287 private int height;
288 /** The relative position, root holds absolute position. */
289 private int relativePosition;
290 /** The stored element. */
291 private E value;
292
293 /**
294 * Constructs a new node with a relative position.
295 *
296 * @param relativePosition the relative position of the node
297 * @param obj the value for the ndoe
298 * @param rightFollower the node with the value following this one
299 * @param leftFollower the node with the value leading this one
300 */
301 private AVLNode(final int relativePosition, final E obj,
302 final AVLNode<E> rightFollower, final AVLNode<E> leftFollower) {
303 this.relativePosition = relativePosition;
304 value = obj;
305 rightIsNext = true;
306 leftIsPrevious = true;
307 right = rightFollower;
308 left = leftFollower;
309 }
310
311 /**
312 * Gets the value.
313 *
314 * @return the value of this node
315 */
316 E getValue() {
317 return value;
318 }
319
320 /**
321 * Sets the value.
322 *
323 * @param obj the value to store
324 */
325 void setValue(final E obj) {
326 this.value = obj;
327 }
328
329 /**
330 * Locate the element with the given index relative to the
331 * offset of the parent of this node.
332 */
333 AVLNode<E> get(final int index) {
334 final int indexRelativeToMe = index - relativePosition;
335
336 if (indexRelativeToMe == 0) {
337 return this;
338 }
339
340 final AVLNode<E> nextNode = indexRelativeToMe < 0 ? getLeftSubTree() : getRightSubTree();
341 if (nextNode == null) {
342 return null;
343 }
344 return nextNode.get(indexRelativeToMe);
345 }
346
347 /**
348 * Locate the index that contains the specified object.
349 */
350 int indexOf(final Object object, final int index) {
351 if (getLeftSubTree() != null) {
352 final int result = left.indexOf(object, index + left.relativePosition);
353 if (result != -1) {
354 return result;
355 }
356 }
357 if (value == null ? value == object : value.equals(object)) {
358 return index;
359 }
360 if (getRightSubTree() != null) {
361 return right.indexOf(object, index + right.relativePosition);
362 }
363 return -1;
364 }
365
366 /**
367 * Stores the node and its children into the array specified.
368 *
369 * @param array the array to be filled
370 * @param index the index of this node
371 */
372 void toArray(final Object[] array, final int index) {
373 array[index] = value;
374 if (getLeftSubTree() != null) {
375 left.toArray(array, index + left.relativePosition);
376 }
377 if (getRightSubTree() != null) {
378 right.toArray(array, index + right.relativePosition);
379 }
380 }
381
382 /**
383 * Gets the next node in the list after this one.
384 *
385 * @return the next node
386 */
387 AVLNode<E> next() {
388 if (rightIsNext || right == null) {
389 return right;
390 }
391 return right.min();
392 }
393
394 /**
395 * Gets the node in the list before this one.
396 *
397 * @return the previous node
398 */
399 AVLNode<E> previous() {
400 if (leftIsPrevious || left == null) {
401 return left;
402 }
403 return left.max();
404 }
405
406 /**
407 * Inserts a node at the position index.
408 *
409 * @param index is the index of the position relative to the position of
410 * the parent node.
411 * @param obj is the object to be stored in the position.
412 */
413 AVLNode<E> insert(final int index, final E obj) {
414 final int indexRelativeToMe = index - relativePosition;
415
416 if (indexRelativeToMe <= 0) {
417 return insertOnLeft(indexRelativeToMe, obj);
418 }
419 return insertOnRight(indexRelativeToMe, obj);
420 }
421
422 private AVLNode<E> insertOnLeft(final int indexRelativeToMe, final E obj) {
423 if (getLeftSubTree() == null) {
424 setLeft(new AVLNode<E>(-1, obj, this, left), null);
425 } else {
426 setLeft(left.insert(indexRelativeToMe, obj), null);
427 }
428
429 if (relativePosition >= 0) {
430 relativePosition++;
431 }
432 AVLNode<E> ret = balance();
433 recalcHeight();
434 return ret;
435 }
436
437 private AVLNode<E> insertOnRight(final int indexRelativeToMe, final E obj) {
438 if (getRightSubTree() == null) {
439 setRight(new AVLNode<E>(+1, obj, right, this), null);
440 } else {
441 setRight(right.insert(indexRelativeToMe, obj), null);
442 }
443 if (relativePosition < 0) {
444 relativePosition--;
445 }
446 AVLNode<E> ret = balance();
447 recalcHeight();
448 return ret;
449 }
450
451 //-----------------------------------------------------------------------
452 /**
453 * Gets the left node, returning null if its a faedelung.
454 */
455 private AVLNode<E> getLeftSubTree() {
456 return leftIsPrevious ? null : left;
457 }
458
459 /**
460 * Gets the right node, returning null if its a faedelung.
461 */
462 private AVLNode<E> getRightSubTree() {
463 return rightIsNext ? null : right;
464 }
465
466 /**
467 * Gets the rightmost child of this node.
468 *
469 * @return the rightmost child (greatest index)
470 */
471 private AVLNode<E> max() {
472 return getRightSubTree() == null ? this : right.max();
473 }
474
475 /**
476 * Gets the leftmost child of this node.
477 *
478 * @return the leftmost child (smallest index)
479 */
480 private AVLNode<E> min() {
481 return getLeftSubTree() == null ? this : left.min();
482 }
483
484 /**
485 * Removes the node at a given position.
486 *
487 * @param index is the index of the element to be removed relative to the position of
488 * the parent node of the current node.
489 */
490 AVLNode<E> remove(final int index) {
491 final int indexRelativeToMe = index - relativePosition;
492
493 if (indexRelativeToMe == 0) {
494 return removeSelf();
495 }
496 if (indexRelativeToMe > 0) {
497 setRight(right.remove(indexRelativeToMe), right.right);
498 if (relativePosition < 0) {
499 relativePosition++;
500 }
501 } else {
502 setLeft(left.remove(indexRelativeToMe), left.left);
503 if (relativePosition > 0) {
504 relativePosition--;
505 }
506 }
507 recalcHeight();
508 return balance();
509 }
510
511 private AVLNode<E> removeMax() {
512 if (getRightSubTree() == null) {
513 return removeSelf();
514 }
515 setRight(right.removeMax(), right.right);
516 if (relativePosition < 0) {
517 relativePosition++;
518 }
519 recalcHeight();
520 return balance();
521 }
522
523 private AVLNode<E> removeMin() {
524 if (getLeftSubTree() == null) {
525 return removeSelf();
526 }
527 setLeft(left.removeMin(), left.left);
528 if (relativePosition > 0) {
529 relativePosition--;
530 }
531 recalcHeight();
532 return balance();
533 }
534
535 /**
536 * Removes this node from the tree.
537 *
538 * @return the node that replaces this one in the parent
539 */
540 private AVLNode<E> removeSelf() {
541 if (getRightSubTree() == null && getLeftSubTree() == null) {
542 return null;
543 }
544 if (getRightSubTree() == null) {
545 if (relativePosition > 0) {
546 left.relativePosition += relativePosition + (relativePosition > 0 ? 0 : 1);
547 }
548 left.max().setRight(null, right);
549 return left;
550 }
551 if (getLeftSubTree() == null) {
552 right.relativePosition += relativePosition - (relativePosition < 0 ? 0 : 1);
553 right.min().setLeft(null, left);
554 return right;
555 }
556
557 if (heightRightMinusLeft() > 0) {
558 // more on the right, so delete from the right
559 final AVLNode<E> rightMin = right.min();
560 value = rightMin.value;
561 if (leftIsPrevious) {
562 left = rightMin.left;
563 }
564 right = right.removeMin();
565 if (relativePosition < 0) {
566 relativePosition++;
567 }
568 } else {
569 // more on the left or equal, so delete from the left
570 final AVLNode<E> leftMax = left.max();
571 value = leftMax.value;
572 if (rightIsNext) {
573 right = leftMax.right;
574 }
575 final AVLNode<E> leftPrevious = left.left;
576 left = left.removeMax();
577 if (left == null) {
578 // special case where left that was deleted was a double link
579 // only occurs when height difference is equal
580 left = leftPrevious;
581 leftIsPrevious = true;
582 }
583 if (relativePosition > 0) {
584 relativePosition--;
585 }
586 }
587 recalcHeight();
588 return this;
589 }
590
591 //-----------------------------------------------------------------------
592 /**
593 * Balances according to the AVL algorithm.
594 */
595 private AVLNode<E> balance() {
596 switch (heightRightMinusLeft()) {
597 case 1 :
598 case 0 :
599 case -1 :
600 return this;
601 case -2 :
602 if (left.heightRightMinusLeft() > 0) {
603 setLeft(left.rotateLeft(), null);
604 }
605 return rotateRight();
606 case 2 :
607 if (right.heightRightMinusLeft() < 0) {
608 setRight(right.rotateRight(), null);
609 }
610 return rotateLeft();
611 default :
612 throw new RuntimeException("tree inconsistent!");
613 }
614 }
615
616 /**
617 * Gets the relative position.
618 */
619 private int getOffset(final AVLNode<E> node) {
620 if (node == null) {
621 return 0;
622 }
623 return node.relativePosition;
624 }
625
626 /**
627 * Sets the relative position.
628 */
629 private int setOffset(final AVLNode<E> node, final int newOffest) {
630 if (node == null) {
631 return 0;
632 }
633 final int oldOffset = getOffset(node);
634 node.relativePosition = newOffest;
635 return oldOffset;
636 }
637
638 /**
639 * Sets the height by calculation.
640 */
641 private void recalcHeight() {
642 height = Math.max(
643 getLeftSubTree() == null ? -1 : getLeftSubTree().height,
644 getRightSubTree() == null ? -1 : getRightSubTree().height) + 1;
645 }
646
647 /**
648 * Returns the height of the node or -1 if the node is null.
649 */
650 private int getHeight(final AVLNode<E> node) {
651 return node == null ? -1 : node.height;
652 }
653
654 /**
655 * Returns the height difference right - left
656 */
657 private int heightRightMinusLeft() {
658 return getHeight(getRightSubTree()) - getHeight(getLeftSubTree());
659 }
660
661 private AVLNode<E> rotateLeft() {
662 final AVLNode<E> newTop = right; // can't be faedelung!
663 final AVLNode<E> movedNode = getRightSubTree().getLeftSubTree();
664
665 final int newTopPosition = relativePosition + getOffset(newTop);
666 final int myNewPosition = -newTop.relativePosition;
667 final int movedPosition = getOffset(newTop) + getOffset(movedNode);
668
669 setRight(movedNode, newTop);
670 newTop.setLeft(this, null);
671
672 setOffset(newTop, newTopPosition);
673 setOffset(this, myNewPosition);
674 setOffset(movedNode, movedPosition);
675 return newTop;
676 }
677
678 private AVLNode<E> rotateRight() {
679 final AVLNode<E> newTop = left; // can't be faedelung
680 final AVLNode<E> movedNode = getLeftSubTree().getRightSubTree();
681
682 final int newTopPosition = relativePosition + getOffset(newTop);
683 final int myNewPosition = -newTop.relativePosition;
684 final int movedPosition = getOffset(newTop) + getOffset(movedNode);
685
686 setLeft(movedNode, newTop);
687 newTop.setRight(this, null);
688
689 setOffset(newTop, newTopPosition);
690 setOffset(this, myNewPosition);
691 setOffset(movedNode, movedPosition);
692 return newTop;
693 }
694
695 /**
696 * Sets the left field to the node, or the previous node if that is null
697 *
698 * @param node the new left subtree node
699 * @param previous the previous node in the linked list
700 */
701 private void setLeft(final AVLNode<E> node, final AVLNode<E> previous) {
702 leftIsPrevious = node == null;
703 left = leftIsPrevious ? previous : node;
704 recalcHeight();
705 }
706
707 /**
708 * Sets the right field to the node, or the next node if that is null
709 *
710 * @param node the new left subtree node
711 * @param next the next node in the linked list
712 */
713 private void setRight(final AVLNode<E> node, final AVLNode<E> next) {
714 rightIsNext = node == null;
715 right = rightIsNext ? next : node;
716 recalcHeight();
717 }
718
719 // private void checkFaedelung() {
720 // AVLNode maxNode = left.max();
721 // if (!maxNode.rightIsFaedelung || maxNode.right != this) {
722 // throw new RuntimeException(maxNode + " should right-faedel to " + this);
723 // }
724 // AVLNode minNode = right.min();
725 // if (!minNode.leftIsFaedelung || minNode.left != this) {
726 // throw new RuntimeException(maxNode + " should left-faedel to " + this);
727 // }
728 // }
729 //
730 // private int checkTreeDepth() {
731 // int hright = (getRightSubTree() == null ? -1 : getRightSubTree().checkTreeDepth());
732 // // System.out.print("checkTreeDepth");
733 // // System.out.print(this);
734 // // System.out.print(" left: ");
735 // // System.out.print(_left);
736 // // System.out.print(" right: ");
737 // // System.out.println(_right);
738 //
739 // int hleft = (left == null ? -1 : left.checkTreeDepth());
740 // if (height != Math.max(hright, hleft) + 1) {
741 // throw new RuntimeException(
742 // "height should be max" + hleft + "," + hright + " but is " + height);
743 // }
744 // return height;
745 // }
746 //
747 // private int checkLeftSubNode() {
748 // if (getLeftSubTree() == null) {
749 // return 0;
750 // }
751 // int count = 1 + left.checkRightSubNode();
752 // if (left.relativePosition != -count) {
753 // throw new RuntimeException();
754 // }
755 // return count + left.checkLeftSubNode();
756 // }
757 //
758 // private int checkRightSubNode() {
759 // AVLNode right = getRightSubTree();
760 // if (right == null) {
761 // return 0;
762 // }
763 // int count = 1;
764 // count += right.checkLeftSubNode();
765 // if (right.relativePosition != count) {
766 // throw new RuntimeException();
767 // }
768 // return count + right.checkRightSubNode();
769 // }
770
771 /**
772 * Used for debugging.
773 */
774 @Override
775 public String toString() {
776 return new StringBuilder()
777 .append("AVLNode(")
778 .append(relativePosition)
779 .append(',')
780 .append(left != null)
781 .append(',')
782 .append(value)
783 .append(',')
784 .append(getRightSubTree() != null)
785 .append(", faedelung ")
786 .append(rightIsNext)
787 .append(" )")
788 .toString();
789 }
790 }
791
792 /**
793 * A list iterator over the linked list.
794 */
795 static class TreeListIterator<E> implements ListIterator<E>, OrderedIterator<E> {
796 /** The parent list */
797 protected final TreeList<E> parent;
798 /**
799 * Cache of the next node that will be returned by {@link #next()}.
800 */
801 protected AVLNode<E> next;
802 /**
803 * The index of the next node to be returned.
804 */
805 protected int nextIndex;
806 /**
807 * Cache of the last node that was returned by {@link #next()}
808 * or {@link #previous()}.
809 */
810 protected AVLNode<E> current;
811 /**
812 * The index of the last node that was returned.
813 */
814 protected int currentIndex;
815 /**
816 * The modification count that the list is expected to have. If the list
817 * doesn't have this count, then a
818 * {@link java.util.ConcurrentModificationException} may be thrown by
819 * the operations.
820 */
821 protected int expectedModCount;
822
823 /**
824 * Create a ListIterator for a list.
825 *
826 * @param parent the parent list
827 * @param fromIndex the index to start at
828 */
829 protected TreeListIterator(final TreeList<E> parent, final int fromIndex) throws IndexOutOfBoundsException {
830 super();
831 this.parent = parent;
832 this.expectedModCount = parent.modCount;
833 this.next = parent.root == null ? null : parent.root.get(fromIndex);
834 this.nextIndex = fromIndex;
835 this.currentIndex = -1;
836 }
837
838 /**
839 * Checks the modification count of the list is the value that this
840 * object expects.
841 *
842 * @throws ConcurrentModificationException If the list's modification
843 * count isn't the value that was expected.
844 */
845 protected void checkModCount() {
846 if (parent.modCount != expectedModCount) {
847 throw new ConcurrentModificationException();
848 }
849 }
850
851 public boolean hasNext() {
852 return nextIndex < parent.size();
853 }
854
855 public E next() {
856 checkModCount();
857 if (!hasNext()) {
858 throw new NoSuchElementException("No element at index " + nextIndex + ".");
859 }
860 if (next == null) {
861 next = parent.root.get(nextIndex);
862 }
863 final E value = next.getValue();
864 current = next;
865 currentIndex = nextIndex++;
866 next = next.next();
867 return value;
868 }
869
870 public boolean hasPrevious() {
871 return nextIndex > 0;
872 }
873
874 public E previous() {
875 checkModCount();
876 if (!hasPrevious()) {
877 throw new NoSuchElementException("Already at start of list.");
878 }
879 if (next == null) {
880 next = parent.root.get(nextIndex - 1);
881 } else {
882 next = next.previous();
883 }
884 final E value = next.getValue();
885 current = next;
886 currentIndex = --nextIndex;
887 return value;
888 }
889
890 public int nextIndex() {
891 return nextIndex;
892 }
893
894 public int previousIndex() {
895 return nextIndex() - 1;
896 }
897
898 public void remove() {
899 checkModCount();
900 if (currentIndex == -1) {
901 throw new IllegalStateException();
902 }
903 if (nextIndex == currentIndex) {
904 // remove() following previous()
905 next = next.next();
906 parent.remove(currentIndex);
907 } else {
908 // remove() following next()
909 parent.remove(currentIndex);
910 nextIndex--;
911 }
912 current = null;
913 currentIndex = -1;
914 expectedModCount++;
915 }
916
917 public void set(final E obj) {
918 checkModCount();
919 if (current == null) {
920 throw new IllegalStateException();
921 }
922 current.setValue(obj);
923 }
924
925 public void add(final E obj) {
926 checkModCount();
927 parent.add(nextIndex, obj);
928 current = null;
929 currentIndex = -1;
930 nextIndex++;
931 expectedModCount++;
932 }
933 }
934
935 }