blob: eb9e1de3f2f5dbb8dec9a7da41b80ea82f7fd3f0 [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. /// A selection of data manipulation algorithms. library pkg.collection.algorithms; import 'dart:math' show Random; import 'utils.dart'; /// Returns a position of the [value] in [sortedList], if it is there. /// /// If the list isn't sorted according to the [compare] function, the result /// is unpredictable. /// /// If [compare] is omitted, this defaults to calling [Comparable.compareTo] on /// the objects. In this case, the objects must be [Comparable]. /// /// Returns -1 if [value] is not in the list. int binarySearch(List sortedList, E value, {int Function(E, E)? compare}) { compare ??= defaultCompare; return binarySearchBy(sortedList, identity, compare, value); } /// Returns a position of the [value] in [sortedList], if it is there. /// /// If the list isn't sorted according to the [compare] function on the [keyOf] /// property of the elements, the result is unpredictable. /// /// Returns -1 if [value] is not in the list by default. /// /// If [start] and [end] are supplied, only that range is searched, /// and only that range need to be sorted. int binarySearchBy(List sortedList, K Function(E element) keyOf, int Function(K, K) compare, E value, [int start = 0, int? end]) { end = RangeError.checkValidRange(start, end, sortedList.length); var min = start; var max = end; var key = keyOf(value); while (min < max) { var mid = min + ((max - min) >> 1); var element = sortedList[mid]; var comp = compare(keyOf(element), key); if (comp == 0) return mid; if (comp < 0) { min = mid + 1; } else { max = mid; } } return -1; } /// Returns the first position in [sortedList] that does not compare less than /// [value]. /// /// Uses binary search to find the location of [value]. /// This takes on the order of `log(n)` comparisons. /// If the list isn't sorted according to the [compare] function, the result /// is unpredictable. /// /// If [compare] is omitted, this defaults to calling [Comparable.compareTo] on /// the objects. In this case, the objects must be [Comparable]. /// /// Returns [sortedList.length] if all the items in [sortedList] compare less /// than [value]. int lowerBound(List sortedList, E value, {int Function(E, E)? compare}) { compare ??= defaultCompare; return lowerBoundBy(sortedList, identity, compare, value); } /// Returns the first position in [sortedList] that is not before [value]. /// /// Uses binary search to find the location of [value]. /// This takes on the order of `log(n)` comparisons. /// Elements are compared using the [compare] function of the [keyOf] property of /// the elements. /// If the list isn't sorted according to this order, the result is unpredictable. /// /// Returns [sortedList.length] if all the items in [sortedList] are before [value]. /// /// If [start] and [end] are supplied, only that range is searched, /// and only that range need to be sorted. int lowerBoundBy(List sortedList, K Function(E element) keyOf, int Function(K, K) compare, E value, [int start = 0, int? end]) { end = RangeError.checkValidRange(start, end, sortedList.length); var min = start; var max = end; var key = keyOf(value); while (min < max) { var mid = min + ((max - min) >> 1); var element = sortedList[mid]; var comp = compare(keyOf(element), key); if (comp < 0) { min = mid + 1; } else { max = mid; } } return min; } /// Shuffles a list randomly. /// /// A sub-range of a list can be shuffled by providing [start] and [end]. /// /// If [start] or [end] are omitted, /// they default to the start and end of the list. /// /// If [random] is omitted, it defaults to a new instance of [Random]. void shuffle(List elements, [int start = 0, int? end, Random? random]) { random ??= Random(); end ??= elements.length; var length = end - start; while (length > 1) { var pos = random.nextInt(length); length--; var tmp1 = elements[start + pos]; elements[start + pos] = elements[start + length]; elements[start + length] = tmp1; } } /// Reverses a list, or a part of a list, in-place. void reverse(List elements, [int start = 0, int? end]) { end = RangeError.checkValidRange(start, end, elements.length); _reverse(elements, start, end); } /// Internal helper function that assumes valid arguments. void _reverse(List elements, int start, int end) { for (var i = start, j = end - 1; i < j; i++, j--) { var tmp = elements[i]; elements[i] = elements[j]; elements[j] = tmp; } } /// Sort a list between [start] (inclusive) and [end] (exclusive) using /// insertion sort. /// /// If [compare] is omitted, this defaults to calling [Comparable.compareTo] on /// the objects. In this case, the objects must be [Comparable]. /// /// Insertion sort is a simple sorting algorithm. For `n` elements it does on /// the order of `n * log(n)` comparisons but up to `n` squared moves. The /// sorting is performed in-place, without using extra memory. /// /// For short lists the many moves have less impact than the simple algorithm, /// and it is often the favored sorting algorithm for short lists. /// /// This insertion sort is stable: Equal elements end up in the same order /// as they started in. void insertionSort(List elements, {int Function(E, E)? compare, int start = 0, int? end}) { // If the same method could have both positional and named optional // parameters, this should be (list, [start, end], {compare}). compare ??= defaultCompare; end ??= elements.length; for (var pos = start + 1; pos < end; pos++) { var min = start; var max = pos; var element = elements[pos]; while (min < max) { var mid = min + ((max - min) >> 1); var comparison = compare(element, elements[mid]); if (comparison < 0) { max = mid; } else { min = mid + 1; } } elements.setRange(min + 1, pos + 1, elements, min); elements[min] = element; } } /// Generalized insertion sort. /// /// Performs insertion sort on the [elements] range from [start] to [end]. /// Ordering is the [compare] of the [keyOf] of the elements. void insertionSortBy(List elements, K Function(E element) keyOf, int Function(K a, K b) compare, [int start = 0, int? end]) { end = RangeError.checkValidRange(start, end, elements.length); _movingInsertionSort(elements, keyOf, compare, start, end, elements, start); } /// Limit below which merge sort defaults to insertion sort. const int _mergeSortLimit = 32; /// Sorts a list between [start] (inclusive) and [end] (exclusive) using the /// merge sort algorithm. /// /// If [compare] is omitted, this defaults to calling [Comparable.compareTo] on /// the objects. If any object is not [Comparable], that throws a [TypeError]. /// /// Merge-sorting works by splitting the job into two parts, sorting each /// recursively, and then merging the two sorted parts. /// /// This takes on the order of `n * log(n)` comparisons and moves to sort /// `n` elements, but requires extra space of about the same size as the list /// being sorted. /// /// This merge sort is stable: Equal elements end up in the same order /// as they started in. void mergeSort(List elements, {int start = 0, int? end, int Function(E, E)? compare}) { end = RangeError.checkValidRange(start, end, elements.length); compare ??= defaultCompare; var length = end - start; if (length < 2) return; if (length < _mergeSortLimit) { insertionSort(elements, compare: compare, start: start, end: end); return; } // Special case the first split instead of directly calling // _mergeSort, because the _mergeSort requires its target to // be different from its source, and it requires extra space // of the same size as the list to sort. // This split allows us to have only half as much extra space, // and allows the sorted elements to end up in the original list. var firstLength = (end - start) >> 1; var middle = start + firstLength; var secondLength = end - middle; // secondLength is always the same as firstLength, or one greater. var scratchSpace = List.filled(secondLength, elements[start]); E Function(E) id = identity; _mergeSort(elements, id, compare, middle, end, scratchSpace, 0); var firstTarget = end - firstLength; _mergeSort(elements, id, compare, start, middle, elements, firstTarget); _merge(id, compare, elements, firstTarget, end, scratchSpace, 0, secondLength, elements, start); } /// Sort [elements] using a merge-sort algorithm. /// /// The elements are compared using [compare] on the value provided by [keyOf] /// on the element. /// If [start] and [end] are provided, only that range is sorted. /// /// Uses insertion sort for smaller sublists. void mergeSortBy(List elements, K Function(E element) keyOf, int Function(K a, K b) compare, [int start = 0, int? end]) { end = RangeError.checkValidRange(start, end, elements.length); var length = end - start; if (length < 2) return; if (length < _mergeSortLimit) { _movingInsertionSort(elements, keyOf, compare, start, end, elements, start); return; } // Special case the first split instead of directly calling // _mergeSort, because the _mergeSort requires its target to // be different from its source, and it requires extra space // of the same size as the list to sort. // This split allows us to have only half as much extra space, // and it ends up in the original place. var middle = start + (length >> 1); var firstLength = middle - start; var secondLength = end - middle; // secondLength is always the same as firstLength, or one greater. var scratchSpace = List.filled(secondLength, elements[start]); _mergeSort(elements, keyOf, compare, middle, end, scratchSpace, 0); var firstTarget = end - firstLength; _mergeSort(elements, keyOf, compare, start, middle, elements, firstTarget); _merge(keyOf, compare, elements, firstTarget, end, scratchSpace, 0, secondLength, elements, start); } /// Performs an insertion sort into a potentially different list than the /// one containing the original values. /// /// It will work in-place as well. void _movingInsertionSort( List list, K Function(E element) keyOf, int Function(K, K) compare, int start, int end, List target, int targetOffset) { var length = end - start; if (length == 0) return; target[targetOffset] = list[start]; for (var i = 1; i < length; i++) { var element = list[start + i]; var elementKey = keyOf(element); var min = targetOffset; var max = targetOffset + i; while (min < max) { var mid = min + ((max - min) >> 1); if (compare(elementKey, keyOf(target[mid])) < 0) { max = mid; } else { min = mid + 1; } } target.setRange(min + 1, targetOffset + i + 1, target, min); target[min] = element; } } /// Sorts [elements] from [start] to [end] into [target] at [targetOffset]. /// /// The `target` list must be able to contain the range from `start` to `end` /// after `targetOffset`. /// /// Allows target to be the same list as [elements], as long as it's not /// overlapping the `start..end` range. void _mergeSort( List elements, K Function(E element) keyOf, int Function(K, K) compare, int start, int end, List target, int targetOffset) { var length = end - start; if (length < _mergeSortLimit) { _movingInsertionSort( elements, keyOf, compare, start, end, target, targetOffset); return; } var middle = start + (length >> 1); var firstLength = middle - start; var secondLength = end - middle; // Here secondLength >= firstLength (differs by at most one). var targetMiddle = targetOffset + firstLength; // Sort the second half into the end of the target area. _mergeSort(elements, keyOf, compare, middle, end, target, targetMiddle); // Sort the first half into the end of the source area. _mergeSort(elements, keyOf, compare, start, middle, elements, middle); // Merge the two parts into the target area. _merge(keyOf, compare, elements, middle, middle + firstLength, target, targetMiddle, targetMiddle + secondLength, target, targetOffset); } /// Merges two lists into a target list. /// /// One of the input lists may be positioned at the end of the target /// list. /// /// For equal object, elements from [firstList] are always preferred. /// This allows the merge to be stable if the first list contains elements /// that started out earlier than the ones in [secondList] void _merge( K Function(E element) keyOf, int Function(K, K) compare, List firstList, int firstStart, int firstEnd, List secondList, int secondStart, int secondEnd, List target, int targetOffset) { // No empty lists reaches here. assert(firstStart < firstEnd); assert(secondStart < secondEnd); var cursor1 = firstStart; var cursor2 = secondStart; var firstElement = firstList[cursor1++]; var firstKey = keyOf(firstElement); var secondElement = secondList[cursor2++]; var secondKey = keyOf(secondElement); while (true) { if (compare(firstKey, secondKey) <= 0) { target[targetOffset++] = firstElement; if (cursor1 == firstEnd) break; // Flushing second list after loop. firstElement = firstList[cursor1++]; firstKey = keyOf(firstElement); } else { target[targetOffset++] = secondElement; if (cursor2 != secondEnd) { secondElement = secondList[cursor2++]; secondKey = keyOf(secondElement); continue; } // Second list empties first. Flushing first list here. target[targetOffset++] = firstElement; target.setRange(targetOffset, targetOffset + (firstEnd - cursor1), firstList, cursor1); return; } } // First list empties first. Reached by break above. target[targetOffset++] = secondElement; target.setRange( targetOffset, targetOffset + (secondEnd - cursor2), secondList, cursor2); } /// Sort [elements] using a quick-sort algorithm. /// /// The elements are compared using [compare] on the elements. /// If [start] and [end] are provided, only that range is sorted. /// /// Uses insertion sort for smaller sublists. void quickSort(List elements, int Function(E a, E b) compare, [int start = 0, int? end]) { end = RangeError.checkValidRange(start, end, elements.length); _quickSort(elements, identity, compare, Random(), start, end); } /// Sort [elements] using a quick-sort algorithm. /// /// The elements are compared using [compare] on the value provided by [keyOf] /// on the element. /// If [start] and [end] are provided, only that range is sorted. /// /// Uses insertion sort for smaller sublists. void quickSortBy( List list, K Function(E element) keyOf, int Function(K a, K b) compare, [int start = 0, int? end]) { end = RangeError.checkValidRange(start, end, list.length); _quickSort(list, keyOf, compare, Random(), start, end); } void _quickSort(List list, K Function(E element) keyOf, int Function(K a, K b) compare, Random random, int start, int end) { const minQuickSortLength = 24; var length = end - start; while (length >= minQuickSortLength) { var pivotIndex = random.nextInt(length) + start; var pivot = list[pivotIndex]; var pivotKey = keyOf(pivot); var endSmaller = start; var startGreater = end; var startPivots = end - 1; list[pivotIndex] = list[startPivots]; list[startPivots] = pivot; while (endSmaller < startPivots) { var current = list[endSmaller]; var relation = compare(keyOf(current), pivotKey); if (relation < 0) { endSmaller++; } else { startPivots--; var currentTarget = startPivots; list[endSmaller] = list[startPivots]; if (relation > 0) { startGreater--; currentTarget = startGreater; list[startPivots] = list[startGreater]; } list[currentTarget] = current; } } if (endSmaller - start < end - startGreater) { _quickSort(list, keyOf, compare, random, start, endSmaller); start = startGreater; } else { _quickSort(list, keyOf, compare, random, startGreater, end); end = endSmaller; } length = end - start; } _movingInsertionSort(list, keyOf, compare, start, end, list, start); }