A generalized and Swift-y adaptation of NSString.replacingOccurrences(of: with: options: range:). See <https://forums.swift.org/t/additional-string-processing-apis/36255/25?u=ctmacuser> for more.

FirstRange.swift

import Foundation


extension Collection {

    /// Returns the index range for the earliest subsequence of this collection
    /// that is equivalent to the given sequence, using the given predicate to
    /// compare elements.
    ///
    /// The predicate must be an equivalence relation over the elements.
    ///
    /// Comparisons are done element-wise.  If there are runs of different
    /// elements that have the same semantic meaning, like Unicode string
    /// equivalence, both the receiver and the target must be set to the same
    /// normalization before comparing.
    ///
    /// - Parameters:
    ///     - target: A collection to find within this collection.
    ///     - areEquivalent: A predicate that returns `true` if its two
    ///       arguments are equivalent; otherwise, `false`.
    /// - Returns: A range *r* such that
    ///   `self[r].elementsEqual(target, by: areEquivalent)` is `true` and that
    ///   any other matching range must have its `lowerBound` greater than
    ///   `r.lowerBound`.  If there is no such range, `nil` is returned instead.
    ///
    /// - Complexity: O(*n* × *m*), where *n* is the length of this collection
    ///   and *m* is the length of `target`.
    public func firstRange<C: Collection>(
        equaling target: C,
        by areEquivalent: (Element, C.Element) throws -> Bool
    ) rethrows -> Range<Index>? {
        var start = startIndex
        guard let firstTarget = target.first else { return start..<start }

        let end = target.endIndex
        while let nextStart = try self[start...].firstIndex(where: {
            try areEquivalent($0, firstTarget)
        }) {
            start = index(after: nextStart)
            let (nextEnd, targetEnd) = try self[nextStart...].diverges(from: target, by: areEquivalent)
            if targetEnd == end {
                return nextStart..<nextEnd
            }
        }
        return nil
    }

}

extension Collection where Element: Equatable {

    /// Returns the index range for the earliest subsequence of this collection
    /// that equals the given sequence.
    ///
    /// Comparisons are done element-wise.  If there are runs of different
    /// elements that have the same semantic meaning, like Unicode string
    /// equivalence, both the receiver and the target must be set to the same
    /// normalization before comparing.
    ///
    /// - Parameters:
    ///     - target: A collection to find within this collection.
    /// - Returns: A range *r* such that `self[r].elementsEqual(target)` is
    ///   `true` and that any other matching range must have its `lowerBound`
    ///   greater than `r.lowerBound`.  If there is no such range, `nil` is
    ///   returned instead.
    ///
    /// - Complexity: O(*n* × *m*), where *n* is the length of this collection
    ///   and *m* is the length of `target`.
    @inlinable
    public func firstRange<C: Collection>(equaling target: C) -> Range<Index>?
        where C.Element == Element {
        return firstRange(equaling: target, by: ==)
    }

}

extension BidirectionalCollection {

    /// Returns the index range for the last subsequence of this collection that
    /// is equivalent to the given sequence, using the given predicate to
    /// compare elements.
    ///
    /// The predicate must be an equivalence relation over the elements.
    ///
    /// Comparisons are done element-wise.  If there are runs of different
    /// elements that have the same semantic meaning, like Unicode string
    /// equivalence, both the receiver and the target must be set to the same
    /// normalization before comparing.
    ///
    /// - Parameters:
    ///     - target: A collection to find within this collection.
    ///     - areEquivalent: A predicate that returns `true` if its two
    ///       arguments are equivalent; otherwise, `false`.
    /// - Returns: A range *r* such that
    ///   `self[r].elementsEqual(target, by: areEquivalent)` is `true` and that
    ///   any other matching range must have its `lowerBound` less than
    ///   `r.lowerBound`.  If there is no such range, `nil` is returned instead.
    ///
    /// - Complexity: O(*n* × *m*), where *n* is the length of this collection
    ///   and *m* is the length of `target`.
    @inlinable
    public func lastRange<C: BidirectionalCollection>(
        equaling target: C,
        by areEquivalent: (Element, C.Element) throws -> Bool
    ) rethrows -> Range<Index>? {
        let result = try reversed().firstRange(equaling: target.reversed(), by: areEquivalent)
        return result.map { $0.upperBound.base ..< $0.lowerBound.base }
    }

}

extension BidirectionalCollection where Element: Equatable {

    /// Returns the index range for the last subsequence of this collection that
    /// equals the given sequence.
    ///
    /// Comparisons are done element-wise.  If there are runs of different
    /// elements that have the same semantic meaning, like Unicode string
    /// equivalence, both the receiver and the target must be set to the same
    /// normalization before comparing.
    ///
    /// - Parameters:
    ///     - target: A collection to find within this collection.
    /// - Returns: A range *r* such that `self[r].elementsEqual(target)` is
    ///   `true` and that any other matching range must have its `lowerBound`
    ///   less than `r.lowerBound`.  If there is no such range, `nil` is
    ///   returned instead.
    ///
    /// - Complexity: O(*n* × *m*), where *n* is the length of this collection
    ///   and *m* is the length of `target`.
    @inlinable
    public func lastRange<C: BidirectionalCollection>(equaling target: C)
        -> Range<Index>? where C.Element == Element {
        return lastRange(equaling: target, by: ==)
    }

}

MatchingRanges.swift

import Foundation


