8
0

diff.js 3.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118
  1. /**
  2. * @license Copyright (c) 2003-2015, CKSource - Frederico Knabben. All rights reserved.
  3. * For licensing, see LICENSE.md.
  4. */
  5. 'use strict';
  6. // The following code is based on the "O(NP) Sequence Comparison Algorithm"
  7. // by Sun Wu, Udi Manber, Gene Myers, Webb Miller.
  8. /**
  9. * Calculates the difference between two arrays or strings producing an array containing a list of changes
  10. * necessary to transform input into output.
  11. *
  12. * diff( 'aba', 'acca' ); // [ 'equal', 'insert', 'insert', 'delete', 'equal' ]
  13. *
  14. * @method utils.diff
  15. * @param {Array|String} a Input array or string.
  16. * @param {Array|String} b Output array or string.
  17. * @param {Function} [cmp] Optional function used to compare array values, by default === is used.
  18. * @returns {Array} Array of changes.
  19. */
  20. export default function diff( a, b, cmp ) {
  21. // Set the comparator function.
  22. cmp = cmp || function( a, b ) {
  23. return a === b;
  24. };
  25. // Temporary action type statics.
  26. let _insert, _delete;
  27. // Swapped the arrays to use the shorter one as the first one.
  28. if ( b.length < a.length ) {
  29. let tmp = a;
  30. a = b;
  31. b = tmp;
  32. // We swap the action types as well.
  33. _insert = 'delete';
  34. _delete = 'insert';
  35. } else {
  36. _insert = 'insert';
  37. _delete = 'delete';
  38. }
  39. const m = a.length;
  40. const n = b.length;
  41. const delta = n - m;
  42. // Edit scripts, for each diagonal.
  43. const es = {};
  44. // Furthest points, the furthest y we can get on each diagonal.
  45. const fp = {};
  46. function snake( k ) {
  47. // We use -1 as an alternative below to handle initial values ( instead of filling the fp with -1 first ).
  48. // Furthest points (y) on the diagonal below k.
  49. const y1 = ( fp[ k - 1 ] !== undefined ? fp[ k - 1 ] : -1 ) + 1;
  50. // Furthest points (y) on the diagonal above k.
  51. const y2 = fp[ k + 1 ] !== undefined ? fp[ k + 1 ] : -1;
  52. // The way we should go to get further.
  53. const dir = y1 > y2 ? -1 : 1;
  54. // Clone previous changes array (if any).
  55. if ( es[ k + dir ] ) {
  56. es[ k ] = es[ k + dir ].slice( 0 );
  57. }
  58. // Create changes array.
  59. if ( !es[ k ] ) {
  60. es[ k ] = [];
  61. }
  62. // Push the action.
  63. es[ k ].push( y1 > y2 ? _insert : _delete );
  64. // Set the beginning coordinates.
  65. let y = Math.max( y1, y2 );
  66. let x = y - k;
  67. // Traverse the diagonal as long as the values match.
  68. while ( x < m && y < n && cmp( a[ x ], b[ y ] ) ) {
  69. x++;
  70. y++;
  71. // Push no change action.
  72. es[ k ].push( 'equal' );
  73. }
  74. return y;
  75. }
  76. let p = 0;
  77. let k;
  78. // Traverse the graph until we reach the end of the longer string.
  79. do {
  80. // Updates furthest points and edit scripts for diagonals below delta.
  81. for ( k = -p; k < delta; k++ ) {
  82. fp[ k ] = snake( k );
  83. }
  84. // Updates furthest points and edit scripts for diagonals above delta.
  85. for ( k = delta + p; k > delta; k-- ) {
  86. fp[ k ] = snake( k );
  87. }
  88. // Updates furthest point and edit script for the delta diagonal.
  89. // note that the delta diagonal is the one which goes through the sink (m, n).
  90. fp[ delta ] = snake( delta );
  91. p++;
  92. } while ( fp[ delta ] !== n );
  93. // Return the final list of edit changes.
  94. // We remove the first item that represents the action for the injected nulls.
  95. return es[ delta ].slice( 1 );
  96. }