| OLD | NEW |
| 1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file | 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 | 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. | 3 // BSD-style license that can be found in the LICENSE file. |
| 4 | 4 |
| 5 // Dart test for sort routines. | 5 // Dart test for sort routines. |
| 6 #library("SortTest.dart"); | 6 #library("SortTest.dart"); |
| 7 #import("dart:coreimpl"); | 7 #import("dart:coreimpl"); |
| 8 #source("SortHelper.dart"); | 8 #source("SortHelper.dart"); |
| 9 | 9 |
| 10 void checkListEquals(List expected, List actual) { | |
| 11 Expect.equals(expected.length, actual.length); | |
| 12 for (int i = 0; i < expected.length; i++) { | |
| 13 Expect.equals(expected[i], actual[i]); | |
| 14 } | |
| 15 } | |
| 16 | |
| 17 main() { | 10 main() { |
| 18 var compare = (a, b) => a.compareTo(b); | 11 var compare = (a, b) => a.compareTo(b); |
| 19 var sort = (list) => DualPivotQuicksort.sort(list, compare); | 12 var sort = (list) => DualPivotQuicksort.sort(list, compare); |
| 20 new SortHelper(sort, compare).run(); | 13 new SortHelper(sort, compare).run(); |
| 21 | 14 |
| 22 compare = (a, b) => -a.compareTo(b); | 15 compare = (a, b) => -a.compareTo(b); |
| 23 new SortHelper(sort, compare).run(); | 16 new SortHelper(sort, compare).run(); |
| 24 | 17 |
| 25 compare = (a, b) => a.compareTo(b); | 18 compare = (a, b) => a.compareTo(b); |
| 26 | 19 |
| 27 // Pivot-canditate indices: 7, 15, 22, 29, 37 | 20 // Pivot-canditate indices: 7, 15, 22, 29, 37 |
| 28 // Test dutch flag partitioning (canditates 2 and 4 are the same). | 21 // Test dutch flag partitioning (canditates 2 and 4 are the same). |
| 29 var list = [0, 0, 0, 0, 0, 0, 0, 0/**/, 0, 0, 0, 0, 0, 0, 0, | 22 var list = [0, 0, 0, 0, 0, 0, 0, 0/**/, 0, 0, 0, 0, 0, 0, 0, |
| 30 1/**/, 1, 1, 1, 1, 1, 1, 1/**/, 1, 1, 1, 1, 1, 1, 1/**/, | 23 1/**/, 1, 1, 1, 1, 1, 1, 1/**/, 1, 1, 1, 1, 1, 1, 1/**/, |
| 31 2, 2, 2, 2, 2, 2, 2, 2/**/, 2, 2, 2, 2, 2, 2, 2]; | 24 2, 2, 2, 2, 2, 2, 2, 2/**/, 2, 2, 2, 2, 2, 2, 2]; |
| 32 list.sort(compare); | 25 list.sort(compare); |
| 33 checkListEquals(list, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | 26 Expect.listEquals(list, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
| 34 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, | 27 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, |
| 35 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]); | 28 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]); |
| 36 | 29 |
| 37 list = [0, 0, 0, 0, 0, 0, 0, 1/**/, 0, 0, 0, 0, 0, 0, 0, | 30 list = [0, 0, 0, 0, 0, 0, 0, 1/**/, 0, 0, 0, 0, 0, 0, 0, |
| 38 0/**/, 1, 1, 1, 1, 1, 1, 0/**/, 1, 1, 1, 1, 1, 1, 0/**/, | 31 0/**/, 1, 1, 1, 1, 1, 1, 0/**/, 1, 1, 1, 1, 1, 1, 0/**/, |
| 39 2/**/, 2, 2, 2, 2, 2, 2, 2/**/, 2, 2, 2, 2, 2, 2, 2]; | 32 2/**/, 2, 2, 2, 2, 2, 2, 2/**/, 2, 2, 2, 2, 2, 2, 2]; |
| 40 list.sort(compare); | 33 list.sort(compare); |
| 41 checkListEquals(list, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | 34 Expect.listEquals(list, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, |
| 42 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, | 35 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, |
| 43 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]); | 36 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]); |
| 44 | 37 |
| 45 // Pivots: 1 and 8. | 38 // Pivots: 1 and 8. |
| 46 // The second partition will be big (more than 2/3 of the list), and an | 39 // The second partition will be big (more than 2/3 of the list), and an |
| 47 // optimization kicks in that removes the pivots from the partition. | 40 // optimization kicks in that removes the pivots from the partition. |
| 48 list = [0, 9, 0, 9, 3, 9, 0, 1/**/, 1, 0, 1, 9, 8, 2, 1, | 41 list = [0, 9, 0, 9, 3, 9, 0, 1/**/, 1, 0, 1, 9, 8, 2, 1, |
| 49 1/**/, 4, 5, 2, 5, 0, 1, 8/**/, 8, 8, 5, 2, 2, 9, 8/**/, | 42 1/**/, 4, 5, 2, 5, 0, 1, 8/**/, 8, 8, 5, 2, 2, 9, 8/**/, |
| 50 8, 4, 4, 1, 5, 3, 2, 8/**/, 5, 1, 2, 8, 5, 6, 8]; | 43 8, 4, 4, 1, 5, 3, 2, 8/**/, 5, 1, 2, 8, 5, 6, 8]; |
| 51 list.sort(compare); | 44 list.sort(compare); |
| 52 checkListEquals(list, [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, | 45 Expect.listEquals(list, [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, |
| 53 2, 2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 5, | 46 2, 2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 5, |
| 54 6, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9]); | 47 6, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9]); |
| 55 } | 48 } |
| OLD | NEW |