151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski/* 2fee325d834eb37a26761e849c9becd7b9b4d3a12Tobias Thierer * Copyright (c) 1997, 2012, Oracle and/or its affiliates. All rights reserved. 351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This code is free software; you can redistribute it and/or modify it 651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * under the terms of the GNU General Public License version 2 only, as 751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * published by the Free Software Foundation. Oracle designates this 851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * particular file as subject to the "Classpath" exception as provided 951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * by Oracle in the LICENSE file that accompanied this code. 1051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 1151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This code is distributed in the hope that it will be useful, but WITHOUT 1251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * version 2 for more details (a copy is included in the LICENSE file that 1551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * accompanied this code). 1651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 1751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * You should have received a copy of the GNU General Public License version 1851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 2 along with this work; if not, write to the Free Software Foundation, 1951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 2051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 2151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 2251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * or visit www.oracle.com if you need additional information or have any 2351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * questions. 2451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 2551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 2651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebskipackage java.util; 2751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 2851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski/** 2951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This class provides a skeletal implementation of the {@link List} 3051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * interface to minimize the effort required to implement this interface 3151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * backed by a "random access" data store (such as an array). For sequential 3251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * access data (such as a linked list), {@link AbstractSequentialList} should 3351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * be used in preference to this class. 3451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 3551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>To implement an unmodifiable list, the programmer needs only to extend 3651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * this class and provide implementations for the {@link #get(int)} and 3751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@link List#size() size()} methods. 3851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 3951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>To implement a modifiable list, the programmer must additionally 4051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * override the {@link #set(int, Object) set(int, E)} method (which otherwise 4151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * throws an {@code UnsupportedOperationException}). If the list is 4251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * variable-size the programmer must additionally override the 4351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@link #add(int, Object) add(int, E)} and {@link #remove(int)} methods. 4451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 4551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>The programmer should generally provide a void (no argument) and collection 4651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * constructor, as per the recommendation in the {@link Collection} interface 4751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * specification. 4851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 4951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>Unlike the other abstract collection implementations, the programmer does 5051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <i>not</i> have to provide an iterator implementation; the iterator and 5151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * list iterator are implemented by this class, on top of the "random access" 5251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * methods: 5351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@link #get(int)}, 5451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@link #set(int, Object) set(int, E)}, 5551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@link #add(int, Object) add(int, E)} and 5651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@link #remove(int)}. 5751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 5851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>The documentation for each non-abstract method in this class describes its 5951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * implementation in detail. Each of these methods may be overridden if the 6051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * collection being implemented admits a more efficient implementation. 6151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 6251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This class is a member of the 63309f9df28350e15445b9135e8b710fa2b34b5dc1Yi Kong * <a href="{@docRoot}openjdk-redirect.html?v=8&path=/technotes/guides/collections/index.html"> 6451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Java Collections Framework</a>. 6551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 6651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @author Josh Bloch 6751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @author Neal Gafter 6851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @since 1.2 6951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 7051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 7151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebskipublic abstract class AbstractList<E> extends AbstractCollection<E> implements List<E> { 7251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 7351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Sole constructor. (For invocation by subclass constructors, typically 7451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * implicit.) 7551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 7651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski protected AbstractList() { 7751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 7851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 7951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 8051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Appends the specified element to the end of this list (optional 8151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * operation). 8251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 8351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>Lists that support this operation may place limitations on what 8451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * elements may be added to this list. In particular, some 8551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * lists will refuse to add null elements, and others will impose 8651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * restrictions on the type of elements that may be added. List 8751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * classes should clearly specify in their documentation any restrictions 8851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * on what elements may be added. 8951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 9051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This implementation calls {@code add(size(), e)}. 9151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 9251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>Note that this implementation throws an 9351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code UnsupportedOperationException} unless 9451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@link #add(int, Object) add(int, E)} is overridden. 9551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 9651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param e element to be appended to this list 9751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return {@code true} (as specified by {@link Collection#add}) 9851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws UnsupportedOperationException if the {@code add} operation 9951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * is not supported by this list 10051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException if the class of the specified element 10151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * prevents it from being added to this list 10251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException if the specified element is null and this 10351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * list does not permit null elements 10451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalArgumentException if some property of this element 10551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * prevents it from being added to this list 10651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 10751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public boolean add(E e) { 10851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski add(size(), e); 10951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return true; 11051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 11151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 11251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 11351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@inheritDoc} 11451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 11551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IndexOutOfBoundsException {@inheritDoc} 11651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 11751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski abstract public E get(int index); 11851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 11951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 12051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@inheritDoc} 12151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 12251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This implementation always throws an 12351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code UnsupportedOperationException}. 12451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 12551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws UnsupportedOperationException {@inheritDoc} 12651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException {@inheritDoc} 12751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException {@inheritDoc} 12851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalArgumentException {@inheritDoc} 12951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IndexOutOfBoundsException {@inheritDoc} 13051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 13151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public E set(int index, E element) { 13251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new UnsupportedOperationException(); 13351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 13451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 13551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 13651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@inheritDoc} 13751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 13851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This implementation always throws an 13951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code UnsupportedOperationException}. 14051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 14151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws UnsupportedOperationException {@inheritDoc} 14251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException {@inheritDoc} 14351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException {@inheritDoc} 14451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalArgumentException {@inheritDoc} 14551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IndexOutOfBoundsException {@inheritDoc} 14651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 14751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public void add(int index, E element) { 14851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new UnsupportedOperationException(); 14951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 15051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 15151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 15251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@inheritDoc} 15351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 15451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This implementation always throws an 15551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code UnsupportedOperationException}. 15651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 15751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws UnsupportedOperationException {@inheritDoc} 15851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IndexOutOfBoundsException {@inheritDoc} 15951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 16051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public E remove(int index) { 16151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new UnsupportedOperationException(); 16251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 16351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 16451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 16551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Search Operations 16651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 16751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 16851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@inheritDoc} 16951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 17051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This implementation first gets a list iterator (with 17151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code listIterator()}). Then, it iterates over the list until the 17251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * specified element is found or the end of the list is reached. 17351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 17451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException {@inheritDoc} 17551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException {@inheritDoc} 17651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 17751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public int indexOf(Object o) { 17851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ListIterator<E> it = listIterator(); 17951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (o==null) { 18051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (it.hasNext()) 18151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (it.next()==null) 18251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return it.previousIndex(); 18351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } else { 18451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (it.hasNext()) 18551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (o.equals(it.next())) 18651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return it.previousIndex(); 18751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 18851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return -1; 18951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 19051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 19151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 19251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@inheritDoc} 19351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 19451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This implementation first gets a list iterator that points to the end 19551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * of the list (with {@code listIterator(size())}). Then, it iterates 19651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * backwards over the list until the specified element is found, or the 19751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * beginning of the list is reached. 19851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 19951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException {@inheritDoc} 20051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException {@inheritDoc} 20151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 20251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public int lastIndexOf(Object o) { 20351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ListIterator<E> it = listIterator(size()); 20451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (o==null) { 20551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (it.hasPrevious()) 20651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (it.previous()==null) 20751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return it.nextIndex(); 20851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } else { 20951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (it.hasPrevious()) 21051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (o.equals(it.previous())) 21151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return it.nextIndex(); 21251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 21351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return -1; 21451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 21551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 21651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 21751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Bulk Operations 21851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 21951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 22051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Removes all of the elements from this list (optional operation). 22151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The list will be empty after this call returns. 22251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 22351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This implementation calls {@code removeRange(0, size())}. 22451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 22551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>Note that this implementation throws an 22651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code UnsupportedOperationException} unless {@code remove(int 22751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * index)} or {@code removeRange(int fromIndex, int toIndex)} is 22851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * overridden. 22951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 23051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws UnsupportedOperationException if the {@code clear} operation 23151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * is not supported by this list 23251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 23351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public void clear() { 23451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski removeRange(0, size()); 23551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 23651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 23751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 23851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@inheritDoc} 23951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 24051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This implementation gets an iterator over the specified collection 24151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * and iterates over it, inserting the elements obtained from the 24251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * iterator into this list at the appropriate position, one at a time, 24351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * using {@code add(int, E)}. 24451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Many implementations will override this method for efficiency. 24551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 24651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>Note that this implementation throws an 24751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code UnsupportedOperationException} unless 24851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@link #add(int, Object) add(int, E)} is overridden. 24951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 25051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws UnsupportedOperationException {@inheritDoc} 25151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws ClassCastException {@inheritDoc} 25251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws NullPointerException {@inheritDoc} 25351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalArgumentException {@inheritDoc} 25451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IndexOutOfBoundsException {@inheritDoc} 25551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 25651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public boolean addAll(int index, Collection<? extends E> c) { 25751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski rangeCheckForAdd(index); 25851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski boolean modified = false; 25951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (E e : c) { 26051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski add(index++, e); 26151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski modified = true; 26251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 26351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return modified; 26451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 26551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 26651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 26751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Iterators 26851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 26951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 27051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Returns an iterator over the elements in this list in proper sequence. 27151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 27251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This implementation returns a straightforward implementation of the 27351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * iterator interface, relying on the backing list's {@code size()}, 27451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code get(int)}, and {@code remove(int)} methods. 27551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 27651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>Note that the iterator returned by this method will throw an 27751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@link UnsupportedOperationException} in response to its 27851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code remove} method unless the list's {@code remove(int)} method is 27951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * overridden. 28051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 28151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This implementation can be made to throw runtime exceptions in the 28251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * face of concurrent modification, as described in the specification 28351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * for the (protected) {@link #modCount} field. 28451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 28551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return an iterator over the elements in this list in proper sequence 28651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 28751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public Iterator<E> iterator() { 28851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return new Itr(); 28951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 29051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 29151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 29251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@inheritDoc} 29351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 29451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This implementation returns {@code listIterator(0)}. 29551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 29651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @see #listIterator(int) 29751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 29851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public ListIterator<E> listIterator() { 29951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return listIterator(0); 30051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 30151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 30251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 30351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@inheritDoc} 30451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 30551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This implementation returns a straightforward implementation of the 30651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code ListIterator} interface that extends the implementation of the 30751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code Iterator} interface returned by the {@code iterator()} method. 30851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The {@code ListIterator} implementation relies on the backing list's 30951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code get(int)}, {@code set(int, E)}, {@code add(int, E)} 31051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * and {@code remove(int)} methods. 31151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 31251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>Note that the list iterator returned by this implementation will 31351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * throw an {@link UnsupportedOperationException} in response to its 31451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code remove}, {@code set} and {@code add} methods unless the 31551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * list's {@code remove(int)}, {@code set(int, E)}, and 31651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code add(int, E)} methods are overridden. 31751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 31851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This implementation can be made to throw runtime exceptions in the 31951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * face of concurrent modification, as described in the specification for 32051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the (protected) {@link #modCount} field. 32151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 32251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IndexOutOfBoundsException {@inheritDoc} 32351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 32451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public ListIterator<E> listIterator(final int index) { 32551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski rangeCheckForAdd(index); 32651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 32751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return new ListItr(index); 32851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 32951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 33051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private class Itr implements Iterator<E> { 33151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 33251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Index of element to be returned by subsequent call to next. 33351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 33451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int cursor = 0; 33551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 33651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 33751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Index of element returned by most recent call to next or 33851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * previous. Reset to -1 if this element is deleted by a call 33951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * to remove. 34051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 34151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int lastRet = -1; 34251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 34351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 34451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The modCount value that the iterator believes that the backing 34551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * List should have. If this expectation is violated, the iterator 34651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * has detected concurrent modification. 34751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 34851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int expectedModCount = modCount; 34951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 35051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public boolean hasNext() { 35151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return cursor != size(); 35251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 35351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 35451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public E next() { 35551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski checkForComodification(); 35651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski try { 35751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int i = cursor; 35851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E next = get(i); 35951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski lastRet = i; 36051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski cursor = i + 1; 36151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return next; 36251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } catch (IndexOutOfBoundsException e) { 36351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski checkForComodification(); 36451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new NoSuchElementException(); 36551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 36651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 36751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 36851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public void remove() { 36951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (lastRet < 0) 37051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new IllegalStateException(); 37151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski checkForComodification(); 37251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 37351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski try { 37451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski AbstractList.this.remove(lastRet); 37551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (lastRet < cursor) 37651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski cursor--; 37751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski lastRet = -1; 37851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski expectedModCount = modCount; 37951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } catch (IndexOutOfBoundsException e) { 38051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new ConcurrentModificationException(); 38151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 38251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 38351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 38451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski final void checkForComodification() { 38551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (modCount != expectedModCount) 38651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new ConcurrentModificationException(); 38751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 38851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 38951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 39051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private class ListItr extends Itr implements ListIterator<E> { 39151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ListItr(int index) { 39251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski cursor = index; 39351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 39451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 39551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public boolean hasPrevious() { 39651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return cursor != 0; 39751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 39851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 39951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public E previous() { 40051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski checkForComodification(); 40151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski try { 40251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int i = cursor - 1; 40351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E previous = get(i); 40451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski lastRet = cursor = i; 40551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return previous; 40651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } catch (IndexOutOfBoundsException e) { 40751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski checkForComodification(); 40851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new NoSuchElementException(); 40951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 41051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 41151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 41251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public int nextIndex() { 41351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return cursor; 41451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 41551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 41651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public int previousIndex() { 41751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return cursor-1; 41851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 41951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 42051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public void set(E e) { 42151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (lastRet < 0) 42251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new IllegalStateException(); 42351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski checkForComodification(); 42451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 42551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski try { 42651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski AbstractList.this.set(lastRet, e); 42751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski expectedModCount = modCount; 42851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } catch (IndexOutOfBoundsException ex) { 42951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new ConcurrentModificationException(); 43051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 43151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 43251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 43351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public void add(E e) { 43451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski checkForComodification(); 43551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 43651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski try { 43751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int i = cursor; 43851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski AbstractList.this.add(i, e); 43951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski lastRet = -1; 44051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski cursor = i + 1; 44151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski expectedModCount = modCount; 44251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } catch (IndexOutOfBoundsException ex) { 44351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new ConcurrentModificationException(); 44451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 44551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 44651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 44751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 44851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 44951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@inheritDoc} 45051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 45151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This implementation returns a list that subclasses 45251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code AbstractList}. The subclass stores, in private fields, the 45351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * offset of the subList within the backing list, the size of the subList 45451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (which can change over its lifetime), and the expected 45551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code modCount} value of the backing list. There are two variants 45651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * of the subclass, one of which implements {@code RandomAccess}. 45751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * If this list implements {@code RandomAccess} the returned list will 45851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * be an instance of the subclass that implements {@code RandomAccess}. 45951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 46051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>The subclass's {@code set(int, E)}, {@code get(int)}, 46151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code add(int, E)}, {@code remove(int)}, {@code addAll(int, 46251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Collection)} and {@code removeRange(int, int)} methods all 46351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * delegate to the corresponding methods on the backing abstract list, 46451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * after bounds-checking the index and adjusting for the offset. The 46551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code addAll(Collection c)} method merely returns {@code addAll(size, 46651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * c)}. 46751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 46851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>The {@code listIterator(int)} method returns a "wrapper object" 46951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * over a list iterator on the backing list, which is created with the 47051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * corresponding method on the backing list. The {@code iterator} method 47151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * merely returns {@code listIterator()}, and the {@code size} method 47251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * merely returns the subclass's {@code size} field. 47351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 47451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>All methods first check to see if the actual {@code modCount} of 47551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the backing list is equal to its expected value, and throw a 47651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code ConcurrentModificationException} if it is not. 47751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 47851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IndexOutOfBoundsException if an endpoint index value is out of range 47951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code (fromIndex < 0 || toIndex > size)} 48051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @throws IllegalArgumentException if the endpoint indices are out of order 48151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code (fromIndex > toIndex)} 48251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 48351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public List<E> subList(int fromIndex, int toIndex) { 48451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return (this instanceof RandomAccess ? 48551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski new RandomAccessSubList<>(this, fromIndex, toIndex) : 48651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski new SubList<>(this, fromIndex, toIndex)); 48751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 48851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 48951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski // Comparison and hashing 49051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 49151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 49251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Compares the specified object with this list for equality. Returns 49351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code true} if and only if the specified object is also a list, both 49451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * lists have the same size, and all corresponding pairs of elements in 49551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the two lists are <i>equal</i>. (Two elements {@code e1} and 49651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code e2} are <i>equal</i> if {@code (e1==null ? e2==null : 49751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * e1.equals(e2))}.) In other words, two lists are defined to be 49851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * equal if they contain the same elements in the same order.<p> 49951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 50051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This implementation first checks if the specified object is this 50151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * list. If so, it returns {@code true}; if not, it checks if the 50251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * specified object is a list. If not, it returns {@code false}; if so, 50351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * it iterates over both lists, comparing corresponding pairs of elements. 50451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * If any comparison returns {@code false}, this method returns 50551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code false}. If either iterator runs out of elements before the 50651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * other it returns {@code false} (as the lists are of unequal length); 50751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * otherwise it returns {@code true} when the iterations complete. 50851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 50951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param o the object to be compared for equality with this list 51051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return {@code true} if the specified object is equal to this list 51151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 51251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public boolean equals(Object o) { 51351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (o == this) 51451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return true; 51551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (!(o instanceof List)) 51651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return false; 51751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 51851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ListIterator<E> e1 = listIterator(); 519fee325d834eb37a26761e849c9becd7b9b4d3a12Tobias Thierer ListIterator<?> e2 = ((List<?>) o).listIterator(); 52051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski while (e1.hasNext() && e2.hasNext()) { 52151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E o1 = e1.next(); 52251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski Object o2 = e2.next(); 52351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (!(o1==null ? o2==null : o1.equals(o2))) 52451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return false; 52551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 52651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return !(e1.hasNext() || e2.hasNext()); 52751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 52851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 52951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 53051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Returns the hash code value for this list. 53151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 53251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This implementation uses exactly the code that is used to define the 53351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * list hash function in the documentation for the {@link List#hashCode} 53451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * method. 53551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 53651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @return the hash code value for this list 53751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 53851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public int hashCode() { 53951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int hashCode = 1; 54051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (E e : this) 54151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski hashCode = 31*hashCode + (e==null ? 0 : e.hashCode()); 54251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return hashCode; 54351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 54451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 54551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 54651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Removes from this list all of the elements whose index is between 54751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code fromIndex}, inclusive, and {@code toIndex}, exclusive. 54851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Shifts any succeeding elements to the left (reduces their index). 54951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * This call shortens the list by {@code (toIndex - fromIndex)} elements. 55051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * (If {@code toIndex==fromIndex}, this operation has no effect.) 55151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 55251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This method is called by the {@code clear} operation on this list 55351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * and its subLists. Overriding this method to take advantage of 55451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the internals of the list implementation can <i>substantially</i> 55551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * improve the performance of the {@code clear} operation on this list 55651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * and its subLists. 55751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 55851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This implementation gets a list iterator positioned before 55951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code fromIndex}, and repeatedly calls {@code ListIterator.next} 56051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * followed by {@code ListIterator.remove} until the entire range has 56151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * been removed. <b>Note: if {@code ListIterator.remove} requires linear 56251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * time, this implementation requires quadratic time.</b> 56351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 56451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param fromIndex index of first element to be removed 56551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * @param toIndex index after last element to be removed 56651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 56751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski protected void removeRange(int fromIndex, int toIndex) { 56851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ListIterator<E> it = listIterator(fromIndex); 56951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski for (int i=0, n=toIndex-fromIndex; i<n; i++) { 57051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski it.next(); 57151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski it.remove(); 57251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 57351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 57451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 57551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski /** 57651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * The number of times this list has been <i>structurally modified</i>. 57751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * Structural modifications are those that change the size of the 57851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * list, or otherwise perturb it in such a fashion that iterations in 57951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * progress may yield incorrect results. 58051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 58151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p>This field is used by the iterator and list iterator implementation 58251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * returned by the {@code iterator} and {@code listIterator} methods. 58351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * If the value of this field changes unexpectedly, the iterator (or list 58451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * iterator) will throw a {@code ConcurrentModificationException} in 58551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * response to the {@code next}, {@code remove}, {@code previous}, 58651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code set} or {@code add} operations. This provides 58751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <i>fail-fast</i> behavior, rather than non-deterministic behavior in 58851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * the face of concurrent modification during iteration. 58951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * 59051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * <p><b>Use of this field by subclasses is optional.</b> If a subclass 59151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * wishes to provide fail-fast iterators (and list iterators), then it 59251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * merely has to increment this field in its {@code add(int, E)} and 59351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code remove(int)} methods (and any other methods that it overrides 59451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * that result in structural modifications to the list). A single call to 59551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * {@code add(int, E)} or {@code remove(int)} must add no more than 59651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * one to this field, or the iterators (and list iterators) will throw 59751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * bogus {@code ConcurrentModificationExceptions}. If an implementation 59851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * does not wish to provide fail-fast iterators, this field may be 59951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski * ignored. 60051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski */ 60151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski protected transient int modCount = 0; 60251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 60351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void rangeCheckForAdd(int index) { 60451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (index < 0 || index > size()) 60551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 60651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 60751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 60851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private String outOfBoundsMsg(int index) { 60951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return "Index: "+index+", Size: "+size(); 61051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 61151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski} 61251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 61351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebskiclass SubList<E> extends AbstractList<E> { 61451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private final AbstractList<E> l; 61551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private final int offset; 61651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private int size; 61751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 61851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski SubList(AbstractList<E> list, int fromIndex, int toIndex) { 61951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (fromIndex < 0) 62051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new IndexOutOfBoundsException("fromIndex = " + fromIndex); 62151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (toIndex > list.size()) 62251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new IndexOutOfBoundsException("toIndex = " + toIndex); 62351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (fromIndex > toIndex) 62451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new IllegalArgumentException("fromIndex(" + fromIndex + 62551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski ") > toIndex(" + toIndex + ")"); 62651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski l = list; 62751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski offset = fromIndex; 62851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski size = toIndex - fromIndex; 62951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski this.modCount = l.modCount; 63051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 63151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 63251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public E set(int index, E element) { 63351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski rangeCheck(index); 63451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski checkForComodification(); 63551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return l.set(index+offset, element); 63651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 63751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 63851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public E get(int index) { 63951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski rangeCheck(index); 64051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski checkForComodification(); 64151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return l.get(index+offset); 64251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 64351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 64451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public int size() { 64551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski checkForComodification(); 64651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return size; 64751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 64851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 64951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public void add(int index, E element) { 65051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski rangeCheckForAdd(index); 65151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski checkForComodification(); 65251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski l.add(index+offset, element); 65351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski this.modCount = l.modCount; 65451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski size++; 65551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 65651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 65751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public E remove(int index) { 65851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski rangeCheck(index); 65951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski checkForComodification(); 66051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski E result = l.remove(index+offset); 66151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski this.modCount = l.modCount; 66251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski size--; 66351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return result; 66451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 66551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 66651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski protected void removeRange(int fromIndex, int toIndex) { 66751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski checkForComodification(); 66851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski l.removeRange(fromIndex+offset, toIndex+offset); 66951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski this.modCount = l.modCount; 67051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski size -= (toIndex-fromIndex); 67151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 67251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 67351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public boolean addAll(Collection<? extends E> c) { 67451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return addAll(size, c); 67551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 67651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 67751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public boolean addAll(int index, Collection<? extends E> c) { 67851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski rangeCheckForAdd(index); 67951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski int cSize = c.size(); 68051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (cSize==0) 68151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return false; 68251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 68351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski checkForComodification(); 68451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski l.addAll(offset+index, c); 68551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski this.modCount = l.modCount; 68651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski size += cSize; 68751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return true; 68851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 68951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 69051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public Iterator<E> iterator() { 69151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return listIterator(); 69251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 69351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 69451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public ListIterator<E> listIterator(final int index) { 69551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski checkForComodification(); 69651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski rangeCheckForAdd(index); 69751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 69851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return new ListIterator<E>() { 69951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private final ListIterator<E> i = l.listIterator(index+offset); 70051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 70151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public boolean hasNext() { 70251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return nextIndex() < size; 70351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 70451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 70551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public E next() { 70651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (hasNext()) 70751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return i.next(); 70851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski else 70951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new NoSuchElementException(); 71051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 71151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 71251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public boolean hasPrevious() { 71351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return previousIndex() >= 0; 71451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 71551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 71651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public E previous() { 71751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (hasPrevious()) 71851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return i.previous(); 71951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski else 72051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new NoSuchElementException(); 72151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 72251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 72351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public int nextIndex() { 72451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return i.nextIndex() - offset; 72551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 72651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 72751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public int previousIndex() { 72851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return i.previousIndex() - offset; 72951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 73051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 73151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public void remove() { 73251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski i.remove(); 73351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski SubList.this.modCount = l.modCount; 73451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski size--; 73551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 73651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 73751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public void set(E e) { 73851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski i.set(e); 73951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 74051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 74151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public void add(E e) { 74251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski i.add(e); 74351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski SubList.this.modCount = l.modCount; 74451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski size++; 74551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 74651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski }; 74751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 74851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 74951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public List<E> subList(int fromIndex, int toIndex) { 75051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return new SubList<>(this, fromIndex, toIndex); 75151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 75251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 75351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void rangeCheck(int index) { 75451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (index < 0 || index >= size) 75551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 75651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 75751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 75851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void rangeCheckForAdd(int index) { 75951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (index < 0 || index > size) 76051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new IndexOutOfBoundsException(outOfBoundsMsg(index)); 76151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 76251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 76351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private String outOfBoundsMsg(int index) { 76451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return "Index: "+index+", Size: "+size; 76551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 76651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 76751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski private void checkForComodification() { 76851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski if (this.modCount != l.modCount) 76951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski throw new ConcurrentModificationException(); 77051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 77151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski} 77251b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 77351b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebskiclass RandomAccessSubList<E> extends SubList<E> implements RandomAccess { 77451b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski RandomAccessSubList(AbstractList<E> list, int fromIndex, int toIndex) { 77551b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski super(list, fromIndex, toIndex); 77651b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 77751b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski 77851b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski public List<E> subList(int fromIndex, int toIndex) { 77951b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski return new RandomAccessSubList<>(this, fromIndex, toIndex); 78051b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski } 78151b1b6997fd3f980076b8081f7f1165ccc2a4008Piotr Jastrzebski} 782