/// A sequence of the locations of all the occurrances a substring appears in
/// some collection according to an element-equivalence function.
///
/// - Warning: `startIndex` is computed on the fly, making it O(*n*) instead of
///   O(1), where *n* is the length of the base collection.  Since collection
///   iteration repeatedly tests the last-reachable end-point, prefer forward
///   iteration when possible, since `endIndex` is a lot quicker to compute.
public struct MatchingRangesCollection<Base: Collection, TargetElement> {

    /// The collection to be searched.
    let base: Base
    /// The sequence to be searched for.
    let target: [TargetElement]
    /// The closure to compare elements for equivalence.
    let areEquivalent: (Base.Element, TargetElement) -> Bool

    /// Creates a searcher for the given sequence within the given collection,
    /// using the given predicate for element-level equivalence tests.
    init<S: Sequence>(
        _ base: Base,
        target: S,
        areEquivalent: @escaping (Base.Element, TargetElement) -> Bool
    ) where S.Element == TargetElement {
        self.base = base
        self.target = Array(target)
        self.areEquivalent = areEquivalent
    }

}

extension MatchingRangesCollection: LazyCollectionProtocol {

    public struct Index: Comparable {
        /// The location of the matching subsequence, or `nil` for past-the-end.
        let indices: Range<Base.Index>?

        public static func < (lhs: Self, rhs: Self) -> Bool {
            switch (lhs.indices, rhs.indices) {
            case (nil, _):
                return false
            case (_?, nil):
                return true
            case let (li?, ri?):
                // Assumes the "upperBound" properties are in the same relative
                // order.
                return li.lowerBound < ri.upperBound
            }
        }
    }

    public var startIndex: Index {
        Index(indices: base.firstRange(equaling: target, by: areEquivalent))
    }
    public var endIndex: Index { Index(indices: nil) }

    public subscript(position: Index) -> Range<Base.Index> {
        return position.indices!
    }

    public func index(after i: Index) -> Index {
        return Index(indices: base[base.index(after: i.indices!.lowerBound)...].firstRange(equaling: target, by: areEquivalent))
    }

}

extension MatchingRangesCollection.Index: Hashable where Base.Index: Hashable {}

extension MatchingRangesCollection: BidirectionalCollection
where Base: BidirectionalCollection {

    public func index(before i: Index) -> Index {
        if let currentIndices = i.indices {
            return Index(indices: base[..<base.index(before: currentIndices.upperBound)].lastRange(equaling: target, by: areEquivalent))
        } else {
            return Index(indices: base.lastRange(equaling: target, by: areEquivalent))
        }
    }

}

extension Collection {

    /// Returns the index ranges for each subsequence of this collection that is
    /// equivalent to the given sequence, using the given predicate to compare
    /// elements.
    ///
    /// The predicate must be an equivalence relation over the elements.
    ///
    /// Matches are listed from the earliest to the latest.  Overlap is allowed.
    ///
    /// Comparisons are done element-wise.  If there are runs of different
    /// elements that have the same semantic meaning, like Unicode string
    /// equivalence, both the receiver and the target must be set to the same
    /// normalization before comparing.
    ///
    /// - Precondition: `target` must be finite.
    ///
    /// - Parameters:
    ///     - target: A sequence to find within this collection.
    ///     - areEquivalent: A predicate that returns `true` if its two
    ///       arguments are equivalent; otherwise, `false`.
    /// - Returns: A lazily-generated collection of the index ranges for each
    ///   matching subsequence.  In other words, every range *r* where
    ///   `self[r].elementsEqual(target, by: areEquivalent)` is `true`.
    public func matchingRanges<S: Sequence>(
        for target: S,
        by areEquivalent: @escaping (Element, S.Element) -> Bool
    ) -> MatchingRangesCollection<Self, S.Element> {
        return MatchingRangesCollection(self, target: target, areEquivalent: areEquivalent)
    }

}

extension Collection where Element: Equatable {

    /// Returns the index ranges for each subsequence of this collection that is
    /// equal to the given sequence.
    ///
    /// Matches are listed from the earliest to the latest.  Overlap is allowed.
    ///
    /// Comparisons are done element-wise.  If there are runs of different
    /// elements that have the same semantic meaning, like Unicode string
    /// equivalence, both the receiver and the target must be set to the same
    /// normalization before comparing.
    ///
    /// - Precondition: `target` must be finite.
    ///
    /// - Parameters:
    ///     - target: A sequence to find within this collection.
    /// - Returns: A lazily-generated collection of the index ranges for each
    ///   matching subsequence.  In other words, every range *r* where
    ///   `self[r].elementsEqual(target)` is `true`.
    @inlinable
    public func matchingRanges<S: Sequence>(
        for target: S
    ) -> MatchingRangesCollection<Self, Element> where S.Element == Element {
        return matchingRanges(for: target, by: ==)
    }

}

ReplaceSubranges.swift

extension Collection {

