edit-distance/myers-1986 Home Manual Reference Source

src/recurse.js

  1. import assert from 'assert';
  2.  
  3. import {ValueError} from '@failure-abstraction/error';
  4.  
  5. import twoWayAlloc from './twoWayAlloc.js';
  6. import twoWayScan from './twoWayScan.js';
  7.  
  8. import RecurseDeeper from './RecurseDeeper.js';
  9. import StackEntry from './StackEntry.js';
  10.  
  11. /**
  12. * Recurse.
  13. *
  14. * @param {number} MAX
  15. * @param {Function} eq
  16. * @param {number} li
  17. * @param {number} lj
  18. * @param {number} ri
  19. * @param {number} rj
  20. * @return {IterableIterator}
  21. */
  22. export default function recurse(MAX, eq, li, lj, ri, rj) {
  23. assert(MAX >= 0);
  24. assert(lj - li + rj - ri > MAX);
  25. if (li === lj || ri === rj) {
  26. assert(lj - li > MAX || rj - ri > MAX);
  27. throw new ValueError();
  28. }
  29.  
  30. assert(li < lj);
  31. assert(ri < rj);
  32. assert(!eq(li, ri));
  33. assert(!eq(lj - 1, rj - 1));
  34.  
  35. const {V, centerF, centerB} = twoWayAlloc(MAX, li, lj, ri, rj);
  36.  
  37. const split = twoWayScan(MAX, V, centerF, centerB, eq, li, lj, ri, rj);
  38.  
  39. const k = split.k;
  40. const xBegin = split.xBegin;
  41. const xEnd = split.xEnd;
  42. const distanceLeft = split.distanceLeft;
  43. const distance = split.distance;
  44. const distanceRight = (distance - distanceLeft) | 0;
  45.  
  46. console.debug({k, xBegin, xEnd, distance});
  47.  
  48. if (distance === -1) throw new ValueError();
  49.  
  50. assert(distance > 0);
  51. const maxDistance =
  52. (((lj - li) | 0) + ((((rj - ri) | 0) - ((xEnd - xBegin) << 1)) | 0)) | 0;
  53. if (distance === maxDistance) {
  54. // Early exit when there is no match in the recursive calls
  55. assert(xBegin < xEnd);
  56. return [
  57. [li, xBegin, ri, (xBegin - k) | 0],
  58. [xEnd, lj, (xEnd - k) | 0, rj],
  59. ][Symbol.iterator]();
  60. }
  61.  
  62. assert(distance < maxDistance);
  63. return new RecurseDeeper(
  64. V,
  65. [
  66. new StackEntry(distanceRight, xEnd, lj, (xEnd - k) | 0, rj),
  67. new StackEntry(distanceLeft, li, xBegin, ri, (xBegin - k) | 0),
  68. ],
  69. eq,
  70. );
  71. }