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 }