| OLD | NEW |
|---|
| (Empty) |
| 1 // Copyright (c) 2011, 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 library queue.test; | |
| 6 | |
| 7 import "package:expect/expect.dart"; | |
| 8 import 'dart:collection'; | |
| 9 | |
| 10 abstract class QueueTest { | |
| 11 Queue newQueue(); | |
| 12 Queue newQueueFrom(Iterable iterable); | |
| 13 | |
| 14 void testMain() { | |
| 15 Queue queue = newQueue(); | |
| 16 checkQueue(queue, 0, 0); | |
| 17 | |
| 18 queue.addFirst(1); | |
| 19 checkQueue(queue, 1, 1); | |
| 20 | |
| 21 queue.addLast(10); | |
| 22 checkQueue(queue, 2, 11); | |
| 23 | |
| 24 Expect.equals(10, queue.removeLast()); | |
| 25 checkQueue(queue, 1, 1); | |
| 26 | |
| 27 queue.addLast(10); | |
| 28 Expect.equals(1, queue.removeFirst()); | |
| 29 checkQueue(queue, 1, 10); | |
| 30 | |
| 31 queue.addFirst(1); | |
| 32 queue.addLast(100); | |
| 33 queue.addLast(1000); | |
| 34 Expect.equals(1000, queue.removeLast()); | |
| 35 queue.addLast(1000); | |
| 36 checkQueue(queue, 4, 1111); | |
| 37 | |
| 38 queue.removeFirst(); | |
| 39 checkQueue(queue, 3, 1110); | |
| 40 | |
| 41 int mapTest(int value) { | |
| 42 return value ~/ 10; | |
| 43 } | |
| 44 | |
| 45 bool is10(int value) { | |
| 46 return (value == 10); | |
| 47 } | |
| 48 | |
| 49 Queue mapped = newQueueFrom(queue.map(mapTest)); | |
| 50 checkQueue(mapped, 3, 111); | |
| 51 checkQueue(queue, 3, 1110); | |
| 52 Expect.equals(1, mapped.removeFirst()); | |
| 53 Expect.equals(100, mapped.removeLast()); | |
| 54 Expect.equals(10, mapped.removeFirst()); | |
| 55 | |
| 56 Queue other = newQueueFrom(queue.where(is10)); | |
| 57 checkQueue(other, 1, 10); | |
| 58 | |
| 59 Expect.equals(true, queue.any(is10)); | |
| 60 | |
| 61 bool isInstanceOfInt(int value) { | |
| 62 return (value is int); | |
| 63 } | |
| 64 | |
| 65 Expect.equals(true, queue.every(isInstanceOfInt)); | |
| 66 | |
| 67 Expect.equals(false, queue.every(is10)); | |
| 68 | |
| 69 bool is1(int value) { | |
| 70 return (value == 1); | |
| 71 } | |
| 72 | |
| 73 Expect.equals(false, queue.any(is1)); | |
| 74 | |
| 75 queue.clear(); | |
| 76 Expect.equals(0, queue.length); | |
| 77 | |
| 78 var exception = null; | |
| 79 try { | |
| 80 queue.removeFirst(); | |
| 81 } on StateError catch (e) { | |
| 82 exception = e; | |
| 83 } | |
| 84 Expect.equals(true, exception != null); | |
| 85 Expect.equals(0, queue.length); | |
| 86 | |
| 87 exception = null; | |
| 88 try { | |
| 89 queue.removeLast(); | |
| 90 } on StateError catch (e) { | |
| 91 exception = e; | |
| 92 } | |
| 93 Expect.equals(true, exception != null); | |
| 94 Expect.equals(0, queue.length); | |
| 95 | |
| 96 queue.addFirst(1); | |
| 97 queue.addFirst(2); | |
| 98 Expect.equals(2, queue.first); | |
| 99 Expect.equals(1, queue.last); | |
| 100 | |
| 101 queue.addLast(3); | |
| 102 Expect.equals(3, queue.last); | |
| 103 bool isGreaterThanOne(int value) { | |
| 104 return (value > 1); | |
| 105 } | |
| 106 | |
| 107 other = newQueueFrom(queue.where(isGreaterThanOne)); | |
| 108 checkQueue(other, 2, 5); | |
| 109 | |
| 110 // Cycle through values without ever having large element count. | |
| 111 queue = newQueue(); | |
| 112 queue.add(0); | |
| 113 for (int i = 0; i < 255; i++) { | |
| 114 queue.add(i + 1); | |
| 115 Expect.equals(i, queue.removeFirst()); | |
| 116 } | |
| 117 Expect.equals(255, queue.removeFirst()); | |
| 118 Expect.isTrue(queue.isEmpty); | |
| 119 | |
| 120 testAddAll(); | |
| 121 testLengthChanges(); | |
| 122 testLarge(); | |
| 123 testFromListToList(); | |
| 124 } | |
| 125 | |
| 126 void checkQueue(Queue queue, int expectedSize, int expectedSum) { | |
| 127 testLength(expectedSize, queue); | |
| 128 int sum = 0; | |
| 129 void sumElements(int value) { | |
| 130 sum += value; | |
| 131 } | |
| 132 | |
| 133 queue.forEach(sumElements); | |
| 134 Expect.equals(expectedSum, sum); | |
| 135 } | |
| 136 | |
| 137 testLength(int length, Queue queue) { | |
| 138 Expect.equals(length, queue.length); | |
| 139 ((length == 0) ? Expect.isTrue : Expect.isFalse)(queue.isEmpty); | |
| 140 ((length != 0) ? Expect.isTrue : Expect.isFalse)(queue.isNotEmpty); | |
| 141 } | |
| 142 | |
| 143 void testAddAll() { | |
| 144 Set<int> set = new Set<int>.from([1, 2, 4]); | |
| 145 Expect.equals(3, set.length); | |
| 146 | |
| 147 Queue queue1 = newQueueFrom(set); | |
| 148 Queue queue2 = newQueue(); | |
| 149 Queue queue3 = newQueue(); | |
| 150 testLength(3, queue1); | |
| 151 testLength(0, queue2); | |
| 152 testLength(0, queue3); | |
| 153 | |
| 154 queue2.addAll(set); | |
| 155 testLength(3, queue2); | |
| 156 | |
| 157 queue3.addAll(queue1); | |
| 158 testLength(3, queue3); | |
| 159 | |
| 160 int sum = 0; | |
| 161 void f(e) { | |
| 162 sum += e; | |
| 163 } | |
| 164 | |
| 165 ; | |
| 166 | |
| 167 set.forEach(f); | |
| 168 Expect.equals(7, sum); | |
| 169 sum = 0; | |
| 170 | |
| 171 queue1.forEach(f); | |
| 172 Expect.equals(7, sum); | |
| 173 sum = 0; | |
| 174 | |
| 175 queue2.forEach(f); | |
| 176 Expect.equals(7, sum); | |
| 177 sum = 0; | |
| 178 | |
| 179 queue3.forEach(f); | |
| 180 Expect.equals(7, sum); | |
| 181 sum = 0; | |
| 182 | |
| 183 set = new Set<int>.from([]); | |
| 184 queue1 = newQueueFrom(set); | |
| 185 queue2 = newQueue(); | |
| 186 queue3 = newQueue(); | |
| 187 | |
| 188 queue2.addAll(set); | |
| 189 queue3.addAll(queue1); | |
| 190 | |
| 191 Expect.equals(0, set.length); | |
| 192 Expect.equals(0, queue1.length); | |
| 193 Expect.equals(0, queue2.length); | |
| 194 Expect.equals(0, queue3.length); | |
| 195 } | |
| 196 | |
| 197 void testLengthChanges() { | |
| 198 // Test that the length property is updated properly by | |
| 199 // modifications; | |
| 200 Queue queue = newQueue(); | |
| 201 testLength(0, queue); | |
| 202 | |
| 203 for (int i = 1; i <= 10; i++) { | |
| 204 queue.add(i); | |
| 205 testLength(i, queue); | |
| 206 } | |
| 207 | |
| 208 for (int i = 1; i <= 10; i++) { | |
| 209 queue.addFirst(11 - i); | |
| 210 testLength(10 + i, queue); | |
| 211 } | |
| 212 | |
| 213 for (int i = 1; i <= 10; i++) { | |
| 214 queue.addLast(i); | |
| 215 testLength(20 + i, queue); | |
| 216 } | |
| 217 | |
| 218 queue.addAll([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]); | |
| 219 testLength(40, queue); | |
| 220 | |
| 221 for (int i = 1; i <= 5; i++) { | |
| 222 Expect.equals(i, queue.removeFirst()); | |
| 223 testLength(40 - i, queue); | |
| 224 } | |
| 225 | |
| 226 for (int i = 1; i <= 5; i++) { | |
| 227 Expect.equals(11 - i, queue.removeLast()); | |
| 228 testLength(35 - i, queue); | |
| 229 } | |
| 230 | |
| 231 Expect.isTrue(queue.remove(10)); | |
| 232 testLength(29, queue); | |
| 233 Expect.isFalse(queue.remove(999)); | |
| 234 testLength(29, queue); | |
| 235 | |
| 236 queue.removeWhere((x) => x == 7); | |
| 237 testLength(26, queue); | |
| 238 | |
| 239 queue.retainWhere((x) => x != 3); | |
| 240 testLength(23, queue); | |
| 241 | |
| 242 Expect.listEquals( | |
| 243 [6, 8, 9, 1, 2, 4, 5, 6, 8, 9, 10, 1, 2, 4, 5, 6, 8, 9, 10, 1, 2, 4, 5], | |
| 244 queue.toList()); | |
| 245 | |
| 246 // Regression test: http://dartbug.com/16270 | |
| 247 // These should all do nothing, and should not throw. | |
| 248 Queue emptyQueue = newQueue(); | |
| 249 emptyQueue.remove(0); | |
| 250 emptyQueue.removeWhere((x) => null); | |
| 251 emptyQueue.retainWhere((x) => null); | |
| 252 } | |
| 253 | |
| 254 void testLarge() { | |
| 255 int N = 10000; | |
| 256 Set set = new Set(); | |
| 257 | |
| 258 Queue queue = newQueue(); | |
| 259 Expect.isTrue(queue.isEmpty); | |
| 260 | |
| 261 for (int i = 0; i < N; i++) { | |
| 262 queue.add(i); | |
| 263 set.add(i); | |
| 264 } | |
| 265 Expect.equals(N, queue.length); | |
| 266 Expect.isFalse(queue.isEmpty); | |
| 267 | |
| 268 Expect.equals(0, queue.elementAt(0)); | |
| 269 Expect.equals(N - 1, queue.elementAt(N - 1)); | |
| 270 Expect.throws(() { | |
| 271 queue.elementAt(-1); | |
| 272 }); | |
| 273 Expect.throws(() { | |
| 274 queue.elementAt(N); | |
| 275 }); | |
| 276 | |
| 277 Iterable skip1 = queue.skip(1); | |
| 278 Iterable take1 = queue.take(1); | |
| 279 Iterable mapped = queue.map((e) => -e); | |
| 280 | |
| 281 for (int i = 0; i < 500; i++) { | |
| 282 Expect.equals(i, take1.first); | |
| 283 Expect.equals(i, queue.first); | |
| 284 Expect.equals(-i, mapped.first); | |
| 285 Expect.equals(i + 1, skip1.first); | |
| 286 Expect.equals(i, queue.removeFirst()); | |
| 287 Expect.equals(i + 1, take1.first); | |
| 288 Expect.equals(-i - 1, mapped.first); | |
| 289 Expect.equals(N - 1 - i, queue.last); | |
| 290 Expect.equals(N - 1 - i, queue.removeLast()); | |
| 291 } | |
| 292 Expect.equals(N - 1000, queue.length); | |
| 293 | |
| 294 Expect.isTrue(queue.remove(N >> 1)); | |
| 295 Expect.equals(N - 1001, queue.length); | |
| 296 | |
| 297 queue.clear(); | |
| 298 Expect.equals(0, queue.length); | |
| 299 Expect.isTrue(queue.isEmpty); | |
| 300 | |
| 301 queue.addAll(set); | |
| 302 Expect.equals(N, queue.length); | |
| 303 Expect.isFalse(queue.isEmpty); | |
| 304 | |
| 305 // Iterate. | |
| 306 for (var element in queue) { | |
| 307 Expect.isTrue(set.contains(element)); | |
| 308 } | |
| 309 | |
| 310 queue.forEach((element) { | |
| 311 Expect.isTrue(set.contains(element)); | |
| 312 }); | |
| 313 | |
| 314 queue.addAll(set); | |
| 315 Expect.equals(N * 2, queue.length); | |
| 316 Expect.isFalse(queue.isEmpty); | |
| 317 | |
| 318 queue.clear(); | |
| 319 Expect.equals(0, queue.length); | |
| 320 Expect.isTrue(queue.isEmpty); | |
| 321 } | |
| 322 | |
| 323 void testFromListToList() { | |
| 324 const int N = 256; | |
| 325 List list = []; | |
| 326 for (int i = 0; i < N; i++) { | |
| 327 Queue queue = newQueueFrom(list); | |
| 328 | |
| 329 Expect.equals(list.length, queue.length); | |
| 330 List to = queue.toList(); | |
| 331 Expect.listEquals(list, to); | |
| 332 | |
| 333 queue.add(i); | |
| 334 list.add(i); | |
| 335 Expect.equals(list.length, queue.length); | |
| 336 to = queue.toList(); | |
| 337 Expect.listEquals(list, to); | |
| 338 } | |
| 339 } | |
| 340 } | |
| 341 | |
| 342 class ListQueueTest extends QueueTest { | |
| 343 Queue newQueue() => new ListQueue(); | |
| 344 Queue newQueueFrom(Iterable elements) => new ListQueue.from(elements); | |
| 345 | |
| 346 void testMain() { | |
| 347 super.testMain(); | |
| 348 trickyTest(); | |
| 349 } | |
| 350 | |
| 351 void trickyTest() { | |
| 352 // Test behavior around the know growing capacities of a ListQueue. | |
| 353 Queue q = new ListQueue(); | |
| 354 | |
| 355 for (int i = 0; i < 255; i++) { | |
| 356 q.add(i); | |
| 357 } | |
| 358 for (int i = 0; i < 128; i++) { | |
| 359 Expect.equals(i, q.removeFirst()); | |
| 360 } | |
| 361 q.add(255); | |
| 362 for (int i = 0; i < 127; i++) { | |
| 363 q.add(i); | |
| 364 } | |
| 365 | |
| 366 Expect.equals(255, q.length); | |
| 367 | |
| 368 // Remove element at end of internal buffer. | |
| 369 q.removeWhere((v) => v == 255); | |
| 370 // Remove element at beginning of internal buffer. | |
| 371 q.removeWhere((v) => v == 0); | |
| 372 // Remove element at both ends of internal buffer. | |
| 373 q.removeWhere((v) => v == 254 || v == 1); | |
| 374 | |
| 375 Expect.equals(251, q.length); | |
| 376 | |
| 377 Iterable i255 = new Iterable.generate(255, (x) => x); | |
| 378 | |
| 379 q = new ListQueue(); | |
| 380 q.addAll(i255); | |
| 381 Expect.listEquals(i255.toList(), q.toList()); | |
| 382 | |
| 383 q = new ListQueue(); | |
| 384 q.addAll(i255.toList()); | |
| 385 Expect.listEquals(i255.toList(), q.toList()); | |
| 386 | |
| 387 q = new ListQueue.from(i255); | |
| 388 for (int i = 0; i < 128; i++) q.removeFirst(); | |
| 389 q.add(256); | |
| 390 q.add(0); | |
| 391 q.addAll(i255.toList()); | |
| 392 Expect.equals(129 + 255, q.length); | |
| 393 | |
| 394 // Test addAll that requires the queue to grow. | |
| 395 q = new ListQueue(); | |
| 396 q.addAll(i255.take(35)); | |
| 397 q.addAll(i255.skip(35).take(96)); | |
| 398 q.addAll(i255.skip(35 + 96)); | |
| 399 Expect.listEquals(i255.toList(), q.toList()); | |
| 400 } | |
| 401 } | |
| 402 | |
| 403 class DoubleLinkedQueueTest extends QueueTest { | |
| 404 Queue newQueue() => new DoubleLinkedQueue(); | |
| 405 Queue newQueueFrom(Iterable elements) => new DoubleLinkedQueue.from(elements); | |
| 406 | |
| 407 void testMain() { | |
| 408 super.testMain(); | |
| 409 testQueueElements(); | |
| 410 } | |
| 411 | |
| 412 void testQueueElements() { | |
| 413 DoubleLinkedQueue<int> queue1 = new DoubleLinkedQueue<int>.from([1, 2, 3]); | |
| 414 DoubleLinkedQueue<int> queue2 = new DoubleLinkedQueue<int>(); | |
| 415 queue2.addAll(queue1); | |
| 416 | |
| 417 Expect.equals(queue1.length, queue2.length); | |
| 418 DoubleLinkedQueueEntry<int> entry1 = queue1.firstEntry(); | |
| 419 DoubleLinkedQueueEntry<int> entry2 = queue2.firstEntry(); | |
| 420 while (entry1 != null) { | |
| 421 Expect.equals(true, !identical(entry1, entry2)); | |
| 422 entry1 = entry1.nextEntry(); | |
| 423 entry2 = entry2.nextEntry(); | |
| 424 } | |
| 425 Expect.equals(null, entry2); | |
| 426 | |
| 427 var firstEntry = queue1.firstEntry(); | |
| 428 var secondEntry = queue1.firstEntry().nextEntry(); | |
| 429 var thirdEntry = queue1.lastEntry(); | |
| 430 firstEntry.prepend(4); | |
| 431 firstEntry.append(5); | |
| 432 secondEntry.prepend(6); | |
| 433 secondEntry.append(7); | |
| 434 thirdEntry.prepend(8); | |
| 435 thirdEntry.append(9); | |
| 436 Expect.equals(9, queue1.length); | |
| 437 Expect.listEquals(queue1.toList(), [4, 1, 5, 6, 2, 7, 8, 3, 9]); | |
| 438 Expect.equals(1, firstEntry.remove()); | |
| 439 Expect.equals(2, secondEntry.remove()); | |
| 440 Expect.equals(3, thirdEntry.remove()); | |
| 441 Expect.equals(6, queue1.length); | |
| 442 Expect.listEquals(queue1.toList(), [4, 5, 6, 7, 8, 9]); | |
| 443 } | |
| 444 } | |
| 445 | |
| 446 void linkEntryTest() { | |
| 447 var entry = new DoubleLinkedQueueEntry(42); | |
| 448 Expect.equals(null, entry.previousEntry()); | |
| 449 Expect.equals(null, entry.nextEntry()); | |
| 450 | |
| 451 entry.append(37); | |
| 452 entry.prepend(87); | |
| 453 var prev = entry.previousEntry(); | |
| 454 var next = entry.nextEntry(); | |
| 455 Expect.equals(42, entry.element); | |
| 456 Expect.equals(37, next.element); | |
| 457 Expect.equals(87, prev.element); | |
| 458 Expect.identical(entry, prev.nextEntry()); | |
| 459 Expect.identical(entry, next.previousEntry()); | |
| 460 Expect.equals(null, next.nextEntry()); | |
| 461 Expect.equals(null, prev.previousEntry()); | |
| 462 | |
| 463 entry.element = 117; | |
| 464 Expect.equals(117, entry.element); | |
| 465 Expect.identical(next, entry.nextEntry()); | |
| 466 Expect.identical(prev, entry.previousEntry()); | |
| 467 | |
| 468 Expect.equals(117, entry.remove()); | |
| 469 Expect.identical(next, prev.nextEntry()); | |
| 470 Expect.identical(prev, next.previousEntry()); | |
| 471 Expect.equals(null, next.nextEntry()); | |
| 472 Expect.equals(null, prev.previousEntry()); | |
| 473 Expect.equals(37, next.element); | |
| 474 Expect.equals(87, prev.element); | |
| 475 | |
| 476 Expect.equals(37, next.remove()); | |
| 477 Expect.equals(87, prev.element); | |
| 478 Expect.equals(null, prev.nextEntry()); | |
| 479 Expect.equals(null, prev.previousEntry()); | |
| 480 | |
| 481 Expect.equals(87, prev.remove()); | |
| 482 } | |
| 483 | |
| 484 main() { | |
| 485 new DoubleLinkedQueueTest().testMain(); | |
| 486 new ListQueueTest().testMain(); | |
| 487 linkEntryTest(); | |
| 488 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2987203002:
Migrated test block 17 to Dart 2.0. (Closed)
