Proposal to copy C++'s mismatch


(Daryle Walker) #1

I mentioned in other messages about adding permutations and combinations (probably as generators/iterators) to the standard library. I tried making sample implementations and a proposal, but it transitioned to adapting C++’s “is_permutation,” “next_permutation,” and “prev_permutation” instead. The sample implementation of “is_permutation” I saw at <http://en.cppreference.com/w/cpp/algorithm/is_permutation> involves the “mismatch” function, which we also don’t seem to have. Since that function seems like a small enough bite the chew, I finally made a proposal at <https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc>. (The Gist is currently flagged as secret.)

Oh, it seems that everyone here has moved on to Swift 3, and so has my third-party documentation program. Unfortunately, I still on non-beta code, which means Swift 2.2. So I took some time having to translate concepts between the versions, including new names.

The name “mismatch” didn’t seem Swift-y enough since it doesn’t describe what’s happening from a Swift programming perspective. I tried:

* commonPrefixUntil / commonSuffixUntil
* elementsEqualUntil / elementsEqualSince
* elementsShared(until:) / elementsShared(since:)
* elementsDiverge / elementsConverge

No, those parameters on the third one don’t make sense. The last one inspired me to trim the fat and just use “diverge(from:)”. Since we use indexes here like C++’s iterators, that was the best choice for a return type that allows the users to take the results in an inspecting manner or mutating manner. But Swift’s model doesn’t handle reversed collections like C++ does, so I need a separate routine for mismatching with reverse iterators, i.e. searching backwards with indexes. Since I used the “diverge” name for the forward search, I flipped it to “converge(with:)” for the reverse/suffix search. The returns aren’t used in quite the same manner since I have to avoid needing a before-the-start index.

