1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
|
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2021-2022 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
//
//===----------------------------------------------------------------------===//
struct NaivePatternSearcher<Searched: Collection, Pattern: Collection>
where Searched.Element: Equatable, Pattern.Element == Searched.Element
{
let pattern: Pattern
}
extension NaivePatternSearcher: StatelessCollectionSearcher {
func search(
_ searched: Searched,
in range: Range<Searched.Index>
) -> Range<Searched.Index>? {
var searchStart = range.lowerBound
guard let patternFirst = pattern.first else {
return searchStart..<searchStart
}
while let matchStart = searched[searchStart..<range.upperBound]
.firstIndex(of: patternFirst)
{
var index = matchStart
var patternIndex = pattern.startIndex
repeat {
searched.formIndex(after: &index)
pattern.formIndex(after: &patternIndex)
if patternIndex == pattern.endIndex {
return matchStart..<index
} else if index == range.upperBound {
return nil
}
} while searched[index] == pattern[patternIndex]
searchStart = searched.index(after: matchStart)
}
return nil
}
}
extension NaivePatternSearcher: BackwardCollectionSearcher,
BackwardStatelessCollectionSearcher
where Searched: BidirectionalCollection, Pattern: BidirectionalCollection
{
typealias BackwardSearched = Searched
func searchBack(
_ searched: BackwardSearched,
in range: Range<Searched.Index>
) -> Range<Searched.Index>? {
var searchEnd = range.upperBound
guard let otherLastIndex = pattern.indices.last else {
return searchEnd..<searchEnd
}
let patternLast = pattern[otherLastIndex]
while let matchEnd = searched[range.lowerBound..<searchEnd]
.lastIndex(of: patternLast)
{
var index = matchEnd
var otherIndex = otherLastIndex
repeat {
if otherIndex == pattern.startIndex {
return index..<searched.index(after: matchEnd)
} else if index == range.lowerBound {
return nil
}
searched.formIndex(before: &index)
pattern.formIndex(before: &otherIndex)
} while searched[index] == pattern[otherIndex]
searchEnd = matchEnd
}
return nil
}
}
|
