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.AbstractList; 13 14 import std.algorithm; 15 import std.conv; 16 import std.traits; 17 18 import hunt.collection.AbstractCollection; 19 import hunt.collection.List; 20 import hunt.Exceptions; 21 import hunt.Object; 22 import hunt.util.Comparator; 23 24 /** 25 */ 26 abstract class AbstractList(E) : AbstractCollection!E, List!E { 27 28 /** 29 * The number of times this list has been <i>structurally modified</i>. 30 * Structural modifications are those that change the size of the 31 * list, or otherwise perturb it in such a fashion that iterations in 32 * progress may yield incorrect results. 33 * 34 * <p>This field is used by the iterator and list iterator implementation 35 * returned by the {@code iterator} and {@code listIterator} methods. 36 * If the value of this field changes unexpectedly, the iterator (or list 37 * iterator) will throw a {@code ConcurrentModificationException} in 38 * response to the {@code next}, {@code remove}, {@code previous}, 39 * {@code set} or {@code add} operations. This provides 40 * <i>fail-fast</i> behavior, rather than non-deterministic behavior in 41 * the face of concurrent modification during iteration. 42 * 43 * <p><b>Use of this field by subclasses is optional.</b> If a subclass 44 * wishes to provide fail-fast iterators (and list iterators), then it 45 * merely has to increment this field in its {@code add(int, E)} and 46 * {@code remove(int)} methods (and any other methods that it overrides 47 * that result in structural modifications to the list). A single call to 48 * {@code add(int, E)} or {@code remove(int)} must add no more than 49 * one to this field, or the iterators (and list iterators) will throw 50 * bogus {@code ConcurrentModificationExceptions}. If an implementation 51 * does not wish to provide fail-fast iterators, this field may be 52 * ignored. 53 */ 54 protected int modCount = 0; 55 56 /** 57 * Sole constructor. (For invocation by subclass constructors, typically 58 * implicit.) 59 */ 60 protected this() { 61 } 62 63 /** 64 * Appends the specified element to the end of this list (optional 65 * operation). 66 * 67 * <p>Lists that support this operation may place limitations on what 68 * elements may be added to this list. In particular, some 69 * lists will refuse to add null elements, and others will impose 70 * restrictions on the type of elements that may be added. List 71 * classes should clearly specify in their documentation any restrictions 72 * on what elements may be added. 73 * 74 * <p>This implementation calls {@code add(size(), e)}. 75 * 76 * <p>Note that this implementation throws an 77 * {@code UnsupportedOperationException} unless 78 * {@link #add(int, Object) add(int, E)} is overridden. 79 * 80 * @param e element to be appended to this list 81 * @return {@code true} (as specified by {@link Collection#add}) 82 * @throws UnsupportedOperationException if the {@code add} operation 83 * is not supported by this list 84 * @throws ClassCastException if the class of the specified element 85 * prevents it from being added to this list 86 * @throws NullPointerException if the specified element is null and this 87 * list does not permit null elements 88 * @throws IllegalArgumentException if some property of this element 89 * prevents it from being added to this list 90 */ 91 // bool add(E e) { throw new UnsupportedOperationException(""); } 92 93 /** 94 * {@inheritDoc} 95 * 96 * @throws IndexOutOfBoundsException {@inheritDoc} 97 */ 98 E get(int index) { 99 throw new UnsupportedOperationException(""); 100 } 101 102 E opIndex(int index) { 103 return get(index); 104 } 105 106 /** 107 * {@inheritDoc} 108 * 109 * <p>This implementation always throws an 110 * {@code UnsupportedOperationException}. 111 * 112 * @throws UnsupportedOperationException {@inheritDoc} 113 * @throws ClassCastException {@inheritDoc} 114 * @throws NullPointerException {@inheritDoc} 115 * @throws IllegalArgumentException {@inheritDoc} 116 * @throws IndexOutOfBoundsException {@inheritDoc} 117 */ 118 E set(int index, E element) { 119 throw new UnsupportedOperationException(""); 120 } 121 122 /** 123 * {@inheritDoc} 124 * 125 * <p>This implementation always throws an 126 * {@code UnsupportedOperationException}. 127 * 128 * @throws UnsupportedOperationException {@inheritDoc} 129 * @throws ClassCastException {@inheritDoc} 130 * @throws NullPointerException {@inheritDoc} 131 * @throws IllegalArgumentException {@inheritDoc} 132 * @throws IndexOutOfBoundsException {@inheritDoc} 133 */ 134 void add(int index, E element) { 135 throw new UnsupportedOperationException(""); 136 } 137 138 /** 139 * {@inheritDoc} 140 * 141 * <p>This implementation always throws an 142 * {@code UnsupportedOperationException}. 143 * 144 * @throws UnsupportedOperationException {@inheritDoc} 145 * @throws IndexOutOfBoundsException {@inheritDoc} 146 */ 147 E removeAt(int index) { 148 throw new UnsupportedOperationException(""); 149 } 150 151 // bool remove(E o) { throw new UnsupportedOperationException(""); } 152 153 // Search Operations 154 155 /** 156 * {@inheritDoc} 157 * 158 * <p>This implementation first gets a list iterator (with 159 * {@code listIterator()}). Then, it iterates over the list until the 160 * specified element is found or the end of the list is reached. 161 * 162 * @throws ClassCastException {@inheritDoc} 163 * @throws NullPointerException {@inheritDoc} 164 */ 165 int indexOf(E o) { 166 throw new UnsupportedOperationException(""); 167 } 168 169 /** 170 * {@inheritDoc} 171 * 172 * <p>This implementation first gets a list iterator that points to the end 173 * of the list (with {@code listIterator(size())}). Then, it iterates 174 * backwards over the list until the specified element is found, or the 175 * beginning of the list is reached. 176 * 177 * @throws ClassCastException {@inheritDoc} 178 * @throws NullPointerException {@inheritDoc} 179 */ 180 int lastIndexOf(E o) { 181 throw new UnsupportedOperationException(""); 182 } 183 184 // Bulk Operations 185 186 /** 187 * Removes all of the elements from this list (optional operation). 188 * The list will be empty after this call returns. 189 * 190 * <p>This implementation calls {@code removeRange(0, size())}. 191 * 192 * <p>Note that this implementation throws an 193 * {@code UnsupportedOperationException} unless {@code remove(int 194 * index)} or {@code removeRange(int fromIndex, int toIndex)} is 195 * overridden. 196 * 197 * @throws UnsupportedOperationException if the {@code clear} operation 198 * is not supported by this list 199 */ 200 // void clear() { throw new UnsupportedOperationException(""); } 201 202 // Comparison and hashing 203 204 /** 205 * Compares the specified object with this list for equality. Returns 206 * {@code true} if and only if the specified object is also a list, both 207 * lists have the same size, and all corresponding pairs of elements in 208 * the two lists are <i>equal</i>. (Two elements {@code e1} and 209 * {@code e2} are <i>equal</i> if {@code (e1==null ? e2==null : 210 * e1.equals(e2))}.) In other words, two lists are defined to be 211 * equal if they contain the same elements in the same order.<p> 212 * 213 * This implementation first checks if the specified object is this 214 * list. If so, it returns {@code true}; if not, it checks if the 215 * specified object is a list. If not, it returns {@code false}; if so, 216 * it iterates over both lists, comparing corresponding pairs of elements. 217 * If any comparison returns {@code false}, this method returns 218 * {@code false}. If either iterator runs out of elements before the 219 * other it returns {@code false} (as the lists are of unequal length); 220 * otherwise it returns {@code true} when the iterations complete. 221 * 222 * @param o the object to be compared for equality with this list 223 * @return {@code true} if the specified object is equal to this list 224 */ 225 override bool opEquals(Object o) { 226 if (o is this) 227 return true; 228 List!E e2 = cast(List!E) o; 229 if (e2 is null) 230 return false; 231 232 if (this.size() != e2.size()) 233 return false; 234 235 for (int i = 0; i < this.size(); i++) { 236 if (this.get(i) != e2.get(i)) 237 return false; 238 } 239 240 return true; 241 } 242 243 override bool opEquals(IObject o) { 244 return opEquals(cast(Object) o); 245 } 246 247 /** 248 * Returns the hash code value for this list. 249 * 250 * <p>This implementation uses exactly the code that is used to define the 251 * list hash function in the documentation for the {@link List#hashCode} 252 * method. 253 * 254 * @return the hash code value for this list 255 */ 256 override size_t toHash() @trusted nothrow { 257 size_t hashCode = 1; 258 try { 259 static if (is(E == class)) { 260 foreach (E e; this) 261 hashCode = 31 * hashCode + (e is null ? 0 : (cast(Object) e).toHash()); 262 } else { 263 foreach (E e; this) 264 hashCode = 31 * hashCode + hashOf(e); 265 } 266 } catch (Exception e) { 267 hashCode = super.toHash(); 268 } 269 270 return hashCode; 271 } 272 273 override string toString() { 274 return super.toString(); 275 } 276 277 override int opApply(scope int delegate(ref E) dg) { 278 return 0; 279 } 280 281 282 static if (isOrderingComparable!E) { 283 void sort(bool isAscending = true) { 284 throw new UnsupportedOperationException(); 285 } 286 } 287 288 void sort(Comparator!E c) { 289 throw new UnsupportedOperationException(); 290 } 291 292 // List!(E) opCast(C)(C c) nothrow 293 // //if(is(C == immutable (E)[])) 294 // { 295 // return cast(List!(E))c; 296 // } 297 /** 298 * {@inheritDoc} 299 * 300 * <p>This implementation gets an iterator over the specified collection 301 * and iterates over it, inserting the elements obtained from the 302 * iterator into this list at the appropriate position, one at a time, 303 * using {@code add(int, E)}. 304 * Many implementations will override this method for efficiency. 305 * 306 * <p>Note that this implementation throws an 307 * {@code UnsupportedOperationException} unless 308 * {@link #add(int, Object) add(int, E)} is overridden. 309 * 310 * @throws UnsupportedOperationException {@inheritDoc} 311 * @throws ClassCastException {@inheritDoc} 312 * @throws NullPointerException {@inheritDoc} 313 * @throws IllegalArgumentException {@inheritDoc} 314 * @throws IndexOutOfBoundsException {@inheritDoc} 315 */ 316 // bool addAll(int index, Collection<E> c) { 317 // rangeCheckForAdd(index); 318 // bool modified = false; 319 // for (E e : c) { 320 // add(index++, e); 321 // modified = true; 322 // } 323 // return modified; 324 // } 325 } 326 327 328 /** 329 */ 330 class EmptyList(E) : AbstractList!E { 331 // private static long serialVersionUID = 8842843931221139166L; 332 333 override int size() { 334 return 0; 335 } 336 337 override bool isEmpty() { 338 return true; 339 } 340 341 override bool contains(E obj) { 342 return false; 343 } 344 // override bool containsAll(Collection!E c) { return c.isEmpty(); } 345 346 override E[] toArray() { 347 return new E[0]; 348 } 349 350 T[] toArray(T)(T[] a) { 351 if (a.length > 0) 352 a[0] = null; 353 return a; 354 } 355 356 override E get(int index) { 357 throw new IndexOutOfBoundsException("Index: " ~ index.to!string); 358 } 359 360 override bool add(E e) { 361 throw new UnsupportedOperationException(""); 362 } 363 364 override E removeAt(int index) { 365 throw new IndexOutOfBoundsException("Index: " ~ index.to!string); 366 } 367 368 override bool remove(E o) { 369 return false; 370 } 371 372 override int indexOf(E o) { 373 return -1; 374 } 375 376 override int lastIndexOf(E o) { 377 return -1; 378 } 379 380 override bool opEquals(Object o) { 381 return (typeid(o) == typeid(List!E)) && (cast(List!E) o).isEmpty(); 382 } 383 384 385 override size_t toHash() { 386 return 1; 387 } 388 389 // override 390 // bool removeIf(Predicate!E filter) { 391 // assert(filter !is null); 392 // return false; 393 // } 394 395 // override 396 // void replaceAll(UnaryOperator!E operator) { 397 // Objects.requireNonNull(operator); 398 // } 399 400 // Override default methods in Collection 401 override int opApply(scope int delegate(ref E) dg) { 402 return 0; 403 } 404 405 // override 406 // Spliterator!E spliterator() { return Spliterators.emptySpliterator(); } 407 408 // // Preserves singleton property 409 // private Object readResolve() { 410 // return EMPTY_LIST; 411 // } 412 }