Line data Source code
1 : /*
2 : * SPDX-License-Identifier: GPL-3.0-only
3 : * MuseScore-CLA-applies
4 : *
5 : * MuseScore
6 : * Music Composition & Notation
7 : *
8 : * Copyright (C) 2026 MuseScore Limited and others
9 : *
10 : * This program is free software: you can redistribute it and/or modify
11 : * it under the terms of the GNU General Public License version 3 as
12 : * published by the Free Software Foundation.
13 : *
14 : * This program is distributed in the hope that it will be useful,
15 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 : * GNU General Public License for more details.
18 : *
19 : * You should have received a copy of the GNU General Public License
20 : * along with this program. If not, see <https://www.gnu.org/licenses/>.
21 : */
22 :
23 : #include "stringsearch.h"
24 :
25 : #include <algorithm>
26 :
27 18 : bool muse::operator==(const FuzzyMatch& left, const FuzzyMatch& right)
28 : {
29 18 : return left.beginPos == right.beginPos
30 18 : && left.endPos == right.endPos
31 36 : && left.editDistance == right.editDistance;
32 : }
33 :
34 0 : bool muse::operator!=(const FuzzyMatch& left, const FuzzyMatch& right)
35 : {
36 0 : return !(left == right);
37 : }
38 :
39 : namespace muse {
40 12 : FuzzyMatcher& FuzzyMatcher::operator()(const std::u32string_view text, const std::u32string_view pattern, const std::size_t maxDistance)
41 : {
42 12 : return match(text, pattern, maxDistance);
43 : }
44 :
45 12 : FuzzyMatcher& FuzzyMatcher::match(const std::u32string_view text, const std::u32string_view pattern, const std::size_t maxDistance)
46 : {
47 12 : m_textSize = text.size();
48 12 : m_patternSize = pattern.size();
49 12 : m_suffixTable.clear();
50 12 : m_suffixTable.resize((m_patternSize + 1) * (m_textSize + 1));
51 12 : m_maxDistance = maxDistance;
52 :
53 195 : for (std::size_t textSuffixSize = 0; textSuffixSize <= m_textSize; ++textSuffixSize) {
54 183 : const std::size_t endPos = text.size() - textSuffixSize;
55 : // 0 insertions to transform empty pattern to text suffix.
56 : // This allows the match to be at any position in text.
57 183 : m_suffixTable[index(0, textSuffixSize)] = SuffixMatch{ endPos, 0 };
58 : }
59 :
60 68 : for (std::size_t patternSuffixSize = 1; patternSuffixSize <= m_patternSize; ++patternSuffixSize) {
61 : // patternSuffixSize deletions to transform pattern suffix to empty text
62 56 : m_suffixTable[index(patternSuffixSize, 0)] = SuffixMatch{ 0, patternSuffixSize };
63 :
64 56 : const std::size_t patternIdx = pattern.size() - patternSuffixSize;
65 1048 : for (std::size_t textSuffixSize = 1; textSuffixSize <= m_textSize; ++textSuffixSize) {
66 992 : const std::size_t textIdx = text.size() - textSuffixSize;
67 :
68 992 : if (pattern[patternIdx] == text[textIdx]) {
69 109 : m_suffixTable[index(patternSuffixSize, textSuffixSize)] = m_suffixTable[index(patternSuffixSize - 1, textSuffixSize - 1)];
70 109 : continue;
71 : }
72 :
73 883 : const SuffixMatch insertMatch = m_suffixTable[index(patternSuffixSize, textSuffixSize - 1)];
74 883 : const SuffixMatch replaceMatch = m_suffixTable[index(patternSuffixSize - 1, textSuffixSize - 1)];
75 883 : const SuffixMatch deleteMatch = m_suffixTable[index(patternSuffixSize - 1, textSuffixSize)];
76 883 : SuffixMatch minMatch = std::min(insertMatch, std::min(replaceMatch, deleteMatch));
77 :
78 742 : if (patternSuffixSize > 1 && textSuffixSize > 1
79 701 : && pattern[patternIdx] == text[textIdx + 1]
80 1625 : && pattern[patternIdx + 1] == text[textIdx]) {
81 4 : const SuffixMatch transpositionMatch = m_suffixTable[index(patternSuffixSize - 2, textSuffixSize - 2)];
82 4 : minMatch = std::min(transpositionMatch, minMatch);
83 : }
84 :
85 883 : m_suffixTable[index(patternSuffixSize, textSuffixSize)] = SuffixMatch{ minMatch.endPos, minMatch.editDistance + 1 };
86 : }
87 : }
88 :
89 12 : return *this;
90 : }
91 :
92 32 : std::optional<FuzzyMatch> FuzzyMatcher::findMatch(const std::size_t textBeginPos) const
93 : {
94 32 : if (m_suffixTable.empty() || textBeginPos > m_textSize) {
95 5 : return std::nullopt;
96 : }
97 :
98 192 : for (std::size_t beginPos = textBeginPos; beginPos <= m_textSize; ++beginPos) {
99 183 : const std::size_t textSuffixSize = m_textSize - beginPos;
100 183 : const SuffixMatch match = m_suffixTable[index(m_patternSize, textSuffixSize)];
101 183 : if (match.editDistance <= m_maxDistance) {
102 18 : return FuzzyMatch{ beginPos, match.endPos, match.editDistance };
103 : }
104 : }
105 :
106 9 : return std::nullopt;
107 : }
108 :
109 1 : bool FuzzyMatcher::empty() const
110 : {
111 1 : return !findMatch(0).has_value();
112 : }
113 :
114 0 : void FuzzyMatcher::clear()
115 : {
116 0 : m_textSize = 0;
117 0 : m_patternSize = 0;
118 0 : m_suffixTable.clear();
119 0 : }
120 :
121 12 : FuzzyMatcher::const_iterator FuzzyMatcher::begin() const
122 : {
123 12 : return Iterator(*this);
124 : }
125 :
126 42 : FuzzyMatcher::const_iterator FuzzyMatcher::end() const
127 : {
128 42 : return Iterator();
129 : }
130 :
131 4176 : std::size_t FuzzyMatcher::index(const std::size_t patternSuffixSize, const std::size_t textSuffixSize) const
132 : {
133 4176 : return (m_textSize + 1) * patternSuffixSize + textSuffixSize;
134 : }
135 :
136 12 : FuzzyMatcher::Iterator::Iterator(const FuzzyMatcher& matcher)
137 12 : : m_matcher{&matcher}
138 : {
139 12 : next(0);
140 12 : }
141 :
142 18 : FuzzyMatcher::Iterator::reference FuzzyMatcher::Iterator::operator*() const
143 : {
144 18 : return *m_match;
145 : }
146 :
147 0 : FuzzyMatcher::Iterator::pointer FuzzyMatcher::Iterator::operator->() const
148 : {
149 0 : return m_match.operator->();
150 : }
151 :
152 18 : FuzzyMatcher::Iterator& FuzzyMatcher::Iterator::operator++()
153 : {
154 18 : next(m_match->beginPos + 1);
155 18 : return *this;
156 : }
157 :
158 0 : FuzzyMatcher::Iterator FuzzyMatcher::Iterator::operator++(int)
159 : {
160 0 : Iterator prev = *this;
161 0 : operator++();
162 :
163 0 : return prev;
164 : }
165 :
166 42 : bool FuzzyMatcher::Iterator::operator==(const Iterator& right) const
167 : {
168 42 : return m_matcher == right.m_matcher && m_match == right.m_match;
169 : }
170 :
171 42 : bool FuzzyMatcher::Iterator::operator!=(const Iterator& right) const
172 : {
173 42 : return !(*this == right);
174 : }
175 :
176 30 : void FuzzyMatcher::Iterator::next(const std::size_t textBeginPos)
177 : {
178 30 : m_match = m_matcher->findMatch(textBeginPos);
179 30 : if (!m_match) {
180 12 : m_matcher = nullptr;
181 : }
182 30 : }
183 : }
|
