KCoreAddons

kfuzzymatcher.h
1 /*
2  This file is part of the KDE libraries
3 
4  SPDX-FileCopyrightText: 2017 Forrest Smith <[email protected]>
5  SPDX-FileCopyrightText: 2021 Waqar Ahmed <[email protected]>
6 
7  SPDX-License-Identifier: LGPL-2.0-or-later
8 */
9 #ifndef KFUZZYMATCHER_H
10 #define KFUZZYMATCHER_H
11 
12 #include <kcoreaddons_export.h>
13 
14 #include <QtContainerFwd>
15 
16 class QString;
17 class QStringView;
18 
19 /**
20  * This namespace contains functions for fuzzy matching a list of strings
21  * against a pattern.
22  *
23  * This code is ported to Qt from lib_fts:
24  * https://github.com/forrestthewoods/lib_fts
25  * which tries to replicate SublimeText like fuzzy matching.
26  *
27  * @note
28  * All character matches will happen sequentially. That means that this function is not
29  * typo tolerant i.e., "gti" will not match "git", but "gt" will. All methods in here are
30  * stateless i.e., the input string will not be modified. Also note that strings in all the
31  * functions in this namespace will be matched case-insensitively.
32  *
33  * Limitations:
34  * - Currently this will match only strings with length < 256 correctly. This is because we
35  * intend on matching a pattern against words / short strings and not paragraphs.
36  * - No more than 256 matches will happen.
37  *
38  * If you are using this with @c QSortFilterProxyModel, you need to override both
39  * @c QSortFilterProxyModel::lessThan and @c QSortFilterProxyModel::filterAcceptsRow.
40  * A simple example:
41  *
42  * \code
43  bool filterAcceptsRow(int sourceRow, const QModelIndex &sourceParent) const override
44  {
45  int score = 0;
46  const auto idx = sourceModel()->index(sourceRow, 0, sourceParent);
47  const auto actionName = idx.data().toString().splitRef(QLatin1Char(':')).at(1);
48  const bool res = kfts::fuzzy_match_sequential(m_pattern, actionName, score);
49  // store the score in the source model
50  sourceModel()->setData(idx, score, ScoreRole);
51  return res;
52  }
53 
54  bool lessThan(const QModelIndex &sourceLeft, const QModelIndex &sourceRight) const override
55  {
56  // use the score here to sort
57  const int l = sourceLeft.data(ScoreRole).toInt();
58  const int r = sourceRight.data(ScoreRole).toInt();
59  return l < r;
60  }
61  * \endcode
62  *
63  * Additionally you must not use @c invalidateFilter() if you go with the above approach. Instead
64  * use @c beginResetModel()/@c endResetModel():
65  *
66  * \code
67  * Q_SLOT void setFilterString(const QString &string)
68  {
69  beginResetModel();
70  m_pattern = string;
71  endResetModel();
72  }
73  * \endcode
74  *
75  * @short Namespace for fuzzy matching of strings
76  * @author Waqar Ahmed <[email protected]>
77  */
78 namespace KFuzzyMatcher
79 {
80 /**
81  * @brief The result of a fuzzy match
82  */
83 struct KCOREADDONS_EXPORT Result {
84  /**
85  * Score of this match. This can be negative.if matched is @c false
86  * then the score will be zero.
87  */
88  int score = 0;
89  /** @c true if match was successful */
90  bool matched = false;
91 };
92 
93 /**
94  * @brief A range representing a matched sequence in a string
95  *
96  * @since 5.84
97  */
98 struct KCOREADDONS_EXPORT Range {
99  int start;
100  int length;
101 };
102 
103 /**
104  * @brief The type of matches to consider when requesting for ranges.
105  * @see matchedRanges
106  *
107  * @since 5.84
108  */
109 enum class RangeType : unsigned char {
110  /**
111  * We want ranges only where the pattern fully matches the user
112  * supplied string
113  */
114  FullyMatched,
115  /**
116  * We want ranges for all matches, even if the pattern partially
117  * matched the user supplied string
118  */
119  All
120 };
121 
122 /**
123  * @brief Simple fuzzy matching of chars in @p pattern with chars in @p str
124  * sequentially. If there is a match, it will return true and false otherwise.
125  * There is no scoring. You should use this if score is not important for you
126  * and only matching is important.
127  *
128  * If @p pattern is empty, the function will return @c true
129  *
130  * @param pattern to search for. For e.g., text entered by a user to filter a
131  * list
132  * @param str the current string from your list of strings
133  * @return @c true on sucessful match
134  *
135  * @since 5.79
136  */
137 KCOREADDONS_EXPORT bool matchSimple(QStringView pattern, QStringView str);
138 
139 /**
140  * @brief This is the main function which does scored fuzzy matching.
141  *
142  * The return value of this function contains Result#score which should be used to
143  * sort the results. Without sorting of the results this function won't very effective.
144  *
145  * If @p pattern is empty, the function will return @c true
146  *
147  * @param pattern to search for. For e.g., text entered by a user to filter a
148  * list or model
149  * @param str the current string from your list of strings
150  * @return A Result type with score of this match and whether the match was
151  * successful. If there is no match, score is zero. If the match is successful,
152  * score must be used to sort the results.
153  *
154  * @since 5.79
155  */
156 KCOREADDONS_EXPORT Result match(QStringView pattern, QStringView str);
157 
158 /**
159  * @brief A function which returns the positions + lengths where the @p pattern matched
160  * inside the @p str. The resulting ranges can then be utilized to show the user where
161  * the matches occurred. Example:
162  *
163  * @code
164  * String: hello
165  * Pattern: Hlo
166  *
167  * Output: [Range{0, 1}, Range{3, 2}]
168  * @endcode
169  *
170  * In the above example @c "Hlo" matched inside the string @c "hello" in two places i.e.,
171  * position 0 and position 3. At position 0 it matched 'h', and at position 3 it
172  * matched 'lo'.
173  *
174  * The ranges themeselves can't do much so you will have to make the result useful
175  * in your own way. Some possible uses can be:
176  * - Transform the result into a vector of @c QTextLayout::FormatRange and then paint
177  * them in the view
178  * - Use the result to transform the string into html, for example conver the string from
179  * above example to "<b>H</b>el<b>lo</b>, and then use @c QTextDocument
180  * to paint it into your view.
181  *
182  * Example with the first method:
183  * @code
184  * auto ranges = KFuzzyMatcher::matchedRanges(pattern, string);
185  * QVector<QTextLayout::FormatRange> out;
186  * std::transform(ranges.begin(), ranges.end(), std::back_inserter(out), [](const KFuzzyMatcher::Range &fr){
187  * return QTextLayout::FormatRange{fr.start, fr.length, QTextCharFormat()};
188  * });
189  *
190  * QTextLayout layout(text, font);
191  * layout.beginLayout();
192  * QTextLine line = layout.createLine();
193  * //...
194  * layout.endLayout();
195  *
196  * layout.setFormats(layout.formats() + out);
197  * layout.draw(painter, position);
198  * @endcode
199  *
200  * If @p pattern is empty, the function will return an empty vector
201  *
202  * if @p type is @c RangeType::All, the function will try to get ranges even if
203  * the pattern didn't fully match. For example:
204  * @code
205  * pattern: "git"
206  * string: "gti"
207  * RangeType: All
208  *
209  * Output: [Range{0, 1}, Range{2, 1}]
210  * @endcode
211  *
212  * @param pattern to search for. For e.g., text entered by a user to filter a
213  * list or model
214  * @param str the current string from your list of strings
215  * @param type whether to consider ranges from full matches only or all matches including partial matches
216  * @return A vector of ranges containing positions and lengths where the pattern
217  * matched. If there was no match, the vector will be empty
218  *
219  * @since 5.84
220  */
222 
223 } // namespace KFuzzyMatcher
224 
225 #endif // KFUZZYMATCHER_H
KCOREADDONS_EXPORT QVector< KFuzzyMatcher::Range > matchedRanges(QStringView pattern, QStringView str, RangeType type=RangeType::FullyMatched)
A function which returns the positions + lengths where the pattern matched inside the str.
Q_SCRIPTABLE Q_NOREPLY void start()
A range representing a matched sequence in a string.
Definition: kfuzzymatcher.h:98
KCOREADDONS_EXPORT bool matchSimple(QStringView pattern, QStringView str)
Simple fuzzy matching of chars in pattern with chars in str sequentially.
@ All
We want ranges for all matches, even if the pattern partially matched the user supplied string.
This namespace contains functions for fuzzy matching a list of strings against a pattern.
Definition: kfuzzymatcher.h:78
RangeType
The type of matches to consider when requesting for ranges.
KCOREADDONS_EXPORT Result match(QStringView pattern, QStringView str)
This is the main function which does scored fuzzy matching.
The result of a fuzzy match.
Definition: kfuzzymatcher.h:83
@ FullyMatched
We want ranges only where the pattern fully matches the user supplied string.
This file is part of the KDE documentation.
Documentation copyright © 1996-2022 The KDE developers.
Generated on Mon Jul 4 2022 04:07:21 by doxygen 1.8.17 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.