    /// Returns a copy of this collection into a collection of the given type,
    /// but where the subsequences of this collection indicated by the given
    /// list of index ranges are replaced by mapped versions of themselves, in
    /// the given direction, using the given mapping function.
    ///
    /// - Precondition:
    ///     - `list` is finite.
    ///     - The returned sequences from `transform` are finite.
    ///
    /// - Parameters:
    ///    - list: A sequence of ranges representing the subsequences to be read
    ///      and replaced.
    ///    - backwards: Whether checking for overlapping ranges in `list` goes
    ///      from the first-most subsequence to the last-most (`false`), or the
    ///      other way (`true`).  When two ranges overlap, the subsequence for
    ///      the range checked first is kept and the second one is ignored.
    ///      Subsequent ranges are compared to the last kept one.
    ///    - type: The type of the collection to be returned.
    ///    - transform: A function that reads a target subsequence and returns
    ///      its replacement.
    /// - Returns: A copy of this collection, but with the targeted subsequences
    ///   replaced by their transformations.
    ///
    /// - Complexity: O(*kn*), where *n* is the length of this collection and
    ///   *k* is the ratio that `transform` typically expands its input by.
    public func replaceSubranges<S, T, U>(
        listedBy list: S,
        backwards: Bool,
        into type: T.Type,
        withResultsOf transform: (SubSequence) throws -> U
    ) rethrows -> T
        where S: Sequence, S.Element: RangeExpression, S.Element.Bound == Index,
              T: RangeReplaceableCollection, T.Element == Element,
              U: Sequence, U.Element == Element
    {
        // Convert the targeted ranges to a sorted list.
        var listRanges = list.map { $0.relative(to: self) }
        if backwards {
            let anchor = endIndex
            listRanges.sort(by: { $0.upperBound > $1.upperBound })
            precondition(listRanges.first.map { $0.upperBound <= anchor } ?? true)
        } else {
            let anchor = startIndex
            listRanges.sort(by: { $0.lowerBound < $1.lowerBound })
            precondition(listRanges.first.map { $0.lowerBound >= anchor } ?? true)
        }

        // Purge overlaps.
        var targetRanges = Array<Range<Index>>()
        targetRanges.reserveCapacity(listRanges.count)
        if let firstRange = listRanges.first {
            targetRanges.append(firstRange)
            for range in listRanges.dropFirst() {
                if !targetRanges.last!.overlaps(range) {
                    targetRanges.append(range)
                }
            }
        } else {
            return T(self)
        }
        targetRanges.sort(by: { $0.lowerBound < $1.lowerBound })
        assert(zip(targetRanges.dropLast(), targetRanges.dropFirst()).allSatisfy { $0.0.upperBound <= $0.1.lowerBound })

        // Copy each segment, transforming the targeted ones.
        var result = T(), lastEnd = startIndex
        for range in targetRanges {
            result.append(contentsOf: self[lastEnd..<range.lowerBound])
            result.append(contentsOf: try transform(self[range]))
            lastEnd = range.upperBound
        }
        result.append(contentsOf: self[lastEnd...])
        return result
    }

    /// Copies this collection into an array, except that subsequences of this
    /// collection indicated by the given list of index ranges are replaced in
    /// the given direction by mapped versions of themselves, using the given
    /// mapping function.
    ///
    /// - Precondition:
    ///     - `list` is finite.
    ///     - The returned sequences from `transform` are finite.
    ///
    /// - Parameters:
    ///    - list: A sequence of ranges representing the subsequences to be read
    ///      and replaced.
    ///    - backwards: Whether checking for overlapping ranges in `list` goes
    ///      from the first-most subsequence to the last-most (`false`), or the
    ///      other way (`true`).  When two ranges overlap, the subsequence for
    ///      the range checked first is kept and the second one is ignored.
    ///      Subsequent ranges are compared to the last kept one.
    ///    - transform: A function that reads a target subsequence and returns
    ///      its replacement.
    /// - Returns: A copy of this collection, but with the targeted subsequences
    ///   replaced by their transformations.
    ///
    /// - Complexity: O(*kn*), where *n* is the length of this collection and
    ///   *k* is the ratio that `transform` typically expands its input by.
    @inlinable
    public func replaceSubranges<S: Sequence, U: Sequence>(
        listedBy list: S,
        backwards: Bool,
        withResultsOf transform: (SubSequence) throws -> U
    ) rethrows -> [Element]
        where S.Element: RangeExpression, S.Element.Bound == Index,
              U.Element == Element
    {
        return try replaceSubranges(listedBy: list, backwards: backwards, into: Array.self, withResultsOf: transform)
    }

}

ReplacingOccurrences.swift

import Foundation


extension Collection {

    /// Returns a copy of this collection into a collection of the given type,
    /// except subsequences that match the given collection according to the
    /// given predicate are replaced with copies of another given collection.
    ///
    /// The predicate must be an equivalence relation over the elements.
    ///
    /// Comparisons are done element-wise.  If there are runs of different
    /// elements that have the same semantic meaning, like Unicode string
    /// equivalence, both the receiver and the target must be set to the same
    /// normalization before comparing.
    ///
    /// - Parameters:
    ///    - target: A sequence to find within this collection.
    ///    - replacement: A collection whose copies will replace each
    ///      non-overlapping occurrance of `target`.
    ///    - onlyAsPrefix: When `true`, only the prefix of this collection is
    ///      checked for matching `target` and possibly replaced by
    ///      `replacement`.  All other occurrances are ignored, even when the
    ///      prefix doesn't actually match `target` (therefore not replaced).
    ///      Otherwise, all non-overlapping matches to `target` are replaced.
    ///    - type: The type of the collection to be returned.
    ///    - areEquivalent: A predicate that returns `true` if its two arguments
    ///      are equivalent; otherwise, `false`.
    /// - Returns: A copy of this collection, but with the subsequences that
    ///   both match the target and don't overlap with an earlier replacement
    ///   replaced by the given new value.
    ///
    /// - Complexity: O(*k* × *n²* × *m*), where *n* is the length of this
    ///   collection, *m* is the length of `target`, and *k* is the ratio
    ///   between `target` and `replacement`.
    public func replacingOccurrences<T, R, RR>(
        of target: T,
        with replacement: R,
        onlyAsPrefix: Bool,
        into type: RR.Type,
        by areEquivalent: (Element, T.Element) throws -> Bool
    ) rethrows -> RR
        where T: Collection,
        R: Collection, R.Element == Element,
        RR: RangeReplaceableCollection, RR.Element == Element
    {
        guard !onlyAsPrefix else {
            // Only check the start for a match.
            let (suffixStart, targetEnd) = try diverges(from: target, by: areEquivalent)
            if targetEnd == target.endIndex {
                var result = RR(replacement)
                result.append(contentsOf: self[suffixStart...])
                return result
            } else {
                return RR(self)
            }

        }

        // Find each match, then copy all the elements before that match
        // followed by a copy of the replacement sequence.
        var result = RR(), lastEnd = startIndex
        while let matchingRange = try self[lastEnd...].firstRange(equaling: target, by: areEquivalent) {
            result.append(contentsOf: self[lastEnd..<matchingRange.lowerBound])
            result.append(contentsOf: replacement)
            lastEnd = matchingRange.upperBound
        }
        result.append(contentsOf: self[lastEnd...])
        return result
    }