A lot of the format was badly copied from the rotate/reverse proposal (<https://github.com/apple/swift-evolution/blob/master/proposals/0078-rotate-algorithm.md>). Looking for opinions, mistakes/clean-up, anything major missing?...

···


Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com


Blasts from the past: algorithms
SE-0203 — Rename Sequence.elementsEqual
(Daryle Walker) #2

I doesn’t seem that anyone noticed the previous post. Here’s an inline copy:

Implement a mismatch algorithm, equivalent to std::mismatch() in C++

Proposal: SE-NNNN <https://gist.github.com/CTMacUser/NNNN-filename.md>
Author: Daryle Walker <https://github.com/CTMacUser>
Status: Awaiting review
Review manager: TBD
<https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#introduction>Introduction

This proposal is to add difference detection to Swift's standard library collections.

Swift-evolution thread: Discussion thread topic for that proposal <http://news.gmane.org/gmane.comp.lang.swift.evolution>
<https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#motivation>Motivation

Finding where two similar collections differ is needed in algorithms that have different policies on handling the common part versus the uncommon parts. Similar tests already exist in the standard library: the elementsEqual methods in Sequence for instance; the methods can indicate two sequences are different but not where they diverged. Flipping it around, it means that sequence equivalence, and several other sequence methods, can be expressed in terms of mismatch-finding. However, returning the divergence point means returning references to the diverging elements, which means an index, which means that collections are required instead of plain sequences.

<https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#proposed-solution>Proposed solution

The Swift standard library should provide generic implementations of the "mismatch" algorithm for forward searches on prefixes and backward searches on suffixes. The forward/prefix form is called diverges(from: isEquivalent:). The backward/suffix form is called converges(with: isEquivalent:), and is present only when the collection type supports bidirectional indexing. If the collection's element type conforms to Equatable, there variants of the method(s) that drop the second argument and instead use == for the equivalency test.

<https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#detailed-design>Detailed design

<https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#divergesfromisequivalent-and-divergesfrom>diverges(from:isEquivalent:) and diverges(from:)

Forward mismatching on prefixes will be added to the Collection protocol requirements with a default implementation. Its variant will extend Collection with a default implementation. These methods will have the following declarations:

protocol Collection {
    // existing declarations

    /**
        Compares the collection against a given collection element-wise until either corresponding elements are no longer equivalent, using the given predicate as the equivalence test, or at least one collection reaches its end index.

        The predicate must be an equivalence relation over the elements.

        - parameter from: A collection to compare to this one.
        - parameter isEquivalent: A predicate the returns `true` if and only if its two arguments are equivalent.
        - returns: A pair of indices, indicating where the two collections mismatched. The first member is the index of the element that mismatched in this collection, the second is the index of the element that mismatched in the given collection. If the testing stopped because the collections were of different lengths, but were equivalent until that point, then exactly one member of the tuple will be at its collection's end index. If both tuple members are at their respective collection's end index, then the collections were equivalent.
        - complexity: `min(count, from.count)` comparisons.
        - throws: Whatever `isEquivalent` may throw.
    */
    func diverges<PossiblePrefix: Collection where PossiblePrefix.Iterator.Element == Iterator.Element>(from possiblePrefix: PossiblePrefix, isEquivalent: (Iterator.Element, Iterator.Element) throws -> Bool) rethrows -> (Index, PossiblePrefix.Index)
}

extension Collection {
    /**
        Compares the collection against a given collection element-wise until either corresponding elements are no longer equivalent, using the given predicate as the equivalence test, or at least one collection reaches its end index.

        The predicate must be an equivalence relation over the elements.

        - parameter from: A collection to compare to this one.
        - parameter isEquivalent: A predicate the returns `true` if and only if its two arguments are equivalent.
        - returns: A pair of indices, indicating where the two collections mismatched. The first member is the index of the element that mismatched in this collection, the second is the index of the element that mismatched in the given collection. If the testing stopped because the collections were of different lengths, but were equivalent until that point, then exactly one member of the tuple will be at its collection's end index. If both tuple members are at their respective collection's end index, then the collections were equivalent.
        - complexity: `min(count, from.count)` comparisons.
        - throws: Whatever `isEquivalent` may throw.
    */
    func diverges<PossiblePrefix: Collection where PossiblePrefix.Iterator.Element == Iterator.Element>(from possiblePrefix: PossiblePrefix, isEquivalent: (Iterator.Element, Iterator.Element) throws -> Bool) rethrows -> (Index, PossiblePrefix.Index)
}

extension Collection where Iterator.Element: Equatable {
    /**
        Compares the collection against a given collection element-wise until either corresponding elements are no longer equal, or at least one collection reaches its end index.

        - parameter from: A collection to compare to this one.
        - returns: A pair of indices, indicating where the two collections mismatched. The first member is the index of the element that mismatched in this collection, the second is the index of the element that mismatched in the given collection. If the testing stopped because the collections were of different lengths, but were equal until that point, then exactly one member of the tuple will be at its collection's end index. If both tuple members are at their respective collection's end index, then the collections were equal.
        - complexity: `min(count, from.count)` comparisons.
    */
    func diverges<PossiblePrefix: Collection where PossiblePrefix.Iterator.Element == Iterator.Element>(from possiblePrefix: PossiblePrefix) -> (Index, PossiblePrefix.Index)
}
I don't know if we should insist that at least one (or both) of the collections tested should be finite. I don't know if the results should be discardable.

<https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#convergeswithisequivalent-and-convergeswith>converges(with:isEquivalent:) and converges(with:)

Backward mismatching on suffixes will be added to the BidirectionalCollection protocol requirements with a default implementation. Its variant will extend BidirectionalCollection with a default implementation. These methods will have the following declarations:

protocol BidirectionalCollection {
    // existing declarations

    /**
        Compares the collection against a given collection element-wise and backwards until either corresponding elements are no longer equivalent, using the given predicate as the equivalence test, or at least one collection reaches its start index.

        Both collections must be finite.

        The predicate must be an equivalence relation over the elements.

        - parameter with: A collection to compare to this one.
        - parameter isEquivalent: A predicate the returns `true` if and only if its two arguments are equivalent.
        - returns: A pair of indices, indicating where the two collections started to match. The first member is the index of the element that suffix-matched in this collection, the second is the index of the element that suffix-matched in the given collection. If the testing stopped because the collections were of different lengths, but were equivalent until that point, then exactly one member of the tuple will be at its collection's start index. If both tuple members are at their respective collection's start index, then the collections were equivalent. If both tuple members are at their respective collection's end index, then either the collections' last elements differ or at least one collection was empty.
        - complexity: `min(count, from.count)` comparisons.
        - throws: Whatever `isEquivalent` may throw.
    */
    func converges<PossibleSuffix: BidirectionalCollection where PossibleSuffix.Iterator.Element == Iterator.Element>(with possibleSuffix: PossibleSuffix, isEquivalent: (Iterator.Element, Iterator.Element) throws -> Bool) rethrows -> (Index, PossibleSuffix.Index)
}

extension BidirectionalCollection {
    /**
        Compares the collection against a given collection element-wise and backwards until either corresponding elements are no longer equivalent, using the given predicate as the equivalence test, or at least one collection reaches its start index.

        Both collections must be finite.

        The predicate must be an equivalence relation over the elements.

        - parameter with: A collection to compare to this one.
        - parameter isEquivalent: A predicate the returns `true` if and only if its two arguments are equivalent.
        - returns: A pair of indices, indicating where the two collections started to match. The first member is the index of the element that suffix-matched in this collection, the second is the index of the element that suffix-matched in the given collection. If the testing stopped because the collections were of different lengths, but were equivalent until that point, then exactly one member of the tuple will be at its collection's start index. If both tuple members are at their respective collection's start index, then the collections were equivalent. If both tuple members are at their respective collection's end index, then either the collections' last elements differ or at least one collection was empty.
        - complexity: `min(count, from.count)` comparisons.
        - throws: Whatever `isEquivalent` may throw.
    */
    func converges<PossibleSuffix: BidirectionalCollection where PossibleSuffix.Iterator.Element == Iterator.Element>(with possibleSuffix: PossibleSuffix, isEquivalent: (Iterator.Element, Iterator.Element) throws -> Bool) rethrows -> (Index, PossibleSuffix.Index)
}

extension BidirectionalCollection where Iterator.Element: Equatable {
    /**
        Compares the collection against a given collection element-wise and backwards until either corresponding elements are no longer equal, or at least one collection reaches its start index.

        Both collections must be finite.

        - parameter with: A collection to compare to this one.
        - returns: A pair of indices, indicating where the two collections started to match. The first member is the index of the element that suffix-matched in this collection, the second is the index of the element that suffix-matched in the given collection. If the testing stopped because the collections were of different lengths, but were equivalent until that point, then exactly one member of the tuple will be at its collection's start index. If both tuple members are at their respective collection's start index, then the collections were equivalent. If both tuple members are at their respective collection's end index, then either the collections' last elements differ or at least one collection was empty.
        - complexity: `min(count, from.count)` comparisons.
    */
    func converges<PossibleSuffix: BidirectionalCollection where PossibleSuffix.Iterator.Element == Iterator.Element>(with possibleSuffix: PossibleSuffix) -> (Index, PossibleSuffix.Index)
}
I don't know if the results should be discardable.

<https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#impact-on-existing-code>Impact on existing code

The comparison methods are an additive feature that doesn’t impact existing code.

<https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#alternatives-considered>Alternatives considered

The alternative is to not include these methods in the standard library, but the user will need to develop their custom implementation of the mismatch algorithms tailored for their needs.

···


Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com

On Jul 6, 2016, at 5:01 AM, Daryle Walker <darylew@mac.com> wrote:

I mentioned in other messages about adding permutations and combinations (probably as generators/iterators) to the standard library. I tried making sample implementations and a proposal, but it transitioned to adapting C++’s “is_permutation,” “next_permutation,” and “prev_permutation” instead. The sample implementation of “is_permutation” I saw at <http://en.cppreference.com/w/cpp/algorithm/is_permutation> involves the “mismatch” function, which we also don’t seem to have. Since that function seems like a small enough bite the chew, I finally made a proposal at <https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc>. (The Gist is currently flagged as secret.)

Oh, it seems that everyone here has moved on to Swift 3, and so has my third-party documentation program. Unfortunately, I still on non-beta code, which means Swift 2.2. So I took some time having to translate concepts between the versions, including new names.

The name “mismatch” didn’t seem Swift-y enough since it doesn’t describe what’s happening from a Swift programming perspective. I tried:

* commonPrefixUntil / commonSuffixUntil
* elementsEqualUntil / elementsEqualSince
* elementsShared(until:) / elementsShared(since:)
* elementsDiverge / elementsConverge

No, those parameters on the third one don’t make sense. The last one inspired me to trim the fat and just use “diverge(from:)”. Since we use indexes here like C++’s iterators, that was the best choice for a return type that allows the users to take the results in an inspecting manner or mutating manner. But Swift’s model doesn’t handle reversed collections like C++ does, so I need a separate routine for mismatching with reverse iterators, i.e. searching backwards with indexes. Since I used the “diverge” name for the forward search, I flipped it to “converge(with:)” for the reverse/suffix search. The returns aren’t used in quite the same manner since I have to avoid needing a before-the-start index.

A lot of the format was badly copied from the rotate/reverse proposal (<https://github.com/apple/swift-evolution/blob/master/proposals/0078-rotate-algorithm.md>). Looking for opinions, mistakes/clean-up, anything major missing?...


Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com


(Dave Abrahams) #3

I doesn’t seem that anyone noticed the previous post. Here’s an inline copy:

Implement a mismatch algorithm, equivalent to std::mismatch() in C++

I definitely want this algorithm in the standard library, someday soon.
It's out of scope for Swift 3, though.

···

on Thu Jul 07 2016, Daryle Walker <swift-evolution@swift.org> wrote:

Proposal: SE-NNNN <https://gist.github.com/CTMacUser/NNNN-filename.md>
Author: Daryle Walker <https://github.com/CTMacUser>
Status: Awaiting review
Review manager: TBD
<https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#introduction>Introduction

This proposal is to add difference detection to Swift's standard library collections.

Swift-evolution thread: Discussion thread topic for that proposal <http://news.gmane.org/gmane.comp.lang.swift.evolution>
<https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#motivation>Motivation

Finding where two similar collections differ is needed in algorithms that have different policies on handling the common part versus the uncommon parts. Similar tests already exist in the standard library: the elementsEqual methods in Sequence for instance; the methods can indicate two sequences are different but not where they diverged. Flipping it around, it means that sequence equivalence, and several other sequence methods, can be expressed in terms of mismatch-finding. However, returning the divergence point means returning references to the diverging elements, which means an index, which means that collections are required instead of plain sequences.

<https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#proposed-solution>Proposed solution

The Swift standard library should provide generic implementations of the "mismatch" algorithm for forward searches on prefixes and backward searches on suffixes. The forward/prefix form is called diverges(from: isEquivalent:). The backward/suffix form is called converges(with: isEquivalent:), and is present only when the collection type supports bidirectional indexing. If the collection's element type conforms to Equatable, there variants of the method(s) that drop the second argument and instead use == for the equivalency test.

<https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#detailed-design>Detailed design

<https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#divergesfromisequivalent-and-divergesfrom>diverges(from:isEquivalent:) and diverges(from:)

Forward mismatching on prefixes will be added to the Collection protocol requirements with a default implementation. Its variant will extend Collection with a default implementation. These methods will have the following declarations:

protocol Collection {
    // existing declarations

    /**
        Compares the collection against a given collection element-wise until either corresponding elements are no longer equivalent, using the given predicate as the equivalence test, or at least one collection reaches its end index.

        The predicate must be an equivalence relation over the elements.

        - parameter from: A collection to compare to this one.
        - parameter isEquivalent: A predicate the returns `true` if and only if its two arguments are equivalent.
        - returns: A pair of indices, indicating where the two collections mismatched. The first member is the index of the element that mismatched in this collection, the second is the index of the element that mismatched in the given collection. If the testing stopped because the collections were of different lengths, but were equivalent until that point, then exactly one member of the tuple will be at its collection's end index. If both tuple members are at their respective collection's end index, then the collections were equivalent.
        - complexity: `min(count, from.count)` comparisons.
        - throws: Whatever `isEquivalent` may throw.
    */
    func diverges<PossiblePrefix: Collection where PossiblePrefix.Iterator.Element == Iterator.Element>(from possiblePrefix: PossiblePrefix, isEquivalent: (Iterator.Element, Iterator.Element) throws -> Bool) rethrows -> (Index, PossiblePrefix.Index)
}

extension Collection {
    /**
        Compares the collection against a given collection element-wise until either corresponding elements are no longer equivalent, using the given predicate as the equivalence test, or at least one collection reaches its end index.

        The predicate must be an equivalence relation over the elements.

        - parameter from: A collection to compare to this one.
        - parameter isEquivalent: A predicate the returns `true` if and only if its two arguments are equivalent.
        - returns: A pair of indices, indicating where the two collections mismatched. The first member is the index of the element that mismatched in this collection, the second is the index of the element that mismatched in the given collection. If the testing stopped because the collections were of different lengths, but were equivalent until that point, then exactly one member of the tuple will be at its collection's end index. If both tuple members are at their respective collection's end index, then the collections were equivalent.
        - complexity: `min(count, from.count)` comparisons.
        - throws: Whatever `isEquivalent` may throw.
    */
    func diverges<PossiblePrefix: Collection where PossiblePrefix.Iterator.Element == Iterator.Element>(from possiblePrefix: PossiblePrefix, isEquivalent: (Iterator.Element, Iterator.Element) throws -> Bool) rethrows -> (Index, PossiblePrefix.Index)
}

extension Collection where Iterator.Element: Equatable {
    /**
        Compares the collection against a given collection element-wise until either corresponding elements are no longer equal, or at least one collection reaches its end index.

        - parameter from: A collection to compare to this one.
        - returns: A pair of indices, indicating where the two collections mismatched. The first member is the index of the element that mismatched in this collection, the second is the index of the element that mismatched in the given collection. If the testing stopped because the collections were of different lengths, but were equal until that point, then exactly one member of the tuple will be at its collection's end index. If both tuple members are at their respective collection's end index, then the collections were equal.
        - complexity: `min(count, from.count)` comparisons.
    */
    func diverges<PossiblePrefix: Collection where PossiblePrefix.Iterator.Element == Iterator.Element>(from possiblePrefix: PossiblePrefix) -> (Index, PossiblePrefix.Index)
}
I don't know if we should insist that at least one (or both) of the collections tested should be finite. I don't know if the results should be discardable.

<https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#convergeswithisequivalent-and-convergeswith>converges(with:isEquivalent:) and converges(with:)

Backward mismatching on suffixes will be added to the BidirectionalCollection protocol requirements with a default implementation. Its variant will extend BidirectionalCollection with a default implementation. These methods will have the following declarations:

protocol BidirectionalCollection {
    // existing declarations

    /**
        Compares the collection against a given collection element-wise and backwards until either corresponding elements are no longer equivalent, using the given predicate as the equivalence test, or at least one collection reaches its start index.

        Both collections must be finite.

        The predicate must be an equivalence relation over the elements.

        - parameter with: A collection to compare to this one.
        - parameter isEquivalent: A predicate the returns `true` if and only if its two arguments are equivalent.
        - returns: A pair of indices, indicating where the two collections started to match. The first member is the index of the element that suffix-matched in this collection, the second is the index of the element that suffix-matched in the given collection. If the testing stopped because the collections were of different lengths, but were equivalent until that point, then exactly one member of the tuple will be at its collection's start index. If both tuple members are at their respective collection's start index, then the collections were equivalent. If both tuple members are at their respective collection's end index, then either the collections' last elements differ or at least one collection was empty.
        - complexity: `min(count, from.count)` comparisons.
        - throws: Whatever `isEquivalent` may throw.
    */
    func converges<PossibleSuffix: BidirectionalCollection where PossibleSuffix.Iterator.Element == Iterator.Element>(with possibleSuffix: PossibleSuffix, isEquivalent: (Iterator.Element, Iterator.Element) throws -> Bool) rethrows -> (Index, PossibleSuffix.Index)
}

extension BidirectionalCollection {
    /**
        Compares the collection against a given collection element-wise and backwards until either corresponding elements are no longer equivalent, using the given predicate as the equivalence test, or at least one collection reaches its start index.

        Both collections must be finite.

        The predicate must be an equivalence relation over the elements.

        - parameter with: A collection to compare to this one.
        - parameter isEquivalent: A predicate the returns `true` if and only if its two arguments are equivalent.
        - returns: A pair of indices, indicating where the two collections started to match. The first member is the index of the element that suffix-matched in this collection, the second is the index of the element that suffix-matched in the given collection. If the testing stopped because the collections were of different lengths, but were equivalent until that point, then exactly one member of the tuple will be at its collection's start index. If both tuple members are at their respective collection's start index, then the collections were equivalent. If both tuple members are at their respective collection's end index, then either the collections' last elements differ or at least one collection was empty.
        - complexity: `min(count, from.count)` comparisons.
        - throws: Whatever `isEquivalent` may throw.
    */
    func converges<PossibleSuffix: BidirectionalCollection where PossibleSuffix.Iterator.Element == Iterator.Element>(with possibleSuffix: PossibleSuffix, isEquivalent: (Iterator.Element, Iterator.Element) throws -> Bool) rethrows -> (Index, PossibleSuffix.Index)
}

extension BidirectionalCollection where Iterator.Element: Equatable {
    /**
        Compares the collection against a given collection element-wise and backwards until either corresponding elements are no longer equal, or at least one collection reaches its start index.

        Both collections must be finite.

        - parameter with: A collection to compare to this one.
        - returns: A pair of indices, indicating where the two collections started to match. The first member is the index of the element that suffix-matched in this collection, the second is the index of the element that suffix-matched in the given collection. If the testing stopped because the collections were of different lengths, but were equivalent until that point, then exactly one member of the tuple will be at its collection's start index. If both tuple members are at their respective collection's start index, then the collections were equivalent. If both tuple members are at their respective collection's end index, then either the collections' last elements differ or at least one collection was empty.
        - complexity: `min(count, from.count)` comparisons.
    */
    func converges<PossibleSuffix: BidirectionalCollection where PossibleSuffix.Iterator.Element == Iterator.Element>(with possibleSuffix: PossibleSuffix) -> (Index, PossibleSuffix.Index)
}
I don't know if the results should be discardable.

<https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#impact-on-existing-code>Impact on existing code

The comparison methods are an additive feature that doesn’t impact existing code.

<https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#alternatives-considered>Alternatives considered

The alternative is to not include these methods in the standard library, but the user will need to develop their custom implementation of the mismatch algorithms tailored for their needs.


Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com

On Jul 6, 2016, at 5:01 AM, Daryle Walker <darylew@mac.com> wrote:

I mentioned in other messages about adding permutations and
combinations (probably as generators/iterators) to the standard
library. I tried making sample implementations and a proposal, but
it transitioned to adapting C++’s “is_permutation,”
“next_permutation,” and “prev_permutation” instead. The sample
implementation of “is_permutation” I saw at
<http://en.cppreference.com/w/cpp/algorithm/is_permutation
<http://en.cppreference.com/w/cpp/algorithm/is_permutation>>
involves the “mismatch” function, which we also don’t seem to have.
Since that function seems like a small enough bite the chew, I
finally made a proposal at
<https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc
<https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc>>.
(The Gist is currently flagged as secret.)

Oh, it seems that everyone here has moved on to Swift 3, and so has
my third-party documentation program. Unfortunately, I still on
non-beta code, which means Swift 2.2. So I took some time having to
translate concepts between the versions, including new names.

The name “mismatch” didn’t seem Swift-y enough since it doesn’t describe what’s happening from a Swift programming perspective. I tried:

* commonPrefixUntil / commonSuffixUntil
* elementsEqualUntil / elementsEqualSince
* elementsShared(until:) / elementsShared(since:)
* elementsDiverge / elementsConverge

No, those parameters on the third one don’t make sense. The last
one inspired me to trim the fat and just use “diverge(from:)”.
Since we use indexes here like C++’s iterators, that was the best
choice for a return type that allows the users to take the results
in an inspecting manner or mutating manner. But Swift’s model
doesn’t handle reversed collections like C++ does, so I need a
separate routine for mismatching with reverse iterators,
i.e. searching backwards with indexes. Since I used the “diverge”
name for the forward search, I flipped it to “converge(with:)” for
the reverse/suffix search. The returns aren’t used in quite the
same manner since I have to avoid needing a before-the-start index.

A lot of the format was badly copied from the rotate/reverse
proposal
(<https://github.com/apple/swift-evolution/blob/master/proposals/0078-rotate-algorithm.md
<https://github.com/apple/swift-evolution/blob/master/proposals/0078-rotate-algorithm.md>>).
Looking for opinions, mistakes/clean-up, anything major missing?...


Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

--
Dave


(Shawn Erickson) #4

Folks are focusing on Swift 3 and non-critical additive things aren't going
to get attention. It is best to avoid discussion of non-critical additive
proposals until the focus returns to future looking (e.g post Swift 3).

···

On Thu, Jul 7, 2016 at 1:48 PM Daryle Walker via swift-evolution < swift-evolution@swift.org> wrote:

I doesn’t seem that anyone noticed the previous post. Here’s an inline
copy:

Implement a mismatch algorithm, equivalent to std::mismatch() in C++

   - Proposal: SE-NNNN
   <https://gist.github.com/CTMacUser/NNNN-filename.md>
   - Author: Daryle Walker <https://github.com/CTMacUser>
   - Status: Awaiting review
   - Review manager: TBD

<https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#introduction>
Introduction

This proposal is to add difference detection to Swift's standard library
collections.

Swift-evolution thread: Discussion thread topic for that proposal
<http://news.gmane.org/gmane.comp.lang.swift.evolution>

<https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#motivation>
Motivation

Finding where two similar collections differ is needed in algorithms that
have different policies on handling the common part versus the uncommon
parts. Similar tests already exist in the standard library: the
elementsEqual methods in Sequence for instance; the methods can indicate
two sequences are different but not where they diverged. Flipping it
around, it means that sequence equivalence, and several other sequence
methods, can be expressed in terms of mismatch-finding. However, returning
the divergence point means returning references to the diverging elements,
which means an index, which means that collections are required instead of
plain sequences.

<https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#proposed-solution>Proposed
solution

The Swift standard library should provide generic implementations of the
"mismatch" algorithm for forward searches on prefixes and backward searches
on suffixes. The forward/prefix form is called diverges(from:
isEquivalent:). The backward/suffix form is called converges(with:
isEquivalent:), and is present only when the collection type supports
bidirectional indexing. If the collection's element type conforms to
Equatable, there variants of the method(s) that drop the second argument
and instead use == for the equivalency test.

<https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#detailed-design>Detailed
design
<https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#divergesfromisequivalent-and-divergesfrom>
diverges(from:isEquivalent:) and diverges(from:)

Forward mismatching on prefixes will be added to the Collection protocol
requirements with a default implementation. Its variant will extend
Collection with a default implementation. These methods will have the
following declarations:

protocol Collection {
    // existing declarations

    /** Compares the collection against a given collection element-wise until either corresponding elements are no longer equivalent, using the given predicate as the equivalence test, or at least one collection reaches its end index. The predicate must be an equivalence relation over the elements. - parameter from: A collection to compare to this one. - parameter isEquivalent: A predicate the returns `true` if and only if its two arguments are equivalent. - returns: A pair of indices, indicating where the two collections mismatched. The first member is the index of the element that mismatched in this collection, the second is the index of the element that mismatched in the given collection. If the testing stopped because the collections were of different lengths, but were equivalent until that point, then exactly one member of the tuple will be at its collection's end index. If both tuple members are at their respective collection's end index, then the collections were equivalent. - complexity: `min(count, from.count)` comparisons. - throws: Whatever `isEquivalent` may throw. */
    func diverges<PossiblePrefix: Collection where PossiblePrefix.Iterator.Element == Iterator.Element>(from possiblePrefix: PossiblePrefix, isEquivalent: (Iterator.Element, Iterator.Element) throws -> Bool) rethrows -> (Index, PossiblePrefix.Index)
}
extension Collection {
    /** Compares the collection against a given collection element-wise until either corresponding elements are no longer equivalent, using the given predicate as the equivalence test, or at least one collection reaches its end index. The predicate must be an equivalence relation over the elements. - parameter from: A collection to compare to this one. - parameter isEquivalent: A predicate the returns `true` if and only if its two arguments are equivalent. - returns: A pair of indices, indicating where the two collections mismatched. The first member is the index of the element that mismatched in this collection, the second is the index of the element that mismatched in the given collection. If the testing stopped because the collections were of different lengths, but were equivalent until that point, then exactly one member of the tuple will be at its collection's end index. If both tuple members are at their respective collection's end index, then the collections were equivalent. - complexity: `min(count, from.count)` comparisons. - throws: Whatever `isEquivalent` may throw. */
    func diverges<PossiblePrefix: Collection where PossiblePrefix.Iterator.Element == Iterator.Element>(from possiblePrefix: PossiblePrefix, isEquivalent: (Iterator.Element, Iterator.Element) throws -> Bool) rethrows -> (Index, PossiblePrefix.Index)
}
extension Collection where Iterator.Element: Equatable {
    /** Compares the collection against a given collection element-wise until either corresponding elements are no longer equal, or at least one collection reaches its end index. - parameter from: A collection to compare to this one. - returns: A pair of indices, indicating where the two collections mismatched. The first member is the index of the element that mismatched in this collection, the second is the index of the element that mismatched in the given collection. If the testing stopped because the collections were of different lengths, but were equal until that point, then exactly one member of the tuple will be at its collection's end index. If both tuple members are at their respective collection's end index, then the collections were equal. - complexity: `min(count, from.count)` comparisons. */
    func diverges<PossiblePrefix: Collection where PossiblePrefix.Iterator.Element == Iterator.Element>(from possiblePrefix: PossiblePrefix) -> (Index, PossiblePrefix.Index)
}

I don't know if we should insist that at least one (or both) of the
collections tested should be finite. I don't know if the results should be
discardable.

<https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#convergeswithisequivalent-and-convergeswith>
converges(with:isEquivalent:) and converges(with:)

Backward mismatching on suffixes will be added to the
BidirectionalCollection protocol requirements with a default
implementation. Its variant will extend BidirectionalCollection with a
default implementation. These methods will have the following declarations:

protocol BidirectionalCollection {
    // existing declarations

    /** Compares the collection against a given collection element-wise and backwards until either corresponding elements are no longer equivalent, using the given predicate as the equivalence test, or at least one collection reaches its start index. Both collections must be finite. The predicate must be an equivalence relation over the elements. - parameter with: A collection to compare to this one. - parameter isEquivalent: A predicate the returns `true` if and only if its two arguments are equivalent. - returns: A pair of indices, indicating where the two collections started to match. The first member is the index of the element that suffix-matched in this collection, the second is the index of the element that suffix-matched in the given collection. If the testing stopped because the collections were of different lengths, but were equivalent until that point, then exactly one member of the tuple will be at its collection's start index. If both tuple members are at their respective collection's start index, then the collections were equivalent. If both tuple members are at their respective collection's end index, then either the collections' last elements differ or at least one collection was empty. - complexity: `min(count, from.count)` comparisons. - throws: Whatever `isEquivalent` may throw. */
    func converges<PossibleSuffix: BidirectionalCollection where PossibleSuffix.Iterator.Element == Iterator.Element>(with possibleSuffix: PossibleSuffix, isEquivalent: (Iterator.Element, Iterator.Element) throws -> Bool) rethrows -> (Index, PossibleSuffix.Index)
}
extension BidirectionalCollection {
    /** Compares the collection against a given collection element-wise and backwards until either corresponding elements are no longer equivalent, using the given predicate as the equivalence test, or at least one collection reaches its start index. Both collections must be finite. The predicate must be an equivalence relation over the elements. - parameter with: A collection to compare to this one. - parameter isEquivalent: A predicate the returns `true` if and only if its two arguments are equivalent. - returns: A pair of indices, indicating where the two collections started to match. The first member is the index of the element that suffix-matched in this collection, the second is the index of the element that suffix-matched in the given collection. If the testing stopped because the collections were of different lengths, but were equivalent until that point, then exactly one member of the tuple will be at its collection's start index. If both tuple members are at their respective collection's start index, then the collections were equivalent. If both tuple members are at their respective collection's end index, then either the collections' last elements differ or at least one collection was empty. - complexity: `min(count, from.count)` comparisons. - throws: Whatever `isEquivalent` may throw. */
    func converges<PossibleSuffix: BidirectionalCollection where PossibleSuffix.Iterator.Element == Iterator.Element>(with possibleSuffix: PossibleSuffix, isEquivalent: (Iterator.Element, Iterator.Element) throws -> Bool) rethrows -> (Index, PossibleSuffix.Index)
}
extension BidirectionalCollection where Iterator.Element: Equatable {
    /** Compares the collection against a given collection element-wise and backwards until either corresponding elements are no longer equal, or at least one collection reaches its start index. Both collections must be finite. - parameter with: A collection to compare to this one. - returns: A pair of indices, indicating where the two collections started to match. The first member is the index of the element that suffix-matched in this collection, the second is the index of the element that suffix-matched in the given collection. If the testing stopped because the collections were of different lengths, but were equivalent until that point, then exactly one member of the tuple will be at its collection's start index. If both tuple members are at their respective collection's start index, then the collections were equivalent. If both tuple members are at their respective collection's end index, then either the collections' last elements differ or at least one collection was empty. - complexity: `min(count, from.count)` comparisons. */
    func converges<PossibleSuffix: BidirectionalCollection where PossibleSuffix.Iterator.Element == Iterator.Element>(with possibleSuffix: PossibleSuffix) -> (Index, PossibleSuffix.Index)
}

I don't know if the results should be discardable.

<https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#impact-on-existing-code>Impact
on existing code

The comparison methods are an additive feature that doesn’t impact
existing code.

<https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc#alternatives-considered>Alternatives
considered
The alternative is to not include these methods in the standard library,
but the user will need to develop their custom implementation of the
mismatch algorithms tailored for their needs.


Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com

On Jul 6, 2016, at 5:01 AM, Daryle Walker <darylew@mac.com> wrote:

I mentioned in other messages about adding permutations and combinations
(probably as generators/iterators) to the standard library. I tried making
sample implementations and a proposal, but it transitioned to adapting
C++’s “is_permutation,” “next_permutation,” and “prev_permutation”
instead. The sample implementation of “is_permutation” I saw at <
http://en.cppreference.com/w/cpp/algorithm/is_permutation> involves the
“mismatch” function, which we also don’t seem to have. Since that function
seems like a small enough bite the chew, I finally made a proposal at <
https://gist.github.com/CTMacUser/c1a0d7ac60cf827184c33e8768a23dfc>.
(The Gist is currently flagged as secret.)

Oh, it seems that everyone here has moved on to Swift 3, and so has my
third-party documentation program. Unfortunately, I still on non-beta
code, which means Swift 2.2. So I took some time having to translate
concepts between the versions, including new names.

The name “mismatch” didn’t seem Swift-y enough since it doesn’t describe
what’s happening from a Swift programming perspective. I tried:

* commonPrefixUntil / commonSuffixUntil
* elementsEqualUntil / elementsEqualSince
* elementsShared(until:) / elementsShared(since:)
* elementsDiverge / elementsConverge

No, those parameters on the third one don’t make sense. The last one
inspired me to trim the fat and just use “diverge(from:)”. Since we use
indexes here like C++’s iterators, that was the best choice for a return
type that allows the users to take the results in an inspecting manner or
mutating manner. But Swift’s model doesn’t handle reversed collections
like C++ does, so I need a separate routine for mismatching with reverse
iterators, i.e. searching backwards with indexes. Since I used the
“diverge” name for the forward search, I flipped it to “converge(with:)”
for the reverse/suffix search. The returns aren’t used in quite the same
manner since I have to avoid needing a before-the-start index.

A lot of the format was badly copied from the rotate/reverse proposal (<
https://github.com/apple/swift-evolution/blob/master/proposals/0078-rotate-algorithm.md>).
Looking for opinions, mistakes/clean-up, anything major missing?...


Daryle Walker
Mac, Internet, and Video Game Junkie
darylew AT mac DOT com

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution