8
0

utils-diff.js 3.0 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117
  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 producing an object containing a list of actions
  10. * necessary to transform one array into another.
  11. *
  12. * diff( 'aba', 'acca' ); // [ EQUAL, INSERT, INSERT, DELETE, EQUAL ]
  13. *
  14. * @param {Array} a Input array
  15. * @param {Array} b Output array
  16. * @param {Function} [cmp] Optional function used to compare array values, by default === is used
  17. * @return {Array}
  18. */
  19. export default function diff( a, b, cmp ) {
  20. // Set the comparator function.
  21. cmp = cmp || function( a, b ) {
  22. return a === b;
  23. };
  24. // Temporary action type statics.
  25. let _INSERT, _DELETE;
  26. // Swapped the arrays to use the shorter one as the first one.
  27. if ( b.length < a.length ) {
  28. let tmp = a;
  29. a = b;
  30. b = tmp;
  31. // We swap the action types as well.
  32. _INSERT = 'DELETE';
  33. _DELETE = 'INSERT';
  34. } else {
  35. _INSERT = 'INSERT';
  36. _DELETE = 'DELETE';
  37. }
  38. const m = a.length;
  39. const n = b.length;
  40. const delta = n - m;
  41. // Edit scripts, for each diagonal.
  42. const es = {};
  43. // Furthest points, the furthest y we can get on each diagonal.
  44. const fp = {};
  45. function snake( k ) {
  46. // We use -1 as an alternative below to handle initial values ( instead of filling the fp with -1 first ).
  47. // Furthest points (y) on the diagonal below k.
  48. const y1 = ( fp[ k - 1 ] !== undefined ? fp[ k - 1 ] : -1 ) + 1;
  49. // Furthest points (y) on the diagonal above k.
  50. const y2 = fp[ k + 1 ] !== undefined ? fp[ k + 1 ] : -1;
  51. // The way we should go to get further.
  52. const dir = y1 > y2 ? -1 : 1;
  53. // Clone previous actions array (if any).
  54. if ( es[ k + dir ] ) {
  55. es[ k ] = es[ k + dir ].slice( 0 );
  56. }
  57. // Create actions array.
  58. if ( !es[ k ] ) {
  59. es[ k ] = [];
  60. }
  61. // Push the action.
  62. es[ k ].push( y1 > y2 ? _INSERT : _DELETE );
  63. // Set the beginning coordinates.
  64. let y = Math.max( y1, y2 );
  65. let x = y - k;
  66. // Traverse the diagonal as long as the values match.
  67. while ( x < m && y < n && cmp( a[ x ], b[ y ] ) ) {
  68. x++;
  69. y++;
  70. // Push no change action.
  71. es[ k ].push( 'EQUAL' );
  72. }
  73. return y;
  74. }
  75. let p = 0;
  76. let k;
  77. // Traverse the graph until we reach the end of the longer string.
  78. do {
  79. // Updates furthest points and edit scripts for diagonals below delta.
  80. for ( k = -p; k < delta; k++ ) {
  81. fp[ k ] = snake( k );
  82. }
  83. // Updates furthest points and edit scripts for diagonals above delta.
  84. for ( k = delta + p; k > delta; k-- ) {
  85. fp[ k ] = snake( k );
  86. }
  87. // Updates furthest point and edit script for the delta diagonal.
  88. // note that the delta diagonal is the one which goes through the sink (m, n).
  89. fp[ delta ] = snake( delta );
  90. p++;
  91. } while ( fp[ delta ] !== n );
  92. // Return the final list of edit actions.
  93. // We remove the first item that represents the action for the injected nulls.
  94. return es[ delta ].slice( 1 );
  95. }