    /// Copies this collection into an array, except subsequences that match the
    /// given collection according to the given predicate are replaced with
    /// copies of another given collection.
    ///
    /// The predicate must be an equivalence relation over the elements.
    ///
    /// Comparisons are done element-wise.  If there are runs of different
    /// elements that have the same semantic meaning, like Unicode string
    /// equivalence, both the receiver and the target must be set to the same
    /// normalization before comparing.
    ///
    /// - Parameters:
    ///    - target: A sequence to find within this collection.
    ///    - replacement: A collection whose copies will replace each
    ///      non-overlapping occurrance of `target`.
    ///    - onlyAsPrefix: When `true`, only the prefix of this collection is
    ///      checked for matching `target` and possibly replaced by
    ///      `replacement`.  All other occurrances are ignored, even when the
    ///      prefix doesn't actually match `target` (therefore not replaced).
    ///      Otherwise, all non-overlapping matches to `target` are replaced.
    ///    - areEquivalent: A predicate that returns `true` if its two arguments
    ///      are equivalent; otherwise, `false`.
    /// - Returns: An array copy of this collection, but with the subsequences
    ///   that both match the target and don't overlap with an earlier
    ///   replacement getting replaced by the given new value.
    ///
    /// - Complexity: O(*k* × *n²* × *m*), where *n* is the length of this
    ///   collection, *m* is the length of `target`, and *k* is the ratio
    ///   between `target` and `replacement`.
    @inlinable
    public func replacingOccurrences<T: Collection, R: Collection>(
        of target: T,
        with replacement: R,
        onlyAsPrefix: Bool,
        by areEquivalent: (Element, T.Element) throws -> Bool
    ) rethrows -> [Element] where R.Element == Element
    {
        return try replacingOccurrences(of: target, with: replacement, onlyAsPrefix: onlyAsPrefix, into: Array.self, by: areEquivalent)
    }

}

extension BidirectionalCollection {

    /// Returns a copy of this collection into a collection of the given type,
    /// except subsequences that match the given collection according to the
    /// given predicate are replaced in a given order with copies of another
    /// given collection.
    ///
    /// The predicate must be an equivalence relation over the elements.
    ///
    /// Comparisons are done element-wise.  If there are runs of different
    /// elements that have the same semantic meaning, like Unicode string
    /// equivalence, both the receiver and the target must be set to the same
    /// normalization before comparing.
    ///
    /// - Parameters:
    ///    - target: A sequence to find within this collection.
    ///    - replacement: A collection whose copies will replace each
    ///      non-overlapping occurrance of `target`.
    ///    - backwards: When `false`, the first occurrance of `target` will be
    ///      replaced, followed by occurrances that don't overlap with the first
    ///      or any later accepted occurrance.  Otherwise, the last occurrance
    ///      will be replaced, then any occurrances that don't overlap with the
    ///      last or any earlier accepted occurrance.
    ///    - onlyAtLeadingAdfix: When `true`, only the matching occurrance at
    ///      the leading end of this collection will be replaced, leaving all
    ///      other occurrances unchanged.  The leading end is the prefix when
    ///      `backwards` is `false`, and the suffix otherwise.  If the leading
    ///      end does not match `target`, then no replacements are done.
    ///    - type: The type of the collection to be returned.
    ///    - areEquivalent: A predicate that returns `true` if its two arguments
    ///      are equivalent; otherwise, `false`.
    /// - Returns: A copy of this collection, but with the subsequences that
    ///   both match the target and don't overlap in the given direction
    ///   replaced by the given new value.
    ///
    /// - Complexity: O(*k* × *n²* × *m*), where *n* is the length of this
    ///   collection, *m* is the length of `target`, and *k* is the ratio
    ///   between `target` and `replacement`.
    @inlinable
    public func replacingOccurrences<T, R, RR>(
        of target: T,
        with replacement: R,
        backwards: Bool,
        onlyAtLeadingAdfix: Bool,
        into type: RR.Type,
        by areEquivalent: (Element, T.Element) throws -> Bool
    ) rethrows -> RR
        where T: BidirectionalCollection,
        R: BidirectionalCollection, R.Element == Element,
        RR: RangeReplaceableCollection, RR.Element == Element
    {
        guard backwards else {
            return try replacingOccurrences(of: target, with: replacement, onlyAsPrefix: onlyAtLeadingAdfix, into: RR.self, by: areEquivalent)
        }

        let backwardsResult = try reversed().replacingOccurrences(of: target.reversed(), with: replacement.reversed(), onlyAsPrefix: onlyAtLeadingAdfix, by: areEquivalent)
        return RR(backwardsResult.reversed())
    }

