/*
|--------------------------------------------------------------------------
| Diff mot à mot, pour l'aperçu « avant / après »
|--------------------------------------------------------------------------
|
| Aucune dépendance : le dépôt n'embarque aucune bibliothèque de diff, et en ajouter
| une pour 60 lignes de plus-longue-sous-suite-commune serait du poids pour rien.
|
| Le découpage conserve les blocs d'espaces comme des unités à part entière. C'est ce
| qui garantit que la concaténation des segments redonne EXACTEMENT les deux textes —
| corollaire : une correction d'espaces multiples apparaît bien dans le diff, sous la
| forme d'un segment « del » et d'un segment « add » quasi invisibles à l'œil. L'appelant
| qui veut les mettre en valeur doit styliser les segments dont la valeur est blanche.
*/

export type DiffSegmentType = 'same' | 'del' | 'add';

export interface DiffSegment {
    type: DiffSegmentType;
    value: string;
}

/**
 * Au-delà, la table de plus-longue-sous-suite-commune dépasse le million de cases.
 * Un message de messagerie dépasse rarement 400 unités : la garde ne se déclenche que
 * sur un collage anormal, où l'on se rabat sur un « tout remplacé ».
 */
export const MAX_DIFF_UNITS = 800;

/** Découpe en unités « mot » et « blocs d'espaces », sans rien perdre. */
function splitIntoUnits(text: string): string[] {
    return text.split(/(\s+)/u).filter((unit) => unit !== '');
}

/** Diff mot à mot entre le texte d'origine et le texte corrigé. */
export function diffWords(before: string, after: string): DiffSegment[] {
    if (before === after) {
        return before === '' ? [] : [{ type: 'same', value: before }];
    }

    const left = splitIntoUnits(before);
    const right = splitIntoUnits(after);

    if (left.length > MAX_DIFF_UNITS || right.length > MAX_DIFF_UNITS) {
        return mergeSegments([
            { type: 'del', value: before },
            { type: 'add', value: after },
        ]);
    }

    const width = right.length + 1;
    const commonLengths = longestCommonSubsequence(left, right, width);
    const segments: DiffSegment[] = [];
    let leftIndex = 0;
    let rightIndex = 0;

    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] === right[rightIndex]) {
            segments.push({ type: 'same', value: left[leftIndex] });
            leftIndex += 1;
            rightIndex += 1;
            continue;
        }

        // On avance du côté qui conserve la plus longue sous-suite commune restante.
        if (commonLengths[(leftIndex + 1) * width + rightIndex] >= commonLengths[leftIndex * width + rightIndex + 1]) {
            segments.push({ type: 'del', value: left[leftIndex] });
            leftIndex += 1;
        } else {
            segments.push({ type: 'add', value: right[rightIndex] });
            rightIndex += 1;
        }
    }

    while (leftIndex < left.length) {
        segments.push({ type: 'del', value: left[leftIndex] });
        leftIndex += 1;
    }

    while (rightIndex < right.length) {
        segments.push({ type: 'add', value: right[rightIndex] });
        rightIndex += 1;
    }

    return mergeSegments(segments);
}

function longestCommonSubsequence(left: readonly string[], right: readonly string[], width: number): Uint32Array {
    const table = new Uint32Array((left.length + 1) * width);

    for (let leftIndex = left.length - 1; leftIndex >= 0; leftIndex -= 1) {
        for (let rightIndex = right.length - 1; rightIndex >= 0; rightIndex -= 1) {
            table[leftIndex * width + rightIndex] =
                left[leftIndex] === right[rightIndex]
                    ? table[(leftIndex + 1) * width + rightIndex + 1] + 1
                    : Math.max(table[(leftIndex + 1) * width + rightIndex], table[leftIndex * width + rightIndex + 1]);
        }
    }

    return table;
}

/** Recolle les segments consécutifs de même type : l'affichage n'a pas à gérer 40 `<span>` par phrase. */
function mergeSegments(segments: readonly DiffSegment[]): DiffSegment[] {
    const merged: DiffSegment[] = [];

    for (const segment of segments) {
        if (segment.value === '') {
            continue;
        }

        const last = merged[merged.length - 1];

        if (last !== undefined && last.type === segment.type) {
            last.value += segment.value;
            continue;
        }

        merged.push({ ...segment });
    }

    return merged;
}