Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Merging, Combining, and Testing of Sorted Sequences in Swift, inspired by the C++ Standard Library. See <https://forums.swift.org/t/sorted-sequence-operations-merge-sort-set-operations-inclusion-testing/31145> for more information.
// MARK: Per-Element Sharing in Merged Sorted Sequences
/// Primary source categories when merging two sets together.
public enum MergedSetElementSource<Element> {
/// The given element is only in the first set.
case exclusivelyFirst(Element)
/// The element is in both sets. Both versions are given.
case shared(Element, Element)
/// The given element is only in the second set.
case exclusivelySecond(Element)
}
// MARK: - Eager Merger of Sorted Sequences
extension Sequence {
/// Assuming this sequence is sorted according to the given predicate
/// comparing elements, and the given sequence is sorted the same way,
/// process the virtual set-merger of the two sequences with the other given
/// closure.
///
/// `areInIncreasingOrder` must be a strict weak ordering over the elements.
///
/// Relative to elements from the same source sequence, the resulting
/// virtual sequence sorts stably.
///
/// - Precondition: Both this sequence and `other` are finite, and they are
/// both sorted according to `areInIncreaasingOrder`.
///
/// - Parameter other: A sequence to blend with this one.
/// - Parameter body: A closure processing each element of both sequences.
/// Each call indicates if an element value is in only one sequence or in
/// both. If a value is duplicated in a sequence, a call will be made for
/// each copy.
/// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
/// first argument should be ordered before its second argument;
/// otherwise, `false`.
///
/// - Complexity: O(*n* + *m*), where *n* and *m* are the lengths of this
/// sequence and `other`.
public func whileMergingSorted<S: Sequence>(with other: S, do body: (MergedSetElementSource<Element>) throws -> Void, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows where S.Element == Element {
var iterator = makeIterator(), otherIterator = other.makeIterator()
var cache = iterator.next(), otherCache = otherIterator.next()
while let current = cache, let otherCurrent = otherCache {
if try areInIncreasingOrder(current, otherCurrent) {
try body(.exclusivelyFirst(current))
cache = iterator.next()
} else if try areInIncreasingOrder(otherCurrent, current) {
try body(.exclusivelySecond(otherCurrent))
otherCache = otherIterator.next()
} else {
try body(.shared(current, otherCurrent))
cache = iterator.next()
otherCache = otherIterator.next()
}
}
if let firstSuffix = cache {
assert(otherCache == nil)
try body(.exclusivelyFirst(firstSuffix))
while let suffix = iterator.next() {
try body(.exclusivelyFirst(suffix))
}
} else if let firstOtherSuffix = otherCache {
try body(.exclusivelySecond(firstOtherSuffix))
while let suffix = otherIterator.next() {
try body(.exclusivelySecond(suffix))
}
}
}
}
// MARK: - Merger of Sorted Sequences, Iterator
/// An iterator blending two iterators' sorted sequences together.
public struct MergingSortedIterator<Base1: IteratorProtocol, Base2: IteratorProtocol> where Base1.Element == Base2.Element {
/// The first source iterator.
var iterator1: Base1
/// The second source iterator.
var iterator2: Base2
/// The ordering predicate.
let areInIncreasingOrder: (Base1.Element, Base2.Element) -> Bool
/// The last element read from `iterator1`.
var cache1: Base1.Element?
/// The last element read from `iterator2`.
var cache2: Base2.Element?
/// Creates a blend of the sorted source iterators into an also-sorted
/// iterator.
@usableFromInline
init(merging first: Base1, and second: Base2, by areInIncreasingOrder: @escaping (Base1.Element, Base2.Element) -> Bool) {
iterator1 = first
iterator2 = second
self.areInIncreasingOrder = areInIncreasingOrder
}
}
extension MergingSortedIterator: IteratorProtocol {
public mutating func next() -> MergedSetElementSource<Base1.Element>? {
if cache1 == nil {
cache1 = iterator1.next()
}
if cache2 == nil {
cache2 = iterator2.next()
}
switch (cache1, cache2) {
case (nil, nil):
return nil
case (let first?, nil):
defer { cache1 = nil }
return .exclusivelyFirst(first)
case (nil, let second?):
defer { cache2 = nil }
return .exclusivelySecond(second)
case let (first?, second?):
if areInIncreasingOrder(first, second) {
defer { cache1 = nil }
return .exclusivelyFirst(first)
} else if areInIncreasingOrder(second, first) {
defer { cache2 = nil }
return .exclusivelySecond(second)
} else {
defer {
cache1 = nil
cache2 = nil
}
return .shared(first, second)
}
}
}
}
// MARK: - Lazy Merger of Sorted Sequences
/// A sequence blending two sorted sequences together.
///
/// An instance is finite only when both source sequences are. It is multi-pass
/// only when both source sequences are. It is also a collection only when both
/// sources are also collections. (An instance can be at most a forward-only,
/// non-mutable collection, even when the sources' common refinement is past
/// `Collection`.)
public struct MergedSortedSequence<Base1: Sequence, Base2: Sequence> where Base1.Element == Base2.Element {
/// The first source sequence.
@usableFromInline
let sequence1: Base1
/// The second source sequence.
@usableFromInline
let sequence2: Base2
/// The ordering predicate.
@usableFromInline
let areInIncreasingOrder: (Base1.Element, Base2.Element) -> Bool
/// Creates a sorted sequence that is a blend of the two given sequences
/// that are both sorted according to the given predicate.
///
/// `areInIncreasingOrder` must be a strict weak ordering over the elements.
///
/// Relative to elements from the same source sequence, this sequence sorts
/// stably.
///
/// - Precondition: Both `first` and `second` are sorted along
/// `areInIncreasingOrder`.
///
/// - Parameter first: The first source sequence.
/// - Parameter second: The second source sequence.
/// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
/// first argument should be ordered before its second argument;
/// otherwise, `false`.
///
/// - Postcondition: Each turn, this sequence will vend the lowest-ordered
/// available element between the two source sequences. A tag will
/// accompany the element value indicating which source sequence it came
/// from. When the two currently available elements are equivalent, then
/// both are extracted and returned with a tag indicating a tie.
@inlinable
public init(merging first: Base1, and second: Base2, by areInIncreasingOrder: @escaping (Base1.Element, Base2.Element) -> Bool) {
sequence1 = first
sequence2 = second
self.areInIncreasingOrder = areInIncreasingOrder
}
}
extension MergedSortedSequence where Base1.Element: Comparable {
/// Creates a sorted sequence that is a blend of the two given sorted
/// sequences.
///
/// Relative to elements from the same source sequence, this sequence sorts
/// stably.
///
/// - Precondition: Both `first` and `second` are sorted.
///
/// - Parameter first: The first source sequence.
/// - Parameter second: The second source sequence.
///
/// - Postcondition: Each turn, this sequence will vend the minimum
/// available element between the two source sequences. A tag will
/// accompany the element value indicating which source sequence it came
/// from. When the two currently available elements are equal, then both
/// both are extracted and returned with a tag indicating a tie.
@inlinable
public init(merging first: Base1, and second: Base2) {
self.init(merging: first, and: second, by: <)
}
}
extension MergedSortedSequence: Sequence {
public typealias Iterator = MergingSortedIterator<Base1.Iterator, Base2.Iterator>
public typealias Element = Iterator.Element
@inlinable
public func makeIterator() -> Iterator {
return MergingSortedIterator(merging: sequence1.makeIterator(), and: sequence2.makeIterator(), by: areInIncreasingOrder)
}
@inlinable
public var underestimatedCount: Int
{ Swift.max(sequence1.underestimatedCount, sequence2.underestimatedCount) }
}
extension MergedSortedSequence: LazySequenceProtocol {}
// MARK: - Support for Merged Collections
/// An index type for `MergedSortedCollection`.
public struct MergedSortedIndex<Base1: Comparable, Base2: Comparable> {
/// The index into the first collection.
let first: Base1
/// The index into the second collection.
let second: Base2
/// Whether to dereference `first`.
let dereferenceFirst: Bool
/// Whether to dereference `second`.
let dereferenceSecond: Bool
/// Creates an index from the two given indices and whether
/// to use either or both for dereferencing.
@usableFromInline
init(first: Base1, second: Base2, dereferenceFirst: Bool, dereferenceSecond: Bool) {
self.first = first
self.second = second
self.dereferenceFirst = dereferenceFirst
self.dereferenceSecond = dereferenceSecond
}
}
extension MergedSortedIndex: Equatable {}
extension MergedSortedIndex: Hashable where Base1: Hashable, Base2: Hashable {}
extension MergedSortedIndex: Comparable {
public static func < (lhs: Self, rhs: Self) -> Bool {
let less1 = lhs.first < rhs.first || lhs.first == rhs.first && !lhs.dereferenceFirst && rhs.dereferenceFirst
let equal1 = lhs.first == rhs.first && lhs.dereferenceFirst == rhs.dereferenceFirst
let less2 = lhs.second < rhs.second || lhs.second == rhs.second && !lhs.dereferenceSecond && rhs.dereferenceSecond
let equal2 = lhs.second == rhs.second && lhs.dereferenceSecond == rhs.dereferenceSecond
return less1 && less2 || equal1 && less2 || less1 && equal2
}
}
// MARK: Merged Collection of Sorted Collections
/// A collection blending two sorted collections together.
public typealias MergedSortedCollection<T: Collection, U: Collection> = MergedSortedSequence<T, U> where T.Element == U.Element
extension MergedSortedCollection: Collection {
public typealias Index = MergedSortedIndex<Base1.Index, Base2.Index>
public var startIndex: Index {
if let first1 = sequence1.first, let first2 = sequence2.first {
let willDereference1 = !areInIncreasingOrder(first2, first1)
let willDereference2 = !areInIncreasingOrder(first1, first2)
return Index(first: sequence1.startIndex, second: sequence2.startIndex, dereferenceFirst: willDereference1, dereferenceSecond: willDereference2)
} else {
return Index(first: sequence1.startIndex, second: sequence2.startIndex, dereferenceFirst: !sequence1.isEmpty, dereferenceSecond: !sequence2.isEmpty)
}
}
@inlinable
public var endIndex: Index {
Index(first: sequence1.endIndex, second: sequence2.endIndex, dereferenceFirst: false, dereferenceSecond: false)
}
public subscript(position: Index) -> Element {
switch (position.dereferenceFirst, position.dereferenceSecond) {
case (false, false):
assert(position.first == sequence1.endIndex)
assert(position.second == sequence2.endIndex)
preconditionFailure("Attempt to dereference endIndex")
case (false, true):
return .exclusivelySecond(sequence2[position.second])
case (true, false):
return .exclusivelyFirst(sequence1[position.first])
case (true, true):
return .shared(sequence1[position.first], sequence2[position.second])
}
}
public func index(after i: Index) -> Index {
let end1 = sequence1.endIndex, end2 = sequence2.endIndex
switch (i.first < end1, i.second < end2) {
case (false, false):
assert(!i.dereferenceFirst)
assert(!i.dereferenceSecond)
preconditionFailure("Attempt to increment past endIndex")
case (false, true):
assert(!i.dereferenceFirst)
assert(i.dereferenceSecond)
let afterSecond = sequence2.index(after: i.second)
return Index(first: i.first, second: afterSecond, dereferenceFirst: false, dereferenceSecond: afterSecond < end2)
case (true, false):
assert(i.dereferenceFirst)
assert(!i.dereferenceSecond)
let afterFirst = sequence1.index(after: i.first)
return Index(first: afterFirst, second: i.second, dereferenceFirst: afterFirst < end1, dereferenceSecond: false)
case (true, true):
assert(i.dereferenceFirst || i.dereferenceSecond)
let nextFirst = sequence1.index(i.first, offsetBy: i.dereferenceFirst ? +1 : 0)
let nextSecond = sequence2.index(i.second, offsetBy: i.dereferenceSecond ? +1 : 0)
let couldDereference1 = nextFirst < end1
let couldDereference2 = nextSecond < end2
if couldDereference1, couldDereference2 {
let next1 = sequence1[nextFirst], next2 = sequence2[nextSecond]
let willDereference1 = !areInIncreasingOrder(next2, next1)
let willDereference2 = !areInIncreasingOrder(next1, next2)
return Index(first: nextFirst, second: nextSecond, dereferenceFirst: willDereference1, dereferenceSecond: willDereference2)
} else {
return Index(first: nextFirst, second: nextSecond, dereferenceFirst: couldDereference1, dereferenceSecond: couldDereference2)
}
}
}
}
extension MergedSortedCollection: LazyCollectionProtocol {}
// MARK: - Overlap Detection in Merged Sorted Sequences
/// Degree of overlap when merging two sets together.
public enum TwoSetOverlap: UInt, CaseIterable {
/// Neither set has any elements.
case bothEmpty
/// Only the second set has any elements.
case onlyFirstEmpty
/// Both sets have elements, all shared.
case total
/// The first set has elements; the second has those and at least one more.
case secondExtendsFirst
/// Only the first set has any elements.
case onlySecondEmpty
/// Both sets have elements, but none in common.
case disjoint
/// The second set has elements; the first has those and at least one more.
case firstExtendsSecond
/// Both sets have elements, but only some in common.
case partial
/// Whether there is at least one element exclusive to the second set.
@inlinable
public var hasExclusivesToSecond: Bool { rawValue & 0x01 != 0 }
/// Whether there is at least one element that is in both sets.
@inlinable
public var hasSomeOverlap: Bool { rawValue & 0x02 != 0 }
/// Whether there is at least one element exclusive to the first set.
@inlinable
public var hasExclusivesToFirst: Bool { rawValue & 0x04 != 0 }
/// Creates an overlap pack representing the given combination of flags.
@inlinable
public init(hasExclusivesToFirst firstOnly: Bool, hasSomeOverlap overlap: Bool, hasExclusivesToSecond secondOnly: Bool) {
self.init(rawValue: (firstOnly ? 0x04 : 0) | (overlap ? 0x02 : 0) | (secondOnly ? 0x01 : 0))!
}
/// Whether the sets equal, *i.e.* no exclusives.
@inlinable
public var areEqual: Bool { rawValue & 0x05 == 0 }
/// Whether the first set has at least one element.
@inlinable
public var isFirstEmpty: Bool { rawValue & 0x06 == 0 }
/// Whether the second set has at least one element.
@inlinable
public var isSecondEmpty: Bool { rawValue & 0x03 == 0 }
/// Whether the first set has all the elements of the second.
@inlinable
public var firstIsSupersetOfSecond: Bool { !hasExclusivesToSecond }
/// Whether the second set has all the elements of the first.
@inlinable
public var firstIsSubsetOfSecond: Bool { !hasExclusivesToFirst }
/// Whether the first set has all the elements of the second, and then some.
@inlinable
public var firstIsStrictSupersetOfSecond: Bool { rawValue & 0x05 == 0x04 }
/// Whether the second set has all the elements of the first, and then some.
@inlinable
public var firstIsStrictSubsetOfSecond: Bool { rawValue & 0x05 == 0x01 }
}
/// An error for the internals of `Sequence.whileMergingSortedConfirmFor(selfOnly: shared: otherOnly: mergingWith: by:)`.
fileprivate enum ConfirmationFail: Error {
/// An element was found that was not supposed to be there.
case failed
}
extension Sequence {
/// Assuming this sequence is sorted according to the given predicate
/// comparing elements, and the given sequence is sorted the same way,
/// count how many elements are shared or not shared between sequences.
///
/// `areInIncreasingOrder` must be a strict weak ordering over the elements.
///
/// - Precondition: Both this sequence and `other` are finite, and they are
/// both sorted according to `areInIncreaasingOrder`.
///
/// - Parameter other: A sequence to blend with this one.
/// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
/// first argument should be ordered before its second argument;
/// otherwise, `false`.
/// - Returns: A tuple containing how many elements are exclusive to this
/// sequence, how many are shared, and how many are exclusive to `other`.
///
/// - Complexity: O(*n* + *m*), where *n* and *m* are the lengths of this
/// sequence and `other`.
public func sourceCountWhileMergingSorted<S: Sequence>(with other: S, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> (selfOnly: Int, shared: Int, otherOnly: Int) where S.Element == Element {
var (selfCount, sharedCount, otherCount) = (0, 0, 0)
try whileMergingSorted(with: other, do: {
switch $0 {
case .exclusivelyFirst:
selfCount += 1
case .shared:
sharedCount += 1
case .exclusivelySecond:
otherCount += 1
}
}, by: areInIncreasingOrder)
return (selfOnly: selfCount, shared: sharedCount, otherOnly: otherCount)
}
/// Assuming this sequence is sorted according to the given predicate
/// comparing elements, and the given sequence is sorted the same way,
/// confirm if the distribution of the sources of elements matches the given
/// desired outcome.
///
/// `areInIncreasingOrder` must be a strict weak ordering over the elements.
///
/// - Precondition: Both this sequence and `other` are finite, and they are
/// both sorted according to `areInIncreaasingOrder`.
///
/// - Parameter selfOnly: Whether elements exclusive to this sequence were
/// present. Use `true` to confirm at least one element was present, use
/// `false` to confirm their absence instead, or `nil` if you don't care.
/// - Parameter shared: Whether elements shared between the sequences were
/// present. Use `true` to confirm at least one element was present, use
/// `false` to confirm their absence, or `nil` if you don't care.
/// - Parameter otherOnly: Whether elements exclusive to `other` were
/// present. Use `true` to confirm at least one element was present, use
/// `false` to confirm their absence instead, or `nil` if you don't care.
/// - Parameter other: A sequence to blend with this one.
/// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
/// first argument should be ordered before its second argument;
/// otherwise, `false`.
/// - Returns: `true` if the desired outcome matches; otherwise, `false`.
///
/// - Complexity: O(*n* + *m*) if at least one desired outcome was `true`,
/// O(1) if all outcomes were `nil`, and something in between otherwise;
/// where *n* and *m* are the lengths of this sequence and `other`.
public func whileMergingSortedConfirmFor<S: Sequence>(selfOnly: Bool?, shared: Bool?, otherOnly: Bool?, mergingWith other: S, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> Bool where S.Element == Element {
guard selfOnly != nil || shared != nil || otherOnly != nil else {
return true
}
var foundSelfOnly = false, foundShared = false, foundOtherOnly = false
do {
try whileMergingSorted(with: other, do: {
switch ($0, selfOnly, shared, otherOnly) {
case (.exclusivelyFirst, true, _, _):
foundSelfOnly = true
case (.shared, _, true, _):
foundShared = true
case (.exclusivelySecond, _, _, true):
foundOtherOnly = true
case (.exclusivelyFirst, false, _, _), (.shared, _, false, _),
(.exclusivelySecond, _, _, false):
throw ConfirmationFail.failed
default:
break
}
}, by: areInIncreasingOrder)
} catch is ConfirmationFail {
return false
}
if selfOnly == true && !foundSelfOnly
|| shared == true && !foundShared
|| otherOnly == true && !foundOtherOnly {
return false
}
return true
}
/// Assuming this sequence is sorted according to the given predicate
/// comparing elements, and the given sequence is sorted the same way,
/// determine how the sequences would overlap.
///
/// `areInIncreasingOrder` must be a strict weak ordering over the elements.
///
/// - Precondition: Both this sequence and `other` are finite, and they are
/// both sorted according to `areInIncreaasingOrder`.
///
/// - Parameter other: A sequence to blend with this one.
/// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
/// first argument should be ordered before its second argument;
/// otherwise, `false`.
/// - Returns: A set of flags indicating the degree of overlap between the
/// sequences. The first sequence referenced in the flags is this
/// sequence, and the second sequence referenced to is `other`.
///
/// - Complexity: O(*n* + *m*), where *n* and *m* are the lengths of this
/// sequence and `other`.
public func overlapIfMergedSorted<S: Sequence>(with other: S, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> TwoSetOverlap where S.Element == Element {
var haveExclusivesToFirst = false, haveExclusivesToSecond = false
var haveSharedElements = false
try whileMergingSorted(with: other, do: {
switch $0 {
case .exclusivelyFirst:
haveExclusivesToFirst = true
case .shared:
haveSharedElements = true
case .exclusivelySecond:
haveExclusivesToSecond = true
}
}, by: areInIncreasingOrder)
return TwoSetOverlap(hasExclusivesToFirst: haveExclusivesToFirst, hasSomeOverlap: haveSharedElements, hasExclusivesToSecond: haveExclusivesToSecond)
}
}
extension Sequence where Element: Comparable {
/// Assuming this sequence and the given sequence are both sorted, count how
/// many elements are shared or not shared between sequences.
///
/// - Precondition: Both this sequence and `other` are finite and sorted.
///
/// - Parameter other: A sequence to blend with this one.
/// - Returns: A tuple containing how many elements are exclusive to this
/// sequence, how many are shared, and how many are exclusive to `other`.
///
/// - Complexity: O(*n* + *m*), where *n* and *m* are the lengths of this
/// sequence and `other`.
@inlinable
public func sourceCountWhileMergingSorted<S: Sequence>(with other: S) -> (selfOnly: Int, shared: Int, otherOnly: Int) where S.Element == Element {
return sourceCountWhileMergingSorted(with: other, by: <)
}
/// Assuming this sequence and the given sequence are both sorted, confirm
/// if the distribution of the sources of elements matches the given desired
/// outcome.
///
/// - Precondition: Both this sequence and `other` are finite and sorted.
///
/// - Parameter selfOnly: Whether elements exclusive to this sequence were
/// present. Use `true` to confirm at least one element was present, use
/// `false` to confirm their absence instead, or `nil` if you don't care.
/// - Parameter shared: Whether elements shared between the sequences were
/// present. Use `true` to confirm at least one element was present, use
/// `false` to confirm their absence, or `nil` if you don't care.
/// - Parameter otherOnly: Whether elements exclusive to `other` were
/// present. Use `true` to confirm at least one element was present, use
/// `false` to confirm their absence instead, or `nil` if you don't care.
/// - Parameter other: A sequence to blend with this one.
/// - Returns: `true` if the desired outcome matches; otherwise, `false`.
///
/// - Complexity: O(*n* + *m*) if at least one desired outcome was `true`,
/// O(1) if all outcomes were `nil`, and something in between otherwise;
/// where *n* and *m* are the lengths of this sequence and `other`.
@inlinable
public func whileMergingSortedConfirmFor<S: Sequence>(selfOnly: Bool?, shared: Bool?, otherOnly: Bool?, mergingWith other: S) -> Bool where S.Element == Element {
return whileMergingSortedConfirmFor(selfOnly: selfOnly, shared: shared, otherOnly: otherOnly, mergingWith: other, by: <)
}
/// Assuming this sequence and the given one are both sorted, determine how
/// the sequences would overlap.
///
/// - Precondition: Both this sequence and `other` are finite and sorted.
///
/// - Parameter other: A sequence to blend with this one.
/// - Returns: A set of flags indicating the degree of overlap between the
/// sequences. The first sequence referenced in the flags is this
/// sequence, and the second sequence referenced to is `other`.
///
/// - Complexity: O(*n* + *m*), where *n* and *m* are the lengths of this
/// sequence and `other`.
@inlinable
public func overlapIfMergedSorted<S: Sequence>(with other: S) -> TwoSetOverlap where S.Element == Element {
return overlapIfMergedSorted(with: other, by: <)
}
}
// MARK: Ways to Combine 2 Sets
/// Operations to combine two sets.
public enum SetOperation: UInt, CaseIterable {
/// Exclude all elements.
case none
/// Include elements that are only in the second set.
case exclusivesFromSecond
/// Include elements that are present in both sets.
case intersection
/// Include all elements from the second set.
case anyFromSecond
/// Include elements that are only in the first set.
case exclusivesFromFirst
/// Include all elements that are only in exactly one set.
case symmetricDifference
/// Include all elements from the first set.
case anyFromFirst
/// Include all elements.
case union
/// Whether elements that are only in the second set are included.
@inlinable
public var hasExclusivesFromSecond: Bool { rawValue & 0x01 != 0 }
/// Whether elements shared in both sets are included.
@inlinable
public var hasNonExclusives: Bool { rawValue & 0x02 != 0 }
/// Whether elements that are only in the first set are included.
@inlinable
public var hasExclusivesFromFirst: Bool { rawValue & 0x04 != 0 }
}
// MARK: - Eager Set Operations on Sorted Sequences
extension Sequence {
/// Assuming this sequence is sorted according to the given predicate
/// comparing elements, and the given sequence is sorted the same way,
/// return a sorted collection consisting of the two sequences blended
/// together as sets, keeping only the elements indicated by the given
/// operation.
///
/// `areInIncreasingOrder` must be a strict weak ordering over the elements.
///
/// The sort is stable.
///
/// - Precondition: Both this sequence and `other` are finite, and are both
/// sorted according to `areInIncreasingOrder`.
///
/// - Parameter other: A sequence to blend with this one.
/// - Parameter filter: The set operation (union, intersection, *etc.*) to
/// apply to the merger.
/// - Parameter type: A meta-type specifier for the collection to return.
/// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
/// first argument should be ordered before its second argument;
/// otherwise, `false`.
/// - Returns: A collection of the given type containing the elements of
/// this sequence and `other` in a way that maintains the sort determined
/// by `areInIncreasingOrder`. For each value that exists in both sets,
/// only one copy is kept. (Usually the one from this sequence is kept,
/// unless `filter == anyFromSecond`.)
///
/// - Complexity: O(*n* + *m*), where *n* and *m* are the lengths of this
/// sequence and `other`.
public func mergeSortedAsSets<S: Sequence, T: RangeReplaceableCollection>(with other: S, keeping filter: SetOperation, into type: T.Type, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> T where S.Element == Element, T.Element == Element {
var result = T()
let breakTiesWithFirst = filter != .anyFromSecond
result.reserveCapacity(Swift.max(underestimatedCount, other.underestimatedCount))
try whileMergingSorted(with: other, do: {
switch $0 {
case .exclusivelyFirst(let first) where filter.hasExclusivesFromFirst:
result.append(first)
case let .shared(first, second) where filter.hasNonExclusives:
result.append(breakTiesWithFirst ? first : second)
case .exclusivelySecond(let second) where filter.hasExclusivesFromSecond:
result.append(second)
default:
break
}
}, by: areInIncreasingOrder)
return result
}
/// Assuming this sequence is sorted according to the given predicate
/// comparing elements, and the given sequence is sorted the same way,
/// return a sorted array consisting of the two sequences blended together
/// as sets, keeping only the elements indicated by the given operation.
///
/// `areInIncreasingOrder` must be a strict weak ordering over the elements.
///
/// The sort is stable.
///
/// - Precondition: Both this sequence and `other` are finite, and are both
/// sorted according to `areInIncreasingOrder`.
///
/// - Parameter other: A sequence to blend with this one.
/// - Parameter filter: The set operation (union, intersection, *etc.*) to
/// apply to the merger.
/// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
/// first argument should be ordered before its second argument;
/// otherwise, `false`.
/// - Returns: An array containing the elements of this sequence and `other`
/// in a way that maintains the sort determined by `areInIncreasingOrder`.
/// For each value that exists in both sets, only one copy is kept.
/// (Usually the one from this sequence is kept, unless
/// `filter == anyFromSecond`.)
///
/// - Complexity: O(*n* + *m*), where *n* and *m* are the lengths of this
/// sequence and `other`.
@inlinable
public func mergeSortedAsSets<S: Sequence>(with other: S, keeping filter: SetOperation, by areInIncreasingOrder: (Element, Element) throws -> Bool) rethrows -> [Element] where S.Element == Element {
return try mergeSortedAsSets(with: other, keeping: filter, into: Array.self, by: areInIncreasingOrder)
}
}
extension Sequence where Element: Comparable {
/// Assuming this sequence and the given sequence are sorted, return a
/// sorted array consisting of the two sequences blended together as sets,
/// keeping only the elements indicated by the given operation.
///
/// The sort is stable.
///
/// - Precondition: Both this sequence and `other` are finite and sorted.
///
/// - Parameter other: A sequence to blend with this one.
/// - Parameter filter: The set operation (union, intersection, *etc.*) to
/// apply to the merger.
/// - Returns: An array containing the elements of this sequence and `other`
/// in a monotonically increasing sequence. For each value that exists in
/// both sets, only one copy is kept. (Usually the one from this sequence
/// is kept, unless `filter == anyFromSecond`.)
///
/// - Complexity: O(*n* + *m*), where *n* and *m* are the lengths of this
/// sequence and `other`.
@inlinable
public func mergeSortedAsSets<S: Sequence>(with other: S, keeping filter: SetOperation) -> [Element] where S.Element == Element {
return mergeSortedAsSets(with: other, keeping: filter, by: <)
}
}
// MARK: - Lazy Set Operations on Sorted Sequences
// MARK: Iterator
/// An iterator merging two sets, represented by iterators that vend sorted
/// virtual sequences, in a set operation.
public struct SetOperationIterator<Base1: IteratorProtocol, Base2: IteratorProtocol> where Base1.Element == Base2.Element {
/// The sorting iterator.
var iterator: MergingSortedIterator<Base1, Base2>
/// Whether to vend elements exclusive to the first inner iterator.
let useExclusivesToFirst: Bool
/// Which member to take from a returned `.shared(Element, Element)`.
let useFirstFromShared: Bool?
/// Whether to vend elements exclusive to the second inner iterator.
let useExclusivesToSecond: Bool
/// Creates an iterator that vends the filtered/mapped results from the
/// given iterator.
@usableFromInline
init(base: MergingSortedIterator<Base1, Base2>, keeping filter: SetOperation) {
iterator = base
useExclusivesToFirst = filter.hasExclusivesFromFirst
if filter.hasNonExclusives {
useFirstFromShared = filter != .anyFromSecond
} else {
useFirstFromShared = nil
}
useExclusivesToSecond = filter.hasExclusivesFromSecond
}
}
extension SetOperationIterator: IteratorProtocol {
public mutating func next() -> Base1.Element? {
while let baseNext = iterator.next() {
switch baseNext {
case .exclusivelyFirst(let e) where useExclusivesToFirst,
.exclusivelySecond(let e) where useExclusivesToSecond,
.shared(let e, _) where useFirstFromShared == true,
.shared(_, let e) where useFirstFromShared == false:
return e
default:
continue
}
}
return nil
}
}
// MARK: Sequence
/// A sequence merging two sets, represented by two sorted sequences, in a set operation.
public struct SetOperationSequence<Base1: Sequence, Base2: Sequence> where Base1.Element == Base2.Element {
/// The sorting sequence.
@usableFromInline
let sequence: MergedSortedSequence<Base1, Base2>
/// The set operation to apply.
@usableFromInline
let operation: SetOperation
/// Creates a sorted sequence that applies the given set operation to the
/// merger of the two given sequences, where both sequences are sorted
/// according to the given predicate.
@usableFromInline
init(merging first: Base1, and second: Base2, applying filter: SetOperation, by areInIncreasingOrder: @escaping (Base1.Element, Base2.Element) -> Bool) {
sequence = MergedSortedSequence(merging: first, and: second, by: areInIncreasingOrder)
operation = filter
}
}
extension SetOperationSequence: Sequence {
public typealias Iterator = SetOperationIterator<Base1.Iterator, Base2.Iterator>
public typealias Element = Iterator.Element
@inlinable
public func makeIterator() -> Iterator {
return Iterator(base: sequence.makeIterator(), keeping: operation)
}
@inlinable
public var underestimatedCount: Int { 0 }
}
extension SetOperationSequence: LazySequenceProtocol {}
// MARK: Collection
/// A collection merging two sets, represented by two sorted collections, in a
/// set operation.
///
/// - Warning: `startIndex` needs to filter, so it's O(*n*) instead of O(1).
public typealias SetOperationCollection<T: Collection, U: Collection> = SetOperationSequence<T, U> where T.Element == U.Element
extension SetOperationCollection: Collection {
public typealias Index = MergedSortedIndex<Base1.Index, Base2.Index>
public var startIndex: Index {
for i in sequence.indices {
switch sequence[i] {
case .exclusivelyFirst where operation.hasExclusivesFromFirst,
.shared where operation.hasNonExclusives,
.exclusivelySecond where operation.hasExclusivesFromSecond:
return i
default:
continue
}
}
return endIndex
}
@inlinable
public var endIndex: Index { sequence.endIndex }
@inlinable
public subscript(position: Index) -> Element {
switch sequence[position] {
case .exclusivelyFirst(let e), .exclusivelySecond(let e):
return e
case let .shared(first, second):
return operation != .anyFromSecond ? first : second
}
}
public func index(after i: Index) -> Index {
precondition(i < endIndex)
for j in sequence.indices[i...].dropFirst() {
switch sequence[j] {
case .exclusivelyFirst where operation.hasExclusivesFromFirst,
.shared where operation.hasNonExclusives,
.exclusivelySecond where operation.hasExclusivesFromSecond:
return j
default:
continue
}
}
return endIndex
}
}
extension SetOperationCollection: LazyCollectionProtocol {}
// MARK: Generators
extension LazySequenceProtocol {
/// Assuming this lazy sequence is sorted according to the given predicate
/// comparing elements, and the given lazy sequence is sorted the same way,
/// return a lazy sequence vending sorted elements consisting of the two
/// sequences blended together as sets, keeping only the elements indicated
/// by the given operation.
///
/// `areInIncreasingOrder` must be a strict weak ordering over the elements.
///
/// The sort is stable.
///
/// The implementation pulls elements until one from the desired subset is
/// found. If at least one sequence isn't finite, then the thread will
/// soft-lock if a sequence has no more matches for the targeted subset.
///
/// - Precondition: Both this sequence and `other` are sorted according to
/// `areInIncreasingOrder`.
///
/// - Parameter other: A lazy sequence to blend with this one.
/// - Parameter filter: The set operation (union, intersection, *etc.*) to
/// apply to the merger.
/// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
/// first argument should be ordered before its second argument;
/// otherwise, `false`.
/// - Returns: A lazy sequence containing the elements of this sequence and
/// `other` in a way that maintains the sort determined by
/// `areInIncreasingOrder`. For each value that exists in both sets, only
/// one copy is kept. (Usually the one from this sequence is kept, unless
/// `filter == anyFromSecond`.)
@inlinable
public func mergeSortedAsSets<L: LazySequenceProtocol>(with other: L, keeping filter: SetOperation, by areInIncreasingOrder: @escaping (Element, Element) -> Bool) -> SetOperationSequence<Elements, L.Elements> where L.Element == Element {
return SetOperationSequence(merging: elements, and: other.elements, applying: filter, by: areInIncreasingOrder)
}
/// Assuming this lazy sequence is sorted according to the given predicate
/// comparing elements, and the given sequence is sorted the same way,
/// return a lazy sequence vending sorted elements consisting of the two
/// sequences blended together as sets, keeping only the elements indicated
/// by the given operation.
///
/// `areInIncreasingOrder` must be a strict weak ordering over the elements.
///
/// The sort is stable.
///
/// The implementation pulls elements until one from the desired subset is
/// found. If at least one sequence isn't finite, then the thread will
/// soft-lock if a sequence has no more matches for the targeted subset.
///
/// - Precondition: Both this sequence and `other` are sorted according to
/// `areInIncreasingOrder`.
///
/// - Parameter other: A sequence to blend with this one.
/// - Parameter filter: The set operation (union, intersection, *etc.*) to
/// apply to the merger.
/// - Parameter areInIncreasingOrder: A predicate that returns `true` if its
/// first argument should be ordered before its second argument;
/// otherwise, `false`.
/// - Returns: A lazy sequence containing the elements of this sequence and
/// `other` in a way that maintains the sort determined by
/// `areInIncreasingOrder`. For each value that exists in both sets, only
/// one copy is kept. (Usually the one from this sequence is kept, unless
/// `filter == anyFromSecond`.)
@inlinable
public func mergeSortedAsSets<S: Sequence>(with other: S, keeping filter: SetOperation, by areInIncreasingOrder: @escaping (Element, Element) -> Bool) -> SetOperationSequence<Elements, LazySequence<S>.Elements> where S.Element == Element {
return mergeSortedAsSets(with: other.lazy, keeping: filter, by: areInIncreasingOrder)
}
}
extension LazySequenceProtocol where Element: Comparable {
/// Assuming this lazy sequence and the given sequence are sorted, return a
/// lazy sequence vending sorted elements consisting of the two sequences
/// blended together as sets, keeping only the elements indicated by the
/// given operation.
///
/// The sort is stable.
///
/// The implementation pulls elements until one from the desired subset is
/// found. If at least one sequence isn't finite, then the thread will
/// soft-lock if a sequence has no more matches for the targeted subset.
///
/// - Precondition: Both this sequence and `other` are sorted.
///
/// - Parameter other: A sequence to blend with this one.
/// - Parameter filter: The set operation (union, intersection, *etc.*) to
/// apply to the merger.
/// - Returns: A lazily-generated sequence vending the elements of this
/// sequence and `other` in a monotonically increasing sequence. For each
/// value that exists in both sets, only one copy is kept. (Usually the
/// one from this sequence is kept, unless `filter == anyFromSecond`.)
@inlinable
public func mergeSortedAsSets<S: Sequence>(with other: S, keeping filter: SetOperation) -> SetOperationSequence<Elements, LazySequence<S>.Elements> where S.Element == Element {
return mergeSortedAsSets(with: other, keeping: filter, by: <)
}
}
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.