mirror of
https://github.com/apple/swift-algorithms
synced 2026-11-22 04:10:39 +00:00
394 lines
14 KiB
Swift
394 lines
14 KiB
Swift
//===----------------------------------------------------------------------===//
|
|
//
|
|
// This source file is part of the Swift Algorithms open source project
|
|
//
|
|
// Copyright (c) 2020 Apple Inc. and the Swift project authors
|
|
// Licensed under Apache License v2.0 with Runtime Library Exception
|
|
//
|
|
// See https://swift.org/LICENSE.txt for license information
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
extension Sequence {
|
|
/// Implementation for min(count:areInIncreasingOrder:)
|
|
@inlinable
|
|
internal func _minImplementation(
|
|
count: Int,
|
|
sortedBy areInIncreasingOrder: (Element, Element) throws -> Bool
|
|
) rethrows -> [Element] {
|
|
var iterator = makeIterator()
|
|
|
|
var result: [Element] = []
|
|
result.reserveCapacity(count)
|
|
while result.count < count, let e = iterator.next() {
|
|
result.append(e)
|
|
}
|
|
try result.sort(by: areInIncreasingOrder)
|
|
|
|
while let e = iterator.next() {
|
|
// To be part of `result`, `e` must be strictly less than `result.last`.
|
|
guard try areInIncreasingOrder(e, result.last!) else { continue }
|
|
let insertionIndex =
|
|
try result.partitioningIndex { try areInIncreasingOrder(e, $0) }
|
|
|
|
assert(insertionIndex != result.endIndex)
|
|
result.removeLast()
|
|
result.insert(e, at: insertionIndex)
|
|
}
|
|
|
|
return result
|
|
}
|
|
|
|
/// Implementation for max(count:areInIncreasingOrder:)
|
|
@inlinable
|
|
internal func _maxImplementation(
|
|
count: Int,
|
|
sortedBy areInIncreasingOrder: (Element, Element) throws -> Bool
|
|
) rethrows -> [Element] {
|
|
var iterator = makeIterator()
|
|
|
|
var result: [Element] = []
|
|
result.reserveCapacity(count)
|
|
while result.count < count, let e = iterator.next() {
|
|
result.append(e)
|
|
}
|
|
try result.sort(by: areInIncreasingOrder)
|
|
|
|
while let e = iterator.next() {
|
|
// To be part of `result`, `e` must be greater/equal to `result.first`.
|
|
guard try !areInIncreasingOrder(e, result.first!) else { continue }
|
|
let insertionIndex =
|
|
try result.partitioningIndex { try areInIncreasingOrder(e, $0) }
|
|
|
|
assert(insertionIndex > 0)
|
|
// Inserting `e` and then removing the first element (or vice versa)
|
|
// would perform a double shift, so we manually shift down the elements
|
|
// before dropping `e` in.
|
|
var i = 1
|
|
while i < insertionIndex {
|
|
result[i - 1] = result[i]
|
|
i += 1
|
|
}
|
|
result[insertionIndex - 1] = e
|
|
}
|
|
|
|
return result
|
|
}
|
|
|
|
/// Returns the smallest elements of this sequence, as sorted by the given
|
|
/// predicate.
|
|
///
|
|
/// This example partially sorts an array of integers to retrieve its three
|
|
/// smallest values:
|
|
///
|
|
/// let numbers = [7, 1, 6, 2, 8, 3, 9]
|
|
/// let smallestThree = numbers.min(count: 3, sortedBy: <)
|
|
/// // [1, 2, 3]
|
|
///
|
|
/// If you need to sort a sequence but only need to access its smallest
|
|
/// elements, using this method can give you a performance boost over sorting
|
|
/// the entire sequence. The order of equal elements is guaranteed to be
|
|
/// preserved.
|
|
///
|
|
/// - Parameters:
|
|
/// - count: The number of elements to return. If `count` is greater than
|
|
/// the number of elements in this sequence, all of the sequence's
|
|
/// elements are returned.
|
|
/// - areInIncreasingOrder: A predicate that returns `true` if its
|
|
/// first argument should be ordered before its second argument;
|
|
/// otherwise, `false`.
|
|
/// - Returns: An array of the smallest `count` elements of this sequence,
|
|
/// sorted according to `areInIncreasingOrder`.
|
|
///
|
|
/// - Complexity: O(*k* log *k* + *nk*), where *n* is the length of the
|
|
/// sequence and *k* is `count`.
|
|
@inlinable
|
|
public func min(
|
|
count: Int,
|
|
sortedBy areInIncreasingOrder: (Element, Element) throws -> Bool
|
|
) rethrows -> [Element] {
|
|
precondition(
|
|
count >= 0,
|
|
"""
|
|
Cannot find a minimum with a negative count of elements!
|
|
"""
|
|
)
|
|
|
|
// Do nothing if we're prefixing nothing.
|
|
guard count > 0 else {
|
|
return []
|
|
}
|
|
|
|
return try _minImplementation(count: count, sortedBy: areInIncreasingOrder)
|
|
}
|
|
|
|
/// Returns the largest elements of this sequence, as sorted by the given
|
|
/// predicate.
|
|
///
|
|
/// This example partially sorts an array of integers to retrieve its three
|
|
/// largest values:
|
|
///
|
|
/// let numbers = [7, 1, 6, 2, 8, 3, 9]
|
|
/// let smallestThree = numbers.max(count: 3, sortedBy: <)
|
|
/// // [7, 8, 9]
|
|
///
|
|
/// If you need to sort a sequence but only need to access its largest
|
|
/// elements, using this method can give you a performance boost over sorting
|
|
/// the entire sequence. The order of equal elements is guaranteed to be
|
|
/// preserved.
|
|
///
|
|
/// - Parameters:
|
|
/// - count: The number of elements to return. If `count` is greater than
|
|
/// the number of elements in this sequence, all of the sequence's
|
|
/// elements are returned.
|
|
/// - areInIncreasingOrder: A predicate that returns `true` if its
|
|
/// first argument should be ordered before its second argument;
|
|
/// otherwise, `false`.
|
|
/// - Returns: An array of the largest `count` elements of this sequence,
|
|
/// sorted according to `areInIncreasingOrder`.
|
|
///
|
|
/// - Complexity: O(*k* log *k* + *nk*), where *n* is the length of the
|
|
/// sequence and *k* is `count`.
|
|
@inlinable
|
|
public func max(
|
|
count: Int,
|
|
sortedBy areInIncreasingOrder: (Element, Element) throws -> Bool
|
|
) rethrows -> [Element] {
|
|
precondition(
|
|
count >= 0,
|
|
"""
|
|
Cannot find a maximum with a negative count of elements!
|
|
"""
|
|
)
|
|
|
|
// Do nothing if we're suffixing nothing.
|
|
guard count > 0 else {
|
|
return []
|
|
}
|
|
|
|
return try _maxImplementation(count: count, sortedBy: areInIncreasingOrder)
|
|
}
|
|
}
|
|
|
|
extension Sequence where Element: Comparable {
|
|
/// Returns the smallest elements of this sequence.
|
|
///
|
|
/// This example partially sorts an array of integers to retrieve its three
|
|
/// smallest values:
|
|
///
|
|
/// let numbers = [7, 1, 6, 2, 8, 3, 9]
|
|
/// let smallestThree = numbers.min(count: 3)
|
|
/// // [1, 2, 3]
|
|
///
|
|
/// If you need to sort a sequence but only need to access its smallest
|
|
/// elements, using this method can give you a performance boost over sorting
|
|
/// the entire sequence. The order of equal elements is guaranteed to be
|
|
/// preserved.
|
|
///
|
|
/// - Parameter count: The number of elements to return. If `count` is greater
|
|
/// than the number of elements in this sequence, all of the sequence's
|
|
/// elements are returned.
|
|
/// - Returns: An array of the smallest `count` elements of this sequence.
|
|
///
|
|
/// - Complexity: O(*k* log *k* + *nk*), where *n* is the length of the
|
|
/// sequence and *k* is `count`.
|
|
@inlinable
|
|
public func min(count: Int) -> [Element] {
|
|
return min(count: count, sortedBy: <)
|
|
}
|
|
|
|
/// Returns the largest elements of this sequence.
|
|
///
|
|
/// This example partially sorts an array of integers to retrieve its three
|
|
/// largest values:
|
|
///
|
|
/// let numbers = [7, 1, 6, 2, 8, 3, 9]
|
|
/// let smallestThree = numbers.max(count: 3)
|
|
/// // [7, 8, 9]
|
|
///
|
|
/// If you need to sort a sequence but only need to access its largest
|
|
/// elements, using this method can give you a performance boost over sorting
|
|
/// the entire sequence. The order of equal elements is guaranteed to be
|
|
/// preserved.
|
|
///
|
|
/// - Parameter count: The number of elements to return. If `count` is greater
|
|
/// than the number of elements in this sequence, all of the sequence's
|
|
/// elements are returned.
|
|
/// - Returns: An array of the largest `count` elements of this sequence.
|
|
///
|
|
/// - Complexity: O(*k* log *k* + *nk*), where *n* is the length of the
|
|
/// sequence and *k* is `count`.
|
|
@inlinable
|
|
public func max(count: Int) -> [Element] {
|
|
return max(count: count, sortedBy: <)
|
|
}
|
|
}
|
|
|
|
extension Collection {
|
|
/// Returns the smallest elements of this collection, as sorted by the given
|
|
/// predicate.
|
|
///
|
|
/// This example partially sorts an array of integers to retrieve its three
|
|
/// smallest values:
|
|
///
|
|
/// let numbers = [7, 1, 6, 2, 8, 3, 9]
|
|
/// let smallestThree = numbers.min(count: 3, sortedBy: <)
|
|
/// // [1, 2, 3]
|
|
///
|
|
/// If you need to sort a collection but only need to access its smallest
|
|
/// elements, using this method can give you a performance boost over sorting
|
|
/// the entire collection. The order of equal elements is guaranteed to be
|
|
/// preserved.
|
|
///
|
|
/// - Parameters:
|
|
/// - count: The number of elements to return. If `count` is greater than
|
|
/// the number of elements in this collection, all of the collection's
|
|
/// elements are returned.
|
|
/// - areInIncreasingOrder: A predicate that returns `true` if its
|
|
/// first argument should be ordered before its second argument;
|
|
/// otherwise, `false`.
|
|
/// - Returns: An array of the smallest `count` elements of this collection,
|
|
/// sorted according to `areInIncreasingOrder`.
|
|
///
|
|
/// - Complexity: O(*k* log *k* + *nk*), where *n* is the length of the
|
|
/// collection and *k* is `count`.
|
|
@inlinable
|
|
public func min(
|
|
count: Int,
|
|
sortedBy areInIncreasingOrder: (Element, Element) throws -> Bool
|
|
) rethrows -> [Element] {
|
|
precondition(
|
|
count >= 0,
|
|
"""
|
|
Cannot find a minimum with a negative count of elements!
|
|
"""
|
|
)
|
|
|
|
// Do nothing if we're prefixing nothing.
|
|
guard count > 0 else {
|
|
return []
|
|
}
|
|
|
|
// Make sure we are within bounds.
|
|
let prefixCount = Swift.min(count, self.count)
|
|
|
|
// If we're attempting to prefix more than 10% of the collection, it's
|
|
// faster to sort everything.
|
|
guard prefixCount < (self.count / 10) else {
|
|
return Array(try sorted(by: areInIncreasingOrder).prefix(prefixCount))
|
|
}
|
|
|
|
return try _minImplementation(count: count, sortedBy: areInIncreasingOrder)
|
|
}
|
|
|
|
/// Returns the largest elements of this collection, as sorted by the given
|
|
/// predicate.
|
|
///
|
|
/// This example partially sorts an array of integers to retrieve its three
|
|
/// largest values:
|
|
///
|
|
/// let numbers = [7, 1, 6, 2, 8, 3, 9]
|
|
/// let smallestThree = numbers.max(count: 3, sortedBy: <)
|
|
/// // [7, 8, 9]
|
|
///
|
|
/// If you need to sort a collection but only need to access its largest
|
|
/// elements, using this method can give you a performance boost over sorting
|
|
/// the entire collection. The order of equal elements is guaranteed to be
|
|
/// preserved.
|
|
///
|
|
/// - Parameters:
|
|
/// - count: The number of elements to return. If `count` is greater than
|
|
/// the number of elements in this collection, all of the collection's
|
|
/// elements are returned.
|
|
/// - areInIncreasingOrder: A predicate that returns `true` if its
|
|
/// first argument should be ordered before its second argument;
|
|
/// otherwise, `false`.
|
|
/// - Returns: An array of the largest `count` elements of this collection,
|
|
/// sorted according to `areInIncreasingOrder`.
|
|
///
|
|
/// - Complexity: O(*k* log *k* + *nk*), where *n* is the length of the
|
|
/// collection and *k* is `count`.
|
|
@inlinable
|
|
public func max(
|
|
count: Int,
|
|
sortedBy areInIncreasingOrder: (Element, Element) throws -> Bool
|
|
) rethrows -> [Element] {
|
|
precondition(
|
|
count >= 0,
|
|
"""
|
|
Cannot find a maximum with a negative count of elements!
|
|
"""
|
|
)
|
|
|
|
// Do nothing if we're suffixing nothing.
|
|
guard count > 0 else {
|
|
return []
|
|
}
|
|
|
|
// Make sure we are within bounds.
|
|
let suffixCount = Swift.min(count, self.count)
|
|
|
|
// If we're attempting to prefix more than 10% of the collection, it's
|
|
// faster to sort everything.
|
|
guard suffixCount < (self.count / 10) else {
|
|
return Array(try sorted(by: areInIncreasingOrder).suffix(suffixCount))
|
|
}
|
|
|
|
return try _maxImplementation(count: count, sortedBy: areInIncreasingOrder)
|
|
}
|
|
}
|
|
|
|
extension Collection where Element: Comparable {
|
|
/// Returns the smallest elements of this collection.
|
|
///
|
|
/// This example partially sorts an array of integers to retrieve its three
|
|
/// smallest values:
|
|
///
|
|
/// let numbers = [7, 1, 6, 2, 8, 3, 9]
|
|
/// let smallestThree = numbers.min(count: 3)
|
|
/// // [1, 2, 3]
|
|
///
|
|
/// If you need to sort a collection but only need to access its smallest
|
|
/// elements, using this method can give you a performance boost over sorting
|
|
/// the entire collection. The order of equal elements is guaranteed to be
|
|
/// preserved.
|
|
///
|
|
/// - Parameter count: The number of elements to return. If `count` is greater
|
|
/// than the number of elements in this collection, all of the collection's
|
|
/// elements are returned.
|
|
/// - Returns: An array of the smallest `count` elements of this collection.
|
|
///
|
|
/// - Complexity: O(*k* log *k* + *nk*), where *n* is the length of the
|
|
/// collection and *k* is `count`.
|
|
@inlinable
|
|
public func min(count: Int) -> [Element] {
|
|
return min(count: count, sortedBy: <)
|
|
}
|
|
|
|
/// Returns the largest elements of this collection.
|
|
///
|
|
/// This example partially sorts an array of integers to retrieve its three
|
|
/// largest values:
|
|
///
|
|
/// let numbers = [7, 1, 6, 2, 8, 3, 9]
|
|
/// let smallestThree = numbers.max(count: 3)
|
|
/// // [7, 8, 9]
|
|
///
|
|
/// If you need to sort a collection but only need to access its largest
|
|
/// elements, using this method can give you a performance boost over sorting
|
|
/// the entire collection. The order of equal elements is guaranteed to be
|
|
/// preserved.
|
|
///
|
|
/// - Parameter count: The number of elements to return. If `count` is greater
|
|
/// than the number of elements in this collection, all of the collection's
|
|
/// elements are returned.
|
|
/// - Returns: An array of the largest `count` elements of this collection.
|
|
///
|
|
/// - Complexity: O(*k* log *k* + *nk*), where *n* is the length of the
|
|
/// collection and *k* is `count`.
|
|
@inlinable
|
|
public func max(count: Int) -> [Element] {
|
|
return max(count: count, sortedBy: <)
|
|
}
|
|
}
|