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?