Hard linking of texts to catalogue.
[redakcja.git] / src / redakcja / static / js / lib / diff.js
1 $.wiki.diff = function(a, b) {
2     MAXD = 500;
3
4     let VV = new Array(),
5         N = a.length,
6         M = b.length,
7         V, Vp, D, x, y, k;
8     V = VV[-1] = Array();
9     V[1] = 0;
10     let endD = null;
11     for (D = 0; D < MAXD && endD === null; D++) {
12         Vp = V;
13         V = VV[D] = Array();
14         for (k = -D; k <= D; k += 2) {
15             if (k == -D || (k != D && Vp[k-1] < Vp[k + 1])) {
16                 x = Vp[k + 1];
17             } else {
18                 x = Vp[k - 1] + 1;
19             }
20             y = x - k;
21
22             while (x < N && y < M && a[x] == b[y]) {
23                 x ++;
24                 y ++;
25
26                 // Avoid comparing long text character by character.
27                 let step = 1;
28                 while (true) {
29                     step = Math.min(step * 2, N - x, M - y);
30                     if (!step) break;
31                     if (a.substr(x, step) == b.substr(y, step)) {
32                         x += step;
33                         y += step;
34                     } else {
35                         break;
36                     }
37                 }
38             }
39
40             V[k] = x;
41             if (x == N && y == M) {
42                 endD = D;
43                 break;
44             }
45         }
46     }
47     if (endD === null) {
48         // Max D limit reached, diff too big. Bail and just return the whole target text.
49         return b;
50     }
51
52     // Now go back.
53     result = []
54     let px, py;
55     for (D = endD; D; --D) {
56         k = x - y;
57         V = VV[D - 1];
58         if (V[k - 1] === undefined || V[k + 1] > V[k - 1]) {
59             // move up
60             k ++;
61             px = V[k];
62             py = px - k;
63             if (result.length && result[0][0] && result[0][1] == px) {
64                 result[0][2] = b[py] + result[0][2];
65             } else {
66                 result.unshift(
67                     [true, px, b[py]]
68                 )
69             }
70         } else {
71             // move down
72             k --;
73             px = V[k];
74             py = px - k;
75             if (result.length && !result[0][0] && result[0][1] == px + 1) {
76                 result[0][1]--;
77                 result[0][2]++;
78             } else {
79                 result.unshift(
80                     [false, px, 1]
81                 )
82             }
83         }
84         x = px;
85         y = py;
86     }
87     return result
88 }
89
90
91 $.wiki.patch = function(a, p) {
92     for (i = p.length - 1; i >= 0; -- i) {
93         let c = p[i];
94         if (c[0]) {
95             a = a.substr(0, c[1]) + c[2] + a.substr(c[1]);
96         } else {
97             a = a.substr(0, c[1]) + a.substr(c[1] + c[2]);
98         }
99     }
100     return a;
101 }