| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file | |
| 2 // for details. All rights reserved. Use of this source code is governed by a | |
| 3 // BSD-style license that can be found in the LICENSE file. | |
| 4 | |
| 5 part of dart.collection; | |
| 6 | |
| 7 /** | |
| 8 * Abstract implementation of a list. | |
| 9 * | |
| 10 * `ListBase` can be used as a base class for implementing the `List` interface. | |
| 11 * | |
| 12 * All operations are defined in terms of `length`, `operator[]`, | |
| 13 * `operator[]=` and `length=`, which need to be implemented. | |
| 14 * | |
| 15 * *NOTICE*: Forwarding just these four operations to a normal growable [List] | |
| 16 * (as created by `new List()`) will give very bad performance for `add` and | |
| 17 * `addAll` operations of `ListBase`. These operations are implemented by | |
| 18 * increasing the length of the list by one for each `add` operation, and | |
| 19 * repeatedly increasing the length of a growable list is not efficient. | |
| 20 * To avoid this, either override 'add' and 'addAll' to also forward directly | |
| 21 * to the growable list, or, preferably, use `DelegatingList` from | |
| 22 * "package:collection/wrappers.dart" instead. | |
| 23 */ | |
| 24 abstract class ListBase<E> extends Object with ListMixin<E> { | |
| 25 /** | |
| 26 * Convert a `List` to a string as `[each, element, as, string]`. | |
| 27 * | |
| 28 * Handles circular references where converting one of the elements | |
| 29 * to a string ends up converting [list] to a string again. | |
| 30 */ | |
| 31 static String listToString(List list) => | |
| 32 IterableBase.iterableToFullString(list, '[', ']'); | |
| 33 } | |
| 34 | |
| 35 /** | |
| 36 * Base implementation of a [List] class. | |
| 37 * | |
| 38 * `ListMixin` can be used as a mixin to make a class implement | |
| 39 * the `List` interface. | |
| 40 * | |
| 41 * This implements all read operations using only the `length` and | |
| 42 * `operator[]` members. It implements write operations using those and | |
| 43 * `length=` and `operator[]=` | |
| 44 * | |
| 45 * *NOTICE*: Forwarding just these four operations to a normal growable [List] | |
| 46 * (as created by `new List()`) will give very bad performance for `add` and | |
| 47 * `addAll` operations of `ListBase`. These operations are implemented by | |
| 48 * increasing the length of the list by one for each `add` operation, and | |
| 49 * repeatedly increasing the length of a growable list is not efficient. | |
| 50 * To avoid this, either override 'add' and 'addAll' to also forward directly | |
| 51 * to the growable list, or, if possible, use `DelegatingList` from | |
| 52 * "package:collection/wrappers.dart" instead. | |
| 53 */ | |
| 54 abstract class ListMixin<E> implements List<E> { | |
| 55 // Iterable interface. | |
| 56 Iterator<E> get iterator => new ListIterator<E>(this); | |
| 57 | |
| 58 E elementAt(int index) => this[index]; | |
| 59 | |
| 60 void forEach(void action(E element)) { | |
| 61 int length = this.length; | |
| 62 for (int i = 0; i < length; i++) { | |
| 63 action(this[i]); | |
| 64 if (length != this.length) { | |
| 65 throw new ConcurrentModificationError(this); | |
| 66 } | |
| 67 } | |
| 68 } | |
| 69 | |
| 70 bool get isEmpty => length == 0; | |
| 71 | |
| 72 bool get isNotEmpty => !isEmpty; | |
| 73 | |
| 74 E get first { | |
| 75 if (length == 0) throw IterableElementError.noElement(); | |
| 76 return this[0]; | |
| 77 } | |
| 78 | |
| 79 E get last { | |
| 80 if (length == 0) throw IterableElementError.noElement(); | |
| 81 return this[length - 1]; | |
| 82 } | |
| 83 | |
| 84 E get single { | |
| 85 if (length == 0) throw IterableElementError.noElement(); | |
| 86 if (length > 1) throw IterableElementError.tooMany(); | |
| 87 return this[0]; | |
| 88 } | |
| 89 | |
| 90 bool contains(Object element) { | |
| 91 int length = this.length; | |
| 92 for (int i = 0; i < this.length; i++) { | |
| 93 if (this[i] == element) return true; | |
| 94 if (length != this.length) { | |
| 95 throw new ConcurrentModificationError(this); | |
| 96 } | |
| 97 } | |
| 98 return false; | |
| 99 } | |
| 100 | |
| 101 bool every(bool test(E element)) { | |
| 102 int length = this.length; | |
| 103 for (int i = 0; i < length; i++) { | |
| 104 if (!test(this[i])) return false; | |
| 105 if (length != this.length) { | |
| 106 throw new ConcurrentModificationError(this); | |
| 107 } | |
| 108 } | |
| 109 return true; | |
| 110 } | |
| 111 | |
| 112 bool any(bool test(E element)) { | |
| 113 int length = this.length; | |
| 114 for (int i = 0; i < length; i++) { | |
| 115 if (test(this[i])) return true; | |
| 116 if (length != this.length) { | |
| 117 throw new ConcurrentModificationError(this); | |
| 118 } | |
| 119 } | |
| 120 return false; | |
| 121 } | |
| 122 | |
| 123 E firstWhere(bool test(E element), { E orElse() }) { | |
| 124 int length = this.length; | |
| 125 for (int i = 0; i < length; i++) { | |
| 126 E element = this[i]; | |
| 127 if (test(element)) return element; | |
| 128 if (length != this.length) { | |
| 129 throw new ConcurrentModificationError(this); | |
| 130 } | |
| 131 } | |
| 132 if (orElse != null) return orElse(); | |
| 133 throw IterableElementError.noElement(); | |
| 134 } | |
| 135 | |
| 136 E lastWhere(bool test(E element), { E orElse() }) { | |
| 137 int length = this.length; | |
| 138 for (int i = length - 1; i >= 0; i--) { | |
| 139 E element = this[i]; | |
| 140 if (test(element)) return element; | |
| 141 if (length != this.length) { | |
| 142 throw new ConcurrentModificationError(this); | |
| 143 } | |
| 144 } | |
| 145 if (orElse != null) return orElse(); | |
| 146 throw IterableElementError.noElement(); | |
| 147 } | |
| 148 | |
| 149 E singleWhere(bool test(E element)) { | |
| 150 int length = this.length; | |
| 151 E match = null; | |
| 152 bool matchFound = false; | |
| 153 for (int i = 0; i < length; i++) { | |
| 154 E element = this[i]; | |
| 155 if (test(element)) { | |
| 156 if (matchFound) { | |
| 157 throw IterableElementError.tooMany(); | |
| 158 } | |
| 159 matchFound = true; | |
| 160 match = element; | |
| 161 } | |
| 162 if (length != this.length) { | |
| 163 throw new ConcurrentModificationError(this); | |
| 164 } | |
| 165 } | |
| 166 if (matchFound) return match; | |
| 167 throw IterableElementError.noElement(); | |
| 168 } | |
| 169 | |
| 170 String join([String separator = ""]) { | |
| 171 if (length == 0) return ""; | |
| 172 StringBuffer buffer = new StringBuffer()..writeAll(this, separator); | |
| 173 return buffer.toString(); | |
| 174 } | |
| 175 | |
| 176 Iterable<E> where(bool test(E element)) => new WhereIterable<E>(this, test); | |
| 177 | |
| 178 Iterable/*<T>*/ map/*<T>*/(/*=T*/ f(E element)) => | |
| 179 new MappedListIterable/*<E, T>*/(this, f); | |
| 180 | |
| 181 Iterable/*<T>*/ expand/*<T>*/(Iterable/*<T>*/ f(E element)) => | |
| 182 new ExpandIterable<E, dynamic/*=T*/>(this, f); | |
| 183 | |
| 184 E reduce(E combine(E previousValue, E element)) { | |
| 185 int length = this.length; | |
| 186 if (length == 0) throw IterableElementError.noElement(); | |
| 187 E value = this[0]; | |
| 188 for (int i = 1; i < length; i++) { | |
| 189 value = combine(value, this[i]); | |
| 190 if (length != this.length) { | |
| 191 throw new ConcurrentModificationError(this); | |
| 192 } | |
| 193 } | |
| 194 return value; | |
| 195 } | |
| 196 | |
| 197 dynamic/*=T*/ fold/*<T>*/(var/*=T*/ initialValue, | |
| 198 dynamic/*=T*/ combine(var/*=T*/ previousValue, E element)) { | |
| 199 var value = initialValue; | |
| 200 int length = this.length; | |
| 201 for (int i = 0; i < length; i++) { | |
| 202 value = combine(value, this[i]); | |
| 203 if (length != this.length) { | |
| 204 throw new ConcurrentModificationError(this); | |
| 205 } | |
| 206 } | |
| 207 return value; | |
| 208 } | |
| 209 | |
| 210 Iterable<E> skip(int count) => new SubListIterable<E>(this, count, null); | |
| 211 | |
| 212 Iterable<E> skipWhile(bool test(E element)) { | |
| 213 return new SkipWhileIterable<E>(this, test); | |
| 214 } | |
| 215 | |
| 216 Iterable<E> take(int count) => new SubListIterable<E>(this, 0, count); | |
| 217 | |
| 218 Iterable<E> takeWhile(bool test(E element)) { | |
| 219 return new TakeWhileIterable<E>(this, test); | |
| 220 } | |
| 221 | |
| 222 List<E> toList({ bool growable: true }) { | |
| 223 List<E> result; | |
| 224 if (growable) { | |
| 225 result = new List<E>()..length = length; | |
| 226 } else { | |
| 227 result = new List<E>(length); | |
| 228 } | |
| 229 for (int i = 0; i < length; i++) { | |
| 230 result[i] = this[i]; | |
| 231 } | |
| 232 return result; | |
| 233 } | |
| 234 | |
| 235 Set<E> toSet() { | |
| 236 Set<E> result = new Set<E>(); | |
| 237 for (int i = 0; i < length; i++) { | |
| 238 result.add(this[i]); | |
| 239 } | |
| 240 return result; | |
| 241 } | |
| 242 | |
| 243 // Collection interface. | |
| 244 void add(E element) { | |
| 245 this[this.length++] = element; | |
| 246 } | |
| 247 | |
| 248 void addAll(Iterable<E> iterable) { | |
| 249 int i = this.length; | |
| 250 for (E element in iterable) { | |
| 251 assert(this.length == i || (throw new ConcurrentModificationError(this))); | |
| 252 this.length = i + 1; | |
| 253 this[i] = element; | |
| 254 i++; | |
| 255 } | |
| 256 } | |
| 257 | |
| 258 bool remove(Object element) { | |
| 259 for (int i = 0; i < this.length; i++) { | |
| 260 if (this[i] == element) { | |
| 261 this.setRange(i, this.length - 1, this, i + 1); | |
| 262 this.length -= 1; | |
| 263 return true; | |
| 264 } | |
| 265 } | |
| 266 return false; | |
| 267 } | |
| 268 | |
| 269 void removeWhere(bool test(E element)) { | |
| 270 _filter(test, false); | |
| 271 } | |
| 272 | |
| 273 void retainWhere(bool test(E element)) { | |
| 274 _filter(test, true); | |
| 275 } | |
| 276 | |
| 277 void _filter(bool test(var element), bool retainMatching) { | |
| 278 var source = this; | |
| 279 var retained = <E>[]; | |
| 280 int length = source.length; | |
| 281 for (int i = 0; i < length; i++) { | |
| 282 var element = source[i]; | |
| 283 if (test(element) == retainMatching) { | |
| 284 retained.add(element); | |
| 285 } | |
| 286 if (length != source.length) { | |
| 287 throw new ConcurrentModificationError(source); | |
| 288 } | |
| 289 } | |
| 290 if (retained.length != source.length) { | |
| 291 source.setRange(0, retained.length, retained); | |
| 292 source.length = retained.length; | |
| 293 } | |
| 294 } | |
| 295 | |
| 296 void clear() { this.length = 0; } | |
| 297 | |
| 298 // List interface. | |
| 299 | |
| 300 E removeLast() { | |
| 301 if (length == 0) { | |
| 302 throw IterableElementError.noElement(); | |
| 303 } | |
| 304 E result = this[length - 1]; | |
| 305 length--; | |
| 306 return result; | |
| 307 } | |
| 308 | |
| 309 void sort([int compare(E a, E b)]) { | |
| 310 if (compare == null) { | |
| 311 Sort.sort(this, (a, b) => Comparable.compare(a, b)); | |
| 312 } else { | |
| 313 Sort.sort(this, compare); | |
| 314 } | |
| 315 } | |
| 316 | |
| 317 void shuffle([Random random]) { | |
| 318 if (random == null) random = new Random(); | |
| 319 int length = this.length; | |
| 320 while (length > 1) { | |
| 321 int pos = random.nextInt(length); | |
| 322 length -= 1; | |
| 323 var tmp = this[length]; | |
| 324 this[length] = this[pos]; | |
| 325 this[pos] = tmp; | |
| 326 } | |
| 327 } | |
| 328 | |
| 329 Map<int, E> asMap() { | |
| 330 return new ListMapView<E>(this); | |
| 331 } | |
| 332 | |
| 333 List<E> sublist(int start, [int end]) { | |
| 334 int listLength = this.length; | |
| 335 if (end == null) end = listLength; | |
| 336 RangeError.checkValidRange(start, end, listLength); | |
| 337 int length = end - start; | |
| 338 List<E> result = new List<E>()..length = length; | |
| 339 for (int i = 0; i < length; i++) { | |
| 340 result[i] = this[start + i]; | |
| 341 } | |
| 342 return result; | |
| 343 } | |
| 344 | |
| 345 Iterable<E> getRange(int start, int end) { | |
| 346 RangeError.checkValidRange(start, end, this.length); | |
| 347 return new SubListIterable<E>(this, start, end); | |
| 348 } | |
| 349 | |
| 350 void removeRange(int start, int end) { | |
| 351 RangeError.checkValidRange(start, end, this.length); | |
| 352 int length = end - start; | |
| 353 setRange(start, this.length - length, this, end); | |
| 354 this.length -= length; | |
| 355 } | |
| 356 | |
| 357 void fillRange(int start, int end, [E fill]) { | |
| 358 RangeError.checkValidRange(start, end, this.length); | |
| 359 for (int i = start; i < end; i++) { | |
| 360 this[i] = fill; | |
| 361 } | |
| 362 } | |
| 363 | |
| 364 void setRange(int start, int end, Iterable<E> iterable, [int skipCount = 0]) { | |
| 365 RangeError.checkValidRange(start, end, this.length); | |
| 366 int length = end - start; | |
| 367 if (length == 0) return; | |
| 368 RangeError.checkNotNegative(skipCount, "skipCount"); | |
| 369 | |
| 370 List<E> otherList; | |
| 371 int otherStart; | |
| 372 // TODO(floitsch): Make this accept more. | |
| 373 if (iterable is List/*<E>*/) { | |
| 374 otherList = iterable; | |
| 375 otherStart = skipCount; | |
| 376 } else { | |
| 377 otherList = iterable.skip(skipCount).toList(growable: false); | |
| 378 otherStart = 0; | |
| 379 } | |
| 380 if (otherStart + length > otherList.length) { | |
| 381 throw IterableElementError.tooFew(); | |
| 382 } | |
| 383 if (otherStart < start) { | |
| 384 // Copy backwards to ensure correct copy if [from] is this. | |
| 385 for (int i = length - 1; i >= 0; i--) { | |
| 386 this[start + i] = otherList[otherStart + i]; | |
| 387 } | |
| 388 } else { | |
| 389 for (int i = 0; i < length; i++) { | |
| 390 this[start + i] = otherList[otherStart + i]; | |
| 391 } | |
| 392 } | |
| 393 } | |
| 394 | |
| 395 void replaceRange(int start, int end, Iterable<E> newContents) { | |
| 396 RangeError.checkValidRange(start, end, this.length); | |
| 397 if (newContents is! EfficientLength) { | |
| 398 newContents = newContents.toList(); | |
| 399 } | |
| 400 int removeLength = end - start; | |
| 401 int insertLength = newContents.length; | |
| 402 if (removeLength >= insertLength) { | |
| 403 int delta = removeLength - insertLength; | |
| 404 int insertEnd = start + insertLength; | |
| 405 int newLength = this.length - delta; | |
| 406 this.setRange(start, insertEnd, newContents); | |
| 407 if (delta != 0) { | |
| 408 this.setRange(insertEnd, newLength, this, end); | |
| 409 this.length = newLength; | |
| 410 } | |
| 411 } else { | |
| 412 int delta = insertLength - removeLength; | |
| 413 int newLength = this.length + delta; | |
| 414 int insertEnd = start + insertLength; // aka. end + delta. | |
| 415 this.length = newLength; | |
| 416 this.setRange(insertEnd, newLength, this, end); | |
| 417 this.setRange(start, insertEnd, newContents); | |
| 418 } | |
| 419 } | |
| 420 | |
| 421 int indexOf(Object element, [int startIndex = 0]) { | |
| 422 if (startIndex >= this.length) { | |
| 423 return -1; | |
| 424 } | |
| 425 if (startIndex < 0) { | |
| 426 startIndex = 0; | |
| 427 } | |
| 428 for (int i = startIndex; i < this.length; i++) { | |
| 429 if (this[i] == element) { | |
| 430 return i; | |
| 431 } | |
| 432 } | |
| 433 return -1; | |
| 434 } | |
| 435 | |
| 436 /** | |
| 437 * Returns the last index in the list [a] of the given [element], starting | |
| 438 * the search at index [startIndex] to 0. | |
| 439 * Returns -1 if [element] is not found. | |
| 440 */ | |
| 441 int lastIndexOf(Object element, [int startIndex]) { | |
| 442 if (startIndex == null) { | |
| 443 startIndex = this.length - 1; | |
| 444 } else { | |
| 445 if (startIndex < 0) { | |
| 446 return -1; | |
| 447 } | |
| 448 if (startIndex >= this.length) { | |
| 449 startIndex = this.length - 1; | |
| 450 } | |
| 451 } | |
| 452 for (int i = startIndex; i >= 0; i--) { | |
| 453 if (this[i] == element) { | |
| 454 return i; | |
| 455 } | |
| 456 } | |
| 457 return -1; | |
| 458 } | |
| 459 | |
| 460 void insert(int index, E element) { | |
| 461 RangeError.checkValueInInterval(index, 0, length, "index"); | |
| 462 if (index == this.length) { | |
| 463 add(element); | |
| 464 return; | |
| 465 } | |
| 466 // We are modifying the length just below the is-check. Without the check | |
| 467 // Array.copy could throw an exception, leaving the list in a bad state | |
| 468 // (with a length that has been increased, but without a new element). | |
| 469 if (index is! int) throw new ArgumentError(index); | |
| 470 this.length++; | |
| 471 setRange(index + 1, this.length, this, index); | |
| 472 this[index] = element; | |
| 473 } | |
| 474 | |
| 475 E removeAt(int index) { | |
| 476 E result = this[index]; | |
| 477 setRange(index, this.length - 1, this, index + 1); | |
| 478 length--; | |
| 479 return result; | |
| 480 } | |
| 481 | |
| 482 void insertAll(int index, Iterable<E> iterable) { | |
| 483 RangeError.checkValueInInterval(index, 0, length, "index"); | |
| 484 if (iterable is! EfficientLength || identical(iterable, this)) { | |
| 485 iterable = iterable.toList(); | |
| 486 } | |
| 487 int insertionLength = iterable.length; | |
| 488 // There might be errors after the length change, in which case the list | |
| 489 // will end up being modified but the operation not complete. Unless we | |
| 490 // always go through a "toList" we can't really avoid that. | |
| 491 this.length += insertionLength; | |
| 492 if (iterable.length != insertionLength) { | |
| 493 // If the iterable's length is linked to this list's length somehow, | |
| 494 // we can't insert one in the other. | |
| 495 this.length -= insertionLength; | |
| 496 throw new ConcurrentModificationError(iterable); | |
| 497 } | |
| 498 setRange(index + insertionLength, this.length, this, index); | |
| 499 setAll(index, iterable); | |
| 500 } | |
| 501 | |
| 502 void setAll(int index, Iterable<E> iterable) { | |
| 503 if (iterable is List) { | |
| 504 setRange(index, index + iterable.length, iterable); | |
| 505 } else { | |
| 506 for (E element in iterable) { | |
| 507 this[index++] = element; | |
| 508 } | |
| 509 } | |
| 510 } | |
| 511 | |
| 512 Iterable<E> get reversed => new ReversedListIterable<E>(this); | |
| 513 | |
| 514 String toString() => IterableBase.iterableToFullString(this, '[', ']'); | |
| 515 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2698353003:
unfork DDC's copy of most SDK libraries (Closed)
