RapidFuzz
Loading...
Searching...
No Matches
distance.hpp
1/* SPDX-License-Identifier: MIT */
2/* Copyright © 2022-present Max Bachmann */
3
4#pragma once
5#include <rapidfuzz/distance/DamerauLevenshtein.hpp>
6#include <rapidfuzz/distance/Hamming.hpp>
7#include <rapidfuzz/distance/Indel.hpp>
8#include <rapidfuzz/distance/Jaro.hpp>
9#include <rapidfuzz/distance/JaroWinkler.hpp>
10#include <rapidfuzz/distance/LCSseq.hpp>
11#include <rapidfuzz/distance/Levenshtein.hpp>
12#include <rapidfuzz/distance/OSA.hpp>
13#include <rapidfuzz/distance/Postfix.hpp>
14#include <rapidfuzz/distance/Prefix.hpp>
15
16namespace rapidfuzz {
17
18template <typename CharT, typename InputIt1, typename InputIt2>
19std::basic_string<CharT> editops_apply(const Editops& ops, InputIt1 first1, InputIt1 last1, InputIt2 first2,
20 InputIt2 last2)
21{
22 auto len1 = static_cast<size_t>(std::distance(first1, last1));
23 auto len2 = static_cast<size_t>(std::distance(first2, last2));
24
25 std::basic_string<CharT> res_str;
26 res_str.resize(len1 + len2);
27 size_t src_pos = 0;
28 size_t dest_pos = 0;
29
30 for (const auto& op : ops) {
31 /* matches between last and current editop */
32 while (src_pos < op.src_pos) {
33 res_str[dest_pos] = static_cast<CharT>(first1[static_cast<ptrdiff_t>(src_pos)]);
34 src_pos++;
35 dest_pos++;
36 }
37
38 switch (op.type) {
39 case EditType::None:
40 case EditType::Replace:
41 res_str[dest_pos] = static_cast<CharT>(first2[static_cast<ptrdiff_t>(op.dest_pos)]);
42 src_pos++;
43 dest_pos++;
44 break;
45 case EditType::Insert:
46 res_str[dest_pos] = static_cast<CharT>(first2[static_cast<ptrdiff_t>(op.dest_pos)]);
47 dest_pos++;
48 break;
49 case EditType::Delete: src_pos++; break;
50 }
51 }
52
53 /* matches after the last editop */
54 while (src_pos < len1) {
55 res_str[dest_pos] = static_cast<CharT>(first1[static_cast<ptrdiff_t>(src_pos)]);
56 src_pos++;
57 dest_pos++;
58 }
59
60 res_str.resize(dest_pos);
61 return res_str;
62}
63
64template <typename CharT, typename Sentence1, typename Sentence2>
65std::basic_string<CharT> editops_apply(const Editops& ops, const Sentence1& s1, const Sentence2& s2)
66{
67 return editops_apply<CharT>(ops, detail::to_begin(s1), detail::to_end(s1), detail::to_begin(s2),
68 detail::to_end(s2));
69}
70
71template <typename CharT, typename InputIt1, typename InputIt2>
72std::basic_string<CharT> opcodes_apply(const Opcodes& ops, InputIt1 first1, InputIt1 last1, InputIt2 first2,
73 InputIt2 last2)
74{
75 auto len1 = static_cast<size_t>(std::distance(first1, last1));
76 auto len2 = static_cast<size_t>(std::distance(first2, last2));
77
78 std::basic_string<CharT> res_str;
79 res_str.resize(len1 + len2);
80 size_t dest_pos = 0;
81
82 for (const auto& op : ops) {
83 switch (op.type) {
84 case EditType::None:
85 for (auto i = op.src_begin; i < op.src_end; ++i) {
86 res_str[dest_pos++] = static_cast<CharT>(first1[static_cast<ptrdiff_t>(i)]);
87 }
88 break;
89 case EditType::Replace:
90 case EditType::Insert:
91 for (auto i = op.dest_begin; i < op.dest_end; ++i) {
92 res_str[dest_pos++] = static_cast<CharT>(first2[static_cast<ptrdiff_t>(i)]);
93 }
94 break;
95 case EditType::Delete: break;
96 }
97 }
98
99 res_str.resize(dest_pos);
100 return res_str;
101}
102
103template <typename CharT, typename Sentence1, typename Sentence2>
104std::basic_string<CharT> opcodes_apply(const Opcodes& ops, const Sentence1& s1, const Sentence2& s2)
105{
106 return opcodes_apply<CharT>(ops, detail::to_begin(s1), detail::to_end(s1), detail::to_begin(s2),
107 detail::to_end(s2));
108}
109
110} // namespace rapidfuzz