mirror of
https://github.com/apple/swift.git
synced 2025-12-14 20:36:38 +01:00
500 lines
15 KiB
Swift
500 lines
15 KiB
Swift
//===--- SequenceAlgorithms.swift.gyb -------------------------*- swift -*-===//
|
|
//
|
|
// This source file is part of the Swift.org open source project
|
|
//
|
|
// Copyright (c) 2014 - 2016 Apple Inc. and the Swift project authors
|
|
// Licensed under Apache License v2.0 with Runtime Library Exception
|
|
//
|
|
// See http://swift.org/LICENSE.txt for license information
|
|
// See http://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
%{
|
|
|
|
# We know we will eventually get a Sequence.Element type. Define
|
|
# a shorthand that we can use today.
|
|
GElement = "Iterator.Element"
|
|
|
|
}%
|
|
|
|
//===----------------------------------------------------------------------===//
|
|
// enumerated()
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
extension Sequence {
|
|
/// Returns a lazy `Sequence` containing pairs (*n*, *x*), where
|
|
/// *n*s are consecutive `Int`s starting at zero, and *x*s are
|
|
/// the elements of `self`:
|
|
///
|
|
/// > for (n, c) in "Swift".characters.enumerated() {
|
|
/// print("\(n): '\(c)'")
|
|
/// }
|
|
/// 0: 'S'
|
|
/// 1: 'w'
|
|
/// 2: 'i'
|
|
/// 3: 'f'
|
|
/// 4: 't'
|
|
public func enumerated() -> EnumeratedSequence<Self> {
|
|
return EnumeratedSequence(_base: self)
|
|
}
|
|
}
|
|
|
|
//===----------------------------------------------------------------------===//
|
|
// min(), max()
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
% # Generate two versions: with explicit predicates and with
|
|
% # a Comparable requirement.
|
|
% for preds in [ True, False ]:
|
|
|
|
%{
|
|
if preds:
|
|
orderingRequirement = """
|
|
/// - Precondition: `isOrderedBefore` is a
|
|
/// [strict weak ordering](http://en.wikipedia.org/wiki/Strict_weak_order#Strict_weak_orderings)
|
|
/// over `self`."""
|
|
rethrows_ = "rethrows "
|
|
else:
|
|
orderingRequirement = ""
|
|
rethrows_ = ""
|
|
}%
|
|
|
|
extension Sequence ${"" if preds else "where Iterator.Element : Comparable"} {
|
|
|
|
/// Returns the minimum element in `self` or `nil` if the sequence is empty.
|
|
///
|
|
/// - Complexity: O(`elements.count`).
|
|
///
|
|
/// ${orderingRequirement}
|
|
@warn_unused_result
|
|
public func min(
|
|
% if preds:
|
|
@noescape isOrderedBefore isOrderedBefore:
|
|
(${GElement}, ${GElement}) throws -> Bool
|
|
% end
|
|
) ${rethrows_}-> ${GElement}? {
|
|
var it = makeIterator()
|
|
guard var result = it.next() else { return nil }
|
|
for e in IteratorSequence(it) {
|
|
% if preds:
|
|
if try isOrderedBefore(e, result) { result = e }
|
|
% else:
|
|
if e < result { result = e }
|
|
% end
|
|
}
|
|
return result
|
|
}
|
|
|
|
/// Returns the maximum element in `self` or `nil` if the sequence is empty.
|
|
///
|
|
/// - Complexity: O(`elements.count`).
|
|
/// ${orderingRequirement}
|
|
@warn_unused_result
|
|
public func max(
|
|
% if preds:
|
|
@noescape isOrderedBefore isOrderedBefore:
|
|
(${GElement}, ${GElement}) throws -> Bool
|
|
% end
|
|
) ${rethrows_}-> ${GElement}? {
|
|
var it = makeIterator()
|
|
guard var result = it.next() else { return nil }
|
|
for e in IteratorSequence(it) {
|
|
% if preds:
|
|
if try isOrderedBefore(result, e) { result = e }
|
|
% else:
|
|
if e > result { result = e }
|
|
% end
|
|
}
|
|
return result
|
|
}
|
|
}
|
|
|
|
% end
|
|
|
|
//===----------------------------------------------------------------------===//
|
|
// starts(with:)
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
% # Generate two versions: with explicit predicates and with
|
|
% # an Equatable requirement.
|
|
% for preds in [ True, False ]:
|
|
|
|
extension Sequence ${"" if preds else "where Iterator.Element : Equatable"} {
|
|
|
|
%{
|
|
if preds:
|
|
comment = """
|
|
/// Returns `true` iff `self` begins with elements equivalent to those of
|
|
/// `other`, using `isEquivalent` as the equivalence test. Returns `true` if
|
|
/// `other` is empty.
|
|
///
|
|
/// - Precondition: `isEquivalent` is an
|
|
/// [equivalence relation](http://en.wikipedia.org/wiki/Equivalence_relation)."""
|
|
|
|
rethrows_ = "rethrows "
|
|
else:
|
|
comment = """
|
|
/// Returns `true` iff the initial elements of `self` are equal to `prefix`.
|
|
/// Returns `true` if `other` is empty."""
|
|
rethrows_ = ""
|
|
}%
|
|
${comment}
|
|
@warn_unused_result
|
|
public func starts<
|
|
PossiblePrefix : Sequence where PossiblePrefix.${GElement} == ${GElement}
|
|
>(
|
|
with possiblePrefix: PossiblePrefix${"," if preds else ""}
|
|
% if preds:
|
|
@noescape isEquivalent: (${GElement}, ${GElement}) throws -> Bool
|
|
% end
|
|
) ${rethrows_}-> Bool {
|
|
var possiblePrefixIterator = possiblePrefix.makeIterator()
|
|
for e0 in self {
|
|
if let e1 = possiblePrefixIterator.next() {
|
|
if ${"try !isEquivalent(e0, e1)" if preds else "e0 != e1"} {
|
|
return false
|
|
}
|
|
}
|
|
else {
|
|
return true
|
|
}
|
|
}
|
|
return possiblePrefixIterator.next() == nil
|
|
}
|
|
}
|
|
|
|
% end
|
|
|
|
//===----------------------------------------------------------------------===//
|
|
// elementsEqual()
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
% # Generate two versions: with explicit predicates and with
|
|
% # an Equatable requirement.
|
|
% for preds in [ True, False ]:
|
|
|
|
extension Sequence ${"" if preds else "where Iterator.Element : Equatable"} {
|
|
|
|
%{
|
|
if preds:
|
|
comment = """
|
|
/// Returns `true` iff `self` and `other` contain equivalent elements, using
|
|
/// `isEquivalent` as the equivalence test.
|
|
///
|
|
/// - Precondition: `isEquivalent` is an
|
|
/// [equivalence relation](http://en.wikipedia.org/wiki/Equivalence_relation)."""
|
|
rethrows_ = "rethrows "
|
|
else:
|
|
comment = """
|
|
/// Returns `true` iff `self` and `other` contain the same elements in the
|
|
/// same order."""
|
|
rethrows_ = ""
|
|
}%
|
|
|
|
${comment}
|
|
@warn_unused_result
|
|
public func elementsEqual<
|
|
OtherSequence : Sequence where OtherSequence.${GElement} == ${GElement}
|
|
>(
|
|
other: OtherSequence${"," if preds else ""}
|
|
% if preds:
|
|
@noescape isEquivalent: (${GElement}, ${GElement}) throws -> Bool
|
|
% end
|
|
) ${rethrows_}-> Bool {
|
|
var iter1 = self.makeIterator()
|
|
var iter2 = other.makeIterator()
|
|
while true {
|
|
switch (iter1.next(), iter2.next()) {
|
|
case let (e1?, e2?):
|
|
if ${'try !isEquivalent(e1, e2)' if preds else 'e1 != e2'} {
|
|
return false
|
|
}
|
|
case (_?, nil),
|
|
(nil, _?):
|
|
return false
|
|
case (nil, nil):
|
|
return true
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
% end
|
|
|
|
//===----------------------------------------------------------------------===//
|
|
// lexicographicallyPrecedes()
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
% # Generate two versions: with explicit predicates and with
|
|
% # Comparable requirement.
|
|
% for preds in [ True, False ]:
|
|
|
|
extension Sequence ${"" if preds else "where Iterator.Element : Comparable"} {
|
|
|
|
%{
|
|
if preds:
|
|
comment = """
|
|
/// Returns `true` iff `self` precedes `other` in a lexicographical
|
|
/// ("dictionary") ordering, using `isOrderedBefore` as the comparison
|
|
/// between elements.
|
|
///
|
|
/// - Note: This method implements the mathematical notion of lexicographical
|
|
/// ordering, which has no connection to Unicode. If you are sorting strings
|
|
/// to present to the end-user, you should use `String` APIs that perform
|
|
/// localized comparison.
|
|
///
|
|
/// - Precondition: `isOrderedBefore` is a
|
|
/// [strict weak ordering](http://en.wikipedia.org/wiki/Strict_weak_order#Strict_weak_orderings)
|
|
/// over the elements of `self` and `other`."""
|
|
rethrows_ = "rethrows "
|
|
else:
|
|
comment = """
|
|
/// Returns `true` iff `self` precedes `other` in a lexicographical
|
|
/// ("dictionary") ordering, using "<" as the comparison between elements.
|
|
///
|
|
/// - Note: This method implements the mathematical notion of lexicographical
|
|
/// ordering, which has no connection to Unicode. If you are sorting strings
|
|
/// to present to the end-user, you should use `String` APIs that perform
|
|
/// localized comparison."""
|
|
rethrows_ = ""
|
|
}%
|
|
|
|
${comment}
|
|
@warn_unused_result
|
|
public func lexicographicallyPrecedes<
|
|
OtherSequence : Sequence where OtherSequence.${GElement} == ${GElement}
|
|
>(
|
|
other: OtherSequence${"," if preds else ""}
|
|
% if preds:
|
|
@noescape isOrderedBefore: (${GElement}, ${GElement}) throws -> Bool
|
|
% end
|
|
) ${rethrows_}-> Bool {
|
|
var iter1 = self.makeIterator()
|
|
var iter2 = other.makeIterator()
|
|
while true {
|
|
if let e1 = iter1.next() {
|
|
if let e2 = iter2.next() {
|
|
if ${"try isOrderedBefore(e1, e2)" if preds else "e1 < e2"} {
|
|
return true
|
|
}
|
|
if ${"try isOrderedBefore(e2, e1)" if preds else "e2 < e1"} {
|
|
return false
|
|
}
|
|
continue // Equivalent
|
|
}
|
|
return false
|
|
}
|
|
|
|
return iter2.next() != nil
|
|
}
|
|
}
|
|
}
|
|
|
|
% end
|
|
|
|
//===----------------------------------------------------------------------===//
|
|
// contains()
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
extension Sequence where Iterator.Element : Equatable {
|
|
/// Returns `true` iff `element` is in `self`.
|
|
@warn_unused_result
|
|
public func contains(element: ${GElement}) -> Bool {
|
|
if let result = _customContainsEquatableElement(element) {
|
|
return result
|
|
}
|
|
|
|
for e in self {
|
|
if e == element {
|
|
return true
|
|
}
|
|
}
|
|
return false
|
|
}
|
|
}
|
|
|
|
extension Sequence {
|
|
/// Returns `true` iff an element in `self` satisfies `predicate`.
|
|
@warn_unused_result
|
|
public func contains(
|
|
@noescape predicate: (${GElement}) throws -> Bool
|
|
) rethrows -> Bool {
|
|
for e in self {
|
|
if try predicate(e) {
|
|
return true
|
|
}
|
|
}
|
|
return false
|
|
}
|
|
}
|
|
|
|
//===----------------------------------------------------------------------===//
|
|
// reduce()
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
extension Sequence {
|
|
/// Returns the result of repeatedly calling `combine` with an
|
|
/// accumulated value initialized to `initial` and each element of
|
|
/// `self`, in turn, i.e. return
|
|
/// `combine(combine(...combine(combine(initial, self[0]),
|
|
/// self[1]),...self[count-2]), self[count-1])`.
|
|
@warn_unused_result
|
|
public func reduce<T>(
|
|
initial: T, @noescape combine: (T, ${GElement}) throws -> T
|
|
) rethrows -> T {
|
|
var result = initial
|
|
for element in self {
|
|
result = try combine(result, element)
|
|
}
|
|
return result
|
|
}
|
|
}
|
|
|
|
//===----------------------------------------------------------------------===//
|
|
// reversed()
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
extension Sequence {
|
|
/// Returns an `Array` containing the elements of `self` in reverse
|
|
/// order.
|
|
///
|
|
/// Complexity: O(N), where N is the length of `self`.
|
|
@warn_unused_result
|
|
public func reversed() -> [${GElement}] {
|
|
// FIXME(performance): optimize to 1 pass? But Array(self) can be
|
|
// optimized to a memcpy() sometimes. Those cases are usually collections,
|
|
// though.
|
|
var result = Array(self)
|
|
let count = result.count
|
|
for i in 0..<count/2 {
|
|
swap(&result[i], &result[count - i - 1])
|
|
}
|
|
return result
|
|
}
|
|
}
|
|
|
|
//===----------------------------------------------------------------------===//
|
|
// flatMap()
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
extension Sequence {
|
|
/// Returns an `Array` containing the concatenated results of mapping
|
|
/// `transform` over `self`.
|
|
///
|
|
/// s.flatMap(transform)
|
|
///
|
|
/// is equivalent to
|
|
///
|
|
/// Array(s.map(transform).flatten())
|
|
///
|
|
/// - Complexity: O(*M* + *N*), where *M* is the length of `self`
|
|
/// and *N* is the length of the result.
|
|
@warn_unused_result
|
|
public func flatMap<S : Sequence>(
|
|
@noescape transform: (${GElement}) throws -> S
|
|
) rethrows -> [S.${GElement}] {
|
|
var result: [S.${GElement}] = []
|
|
for element in self {
|
|
result.append(contentsOf: try transform(element))
|
|
}
|
|
return result
|
|
}
|
|
}
|
|
|
|
extension Sequence {
|
|
/// Returns an `Array` containing the non-nil results of mapping
|
|
/// `transform` over `self`.
|
|
///
|
|
/// - Complexity: O(*M* + *N*), where *M* is the length of `self`
|
|
/// and *N* is the length of the result.
|
|
@warn_unused_result
|
|
public func flatMap<T>(
|
|
@noescape transform: (${GElement}) throws -> T?
|
|
) rethrows -> [T] {
|
|
var result: [T] = []
|
|
for element in self {
|
|
if let newElement = try transform(element) {
|
|
result.append(newElement)
|
|
}
|
|
}
|
|
return result
|
|
}
|
|
}
|
|
|
|
extension Sequence {
|
|
@available(*, unavailable, renamed="enumerated")
|
|
public func enumerate() -> EnumeratedSequence<Self> {
|
|
fatalError("unavailable function can't be called")
|
|
}
|
|
|
|
@available(*, unavailable, renamed="min")
|
|
public func minElement(
|
|
@noescape isOrderedBefore: (Iterator.Element, Iterator.Element) throws -> Bool
|
|
) rethrows -> Iterator.Element? {
|
|
fatalError("unavailable function can't be called")
|
|
}
|
|
|
|
@available(*, unavailable, renamed="max")
|
|
public func maxElement(
|
|
@noescape isOrderedBefore: (Iterator.Element, Iterator.Element) throws -> Bool
|
|
) rethrows -> Iterator.Element? {
|
|
fatalError("unavailable function can't be called")
|
|
}
|
|
|
|
@available(*, unavailable, renamed="reversed")
|
|
public func reverse() -> [Iterator.Element] {
|
|
fatalError("unavailable function can't be called")
|
|
}
|
|
|
|
@available(*, unavailable, renamed="starts")
|
|
public func startsWith<
|
|
PossiblePrefix : Sequence where PossiblePrefix.Iterator.Element == Iterator.Element
|
|
>(
|
|
with possiblePrefix: PossiblePrefix,
|
|
@noescape isEquivalent: (Iterator.Element, Iterator.Element) throws -> Bool
|
|
) rethrows-> Bool {
|
|
fatalError("unavailable function can't be called")
|
|
}
|
|
|
|
@available(*, unavailable, renamed="lexicographicallyPrecedes")
|
|
public func lexicographicalCompare<
|
|
OtherSequence : Sequence where OtherSequence.${GElement} == ${GElement}
|
|
>(
|
|
other: OtherSequence,
|
|
@noescape isOrderedBefore: (${GElement}, ${GElement}) throws -> Bool
|
|
) rethrows -> Bool {
|
|
fatalError("unavailable function can't be called")
|
|
}
|
|
}
|
|
|
|
extension Sequence where Iterator.Element : Comparable {
|
|
@available(*, unavailable, renamed="min")
|
|
public func minElement() -> Iterator.Element? {
|
|
fatalError("unavailable function can't be called")
|
|
}
|
|
|
|
@available(*, unavailable, renamed="max")
|
|
public func maxElement() -> Iterator.Element? {
|
|
fatalError("unavailable function can't be called")
|
|
}
|
|
|
|
@available(*, unavailable, renamed="starts")
|
|
public func startsWith<
|
|
PossiblePrefix : Sequence where PossiblePrefix.${GElement} == ${GElement}
|
|
>(
|
|
with possiblePrefix: PossiblePrefix
|
|
) -> Bool {
|
|
fatalError("unavailable function can't be called")
|
|
}
|
|
|
|
@available(*, unavailable, renamed="lexicographicallyPrecedes")
|
|
public func lexicographicalCompare<
|
|
OtherSequence : Sequence where OtherSequence.${GElement} == ${GElement}
|
|
>(
|
|
other: OtherSequence
|
|
) -> Bool {
|
|
fatalError("unavailable function can't be called")
|
|
}
|
|
}
|