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