    /// Copies this collection into an array, except subsequences that match the
    /// given collection according to the given predicate are replaced in a
    /// given order with copies of another given collection.
    ///
    /// The predicate must be an equivalence relation over the elements.
    ///
    /// Comparisons are done element-wise.  If there are runs of different
    /// elements that have the same semantic meaning, like Unicode string
    /// equivalence, both the receiver and the target must be set to the same
    /// normalization before comparing.
    ///
    /// - Parameters:
    ///    - target: A sequence to find within this collection.
    ///    - replacement: A collection whose copies will replace each
    ///      non-overlapping occurrance of `target`.
    ///    - backwards: When `false`, the first occurrance of `target` will be
    ///      replaced, followed by occurrances that don't overlap with the first
    ///      or any later accepted occurrance.  Otherwise, the last occurrance
    ///      will be replaced, then any occurrances that don't overlap with the
    ///      last or any earlier accepted occurrance.
    ///    - onlyAtLeadingAdfix: When `true`, only the matching occurrance at
    ///      the leading end of this collection will be replaced, leaving all
    ///      other occurrances unchanged.  The leading end is the prefix when
    ///      `backwards` is `false`, and the suffix otherwise.  If the leading
    ///      end does not match `target`, then no replacements are done.
    ///    - areEquivalent: A predicate that returns `true` if its two arguments
    ///      are equivalent; otherwise, `false`.
    /// - Returns: An array copy of this collection, but with the subsequences
    ///   that both match the target and don't overlap in the given direction
    ///   getting replaced by the given new value.
    ///
    /// - Complexity: O(*k* × *n²* × *m*), where *n* is the length of this
    ///   collection, *m* is the length of `target`, and *k* is the ratio
    ///   between `target` and `replacement`.
    @inlinable
    public func replacingOccurrences<T, R>(
        of target: T,
        with replacement: R,
        backwards: Bool,
        onlyAtLeadingAdfix: Bool,
        by areEquivalent: (Element, T.Element) throws -> Bool
    ) rethrows -> [Element]
        where T: BidirectionalCollection,
        R: BidirectionalCollection, R.Element == Element
    {
        return try replacingOccurrences(of: target, with: replacement, backwards: backwards, onlyAtLeadingAdfix: onlyAtLeadingAdfix, into: Array.self, by: areEquivalent)
    }

}

extension Collection where Element: Equatable {

    /// Copies this collection into an array, except subsequences that equal the
    /// given collection are replaced with copies of another given collection.
    ///
    /// Comparisons are done element-wise.  If there are runs of different
    /// elements that have the same semantic meaning, like Unicode string
    /// equivalence, both the receiver and the target must be set to the same
    /// normalization before comparing.
    ///
    /// - Parameters:
    ///    - target: A sequence to find within this collection.
    ///    - replacement: A collection whose copies will replace each
    ///      non-overlapping occurrance of `target`.
    ///    - onlyAsPrefix: When `true`, only the prefix of this collection is
    ///      checked for matching `target` and possibly replaced by
    ///      `replacement`.  All other occurrances are ignored, even when the
    ///      prefix doesn't actually match `target` (therefore not replaced).
    ///      Otherwise, all non-overlapping matches to `target` are replaced.
    /// - Returns: An array copy of this collection, but with the subsequences
    ///   that both match the target and don't overlap with an earlier
    ///   replacement getting replaced by the given new value.
    ///
    /// - Complexity: O(*k* × *n²* × *m*), where *n* is the length of this
    ///   collection, *m* is the length of `target`, and *k* is the ratio
    ///   between `target` and `replacement`.
    @inlinable
    public func replacingOccurrences<T: Collection, R: Collection>(
        of target: T,
        with replacement: R,
        onlyAsPrefix: Bool
    ) -> [Element] where T.Element == Element, R.Element == Element
    {
        return replacingOccurrences(of: target, with: replacement, onlyAsPrefix: onlyAsPrefix, by: ==)
    }

}

extension BidirectionalCollection where Element: Equatable {

    /// Copies this collection into an array, except subsequences that equal the
    /// given collection are replaced in a given order with copies of another
    /// given collection.
    ///
    /// Comparisons are done element-wise.  If there are runs of different
    /// elements that have the same semantic meaning, like Unicode string
    /// equivalence, both the receiver and the target must be set to the same
    /// normalization before comparing.
    ///
    /// - Parameters:
    ///    - target: A sequence to find within this collection.
    ///    - replacement: A collection whose copies will replace each
    ///      non-overlapping occurrance of `target`.
    ///    - backwards: When `false`, the first occurrance of `target` will be
    ///      replaced, followed by occurrances that don't overlap with the first
    ///      or any later accepted occurrance.  Otherwise, the last occurrance
    ///      will be replaced, then any occurrances that don't overlap with the
    ///      last or any earlier accepted occurrance.
    ///    - onlyAtLeadingAdfix: When `true`, only the matching occurrance at
    ///      the leading end of this collection will be replaced, leaving all
    ///      other occurrances unchanged.  The leading end is the prefix when
    ///      `backwards` is `false`, and the suffix otherwise.  If the leading
    ///      end does not match `target`, then no replacements are done.
    /// - Returns: An array copy of this collection, but with the subsequences
    ///   that both match the target and don't overlap in the given direction
    ///   getting replaced by the given new value.
    ///
    /// - Complexity: O(*k* × *n²* × *m*), where *n* is the length of this
    ///   collection, *m* is the length of `target`, and *k* is the ratio
    ///   between `target` and `replacement`.
    @inlinable
    public func replacingOccurrences<T, R>(
        of target: T,
        with replacement: R,
        backwards: Bool,
        onlyAtLeadingAdfix: Bool
    ) -> [Element]
        where T: BidirectionalCollection, T.Element == Element,
        R: BidirectionalCollection, R.Element == Element
    {
        return replacingOccurrences(of: target, with: replacement, backwards: backwards, onlyAtLeadingAdfix: onlyAtLeadingAdfix, by: ==)
    }

}

