--Boundary-00=_I86wAkBzJtjvqP9
Content-Type: text/plain;
  charset="us-ascii"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

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

--Boundary-00=_I86wAkBzJtjvqP9
Content-Type: text/x-diff; charset="us-ascii"; name="find_incremenal.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
	filename="find_incremenal.patch"

? 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

--Boundary-00=_I86wAkBzJtjvqP9--