A set type, in Swift 5(.1), that stores its elements in strictly increasing order, requiring Comparable instead of Hashable. Also includes: binary search, sort detection, streaming set operations, and (space-wise) debouncing.

BinarySearch.swift

//
//  BinarySearch.swift
//  SortedSet
//
//  Created by Daryle Walker on 8/22/19.
//  Copyright © 2019 Daryle Walker. All rights reserved.
//


extension Collection {

    /// Assuming the collection is partitioned along the given predicate,
    /// returns the index for the pivot element separating the partitions.
    ///
    /// - Precondition: All elements that match the given predicate are after
    ///   all the elements the don't match.
    ///
    /// - Parameter belongsInSecondPartition: A predicate whose partitioning
    ///   would be compatibile with the collection's current sort.
    /// - Returns: The index of the first element that matches
    ///   `belongsInSecondPartition`, or `endIndex` if no elements match.
    ///
    /// - Complexity: O(log *n*) for random-access collections, O(*n*)
    ///   otherwise, where *n* is the length of the collection.
    public func partitionIndex(by belongsInSecondPartition: (Element) throws -> Bool) rethrows -> Index {
        // Ensure 'self[start]' at the end will be dereferenceable.
        guard !isEmpty else { return endIndex }

        // Whittle down to one element via binary search.
        var start = startIndex, end = endIndex
        while case let span = distance(from: start, to: end), span > 1 {
            let middle = index(start, offsetBy: span / 2)
            if try belongsInSecondPartition(self[middle]) {
                end = middle
            } else {
                start = middle
            }
        }

        // Check which side that sole element is on.
        assert(start < end && index(after: start) == end)
        return try belongsInSecondPartition(self[start]) ? start : end
    }