extension RangeReplaceableCollection {

    /// Copies this collection, except subsequences that match the given
    /// collection according to the given predicate are replaced with copies of
    /// another given collection.
    ///
    /// The predicate must be an equivalence relation over the elements.
    ///
    /// Comparisons are done element-wise.  If there are runs of different
    /// elements that have the same semantic meaning, like Unicode string
    /// equivalence, both the receiver and the target must be set to the same
    /// normalization before comparing.
    ///
    /// - Parameters:
    ///    - target: A sequence to find within this collection.
    ///    - replacement: A collection whose copies will replace each
    ///      non-overlapping occurrance of `target`.
    ///    - onlyAsPrefix: When `true`, only the prefix of this collection is
    ///      checked for matching `target` and possibly replaced by
    ///      `replacement`.  All other occurrances are ignored, even when the
    ///      prefix doesn't actually match `target` (therefore not replaced).
    ///      Otherwise, all non-overlapping matches to `target` are replaced.
    ///    - areEquivalent: A predicate that returns `true` if its two arguments
    ///      are equivalent; otherwise, `false`.
    /// - Returns: A copy of this collection, but with the subsequences that
    ///   both match the target and don't overlap with an earlier replacement
    ///   getting replaced by the given new value.
    ///
    /// - Complexity: O(*k* × *n²* × *m*), where *n* is the length of this
    ///   collection, *m* is the length of `target`, and *k* is the ratio
    ///   between `target` and `replacement`.
    @inlinable
    public func replacingOccurrences<T: Collection, R: Collection>(
        of target: T,
        with replacement: R,
        onlyAsPrefix: Bool,
        by areEquivalent: (Element, T.Element) throws -> Bool
    ) rethrows -> Self where R.Element == Element
    {
        return try replacingOccurrences(of: target, with: replacement, onlyAsPrefix: onlyAsPrefix, into: Self.self, by: areEquivalent)
    }

    /// Replaces subsequences of this collection that match the given collection
    /// according to the given predicate with copies of another given
    /// collection.
    ///
    /// The predicate must be an equivalence relation over the elements.
    ///
    /// Comparisons are done element-wise.  If there are runs of different
    /// elements that have the same semantic meaning, like Unicode string
    /// equivalence, both the receiver and the target must be set to the same
    /// normalization before comparing.
    ///
    /// - Parameters:
    ///    - target: A sequence to find within this collection.
    ///    - replacement: A collection whose copies will replace each
    ///      non-overlapping occurrance of `target`.
    ///    - onlyAsPrefix: When `true`, only the prefix of this collection is
    ///      checked for matching `target` and possibly replaced by
    ///      `replacement`.  All other occurrances are ignored, even when the
    ///      prefix doesn't actually match `target` (therefore not replaced).
    ///      Otherwise, all non-overlapping matches to `target` are replaced.
    ///    - areEquivalent: A predicate that returns `true` if its two arguments
    ///      are equivalent; otherwise, `false`.
    /// - Postcondition: The elements of this collection are replaced with a
    ///   copy, except subsequences that both match the target and don't overlap
    ///   with an earlier replacement get replaced by the given new value.
    ///
    /// - Complexity: O(*k* × *n²* × *m*), where *n* is the length of this
    ///   collection, *m* is the length of `target`, and *k* is the ratio
    ///   between `target` and `replacement`.
    @inlinable
    public mutating func replaceOccurrences<T: Collection, R: Collection>(
        of target: T,
        with replacement: R,
        onlyAsPrefix: Bool,
        by areEquivalent: (Element, T.Element) throws -> Bool
    ) rethrows where R.Element == Element {
        let result = try replacingOccurrences(of: target, with: replacement, onlyAsPrefix: onlyAsPrefix, by: areEquivalent)
        replaceSubrange(startIndex..<endIndex, with: result)
    }

}

extension RangeReplaceableCollection where Self: BidirectionalCollection {

