Save This Page
Home » commons-beanutils-1.8.3-src » org.apache.commons » collections » list » [javadoc | source]
    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 sligtly more memory.
   52    * 
   53    * @since Commons Collections 3.1
   54    * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
   55    *
   56    * @author Joerg Schmuecker
   57    * @author Stephen Colebourne
   58    */
   59   public class TreeList extends AbstractList {
   60   //    add; toArray; iterator; insert; get; indexOf; remove
   61   //    TreeList = 1260;7360;3080;  160;   170;3400;  170;
   62   //   ArrayList =  220;1480;1760; 6870;    50;1540; 7200;
   63   //  LinkedList =  270;7360;3350;55860;290720;2910;55200;
   64   
   65       /** The root node in the AVL tree */
   66       private AVLNode root;
   67   
   68       /** The current size of the list */
   69       private int size;
   70   
   71       //-----------------------------------------------------------------------
   72       /**
   73        * Constructs a new empty list.
   74        */
   75       public TreeList() {
   76           super();
   77       }
   78   
   79       /**
   80        * Constructs a new empty list that copies the specified list.
   81        * 
   82        * @param coll  the collection to copy
   83        * @throws NullPointerException if the collection is null
   84        */
   85       public TreeList(Collection coll) {
   86           super();
   87           addAll(coll);
   88       }
   89   
   90       //-----------------------------------------------------------------------
   91       /**
   92        * Gets the element at the specified index.
   93        * 
   94        * @param index  the index to retrieve
   95        * @return the element at the specified index
   96        */
   97       public Object get(int index) {
   98           checkInterval(index, 0, size() - 1);
   99           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   }

Save This Page
Home » commons-beanutils-1.8.3-src » org.apache.commons » collections » list » [javadoc | source]