Deltas

[CTMacUser]

Description

Adds new API for taking a metric function and applying it to each adjacent pair of elements in a sequence, generating a sequence of those results. It's an adaptation of the adjacent_difference function from C++.

Detailed Design

/// An iterator wrapper that vends the changes between each consecutive pair of
/// elements, as evaluated by some closure.
public struct DeltasIterator<Base: IteratorProtocol, Element> {
}

extension DeltasIterator: IteratorProtocol {
    /// Advances to the next element and returns it, or `nil` if no next element
    /// exists.
    public mutating func next() -> Element?
}

/// A sequence wrapper that vends the changes between each consecutive pair of
/// elements, as evaluated by some closure.
public struct DeltasSequence<Base: Sequence, Element> {
    /// The source of the operands for the differentiating closure.
    public let base: Base
}

extension DeltasSequence: LazySequenceProtocol {
    /// A value less than or equal to the number of elements in the sequence,
    /// calculated nondestructively.
    public var underestimatedCount: Int { get }

    /// Returns an iterator over the elements of this sequence.
    public func makeIterator() -> DeltasIterator<Base.Iterator, Element>
}

/// A collection wrapper presenting the changes between each consecutive pair of
/// elements, as evaluated by some closure.
public typealias DeltasCollection<T: Collection, U> = DeltasSequence<T, U>

extension DeltasSequence: Collection, LazyCollectionProtocol where Base: Collection {
    /// The position of the first element in a nonempty collection.
    public var startIndex: Base.Index { get }
    /// The collection's "past the end" position---that is, the position one
    /// greater than the last valid subscript argument.
    public var endIndex: Base.Index { get }

    /// Accesses the element at the specified position.
    public subscript(position: Base.Index) -> Element { get }
    /// Accesses a contiguous subrange of the collection's elements.
    public subscript(bounds: Range<Base.Index>) -> DeltasSequence<Base.SubSequence, Element> { get }

    /// Returns an index that is the specified distance from the given index.
    public func index(_ i: Base.Index, offsetBy distance: Int) -> Base.Index
    /// Returns an index that is the specified distance from the given index,
    /// unless that distance is beyond a given limiting index.
    public func index(_ i: Base.Index, offsetBy distance: Int, limitedBy limit: Base.Index) -> Base.Index?
    /// Returns the distance between two indices.
    public func distance(from start: Base.Index, to end: Base.Index) -> Int

    /// Returns the position immediately after the given index.
    public func index(after i: Base.Index) -> Base.Index
}

extension DeltasSequence: BidirectionalCollection where Base: BidirectionalCollection {
    /// Returns the position immediately before the given index.
    public func index(before i: Base.Index) -> Base.Index
}

extension DeltasSequence: RandomAccessCollection where Base: RandomAccessCollection {
}

extension Sequence {
    /// Differentiates the sequence into an array, formed by applying the given
    /// closure on each pair of consecutive elements in order.
    public func deltas<T>(via subtracter: (Element, Element) throws -> T) rethrows -> [T]
}

extension LazySequenceProtocol {
    /// Differentiates this sequence into a lazily generated sequence, formed by
    /// applying the given closure on each pair of consecutive elements in order.
    public func deltas<T>(via subtracter: @escaping (Element, Element) -> T) -> DeltasSequence<Elements, T>
}

extension Sequence where Element: AdditiveArithmetic {
    /// Differentiates this sequence into a lazy sequence formed by the
    /// differences between each pair of consecutive elements in order.
    public func differences() -> DeltasSequence<Self, Element>
}

extension Sequence where Element: SIMD, Element.Scalar: FloatingPoint {
    /// Differentiates this sequence into a lazy sequence formed by the vector
    /// differences between each pair of consecutive elements in order.
    public func differences() -> DeltasSequence<Self, Element>
}

extension Sequence where Element: FixedWidthInteger {
    /// Differentiates this sequence into a lazy sequence formed by the wrapped
    /// differences between each pair of consecutive elements in order.
    public func wrappedDifferences() -> DeltasSequence<Self, Element>
}

extension Sequence where Element: SIMD, Element.Scalar: FixedWidthInteger {
    /// Differentiates this sequence into a lazy sequence formed by the vector
    /// wrapped-differences between each pair of consecutive elements in order.
    public func wrappedDifferences() -> DeltasSequence<Self, Element>
}

extension Sequence where Element: Strideable {
    /// Differentiates this sequence into a lazy sequence formed by the
    /// strides between each pair of consecutive elements in order.
    public func strides() -> DeltasSequence<Self, Element.Stride>
}

Documentation Plan

The methods, types, and the types' 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

[xwu]

Is this functionality not adequately served by the existing slidingWindows API? If not, we should figure out what's missing and augment that API, rather than duplicating it.

[timvermeulen]

slidingWindows is on Collection, so it doesn't completely cover this, but something like .adjacentPairs().map(...) seems like it might.

[CTMacUser]

something like .adjacentPairs().map(...)

Where is "adjacentPairs" defined at?. It appears only as part of a comment (for permutations) in this project.

[timvermeulen]

Where is "adjacentPairs" defined at?

It doesn't currently exist, but if it did, it would (seemingly?) cover the functionality of this PR. But I'm not familiar with the corresponding C++ function or why they added it.