Add initializer with uniquing closure(s)

[DandyLyons]

Add an initializer that is equivalent to Dictionarys init(_:uniquingKeysWith:).

Design Discussion

I attempted to do a rough draft implementation of this and discovered that the problem space is more complex for our type. (For more info, see the "What Are Duplicates.md" docs that I added to PR #15 ). In short, we need to guarantee that both left and right are unique. Dictionary only needs to guarantee that keys are unique, and therefore it's sufficient to provide one closure to unique just the keys.

So what should be the shape of our initializer?

One Closure

Perhaps we could use a shape like this:

public init<S>(
        _ pairs: S,
        uniquingLeftRightPairsWith combineLeftRight: ((Left, Right), (Left, Right) throws -> (Left, Right))
    ) rethrows where S: Sequence, S.Element == (Left, Right) {
        self.init()
    }

I need to think more about how this would be implemented. In the case of Dictionary, the combine closure is called when two identical key values are found. But in our case we need to call this closure even when they are not perfectly identical. We need to call it when:

1. Both tuples have the same Left value
2. or both tuples have the same Right value
3. but not when a Left value matches a Right value.

Two Closures

Alternatively we could ask for two closures. One to deduplicate each side respectively. We could use a shape like this:

init<S>(
        _ pairs: S,
        uniquingLeftWith combineLeft: (Left, Left) throws -> Left,
        uniquingRightWith combineRight: (Right, Right) throws -> Right
    ) rethrows where S: Sequence, S.Element == (Left, Right)

But again, I'm not sure how this would be implemented. Would combineLeft be processed on everything first, and then we process using combineRight?

Implementation Discussion

I looked at Dictionary's implementation for inspiration. There are many layers of abstraction, so I'm still wrapping my head around it.

I did notice a few interesting things

1. their implementation uses a public method merge(). Perhaps we should offer and use this. https://developer.apple.com/documentation/swift/dictionary/merge(_:uniquingkeyswith:)-m2ub
2. Under the hood merge() uses an internal _mutatingFind and _find method. It also passes an isUnique variable. I'm not certain if this is relevant to our use case as, unlike them, we are not interacting directly with the hash table. See: https://github.com/swiftlang/swift/blob/c49aeaf177090f4803c5604732cd184be9fa2600/stdlib/public/core/NativeDictionary.swift#L768

[ladvoc]

I implemented a method which checks what type of conflict exists, if any, between a new left-right pair and the current contents of the dictionary. A conflict in this context is a condition that would override an existing left-right pair or break the bijective property. See commit 6eb46cf.

This would allow defining the initializer as follows:

/// Creates a new dictionary from the left-right pairs in the given sequence, using a combining
/// to resolve conflicts.
/// - Parameters:
///   - leftRightPairs: A sequence of left-right pairs to use for the new dictionary.
///   - combine: A closure that is called when a conflict is encountered, receiving the left-right pair
///     and a description of the conflict that exists.
init<S>(
    _ leftRightPairs: S,
    uniquingWith combine: (Element, Conflict) throws -> Element
) rethrows where S: Sequence, S.Element == Element

Note: Element is a type alias of (left: Left, right: Right).

[DandyLyons]

6eb46cf looks good.

Perhaps let's hold off on this issue until that commit is merged.

[ladvoc]

I have renamed the helper methods and made them public as per your suggestion. Please see PR #20.

[DandyLyons]

Do you want to tackle the uniquing init?

[ladvoc]

I have implemented init(discardingConflicts:) initializer, a special case of init(uniquingWith:) which discards all conflicting left-right pairs. See commit dc62d25.

I am giving more thought to the best way to define init(uniquingWith:) to make it easy to use.