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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
|
//===----------------------------------------------------------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
protocol MatchingCollectionSearcher: CollectionSearcher {
associatedtype Match
func matchingSearch(
_ searched: Searched,
_ state: inout State
) -> (range: Range<Searched.Index>, match: Match)?
}
extension MatchingCollectionSearcher {
func search(
_ searched: Searched,
_ state: inout State
) -> Range<Searched.Index>? {
matchingSearch(searched, &state)?.range
}
}
protocol MatchingStatelessCollectionSearcher:
MatchingCollectionSearcher, StatelessCollectionSearcher
{
func matchingSearch(
_ searched: Searched,
in range: Range<Searched.Index>
) -> (range: Range<Searched.Index>, match: Match)?
}
extension MatchingStatelessCollectionSearcher {
// for disambiguation between the `MatchingCollectionSearcher` and
// `StatelessCollectionSearcher` overloads
func search(
_ searched: Searched,
_ state: inout State
) -> Range<Searched.Index>? {
matchingSearch(searched, &state)?.range
}
func matchingSearch(
_ searched: Searched,
_ state: inout State
) -> (range: Range<Searched.Index>, match: Match)? {
// TODO: deduplicate this logic with `StatelessCollectionSearcher`?
guard
case .index(let index) = state.position,
let (range, value) = matchingSearch(searched, in: index..<state.end)
else { return nil }
if range.isEmpty {
if range.upperBound == searched.endIndex {
state.position = .done
} else {
state.position = .index(searched.index(after: range.upperBound))
}
} else {
state.position = .index(range.upperBound)
}
return (range, value)
}
func search(
_ searched: Searched,
in range: Range<Searched.Index>
) -> Range<Searched.Index>? {
matchingSearch(searched, in: range)?.range
}
}
// MARK: Searching from the back
protocol BackwardMatchingCollectionSearcher: BackwardCollectionSearcher {
associatedtype Match
func matchingSearchBack(
_ searched: BackwardSearched,
_ state: inout BackwardState
) -> (range: Range<BackwardSearched.Index>, match: Match)?
}
protocol BackwardMatchingStatelessCollectionSearcher:
BackwardMatchingCollectionSearcher, BackwardStatelessCollectionSearcher
{
func matchingSearchBack(
_ searched: BackwardSearched,
in range: Range<BackwardSearched.Index>
) -> (range: Range<BackwardSearched.Index>, match: Match)?
}
extension BackwardMatchingStatelessCollectionSearcher {
func searchBack(
_ searched: BackwardSearched,
in range: Range<BackwardSearched.Index>
) -> Range<BackwardSearched.Index>? {
matchingSearchBack(searched, in: range)?.range
}
func matchingSearchBack(
_ searched: BackwardSearched,
_ state: inout BackwardState) -> (range: Range<BackwardSearched.Index>, match: Match)?
{
// TODO: deduplicate this logic with `StatelessBackwardCollectionSearcher`?
guard
case .index(let index) = state.position,
let (range, value) = matchingSearchBack(searched, in: state.end..<index)
else { return nil }
if range.isEmpty {
if range.lowerBound == searched.startIndex {
state.position = .done
} else {
state.position = .index(searched.index(before: range.lowerBound))
}
} else {
state.position = .index(range.lowerBound)
}
return (range, value)
}
}
|
