Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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
// 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
// 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
// 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
// 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
//
// 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)
}
}
@shpakovski

This comment has been minimized.

Copy link

shpakovski commented Aug 23, 2019

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.