    /// Assuming a monotonic sequence, returns the index for the first element
    /// exceeding the given limit, using the given predicate for comparisons.
    ///
    /// The collection must already sorted according to the given predicate,
    /// such that a binary search can be used.  If the type has certain values
    /// that cannot be compared, like the default floating-point numeric types
    /// with their Not-a-Number states and `<`, then such values cannot be used
    /// for an element.
    ///
    /// If the collection also conforms to `RangeReplaceableCollection`, then
    /// the return value is where an element with value `limit` may be inserted
    /// while maintaining the sort.
    ///
    /// - Precondition: The collection's elements values all must be of the same
    ///   comparison class as `limit` by the standards of `areInIncreasingOrder`
    ///   and be non-decreasing (*i.e.* all subsequences are either steady-order
    ///   or strictly increasing).
    ///
    /// - Parameter limit: The element value threshold to search for.
    /// - Parameter areInIncreasingOrder: A predicate that returns `true` when
    ///   its first argument should be ordered before its second, and `false`
    ///   otherwise.
    /// - Returns: The first index with a corresponding element ahead of
    ///   `limit`, or `endIndex` if no element is.
    ///
    /// - Complexity: O(log *n*) for random-access collections, O(*n*)
    ///   otherwise, where *n* is the length of the collection.
    @inlinable
    public func firstIndexOfSorted(exceeding limit: Element, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> Index {
        return try partitionIndex() { try areInIncreasingOrder(limit, $0) }
    }

    /// Assuming a monotonic sequence, returns the indices for the elements
    /// matching the given target, using the given predicate for comparisons.
    ///
    /// The collection must already sorted according to the given predicate,
    /// such that a binary search can be used.  If the type has certain values
    /// that cannot be compared, like the default floating-point numeric types
    /// with their Not-a-Number states and `<`, then such values cannot be used
    /// for an element.
    ///
    /// - Precondition: The collection's elements must have all their values be
    ///   of the same comparison class as `target` (by the standards of
    ///   `areInIncreasingOrder`) and be non-decreasing (*i.e.* all subsequences
    ///   are either steady-order or strictly increasing).
    ///
    /// - Parameter target: The element value to search for.
    /// - Parameter areInIncreasingOrder: A predicate that returns `true` when
    ///   its first argument should be ordered before its second, and `false`
    ///   otherwise.
    /// - Returns: A range from the first element not lower than the target to
    ///   right before the first element higher than the target.  If there are
    ///   no elements equivalent to `target`, an empty range centered on the
    ///   first higher element is returned, or `endIndex..<endIndex` if there
    ///   are no higher elements.
    ///
    /// - Complexity: O(log *n*) for random-access collections, O(*n*)
    ///   otherwise, where *n* is the length of the collection.
    @inlinable
    public func indicesOfSorted(for target: Element, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> Range<Index> {
        let greater = try partitionIndex { try areInIncreasingOrder(target, $0) }
        let notLess = try self[..<greater].partitionIndex { try !areInIncreasingOrder($0, target) }
        return notLess..<greater
    }

}

extension Collection where Element: Comparable {

    /// Assuming a non-decreasing sequence, returns the index for the first
    /// element greater than the given limit.
    ///
    /// The collection must already be sorted, such that a binary search can be
    /// used.  If the type has certain values that cannot be compared, like the
    /// default floating-point types' Not-a-Number values, then such values
    /// cannot be used for an element.
    ///
    /// If the collection also conforms to `RangeReplaceableCollection`, then
    /// the return value is where an element with value `limit` may be inserted
    /// while maintaining the sort.
    ///
    /// - Precondition: The collection's element values all must be of the same
    ///   comparison class as `limit`, and be non-decreasing (*i.e.* a
    ///   subsequent element must be either equal or greater than its
    ///   predecessor).
    ///
    /// - Parameter limit: The element value threshold to search for.
    /// - Returns: The first index with a corresponding element greater than
    ///   `limit`, or `endIndex` if none are.
    ///
    /// - Complexity: O(log *n*) for random-access collections, O(*n*)
    ///   otherwise, where *n* is the length of the collection.
    @inlinable
    public func firstIndexOfSorted(exceeding limit: Element) -> Index {
        return firstIndexOfSorted(exceeding: limit, by: <)
    }

    /// Assuming a non-decreasing sequence, returns the indices for the elements
    /// equal to the given target.
    ///
    /// The collection must already be sorted, such that a binary search can be
    /// used.  If the type has certain values that cannot be compared, like the
    /// default floating-point types' Not-a-Number values, then such values
    /// cannot be used for an element.
    ///
    /// - Precondition: The collection's elements must have all their values be
    ///   of the same comparison class as `target`, and be non-decreasing
    ///   (*i.e.* a subsequent element must be either equal or greater than its
    ///   predecessor).
    ///
    /// - Parameter target: The element value to search for.
    /// - Returns: A range from the first element equal to `target` to right
    ///   before the first one greater.  If there are no equal elements, an
    ///   empty range on the first greater element is returned, or
    ///   `endIndex..<endIndex` if there is no such element.
    ///
    /// - Complexity: O(log *n*) for random-access collections, O(*n*)
    ///   otherwise, where *n* is the length of the collection.
    @inlinable
    public func indicesOfSorted(for target: Element) -> Range<Index> {
        return indicesOfSorted(for: target, by: <)
    }

    /// Assuming a non-decreasing sequence, returns the indices for the elements
    /// with values within the given range.
    ///
    /// The collection must already be sorted, such that a binary search can be
    /// used.  If the type has certain values that cannot be compared, like the
    /// default floating-point types' Not-a-Number values, then such values
    /// cannot be used for an element.
    ///
    /// - Precondition: Both the collection and range must have all their
    ///   elements in the same comparison class.  Further, the elements of the
    ///   collection must be non-decreasing (*i.e.* a subsequent element must be
    ///   either equal or greater than its predecessor).
    ///
    /// - Parameter targets: The element values to search for.
    /// - Returns: The index range for the maximal-length subsequence such that
    ///   `self[returnValue].allSatisfy { targets.contains($0) }`; such a
    ///   subsequence may be empty.  If the returned range is empty, then its
    ///   index is centered on the first element with a value at least that of
    ///   any bounded by `targets`, or `endIndex` if there's no such element.
    ///
    /// - Complexity: O(log *n*) for random-access collections, O(*n*)
    ///   otherwise, where *n* is the length of the collection.
    @inlinable
    public func indicesOfSorted(over targets: Range<Element>) -> Range<Index> {
        let notLess = partitionIndex { $0 >= targets.lowerBound }
        let greater = self[notLess...].partitionIndex { $0 >= targets.upperBound }
        return notLess..<greater
    }

}

Debounce.swift

//
//  Debounce.swift
//  SortedSet
//
//  Created by Daryle Walker on 9/12/19.
//  Copyright © 2019 Daryle Walker. All rights reserved.
//


// MARK: Debouncing, Eager

extension Sequence {

    /// Returns the elements of the sequence as a collection of the given type,
    /// collapsing consecutive equivalent elements to a single instance, using
    /// the given predicate as the equivalence test.
    ///
    /// - Parameter type: A metatype specifier for the type of the returned
    ///   collection.
    /// - Parameter areEquivalent: A predicate that returns `true` when its
    ///   first argument is equivalent to the second, and `false` otherwise.
    /// - Returns: A copy of this sequence with consecutively equivalent
    ///   elements filtered out.
    ///
    /// - Complexity: O(*n*), where *n* is the length of this sequence.
    public func debounced<T>(to type: T.Type, by areEquivalent: (Element, Element) throws -> Bool) rethrows -> T where T: RangeReplaceableCollection, T.Element == Element {
        var iterator = makeIterator()
        guard var previous = iterator.next() else { return T() }

        var result = T(repeating: previous, count: 1)
        result.reserveCapacity(underestimatedCount)
        while let current = iterator.next() {
            guard try !areEquivalent(previous, current) else { continue }
            defer { previous = current }

            result.append(current)
        }
        return result
    }

    /// Returns the elements of the sequence as an array, collapsing consecutive
    /// equivalent elements to a single instance, using the given predicate as
    /// the equivalence test.
    ///
    /// - Parameter areEquivalent: A predicate that returns `true` when its
    ///   first argument is equivalent to the second, and `false` otherwise.
    /// - Returns: A copy of this sequence with consecutively equivalent
    ///   elements filtered out.
    ///
    /// - Complexity: O(*n*), where *n* is the length of this sequence.
    @inlinable
    public func debounced(by areEquivalent: (Element, Element) throws -> Bool) rethrows -> [Element] {
        return try debounced(to: Array.self, by: areEquivalent)
    }

}

extension Sequence where Element: Equatable {

    /// Returns the elements of the sequence as a collection of the given type,
    /// collapsing consecutive equal elements to a single instance.
    ///
    /// - Parameter type: A metatype specifier for the type of the returned
    ///   collection.
    /// - Returns: A copy of this sequence with consecutively equal elements
    ///   filtered out.
    ///
    /// - Complexity: O(*n*), where *n* is the length of this sequence.
    @inlinable
    public func debounced<T>(to type: T.Type) -> T where T: RangeReplaceableCollection, T.Element == Element {
        return debounced(to: T.self, by: ==)
    }

    /// Returns the elements of the sequence as an array, collapsing consecutive
    /// equal elements to a single instance.
    ///
    /// - Returns: A copy of this sequence with consecutively equal elements
    ///   filtered out.
    ///
    /// - Complexity: O(*n*), where *n* is the length of this sequence.
    @inlinable
    public func debounced() -> [Element] {
        return debounced(to: Array.self)
    }

}

extension RangeReplaceableCollection {

    /// Returns the elements of the collection, but collapsing consecutive
    /// equivalent elements to a single instance, using the given predicate as
    /// the equivalence test.
    ///
    /// - Parameter areEquivalent: A predicate that returns `true` when its
    ///   first argument is equivalent to the second, and `false` otherwise.
    /// - Returns: A copy of this collection with consecutively equivalent
    ///   elements filtered out.
    ///
    /// - Complexity: O(*n*), where *n* is the length of this sequence.
    @inlinable
    public func debounced(by areEquivalent: (Element, Element) throws -> Bool) rethrows -> Self {
        return try debounced(to: Self.self, by: areEquivalent)
    }

}

extension RangeReplaceableCollection where Element: Equatable {

    /// Returns the elements of the collection, but collapsing consecutive equal
    /// elements to a single instance.
    ///
    /// - Returns: A copy of this sequence with consecutively equal elements
    ///   filtered out.
    ///
    /// - Complexity: O(*n*), where *n* is the length of this sequence.
    @inlinable
    public func debounced() -> Self {
        return debounced(by: ==)
    }

}

// MARK: - Debouncing, Lazy

// MARK: Iterator

/// An iterator that vends only the elements of its base that are not equivalent
/// to their predecessors.
public struct LazyDebouncingIterator<Base: IteratorProtocol> {

    /// The source iterator.
    @usableFromInline
    var base: Base
    /// The predicate to check for equivalence.
    @usableFromInline
    let areEquivalent: (Base.Element, Base.Element) -> Bool
    /// The last element returned.
    @usableFromInline
    var previous: Base.Element?

    /// Creates an iterator passing along the elements of the given iterator,
    /// except those equivalent to their predecessor, determined by the given
    /// predicate.
    @inlinable
    init(_ base: Base, by areEquivalent: @escaping (Base.Element, Base.Element) -> Bool) {
        self.base = base
        self.areEquivalent = areEquivalent
        previous = nil
    }

}

extension LazyDebouncingIterator: IteratorProtocol {

    public typealias Element = Base.Element

    public mutating func next() -> Element? {
        if let previous = previous {
            self.previous = nil
            while let current = base.next() {
                guard !areEquivalent(previous, current) else { continue }

                self.previous = current
                break
            }
        } else {
            previous = base.next()
        }
        return previous
    }

}

// MARK: Sequence

/// A sequence that vends only the elements of its base that are not equivalent
/// to their predecessors.
public struct LazyDebouncingSequence<Base: Sequence> {

    /// The source sequence.
    @usableFromInline
    let base: Base
    /// The predicate to check for equivalence.
    @usableFromInline
    let areEquivalent: (Base.Element, Base.Element) -> Bool

    /// Creates a sequence passing along the elements of the given sequence,
    /// except those equivalent to their predecessor, determined by the given
    /// predicate.
    @inlinable
    init(_ base: Base, by areEquivalent: @escaping (Base.Element, Base.Element) -> Bool) {
        self.base = base
        self.areEquivalent = areEquivalent
    }

}

extension LazyDebouncingSequence: Sequence {

    public typealias Iterator = LazyDebouncingIterator<Base.Iterator>
    public typealias Element = Iterator.Element

    @inlinable
    public __consuming func makeIterator() -> Iterator {
        return LazyDebouncingIterator(base.makeIterator(), by: areEquivalent)
    }

    @inlinable
    public var underestimatedCount: Int {
        return base.underestimatedCount.signum()
    }

}

extension LazyDebouncingSequence: LazySequenceProtocol {}

// MARK: Collection

/// A collection that vends only the elements of its base that are not
/// equivalent to their predecessors.
///
/// - Note: Traversing to adjacent elements requires an O(n) search time, maybe
///   giving subpar performance.
public typealias LazyDebouncingCollection<T: Collection> = LazyDebouncingSequence<T>

extension LazyDebouncingCollection: Collection {

    public typealias SubSequence = LazyDebouncingCollection<Base.SubSequence>
    public typealias Index = Base.Index

    @inlinable
    public var startIndex: Index {
        return base.startIndex
    }
    @inlinable
    public var endIndex: Index {
        return base.endIndex
    }

    public func index(after i: Index) -> Index {
        precondition(i < endIndex)

        let antiTarget = self[i]
        let nextBaseIndex = base.index(after: i)
        return base[nextBaseIndex...].firstIndex { !areEquivalent($0, antiTarget) } ?? base.endIndex
    }

    @inlinable
    public subscript(position: Index) -> Element {
        return base[position]
    }
    @inlinable
    public subscript(bounds: Range<Index>) -> SubSequence {
        return LazyDebouncingCollection<Base.SubSequence>(base[bounds], by: areEquivalent)
    }

}

extension LazyDebouncingCollection: LazyCollectionProtocol {}

extension LazyDebouncingCollection: BidirectionalCollection where Base: BidirectionalCollection {

    public func index(before i: Index) -> Index {
        precondition(i > startIndex)

        // When handling a block of equivalent values, the iterator, startIndex,
        // and index(after:) compare all non-first elements to the first one.
        // Here, we're compare all non-last elements to the last one.  If the
        // predicate has a slack factor such that it isn't perfectly transitive,
        // and the last and first elements aren't perfectly equivalent, then the
        // following search may stop at a different element than the first,
        // which would be VERY bad for consistency.

        let previousBaseIndex = base.index(before: i)
        let previousValue = base[previousBaseIndex]
        assert(i == endIndex || !areEquivalent(previousValue, self[i]))

        let previousStart: Base.Index
        if let doublePreviousBaseIndex = base[..<previousBaseIndex].lastIndex(where: { !areEquivalent($0, previousValue) }) {
            previousStart = base.index(after: doublePreviousBaseIndex)
        } else {
            previousStart = base.startIndex
        }
        return previousStart
    }

}

// MARK: Generators

extension LazySequenceProtocol {

    /// Returns the sequence's elements, lazily filtering out elements that are
    /// equivalent to their immediate predecessor, using the given predicate as
    /// the equivalence test.
    ///
    /// - Parameter areEquivalent: A predicate that returns `true` when its
    ///   first argument is equivalent to the second, and `false` otherwise.
    /// - Returns: A sequence that vends the same elements as this sequence as
    ///   needed, filtering out consecutively equivalent ones after the first.
    @inlinable
    public func debounced(by areEquivalent: @escaping (Element, Element) -> Bool) -> LazyDebouncingSequence<Elements> {
        return LazyDebouncingSequence(elements, by: areEquivalent)
    }

}

extension LazySequenceProtocol where Element: Equatable {

    /// Returns the sequence's elements, lazily filtering out elements that are
    /// equal to their immediate predecessor.
    ///
    /// - Returns: A sequence that vends the same elements as this sequence as
    ///   needed, filtering out consecutively equal ones after the first.
    @inlinable
    public func debounced() -> LazyDebouncingSequence<Elements> {
        return debounced(by: ==)
    }

}

IsSorted.swift

//
//  IsSorted.swift
//  SortedSet
//
//  Created by Daryle Walker on 8/24/19.
//  Copyright © 2019 Daryle Walker. All rights reserved.
//


// MARK: Partition Confirmation

extension Sequence {

    /// Hoping the sequence is partitioned along the given predicate, returns
    /// the two element surrounding the pivot where that assumption fails.
    ///
    /// - Precondition: The sequence is finite.
    ///
    /// - Parameter belongsInSecondPartition: A predicate whose partitioning is
    ///   supposedly compatible with the sequence's current sort.
    /// - Returns: If there's a point where an element categorized in the second
    ///   partition is followed by one that is supposed to be in the first
    ///   partition (which violates partitioning), return those two elements,
    ///   otherwise return `nil`.
    ///
    /// - Complexity: O(*n*), where *n* is the length of the sequence.
    public func partitionFailure(by belongsInSecondPartition: (Element) throws -> Bool) rethrows -> (Element, Element)? {
        var iterator = makeIterator()
        guard var previous = iterator.next() else { return nil }

        while let current = iterator.next() {
            defer { previous = current }

            if try belongsInSecondPartition(previous), try !belongsInSecondPartition(current) {
                return (previous, current)
            }
        }
        return nil
    }

    /// Returns whether a sequence is really partitioned according to the given
    /// predicate.
    ///
    /// - Precondition: The sequence is finite.
    ///
    /// - Parameter belongsInSecondPartition: A predicate whose partitioning is
    ///   supposedly compatible with the sequence's current sort.
    /// - Returns: Whether the sequence never flips its partition state down.
    ///
    /// - Complexity: O(*n*), where *n* is the length of the sequence.
    @inlinable
    public func isPartitioned(by belongsInSecondPartition: (Element) throws -> Bool) rethrows -> Bool {
        return try partitionFailure(by: belongsInSecondPartition) == nil
    }

}

// MARK: - Sorting Confirmation

extension Sequence {

    /// Hoping the sequence is sorted along the given predicate that can compare
    /// between elements, returns the two elements surrounding the point where
    /// that assumption fails.
    ///
    /// - Precondition: The sequence is finite; and all of its elements must be
    ///   of the same comparison class (by the standards of
    ///   `areInIncreasingOrder`).
    ///
    /// - Parameter monotonic: Whether consecutive elements being equivalent is
    ///   OK when checking the sort, or must elements continuously increase in
    ///   order ranking.
    /// - Parameter areInIncreasingOrder: A predicate that returns `true` when
    ///   its first argument should be ordered before its second, and `false`
    ///   otherwise.  It's supposedly compatible with the sequence's current
    ///   sort.
    /// - Returns: If there's a point where an element is followed by one that
    ///   is in decreasing order (or equivalent order if `monotonic` is
    ///   `false`), return those two elements, otherwise return `nil`.
    ///
    /// - Complexity: O(*n*), where *n* is the length of the sequence.
    public func sortFailure(monotonic: Bool, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> (Element, Element)? {
        var iterator = makeIterator()
        guard var previous = iterator.next() else { return nil }

        while let current = iterator.next() {
            defer { previous = current }
            guard try !areInIncreasingOrder(previous, current) else { continue }

            if try areInIncreasingOrder(current, previous) || !monotonic {
                return (previous, current)
            }
        }
        return nil
    }

    /// Returns whether a sequence could be considered sorted according to the
    /// given predicate that can compare between elements.
    ///
    /// - Precondition: The sequence is finite; and all of its elements must be
    ///   of the same comparison class (by the standards of
    ///   `areInIncreasingOrder`).
    ///
    /// - Parameter monotonic: Whether consecutive elements being equivalent is
    ///   OK when checking the sort, or must elements continuously increase in
    ///   order ranking.
    /// - Parameter areInIncreasingOrder: A predicate that returns `true` when
    ///   its first argument should be ordered before its second, and `false`
    ///   otherwise.  It's supposedly compatible with the sequence's current
    ///   sort.
    /// - Returns: Whether the sequence is sorted.
    ///
    /// - Complexity: O(*n*), where *n* is the length of the sequence.
    @inlinable
    public func isSorted(monotonically monotonic: Bool, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> Bool {
        return try sortFailure(monotonic: monotonic, by: areInIncreasingOrder) == nil
    }

}

// MARK: - Confirmation with Collections

extension Collection {

    /// Returns where the collection ends being partitioned according to the
    /// given predicate that can compare between elements.
    ///
    /// - Parameter belongsInSecondPartition: A predicate whose partitioning is
    ///   supposedly compatible with the collection's current sort.
    /// - Returns: The index where the collection's elements starting being part
    ///   of the first partition again, or `endIndex` if the collection never
    ///   flips its partition state back.
    ///
    /// - Complexity: O(*n*), where *n* is the length of the collection.
    @inlinable
    public func endIndexOfPartitions(by belongsInSecondPartition: (Element) throws -> Bool) rethrows -> Index {
        return try indices.partitionFailure { try belongsInSecondPartition(self[$0]) }?.1 ?? endIndex
    }

    /// Returns where the collection ends being sorted according to the given
    /// predicate that can compare between elements.
    ///
    /// - Precondition: All of the elements must be of the same comparison class
    ///   (by the standards of `areInIncreasingOrder`).
    ///
    /// - Parameter monotonic: Whether consecutive elements being equivalent is
    ///   OK when checking the sort, or must elements continuously increase in
    ///   order ranking.
    /// - Parameter areInIncreasingOrder: A predicate that returns `true` when
    ///   its first argument should be ordered before its second, and `false`
    ///   otherwise.  It's supposedly compatible with the collection's current
    ///   sort.
    /// - Returns: The index where the collection's elements regress in ranking,
    ///   or maintain in ranking if `monotonic` is `false`.  If no disqualifying
    ///   transitions occur when iterating, `endIndex` is returned.
    ///
    /// - Complexity: O(*n*), where *n* is the length of the collection.
    @inlinable
    public func endIndexOfSorted(monotonically monotonic: Bool, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> Index {
        return try indices.sortFailure(monotonic: monotonic) { try areInIncreasingOrder(self[$0], self[$1]) }?.1 ?? endIndex
    }

}

extension Collection where Element: Comparable {

    /// Returns where the collection ends being sorted.
    ///
    /// - Precondition: All of the elements must be of the same comparison
    ///   class.
    ///
    /// - Parameter monotonic: Whether consecutive elements being equal is OK
    ///   when checking the sort.  (Otherwise, elements must continuously
    ///   increase.)
    /// - Returns: The first index where its element is either less than (when
    ///   `monotonic` is `true`) or not greater than (`monotonic` is `false`)
    ///   its predecessor, or `endIndex` if no such element is found.
    ///
    /// - Complexity: O(*n*), where *n* is the length of the collection.
    @inlinable
    public func endIndexOfSorted(monotonically monotonic: Bool) -> Index {
        return endIndexOfSorted(monotonically: monotonic, by: <)
    }

}

SetMerge.swift

//
//  SetMerge.swift
//  SortedSet
//
//  Created by Daryle Walker on 9/16/19.
//  Copyright © 2019 Daryle Walker. All rights reserved.
//


// MARK: Support Types for Sequence-Set Combinations

/// The operations to merge two sets together.
public enum SetBinaryOperation: UInt, CaseIterable {

    /// No elements are included.
    case empty
    /// Elements of the second set that are not in the first.
    case exclusivelySecond
    /// Elements that are in both sets.
    case intersection
    /// Elements that are in the second set.
    case second
    /// Elements of the first set that are not in the second.
    case exclusivelyFirst
    /// Elements that are in exactly one set.
    case symmetricDifference
    /// Elements that are in the first set.
    case first
    /// Elements that are in either set.
    case union

    /// Whether elements exclusive to the first set are included.
    @inlinable
    public var hasFirstExclusives: Bool {
        return rawValue & 0x04 != 0
    }
    /// Whether elements shared with both sets are included.
    @inlinable
    public var hasShared: Bool {
        return rawValue & 0x02 != 0
    }
    /// Whether elements exclusive to the second set are included.
    @inlinable
    public var hasSecondExclusives: Bool {
        return rawValue & 0x01 != 0
    }

}

// MARK: - Eager Sequence-Set Combinations

extension Sequence {

    /// Assuming this sequence is strictly increasing according to the given
    /// predicate, and so is the given sequence, returns the application of the
    /// given set operation to those sequences as a collection of the given
    /// type.
    ///
    /// The receiver is the first set operand and `other` is the second.
    ///
    /// - Precondition: Both sequences must be finite.
    ///
    /// - Parameter operation: The set operation to apply to the receiver and
    ///   `other`.  (One or both operands may end up being ignored.)
    /// - Parameter other: A sequence whose elements will be combined with
    ///   this one's elements.
    /// - Parameter type: A meta-type specifier for the type of the collection
    ///   returned.
    /// - Parameter areInIncreasingOrder: A predicate that returns `true` if
    ///   its first argument should be ordered before its second argument;
    ///   otherwise, `false`.
    /// - Returns: A collection with the resulting elements from the set
    ///   operation, in an order compatible with the predicate.
    ///
    /// - Complexity: O(*n* + *m*), where *n* and *m* are the lengths of the
    ///   sequences.
    public func applySetOperation<S: Sequence, T: RangeReplaceableCollection>(_ operation: SetBinaryOperation, with other: S, returningAs type: T.Type, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> T where S.Element == Element, T.Element == Element {
        var potentialSelf, potentialOther: Element?
        var selfIterator = makeIterator(), otherIterator = other.makeIterator()
        var mergedSet = T()
        mergedSet.reserveCapacity(underestimatedCount + other.underestimatedCount)
        loop: while true {
            if potentialSelf == nil {
                potentialSelf = selfIterator.next()
            }
            if potentialOther == nil {
                potentialOther = otherIterator.next()
            }
            switch (potentialSelf, potentialOther) {
            case (nil, nil):
                break loop
            case let (latestSelf?, latestOther?) where try areInIncreasingOrder(latestSelf, latestOther):
                fallthrough
            case (let latestSelf?, nil):
                if operation.hasFirstExclusives {
                    mergedSet.append(latestSelf)
                }
                potentialSelf = nil
            case let (latestSelf?, latestOther?) where try areInIncreasingOrder(latestOther, latestSelf):
                fallthrough
            case (nil, let latestOther?):
                if operation.hasSecondExclusives {
                    mergedSet.append(latestOther)
                }
                potentialOther = nil
            case let (latestSelf?, latestOther?):  // equivalent
                if operation.hasShared {
                    mergedSet.append(operation == .second ? latestOther : latestSelf)
                }
                potentialSelf = nil
                potentialOther = nil
            }
        }
        return mergedSet
    }

    /// Assuming this sequence is strictly increasing according to the given
    /// predicate, and so is the given sequence, returns an array containing the
    /// results of applying the given set operation to the sequences.
    ///
    /// The receiver is the first set operand and `other` is the second.
    ///
    /// - Precondition: Both sequences must be finite.
    ///
    /// - Parameter operation: The set operation to apply to the receiver and
    ///   `other`.  (One or both operands may end up being ignored.)
    /// - Parameter other: A sequence whose elements will be combined with
    ///   this one's elements.
    /// - Parameter areInIncreasingOrder: A predicate that returns `true` if
    ///   its first argument should be ordered before its second argument;
    ///   otherwise, `false`.
    /// - Returns: An array with the resulting elements from the set operation,
    ///   in an order compatible with the predicate.
    ///
    /// - Complexity: O(*n* + *m*), where *n* and *m* are the lengths of the
    ///   sequences.
    @inlinable
    public func applySetOperation<S: Sequence>(_ operation: SetBinaryOperation, with other: S, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> [Element] where S.Element == Element {
        return try applySetOperation(operation, with: other, returningAs: Array.self, by: areInIncreasingOrder)
    }

    /// Assuming this sequence is strictly increasing according to the given
    /// predicate, and so is the given sequence, returns how many element values
    /// are and are not shared.
    ///
    /// - Precondition: Both sequences must be finite.
    ///
    /// - Parameter other: A sequence whose elements will be combined with
    ///   this one's elements.
    /// - Parameter areInIncreasingOrder: A predicate that returns `true` if
    ///   its first argument should be ordered before its second argument;
    ///   otherwise, `false`.
    /// - Returns: A tuple with the counts of: elements exclusive to the
    ///   receiver, elements shared by both sequences, and elements exclusive to
    ///   `other`.
    ///
    /// - Complexity: O(*n* + *m*), where *n* and *m* are the lengths of the
    ///   sequences.
    public func setStatistics<S: Sequence>(combiningWith other: S, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> (receiver: Int, shared: Int, other: Int) where S.Element == Element {
        var potentialSelf, potentialOther: Element?
        var selfIterator = makeIterator(), otherIterator = other.makeIterator()
        var receiverExclusiveCount = 0, sharedCount = 0, otherExclusiveCount = 0
        loop: while true {
            if potentialSelf == nil {
                potentialSelf = selfIterator.next()
            }
            if potentialOther == nil {
                potentialOther = otherIterator.next()
            }
            switch (potentialSelf, potentialOther) {
            case (nil, nil):
                break loop
            case let (latestSelf?, latestOther?) where try areInIncreasingOrder(latestSelf, latestOther):
                fallthrough
            case (_?, nil):
                receiverExclusiveCount += 1
                potentialSelf = nil
            case let (latestSelf?, latestOther?) where try areInIncreasingOrder(latestOther, latestSelf):
                fallthrough
            case (nil, _?):
                otherExclusiveCount += 1
                potentialOther = nil
            case (_?, _?):  // equivalent
                sharedCount += 1
                potentialSelf = nil
                potentialOther = nil
            }
        }
        return (receiverExclusiveCount, sharedCount, otherExclusiveCount)
    }

}

extension Sequence where Element: Comparable {

    /// Assuming this and the given sequence are both strictly increasing,
    /// returns the application of the given set operation to those sequences as
    /// a collection of the given type.
    ///
    /// The receiver is the first set operand and `other` is the second.
    ///
    /// - Precondition: Both sequences must be finite.
    ///
    /// - Parameter operation: The set operation to apply to the receiver and
    ///   `other`.  (One or both operands may end up being ignored.)
    /// - Parameter other: A sequence whose elements will be combined with
    ///   this one's elements.
    /// - Parameter type: A meta-type specifier for the type of the collection
    ///   returned.
    /// - Returns: A collection with the resulting elements from the set
    ///   operation, in an order compatible with the predicate.
    ///
    /// - Complexity: O(*n* + *m*), where *n* and *m* are the lengths of the
    ///   sequences.
    @inlinable
    public func applySetOperation<S: Sequence, T: RangeReplaceableCollection>(_ operation: SetBinaryOperation, with other: S, returningAs type: T.Type) -> T where S.Element == Element, T.Element == Element {
        return applySetOperation(operation, with: other, returningAs: type, by: <)
    }

    /// Assuming this and the given sequence are both strictly increasing,
    /// returns an array containing the results of applying the given set
    /// operation to the sequences.
    ///
    /// The receiver is the first set operand and `other` is the second.
    ///
    /// - Precondition: Both sequences must be finite.
    ///
    /// - Parameter operation: The set operation to apply to the receiver and
    ///   `other`.  (One or both operands may end up being ignored.)
    /// - Parameter other: A sequence whose elements will be combined with
    ///   this one's elements.
    /// - Returns: An array with the resulting elements from the set operation,
    ///   in an order compatible with the predicate.
    ///
    /// - Complexity: O(*n* + *m*), where *n* and *m* are the lengths of the
    ///   sequences.
    @inlinable
    public func applySetOperation<S: Sequence>(_ operation: SetBinaryOperation, with other: S) -> [Element] where S.Element == Element {
        return applySetOperation(operation, with: other, returningAs: Array.self)
    }

    /// Assuming this and the given sequence are both strictly increasing,
    /// returns how many element values are and are not shared.
    ///
    /// - Precondition: Both sequences must be finite.
    ///
    /// - Parameter other: A sequence whose elements will be combined with
    ///   this one's elements.
    /// - Returns: A tuple with the counts of: elements exclusive to the
    ///   receiver, elements shared by both sequences, and elements exclusive to
    ///   `other`.
    ///
    /// - Complexity: O(*n* + *m*), where *n* and *m* are the lengths of the
    ///   sequences.
    @inlinable
    public func setStatistics<S: Sequence>(combiningWith other: S) -> (receiver: Int, shared: Int, other: Int) where S.Element == Element {
        return setStatistics(combiningWith: other, by: <)
    }

}

// MARK: - Lazy Sequence-Set Combinations

// MARK: Iterator

/// An iterator vending the set-merger of two strictly increasing iterators.
public struct LazySetApplicationIterator<First: IteratorProtocol, Second: IteratorProtocol> where First.Element == Second.Element {

    /// The first set iterator.
    var first: First
    /// The second set iterator.
    var second: Second
    /// The ordering predicate.
    let areInIncreasingOrder: (First.Element, Second.Element) -> Bool
    /// The set-operation to perform.
    let operation: SetBinaryOperation

    /// The count of elements exclusive to the first set read so far.
    public private(set) var exclusivelyFirstCount: Int
    /// The count of elements read so far that are members of both sets.
    public private(set) var sharedCount: Int
    /// The count of elements exclusive to the second set read so far.
    public private(set) var exclusivelySecondCount: Int

    /// The last element from the first set read but not used.
    private var potentialFirst: First.Element?
    /// The last element from the second set read but not used.
    private var potentialSecond: Second.Element?

    /// Creates a strictly increasing (based off the given predicate) iteration
    /// generated from applying the given set operation to the given strictly
    /// increasing iterators.
    init(first: First, operation: SetBinaryOperation, second: Second, by areInIncreasingOrder: @escaping (First.Element, Second.Element) -> Bool) {
        self.first = first
        self.second = second
        self.areInIncreasingOrder = areInIncreasingOrder
        self.operation = operation
        exclusivelyFirstCount = 0
        sharedCount = 0
        exclusivelySecondCount = 0
        potentialFirst = nil
        potentialSecond = nil
    }

}

extension LazySetApplicationIterator: IteratorProtocol {

    public mutating func next() -> First.Element? {
        while true {
            if potentialFirst == nil {
                potentialFirst = first.next()
            }
            if potentialSecond == nil {
                potentialSecond = second.next()
            }
            switch (potentialFirst, potentialSecond) {
            case (nil, nil):
                return nil
            case let (latestFirst?, latestSecond?) where areInIncreasingOrder(latestFirst, latestSecond):
                fallthrough
            case (let latestFirst?, nil):
                potentialFirst = nil
                exclusivelyFirstCount += 1
                if operation.hasFirstExclusives {
                    return latestFirst
                }
            case let (latestFirst?, latestSecond?) where areInIncreasingOrder(latestSecond, latestFirst):
                fallthrough
            case (nil, let latestSecond?):
                potentialSecond = nil
                exclusivelySecondCount += 1
                if operation.hasSecondExclusives {
                    return latestSecond
                }
            case let (latestFirst?, latestSecond?):  // equivalent
                potentialFirst = nil
                potentialSecond = nil
                sharedCount += 1
                if operation.hasShared {
                    return operation != .second ? latestFirst : latestSecond
                }
            }
        }
    }

}

// MARK: Sequence

/// A sequence vending the set-merger of two strictly increasing sequences.
public struct LazySetApplicationSequence<First: Sequence, Second: Sequence> where First.Element == Second.Element {

    /// The first set sequence.
    @usableFromInline
    let first: First
    /// The second set sequence.
    @usableFromInline
    let second: Second
    /// The ordering predicate.
    @usableFromInline
    let areInIncreasingOrder: (First.Element, Second.Element) -> Bool
    /// The set-operation to perform.
    @usableFromInline
    let operation: SetBinaryOperation

    /// Creates a strictly increasing (based off the given predicate) sequence
    /// generated from applying the given set operation to the given strictly
    /// increasing sequences.
    @inlinable
    init(first: First, operation: SetBinaryOperation, second: Second, by areInIncreasingOrder: @escaping (First.Element, Second.Element) -> Bool) {
        self.first = first
        self.second = second
        self.areInIncreasingOrder = areInIncreasingOrder
        self.operation = operation
    }

}

extension LazySetApplicationSequence: Sequence {

    public __consuming func makeIterator() -> LazySetApplicationIterator<First.Iterator, Second.Iterator> {
        return LazySetApplicationIterator(first: first.makeIterator(), operation: operation, second: second.makeIterator(), by: areInIncreasingOrder)
    }

    public var underestimatedCount: Int {
        // Even when the operation isn't .empty, we can't know if any elements
        // from either sequence will pass through without reading them.
        return 0
    }

}

extension LazySetApplicationSequence: LazySequenceProtocol {}

// MARK: Generators

extension LazySequenceProtocol {

    /// Assuming this and the given lazy sequence are both strictly increasing
    /// according to the given predicate, returns a lazily-evaluated sequence of
    /// the results of apply the given set operation to the sequences.
    ///
    /// The receiver is the first set operand and `other` is the second.
    ///
    /// - Precondition: Both sequences must be finite.
    ///
    /// - Parameter operation: The set operation to apply to the receiver and
    ///   `other`.  (One or both operands may end up being ignored.)
    /// - Parameter other: A sequence whose elements will be combined with
    ///   this one's elements.
    /// - Parameter areInIncreasingOrder: A predicate that returns `true` if
    ///   its first argument should be ordered before its second argument;
    ///   otherwise, `false`.
    /// - Returns: A sequence that computes the resulting elements from the
    ///   set operation on-demand, in an order compatible with the predicate.
    @inlinable
    public func applySetOperation<L: LazySequenceProtocol>(_ operation: SetBinaryOperation, with other: L, by areInIncreasingOrder: @escaping (Element, Element) -> Bool) -> LazySetApplicationSequence<Elements, L.Elements> where L.Element == Element {
        return LazySetApplicationSequence(first: elements, operation: operation, second: other.elements, by: areInIncreasingOrder)
    }

    /// Assuming this and the given sequence are both strictly increasing
    /// according to the given predicate, returns a lazily-evaluated sequence of
    /// the results of apply the given set operation to the sequences.
    ///
    /// The receiver is the first set operand and `other` is the second.
    ///
    /// - Precondition: Both sequences must be finite.
    ///
    /// - Parameter operation: The set operation to apply to the receiver and
    ///   `other`.  (One or both operands may end up being ignored.)
    /// - Parameter other: A sequence whose elements will be combined with
    ///   this one's elements.
    /// - Parameter areInIncreasingOrder: A predicate that returns `true` if
    ///   its first argument should be ordered before its second argument;
    ///   otherwise, `false`.
    /// - Returns: A sequence that computes the resulting elements from the
    ///   set operation on-demand, in an order compatible with the predicate.
    @inlinable
    public func applySetOperation<S: Sequence>(_ operation: SetBinaryOperation, with other: S, by areInIncreasingOrder: @escaping (Element, Element) -> Bool) -> LazySetApplicationSequence<Elements, LazySequence<S>.Elements> where S.Element == Element {
        return applySetOperation(operation, with: other.lazy, by: areInIncreasingOrder)
    }

}

extension LazySequenceProtocol where Element: Comparable {

    /// Assuming this and the given lazy sequence are both strictly increasing,
    /// returns a lazily-evaluated sequence of the results of applying the given
    /// set operation to the sequences.
    ///
    /// The receiver is the first set operand and `other` is the second.
    ///
    /// - Precondition: Both sequences must be finite.
    ///
    /// - Parameter operation: The set operation to apply to the receiver and
    ///   `other`.  (One or both operands may end up being ignored.)
    /// - Parameter other: A sequence whose elements will be combined with
    ///   this one's elements.
    /// - Returns: A sequence that computes the resulting elements from the
    ///   set operation on-demand, in an order compatible with the predicate.
    @inlinable
    public func applySetOperation<L: LazySequenceProtocol>(_ operation: SetBinaryOperation, with other: L) -> LazySetApplicationSequence<Elements, L.Elements> where L.Element == Element {
        return applySetOperation(operation, with: other, by: <)
    }

    /// Assuming this and the given sequence are both strictly increasing,
    /// returns a lazily-evaluated sequence of the results of applying the given
    /// set operation to the sequences.
    ///
    /// The receiver is the first set operand and `other` is the second.
    ///
    /// - Precondition: Both sequences must be finite.
    ///
    /// - Parameter operation: The set operation to apply to the receiver and
    ///   `other`.  (One or both operands may end up being ignored.)
    /// - Parameter other: A sequence whose elements will be combined with
    ///   this one's elements.
    /// - Returns: A sequence that computes the resulting elements from the
    ///   set operation on-demand, in an order compatible with the predicate.
    @inlinable
    public func applySetOperation<S: Sequence>(_ operation: SetBinaryOperation, with other: S) -> LazySetApplicationSequence<Elements, LazySequence<S>.Elements> where S.Element == Element {
        return applySetOperation(operation, with: other.lazy)
    }

}

SortedSet.swift

//
//  SortedSet.swift
//  SortedSet
//
//  Created by Daryle Walker on 9/12/19.
//  Copyright © 2019 Daryle Walker. All rights reserved.
//


// MARK: Always-Sorted Collection, Primary Definition

/// An sorted collection of unique elements.
///
/// You use a sorted set instead of an array when you need to test somewhat
/// efficiently for membership and you aren't concerned with the order of the
/// elements in the collection, or when you need to ensure that each element
/// appears only once in a collection.
///
/// You can create a set with any element type that conforms to the `Comparable`
/// protocol. By default, many types in the standard library are comparable,
/// including strings, the numeric types, and even sorted-sets themselves.
///
/// Swift makes it as easy to create a new sorted-set as to create a new array.
/// Simply assign an array literal to a variable or constant with the
/// `SortedSet` type specified.
///
///     let ingredients: SortedSet = ["cocoa beans", "sugar", "cocoa butter", "salt"]
///     if ingredients.contains("sugar") {
///         print("No thanks, too sweet.")
///     }
///     // Prints "No thanks, too sweet."
///
/// Set Operations
/// ==============
///
/// Sorted-sets provide a suite of mathematical set operations. For example, you
/// can efficiently test a set for membership of an element or check its
/// intersection with another set:
///
/// - Use the `contains(_:)` method to test whether a set contains a specific
///   element.
/// - Use the "equal to" operator (`==`) to test whether two sets contain the
///   same elements.
/// - Use the `isSubset(of:)` method to test whether a set contains all the
///   elements of another set or sequence.
/// - Use the `isSuperset(of:)` method to test whether all elements of a set
///   are contained in another set or sequence.
/// - Use the `isStrictSubset(of:)` and `isStrictSuperset(of:)` methods to test
///   whether a set is a subset or superset of, but not equal to, another set.
/// - Use the `isDisjoint(with:)` method to test whether a set has any elements
///   in common with another set.
///
/// You can also combine, exclude, or subtract the elements of two sets:
///
/// - Use the `union(_:)` method to create a new set with the elements of a set
///   and another set or sequence.
/// - Use the `intersection(_:)` method to create a new set with only the
///   elements common to a set and another set or sequence.
/// - Use the `symmetricDifference(_:)` method to create a new set with the
///   elements that are in either a set or another set or sequence, but not in
///   both.
/// - Use the `subtracting(_:)` method to create a new set with the elements of
///   a set that are not also in another set or sequence.
///
/// You can modify a set in place by using these methods' mutating
/// counterparts: `formUnion(_:)`, `formIntersection(_:)`,
/// `formSymmetricDifference(_:)`, and `subtract(_:)`.
///
/// Set operations are not limited to use with other sorted-sets. Instead, you
/// can perform set operations with another set, an array, or any other sequence
/// type.
///
///     var primes: SortedSet = [2, 3, 5, 7]
///
///     // Tests whether primes is a subset of a Range<Int>
///     print(primes.isSubset(of: 0..<10))
///     // Prints "true"
///
///     // Performs an intersection with an Array<Int>
///     let favoriteNumbers = [5, 7, 15, 21]
///     print(primes.intersection(favoriteNumbers))
///     // Prints "[5, 7]"
///
/// Sequence and Collection Operations
/// ==================================
///
/// In addition to the `SortedSet` type's set operations, you can use any
/// nonmutating sequence or collection methods with a set.
///
///     if primes.isEmpty {
///         print("No primes!")
///     } else {
///         print("We have \(primes.count) primes.")
///     }
///     // Prints "We have 4 primes."
///
///     let primesSum = primes.reduce(0, +)
///     // 'primesSum' == 17
///
///     let primeStrings = primes.map(String.init)
///     // 'primeStrings' == ["2", "3", "5", "7"]
///
/// You can iterate through a sorted-set's elements with a `for`-`in` loop.
///
///     for number in primes {
///         print(number)
///     }
///     // Prints "2"
///     // Prints "3"
///     // Prints "5"
///     // Prints "7"
///
/// Many sequence and collection operations return an array or a type-erasing
/// collection wrapper instead of a sorted-set. To restore efficient set
/// operations, create a new sorted-set from the result.
///
///     let morePrimes = primes.union([11, 13, 17, 19])
///
///     let floatPrimes = morePrimes.map(Double.init)
///     // 'floatPrimes' is of type Array<Double>
///
///     let floatPrimesSet = SortedSet(morePrimes.map(Double.init))
///     // 'floatPrimesSet' is of type SortedSet<Double>
public struct SortedSet<Element: Comparable> {

    /// The container for the elements.
    @usableFromInline
    typealias _Base = ArraySlice<Element>

    /// The already sorted elements.
    @usableFromInline
    internal private(set) var elements: _Base

    /// Confirms the type's invariant: the elements are sorted and unique.
    private var invariant: Bool {
        return elements.isSorted(monotonically: false, by: <)
    }

    /// Creates a set from a given already-prepared collection.
    ///
    /// - Precondition: `elements` already matches the invariant.
    ///
    /// - Parameter elements: The sorted elements for this set.
    ///
    /// - Postcondition: This set represents the given element values.
    @usableFromInline
    init(elements: _Base) {
        self.elements = elements
        assert(invariant)
    }

    // Read the elements of the given sequence, keeping only one copy of any
    // given value, and storing them in (strictly) increasing order.
    public init<S: Sequence>(_ elements: S) where S.Element == Element {
        var source = elements.makeIterator()
        var sink = ContiguousArray<Element>()
        sink.reserveCapacity(elements.underestimatedCount)
        if var previous = source.next() {
            var stillSorted = true
            sink.append(previous)
            while let element = source.next() {
                if stillSorted {
                    if previous < element {
                        // Add a new greater value.
                        previous = element
                        sink.append(element)
                        continue
                    } else if previous == element {
                        // Ignore runs of the current value.
                        continue
                    } else {
                        // Found a lesser value, so the sorted prefix has ended.
                        stillSorted = false

                        // Fall through to insert....
                    }
                }

                // Now insert via a binary search, if it's not already there.
                let equalRange = sink.indicesOfSorted(for: element)
                if equalRange.isEmpty {
                    sink.insert(element, at: equalRange.upperBound)
                }
            }
        }
        self.init(elements: sink[...])
    }

}

// MARK: - Text Representation

extension SortedSet: CustomDebugStringConvertible {

    @inlinable
    public var debugDescription: String {
        return String(describing: type(of: self)) + "(" + elements.lazy.map(String.init(describing:)).joined(separator: ", ") + ")"
    }

}

extension SortedSet: CustomStringConvertible {

    @inlinable
    public var description: String {
        return "[" + lazy.map(String.init(reflecting:)).joined(separator: ", ") + "]"
    }

}

// MARK: Comparisons

extension SortedSet: Equatable {

    @inlinable
    public static func == (lhs: Self, rhs: Self) -> Bool {
        return lhs.elements == rhs.elements
    }

}

extension SortedSet: Comparable {

    @inlinable
    public static func < (lhs: Self, rhs: Self) -> Bool {
        return lhs.elements.lexicographicallyPrecedes(rhs.elements)
    }

}

extension SortedSet: Hashable where Element: Hashable {

    @inlinable
    public func hash(into hasher: inout Hasher) {
        hasher.combine(elements)
    }

}

// MARK: - Sequence

extension SortedSet: Sequence {

    public struct Iterator: IteratorProtocol {
        /// An iterator from the implementation collection.
        @usableFromInline
        var elements: _Base.Iterator

        /// Creates an iterator from a given base one.
        @usableFromInline
        init(_ elements: _Base.Iterator) {
            self.elements = elements
        }

        @inlinable
        mutating public func next() -> Element? {
            return elements.next()
        }
    }

    @inlinable
    public __consuming func makeIterator() -> Iterator {
        return Iterator(elements.makeIterator())
    }

    @inlinable
    public var underestimatedCount: Int { return elements.underestimatedCount }

    @inlinable
    public func withContiguousStorageIfAvailable<R>(_ body: (UnsafeBufferPointer<Element>) throws -> R) rethrows -> R? {
        return try elements.withContiguousStorageIfAvailable(body)
    }

    // Secret implementations

    @inlinable
    public func _customContainsEquatableElement(_ element: Element) -> Bool? {
        return _customIndexOfEquatableElement(element).map { $0 != nil }
    }

    @inlinable
    __consuming public func _copyToContiguousArray() -> ContiguousArray<Element> {
        return elements._copyToContiguousArray()
    }

    @inlinable
    __consuming public func _copyContents(initializing ptr: UnsafeMutableBufferPointer<Element>) -> (Iterator,UnsafeMutableBufferPointer<Element>.Index) {
        let base = elements._copyContents(initializing: ptr)
        return (Iterator(base.0), base.1)
    }

}

extension SortedSet {

    /// Returns the minimum element in the set.
    ///
    /// - Returns: The set's smallest value, or `nil` if the set is empty.
    ///
    /// - Complexity: O(1).
    @inlinable
    public func min() -> Element? {
        return elements.first
    }

    /// Returns the maximum element in the set.
    ///
    /// - Returns: The set's largest value, or `nil` if the set is empty.
    ///
    /// - Complexity: O(1).
    @inlinable
    public func max() -> Element? {
        return elements.last
    }

    /// Returns the elements of the set, sorted.
    ///
    /// - Returns: A sorted set of the elements.
    ///
    /// - Complexity: O(1).
    @inlinable
    public func sorted() -> Self {
        return self
    }

}

// MARK: - Collection

extension SortedSet: Collection {

    public struct Index: Comparable, Hashable {
        /// An index from the implementation collection.
        @usableFromInline
        fileprivate(set) var index: _Base.Index

        /// Creates an index from a given base one.
        @usableFromInline
        init(_ index: _Base.Index) {
            self.index = index
        }

        // Use automatic Equatable and Hashable conformance.

        @inlinable
        public static func < (lhs: Self, rhs: Self) -> Bool {
            return lhs.index < rhs.index
        }
    }

    @inlinable
    public var startIndex: Index { return Index(elements.startIndex) }
    @inlinable
    public var endIndex: Index { return Index(elements.endIndex) }

    @inlinable
    public subscript(position: Index) -> Element {
        return elements[position.index]
    }
    @inlinable
    public subscript(bounds: Range<Index>) -> Self {
        return SortedSet(elements: elements[bounds.lowerBound.index ..< bounds.upperBound.index])
    }

    // Use the default-defined Indices and indices.

    @inlinable
    public var isEmpty: Bool { return elements.isEmpty }
    @inlinable
    public var count: Int { return elements.count }

    @inlinable
    public func index(_ i: Index, offsetBy distance: Int) -> Index {
        return Index(elements.index(i.index, offsetBy: distance))
    }
    @inlinable
    public func index(_ i: Index, offsetBy distance: Int, limitedBy limit: Index) -> Index? {
        return elements.index(i.index, offsetBy: distance, limitedBy: limit.index).map { Index($0) }
    }
    @inlinable
    public func distance(from start: Index, to end: Index) -> Int {
        return elements.distance(from: start.index, to: end.index)
    }

    @inlinable
    public func index(after i: Index) -> Index {
        return Index(elements.index(after: i.index))
    }
    public func formIndex(after i: inout Index) {
        elements.formIndex(after: &i.index)
    }

    // Secret implementations

    @inlinable
    public func _customIndexOfEquatableElement(_ element: Element) -> Index?? {
        let range = elements.indicesOfSorted(for: element)
        return .some(range.isEmpty ? .none : .some(Index(range.lowerBound)))
    }
    @inline(__always)
    public func _customLastIndexOfEquatableElement(_ element: Element) -> Index?? {
        // Elements are unique, so the first find is also the last.
        return _customIndexOfEquatableElement(element)
    }

    @inline(__always)
    public func _failEarlyRangeCheck(_ index: Index, bounds: Range<Index>) {
        elements._failEarlyRangeCheck(index.index, bounds: bounds.lowerBound.index ..< bounds.upperBound.index)
    }
    @inline(__always)
    public func _failEarlyRangeCheck(_ index: Index, bounds: ClosedRange<Index>) {
        elements._failEarlyRangeCheck(index.index, bounds: bounds.lowerBound.index ... bounds.upperBound.index)
    }
    @inline(__always)
    public func _failEarlyRangeCheck(_ range: Range<Index>, bounds: Range<Index>) {
        elements._failEarlyRangeCheck(range.lowerBound.index ..< range.upperBound.index, bounds: bounds.lowerBound.index ..< bounds.upperBound.index)
    }

}

extension SortedSet: BidirectionalCollection {

    @inlinable
    public func index(before i: Index) -> Index {
        return Index(elements.index(before: i.index))
    }
    public func formIndex(before i: inout Index) {
        elements.formIndex(before: &i.index)
    }

}

extension SortedSet: RandomAccessCollection {}

// MutableCollection isn't supported because rearrangements would break the
// sort, and arbitrary writes would most likely break the sort.

// RangeReplaceableCollection isn't supported because, while arbitrary removals
// wouldn't break the sort, arbitrary inserts or replacements would likely to.

// MARK: - Restricted RangeReplaceableCollection-like Interface

extension SortedSet {

    @inlinable
    public init() {
        self.init(EmptyCollection())
    }

    // Use the standard versions of the .popFirst and .popLast methods.

    /// Removes and returns the element at the specified position.
    @discardableResult
    public mutating func remove(at position: Index) -> Element {
        elements.remove(at: position.index)
    }

    /// Removes all elements from the collection.
    public mutating func removeAll(keepingCapacity keepCapacity: Bool = false) {
        elements.removeAll(keepingCapacity: keepCapacity)
    }

    /// Removes all the elements that satisfy the given predicate.
    public mutating func removeAll(where shouldBeRemoved: (Element) throws -> Bool) rethrows {
        try elements.removeAll(where: shouldBeRemoved)
    }

    // Use the standard versions of the .removeFirst and .removeLast methods.

    /// Removes the specified subrange of elements from the collection.
    public mutating func removeSubrange(_ bounds: Range<Index>) {
        elements.removeSubrange(bounds.lowerBound.index ..< bounds.upperBound.index)
    }

    /// Removes the elements in the specified subrange from the collection.
    public mutating func removeSubrange<R: RangeExpression>(_ bounds: R) where R.Bound == Index {
        let adjustedBounds = bounds.relative(to: self)
        elements.removeSubrange(adjustedBounds.lowerBound.index ..< adjustedBounds.upperBound.index)
    }

    /// Prepares the collection to store the specified number of elements, when
    /// doing so is appropriate for the underlying type.
    public mutating func reserveCapacity(_ n: Int) {
        elements.reserveCapacity(n)
    }

    /// The total number of elements that the array can contain without
    /// allocating new storage.
    @inlinable
    public var capacity: Int {
        return elements.capacity
    }

}

extension SortedSet {

    /// Returns a new set containing the elements of the set that satisfy the
    /// given predicate.
    public __consuming func filter(_ isIncluded: (Element) throws -> Bool) rethrows -> Self {
        var filteredElements = ContiguousArray<Element>()
        filteredElements.reserveCapacity(elements.underestimatedCount)
        for element in elements {
            if try isIncluded(element) {
                filteredElements.append(element)
            }
        }
        return SortedSet(elements: filteredElements[...])
    }

}

// MARK: - Set Algebra

extension SortedSet: SetAlgebra {

    // .init() in RRC-lite extension.

    // The Sequence.contains(_:) extension method satisfies the requirements.

    // Element is a generic parameter.

    @discardableResult
    public mutating func insert(_ newMember: __owned Element) -> (inserted: Bool, memberAfterInsert: Element) {
        let range = elements.indicesOfSorted(for: newMember)
        if range.isEmpty {
            elements.insert(newMember, at: range.upperBound)
            return (true, newMember)
        } else {
            return (false, elements[range.lowerBound])
        }
    }

    @discardableResult
    public mutating func update(with newMember: __owned Element) -> Element? {
        let range = elements.indicesOfSorted(for: newMember)
        if range.isEmpty {
            elements.insert(newMember, at: range.upperBound)
            return nil
        } else {
            defer { elements[range.lowerBound] = newMember }
            return elements[range.lowerBound]
        }
    }

    @inlinable
    @discardableResult
    public mutating func remove(_ member: Element) -> Element? {
        return firstIndex(of: member).map { remove(at: $0) }
    }

    @inlinable
    public __consuming func union(_ other: __owned Self) -> Self {
        return SortedSet(elements.lazy.applySetOperation(.union, with: other.elements))
    }

    public mutating func formUnion(_ other: __owned Self) {
        elements[...] = union(other).elements
    }

    @inlinable
    public __consuming func intersection(_ other: Self) -> Self {
        return SortedSet(elements.lazy.applySetOperation(.intersection, with: other.elements))
    }

    public mutating func formIntersection(_ other: Self) {
        elements[...] = intersection(other).elements
    }

    @inlinable
    public __consuming func symmetricDifference(_ other: __owned Self) -> Self {
        return SortedSet(elements.lazy.applySetOperation(.symmetricDifference, with: other.elements))
    }

    public mutating func formSymmetricDifference(_ other: __owned Self) {
        elements[...] = symmetricDifference(other).elements
    }

    @inlinable
    public func isStrictSubset(of other: Self) -> Bool {
        let stats = elements.setStatistics(combiningWith: other.elements)
        return stats.receiver == 0 && stats.other > 0
    }

    @inlinable
    public func isStrictSuperset(of other: Self) -> Bool {
        let stats = elements.setStatistics(combiningWith: other.elements)
        return stats.receiver > 0 && stats.other == 0
    }

    // .init<S>(_:) in primary definition.

    // .isEmpty in Collection extension.

    @inlinable
    public func isDisjoint(with other: Self) -> Bool {
        let stats = elements.setStatistics(combiningWith: other.elements)
        return stats.shared == 0
    }

    @inlinable
    public func isSubset(of other: Self) -> Bool {
        let stats = elements.setStatistics(combiningWith: other.elements)
        return stats.receiver == 0
    }

    @inlinable
    public func isSuperset(of other: Self) -> Bool {
        let stats = elements.setStatistics(combiningWith: other.elements)
        return stats.other == 0
    }

    public mutating func subtract(_ other: Self) {
        elements[...] = subtracting(other).elements
    }

    @inlinable
    public func subtracting(_ other: Self) -> Self {
        return SortedSet(elements.lazy.applySetOperation(.exclusivelyFirst, with: other.elements))
    }

    // Equatable conformance already defined in a previous extension.

    // ExpressibleByArrayLiteral conformance default-defined.

}

extension SortedSet {

    /// Returns a new set with the elements of both this set and the given
    /// sequence.
    @inlinable
    public __consuming func union<S: Sequence>(_ other: __owned S) -> Self where S.Element == Element {
        return SortedSet(elements.lazy.applySetOperation(.union, with: other.sorted().lazy.debounced()))
    }

    /// Adds the elements of the given sequence to the set.
    public mutating func formUnion<S: Sequence>(_ other: __owned S) where S.Element == Element {
        elements[...] = union(other).elements
    }

    /// Returns a new set with the elements that are common to both this set and
    /// the given sequence.
    @inlinable
    public __consuming func intersection<S: Sequence>(_ other: S) -> Self where S.Element == Element {
        return SortedSet(elements.lazy.applySetOperation(.intersection, with: other.sorted().lazy.debounced()))
    }

    /// Removes the elements of this set that aren’t also in the given sequence.
    public mutating func formIntersection<S: Sequence>(_ other: S) where S.Element == Element {
        elements[...] = intersection(other).elements
    }

    /// Returns a new set with the elements that are either in this set or in
    /// the given sequence, but not in both.
    @inlinable
    public __consuming func symmetricDifference<S: Sequence>(_ other: __owned S) -> Self where S.Element == Element {
        return SortedSet(elements.lazy.applySetOperation(.symmetricDifference, with: other.sorted().lazy.debounced()))
    }

    /// Removes the elements of the set that are also in the given sequence and
    /// adds the members of that sequence not already in the set.
    public mutating func formSymmetricDifference<S: Sequence>(_ other: __owned S) where S.Element == Element {
        elements[...] = symmetricDifference(other).elements
    }

    /// Returns a Boolean value that indicates whether the set is a strict
    /// subset of the given sequence.
    @inlinable
    public func isStrictSubset<S: Sequence>(of other: S) -> Bool where S.Element == Element {
        let stats = elements.setStatistics(combiningWith: other.sorted().lazy.debounced())
        return stats.receiver == 0 && stats.other > 0
    }

    /// Returns a Boolean value that indicates whether the set is a strict
    /// superset of the given sequence.
    @inlinable
    public func isStrictSuperset<S: Sequence>(of other: S) -> Bool where S.Element == Element {
        let stats = elements.setStatistics(combiningWith: other.sorted().lazy.debounced())
        return stats.receiver > 0 && stats.other == 0
    }

    /// Returns a Boolean value that indicates whether the set has no members in
    /// common with the given sequence.
    @inlinable
    public func isDisjoint<S: Sequence>(with other: S) -> Bool where S.Element == Element {
        let stats = elements.setStatistics(combiningWith: other.sorted().lazy.debounced())
        return stats.shared == 0
    }

    /// Returns a Boolean value that indicates whether the set is a subset of
    /// the given sequence.
    @inlinable
    public func isSubset<S: Sequence>(of other: S) -> Bool where S.Element == Element {
        let stats = elements.setStatistics(combiningWith: other.sorted().lazy.debounced())
        return stats.receiver == 0
    }

    /// Returns a Boolean value that indicates whether the set is a superset of
    /// the given sequence.
    @inlinable
    public func isSuperset<S: Sequence>(of other: S) -> Bool where S.Element == Element {
        let stats = elements.setStatistics(combiningWith: other.sorted().lazy.debounced())
        return stats.other == 0
    }

    /// Removes the elements of the given sequence from this set.
    public mutating func subtract<S: Sequence>(_ other: S) where S.Element == Element {
        elements[...] = subtracting(other).elements
    }

    /// Returns a new set containing the elements of this set that do not occur
    /// in the given sequence.
    @inlinable
    public func subtracting<S: Sequence>(_ other: S) -> Self where S.Element == Element {
        return SortedSet(elements.lazy.applySetOperation(.exclusivelyFirst, with: other.sorted().lazy.debounced()))
    }

    // QUERY: Would converting the other sequences to a SortedSet first be
    // faster than using .sorted().lazy.debounced() on them instead?

}

extension SortedSet {

    /// Creates a new set that forms a union of the elements of the sets.
    @inlinable
    public static func + (lhs: Self, rhs: Self) -> Self {
        return lhs.union(rhs)
    }

    /// Adds the elements of the second set to the first.
    @inlinable
    public static func += (lhs: inout Self, rhs: Self) {
        lhs.formUnion(rhs)
    }

    /// Adds the elements of the sequence to the set.
    @inlinable
    public static func += <S: Sequence>(lhs: inout Self, rhs: S) where S.Element == Element {
        lhs.formUnion(rhs)
    }

    /// Creates a new set that subtracts the elements of the second set from the
    /// first.
    @inlinable
    public static func - (lhs: Self, rhs: Self) -> Self {
        return lhs.subtracting(rhs)
    }

    /// Removes the elements of the second set from the first.
    @inlinable
    public static func -= (lhs: inout Self, rhs: Self) {
        lhs.subtract(rhs)
    }

    /// Removes the elements of the sequence from the set.
    @inlinable
    public static func -= <S: Sequence>(lhs: inout Self, rhs: S) where S.Element == Element {
        lhs.subtract(rhs)
    }

}

Thanks for sharing, I really miss SortedSet in the Standard Library. Once tried to adopt NSOrderedSet from Foundation, but it’s ‘typeless’ in Swift which makes it almost unusable.