mirror of
https://github.com/apple/swift-algorithms
synced 2026-11-22 04:10:39 +00:00
292 lines
7.6 KiB
Swift
292 lines
7.6 KiB
Swift
//===----------------------------------------------------------------------===//
|
|
//
|
|
// This source file is part of the Swift Algorithms open source project
|
|
//
|
|
// Copyright (c) 2020 Apple Inc. and the Swift project authors
|
|
// Licensed under Apache License v2.0 with Runtime Library Exception
|
|
//
|
|
// See https://swift.org/LICENSE.txt for license information
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
public struct SubSequenceFinder<Base: Collection, Other: Collection>
|
|
where Base.Element == Other.Element, Base.Element: Equatable
|
|
{
|
|
internal var base: Base
|
|
internal var other: Other
|
|
internal var firstRange: Range<Base.Index>?
|
|
internal var areEquivalent: (Base.Element, Base.Element) -> Bool
|
|
|
|
internal init(
|
|
base: Base,
|
|
other: Other,
|
|
by areEquivalent: @escaping (Base.Element, Base.Element) -> Bool)
|
|
{
|
|
self.base = base
|
|
self.other = other
|
|
self.areEquivalent = areEquivalent
|
|
self.firstRange = base.firstRange(of: other, by: areEquivalent)
|
|
}
|
|
}
|
|
|
|
extension SubSequenceFinder: Collection {
|
|
public struct Index: Comparable {
|
|
internal enum Representation: Comparable {
|
|
case match(Range<Base.Index>)
|
|
case end
|
|
|
|
public static func < (lhs: Representation, rhs: Representation) -> Bool {
|
|
switch (lhs, rhs) {
|
|
case (.match, .end):
|
|
return true
|
|
case (.end, _):
|
|
return false
|
|
case (.match(let lhs), .match(let rhs)):
|
|
return lhs.lowerBound < rhs.lowerBound
|
|
}
|
|
}
|
|
}
|
|
|
|
internal var base: Representation
|
|
|
|
internal static var end: Index {
|
|
Index(base: .end)
|
|
}
|
|
|
|
private init(base: Representation) {
|
|
self.base = base
|
|
}
|
|
|
|
internal init(_ range: Range<Base.Index>) {
|
|
self.base = .match(range)
|
|
}
|
|
|
|
public static func < (lhs: Index, rhs: Index) -> Bool {
|
|
lhs.base < rhs.base
|
|
}
|
|
}
|
|
|
|
public var startIndex: Index {
|
|
firstRange.map { Index($0) } ?? .end
|
|
}
|
|
|
|
public var endIndex: Index {
|
|
.end
|
|
}
|
|
|
|
public func index(after i: Index) -> Index {
|
|
guard case .match(let range) = i.base else {
|
|
preconditionFailure("Can't advance past endIndex")
|
|
}
|
|
let startingPoint = base.index(after: range.lowerBound)
|
|
return base[startingPoint...]
|
|
.firstRange(of: other)
|
|
.map { Index($0) } ?? .end
|
|
}
|
|
|
|
public subscript(position: Index) -> Range<Base.Index> {
|
|
guard case .match(let range) = position.base else {
|
|
preconditionFailure("Can't subscript with endIndex")
|
|
}
|
|
return range
|
|
}
|
|
}
|
|
|
|
extension SubSequenceFinder: BidirectionalCollection
|
|
where Base: BidirectionalCollection, Other: BidirectionalCollection
|
|
{
|
|
public func index(before i: Index) -> Index {
|
|
let endingPoint: Base.Index
|
|
switch i.base {
|
|
case .match(let range):
|
|
precondition(range != firstRange, "Can't move before startIndex")
|
|
endingPoint = base.index(before: range.upperBound)
|
|
case .end:
|
|
endingPoint = base.endIndex
|
|
}
|
|
return Index(base[..<endingPoint].lastRange(of: other)!)
|
|
}
|
|
}
|
|
|
|
// MARK: allRanges(of:by:) / allRanges(of:)
|
|
|
|
extension Collection {
|
|
public func allRanges<Other: Collection>(
|
|
of other: Other,
|
|
by areEquivalent: @escaping (Element, Element) -> Bool
|
|
)
|
|
-> SubSequenceFinder<Self, Other>
|
|
{
|
|
SubSequenceFinder(base: self, other: other, by: areEquivalent)
|
|
}
|
|
}
|
|
|
|
extension Collection where Element: Equatable {
|
|
public func allRanges<Other: Collection>(of other: Other) -> SubSequenceFinder<Self, Other>
|
|
where Element == Other.Element
|
|
{
|
|
allRanges(of: other, by: ==)
|
|
}
|
|
}
|
|
|
|
// MARK: - firstRange(of:by:) / firstRange(of:)
|
|
|
|
extension Collection {
|
|
public func firstRange<Other: Collection>(
|
|
of other: Other,
|
|
by areEquivalent: (Element, Element) throws -> Bool
|
|
) rethrows -> Range<Index>?
|
|
where Other.Element == Element
|
|
{
|
|
var searchStart = startIndex
|
|
guard let needleFirst = other.first else { return nil }
|
|
|
|
while let matchStart = try self[searchStart...]
|
|
.firstIndex(where: { try areEquivalent($0, needleFirst) })
|
|
{
|
|
var selfPos = index(after: matchStart)
|
|
var otherPos = other.index(after: other.startIndex)
|
|
|
|
while true {
|
|
if otherPos == other.endIndex {
|
|
return matchStart..<selfPos
|
|
}
|
|
if selfPos == self.endIndex {
|
|
return nil
|
|
}
|
|
if try !areEquivalent(self[selfPos], other[otherPos]) {
|
|
break
|
|
}
|
|
|
|
self.formIndex(after: &selfPos)
|
|
other.formIndex(after: &otherPos)
|
|
}
|
|
|
|
searchStart = self.index(after: matchStart)
|
|
}
|
|
|
|
return nil
|
|
}
|
|
}
|
|
|
|
extension Collection where Element: Equatable {
|
|
public func firstRange<Other: Collection>(of other: Other) -> Range<Index>?
|
|
where Element == Other.Element
|
|
{
|
|
firstRange(of: other, by: ==)
|
|
}
|
|
}
|
|
|
|
// MARK: - lastRange(of:by:) / lastRange(of:)
|
|
|
|
extension BidirectionalCollection where Element: Equatable {
|
|
public func lastRange<Other: BidirectionalCollection>(of other: Other) -> Range<Index>?
|
|
where Other.Element == Element
|
|
{
|
|
var searchEnd = endIndex
|
|
guard let needleLast = other.last else { return nil }
|
|
let otherLastIndex = other.index(before: other.endIndex)
|
|
|
|
while let matchEnd = self[..<searchEnd].lastIndex(of: needleLast) {
|
|
var selfPos = matchEnd
|
|
var otherPos = otherLastIndex
|
|
|
|
while true {
|
|
if otherPos == other.startIndex {
|
|
return selfPos..<index(after: matchEnd)
|
|
}
|
|
if selfPos == self.startIndex {
|
|
return nil
|
|
}
|
|
|
|
self.formIndex(before: &selfPos)
|
|
other.formIndex(before: &otherPos)
|
|
if self[selfPos] != other[otherPos] {
|
|
break
|
|
}
|
|
}
|
|
|
|
searchEnd = matchEnd
|
|
}
|
|
|
|
return nil
|
|
}
|
|
}
|
|
|
|
|
|
public struct SubSequenceFinderFromEnd<Base: BidirectionalCollection, Other: BidirectionalCollection>
|
|
where Base.Element == Other.Element, Base.Element: Equatable
|
|
{
|
|
internal var base: Base
|
|
internal var other: Other
|
|
internal var lastRange: Range<Base.Index>?
|
|
|
|
internal init(base: Base, other: Other, allowingOverlaps: Bool) {
|
|
self.base = base
|
|
self.other = other
|
|
self.lastRange = base.lastRange(of: other)
|
|
}
|
|
}
|
|
|
|
extension SubSequenceFinderFromEnd: Collection {
|
|
public struct Index: Comparable {
|
|
internal enum Representation: Comparable {
|
|
case match(Range<Base.Index>)
|
|
case end
|
|
|
|
public static func < (lhs: Representation, rhs: Representation) -> Bool {
|
|
switch (lhs, rhs) {
|
|
case (.match, .end):
|
|
return true
|
|
case (.end, _):
|
|
return false
|
|
case (.match(let lhs), .match(let rhs)):
|
|
return lhs.lowerBound > rhs.lowerBound
|
|
}
|
|
}
|
|
}
|
|
|
|
internal var base: Representation
|
|
|
|
internal static var end: Index {
|
|
Index(base: .end)
|
|
}
|
|
|
|
private init(base: Representation) {
|
|
self.base = base
|
|
}
|
|
|
|
internal init(_ range: Range<Base.Index>) {
|
|
self.base = .match(range)
|
|
}
|
|
|
|
public static func < (lhs: Index, rhs: Index) -> Bool {
|
|
lhs.base < rhs.base
|
|
}
|
|
}
|
|
|
|
public var startIndex: Index {
|
|
lastRange.map { Index($0) } ?? .end
|
|
}
|
|
|
|
public var endIndex: Index {
|
|
.end
|
|
}
|
|
|
|
public func index(after i: Index) -> Index {
|
|
guard case .match(let range) = i.base else {
|
|
preconditionFailure("Can't advance past endIndex")
|
|
}
|
|
return base[..<range.lowerBound]
|
|
.lastRange(of: other)
|
|
.map { Index($0) } ?? .end
|
|
}
|
|
|
|
public subscript(position: Index) -> Range<Base.Index> {
|
|
guard case .match(let range) = position.base else {
|
|
preconditionFailure("Can't subscript with endIndex")
|
|
}
|
|
return range
|
|
}
|
|
}
|