KFuzzyMatcher

KFuzzyMatcher Namespace Reference

Classes

struct  Range
 
struct  Result
 

Enumerations

enum  RangeType : unsigned char { RangeType::FullyMatched, RangeType::All }
 

Functions

KCOREADDONS_EXPORT Result match (QStringView pattern, QStringView str)
 
KCOREADDONS_EXPORT QVector< KFuzzyMatcher::RangematchedRanges (QStringView pattern, QStringView str, RangeType type=RangeType::FullyMatched)
 
KCOREADDONS_EXPORT bool matchSimple (QStringView pattern, QStringView str)
 

Detailed Description

This namespace contains functions for fuzzy matching a list of strings against a pattern.

This code is ported to Qt from lib_fts: https://github.com/forrestthewoods/lib_fts which tries to replicate SublimeText like fuzzy matching.

Note
All character matches will happen sequentially. That means that this function is not typo tolerant i.e., "gti" will not match "git", but "gt" will. All methods in here are stateless i.e., the input string will not be modified. Also note that strings in all the functions in this namespace will be matched case-insensitively.

Limitations:

  • Currently this will match only strings with length < 256 correctly. This is because we intend on matching a pattern against words / short strings and not paragraphs.
  • No more than 256 matches will happen.

If you are using this with QSortFilterProxyModel, you need to override both QSortFilterProxyModel::lessThan and QSortFilterProxyModel::filterAcceptsRow. A simple example:

bool filterAcceptsRow(int sourceRow, const QModelIndex &sourceParent) const override
{
int score = 0;
const auto idx = sourceModel()->index(sourceRow, 0, sourceParent);
const auto actionName = idx.data().toString().splitRef(QLatin1Char(':')).at(1);
const bool res = kfts::fuzzy_match_sequential(m_pattern, actionName, score);
// store the score in the source model
sourceModel()->setData(idx, score, ScoreRole);
return res;
}
bool lessThan(const QModelIndex &sourceLeft, const QModelIndex &sourceRight) const override
{
// use the score here to sort
const int l = sourceLeft.data(ScoreRole).toInt();
const int r = sourceRight.data(ScoreRole).toInt();
return l < r;
}

Additionally you must not use invalidateFilter() if you go with the above approach. Instead use beginResetModel()/endResetModel():

Q_SLOT void setFilterString(const QString &string)
{
beginResetModel();
m_pattern = string;
endResetModel();
}

Namespace for fuzzy matching of strings

Author
Waqar Ahmed waqar.nosp@m..17a.nosp@m.@gmai.nosp@m.l.co.nosp@m.m

Enumeration Type Documentation

◆ RangeType

enum KFuzzyMatcher::RangeType : unsigned char
strong

The type of matches to consider when requesting for ranges.

See also
matchedRanges
Since
5.84
Enumerator
FullyMatched 

We want ranges only where the pattern fully matches the user supplied string.

All 

We want ranges for all matches, even if the pattern partially matched the user supplied string.

Definition at line 109 of file kfuzzymatcher.h.

Function Documentation

◆ match()

KFuzzyMatcher::Result KFuzzyMatcher::match ( QStringView  pattern,
QStringView  str 
)

This is the main function which does scored fuzzy matching.

The return value of this function contains Result::score which should be used to sort the results. Without sorting of the results this function won't very effective.

If pattern is empty, the function will return true

Parameters
patternto search for. For e.g., text entered by a user to filter a list or model
strthe current string from your list of strings
Returns
A Result type with score of this match and whether the match was successful. If there is no match, score is zero. If the match is successful, score must be used to sort the results.
Since
5.79

Simple substring matching to flush out non-matching strings

Definition at line 237 of file kfuzzymatcher.cpp.

◆ matchedRanges()

QVector< KFuzzyMatcher::Range > KFuzzyMatcher::matchedRanges ( QStringView  pattern,
QStringView  str,
RangeType  type = RangeType::FullyMatched 
)

A function which returns the positions + lengths where the pattern matched inside the str.

The resulting ranges can then be utilized to show the user where the matches occurred. Example:

String: hello
Pattern: Hlo
Output: [Range{0, 1}, Range{3, 2}]

In the above example "Hlo" matched inside the string "hello" in two places i.e., position 0 and position 3. At position 0 it matched 'h', and at position 3 it matched 'lo'.

The ranges themeselves can't do much so you will have to make the result useful in your own way. Some possible uses can be:

  • Transform the result into a vector of QTextLayout::FormatRange and then paint them in the view
  • Use the result to transform the string into html, for example conver the string from above example to "<b>H</b>el<b>lo</b>, and then use QTextDocument to paint it into your view.

Example with the first method:

auto ranges = KFuzzyMatcher::matchedRanges(pattern, string);
std::transform(ranges.begin(), ranges.end(), std::back_inserter(out), [](const KFuzzyMatcher::Range &fr){
return QTextLayout::FormatRange{fr.start, fr.length, QTextCharFormat()};
});
QTextLayout layout(text, font);
layout.beginLayout();
QTextLine line = layout.createLine();
//...
layout.endLayout();
layout.setFormats(layout.formats() + out);
layout.draw(painter, position);

If pattern is empty, the function will return an empty vector

if type is RangeType::All, the function will try to get ranges even if the pattern didn't fully match. For example:

pattern: "git"
string: "gti"
Output: [Range{0, 1}, Range{2, 1}]
Parameters
patternto search for. For e.g., text entered by a user to filter a list or model
strthe current string from your list of strings
typewhether to consider ranges from full matches only or all matches including partial matches
Returns
A vector of ranges containing positions and lengths where the pattern matched. If there was no match, the vector will be empty
Since
5.84

Check if this match is part of the previous match. If it is, we increase the length of the last range.

This is a new match inside the string

Definition at line 261 of file kfuzzymatcher.cpp.

◆ matchSimple()

bool KFuzzyMatcher::matchSimple ( QStringView  pattern,
QStringView  str 
)

Simple fuzzy matching of chars in pattern with chars in str sequentially.

If there is a match, it will return true and false otherwise. There is no scoring. You should use this if score is not important for you and only matching is important.

If pattern is empty, the function will return true

Parameters
patternto search for. For e.g., text entered by a user to filter a list
strthe current string from your list of strings
Returns
true on sucessful match
Since
5.79

Instead of doing

 strIt.toLower() == patternIt.toLower()

we convert patternIt to Upper / Lower as needed and compare with strIt. This saves us from calling toLower() on both strings, making things a little bit faster

Definition at line 211 of file kfuzzymatcher.cpp.

QString pattern(Mode mode=Reading)
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.
A range representing a matched sequence in a string.
Definition: kfuzzymatcher.h:98
QVariant data(int role) const const
int toInt(bool *ok) const const
RangeType
The type of matches to consider when requesting for ranges.
void draw(QPainter *painter, const QPointF &position, const QTextLayout::FormatRange *selection) const const
This file is part of the KDE documentation.
Documentation copyright © 1996-2023 The KDE developers.
Generated on Fri Sep 22 2023 04:05:43 by doxygen 1.8.17 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.