aboutsummaryrefslogtreecommitdiff
path: root/paludis/util/damerau_levenshtein.cc
blob: ab4d0a5b7f70affd03707b28795451cf89a4fff7 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/* vim: set sw=4 sts=4 et foldmethod=syntax : */

/*
 * Copyright (c) 2007 Fernando J. Pereda
 *
 * This file is part of the Paludis package manager. Paludis is free software;
 * you can redistribute it and/or modify it under the terms of the GNU General
 * Public License version 2, as published by the Free Software Foundation.
 *
 * Paludis 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
 * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
 * Place, Suite 330, Boston, MA  02111-1307  USA
 */

#include <paludis/util/damerau_levenshtein.hh>
#include <paludis/util/pimp-impl.hh>
#include <memory>
#include <vector>

using namespace paludis;

template class Pimp<DamerauLevenshtein>;

namespace paludis
{
    template <>
    struct Imp<DamerauLevenshtein>
    {
        std::string name;
        unsigned n;

        Imp(const std::string & myname) :
            name(myname), n(name.length() + 1)
        {
        }
    };
}

DamerauLevenshtein::DamerauLevenshtein(const std::string & name) :
    Pimp<DamerauLevenshtein>(name)
{
}

DamerauLevenshtein::~DamerauLevenshtein()
{
}

unsigned
DamerauLevenshtein::distance_with(const std::string & candidate) const
{
    std::vector<unsigned> prevprev(_imp->n, 0);
    std::vector<unsigned> prev(_imp->n);
    std::vector<unsigned> current(_imp->n, 0);

    for (unsigned i(0) ; i < _imp->n ; ++i)
        prev[i] = i;

    size_t m(candidate.length() + 1);
    for (unsigned i(1) ; i < m ; ++i)
    {
        current[0] = i;
        for (unsigned j(1) ; j < _imp->n ; ++j)
        {
            unsigned cost(candidate[i - 1] == _imp->name[j - 1] ? 0 : 1);
            current[j] = std::min(
                    std::min(prev[j] + 1, current[j - 1] + 1),
                    prev[j - 1] + cost);
            if (i > 1 && j > 1
                    && candidate[i - 1] == _imp->name[j - 2]
                    && candidate[i - 2] == _imp->name[j - 1])
                current[j] = std::min(current[j], prevprev[j - 2] + cost);
        }
        prevprev.swap(current);
        prevprev.swap(prev);
    }

    return prev[_imp->n - 1];
}