pptxdiff/lcs.py at master · liwii/pptxdiff · GitHub

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
from collections import deque
import copy

class LCS:
    def __init__(self, left, right):
        cells = [[None for _ in range(len(right) + 1)] for i in range(len(left) + 1)]
        cells[0][0] = (None, 0)
        for i in range(1, len(left) + 1):
            cells[i][0] = ((i - 1, 0), 0)
        for j in range(1, len(right) + 1):
            cells[0][j] = ((0, j - 1), 0)

        for i in range(1, len(left) + 1):
            for j in range(1, len(right) + 1):
                lel, rel = left[i - 1], right[j - 1]
                candidate = max(((i - 1, j), cells[i - 1][j][1]), ((i, j - 1), cells[i][j - 1][1]), key = lambda t: t[1])
                if lel != rel:
                    cells[i][j] = candidate
                    continue
                common = ((i - 1, j - 1), cells[i - 1][j - 1][1] + 1)
                cells[i][j] = max(common, candidate, key = lambda t: t[1])
        self.size = cells[len(left)][len(right)][1]
        trace = []
        start = (len(left), len(right))
        while start != (0, 0):
            step = cells[start[0]][start[1]][0]
            if start[0] == step[0]:
                trace.append((None, start[1] - 1))
            elif start[1] == step[1]:
                trace.append((start[0] - 1, None))
            else:
                trace.append((start[0] - 1, start[1] - 1))
            start = step
        self.trace = trace

    def diff_collection(self):
        trace = copy.deepcopy(self.trace)
        diffs = ([], [])
        while len(trace) > 0:
            l, r = trace.pop()
            if r is None:
                diffs[0].append(l)
            if l is None:
                diffs[1].append(r)
        return diffs

    def diff(self):
        trace = copy.deepcopy(self.trace)
        diffs = []
        cur_diff = ((0, 0), (0, 0))
        lidx = 0
        ridx = 0
        while len(trace) > 0:
            lr = trace.pop()
            if lr[0] is None:
                cur_diff = (cur_diff[0], (cur_diff[1][0] + 1, cur_diff[1][1]))
                ridx += 1
            elif lr[1] is None:
                cur_diff = ((cur_diff[0][0] + 1, cur_diff[0][1]), cur_diff[1])
                lidx += 1
            else:
                if cur_diff[0][0] > 0 or cur_diff[1][0] > 0:
                    diffs.append(cur_diff)
                ridx += 1
                lidx += 1
                cur_diff = ((0, lidx), (0, ridx))

        if cur_diff[0][0] > 0 or cur_diff[1][0] > 0:
            diffs.append(cur_diff)

        return diffs