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             while (x < N && y < M && a[x] == b[y]) {
  22                 x ++;
  23                 y ++;
  24             }
  25             V[k] = x;
  26             if (x == N && y == M) {
  27                 endD = D;
  28                 break;
  29             }
  30         }
  31     }
  32     if (endD === null) {
  33         // Max D limit reached, diff too big. Bail and just return the whole target text.
  34         return b;
  35     }
  36
  37     // Now go back.
  38     result = []
  39     let snake, px, py;
  40     for (D = endD; D; --D) {
  41         k = x - y;
  42         V = VV[D - 1];
  43         if (V[k - 1] === undefined || V[k + 1] > V[k - 1]) {
  44             // move up
  45             k ++;
  46             px = V[k];
  47             py = px - k;
  48             if (result.length && result[0][0] && result[0][1] == px) {
  49                 result[0][2] = b[py] + result[0][2];
  50             } else {
  51                 result.unshift(
  52                     [true, px, b[py]]
  53                 )
  54             }
  55         } else {
  56             // move down
  57             k --;
  58             px = V[k];
  59             py = px - k;
  60             if (result.length && !result[0][0] && result[0][1] == px + 1) {
  61                 result[0][1]--;
  62                 result[0][2]++;
  63             } else {
  64                 result.unshift(
  65                     [false, px, 1]
  66                 )
  67             }
  68         }
  69         x = px;
  70         y = py;
  71     }
  72     return result
  73 }
  74
  75
  76 $.wiki.patch = function(a, p) {
  77     for (i = p.length - 1; i >= 0; -- i) {
  78         let c = p[i];
  79         if (c[0]) {
  80             a = a.substr(0, c[1]) + c[2] + a.substr(c[1]);
  81         } else {
  82             a = a.substr(0, c[1]) + a.substr(c[1] + c[2]);
  83         }
  84     }
  85     return a;
  86 }