[prev in list] [next in list] [prev in thread] [next in thread]
List: kde-core-devel
Subject: KFind patch for incremental searching
From: "Arend van Beelen jr." <arend () auton ! nl>
Date: 2004-06-06 23:55:52
Message-ID: 200406070155.52580.arend () auton ! nl
[Download RAW message or body]
Hi guys,
I've completed my patch for incremental search in KFind. It does involve quite
some extra logic to KFind though, so I'd like to post it for review before I
commit.
The incremental search will be used by the type-ahead find feature so it will
be more efficient and can better respond to the path through which the user
searches. To accomplish this, all data block set by KFind::setData() are
cached and the search algorithm will track in which block and at which
position every match (of the current search pattern and its substrings) is.
If the incremental search then decrements it will select the same matches as
it encountered during its first run. This means if the user would press F3 a
few times between incrementing the search pattern, this path is followed in
reverse when decrementing the pattern.
Finally, the patch also fixes a small memleak in KFind::setOptions().
What'd you say?
--
Arend van Beelen jr.
http://www.liacs.nl/~dvbeelen
So if you want my address, it's number one at the end of the bar.
-- Marillion
["find_incremenal.patch" (text/x-diff)]
? find_incremenal.patch
Index: kfind.cpp
===================================================================
RCS file: /home/kde/kdelibs/kutils/kfind.cpp,v
retrieving revision 1.24
diff -u -3 -p -u -r1.24 kfind.cpp
--- kfind.cpp 8 Jan 2004 21:07:06 -0000 1.24
+++ kfind.cpp 6 Jun 2004 23:41:54 -0000
@@ -27,6 +27,7 @@
#include <qregexp.h>
#include <qstylesheet.h>
#include <qguardedptr.h>
+#include <qvaluevector.h>
#include <kdebug.h>
//#define DEBUG_FIND
@@ -53,12 +54,39 @@ KFindNextDialog::KFindNextDialog(const Q
////
-struct KFind::Private {
- Private() {
- findDialog = 0;
- }
- QGuardedPtr<QWidget> findDialog;
+struct KFind::Private
+{
+ Private() :
+ findDialog(0),
+ patternChanged(false),
+ matchedPattern(""),
+ incrementalPath(29, true),
+ currentTextId(0)
+ {
+ incrementalPath.setAutoDelete(true);
+ }
+
+ struct Match
+ {
+ Match(int textId, int index, int matchedLength) :
+ textId(textId),
+ index(index),
+ matchedLength(matchedLength)
+ { }
+
+ int textId;
+ int index;
+ int matchedLength;
+ };
+
+ QGuardedPtr<QWidget> findDialog;
+ bool patternChanged;
+ QString matchedPattern;
+ QDict<Match> incrementalPath;
+ QValueVector<QString> texts;
+ uint currentTextId;
};
+
////
KFind::KFind( const QString &pattern, long options, QWidget *parent )
@@ -115,6 +143,11 @@ bool KFind::needData() const
void KFind::setData( const QString& data, int startPos )
{
m_text = data;
+ if ( m_options & KFindDialog::FindIncremental )
+ {
+ d->currentTextId = d->texts.count();
+ d->texts.append( data );
+ }
if ( startPos != -1 )
m_index = startPos;
else if (m_options & KFindDialog::FindBackwards)
@@ -142,7 +175,8 @@ KDialogBase* KFind::findNextDialog( bool
KFind::Result KFind::find()
{
Q_ASSERT( m_index != INDEX_NOMATCH );
- if ( m_lastResult == Match )
+ if ( m_lastResult == Match &&
+ !(m_options & KFindDialog::FindIncremental && d->patternChanged) )
{
// Move on before looking for the next match, _if_ we just found a match
if (m_options & KFindDialog::FindBackwards) {
@@ -155,43 +189,150 @@ KFind::Result KFind::find()
} else
m_index++;
}
+ d->patternChanged = false;
+
+ // if we're doing an incremental search and the current pattern is shorter
+ // than the matchedPattern we can look up the match in the incrementalPath
+ if ( m_options & KFindDialog::FindIncremental )
+ {
+ if ( m_pattern.length() < d->matchedPattern.length() )
+ {
+ Private::Match *match;
+ if ( (match = d->incrementalPath[m_pattern]) != 0 )
+ {
+ m_text = d->texts[match->textId];
+ m_index = match->index;
+ m_matchedLength = match->matchedLength;
+ d->currentTextId = match->textId;
+
+ emit highlight(m_text, m_index, m_matchedLength);
+
+ kdDebug() << "Highlight " << m_pattern << " (1)" << endl;
+
+ while ( m_pattern.length() < d->matchedPattern.length() )
+ {
+ d->incrementalPath.remove(d->matchedPattern);
+ kdDebug() << "Removed " << d->matchedPattern << " from path" << \
endl; + d->matchedPattern.truncate(d->matchedPattern.length() - \
1); + }
+ m_lastResult = Match;
+ return Match;
+ }
+ else
+ {
+ // if we couldn't look up the match, the new pattern isn't a
+ // substring of the matchedPattern, so we reset
+ d->incrementalPath.clear();
+ d->matchedPattern = m_pattern;
+ m_pattern = "";
+ kdDebug() << "Starting new search for " << d->matchedPattern << \
endl; + }
+ }
+ else if ( m_pattern.length() > d->matchedPattern.length() )
+ {
+ if ( m_pattern.startsWith(d->matchedPattern) )
+ {
+ QString temp = m_pattern;
+ m_pattern = m_pattern.left(d->matchedPattern.length() + 1);
+ d->matchedPattern = temp;
+ kdDebug() << "Going to search for " << d->matchedPattern << " from " \
<< m_pattern.left(m_pattern.length() - 1) << endl; + }
+ else
+ {
+ // if the new pattern is longer than but doesn't start with the
+ // matchedPattern, we also reset
+ d->incrementalPath.clear();
+ d->matchedPattern = m_pattern;
+ m_pattern = "";
+ kdDebug() << "Starting new search for " << d->matchedPattern << \
endl; + }
+ }
+ }
#ifdef DEBUG_FIND
kdDebug() << k_funcinfo << "m_index=" << m_index << endl;
#endif
do // this loop is only because validateMatch can fail
{
- // Find the next candidate match.
- if ( m_options & KFindDialog::RegularExpression )
- m_index = KFind::find(m_text, *m_regExp, m_index, m_options, \
&m_matchedLength);
- else
- m_index = KFind::find(m_text, m_pattern, m_index, m_options, \
&m_matchedLength); + do
+ {
+ kdDebug() << "find loop: text: " << m_text << " index: " << m_index << " \
textId: " << d->currentTextId << endl; + // Find the next candidate match.
+ if ( m_options & KFindDialog::RegularExpression )
+ m_index = KFind::find(m_text, *m_regExp, m_index, m_options, \
&m_matchedLength); + else
+ m_index = KFind::find(m_text, m_pattern, m_index, m_options, \
&m_matchedLength); +
+ if ( m_index == -1 && d->currentTextId < d->texts.count() - 1 )
+ {
+ m_text = d->texts[++d->currentTextId];
+ if ( m_options & KFindDialog::FindBackwards )
+ m_index = QMAX((int) m_text.length() - 1, 0);
+ else
+ m_index = 0;
+ }
+ else
+ break;
+ } while ( m_options & KFindDialog::FindIncremental );
+
if ( m_index != -1 )
{
// Flexibility: the app can add more rules to validate a possible match
if ( validateMatch( m_text, m_index, m_matchedLength ) )
{
- m_matches++;
- // Tell the world about the match we found, in case someone wants to
- // highlight it.
- emit highlight(m_text, m_index, m_matchedLength);
+ bool done = true;
- if ( !m_dialogClosed )
- findNextDialog(true)->show();
+ if ( m_options & KFindDialog::FindIncremental )
+ {
+ d->incrementalPath.replace(m_pattern, new \
Private::Match(d->currentTextId, m_index, m_matchedLength)); + \
kdDebug() << "Added " << m_pattern << " to path" << endl; +
+ if ( m_pattern.length() < d->matchedPattern.length() )
+ {
+ m_pattern += d->matchedPattern.mid(m_pattern.length(), 1);
+ done = false;
+ }
+ }
+
+ if ( done )
+ {
+ m_matches++;
+ // Tell the world about the match we found, in case someone \
wants to + // highlight it.
+ emit highlight(m_text, m_index, m_matchedLength);
+
+ kdDebug() << "Highlight " << m_pattern << " (2)" << endl;
+
+ if ( !m_dialogClosed )
+ findNextDialog(true)->show();
#ifdef DEBUG_FIND
- kdDebug() << k_funcinfo << "Match. Next m_index=" << m_index << \
endl; + kdDebug() << k_funcinfo << "Match. Next m_index=" << \
m_index << endl; #endif
- m_lastResult = Match;
- return Match;
+ m_lastResult = Match;
+ return Match;
+ }
}
else // Skip match
+ {
if (m_options & KFindDialog::FindBackwards)
m_index--;
else
m_index++;
- } else
+ }
+ }
+ else
+ {
+ if ( m_options & KFindDialog::FindIncremental )
+ {
+ QString temp = m_pattern;
+ temp.truncate(temp.length() - 1);
+ m_pattern = d->matchedPattern;
+ d->matchedPattern = temp;
+ }
+
m_index = INDEX_NOMATCH;
+ }
}
while (m_index != INDEX_NOMATCH);
@@ -421,12 +562,12 @@ bool KFind::shouldRestart( bool forceAsk
void KFind::setOptions( long options )
{
m_options = options;
+
+ delete m_regExp;
if (m_options & KFindDialog::RegularExpression)
m_regExp = new QRegExp(m_pattern, m_options & KFindDialog::CaseSensitive);
- else {
- delete m_regExp;
+ else
m_regExp = 0;
- }
}
void KFind::closeFindNextDialog()
@@ -444,6 +585,7 @@ int KFind::index() const
void KFind::setPattern( const QString& pattern )
{
m_pattern = pattern;
+ d->patternChanged = true;
setOptions( options() ); // rebuild m_regExp if necessary
}
Index: kfind.h
===================================================================
RCS file: /home/kde/kdelibs/kutils/kfind.h,v
retrieving revision 1.22
diff -u -3 -p -u -r1.22 kfind.h
--- kfind.h 6 Oct 2003 09:22:24 -0000 1.22
+++ kfind.h 6 Jun 2004 23:41:56 -0000
@@ -273,6 +273,10 @@ signals:
/**
* Connect to this signal to implement highlighting of found text during the \
find
* operation.
+ *
+ * WARNING: If you're using the FindIncremental option, the text argument
+ * passed by this signal is not necessarily the data last set through
+ * \link setData(), but can also be an earlier set data block.
*/
void highlight(const QString &text, int matchingIndex, int matchedLength);
Index: kfinddialog.h
===================================================================
RCS file: /home/kde/kdelibs/kutils/kfinddialog.h,v
retrieving revision 1.14
diff -u -3 -p -u -r1.14 kfinddialog.h
--- kfinddialog.h 9 Mar 2004 14:36:14 -0000 1.14
+++ kfinddialog.h 6 Jun 2004 23:41:56 -0000
@@ -78,6 +78,7 @@ public:
// Options.
+ // KDE4: move to KFind
enum Options
{
WholeWordsOnly = 1, // Match whole words only.
@@ -86,6 +87,7 @@ public:
CaseSensitive = 8, // Consider case when matching.
FindBackwards = 16, // Go backwards.
RegularExpression = 32, // Interpret the pattern as a regular expression.
+ FindIncremental = 64, // Find incremental.
// Note that KReplaceDialog uses 256 and 512
// User extensions can use boolean options above this value.
MinimumUserOption = 65536
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic