-
-
Notifications
You must be signed in to change notification settings - Fork 332
/
LCSMatchingAlgo.kt
75 lines (62 loc) · 2.64 KB
/
LCSMatchingAlgo.kt
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
package io.mockk.impl.verify
import io.mockk.Invocation
import io.mockk.RecordedCall
class LCSMatchingAlgo(
val allCalls: List<Invocation>,
private val verificationSequence: List<RecordedCall>,
private val captureBlocks: MutableList<() -> Unit>? = null
) {
private val nEdits = Array(allCalls.size) { Array(verificationSequence.size) { 0 } }
private val path = Array(allCalls.size) { Array(verificationSequence.size) { '?' } }
val verifiedMatchers = mutableListOf<RecordedCall>()
val verifiedCalls = mutableListOf<Invocation>()
fun lcs(): Boolean {
fun maxOf(a: Pair<Int, Char>, b: Pair<Int, Char>) =
if (a.first > b.first) a else b
for ((callIdx, call) in allCalls.withIndex()) {
for ((matcherIdx, matcher) in verificationSequence.map { it.matcher }.withIndex()) {
val result = if (matcher.match(call)) {
if (matcherIdx == 0 || callIdx == 0)
Pair(1, '=')
else
Pair(nEdits[callIdx - 1][matcherIdx - 1] + 1, '=')
} else {
maxOf(
if (callIdx == 0)
Pair(0, '^')
else
Pair(nEdits[callIdx - 1][matcherIdx], '^'),
if (matcherIdx == 0)
Pair(0, '<')
else
Pair(nEdits[callIdx][matcherIdx - 1], '<')
)
}
nEdits[callIdx][matcherIdx] = result.first
path[callIdx][matcherIdx] = result.second
}
}
backTrackCalls(allCalls.size - 1, verificationSequence.size - 1)
// match only if all matchers present
return nEdits[allCalls.size - 1][verificationSequence.size - 1] == verificationSequence.size
}
private tailrec fun backTrackCalls(callIdx: Int, matcherIdx: Int) {
if (callIdx < 0 || matcherIdx < 0) return
when (path[callIdx][matcherIdx]) {
'=' -> {
val matcher = verificationSequence[matcherIdx].matcher
val invocation = allCalls[callIdx]
captureBlocks?.add { matcher.captureAnswer(invocation) }
verifiedCalls.add(invocation)
verifiedMatchers.add(verificationSequence[matcherIdx])
backTrackCalls(callIdx - 1, matcherIdx - 1)
}
'^' -> {
backTrackCalls(callIdx - 1, matcherIdx)
}
'<' -> {
backTrackCalls(callIdx, matcherIdx - 1)
}
}
}
}