1 /* 2 * Hunt - A refined core library for D programming language. 3 * 4 * Copyright (C) 2018-2019 HuntLabs 5 * 6 * Website: https://www.huntlabs.net/ 7 * 8 * Licensed under the Apache-2.0 License. 9 * 10 */ 11 12 module hunt.collection.List; 13 14 import hunt.collection.Collection; 15 import hunt.util.Comparator; 16 import std.traits; 17 18 /** 19 */ 20 21 interface List(E) : Collection!E { 22 23 /** 24 * Appends all of the elements in the specified collection to the end of 25 * this list, in the order that they are returned by the specified 26 * collection's iterator (optional operation). The behavior of this 27 * operation is undefined if the specified collection is modified while 28 * the operation is in progress. (Note that this will occur if the 29 * specified collection is this list, and it's nonempty.) 30 * 31 * @param c collection containing elements to be added to this list 32 * @return <tt>true</tt> if this list changed as a result of the call 33 * @throws UnsupportedOperationException if the <tt>addAll</tt> operation 34 * is not supported by this list 35 * @throws ClassCastException if the class of an element of the specified 36 * collection prevents it from being added to this list 37 * @throws NullPointerException if the specified collection contains one 38 * or more null elements and this list does not permit null 39 * elements, or if the specified collection is null 40 * @throws IllegalArgumentException if some property of an element of the 41 * specified collection prevents it from being added to this list 42 * @see #add(Object) 43 */ 44 // bool addAll(Collection!E c); 45 46 /** 47 * Inserts all of the elements in the specified collection into this 48 * list at the specified position (optional operation). Shifts the 49 * element currently at that position (if any) and any subsequent 50 * elements to the right (increases their indices). The new elements 51 * will appear in this list in the order that they are returned by the 52 * specified collection's iterator. The behavior of this operation is 53 * undefined if the specified collection is modified while the 54 * operation is in progress. (Note that this will occur if the specified 55 * collection is this list, and it's nonempty.) 56 * 57 * @param index index at which to insert the first element from the 58 * specified collection 59 * @param c collection containing elements to be added to this list 60 * @return <tt>true</tt> if this list changed as a result of the call 61 * @throws UnsupportedOperationException if the <tt>addAll</tt> operation 62 * is not supported by this list 63 * @throws ClassCastException if the class of an element of the specified 64 * collection prevents it from being added to this list 65 * @throws NullPointerException if the specified collection contains one 66 * or more null elements and this list does not permit null 67 * elements, or if the specified collection is null 68 * @throws IllegalArgumentException if some property of an element of the 69 * specified collection prevents it from being added to this list 70 * @throws IndexOutOfBoundsException if the index is out of range 71 * (<tt>index < 0 || index > size()</tt>) 72 */ 73 // bool addAll(int index, Collection!E c); 74 75 76 /** 77 * Replaces each element of this list with the result of applying the 78 * operator to that element. Errors or runtime exceptions thrown by 79 * the operator are relayed to the caller. 80 * 81 * @implSpec 82 * The final implementation is equivalent to, for this {@code list}: 83 * <pre>{@code 84 * final ListIterator<E> li = list.listIterator(); 85 * while (li.hasNext()) { 86 * li.set(operator.apply(li.next())); 87 * } 88 * }</pre> 89 * 90 * If the list's list-iterator does not support the {@code set} operation 91 * then an {@code UnsupportedOperationException} will be thrown when 92 * replacing the first element. 93 * 94 * @param operator the operator to apply to each element 95 * @throws UnsupportedOperationException if this list is unmodifiable. 96 * Implementations may throw this exception if an element 97 * cannot be replaced or if, in general, modification is not 98 * supported 99 * @throws NullPointerException if the specified operator is null or 100 * if the operator result is a null value and this list does 101 * not permit null elements 102 * (<a href="Collection.html#optional-restrictions">optional</a>) 103 * @since 1.8 104 */ 105 // final void replaceAll(UnaryOperator<E> operator) { 106 // Objects.requireNonNull(operator); 107 // final ListIterator<E> li = this.listIterator(); 108 // while (li.hasNext()) { 109 // li.set(operator.apply(li.next())); 110 // } 111 // } 112 113 /** 114 * Sorts this list according to the order induced by the specified 115 * {@link Comparator}. 116 * 117 * <p>All elements in this list must be <i>mutually comparable</i> using the 118 * specified comparator (that is, {@code c.compare(e1, e2)} must not throw 119 * a {@code ClassCastException} for any elements {@code e1} and {@code e2} 120 * in the list). 121 * 122 * <p>If the specified comparator is {@code null} then all elements in this 123 * list must implement the {@link Comparable} interface and the elements' 124 * {@linkplain Comparable natural ordering} should be used. 125 * 126 * <p>This list must be modifiable, but need not be resizable. 127 * 128 * @implSpec 129 * The final implementation obtains an array containing all elements in 130 * this list, sorts the array, and iterates over this list resetting each 131 * element from the corresponding position in the array. (This avoids the 132 * n<sup>2</sup> log(n) performance that would result from attempting 133 * to sort a linked list in place.) 134 * 135 * @implNote 136 * This implementation is a stable, adaptive, iterative mergesort that 137 * requires far fewer than n lg(n) comparisons when the input array is 138 * partially sorted, while offering the performance of a traditional 139 * mergesort when the input array is randomly ordered. If the input array 140 * is nearly sorted, the implementation requires approximately n 141 * comparisons. Temporary storage requirements vary from a small constant 142 * for nearly sorted input arrays to n/2 object references for randomly 143 * ordered input arrays. 144 * 145 * <p>The implementation takes equal advantage of ascending and 146 * descending order in its input array, and can take advantage of 147 * ascending and descending order in different parts of the same 148 * input array. It is well-suited to merging two or more sorted arrays: 149 * simply concatenate the arrays and sort the resulting array. 150 * 151 * <p>The implementation was adapted from Tim Peters's list sort for Python 152 * (<a href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt"> 153 * TimSort</a>). It uses techniques from Peter McIlroy's "Optimistic 154 * Sorting and Information Theoretic Complexity", in Proceedings of the 155 * Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, 156 * January 1993. 157 * 158 * @param c the {@code Comparator} used to compare list elements. 159 * A {@code null} value indicates that the elements' 160 * {@linkplain Comparable natural ordering} should be used 161 * @throws ClassCastException if the list contains elements that are not 162 * <i>mutually comparable</i> using the specified comparator 163 * @throws UnsupportedOperationException if the list's list-iterator does 164 * not support the {@code set} operation 165 * @throws IllegalArgumentException 166 * (<a href="Collection.html#optional-restrictions">optional</a>) 167 * if the comparator is found to violate the {@link Comparator} 168 * contract 169 * @since 1.8 170 */ 171 void sort(Comparator!E c) ; 172 173 static if (isOrderingComparable!E) { 174 void sort(bool isAscending = true); 175 } 176 // 177 // final void sort(Comparator<E> c) { 178 // Object[] a = this.toArray(); 179 // Arrays.sort(a, (Comparator) c); 180 // ListIterator<E> i = this.listIterator(); 181 // for (Object e : a) { 182 // i.next(); 183 // i.set((E) e); 184 // } 185 // } 186 187 188 189 // Positional Access Operations 190 191 /** 192 * Returns the element at the specified position in this list. 193 * 194 * @param index index of the element to return 195 * @return the element at the specified position in this list 196 * @throws IndexOutOfBoundsException if the index is out of range 197 * (<tt>index < 0 || index >= size()</tt>) 198 */ 199 E get(int index); 200 201 E opIndex(int index); 202 203 /** 204 * Replaces the element at the specified position in this list with the 205 * specified element (optional operation). 206 * 207 * @param index index of the element to replace 208 * @param element element to be stored at the specified position 209 * @return the element previously at the specified position 210 * @throws UnsupportedOperationException if the <tt>set</tt> operation 211 * is not supported by this list 212 * @throws ClassCastException if the class of the specified element 213 * prevents it from being added to this list 214 * @throws NullPointerException if the specified element is null and 215 * this list does not permit null elements 216 * @throws IllegalArgumentException if some property of the specified 217 * element prevents it from being added to this list 218 * @throws IndexOutOfBoundsException if the index is out of range 219 * (<tt>index < 0 || index >= size()</tt>) 220 */ 221 E set(int index, E element); 222 223 /** 224 * Inserts the specified element at the specified position in this list 225 * (optional operation). Shifts the element currently at that position 226 * (if any) and any subsequent elements to the right (adds one to their 227 * indices). 228 * 229 * @param index index at which the specified element is to be inserted 230 * @param element element to be inserted 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 236 * this list does not permit null elements 237 * @throws IllegalArgumentException if some property of the specified 238 * element prevents it from being added to this list 239 * @throws IndexOutOfBoundsException if the index is out of range 240 * (<tt>index < 0 || index > size()</tt>) 241 */ 242 void add(int index, E element); 243 244 alias add = Collection!E.add; 245 246 /** 247 * Removes the element at the specified position in this list (optional 248 * operation). Shifts any subsequent elements to the left (subtracts one 249 * from their indices). Returns the element that was removed from the 250 * list. 251 * 252 * @param index the index of the element to be removed 253 * @return the element previously at the specified position 254 * @throws UnsupportedOperationException if the <tt>remove</tt> operation 255 * is not supported by this list 256 * @throws IndexOutOfBoundsException if the index is out of range 257 * (<tt>index < 0 || index >= size()</tt>) 258 */ 259 E removeAt(int index); 260 261 alias remove = Collection!E.remove; 262 263 // Search Operations 264 265 /** 266 * Returns the index of the first occurrence of the specified element 267 * in this list, or -1 if this list does not contain the element. 268 * More formally, returns the lowest index <tt>i</tt> such that 269 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, 270 * or -1 if there is no such index. 271 * 272 * @param o element to search for 273 * @return the index of the first occurrence of the specified element in 274 * this list, or -1 if this list does not contain the element 275 * @throws ClassCastException if the type of the specified element 276 * is incompatible with this list 277 * (<a href="Collection.html#optional-restrictions">optional</a>) 278 * @throws NullPointerException if the specified element is null and this 279 * list does not permit null elements 280 * (<a href="Collection.html#optional-restrictions">optional</a>) 281 */ 282 int indexOf(E o); 283 284 /** 285 * Returns the index of the last occurrence of the specified element 286 * in this list, or -1 if this list does not contain the element. 287 * More formally, returns the highest index <tt>i</tt> such that 288 * <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>, 289 * or -1 if there is no such index. 290 * 291 * @param o element to search for 292 * @return the index of the last occurrence of the specified element in 293 * this list, or -1 if this list does not contain the element 294 * @throws ClassCastException if the type of the specified element 295 * is incompatible with this list 296 * (<a href="Collection.html#optional-restrictions">optional</a>) 297 * @throws NullPointerException if the specified element is null and this 298 * list does not permit null elements 299 * (<a href="Collection.html#optional-restrictions">optional</a>) 300 */ 301 int lastIndexOf(E o); 302 303 304 // List Iterators 305 306 /** 307 * Returns a list iterator over the elements in this list (in proper 308 * sequence). 309 * 310 * @return a list iterator over the elements in this list (in proper 311 * sequence) 312 */ 313 // ListIterator<E> listIterator(); 314 315 /** 316 * Returns a list iterator over the elements in this list (in proper 317 * sequence), starting at the specified position in the list. 318 * The specified index indicates the first element that would be 319 * returned by an initial call to {@link ListIterator#next next}. 320 * An initial call to {@link ListIterator#previous previous} would 321 * return the element with the specified index minus one. 322 * 323 * @param index index of the first element to be returned from the 324 * list iterator (by a call to {@link ListIterator#next next}) 325 * @return a list iterator over the elements in this list (in proper 326 * sequence), starting at the specified position in the list 327 * @throws IndexOutOfBoundsException if the index is out of range 328 * ({@code index < 0 || index > size()}) 329 */ 330 // ListIterator<E> listIterator(int index); 331 332 // View 333 334 /** 335 * Returns a view of the portion of this list between the specified 336 * <tt>fromIndex</tt>, inclusive, and <tt>toIndex</tt>, exclusive. (If 337 * <tt>fromIndex</tt> and <tt>toIndex</tt> are equal, the returned list is 338 * empty.) The returned list is backed by this list, so non-structural 339 * changes in the returned list are reflected in this list, and vice-versa. 340 * The returned list supports all of the optional list operations supported 341 * by this list.<p> 342 * 343 * This method eliminates the need for explicit range operations (of 344 * the sort that commonly exist for arrays). Any operation that expects 345 * a list can be used as a range operation by passing a subList view 346 * instead of a whole list. For example, the following idiom 347 * removes a range of elements from a list: 348 * <pre>{@code 349 * list.subList(from, to).clear(); 350 * }</pre> 351 * Similar idioms may be constructed for <tt>indexOf</tt> and 352 * <tt>lastIndexOf</tt>, and all of the algorithms in the 353 * <tt>Collections</tt> class can be applied to a subList.<p> 354 * 355 * The semantics of the list returned by this method become undefined if 356 * the backing list (i.e., this list) is <i>structurally modified</i> in 357 * any way other than via the returned list. (Structural modifications are 358 * those that change the size of this list, or otherwise perturb it in such 359 * a fashion that iterations in progress may yield incorrect results.) 360 * 361 * @param fromIndex low endpoint (inclusive) of the subList 362 * @param toIndex high endpoint (exclusive) of the subList 363 * @return a view of the specified range within this list 364 * @throws IndexOutOfBoundsException for an illegal endpoint index value 365 * (<tt>fromIndex < 0 || toIndex > size || 366 * fromIndex > toIndex</tt>) 367 */ 368 // List!E subList(int fromIndex, int toIndex); 369 370 /** 371 * Creates a {@link Spliterator} over the elements in this list. 372 * 373 * <p>The {@code Spliterator} reports {@link Spliterator#SIZED} and 374 * {@link Spliterator#ORDERED}. Implementations should document the 375 * reporting of additional characteristic values. 376 * 377 * @implSpec 378 * The final implementation creates a 379 * <em><a href="Spliterator.html#binding">late-binding</a></em> spliterator 380 * from the list's {@code Iterator}. The spliterator inherits the 381 * <em>fail-fast</em> properties of the list's iterator. 382 * 383 * @implNote 384 * The created {@code Spliterator} additionally reports 385 * {@link Spliterator#SUBSIZED}. 386 * 387 * @return a {@code Spliterator} over the elements in this list 388 * @since 1.8 389 */ 390 // override 391 // final Spliterator<E> spliterator() { 392 // return Spliterators.spliterator(this, Spliterator.ORDERED); 393 // } 394 395 // Comparison and hashing 396 397 /** 398 * Compares the specified object with this list for equality. Returns 399 * <tt>true</tt> if and only if the specified object is also a list, both 400 * lists have the same size, and all corresponding pairs of elements in 401 * the two lists are <i>equal</i>. (Two elements <tt>e1</tt> and 402 * <tt>e2</tt> are <i>equal</i> if <tt>(e1==null ? e2==null : 403 * e1.equals(e2))</tt>.) In other words, two lists are defined to be 404 * equal if they contain the same elements in the same order. This 405 * definition ensures that the equals method works properly across 406 * different implementations of the <tt>List</tt> interface. 407 * 408 * @param o the object to be compared for equality with this list 409 * @return <tt>true</tt> if the specified object is equal to this list 410 */ 411 // bool opEquals(Object o); 412 413 /** 414 * Returns the hash code value for this list. The hash code of a list 415 * is defined to be the result of the following calculation: 416 * <pre>{@code 417 * int hashCode = 1; 418 * for (E e : list) 419 * hashCode = 31*hashCode + (e==null ? 0 : e.hashCode()); 420 * }</pre> 421 * This ensures that <tt>list1.equals(list2)</tt> implies that 422 * <tt>list1.hashCode()==list2.hashCode()</tt> for any two lists, 423 * <tt>list1</tt> and <tt>list2</tt>, as required by the general 424 * contract of {@link Object#hashCode}. 425 * 426 * @return the hash code value for this list 427 * @see Object#equals(Object) 428 * @see #equals(Object) 429 */ 430 // size_t toHash() @trusted nothrow ; 431 }