Detection of How One Sorted Sequence Includes Another

[CTMacUser]

Description

Adds a new API for detecting how two already sorted sequences overlap. It is a generalization of the includes function from C++. It returns a custom type instead of a Boolean.

Detailed Design

/// The manner two (multi-)sets may overlap, including degenerate cases.
enum Inclusion {
  case bothUninhabited, onlyFirstInhabited, onlySecondInhabited,
       dualExclusivesOnly, sharedOnly, firstExtendsSecond,
       secondExtendsFirst, dualExclusivesAndShared
}

extension Inclusion {
  /// Whether there are elements exclusive to the first source.
  var hasExclusivesToFirst: Bool { get }
  /// Whether there are elements exclusive to the second source.
  var hasExclusivesToSecond: Bool { get }
  /// Whether there are elements shared by both sources.
  var hasSharedElements: Bool { get }
  /// Whether the sources are identical.
  var areIdentical: Bool { get }
  /// Whether the first source contains everything from the second.
  var doesFirstIncludeSecond: Bool { get }
  /// Whether the second source contains everything from the first.
  var doesSecondIncludeFirst: Bool { get }
}

extension Sequence {
  /// Returns how this sequence and the given sequence overlap, assuming both
  /// are sorted according to the given predicate that can compare elements.
  func sortedOverlap<S: Sequence>(
    with other: S,
    by areInIncreasingOrder: (Element, Element) throws -> Bool
  ) rethrows -> Inclusion where S.Element == Element
}

extension Sequence where Element: Comparable {
  /// Returns how this sequence and the given sequence overlap, assuming both
  /// are sorted.
  func sortedOverlap<S: Sequence>(
    with other: S
  ) -> Inclusion where S.Element == Element
}

Documentation Plan

The methods, type, and the type's cases and properties have block documents. There is also a guide file.

Test Plan

A test file is included.

Source Impact

It adds 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