/** One run of a word diff: kept, added or removed text. */
export interface DiffPart {
  type: 'same' | 'add' | 'del';
  text: string;
}

/** Above this many word pairs the diff is not worth computing: the two texts are shown whole. */
const MAX_CELLS = 4_000_000;

/** Stands for a paragraph break among the words, so the diff keeps the paragraphs apart. */
export const PARAGRAPH = '\u00b6';

const words = (text: string): string[] =>
  text
    .replace(/\n\s*\n/g, ` ${PARAGRAPH} `)
    .split(/\s+/)
    .filter(Boolean);

/** The text of an HTML fragment, paragraphs kept apart by a blank line. */
export const htmlToText = (html: string): string => {
  const container = document.createElement('div');
  container.innerHTML = html
    .replace(/<\/(p|div|li|h[1-6]|tr|blockquote)>/gi, '$&\n\n')
    .replace(/<br\s*\/?>/gi, '\n');
  return (container.textContent ?? '')
    .replace(/[ \t]+\n/g, '\n')
    .replace(/\n{3,}/g, '\n\n')
    .trim();
};

/**
 * The words of `after` against those of `before`, as runs to mark up: what
 * a rewrite kept, what it added and what it dropped. Whitespace is not
 * compared, so a reflowed paragraph reads as unchanged; paragraph breaks
 * come back as PARAGRAPH words.
 */
export const wordDiff = (before: string, after: string): DiffPart[] => {
  const a = words(before);
  const b = words(after);
  if (a.length === 0 || b.length === 0 || a.length * b.length > MAX_CELLS) {
    return [
      ...(a.length ? [{ type: 'del' as const, text: a.join(' ') }] : []),
      ...(b.length ? [{ type: 'add' as const, text: b.join(' ') }] : []),
    ];
  }
  const width = b.length + 1;
  const lengths = new Uint16Array((a.length + 1) * width);
  for (let i = a.length - 1; i >= 0; i -= 1) {
    for (let j = b.length - 1; j >= 0; j -= 1) {
      lengths[i * width + j] =
        a[i] === b[j]
          ? lengths[(i + 1) * width + j + 1] + 1
          : Math.max(lengths[(i + 1) * width + j], lengths[i * width + j + 1]);
    }
  }
  const parts: DiffPart[] = [];
  const push = (type: DiffPart['type'], word: string): void => {
    const last = parts[parts.length - 1];
    if (last && last.type === type) {
      last.text += ` ${word}`;
    } else {
      parts.push({ type, text: word });
    }
  };
  let i = 0;
  let j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] === b[j]) {
      push('same', a[i]);
      i += 1;
      j += 1;
    } else if (lengths[(i + 1) * width + j] >= lengths[i * width + j + 1]) {
      push('del', a[i]);
      i += 1;
    } else {
      push('add', b[j]);
      j += 1;
    }
  }
  for (; i < a.length; i += 1) push('del', a[i]);
  for (; j < b.length; j += 1) push('add', b[j]);
  return parts;
};