    /// Copies this collection, except subsequences that match the given
    /// collection according to the given predicate are replaced in a given
    /// order with copies of another given collection.
    ///
    /// The predicate must be an equivalence relation over the elements.
    ///
    /// Comparisons are done element-wise.  If there are runs of different
    /// elements that have the same semantic meaning, like Unicode string
    /// equivalence, both the receiver and the target must be set to the same
    /// normalization before comparing.
    ///
    /// - Parameters:
    ///    - target: A sequence to find within this collection.
    ///    - replacement: A collection whose copies will replace each
    ///      non-overlapping occurrance of `target`.
    ///    - backwards: When `false`, the first occurrance of `target` will be
    ///      replaced, followed by occurrances that don't overlap with the first
    ///      or any later accepted occurrance.  Otherwise, the last occurrance
    ///      will be replaced, then any occurrances that don't overlap with the
    ///      last or any earlier accepted occurrance.
    ///    - onlyAtLeadingAdfix: When `true`, only the matching occurrance at
    ///      the leading end of this collection will be replaced, leaving all
    ///      other occurrances unchanged.  The leading end is the prefix when
    ///      `backwards` is `false`, and the suffix otherwise.  If the leading
    ///      end does not match `target`, then no replacements are done.
    ///    - areEquivalent: A predicate that returns `true` if its two arguments
    ///      are equivalent; otherwise, `false`.
    /// - Returns: A copy of this collection, but with the subsequences that
    ///   both match the target and don't overlap in the given direction getting
    ///   replaced by the given new value.
    ///
    /// - Complexity: O(*k* × *n²* × *m*), where *n* is the length of this
    ///   collection, *m* is the length of `target`, and *k* is the ratio
    ///   between `target` and `replacement`.
    @inlinable
    public func replacingOccurrences<T, R>(
        of target: T,
        with replacement: R,
        backwards: Bool,
        onlyAtLeadingAdfix: Bool,
        by areEquivalent: (Element, T.Element) throws -> Bool
    ) rethrows -> Self
        where T: BidirectionalCollection,
        R: BidirectionalCollection, R.Element == Element
    {
        return try replacingOccurrences(of: target, with: replacement, backwards: backwards, onlyAtLeadingAdfix: onlyAtLeadingAdfix, into: Self.self, by: areEquivalent)
    }

    /// Replaces in a given order subsequences of this collection that match the
    /// given collection according to the given predicate with copies of another
    /// given collection.
    ///
    /// The predicate must be an equivalence relation over the elements.
    ///
    /// Comparisons are done element-wise.  If there are runs of different
    /// elements that have the same semantic meaning, like Unicode string
    /// equivalence, both the receiver and the target must be set to the same
    /// normalization before comparing.
    ///
    /// - Parameters:
    ///    - target: A sequence to find within this collection.
    ///    - replacement: A collection whose copies will replace each
    ///      non-overlapping occurrance of `target`.
    ///    - backwards: When `false`, the first occurrance of `target` will be
    ///      replaced, followed by occurrances that don't overlap with the first
    ///      or any later accepted occurrance.  Otherwise, the last occurrance
    ///      will be replaced, then any occurrances that don't overlap with the
    ///      last or any earlier accepted occurrance.
    ///    - onlyAtLeadingAdfix: When `true`, only the matching occurrance at
    ///      the leading end of this collection will be replaced, leaving all
    ///      other occurrances unchanged.  The leading end is the prefix when
    ///      `backwards` is `false`, and the suffix otherwise.  If the leading
    ///      end does not match `target`, then no replacements are done.
    ///    - areEquivalent: A predicate that returns `true` if its two arguments
    ///      are equivalent; otherwise, `false`.
    /// - Postcondition: The elements of this collection are replaced with a
    ///   copy, except subsequences that both match the target and don't overlap
    ///   in the given direction get replaced by the given new value.
    ///
    /// - Complexity: O(*k* × *n²* × *m*), where *n* is the length of this
    ///   collection, *m* is the length of `target`, and *k* is the ratio
    ///   between `target` and `replacement`.
    @inlinable
    public mutating func replaceOccurrences<T, R>(
        of target: T,
        with replacement: R,
        backwards: Bool,
        onlyAtLeadingAdfix: Bool,
        by areEquivalent: (Element, T.Element) throws -> Bool
    ) rethrows
        where T: BidirectionalCollection,
        R: BidirectionalCollection, R.Element == Element
    {
        let result = try replacingOccurrences(of: target, with: replacement, backwards: backwards, onlyAtLeadingAdfix: onlyAtLeadingAdfix, by: areEquivalent)
        replaceSubrange(startIndex..<endIndex, with: result)
    }

}

extension RangeReplaceableCollection where Element: Equatable {

    /// Copies this collection, except subsequences that equal the given
    /// collection are replaced with copies of another given collection.
    ///
    /// Comparisons are done element-wise.  If there are runs of different
    /// elements that have the same semantic meaning, like Unicode string
    /// equivalence, both the receiver and the target must be set to the same
    /// normalization before comparing.
    ///
    /// - Parameters:
    ///    - target: A sequence to find within this collection.
    ///    - replacement: A collection whose copies will replace each
    ///      non-overlapping occurrance of `target`.
    ///    - onlyAsPrefix: When `true`, only the prefix of this collection is
    ///      checked for matching `target` and possibly replaced by
    ///      `replacement`.  All other occurrances are ignored, even when the
    ///      prefix doesn't actually match `target` (therefore not replaced).
    ///      Otherwise, all non-overlapping matches to `target` are replaced.
    /// - Returns: A copy of this collection, but with the subsequences that
    ///   both match the target and don't overlap with an earlier replacement
    ///   getting replaced by the given new value.
    ///
    /// - Complexity: O(*k* × *n²* × *m*), where *n* is the length of this
    ///   collection, *m* is the length of `target`, and *k* is the ratio
    ///   between `target` and `replacement`.
    @inlinable
    public func replacingOccurrences<T: Collection, R: Collection>(
        of target: T,
        with replacement: R,
        onlyAsPrefix: Bool
    ) -> Self where T.Element == Element, R.Element == Element
    {
        return replacingOccurrences(of: target, with: replacement, onlyAsPrefix: onlyAsPrefix, by: ==)
    }

