Skip to content

Commit

Permalink
Browse files Browse the repository at this point in the history
Reorder the code; Add more context to the algorithm locator; Add more…
… tests
  • Loading branch information
suricactus authored and nyalldawson committed Mar 17, 2020
1 parent 7684062 commit 9dc1ade
Show file tree
Hide file tree
Showing 7 changed files with 42 additions and 112 deletions.
6 changes: 6 additions & 0 deletions python/core/auto_generated/qgsstringutils.sip.in
Expand Up @@ -258,6 +258,12 @@ a specified ``search`` string. Values are normalized between 0 and 1.
:param candidate: candidate string
:param search: search term string

:return: Normalized value of how likely is the ``search`` to be in the ``candidate``

.. note::

Use this function only to calculate the fuzzy score between two strings and later compare these values, but do not depend on the actual numbers. They are implementation detail that may change in a future release.

.. versionadded:: 3.14
%End

Expand Down
14 changes: 8 additions & 6 deletions python/plugins/processing/gui/AlgorithmLocatorFilter.py
Expand Up @@ -83,14 +83,16 @@ def fetchResults(self, string, context, feedback):
if (context.usingPrefix and not string):
self.resultFetched.emit(result)

for t in a.tags():
result.score = QgsStringUtils.fuzzyScore(t, string)
string = string.lower()
tagScore = 0
tags = [*a.tags(), a.provider().name(), a.group()]

if result.score > 0:
self.resultFetched.emit(result)
continue
for t in tags:
if string in t.lower():
tagScore = 1
break

result.score = QgsStringUtils.fuzzyScore(result.displayString, string)
result.score = QgsStringUtils.fuzzyScore(result.displayString, string) * 0.5 + tagScore * 0.5

if result.score > 0:
self.resultFetched.emit(result)
Expand Down
13 changes: 4 additions & 9 deletions src/app/locator/qgsinbuiltlocatorfilters.cpp
Expand Up @@ -24,7 +24,6 @@
#include "qgslayertree.h"
#include "qgsfeedback.h"
#include "qgisapp.h"
#include "qgsstringutils.h"
#include "qgsmaplayermodel.h"
#include "qgslayoutmanager.h"
#include "qgsmapcanvas.h"
Expand Down Expand Up @@ -64,7 +63,7 @@ void QgsLayerTreeLocatorFilter::fetchResults( const QString &string, const QgsLo
continue;
}

result.score = QgsStringUtils::fuzzyScore( result.displayString, string );
result.score = fuzzyScore( result.displayString, string );

if ( result.score > 0 )
emit resultFetched( result );
Expand Down Expand Up @@ -110,7 +109,7 @@ void QgsLayoutLocatorFilter::fetchResults( const QString &string, const QgsLocat
continue;
}

result.score = QgsStringUtils::fuzzyScore( result.displayString, string );
result.score = fuzzyScore( result.displayString, string );

if ( result.score > 0 )
emit resultFetched( result );
Expand All @@ -127,9 +126,6 @@ void QgsLayoutLocatorFilter::triggerResult( const QgsLocatorResult &result )
QgisApp::instance()->openLayoutDesignerDialog( layout );
}




QgsActionLocatorFilter::QgsActionLocatorFilter( const QList<QWidget *> &parentObjectsForActions, QObject *parent )
: QgsLocatorFilter( parent )
, mActionParents( parentObjectsForActions )
Expand Down Expand Up @@ -221,7 +217,6 @@ void QgsActionLocatorFilter::searchActions( const QString &string, QWidget *pare
{
found << action;
emit resultFetched( result );

}
}
}
Expand Down Expand Up @@ -578,7 +573,7 @@ void QgsSettingsLocatorFilter::fetchResults( const QString &string, const QgsLoc
continue;
}

result.score = QgsStringUtils::fuzzyScore( result.displayString, string );;
result.score = fuzzyScore( result.displayString, string );;

if ( result.score > 0 )
emit resultFetched( result );
Expand Down Expand Up @@ -654,7 +649,7 @@ void QgsBookmarkLocatorFilter::fetchResults( const QString &string, const QgsLoc
continue;
}

result.score = QgsStringUtils::fuzzyScore( result.displayString, string );
result.score = fuzzyScore( result.displayString, string );

