<commit_before>/*
 * Levenshtein distance using the classic DP algorithm.
 * Copyright 2013 <NAME>.
 * All rights reserved. See the file LICENSE for licensing information.
 */

#ifndef levenshtein_impl_h
#define levenshtein_impl_h

#include <algorithm>
#include <climits>
#include <stdexcept>
#include <vector>

static unsigned min(unsigned a, unsigned b, unsigned c)
{
    return std::min(a, std::min(b, c));
}

template <typename Char>
static unsigned levenshtein(Char const *a, size_t m, Char const *b, size_t n)
{
    // Swap a and b if necessary to ensure m <= n.
    if (m > n) {
        Char const *p;
        size_t t;

        p = a;
        a = b;
        b = p;

        t = m;
        m = n;
        n = t;
    }

    // Skip common prefix.
    while (*a == *b) {
        a++, b++;
        m--, n--;
    }

    // Skip common suffix.
    while (m > 0 && n > 0 && a[m - 1] == b[n - 1]) {
        m--, n--;
    }

    // To save memory, we use unsigned as the type in the DP table.
    if (m > UINT_MAX || n > UINT_MAX) {
        throw std::length_error("string too long in Levenshtein distance.");
    }

    if (m == 0) {
        return n;
    }
    if (n == 0) {
        return m;
    }

    std::vector<unsigned> tab((m + 1) * 2);

    unsigned *cur = tab.data(), *prev = tab.data() + m + 1;

    for (size_t i = 0; i <= m; i++) {
        cur[i] = i;
    }
    for (size_t j = 1; j <= n; j++) {
        unsigned *t = cur;
        cur = prev;
        prev = t;

        cur[0] = j;

        for (size_t i = 1; i <= m; i++) {
            if (a[i - 1] == b[j - 1]) {
                cur[i] = prev[i - 1];
            }
            else {
                cur[i] = min(cur[i - 1], prev[i], prev[i - 1]) + 1;
            }
        }
    }
<commit_msg>use std::swap instead of C-style variable swap<commit_after>/*
 * Levenshtein distance using the classic DP algorithm.
 * Copyright 2013 <NAME>.
 * All rights reserved. See the file LICENSE for licensing information.
 */

#ifndef levenshtein_impl_h
#define levenshtein_impl_h

#include <algorithm>
#include <climits>
#include <stdexcept>
#include <vector>

static unsigned min(unsigned a, unsigned b, unsigned c)
{
    return std::min(a, std::min(b, c));
}

template <typename Char>
static unsigned levenshtein(Char const *a, size_t m, Char const *b, size_t n)
{
    // Swap a and b if necessary to ensure m <= n.
    if (m > n) {
        std::swap(a, b);
        std::swap(m, n);
    }

    // Skip common prefix.
    while (*a == *b) {
        a++, b++;
        m--, n--;
    }

    // Skip common suffix.
    while (m > 0 && n > 0 && a[m - 1] == b[n - 1]) {
        m--, n--;
    }

    // To save memory, we use unsigned as the type in the DP table.
    if (m > UINT_MAX || n > UINT_MAX) {
        throw std::length_error("string too long in Levenshtein distance.");
    }

    if (m == 0) {
        return n;
    }
    if (n == 0) {
        return m;
    }

    std::vector<unsigned> tab((m + 1) * 2);
    unsigned *cur = tab.data(), *prev = tab.data() + m + 1;

    for (size_t i = 0; i <= m; i++) {
        cur[i] = i;
    }
    for (size_t j = 1; j <= n; j++) {
        std::swap(cur, prev);

        cur[0] = j;

        for (size_t i = 1; i <= m; i++) {
            if (a[i - 1] == b[j - 1]) {
                cur[i] = prev[i - 1];
            }
            else {
                cur[i] = min(cur[i - 1], prev[i], prev[i - 1]) + 1;
            }
        }
    }

{'fraction_non_alphanumeric': 0.16113053613053613, 'fraction_numerical': 0.013403263403263404, 'mean_word_length': 1.68203125, 'pattern_counts': {'":': 0, '<': 25, '<?xml version=': 0, '>': 27, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '6372974', 'n_tokens_mistral': 1306, 'n_tokens_neox': 1218, 'n_words': 404}