blob: 0c6046351434946647af421f965b2b1aa2ed0939 [file] [log] [blame]
 // Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file // for details. All rights reserved. Use of this source code is governed by a // BSD-style license that can be found in the LICENSE file. /// Tests algorithm utilities. import 'dart:math'; import 'package:collection/collection.dart'; import 'package:collection/src/algorithms.dart'; import 'package:test/test.dart'; void main() { void testShuffle(List list) { var copy = list.toList(); shuffle(list); expect(UnorderedIterableEquality().equals(list, copy), isTrue); } test('Shuffle 0', () { testShuffle([]); }); test('Shuffle 1', () { testShuffle([1]); }); test('Shuffle 3', () { testShuffle([1, 2, 3]); }); test('Shuffle 10', () { testShuffle([1, 2, 3, 4, 5, 1, 3, 5, 7, 9]); }); test('Shuffle shuffles', () { var l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]; var c = l.toList(); var count = 0; do { shuffle(l); if (!const ListEquality().equals(c, l)) return; // Odds of not changing the order should be one in ~ 16! ~= 2e+13. // Repeat this 10 times, and the odds of accidentally shuffling to the // same result every time is disappearingly tiny. count++; // If this happens even once, it's ok to report it. print('Failed shuffle \$count times'); if (count == 10) fail("Shuffle didn't change order."); } while (true); }); test('Shuffle sublist', () { var l = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]; var c = l.toList(); shuffle(l, 4, 12); expect(const IterableEquality().equals(l.getRange(0, 4), c.getRange(0, 4)), isTrue); expect( const IterableEquality().equals(l.getRange(12, 16), c.getRange(12, 16)), isTrue); expect( const UnorderedIterableEquality() .equals(l.getRange(4, 12), c.getRange(4, 12)), isTrue); }); test('binsearch0', () { expect(binarySearch([], 2), equals(-1)); }); test('binsearch1', () { expect(binarySearch([5], 2), equals(-1)); expect(binarySearch([5], 5), equals(0)); expect(binarySearch([5], 7), equals(-1)); }); test('binsearch3', () { expect(binarySearch([0, 5, 10], -1), equals(-1)); expect(binarySearch([0, 5, 10], 0), equals(0)); expect(binarySearch([0, 5, 10], 2), equals(-1)); expect(binarySearch([0, 5, 10], 5), equals(1)); expect(binarySearch([0, 5, 10], 7), equals(-1)); expect(binarySearch([0, 5, 10], 10), equals(2)); expect(binarySearch([0, 5, 10], 12), equals(-1)); }); test('binsearchCompare0', () { expect(binarySearch([], C(2), compare: compareC), equals(-1)); }); test('binsearchCompare1', () { var l1 = [C(5)]; expect(binarySearch(l1, C(2), compare: compareC), equals(-1)); expect(binarySearch(l1, C(5), compare: compareC), equals(0)); expect(binarySearch(l1, C(7), compare: compareC), equals(-1)); }); test('binsearchCompare3', () { var l3 = [C(0), C(5), C(10)]; expect(binarySearch(l3, C(-1), compare: compareC), equals(-1)); expect(binarySearch(l3, C(0), compare: compareC), equals(0)); expect(binarySearch(l3, C(2), compare: compareC), equals(-1)); expect(binarySearch(l3, C(5), compare: compareC), equals(1)); expect(binarySearch(l3, C(7), compare: compareC), equals(-1)); expect(binarySearch(l3, C(10), compare: compareC), equals(2)); expect(binarySearch(l3, C(12), compare: compareC), equals(-1)); }); test('lowerbound0', () { expect(lowerBound([], 2), equals(0)); }); test('lowerbound1', () { expect(lowerBound([5], 2), equals(0)); expect(lowerBound([5], 5), equals(0)); expect(lowerBound([5], 7), equals(1)); }); test('lowerbound3', () { expect(lowerBound([0, 5, 10], -1), equals(0)); expect(lowerBound([0, 5, 10], 0), equals(0)); expect(lowerBound([0, 5, 10], 2), equals(1)); expect(lowerBound([0, 5, 10], 5), equals(1)); expect(lowerBound([0, 5, 10], 7), equals(2)); expect(lowerBound([0, 5, 10], 10), equals(2)); expect(lowerBound([0, 5, 10], 12), equals(3)); }); test('lowerboundRepeat', () { expect(lowerBound([5, 5, 5], 5), equals(0)); expect(lowerBound([0, 5, 5, 5, 10], 5), equals(1)); }); test('lowerboundCompare0', () { expect(lowerBound([], C(2), compare: compareC), equals(0)); }); test('lowerboundCompare1', () { var l1 = [C(5)]; expect(lowerBound(l1, C(2), compare: compareC), equals(0)); expect(lowerBound(l1, C(5), compare: compareC), equals(0)); expect(lowerBound(l1, C(7), compare: compareC), equals(1)); }); test('lowerboundCompare3', () { var l3 = [C(0), C(5), C(10)]; expect(lowerBound(l3, C(-1), compare: compareC), equals(0)); expect(lowerBound(l3, C(0), compare: compareC), equals(0)); expect(lowerBound(l3, C(2), compare: compareC), equals(1)); expect(lowerBound(l3, C(5), compare: compareC), equals(1)); expect(lowerBound(l3, C(7), compare: compareC), equals(2)); expect(lowerBound(l3, C(10), compare: compareC), equals(2)); expect(lowerBound(l3, C(12), compare: compareC), equals(3)); }); test('lowerboundCompareRepeat', () { var l1 = [C(5), C(5), C(5)]; var l2 = [C(0), C(5), C(5), C(5), C(10)]; expect(lowerBound(l1, C(5), compare: compareC), equals(0)); expect(lowerBound(l2, C(5), compare: compareC), equals(1)); }); void testSort(String name, void Function(List elements, [int? start, int? end]) sort) { test('\${name}Random', () { var random = Random(); for (var i = 0; i < 250; i += 10) { var list = [ for (var j = 0; j < i; j++) random.nextInt(25) // Expect some equal elements. ]; sort(list); for (var j = 1; j < i; j++) { expect(list[j - 1], lessThanOrEqualTo(list[j])); } } }); test('\${name}SubRanges', () { var l = [6, 5, 4, 3, 2, 1]; sort(l, 2, 4); expect(l, equals([6, 5, 3, 4, 2, 1])); sort(l, 1, 1); expect(l, equals([6, 5, 3, 4, 2, 1])); sort(l, 4, 6); expect(l, equals([6, 5, 3, 4, 1, 2])); sort(l, 0, 2); expect(l, equals([5, 6, 3, 4, 1, 2])); sort(l, 0, 6); expect(l, equals([1, 2, 3, 4, 5, 6])); }); test('\$name insertionSortSpecialCases', () { var l = [6, 6, 6, 6, 6, 6]; sort(l); expect(l, equals([6, 6, 6, 6, 6, 6])); l = [6, 6, 3, 3, 0, 0]; sort(l); expect(l, equals([0, 0, 3, 3, 6, 6])); }); } int intId(int x) => x; int intCompare(int a, int b) => a - b; testSort('insertionSort', (list, [start, end]) { insertionSortBy(list, intId, intCompare, start ?? 0, end ?? list.length); }); testSort('mergeSort compare', (list, [start, end]) { mergeSort(list, start: start ?? 0, end: end ?? list.length, compare: intCompare); }); testSort('mergeSort comparable', (list, [start, end]) { mergeSort(list, start: start ?? 0, end: end ?? list.length); }); testSort('mergeSortBy', (list, [start, end]) { mergeSortBy(list, intId, intCompare, start ?? 0, end ?? list.length); }); testSort('quickSort', (list, [start, end]) { quickSort(list, intCompare, start ?? 0, end ?? list.length); }); testSort('quickSortBy', (list, [start, end]) { quickSortBy(list, intId, intCompare, start ?? 0, end ?? list.length); }); test('MergeSortSpecialCases', () { for (var size in [511, 512, 513]) { // All equal. var list = List.generate(size, (i) => OC(0, i)); mergeSort(list); for (var i = 0; i < size; i++) { expect(list[i].order, equals(i)); } // All but one equal, first. list[0] = OC(1, 0); for (var i = 1; i < size; i++) { list[i] = OC(0, i); } mergeSort(list); for (var i = 0; i < size - 1; i++) { expect(list[i].order, equals(i + 1)); } expect(list[size - 1].order, equals(0)); // All but one equal, last. for (var i = 0; i < size - 1; i++) { list[i] = OC(0, i); } list[size - 1] = OC(-1, size - 1); mergeSort(list); expect(list[0].order, equals(size - 1)); for (var i = 1; i < size; i++) { expect(list[i].order, equals(i - 1)); } // Reversed. for (var i = 0; i < size; i++) { list[i] = OC(size - 1 - i, i); } mergeSort(list); for (var i = 0; i < size; i++) { expect(list[i].id, equals(i)); expect(list[i].order, equals(size - 1 - i)); } } }); void testSortBy( String name, void Function(List elements, K Function(T element) keyOf, int Function(K a, K b) compare, [int start, int end]) sort) { for (var n in [0, 1, 2, 10, 75, 250]) { var name2 = name; test('\$name2: Same #\$n', () { var list = List.generate(n, (i) => OC(i, 0)); // Should succeed. Bad implementations of, e.g., quicksort can diverge. sort(list, ocOrder, compareInt); }); test('\$name: Pre-sorted #\$n', () { var list = List.generate(n, (i) => OC(-i, i)); var expected = list.toList(); sort(list, ocOrder, compareInt); // Elements have not moved. expect(list, expected); }); test('\$name: Reverse-sorted #\$n', () { var list = List.generate(n, (i) => OC(i, -i)); sort(list, ocOrder, compareInt); expectSorted(list, ocOrder, compareInt); }); test('\$name: Random #\$n', () { var random = Random(); var list = List.generate(n, (i) => OC(i, random.nextInt(n))); sort(list, ocOrder, compareInt); expectSorted(list, ocOrder, compareInt); }); test('\$name: Sublist #\$n', () { var random = Random(); var list = List.generate(n, (i) => OC(i, random.nextInt(n))); var original = list.toList(); var start = n ~/ 4; var end = start * 3; sort(list, ocOrder, compareInt, start, end); expectSorted(list, ocOrder, compareInt, start, end); expect(list.sublist(0, start), original.sublist(0, start)); expect(list.sublist(end), original.sublist(end)); }); } } testSortBy('insertionSort', insertionSortBy); testSortBy('mergeSort', mergeSortBy); testSortBy('quickSortBy', quickSortBy); test('MergeSortPreservesOrder', () { var random = Random(); // Small case where only insertion call is called, // larger case where the internal moving insertion sort is used // larger cases with multiple splittings, numbers just around a power of 2. for (var size in [8, 50, 511, 512, 513]) { // Class OC compares using id. // With size elements with id's in the range 0..size/4, a number of // collisions are guaranteed. These should be sorted so that the 'order' // part of the objects are still in order. var list = [ for (var i = 0; i < size; i++) OC(random.nextInt(size >> 2), i) ]; mergeSort(list); var prev = list[0]; for (var i = 1; i < size; i++) { var next = list[i]; expect(prev.id, lessThanOrEqualTo(next.id)); if (next.id == prev.id) { expect(prev.order, lessThanOrEqualTo(next.order)); } prev = next; } // Reverse compare on part of list. List copy = list.toList(); var min = size >> 2; var max = size - min; mergeSort(list, start: min, end: max, compare: (a, b) => b.compareTo(a)); prev = list[min]; for (var i = min + 1; i < max; i++) { var next = list[i]; expect(prev.id, greaterThanOrEqualTo(next.id)); if (next.id == prev.id) { expect(prev.order, lessThanOrEqualTo(next.order)); } prev = next; } // Equals on OC objects is identity, so this means the parts before min, // and the parts after max, didn't change at all. expect(list.sublist(0, min), equals(copy.sublist(0, min))); expect(list.sublist(max), equals(copy.sublist(max))); } }); test('Reverse', () { var l = [6, 5, 4, 3, 2, 1]; reverse(l, 2, 4); expect(l, equals([6, 5, 3, 4, 2, 1])); reverse(l, 1, 1); expect(l, equals([6, 5, 3, 4, 2, 1])); reverse(l, 4, 6); expect(l, equals([6, 5, 3, 4, 1, 2])); reverse(l, 0, 2); expect(l, equals([5, 6, 3, 4, 1, 2])); reverse(l, 0, 6); expect(l, equals([2, 1, 4, 3, 6, 5])); }); } class C { final int id; C(this.id); } int compareC(C one, C other) => one.id - other.id; int cId(C c) => c.id; /// Class naturally ordered by its first constructor argument. class OC implements Comparable { final int id; final int order; OC(this.id, this.order); @override int compareTo(OC other) => id - other.id; @override String toString() => 'OC[\$id,\$order]'; } int ocId(OC oc) => oc.id; int ocOrder(OC oc) => oc.order; int compareInt(int a, int b) => a - b; /// Check that a list is sorted according to [compare] of [keyOf] of elements. void expectSorted( List list, K Function(T element) keyOf, int Function(K a, K b) compare, [int start = 0, int? end]) { end ??= list.length; if (start == end) return; var prev = keyOf(list[start]); for (var i = start + 1; i < end; i++) { var next = keyOf(list[i]); expect(compare(prev, next), isNonPositive); prev = next; } }