Detection of One Sorted Sequence Being a Subset of Another

Description

This function is an adaptation of the includes function from C++. This pull request is a sequel to "Detection of How One Sorted Sequence Includes Another" (#38).

I started with a new version of the Inclusion type and the sortedOverlap function from Pull #38. I added another function, includes, that calls the overlap detector then translates the exact overlap degree to a simple Bool result.

Then I figured that no one actually cares about the precise overlapping factor. So the precise-overlap function and support type were removed, and its code was moved into includes directly. Since a general answer wasn't required, I could add short-circuit logic.

Detailed Design

One primary function extends Sequence to test if a given sequence is a subset of the receiver, assuming both are sorted according to the given predicate. (The given sequence's elements need not be contiguous in the receiver.) The variant function removes the predicate parameter for a default of the less-than operator (<), at the cost of requiring Comparable conformance.

extension Sequence {
    public func
    includes<T: Sequence>(sorted other: T, sortedBy areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> Bool
    where T.Element == Element
}

extension Sequence where Element: Comparable {
    @inlinable public func
    includes<T: Sequence>(sorted other: T) -> Bool
    where T.Element == Element
}

Documentation Plan

Both introductory documentation and a guide were added.

Test Plan

A test file was added.

Source Impact

The functions are an additive change, not otherwise affecting the API.

Checklist

[x] I've added at least one test that validates that my change is working, if appropriate
[x] I've followed the code style of the rest of the project
[x] I've read the Contribution Guidelines
[x] I've updated the documentation if necessary

apple / swift-algorithms