Need a shorter-range unique filter sequence

I'm trying out a sorted set type for the Containers sub-library. A quick way to get a sorted unique sequence is to pass the source sequence through a sorting method then a method to get rid of any duplicates.

The current uniqued methods from the Algorithms sub-library isn't suitable for this. The big problem is the Hashable requirement. I can only guarantee that elements are Comparable. The type is generic, so the arbitrary-type-to-Hashable method isn't useful, because that would require a universal hash computation. And even if there was one, I would want to use the type's == for the comparisons. After the sorting, duplicate values will be right next to each other, so any kind of Set-based strategy (which is why Hashable is usually needed) is overkill.

I wrote a quick, limited-range, deduplication method:

/// A sequence vending the elements of its wrapped sequence that do not equal
/// their predecessor.
public struct LocallyUniqued<Base: Sequence> { /*...*/ }

/// An iterator vending the elements of its wrapped sequence that do not equal
/// their predecessor.
public struct LocallyDeduplicatingIterator<Base: IteratorProtocol> { /*...*/ }

extension LocallyUniqued : LazySequenceProtocol where Base : LazySequenceProtocol {
}

extension Sequence {

    /// Returns a collection of the given type that is a copy of this sequence
    /// except runs of the same value, determined by using the given predicate as
    /// an equivalence test, are compacted to just the first element of each run.
    @usableFromInline
    internal func locallyUnique<T: RangeReplaceableCollection>(
        into type: T.Type, by areEquivalent: (Element, Element) throws -> Bool
    ) rethrows -> T where T.Element == Element

    /// Returns an array that is a copy of this sequence except runs of the same
    /// value, determined by using the given predicate as an equivalence test, are
    /// compacted to just the first element of each run.
    ///
    /// The predicate must be a *equivalence relation* over the elements. That
    /// is, for any elements `a`, `b`, and `c`, the following conditions must
    /// hold:
    ///
    /// - `areEquivalent(a, a)` is always `true`. (Reflexivity)
    /// - `areEquivalent(a, b)` implies `areEquivalent(b, a)`. (Symmetry)
    /// - If `areEquivalent(a, b)` and `areEquivalent(b, c)` are both `true`, then
    ///   `areEquivalent(a, c)` is also `true`. (Transitivity)
    ///
    /// The following example uses case-insensitive equality for comparisons:
    ///
    ///      let animals = ["dog", "pig", "Pig", "cat", "ox", "dog", "Cat"]
    ///      let uniqued = animals.locallyUniqued() { $0.lowercased() == $1.lowercased() }
    ///      print(uniqued)
    ///      // Prints '["dog", "pig", "cat", "ox", "dog", "Cat"]'
    ///
    /// - Precondition: The sequence must be finite.
    ///
    /// - Parameter areEquivalent: A predicate that returns `true` if its two
    ///   arguments are equivalent; otherwise, `false`.
    /// - Returns: An array with only the locally-unique elements of this
    ///   sequence.
    ///
    /// - Complexity: O(*n*), where *n* is the length of this sequence.
    @inlinable public func locallyUnique(by areEquivalent: (Element, Element) throws -> Bool) rethrows -> [Element]
}

extension Sequence where Self.Element : Equatable {

    /// Returns a sequence that is a copy of this sequence except runs of the same
    /// value are compacted to just the first element of each run.
    ///
    ///      let animals = ["dog", "pig", "Pig", "cat", "ox", "dog", "dog", "Cat"]
    ///      let uniqued = animals.locallyUniqued()
    ///      print(Array(uniqued))
    ///      // Prints '["dog", "pig", "Pig", "cat", "ox", "dog", "Cat"]'
    ///
    /// - Returns: A sequence vending only the locally-unique elements of this
    ///   sequence.
    ///
    /// - Complexity: O(1).
    @inlinable public func locallyUnique() -> LocallyUniqued<Self>
}

extension LazySequenceProtocol {

    /// Returns a sequence that is a copy of this sequence except runs of the same
    /// value, determined by using the given predicate as an equivalence test, are
    /// lazily compacted to just the first element of each run.
    ///
    /// The predicate must be a *equivalence relation* over the elements. That
    /// is, for any elements `a`, `b`, and `c`, the following conditions must
    /// hold:
    ///
    /// - `areEquivalent(a, a)` is always `true`. (Reflexivity)
    /// - `areEquivalent(a, b)` implies `areEquivalent(b, a)`. (Symmetry)
    /// - If `areEquivalent(a, b)` and `areEquivalent(b, c)` are both `true`, then
    ///   `areEquivalent(a, c)` is also `true`. (Transitivity)
    ///
    /// The following example uses case-insensitive equality for comparisons:
    ///
    ///      let animals = ["dog", "pig", "Pig", "cat", "ox", "dog", "dog", "Cat"]
    ///      let uniqued = animals.lazy.locallyUniqued() { $0.lowercased() == $1.lowercased() }
    ///      print(Array(uniqued))
    ///      // Prints '["dog", "pig", "cat", "ox", "dog", "Cat"]'
    ///
    /// - Parameter areEquivalent: A predicate that returns `true` if its two
    ///   arguments are equivalent; otherwise, `false`.
    /// - Returns: A lazily-generated sequence vending only the locally-unique
    ///   elements of this sequence.
    ///
    /// - Complexity: O(1).
    @inlinable public func locallyUnique(by areEquivalent: @escaping (Element, Element) -> Bool) -> LocallyUniqued<Elements>
}

extension LazySequenceProtocol where Self.Element : Equatable {

    /// Returns a sequence that is a copy of this sequence except runs of the same
    /// value are lazily compacted to just the first element of each run.
    ///
    ///      let animals = ["dog", "pig", "Pig", "cat", "ox", "dog", "dog", "Cat"]
    ///      let uniqued = animals.lazy.locallyUnique()
    ///      print(Array(uniqued))
    ///      // Prints '["dog", "pig", "Pig", "cat", "ox", "dog", "Cat"]'
    ///
    /// - Parameter areEquivalent: A predicate that returns `true` if its two
    ///   arguments are equivalent; otherwise, `false`.
    /// - Returns: A lazily-generated sequence vending only the locally-unique
    ///   elements of this sequence.
    ///
    /// - Complexity: O(1).
    @inlinable public func locallyUnique() -> LocallyUniqued<Elements>
}

Interesting idea to add to the Algorithms sub-library?

Terms of Service

Privacy Policy

Cookie Policy