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