// SPDX-License-Identifier: MIT

// Copyright (c) 2019, Guilherme Agostinelli

// Ported from https://github.com/guilhermeagostinelli/levenshtein/blob/master/levenshtein.cpp

#include "cpl_levenshtein.h"

#include <algorithm>

#include <cstring>

#include <limits>

#include <vector>

/** Computes the Levenshtein distance between 2 words.

 *

 * If transpositionAllowed = true, then it is the Damerau-Levenshtein distance

 *

 * Return SIZE_T_MAX in case of error.

 */

size_t CPLLevenshteinDistance(const char *word1, const char *word2,

                              bool transpositionAllowed)

{

    const size_t size1 = strlen(word1);

    const size_t size2 = strlen(word2);

    // If one of the words has zero length, the distance is equal to the size of the other word.

    if (size1 == 0)

        return size2;

    if (size2 == 0)

        return size1;

    // Would cause enormous amount of memory to be allocated

    if (size1 >= 32768 || size2 >= 32768)

    {

        return strcmp(word1, word2) == 0 ? 0

                                         : std::numeric_limits<size_t>::max();

    }

    // Verification matrix i.e. 2D array which will store the calculated distance.

    const size_t dimFastSize = size2 + 1;

    std::vector<unsigned short> verif;

    try

    {

        verif.resize((size1 + 1) * dimFastSize);

    }

    catch (const std::exception &)

    {

        return std::numeric_limits<size_t>::max();

    }

    const auto verifVal = [&verif, dimFastSize](size_t i,

                                                size_t j) -> unsigned short &

    { return verif[i * dimFastSize + j]; };

    // Sets the first row and the first column of the verification matrix with the numerical order from 0 to the length of each word.

    for (size_t i = 0; i <= size1; i++)

        verifVal(i, 0) = static_cast<unsigned short>(i);

    for (size_t j = 0; j <= size2; j++)

        verifVal(0, j) = static_cast<unsigned short>(j);

    // Verification step / matrix filling.

    for (size_t i = 1; i <= size1; i++)

    {

        for (size_t j = 1; j <= size2; j++)

        {

            // Sets the modification cost.

            // 0 means no modification (i.e. equal letters) and 1 means that a modification is needed (i.e. unequal letters).

            const int cost = (word2[j - 1] == word1[i - 1]) ? 0 : 1;

            // Sets the current position of the matrix as the minimum value between a (deletion), b (insertion) and c (substitution).

            // a = the upper adjacent value plus 1: verif[i - 1][j] + 1

            // b = the left adjacent value plus 1: verif[i][j - 1] + 1

            // c = the upper left adjacent value plus the modification cost: verif[i - 1][j - 1] + cost

            verifVal(i, j) = std::min(

                std::min(static_cast<unsigned short>(verifVal(i - 1, j) + 1),

                         static_cast<unsigned short>(verifVal(i, j - 1) + 1)),

                static_cast<unsigned short>(verifVal(i - 1, j - 1) + cost));

            // Cf https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance#Optimal_string_alignment_distance

            // (note that in the Wikipedia page, a[] and b[] are indexed from 1...

            if (transpositionAllowed && i > 1 && j > 1 &&

                word1[i - 1] == word2[j - 2] && word1[i - 2] == word2[j - 1])

            {

                verifVal(i, j) = std::min(

                    verifVal(i, j),

                    static_cast<unsigned short>(verifVal(i - 2, j - 2) + 1));

            }

        }

    }

    // The last position of the matrix will contain the Levenshtein distance.

    return verifVal(size1, size2);

}