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