if ( result.score > 0 )
emit resultFetched( result );
Expand Down
83 changes: 1 addition & 82 deletions src/core/locator/qgslocatorfilter.cpp
Expand Up @@ -46,88 +46,7 @@ bool QgsLocatorFilter::stringMatches( const QString &candidate, const QString &s

double QgsLocatorFilter::fuzzyScore( const QString &candidate, const QString &search )
{
QString candidateNormalized = candidate.simplified().normalized( QString:: NormalizationForm_C ).toLower();
QString searchNormalized = search.simplified().normalized( QString:: NormalizationForm_C ).toLower();

int candidateLength = candidateNormalized.length();
int searchLength = searchNormalized.length();
int score = 0;

// if the candidate and the search term are empty, no other option than 0 score
if ( candidateLength == 0 || searchLength == 0 )
return score;

int candidateIdx = 0;
int searchIdx = 0;
int maxScore = 0;

bool isPreviousIndexMatching = false;
bool isWordOpen = true;

// loop through each candidate char and calculate the potential max score
while ( candidateIdx < candidateLength )
{
QChar candidateChar = candidateNormalized[ candidateIdx++ ];

// the first char is always the default score
if ( candidateIdx == 1 )
maxScore += FUZZY_SCORE_NEW_MATCH;
// every space character or end of string is a opportunity for a new word
else if ( candidateChar.isSpace() || candidateIdx == candidateLength )
maxScore += FUZZY_SCORE_WORD_MATCH;
// potentially we can match every other character
else
maxScore += FUZZY_SCORE_CONSECUTIVE_MATCH;

// we looped all the characters
if ( searchIdx >= searchLength )
continue;

QChar searchChar = searchNormalized[ searchIdx ];

// match!
if ( candidateChar == searchChar )
{
searchIdx++;

// if we have just successfully finished a word, give higher score
if ( candidateChar.isSpace() || searchIdx == searchLength )
{
if ( isWordOpen )
score += FUZZY_SCORE_WORD_MATCH;
else if ( isPreviousIndexMatching )
score += FUZZY_SCORE_CONSECUTIVE_MATCH;
else
score += FUZZY_SCORE_NEW_MATCH;

isWordOpen = true;
}
// if we have consecutive characters matching, give higher score
else if ( isPreviousIndexMatching )
{
score += FUZZY_SCORE_CONSECUTIVE_MATCH;
}
// normal score for new independent character that matches
else
{
score += FUZZY_SCORE_NEW_MATCH;
}

isPreviousIndexMatching = true;
}
// if the current character does NOT match, we are sure we cannot build a word for now
else
{
isPreviousIndexMatching = false;
isWordOpen = false;
}
}

// we didn't loop through all the search chars, it means, that they are not present in the current candidate
if ( searchIdx != searchLength )
score = 0;

return static_cast<float>( std::max( score, 0 ) ) / std::max( maxScore, 1 );
return QgsStringUtils::fuzzyScore( candidate, search );
}

bool QgsLocatorFilter::enabled() const
Expand Down
18 changes: 10 additions & 8 deletions src/core/qgsstringutils.cpp
Expand Up @@ -434,12 +434,13 @@ double QgsStringUtils::fuzzyScore( const QString &candidate, const QString &sear
while ( candidateIdx < candidateLength )
{
QChar candidateChar = candidateNormalized[ candidateIdx++ ];
bool isCandidateCharWordEnd = candidateChar == ' ' || candidateChar.isPunct();

// the first char is always the default score
if ( candidateIdx == 1 )
maxScore += FUZZY_SCORE_NEW_MATCH;
// every space character, punctuation or end of string is a opportunity for a new word
else if ( candidateChar.isSpace() || candidateChar.isPunct() )
// every space character or underscore is a opportunity for a new word
else if ( isCandidateCharWordEnd )
maxScore += FUZZY_SCORE_WORD_MATCH;
// potentially we can match every other character
else
Expand All @@ -450,14 +451,15 @@ double QgsStringUtils::fuzzyScore( const QString &candidate, const QString &sear
continue;

QChar searchChar = searchNormalized[ searchIdx ];
bool isSearchCharWordEnd = searchChar == ' ' || searchChar.isPunct();

// match!
if ( candidateChar == searchChar )
if ( candidateChar == searchChar || ( isCandidateCharWordEnd && isSearchCharWordEnd ) )
{
searchIdx++;

// if we have just successfully finished a word, give higher score
if ( candidateChar.isSpace() || candidateChar.isPunct() )
if ( isSearchCharWordEnd )
{
if ( isWordOpen )
score += FUZZY_SCORE_WORD_MATCH;
Expand Down Expand Up @@ -493,18 +495,18 @@ double QgsStringUtils::fuzzyScore( const QString &candidate, const QString &sear
{
bool isEndOfWord = ( candidateIdx >= candidateLength )
? true
: candidateNormalized[candidateIdx].isSpace() || candidateNormalized[candidateIdx].isPunct();
: candidateNormalized[candidateIdx] == ' ' || candidateNormalized[candidateIdx].isPunct();

if ( isEndOfWord )
score += FUZZY_SCORE_WORD_MATCH;
}

// QgsLogger::debug( QStringLiteral( "TMP: %1 | %2" ).arg( candidateChar, QString::number(score) ) + QStringLiteral( __FILE__ ) );
// QgsLogger::debug( QStringLiteral( "TMP: %1 | %2 | %3 | %4 | %5" ).arg( candidateChar, searchChar, QString::number(score), QString::number(isCandidateCharWordEnd), QString::number(isSearchCharWordEnd) ) + QStringLiteral( __FILE__ ) );
}

// QgsLogger::debug( QStringLiteral( "RES: %1 | % 2" ).arg( QString::number(maxScore), QString::number(score) ) + QStringLiteral( __FILE__ ) );
// QgsLogger::debug( QStringLiteral( "RES: %1 | %2" ).arg( QString::number(maxScore), QString::number(score) ) + QStringLiteral( __FILE__ ) );
// we didn't loop through all the search chars, it means, that they are not present in the current candidate
if ( searchIdx != searchLength )
if ( searchIdx < searchLength )
score = 0;

return static_cast<float>( std::max( score, 0 ) ) / std::max( maxScore, 1 );
Expand Down
2 changes: 2 additions & 0 deletions src/core/qgsstringutils.h
Expand Up @@ -260,6 +260,8 @@ class CORE_EXPORT QgsStringUtils
* a specified \a search string. Values are normalized between 0 and 1.
* \param candidate candidate string
* \param search search term string
* \return Normalized value of how likely is the \a search to be in the \a candidate
* \note Use this function only to calculate the fuzzy score between two strings and later compare these values, but do not depend on the actual numbers. They are implementation detail that may change in a future release.
* \since 3.14
*/
static double fuzzyScore( const QString &candidate, const QString &search );
Expand Down
18 changes: 11 additions & 7 deletions tests/src/python/test_qgsstringutils.py
Expand Up @@ -186,25 +186,29 @@ def testfuzzyScore(self):
self.assertEqual(QgsStringUtils.fuzzyScore(' foo ', 'foo'), 1)
self.assertEqual(QgsStringUtils.fuzzyScore('foo', ' foo '), 1)
self.assertEqual(QgsStringUtils.fuzzyScore('foo', ' foo '), 1)
self.assertEqual(QgsStringUtils.fuzzyScore('foo_bar', 'foo bar'), 1)
self.assertGreater(QgsStringUtils.fuzzyScore('foo bar', 'foo'), 0)
self.assertGreater(QgsStringUtils.fuzzyScore('foo bar', 'foobar'), 0)
self.assertGreater(QgsStringUtils.fuzzyScore('foo bar', 'fooba'), 0)
self.assertGreater(QgsStringUtils.fuzzyScore('foo_bar', 'ob'), 0)
self.assertGreater(QgsStringUtils.fuzzyScore('foo bar', 'foobar'), 0)
self.assertGreater(QgsStringUtils.fuzzyScore('foo bar', 'foo_bar'), 0)
self.assertGreater(QgsStringUtils.fuzzyScore('foo_bar', 'foo bar'), 0)
self.assertEqual(
QgsStringUtils.fuzzyScore('foo bar', 'foobar'),
QgsStringUtils.fuzzyScore('foo_bar', 'foobar')
)
self.assertEqual(
QgsStringUtils.fuzzyScore('foo bar', 'foobar'),
QgsStringUtils.fuzzyScore('foo,bar', 'foobar')
QgsStringUtils.fuzzyScore('foo bar', 'foo_bar'),
QgsStringUtils.fuzzyScore('foo_bar', 'foo_bar')
)
self.assertEqual(
QgsStringUtils.fuzzyScore('foo bar', 'foobar'),
QgsStringUtils.fuzzyScore('foo!bar', 'foobar')
QgsStringUtils.fuzzyScore('foo bar', 'foo bar'),
QgsStringUtils.fuzzyScore('foo_bar', 'foo bar')
)
# note the accent
self.assertEqual(
QgsStringUtils.fuzzyScore('foo!bér', 'foober'),
QgsStringUtils.fuzzyScore('foo!ber', 'foobér')
QgsStringUtils.fuzzyScore('foo_bér', 'foober'),
QgsStringUtils.fuzzyScore('foo_ber', 'foobér')
)
self.assertGreater(
QgsStringUtils.fuzzyScore('abcd efg hig', 'abcd hig'),
Expand Down

0 comments on commit 9dc1ade

Please sign in to comment.