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 18 package java.util; 19 20 /** 21 * {@code AbstractList} is an abstract implementation of the {@code List} interface, optimized 22 * for a backing store which supports random access. This implementation does 23 * not support adding or replacing. A subclass must implement the abstract 24 * methods {@code get()} and {@code size()}, and to create a 25 * modifiable {@code List} it's necessary to override the {@code add()} method that 26 * currently throws an {@code UnsupportedOperationException}. 27 * 28 * @since 1.2 29 */ 30 public abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> { 31 32 /** 33 * A counter for changes to the list. 34 */ 35 protected transient int modCount; 36 37 private class SimpleListIterator implements Iterator<E> { 38 int pos = -1; 39 40 int expectedModCount; 41 42 int lastPosition = -1; 43 44 SimpleListIterator() { 45 expectedModCount = modCount; 46 } 47 48 public boolean hasNext() { 49 return pos + 1 < size(); 50 } 51 52 public E next() { 53 if (expectedModCount == modCount) { 54 try { 55 E result = get(pos + 1); 56 lastPosition = ++pos; 57 return result; 58 } catch (IndexOutOfBoundsException e) { 59 throw new NoSuchElementException(); 60 } 61 } 62 throw new ConcurrentModificationException(); 63 } 64 65 public void remove() { 66 if (this.lastPosition == -1) { 67 throw new IllegalStateException(); 68 } 69 70 if (expectedModCount != modCount) { 71 throw new ConcurrentModificationException(); 72 } 73 74 try { 75 AbstractList.this.remove(lastPosition); 76 } catch (IndexOutOfBoundsException e) { 77 throw new ConcurrentModificationException(); 78 } 79 80 expectedModCount = modCount; 81 if (pos == lastPosition) { 82 pos--; 83 } 84 lastPosition = -1; 85 } 86 } 87 88 private final class FullListIterator extends SimpleListIterator implements ListIterator<E> { 89 FullListIterator(int start) { 90 if (start >= 0 && start <= size()) { 91 pos = start - 1; 92 } else { 93 throw new IndexOutOfBoundsException(); 94 } 95 } 96 97 public void add(E object) { 98 if (expectedModCount == modCount) { 99 try { 100 AbstractList.this.add(pos + 1, object); 101 } catch (IndexOutOfBoundsException e) { 102 throw new NoSuchElementException(); 103 } 104 pos++; 105 lastPosition = -1; 106 if (modCount != expectedModCount) { 107 expectedModCount = modCount; 108 } 109 } else { 110 throw new ConcurrentModificationException(); 111 } 112 } 113 114 public boolean hasPrevious() { 115 return pos >= 0; 116 } 117 118 public int nextIndex() { 119 return pos + 1; 120 } 121 122 public E previous() { 123 if (expectedModCount == modCount) { 124 try { 125 E result = get(pos); 126 lastPosition = pos; 127 pos--; 128 return result; 129 } catch (IndexOutOfBoundsException e) { 130 throw new NoSuchElementException(); 131 } 132 } 133 throw new ConcurrentModificationException(); 134 } 135 136 public int previousIndex() { 137 return pos; 138 } 139 140 public void set(E object) { 141 if (expectedModCount == modCount) { 142 try { 143 AbstractList.this.set(lastPosition, object); 144 } catch (IndexOutOfBoundsException e) { 145 throw new IllegalStateException(); 146 } 147 } else { 148 throw new ConcurrentModificationException(); 149 } 150 } 151 } 152 153 private static final class SubAbstractListRandomAccess<E> extends 154 SubAbstractList<E> implements RandomAccess { 155 SubAbstractListRandomAccess(AbstractList<E> list, int start, int end) { 156 super(list, start, end); 157 } 158 } 159 160 private static class SubAbstractList<E> extends AbstractList<E> { 161 private final AbstractList<E> fullList; 162 163 private int offset; 164 165 private int size; 166 167 private static final class SubAbstractListIterator<E> implements 168 ListIterator<E> { 169 private final SubAbstractList<E> subList; 170 171 private final ListIterator<E> iterator; 172 173 private int start; 174 175 private int end; 176 177 SubAbstractListIterator(ListIterator<E> it, 178 SubAbstractList<E> list, int offset, int length) { 179 iterator = it; 180 subList = list; 181 start = offset; 182 end = start + length; 183 } 184 185 public void add(E object) { 186 iterator.add(object); 187 subList.sizeChanged(true); 188 end++; 189 } 190 191 public boolean hasNext() { 192 return iterator.nextIndex() < end; 193 } 194 195 public boolean hasPrevious() { 196 return iterator.previousIndex() >= start; 197 } 198 199 public E next() { 200 if (iterator.nextIndex() < end) { 201 return iterator.next(); 202 } 203 throw new NoSuchElementException(); 204 } 205 206 public int nextIndex() { 207 return iterator.nextIndex() - start; 208 } 209 210 public E previous() { 211 if (iterator.previousIndex() >= start) { 212 return iterator.previous(); 213 } 214 throw new NoSuchElementException(); 215 } 216 217 public int previousIndex() { 218 int previous = iterator.previousIndex(); 219 if (previous >= start) { 220 return previous - start; 221 } 222 return -1; 223 } 224 225 public void remove() { 226 iterator.remove(); 227 subList.sizeChanged(false); 228 end--; 229 } 230 231 public void set(E object) { 232 iterator.set(object); 233 } 234 } 235 236 SubAbstractList(AbstractList<E> list, int start, int end) { 237 fullList = list; 238 modCount = fullList.modCount; 239 offset = start; 240 size = end - start; 241 } 242 243 @Override 244 public void add(int location, E object) { 245 if (modCount == fullList.modCount) { 246 if (location >= 0 && location <= size) { 247 fullList.add(location + offset, object); 248 size++; 249 modCount = fullList.modCount; 250 } else { 251 throw new IndexOutOfBoundsException(); 252 } 253 } else { 254 throw new ConcurrentModificationException(); 255 } 256 } 257 258 @Override 259 public boolean addAll(int location, Collection<? extends E> collection) { 260 if (modCount == fullList.modCount) { 261 if (location >= 0 && location <= size) { 262 boolean result = fullList.addAll(location + offset, 263 collection); 264 if (result) { 265 size += collection.size(); 266 modCount = fullList.modCount; 267 } 268 return result; 269 } 270 throw new IndexOutOfBoundsException(); 271 } 272 throw new ConcurrentModificationException(); 273 } 274 275 @Override 276 public boolean addAll(Collection<? extends E> collection) { 277 if (modCount == fullList.modCount) { 278 boolean result = fullList.addAll(offset + size, collection); 279 if (result) { 280 size += collection.size(); 281 modCount = fullList.modCount; 282 } 283 return result; 284 } 285 throw new ConcurrentModificationException(); 286 } 287 288 @Override 289 public E get(int location) { 290 if (modCount == fullList.modCount) { 291 if (location >= 0 && location < size) { 292 return fullList.get(location + offset); 293 } 294 throw new IndexOutOfBoundsException(); 295 } 296 throw new ConcurrentModificationException(); 297 } 298 299 @Override 300 public Iterator<E> iterator() { 301 return listIterator(0); 302 } 303 304 @Override 305 public ListIterator<E> listIterator(int location) { 306 if (modCount == fullList.modCount) { 307 if (location >= 0 && location <= size) { 308 return new SubAbstractListIterator<E>(fullList 309 .listIterator(location + offset), this, offset, 310 size); 311 } 312 throw new IndexOutOfBoundsException(); 313 } 314 throw new ConcurrentModificationException(); 315 } 316 317 @Override 318 public E remove(int location) { 319 if (modCount == fullList.modCount) { 320 if (location >= 0 && location < size) { 321 E result = fullList.remove(location + offset); 322 size--; 323 modCount = fullList.modCount; 324 return result; 325 } 326 throw new IndexOutOfBoundsException(); 327 } 328 throw new ConcurrentModificationException(); 329 } 330 331 @Override 332 protected void removeRange(int start, int end) { 333 if (start != end) { 334 if (modCount == fullList.modCount) { 335 fullList.removeRange(start + offset, end + offset); 336 size -= end - start; 337 modCount = fullList.modCount; 338 } else { 339 throw new ConcurrentModificationException(); 340 } 341 } 342 } 343 344 @Override 345 public E set(int location, E object) { 346 if (modCount == fullList.modCount) { 347 if (location >= 0 && location < size) { 348 return fullList.set(location + offset, object); 349 } 350 throw new IndexOutOfBoundsException(); 351 } 352 throw new ConcurrentModificationException(); 353 } 354 355 @Override 356 public int size() { 357 if (modCount == fullList.modCount) { 358 return size; 359 } 360 throw new ConcurrentModificationException(); 361 } 362 363 void sizeChanged(boolean increment) { 364 if (increment) { 365 size++; 366 } else { 367 size--; 368 } 369 modCount = fullList.modCount; 370 } 371 } 372 373 /** 374 * Constructs a new instance of this AbstractList. 375 */ 376 protected AbstractList() { 377 } 378 379 /** 380 * Inserts the specified object into this List at the specified location. 381 * The object is inserted before any previous element at the specified 382 * location. If the location is equal to the size of this List, the object 383 * is added at the end. 384 * <p> 385 * Concrete implementations that would like to support the add functionality 386 * must override this method. 387 * 388 * @param location 389 * the index at which to insert. 390 * @param object 391 * the object to add. 392 * 393 * @throws UnsupportedOperationException 394 * if adding to this List is not supported. 395 * @throws ClassCastException 396 * if the class of the object is inappropriate for this 397 * List 398 * @throws IllegalArgumentException 399 * if the object cannot be added to this List 400 * @throws IndexOutOfBoundsException 401 * if {@code location < 0 || location > size()} 402 */ 403 public void add(int location, E object) { 404 throw new UnsupportedOperationException(); 405 } 406 407 /** 408 * Adds the specified object at the end of this List. 409 * 410 * 411 * @param object 412 * the object to add 413 * @return true 414 * 415 * @throws UnsupportedOperationException 416 * if adding to this List is not supported 417 * @throws ClassCastException 418 * if the class of the object is inappropriate for this 419 * List 420 * @throws IllegalArgumentException 421 * if the object cannot be added to this List 422 */ 423 @Override 424 public boolean add(E object) { 425 add(size(), object); 426 return true; 427 } 428 429 /** 430 * Inserts the objects in the specified Collection at the specified location 431 * in this List. The objects are added in the order they are returned from 432 * the collection's iterator. 433 * 434 * @param location 435 * the index at which to insert. 436 * @param collection 437 * the Collection of objects 438 * @return {@code true} if this List is modified, {@code false} otherwise. 439 * @throws UnsupportedOperationException 440 * if adding to this list is not supported. 441 * @throws ClassCastException 442 * if the class of an object is inappropriate for this list. 443 * @throws IllegalArgumentException 444 * if an object cannot be added to this list. 445 * @throws IndexOutOfBoundsException 446 * if {@code location < 0 || location > size()} 447 */ 448 public boolean addAll(int location, Collection<? extends E> collection) { 449 Iterator<? extends E> it = collection.iterator(); 450 while (it.hasNext()) { 451 add(location++, it.next()); 452 } 453 return !collection.isEmpty(); 454 } 455 456 /** 457 * Removes all elements from this list, leaving it empty. 458 * 459 * @throws UnsupportedOperationException 460 * if removing from this list is not supported. 461 * @see List#isEmpty 462 * @see List#size 463 */ 464 @Override 465 public void clear() { 466 removeRange(0, size()); 467 } 468 469 /** 470 * Compares the specified object to this list and return true if they are 471 * equal. Two lists are equal when they both contain the same objects in the 472 * same order. 473 * 474 * @param object 475 * the object to compare to this object. 476 * @return {@code true} if the specified object is equal to this list, 477 * {@code false} otherwise. 478 * @see #hashCode 479 */ 480 @Override 481 public boolean equals(Object object) { 482 if (this == object) { 483 return true; 484 } 485 if (object instanceof List) { 486 List<?> list = (List<?>) object; 487 if (list.size() != size()) { 488 return false; 489 } 490 491 Iterator<?> it1 = iterator(), it2 = list.iterator(); 492 while (it1.hasNext()) { 493 Object e1 = it1.next(), e2 = it2.next(); 494 if (!(e1 == null ? e2 == null : e1.equals(e2))) { 495 return false; 496 } 497 } 498 return true; 499 } 500 return false; 501 } 502 503 /** 504 * Returns the element at the specified location in this list. 505 * 506 * @param location 507 * the index of the element to return. 508 * @return the element at the specified index. 509 * @throws IndexOutOfBoundsException 510 * if {@code location < 0 || location >= size()} 511 */ 512 public abstract E get(int location); 513 514 /** 515 * Returns the hash code of this list. The hash code is calculated by taking 516 * each element's hashcode into account. 517 * 518 * @return the hash code. 519 * @see #equals 520 * @see List#hashCode() 521 */ 522 @Override 523 public int hashCode() { 524 int result = 1; 525 Iterator<?> it = iterator(); 526 while (it.hasNext()) { 527 Object object = it.next(); 528 result = (31 * result) + (object == null ? 0 : object.hashCode()); 529 } 530 return result; 531 } 532 533 /** 534 * Searches this list for the specified object and returns the index of the 535 * first occurrence. 536 * 537 * @param object 538 * the object to search for. 539 * @return the index of the first occurrence of the object, or -1 if it was 540 * not found. 541 */ 542 public int indexOf(Object object) { 543 ListIterator<?> it = listIterator(); 544 if (object != null) { 545 while (it.hasNext()) { 546 if (object.equals(it.next())) { 547 return it.previousIndex(); 548 } 549 } 550 } else { 551 while (it.hasNext()) { 552 if (it.next() == null) { 553 return it.previousIndex(); 554 } 555 } 556 } 557 return -1; 558 } 559 560 /** 561 * Returns an iterator on the elements of this list. The elements are 562 * iterated in the same order as they occur in the list. 563 * 564 * @return an iterator on the elements of this list. 565 * @see Iterator 566 */ 567 @Override 568 public Iterator<E> iterator() { 569 return new SimpleListIterator(); 570 } 571 572 /** 573 * Searches this list for the specified object and returns the index of the 574 * last occurrence. 575 * 576 * @param object 577 * the object to search for. 578 * @return the index of the last occurrence of the object, or -1 if the 579 * object was not found. 580 */ 581 public int lastIndexOf(Object object) { 582 ListIterator<?> it = listIterator(size()); 583 if (object != null) { 584 while (it.hasPrevious()) { 585 if (object.equals(it.previous())) { 586 return it.nextIndex(); 587 } 588 } 589 } else { 590 while (it.hasPrevious()) { 591 if (it.previous() == null) { 592 return it.nextIndex(); 593 } 594 } 595 } 596 return -1; 597 } 598 599 /** 600 * Returns a ListIterator on the elements of this list. The elements are 601 * iterated in the same order that they occur in the list. 602 * 603 * @return a ListIterator on the elements of this list 604 * @see ListIterator 605 */ 606 public ListIterator<E> listIterator() { 607 return listIterator(0); 608 } 609 610 /** 611 * Returns a list iterator on the elements of this list. The elements are 612 * iterated in the same order as they occur in the list. The iteration 613 * starts at the specified location. 614 * 615 * @param location 616 * the index at which to start the iteration. 617 * @return a ListIterator on the elements of this list. 618 * @throws IndexOutOfBoundsException 619 * if {@code location < 0 || location > size()} 620 * @see ListIterator 621 */ 622 public ListIterator<E> listIterator(int location) { 623 return new FullListIterator(location); 624 } 625 626 /** 627 * Removes the object at the specified location from this list. 628 * 629 * @param location 630 * the index of the object to remove. 631 * @return the removed object. 632 * @throws UnsupportedOperationException 633 * if removing from this list is not supported. 634 * @throws IndexOutOfBoundsException 635 * if {@code location < 0 || location >= size()} 636 */ 637 public E remove(int location) { 638 throw new UnsupportedOperationException(); 639 } 640 641 /** 642 * Removes the objects in the specified range from the start to the end 643 * index minus one. 644 * 645 * @param start 646 * the index at which to start removing. 647 * @param end 648 * the index after the last element to remove. 649 * @throws UnsupportedOperationException 650 * if removing from this list is not supported. 651 * @throws IndexOutOfBoundsException 652 * if {@code start < 0} or {@code start >= size()}. 653 */ 654 protected void removeRange(int start, int end) { 655 Iterator<?> it = listIterator(start); 656 for (int i = start; i < end; i++) { 657 it.next(); 658 it.remove(); 659 } 660 } 661 662 /** 663 * Replaces the element at the specified location in this list with the 664 * specified object. 665 * 666 * @param location 667 * the index at which to put the specified object. 668 * @param object 669 * the object to add. 670 * @return the previous element at the index. 671 * @throws UnsupportedOperationException 672 * if replacing elements in this list is not supported. 673 * @throws ClassCastException 674 * if the class of an object is inappropriate for this list. 675 * @throws IllegalArgumentException 676 * if an object cannot be added to this list. 677 * @throws IndexOutOfBoundsException 678 * if {@code location < 0 || location >= size()} 679 */ 680 public E set(int location, E object) { 681 throw new UnsupportedOperationException(); 682 } 683 684 /** 685 * Returns a part of consecutive elements of this list as a view. The 686 * returned view will be of zero length if start equals end. Any change that 687 * occurs in the returned subList will be reflected to the original list, 688 * and vice-versa. All the supported optional operations by the original 689 * list will also be supported by this subList. 690 * <p> 691 * This method can be used as a handy method to do some operations on a sub 692 * range of the original list, for example 693 * {@code list.subList(from, to).clear();} 694 * <p> 695 * If the original list is modified in other ways than through the returned 696 * subList, the behavior of the returned subList becomes undefined. 697 * <p> 698 * The returned subList is a subclass of AbstractList. The subclass stores 699 * offset, size of itself, and modCount of the original list. If the 700 * original list implements RandomAccess interface, the returned subList 701 * also implements RandomAccess interface. 702 * <p> 703 * The subList's set(int, Object), get(int), add(int, Object), remove(int), 704 * addAll(int, Collection) and removeRange(int, int) methods first check the 705 * bounds, adjust offsets and then call the corresponding methods of the 706 * original AbstractList. addAll(Collection c) method of the returned 707 * subList calls the original addAll(offset + size, c). 708 * <p> 709 * The listIterator(int) method of the subList wraps the original list 710 * iterator. The iterator() method of the subList invokes the original 711 * listIterator() method, and the size() method merely returns the size of 712 * the subList. 713 * <p> 714 * All methods will throw a ConcurrentModificationException if the modCount 715 * of the original list is not equal to the expected value. 716 * 717 * @param start 718 * start index of the subList (inclusive). 719 * @param end 720 * end index of the subList, (exclusive). 721 * @return a subList view of this list starting from {@code start} 722 * (inclusive), and ending with {@code end} (exclusive) 723 * @throws IndexOutOfBoundsException 724 * if (start < 0 || end > size()) 725 * @throws IllegalArgumentException 726 * if (start > end) 727 */ 728 public List<E> subList(int start, int end) { 729 if (start >= 0 && end <= size()) { 730 if (start <= end) { 731 if (this instanceof RandomAccess) { 732 return new SubAbstractListRandomAccess<E>(this, start, end); 733 } 734 return new SubAbstractList<E>(this, start, end); 735 } 736 throw new IllegalArgumentException(); 737 } 738 throw new IndexOutOfBoundsException(); 739 } 740 } 741