    /// Replaces subsequences of this collection that equal the given collection
    /// with copies of another given collection.
    ///
    /// Comparisons are done element-wise.  If there are runs of different
    /// elements that have the same semantic meaning, like Unicode string
    /// equivalence, both the receiver and the target must be set to the same
    /// normalization before comparing.
    ///
    /// - Parameters:
    ///    - target: A sequence to find within this collection.
    ///    - replacement: A collection whose copies will replace each
    ///      non-overlapping occurrance of `target`.
    ///    - onlyAsPrefix: When `true`, only the prefix of this collection is
    ///      checked for matching `target` and possibly replaced by
    ///      `replacement`.  All other occurrances are ignored, even when the
    ///      prefix doesn't actually match `target` (therefore not replaced).
    ///      Otherwise, all non-overlapping matches to `target` are replaced.
    /// - Postcondition: The elements of this collection are replaced with a
    ///   copy, except subsequences that both match the target and don't overlap
    ///   with an earlier replacement get replaced by the given new value.
    ///
    /// - Complexity: O(*k* × *n²* × *m*), where *n* is the length of this
    ///   collection, *m* is the length of `target`, and *k* is the ratio
    ///   between `target` and `replacement`.
    @inlinable
    public mutating func replaceOccurrences<T: Collection, R: Collection>(
        of target: T,
        with replacement: R,
        onlyAsPrefix: Bool
    ) where T.Element == Element, R.Element == Element
    {
        replaceOccurrences(of: target, with: replacement, onlyAsPrefix: onlyAsPrefix, by: ==)
    }

}

extension RangeReplaceableCollection
where Self: BidirectionalCollection, Element: Equatable {

    /// Copies this collection, except subsequences that equal the given
    /// collection are replaced in a given order with copies of another given
    /// collection.
    ///
    /// Comparisons are done element-wise.  If there are runs of different
    /// elements that have the same semantic meaning, like Unicode string
    /// equivalence, both the receiver and the target must be set to the same
    /// normalization before comparing.
    ///
    /// - Parameters:
    ///    - target: A sequence to find within this collection.
    ///    - replacement: A collection whose copies will replace each
    ///      non-overlapping occurrance of `target`.
    ///    - backwards: When `false`, the first occurrance of `target` will be
    ///      replaced, followed by occurrances that don't overlap with the first
    ///      or any later accepted occurrance.  Otherwise, the last occurrance
    ///      will be replaced, then any occurrances that don't overlap with the
    ///      last or any earlier accepted occurrance.
    ///    - onlyAtLeadingAdfix: When `true`, only the matching occurrance at
    ///      the leading end of this collection will be replaced, leaving all
    ///      other occurrances unchanged.  The leading end is the prefix when
    ///      `backwards` is `false`, and the suffix otherwise.  If the leading
    ///      end does not match `target`, then no replacements are done.
    /// - Returns: A copy of this collection, but with the subsequences that
    ///   both match the target and don't overlap in the given direction getting
    ///   replaced by the given new value.
    ///
    /// - Complexity: O(*k* × *n²* × *m*), where *n* is the length of this
    ///   collection, *m* is the length of `target`, and *k* is the ratio
    ///   between `target` and `replacement`.
    @inlinable
    public func replacingOccurrences<T, R>(
        of target: T,
        with replacement: R,
        backwards: Bool,
        onlyAtLeadingAdfix: Bool
    ) -> Self
        where T: BidirectionalCollection, T.Element == Element,
        R: BidirectionalCollection, R.Element == Element
    {
        return replacingOccurrences(of: target, with: replacement, backwards: backwards, onlyAtLeadingAdfix: onlyAtLeadingAdfix, by: ==)
    }

    /// Replaces in a given order subsequences of this collection that equal the
    /// given collection with copies of another given collection.
    ///
    /// Comparisons are done element-wise.  If there are runs of different
    /// elements that have the same semantic meaning, like Unicode string
    /// equivalence, both the receiver and the target must be set to the same
    /// normalization before comparing.
    ///
    /// - Parameters:
    ///    - target: A sequence to find within this collection.
    ///    - replacement: A collection whose copies will replace each
    ///      non-overlapping occurrance of `target`.
    ///    - backwards: When `false`, the first occurrance of `target` will be
    ///      replaced, followed by occurrances that don't overlap with the first
    ///      or any later accepted occurrance.  Otherwise, the last occurrance
    ///      will be replaced, then any occurrances that don't overlap with the
    ///      last or any earlier accepted occurrance.
    ///    - onlyAtLeadingAdfix: When `true`, only the matching occurrance at
    ///      the leading end of this collection will be replaced, leaving all
    ///      other occurrances unchanged.  The leading end is the prefix when
    ///      `backwards` is `false`, and the suffix otherwise.  If the leading
    ///      end does not match `target`, then no replacements are done.
    /// - Postcondition: The elements of this collection are replaced with a
    ///   copy, except subsequences that both match the target and don't overlap
    ///   in the given direction get replaced by the given new value.
    ///
    /// - Complexity: O(*k* × *n²* × *m*), where *n* is the length of this
    ///   collection, *m* is the length of `target`, and *k* is the ratio
    ///   between `target` and `replacement`.
    @inlinable
    public mutating func replaceOccurrences<T, R>(
        of target: T,
        with replacement: R,
        backwards: Bool,
        onlyAtLeadingAdfix: Bool
    ) where T: BidirectionalCollection, T.Element == Element,
        R: BidirectionalCollection, R.Element == Element
    {
        replaceOccurrences(of: target, with: replacement, backwards: backwards, onlyAtLeadingAdfix: onlyAtLeadingAdfix, by: ==)
    }

}