levenshpp/levenshtein.hpp

/**********
    This file is part of levenshpp.

    levenshpp is free library: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    levenshpp is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with levenshpp.  If not, see <http://www.gnu.org/licenses/>.
**********/

#pragma once

#include <utility>
#include <queue>

static unsigned int levenshtein_get(unsigned int * const *map, int px, int py)
{
    if (px == -1 && py == -1)
        return 0;
    if (px == -1)
        return py +1;
    if (py == -1)
        return px +1;
    return map[px][py];
}

template <class T, typename SIZE=unsigned int>
unsigned int levenshtein(const T *a, const T *b, const SIZE aSize, const SIZE bSize)
{
    unsigned int **items = new unsigned int*[aSize]();

    for (SIZE i =0; i < aSize; i++)
    {
        items[i] = new unsigned int[bSize]();
        for (SIZE j =0; j < bSize; j++)
        {
            unsigned int add = levenshtein_get(items, i, j -1) +1;
            unsigned int del = levenshtein_get(items, i -1, j) +1;
            unsigned int mod = levenshtein_get(items, i -1, j -1) +(a[i] == b[j] ? 0 : 1);

            items[i][j] = std::min(std::min(add, del), mod);
        }
    }
    const unsigned int levenshtein = items[aSize -1][bSize -1];
    for (SIZE i =0; i < aSize; i++)
        delete[] items[i];
    delete[] items;
    return levenshtein;
}

template <class T, typename SIZE=unsigned int>
unsigned int levenshtein(const T &a, const T &b, const SIZE aSize, const SIZE bSize)
{
    unsigned int **items = new unsigned int*[aSize]();

    for (SIZE i =0; i < aSize; i++)
    {
        items[i] = new unsigned int[bSize]();
        for (SIZE j =0; j < bSize; j++)
        {
            unsigned int add = levenshtein_get(items, i, j -1) +1;
            unsigned int del = levenshtein_get(items, i -1, j) +1;
            unsigned int mod = levenshtein_get(items, i -1, j -1) +(a[i] == b[j] ? 0 : 1);

            items[i][j] = std::min(std::min(add, del), mod);
        }
    }
    const unsigned int levenshtein = items[aSize -1][bSize -1];
    for (SIZE i =0; i < aSize; i++)
        delete[] items[i];
    delete[] items;
    return levenshtein;
}