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    }