# 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?