1 /*
   2  * Copyright (c) 1997, 2014, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package javany.util;
  27 
  28 import javany.util.function.UnaryOperator;
  29 
  30 import java.util.Objects;
  31 
  32 /**
  33  * An ordered collection (also known as a <i>sequence</i>).  The user of this
  34  * interface has precise control over where in the list each element is
  35  * inserted.  The user can access elements by their integer index (position in
  36  * the list), and search for elements in the list.<p>
  37  *
  38  * Unlike sets, lists typically allow duplicate elements.  More formally,
  39  * lists typically allow pairs of elements <tt>e1</tt> and <tt>e2</tt>
  40  * such that <tt>e1.equals(e2)</tt>, and they typically allow multiple
  41  * null elements if they allow null elements at all.  It is not inconceivable
  42  * that someone might wish to implement a list that prohibits duplicates, by
  43  * throwing runtime exceptions when the user attempts to insert them, but we
  44  * expect this usage to be rare.<p>
  45  *
  46  * The <tt>List</tt> interface places additional stipulations, beyond those
  47  * specified in the <tt>Collection</tt> interface, on the contracts of the
  48  * <tt>iterator</tt>, <tt>add</tt>, <tt>remove</tt>, <tt>equals</tt>, and
  49  * <tt>hashCode</tt> methods.  Declarations for other inherited methods are
  50  * also included here for convenience.<p>
  51  *
  52  * The <tt>List</tt> interface provides four methods for positional (indexed)
  53  * access to list elements.  Lists (like Java arrays) are zero based.  Note
  54  * that these operations may execute in time proportional to the index value
  55  * for some implementations (the <tt>LinkedList</tt> class, for
  56  * example). Thus, iterating over the elements in a list is typically
  57  * preferable to indexing through it if the caller does not know the
  58  * implementation.<p>
  59  *
  60  * The <tt>List</tt> interface provides a special iterator, called a
  61  * <tt>ListIterator</tt>, that allows element insertion and replacement, and
  62  * bidirectional access in addition to the normal operations that the
  63  * <tt>Iterator</tt> interface provides.  A method is provided to obtain a
  64  * list iterator that starts at a specified position in the list.<p>
  65  *
  66  * The <tt>List</tt> interface provides two methods to search for a specified
  67  * object.  From a performance standpoint, these methods should be used with
  68  * caution.  In many implementations they will perform costly linear
  69  * searches.<p>
  70  *
  71  * The <tt>List</tt> interface provides two methods to efficiently insert and
  72  * remove multiple elements at an arbitrary point in the list.<p>
  73  *
  74  * Note: While it is permissible for lists to contain themselves as elements,
  75  * extreme caution is advised: the <tt>equals</tt> and <tt>hashCode</tt>
  76  * methods are no longer well defined on such a list.
  77  *
  78  * <p>Some list implementations have restrictions on the elements that
  79  * they may contain.  For example, some implementations prohibit null elements,
  80  * and some have restrictions on the types of their elements.  Attempting to
  81  * add an ineligible element throws an unchecked exception, typically
  82  * <tt>NullPointerException</tt> or <tt>ClassCastException</tt>.  Attempting
  83  * to query the presence of an ineligible element may throw an exception,
  84  * or it may simply return false; some implementations will exhibit the former
  85  * behavior and some will exhibit the latter.  More generally, attempting an
  86  * operation on an ineligible element whose completion would not result in
  87  * the insertion of an ineligible element into the list may throw an
  88  * exception or it may succeed, at the option of the implementation.
  89  * Such exceptions are marked as "optional" in the specification for this
  90  * interface.
  91  *
  92  * <p>This interface is a member of the
  93  * <a href="{@docRoot}/../technotes/guides/collections/index.html">
  94  * Java Collections Framework</a>.
  95  *
  96  * @param <E> the type of elements in this list
  97  *
  98  * @author  Josh Bloch
  99  * @author  Neal Gafter
 100  * @see Collection
 101  * @see Set
 102  * @see ArrayList
 103  * @see LinkedList
 104  * @see Vector
 105  * @see Arrays#asList(Object[])
 106  * @see Collections#nCopies(int, Object)
 107  * @see Collections#EMPTY_LIST
 108  * @see AbstractList
 109  * @see AbstractSequentialList
 110  * @since 1.2
 111  */
 112 
 113 public interface List<any E> extends Collection<E> {
 114     // Query Operations
 115 
 116     /**
 117      * Returns the number of elements in this list.  If this list contains
 118      * more than <tt>Integer.MAX_VALUE</tt> elements, returns
 119      * <tt>Integer.MAX_VALUE</tt>.
 120      *
 121      * @return the number of elements in this list
 122      */
 123     int size();
 124 
 125     /**
 126      * Returns <tt>true</tt> if this list contains no elements.
 127      *
 128      * @return <tt>true</tt> if this list contains no elements
 129      */
 130     boolean isEmpty();
 131 
 132     /**
 133      * Returns <tt>true</tt> if this list contains the specified element.
 134      * More formally, returns <tt>true</tt> if and only if this list contains
 135      * at least one element <tt>e</tt> such that
 136      * <tt>(o==null&nbsp;?&nbsp;e==null&nbsp;:&nbsp;o.equals(e))</tt>.
 137      *
 138      * @param o element whose presence in this list is to be tested
 139      * @return <tt>true</tt> if this list contains the specified element
 140      * @throws ClassCastException if the type of the specified element
 141      *         is incompatible with this list
 142      * (<a href="Collection.html#optional-restrictions">optional</a>)
 143      * @throws NullPointerException if the specified element is null and this
 144      *         list does not permit null elements
 145      * (<a href="Collection.html#optional-restrictions">optional</a>)
 146      */
 147     boolean contains(Object o);
 148 
 149     /**
 150      * Returns an iterator over the elements in this list in proper sequence.
 151      *
 152      * @return an iterator over the elements in this list in proper sequence
 153      */
 154     Iterator<E> iterator();
 155 
 156     /**
 157      * Returns an array containing all of the elements in this list in proper
 158      * sequence (from first to last element).
 159      *
 160      * <p>The returned array will be "safe" in that no references to it are
 161      * maintained by this list.  (In other words, this method must
 162      * allocate a new array even if this list is backed by an array).
 163      * The caller is thus free to modify the returned array.
 164      *
 165      * <p>This method acts as bridge between array-based and collection-based
 166      * APIs.
 167      *
 168      * @return an array containing all of the elements in this list in proper
 169      *         sequence
 170      * @see Arrays#asList(Object[])
 171      */
 172     Object[] toArray();
 173 
 174     /**
 175      * Returns an array containing all of the elements in this list in
 176      * proper sequence (from first to last element); the runtime type of
 177      * the returned array is that of the specified array.  If the list fits
 178      * in the specified array, it is returned therein.  Otherwise, a new
 179      * array is allocated with the runtime type of the specified array and
 180      * the size of this list.
 181      *
 182      * <p>If the list fits in the specified array with room to spare (i.e.,
 183      * the array has more elements than the list), the element in the array
 184      * immediately following the end of the list is set to <tt>null</tt>.
 185      * (This is useful in determining the length of the list <i>only</i> if
 186      * the caller knows that the list does not contain any null elements.)
 187      *
 188      * <p>Like the {@link #toArray()} method, this method acts as bridge between
 189      * array-based and collection-based APIs.  Further, this method allows
 190      * precise control over the runtime type of the output array, and may,
 191      * under certain circumstances, be used to save allocation costs.
 192      *
 193      * <p>Suppose <tt>x</tt> is a list known to contain only strings.
 194      * The following code can be used to dump the list into a newly
 195      * allocated array of <tt>String</tt>:
 196      *
 197      * <pre>{@code
 198      *     String[] y = x.toArray(new String[0]);
 199      * }</pre>
 200      *
 201      * Note that <tt>toArray(new Object[0])</tt> is identical in function to
 202      * <tt>toArray()</tt>.
 203      *
 204      * @param a the array into which the elements of this list are to
 205      *          be stored, if it is big enough; otherwise, a new array of the
 206      *          same runtime type is allocated for this purpose.
 207      * @return an array containing the elements of this list
 208      * @throws ArrayStoreException if the runtime type of the specified array
 209      *         is not a supertype of the runtime type of every element in
 210      *         this list
 211      * @throws NullPointerException if the specified array is null
 212      */
 213     <any T> T[] toArray(T[] a);
 214 
 215 
 216     // Modification Operations
 217 
 218     /**
 219      * Appends the specified element to the end of this list (optional
 220      * operation).
 221      *
 222      * <p>Lists that support this operation may place limitations on what
 223      * elements may be added to this list.  In particular, some
 224      * lists will refuse to add null elements, and others will impose
 225      * restrictions on the type of elements that may be added.  List
 226      * classes should clearly specify in their documentation any restrictions
 227      * on what elements may be added.
 228      *
 229      * @param e element to be appended to this list
 230      * @return <tt>true</tt> (as specified by {@link Collection#add})
 231      * @throws UnsupportedOperationException if the <tt>add</tt> operation
 232      *         is not supported by this list
 233      * @throws ClassCastException if the class of the specified element
 234      *         prevents it from being added to this list
 235      * @throws NullPointerException if the specified element is null and this
 236      *         list does not permit null elements
 237      * @throws IllegalArgumentException if some property of this element
 238      *         prevents it from being added to this list
 239      */
 240     boolean add(E e);
 241 
 242     /**
 243      * Removes the first occurrence of the specified element from this list,
 244      * if it is present (optional operation).  If this list does not contain
 245      * the element, it is unchanged.  More formally, removes the element with
 246      * the lowest index <tt>i</tt> such that
 247      * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>
 248      * (if such an element exists).  Returns <tt>true</tt> if this list
 249      * contained the specified element (or equivalently, if this list changed
 250      * as a result of the call).
 251      *
 252      * @param o element to be removed from this list, if present
 253      * @return <tt>true</tt> if this list contained the specified element
 254      * @throws ClassCastException if the type of the specified element
 255      *         is incompatible with this list
 256      * (<a href="Collection.html#optional-restrictions">optional</a>)
 257      * @throws NullPointerException if the specified element is null and this
 258      *         list does not permit null elements
 259      * (<a href="Collection.html#optional-restrictions">optional</a>)
 260      * @throws UnsupportedOperationException if the <tt>remove</tt> operation
 261      *         is not supported by this list
 262      */
 263     boolean remove(Object o);
 264 
 265 
 266     // Bulk Modification Operations
 267 
 268     /**
 269      * Returns <tt>true</tt> if this list contains all of the elements of the
 270      * specified collection.
 271      *
 272      * @param  c collection to be checked for containment in this list
 273      * @return <tt>true</tt> if this list contains all of the elements of the
 274      *         specified collection
 275      * @throws ClassCastException if the types of one or more elements
 276      *         in the specified collection are incompatible with this
 277      *         list
 278      * (<a href="Collection.html#optional-restrictions">optional</a>)
 279      * @throws NullPointerException if the specified collection contains one
 280      *         or more null elements and this list does not permit null
 281      *         elements
 282      *         (<a href="Collection.html#optional-restrictions">optional</a>),
 283      *         or if the specified collection is null
 284      * @see #contains(Object)
 285      */
 286     boolean containsAll(Collection<?> c);
 287 
 288     /**
 289      * Appends all of the elements in the specified collection to the end of
 290      * this list, in the order that they are returned by the specified
 291      * collection's iterator (optional operation).  The behavior of this
 292      * operation is undefined if the specified collection is modified while
 293      * the operation is in progress.  (Note that this will occur if the
 294      * specified collection is this list, and it's nonempty.)
 295      *
 296      * @param c collection containing elements to be added to this list
 297      * @return <tt>true</tt> if this list changed as a result of the call
 298      * @throws UnsupportedOperationException if the <tt>addAll</tt> operation
 299      *         is not supported by this list
 300      * @throws ClassCastException if the class of an element of the specified
 301      *         collection prevents it from being added to this list
 302      * @throws NullPointerException if the specified collection contains one
 303      *         or more null elements and this list does not permit null
 304      *         elements, or if the specified collection is null
 305      * @throws IllegalArgumentException if some property of an element of the
 306      *         specified collection prevents it from being added to this list
 307      * @see #add(Object)
 308      */
 309     boolean addAll(Collection<? extends E> c);
 310 
 311     /**
 312      * Inserts all of the elements in the specified collection into this
 313      * list at the specified position (optional operation).  Shifts the
 314      * element currently at that position (if any) and any subsequent
 315      * elements to the right (increases their indices).  The new elements
 316      * will appear in this list in the order that they are returned by the
 317      * specified collection's iterator.  The behavior of this operation is
 318      * undefined if the specified collection is modified while the
 319      * operation is in progress.  (Note that this will occur if the specified
 320      * collection is this list, and it's nonempty.)
 321      *
 322      * @param index index at which to insert the first element from the
 323      *              specified collection
 324      * @param c collection containing elements to be added to this list
 325      * @return <tt>true</tt> if this list changed as a result of the call
 326      * @throws UnsupportedOperationException if the <tt>addAll</tt> operation
 327      *         is not supported by this list
 328      * @throws ClassCastException if the class of an element of the specified
 329      *         collection prevents it from being added to this list
 330      * @throws NullPointerException if the specified collection contains one
 331      *         or more null elements and this list does not permit null
 332      *         elements, or if the specified collection is null
 333      * @throws IllegalArgumentException if some property of an element of the
 334      *         specified collection prevents it from being added to this list
 335      * @throws IndexOutOfBoundsException if the index is out of range
 336      *         (<tt>index &lt; 0 || index &gt; size()</tt>)
 337      */
 338     boolean addAll(int index, Collection<? extends E> c);
 339 
 340     /**
 341      * Removes from this list all of its elements that are contained in the
 342      * specified collection (optional operation).
 343      *
 344      * @param c collection containing elements to be removed from this list
 345      * @return <tt>true</tt> if this list changed as a result of the call
 346      * @throws UnsupportedOperationException if the <tt>removeAll</tt> operation
 347      *         is not supported by this list
 348      * @throws ClassCastException if the class of an element of this list
 349      *         is incompatible with the specified collection
 350      * (<a href="Collection.html#optional-restrictions">optional</a>)
 351      * @throws NullPointerException if this list contains a null element and the
 352      *         specified collection does not permit null elements
 353      *         (<a href="Collection.html#optional-restrictions">optional</a>),
 354      *         or if the specified collection is null
 355      * @see #remove(Object)
 356      * @see #contains(Object)
 357      */
 358     boolean removeAll(Collection<?> c);
 359 
 360     /**
 361      * Retains only the elements in this list that are contained in the
 362      * specified collection (optional operation).  In other words, removes
 363      * from this list all of its elements that are not contained in the
 364      * specified collection.
 365      *
 366      * @param c collection containing elements to be retained in this list
 367      * @return <tt>true</tt> if this list changed as a result of the call
 368      * @throws UnsupportedOperationException if the <tt>retainAll</tt> operation
 369      *         is not supported by this list
 370      * @throws ClassCastException if the class of an element of this list
 371      *         is incompatible with the specified collection
 372      * (<a href="Collection.html#optional-restrictions">optional</a>)
 373      * @throws NullPointerException if this list contains a null element and the
 374      *         specified collection does not permit null elements
 375      *         (<a href="Collection.html#optional-restrictions">optional</a>),
 376      *         or if the specified collection is null
 377      * @see #remove(Object)
 378      * @see #contains(Object)
 379      */
 380     boolean retainAll(Collection<?> c);
 381 
 382     /**
 383      * Replaces each element of this list with the result of applying the
 384      * operator to that element.  Errors or runtime exceptions thrown by
 385      * the operator are relayed to the caller.
 386      *
 387      * @implSpec
 388      * The default implementation is equivalent to, for this {@code list}:
 389      * <pre>{@code
 390      *     final ListIterator<E> li = list.listIterator();
 391      *     while (li.hasNext()) {
 392      *         li.set(operator.apply(li.next()));
 393      *     }
 394      * }</pre>
 395      *
 396      * If the list's list-iterator does not support the {@code set} operation
 397      * then an {@code UnsupportedOperationException} will be thrown when
 398      * replacing the first element.
 399      *
 400      * @param operator the operator to apply to each element
 401      * @throws UnsupportedOperationException if this list is unmodifiable.
 402      *         Implementations may throw this exception if an element
 403      *         cannot be replaced or if, in general, modification is not
 404      *         supported
 405      * @throws NullPointerException if the specified operator is null or
 406      *         if the operator result is a null value and this list does
 407      *         not permit null elements
 408      *         (<a href="Collection.html#optional-restrictions">optional</a>)
 409      * @since 1.8
 410      */
 411     default void replaceAll(UnaryOperator<E> operator) {
 412         Objects.requireNonNull(operator);
 413         final ListIterator<E> li = this.listIterator();
 414         while (li.hasNext()) {
 415             li.set(operator.apply(li.next()));
 416         }
 417     }
 418 
 419     /**
 420      * Sorts this list according to the order induced by the specified
 421      * {@link Comparator}.
 422      *
 423      * <p>All elements in this list must be <i>mutually comparable</i> using the
 424      * specified comparator (that is, {@code c.compare(e1, e2)} must not throw
 425      * a {@code ClassCastException} for any elements {@code e1} and {@code e2}
 426      * in the list).
 427      *
 428      * <p>If the specified comparator is {@code null} then all elements in this
 429      * list must implement the {@link Comparable} interface and the elements'
 430      * {@linkplain Comparable natural ordering} should be used.
 431      *
 432      * <p>This list must be modifiable, but need not be resizable.
 433      *
 434      * @implSpec
 435      * The default implementation obtains an array containing all elements in
 436      * this list, sorts the array, and iterates over this list resetting each
 437      * element from the corresponding position in the array. (This avoids the
 438      * n<sup>2</sup> log(n) performance that would result from attempting
 439      * to sort a linked list in place.)
 440      *
 441      * @implNote
 442      * This implementation is a stable, adaptive, iterative mergesort that
 443      * requires far fewer than n lg(n) comparisons when the input array is
 444      * partially sorted, while offering the performance of a traditional
 445      * mergesort when the input array is randomly ordered.  If the input array
 446      * is nearly sorted, the implementation requires approximately n
 447      * comparisons.  Temporary storage requirements vary from a small constant
 448      * for nearly sorted input arrays to n/2 object references for randomly
 449      * ordered input arrays.
 450      *
 451      * <p>The implementation takes equal advantage of ascending and
 452      * descending order in its input array, and can take advantage of
 453      * ascending and descending order in different parts of the same
 454      * input array.  It is well-suited to merging two or more sorted arrays:
 455      * simply concatenate the arrays and sort the resulting array.
 456      *
 457      * <p>The implementation was adapted from Tim Peters's list sort for Python
 458      * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt">
 459      * TimSort</a>).  It uses techniques from Peter McIlroy's "Optimistic
 460      * Sorting and Information Theoretic Complexity", in Proceedings of the
 461      * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474,
 462      * January 1993.
 463      *
 464      * @param c the {@code Comparator} used to compare list elements.
 465      *          A {@code null} value indicates that the elements'
 466      *          {@linkplain Comparable natural ordering} should be used
 467      * @throws ClassCastException if the list contains elements that are not
 468      *         <i>mutually comparable</i> using the specified comparator
 469      * @throws UnsupportedOperationException if the list's list-iterator does
 470      *         not support the {@code set} operation
 471      * @throws IllegalArgumentException
 472      *         (<a href="Collection.html#optional-restrictions">optional</a>)
 473      *         if the comparator is found to violate the {@link Comparator}
 474      *         contract
 475      * @since 1.8
 476      */
 477     @SuppressWarnings({"unchecked", "rawtypes"})
 478     default void sort(Comparator<? super E> c) {
 479         E[] a = this.toArray(new E[size()]);
 480         Arrays.sort(a, c);
 481         ListIterator<E> i = this.listIterator();
 482         for (E e : a) {
 483             i.next();
 484             i.set(e);
 485         }
 486     }
 487 
 488     /**
 489      * Removes all of the elements from this list (optional operation).
 490      * The list will be empty after this call returns.
 491      *
 492      * @throws UnsupportedOperationException if the <tt>clear</tt> operation
 493      *         is not supported by this list
 494      */
 495     void clear();
 496 
 497 
 498     // Comparison and hashing
 499 
 500     /**
 501      * Compares the specified object with this list for equality.  Returns
 502      * <tt>true</tt> if and only if the specified object is also a list, both
 503      * lists have the same size, and all corresponding pairs of elements in
 504      * the two lists are <i>equal</i>.  (Two elements <tt>e1</tt> and
 505      * <tt>e2</tt> are <i>equal</i> if <tt>(e1==null ? e2==null :
 506      * e1.equals(e2))</tt>.)  In other words, two lists are defined to be
 507      * equal if they contain the same elements in the same order.  This
 508      * definition ensures that the equals method works properly across
 509      * different implementations of the <tt>List</tt> interface.
 510      *
 511      * @param o the object to be compared for equality with this list
 512      * @return <tt>true</tt> if the specified object is equal to this list
 513      */
 514     boolean equals(Object o);
 515 
 516     /**
 517      * Returns the hash code value for this list.  The hash code of a list
 518      * is defined to be the result of the following calculation:
 519      * <pre>{@code
 520      *     int hashCode = 1;
 521      *     for (E e : list)
 522      *         hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
 523      * }</pre>
 524      * This ensures that <tt>list1.equals(list2)</tt> implies that
 525      * <tt>list1.hashCode()==list2.hashCode()</tt> for any two lists,
 526      * <tt>list1</tt> and <tt>list2</tt>, as required by the general
 527      * contract of {@link Object#hashCode}.
 528      *
 529      * @return the hash code value for this list
 530      * @see Object#equals(Object)
 531      * @see #equals(Object)
 532      */
 533     int hashCode();
 534 
 535 
 536     // Positional Access Operations
 537 
 538     /**
 539      * Returns the element at the specified position in this list.
 540      *
 541      * @param index index of the element to return
 542      * @return the element at the specified position in this list
 543      * @throws IndexOutOfBoundsException if the index is out of range
 544      *         (<tt>index &lt; 0 || index &gt;= size()</tt>)
 545      */
 546     E get(int index);
 547 
 548     /**
 549      * Replaces the element at the specified position in this list with the
 550      * specified element (optional operation).
 551      *
 552      * @param index index of the element to replace
 553      * @param element element to be stored at the specified position
 554      * @return the element previously at the specified position
 555      * @throws UnsupportedOperationException if the <tt>set</tt> operation
 556      *         is not supported by this list
 557      * @throws ClassCastException if the class of the specified element
 558      *         prevents it from being added to this list
 559      * @throws NullPointerException if the specified element is null and
 560      *         this list does not permit null elements
 561      * @throws IllegalArgumentException if some property of the specified
 562      *         element prevents it from being added to this list
 563      * @throws IndexOutOfBoundsException if the index is out of range
 564      *         (<tt>index &lt; 0 || index &gt;= size()</tt>)
 565      */
 566     E set(int index, E element);
 567 
 568     /**
 569      * Inserts the specified element at the specified position in this list
 570      * (optional operation).  Shifts the element currently at that position
 571      * (if any) and any subsequent elements to the right (adds one to their
 572      * indices).
 573      *
 574      * @param index index at which the specified element is to be inserted
 575      * @param element element to be inserted
 576      * @throws UnsupportedOperationException if the <tt>add</tt> operation
 577      *         is not supported by this list
 578      * @throws ClassCastException if the class of the specified element
 579      *         prevents it from being added to this list
 580      * @throws NullPointerException if the specified element is null and
 581      *         this list does not permit null elements
 582      * @throws IllegalArgumentException if some property of the specified
 583      *         element prevents it from being added to this list
 584      * @throws IndexOutOfBoundsException if the index is out of range
 585      *         (<tt>index &lt; 0 || index &gt; size()</tt>)
 586      */
 587     void add(int index, E element);
 588 
 589     /**
 590      * Removes the element at the specified position in this list (optional
 591      * operation).  Shifts any subsequent elements to the left (subtracts one
 592      * from their indices).  Returns the element that was removed from the
 593      * list.
 594      *
 595      * @param index the index of the element to be removed
 596      * @return the element previously at the specified position
 597      * @throws UnsupportedOperationException if the <tt>remove</tt> operation
 598      *         is not supported by this list
 599      * @throws IndexOutOfBoundsException if the index is out of range
 600      *         (<tt>index &lt; 0 || index &gt;= size()</tt>)
 601      */
 602     E remove(int index);
 603 
 604 
 605     // Search Operations
 606 
 607     /**
 608      * Returns the index of the first occurrence of the specified element
 609      * in this list, or -1 if this list does not contain the element.
 610      * More formally, returns the lowest index <tt>i</tt> such that
 611      * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
 612      * or -1 if there is no such index.
 613      *
 614      * @param o element to search for
 615      * @return the index of the first occurrence of the specified element in
 616      *         this list, or -1 if this list does not contain the element
 617      * @throws ClassCastException if the type of the specified element
 618      *         is incompatible with this list
 619      *         (<a href="Collection.html#optional-restrictions">optional</a>)
 620      * @throws NullPointerException if the specified element is null and this
 621      *         list does not permit null elements
 622      *         (<a href="Collection.html#optional-restrictions">optional</a>)
 623      */
 624     int indexOf(Object o);
 625 
 626     default int indexOfElement(E e) {
 627         ListIterator<E> it = listIterator();
 628         while (it.hasNext())
 629             if (Any.equals(e, it.next()))
 630                 return it.previousIndex();
 631         return -1;
 632     }
 633 
 634     /**
 635      * Returns the index of the last occurrence of the specified element
 636      * in this list, or -1 if this list does not contain the element.
 637      * More formally, returns the highest index <tt>i</tt> such that
 638      * <tt>(o==null&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;o.equals(get(i)))</tt>,
 639      * or -1 if there is no such index.
 640      *
 641      * @param o element to search for
 642      * @return the index of the last occurrence of the specified element in
 643      *         this list, or -1 if this list does not contain the element
 644      * @throws ClassCastException if the type of the specified element
 645      *         is incompatible with this list
 646      *         (<a href="Collection.html#optional-restrictions">optional</a>)
 647      * @throws NullPointerException if the specified element is null and this
 648      *         list does not permit null elements
 649      *         (<a href="Collection.html#optional-restrictions">optional</a>)
 650      */
 651     int lastIndexOf(Object o);
 652 
 653     default int lastIndexOfElement(E e) {
 654         ListIterator<E> it = listIterator(size());
 655         while (it.hasPrevious())
 656             if (Any.equals(e, it.previous()))
 657                 return it.nextIndex();
 658         return -1;
 659     }
 660 
 661     // List Iterators
 662 
 663     /**
 664      * Returns a list iterator over the elements in this list (in proper
 665      * sequence).
 666      *
 667      * @return a list iterator over the elements in this list (in proper
 668      *         sequence)
 669      */
 670     ListIterator<E> listIterator();
 671 
 672     /**
 673      * Returns a list iterator over the elements in this list (in proper
 674      * sequence), starting at the specified position in the list.
 675      * The specified index indicates the first element that would be
 676      * returned by an initial call to {@link ListIterator#next next}.
 677      * An initial call to {@link ListIterator#previous previous} would
 678      * return the element with the specified index minus one.
 679      *
 680      * @param index index of the first element to be returned from the
 681      *        list iterator (by a call to {@link ListIterator#next next})
 682      * @return a list iterator over the elements in this list (in proper
 683      *         sequence), starting at the specified position in the list
 684      * @throws IndexOutOfBoundsException if the index is out of range
 685      *         ({@code index < 0 || index > size()})
 686      */
 687     ListIterator<E> listIterator(int index);
 688 
 689     // View
 690 
 691     /**
 692      * Returns a view of the portion of this list between the specified
 693      * <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive.  (If
 694      * <tt>fromIndex</tt> and <tt>toIndex</tt> are equal, the returned list is
 695      * empty.)  The returned list is backed by this list, so non-structural
 696      * changes in the returned list are reflected in this list, and vice-versa.
 697      * The returned list supports all of the optional list operations supported
 698      * by this list.<p>
 699      *
 700      * This method eliminates the need for explicit range operations (of
 701      * the sort that commonly exist for arrays).  Any operation that expects
 702      * a list can be used as a range operation by passing a subList view
 703      * instead of a whole list.  For example, the following idiom
 704      * removes a range of elements from a list:
 705      * <pre>{@code
 706      *      list.subList(from, to).clear();
 707      * }</pre>
 708      * Similar idioms may be constructed for <tt>indexOf</tt> and
 709      * <tt>lastIndexOf</tt>, and all of the algorithms in the
 710      * <tt>Collections</tt> class can be applied to a subList.<p>
 711      *
 712      * The semantics of the list returned by this method become undefined if
 713      * the backing list (i.e., this list) is <i>structurally modified</i> in
 714      * any way other than via the returned list.  (Structural modifications are
 715      * those that change the size of this list, or otherwise perturb it in such
 716      * a fashion that iterations in progress may yield incorrect results.)
 717      *
 718      * @param fromIndex low endpoint (inclusive) of the subList
 719      * @param toIndex high endpoint (exclusive) of the subList
 720      * @return a view of the specified range within this list
 721      * @throws IndexOutOfBoundsException for an illegal endpoint index value
 722      *         (<tt>fromIndex &lt; 0 || toIndex &gt; size ||
 723      *         fromIndex &gt; toIndex</tt>)
 724      */
 725     List<E> subList(int fromIndex, int toIndex);
 726 
 727     /**
 728      * Creates a {@link Spliterator} over the elements in this list.
 729      *
 730      * <p>The {@code Spliterator} reports {@link Spliterator#SIZED} and
 731      * {@link Spliterator#ORDERED}.  Implementations should document the
 732      * reporting of additional characteristic values.
 733      *
 734      * @implSpec
 735      * The default implementation creates a
 736      * <em><a href="Spliterator.html#binding">late-binding</a></em> spliterator
 737      * from the list's {@code Iterator}.  The spliterator inherits the
 738      * <em>fail-fast</em> properties of the list's iterator.
 739      *
 740      * @implNote
 741      * The created {@code Spliterator} additionally reports
 742      * {@link Spliterator#SUBSIZED}.
 743      *
 744      * @return a {@code Spliterator} over the elements in this list
 745      * @since 1.8
 746      */
 747 //    @Override
 748 //    default Spliterator<E> spliterator() {
 749 //        return Spliterators.spliterator(this, Spliterator.ORDERED);
 750 //    }
 751 }