• Skip to content
  • Skip to link menu
KDE 3.5 API Reference
  • KDE API Reference
  • API Reference
  • Sitemap
  • Contact Us
 

KUtils

kfind.cpp

Go to the documentation of this file.
00001 /*
00002     Copyright (C) 2001, S.R.Haque <srhaque@iee.org>.
00003     Copyright (C) 2002, David Faure <david@mandrakesoft.com>
00004     Copyright (C) 2004, Arend van Beelen jr. <arend@auton.nl>
00005     This file is part of the KDE project
00006 
00007     This library is free software; you can redistribute it and/or
00008     modify it under the terms of the GNU Library General Public
00009     License version 2, as published by the Free Software Foundation.
00010 
00011     This library is distributed in the hope that it will be useful,
00012     but WITHOUT ANY WARRANTY; without even the implied warranty of
00013     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014     Library General Public License for more details.
00015 
00016     You should have received a copy of the GNU Library General Public License
00017     along with this library; see the file COPYING.LIB.  If not, write to
00018     the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
00019     Boston, MA 02110-1301, USA.
00020 */
00021 
00022 #include "kfind.h"
00023 #include "kfinddialog.h"
00024 #include <kapplication.h>
00025 #include <klocale.h>
00026 #include <kmessagebox.h>
00027 #include <qlabel.h>
00028 #include <qregexp.h>
00029 #include <qstylesheet.h>
00030 #include <qguardedptr.h>
00031 #include <qptrvector.h>
00032 #include <kdebug.h>
00033 
00034 //#define DEBUG_FIND
00035 
00036 #define INDEX_NOMATCH -1
00037 
00038 class KFindNextDialog : public KDialogBase
00039 {
00040 public:
00041     KFindNextDialog(const QString &pattern, QWidget *parent);
00042 };
00043 
00044 // Create the dialog.
00045 KFindNextDialog::KFindNextDialog(const QString &pattern, QWidget *parent) :
00046     KDialogBase(parent, 0, false,  // non-modal!
00047         i18n("Find Next"),
00048         User1 | Close,
00049         User1,
00050         false,
00051         KStdGuiItem::find())
00052 {
00053     setMainWidget( new QLabel( i18n("<qt>Find next occurrence of '<b>%1</b>'?</qt>").arg(pattern), this ) );
00054 }
00055 
00057 
00058 struct KFind::Private
00059 {
00060     Private() :
00061       findDialog(0),
00062       patternChanged(false),
00063       matchedPattern(""),
00064       incrementalPath(29, true),
00065       emptyMatch(0),
00066       currentId(0),
00067       customIds(false)
00068     {
00069         incrementalPath.setAutoDelete(true);
00070         data.setAutoDelete(true);
00071     }
00072 
00073     ~Private()
00074     {
00075         delete emptyMatch;
00076         emptyMatch = 0;
00077     }
00078 
00079     struct Match
00080     {
00081         Match(int dataId, int index, int matchedLength) :
00082           dataId(dataId),
00083           index(index),
00084           matchedLength(matchedLength)
00085         { }
00086 
00087         int dataId;
00088         int index;
00089         int matchedLength;
00090     };
00091 
00092     struct Data
00093     {
00094         Data() : id(-1), dirty(false) { }
00095         Data(int id, const QString &text, bool dirty = false) :
00096           id(id),
00097           text(text),
00098           dirty(dirty)
00099         { }
00100 
00101         int     id;
00102         QString text;
00103         bool    dirty;
00104     };
00105 
00106     QGuardedPtr<QWidget>  findDialog;
00107     bool                  patternChanged;
00108     QString               matchedPattern;
00109     QDict<Match>          incrementalPath;
00110     Match *               emptyMatch;
00111     QPtrVector<Data>      data;
00112     int                   currentId;
00113     bool                  customIds;
00114 };
00115 
00117 
00118 KFind::KFind( const QString &pattern, long options, QWidget *parent )
00119     : QObject( parent )
00120 {
00121     d = new KFind::Private;
00122     m_options = options;
00123     init( pattern );
00124 }
00125 
00126 KFind::KFind( const QString &pattern, long options, QWidget *parent, QWidget *findDialog )
00127     : QObject( parent )
00128 {
00129     d = new KFind::Private;
00130     d->findDialog = findDialog;
00131     m_options = options;
00132     init( pattern );
00133 }
00134 
00135 void KFind::init( const QString& pattern )
00136 {
00137     m_matches = 0;
00138     m_pattern = pattern;
00139     m_dialog = 0;
00140     m_dialogClosed = false;
00141     m_index = INDEX_NOMATCH;
00142     m_lastResult = NoMatch;
00143     if (m_options & KFindDialog::RegularExpression)
00144         m_regExp = new QRegExp(pattern, m_options & KFindDialog::CaseSensitive);
00145     else {
00146         m_regExp = 0;
00147     }
00148 }
00149 
00150 KFind::~KFind()
00151 {
00152     delete m_dialog;
00153     delete d;
00154 }
00155 
00156 bool KFind::needData() const
00157 {
00158     // always true when m_text is empty.
00159     if (m_options & KFindDialog::FindBackwards)
00160         // m_index==-1 and m_lastResult==Match means we haven't answered nomatch yet
00161         // This is important in the "replace with a prompt" case.
00162         return ( m_index < 0 && m_lastResult != Match );
00163     else
00164         // "index over length" test removed: we want to get a nomatch before we set data again
00165         // This is important in the "replace with a prompt" case.
00166         return m_index == INDEX_NOMATCH;
00167 }
00168 
00169 void KFind::setData( const QString& data, int startPos )
00170 {
00171     setData( -1, data, startPos );
00172 }
00173 
00174 void KFind::setData( int id, const QString& data, int startPos )
00175 {
00176     // cache the data for incremental find
00177     if ( m_options & KFindDialog::FindIncremental )
00178     {
00179         if ( id != -1 )
00180             d->customIds = true;
00181         else
00182             id = d->currentId + 1;
00183 
00184         if ( id >= (int) d->data.size() )
00185             d->data.resize( id + 100 );
00186 
00187         d->data.insert( id, new Private::Data(id, data, true) );
00188     }
00189 
00190     if ( !(m_options & KFindDialog::FindIncremental) || needData() )
00191     {
00192         m_text = data;
00193 
00194         if ( startPos != -1 )
00195             m_index = startPos;
00196         else if (m_options & KFindDialog::FindBackwards)
00197             m_index = m_text.length();
00198         else
00199             m_index = 0;
00200 #ifdef DEBUG_FIND
00201         kdDebug() << "setData: '" << m_text << "' m_index=" << m_index << endl;
00202 #endif
00203         Q_ASSERT( m_index != INDEX_NOMATCH );
00204         m_lastResult = NoMatch;
00205 
00206         d->currentId = id;
00207     }
00208 }
00209 
00210 KDialogBase* KFind::findNextDialog( bool create )
00211 {
00212     if ( !m_dialog && create )
00213     {
00214         m_dialog = new KFindNextDialog( m_pattern, parentWidget() );
00215         connect( m_dialog, SIGNAL( user1Clicked() ), this, SLOT( slotFindNext() ) );
00216         connect( m_dialog, SIGNAL( finished() ), this, SLOT( slotDialogClosed() ) );
00217     }
00218     return m_dialog;
00219 }
00220 
00221 KFind::Result KFind::find()
00222 {
00223     Q_ASSERT( m_index != INDEX_NOMATCH || d->patternChanged );
00224 
00225     if ( m_lastResult == Match && !d->patternChanged )
00226     {
00227         // Move on before looking for the next match, _if_ we just found a match
00228         if (m_options & KFindDialog::FindBackwards) {
00229             m_index--;
00230             if ( m_index == -1 ) // don't call KFind::find with -1, it has a special meaning
00231             {
00232                 m_lastResult = NoMatch;
00233                 return NoMatch;
00234             }
00235         } else
00236             m_index++;
00237     }
00238     d->patternChanged = false;
00239 
00240     if ( m_options & KFindDialog::FindIncremental )
00241     {
00242         // if the current pattern is shorter than the matchedPattern we can
00243         // probably look up the match in the incrementalPath
00244         if ( m_pattern.length() < d->matchedPattern.length() )
00245         {
00246             Private::Match *match = m_pattern.isEmpty() ? d->emptyMatch : d->incrementalPath[m_pattern];
00247             QString previousPattern = d->matchedPattern;
00248             d->matchedPattern = m_pattern;
00249             if ( match != 0 )
00250             {
00251                 bool clean = true;
00252 
00253                 // find the first result backwards on the path that isn't dirty
00254                 while ( d->data[match->dataId]->dirty == true &&
00255                         !m_pattern.isEmpty() )
00256                 {
00257                     m_pattern.truncate( m_pattern.length() - 1 );
00258 
00259                     match = d->incrementalPath[m_pattern];
00260 
00261                     clean = false;
00262                 }
00263 
00264                 // remove all matches that lie after the current match
00265                 while ( m_pattern.length() < previousPattern.length() )
00266                 {
00267                     d->incrementalPath.remove(previousPattern);
00268                     previousPattern.truncate(previousPattern.length() - 1);
00269                 }
00270 
00271                 // set the current text, index, etc. to the found match
00272                 m_text = d->data[match->dataId]->text;
00273                 m_index = match->index;
00274                 m_matchedLength = match->matchedLength;
00275                 d->currentId = match->dataId;
00276 
00277                 // if the result is clean we can return it now
00278                 if ( clean )
00279                 {
00280                     if ( d->customIds )
00281                         emit highlight(d->currentId, m_index, m_matchedLength);
00282                     else
00283                         emit highlight(m_text, m_index, m_matchedLength);
00284 
00285                     m_lastResult = Match;
00286                     d->matchedPattern = m_pattern;
00287                     return Match;
00288                 }
00289             }
00290             // if we couldn't look up the match, the new pattern isn't a
00291             // substring of the matchedPattern, so we start a new search
00292             else
00293             {
00294                 startNewIncrementalSearch();
00295             }
00296         }
00297         // if the new pattern is longer than the matchedPattern we might be
00298         // able to proceed from the last search
00299         else if ( m_pattern.length() > d->matchedPattern.length() )
00300         {
00301             // continue from the previous pattern
00302             if ( m_pattern.startsWith(d->matchedPattern) )
00303             {
00304                 // we can't proceed from the previous position if the previous
00305                 // position already failed
00306                 if ( m_index == INDEX_NOMATCH )
00307                     return NoMatch;
00308 
00309                 QString temp = m_pattern;
00310                 m_pattern.truncate(d->matchedPattern.length() + 1);
00311                 d->matchedPattern = temp;
00312             }
00313             // start a new search
00314             else
00315             {
00316                 startNewIncrementalSearch();
00317             }
00318         }
00319         // if the new pattern is as long as the matchedPattern, we reset if
00320         // they are not equal
00321         else if ( m_pattern != d->matchedPattern )
00322         {
00323              startNewIncrementalSearch();
00324         }
00325     }
00326 
00327 #ifdef DEBUG_FIND
00328     kdDebug() << k_funcinfo << "m_index=" << m_index << endl;
00329 #endif
00330     do
00331     {
00332         // if we have multiple data blocks in our cache, walk through these
00333         // blocks till we either searched all blocks or we find a match
00334         do
00335         {
00336             // Find the next candidate match.
00337             if ( m_options & KFindDialog::RegularExpression )
00338                 m_index = KFind::find(m_text, *m_regExp, m_index, m_options, &m_matchedLength);
00339             else
00340                 m_index = KFind::find(m_text, m_pattern, m_index, m_options, &m_matchedLength);
00341 
00342             if ( m_options & KFindDialog::FindIncremental )
00343                 d->data[d->currentId]->dirty = false;
00344 
00345             if ( m_index == -1 && d->currentId < (int) d->data.count() - 1 )
00346             {
00347                 m_text = d->data[++d->currentId]->text;
00348 
00349                 if ( m_options & KFindDialog::FindBackwards )
00350                     m_index = m_text.length();
00351                 else
00352                     m_index = 0;
00353             }
00354             else
00355                 break;
00356         } while ( !(m_options & KFindDialog::RegularExpression) );
00357 
00358         if ( m_index != -1 )
00359         {
00360             // Flexibility: the app can add more rules to validate a possible match
00361             if ( validateMatch( m_text, m_index, m_matchedLength ) )
00362             {
00363                 bool done = true;
00364 
00365                 if ( m_options & KFindDialog::FindIncremental )
00366                 {
00367                     if ( m_pattern.isEmpty() ) {
00368                         delete d->emptyMatch;
00369                         d->emptyMatch = new Private::Match( d->currentId, m_index, m_matchedLength );
00370                     } else
00371                         d->incrementalPath.replace(m_pattern, new Private::Match(d->currentId, m_index, m_matchedLength));
00372 
00373                     if ( m_pattern.length() < d->matchedPattern.length() )
00374                     {
00375                         m_pattern += d->matchedPattern.mid(m_pattern.length(), 1);
00376                         done = false;
00377                     }
00378                 }
00379 
00380                 if ( done )
00381                 {
00382                     m_matches++;
00383                     // Tell the world about the match we found, in case someone wants to
00384                     // highlight it.
00385                     if ( d->customIds )
00386                         emit highlight(d->currentId, m_index, m_matchedLength);
00387                     else
00388                         emit highlight(m_text, m_index, m_matchedLength);
00389 
00390                     if ( !m_dialogClosed )
00391                         findNextDialog(true)->show();
00392 
00393 #ifdef DEBUG_FIND
00394                     kdDebug() << k_funcinfo << "Match. Next m_index=" << m_index << endl;
00395 #endif
00396                     m_lastResult = Match;
00397                     return Match;
00398                 }
00399             }
00400             else // Skip match
00401             {
00402                 if (m_options & KFindDialog::FindBackwards)
00403                     m_index--;
00404                 else
00405                     m_index++;
00406             }
00407         }
00408         else
00409         {
00410             if ( m_options & KFindDialog::FindIncremental )
00411             {
00412                 QString temp = m_pattern;
00413                 temp.truncate(temp.length() - 1);
00414                 m_pattern = d->matchedPattern;
00415                 d->matchedPattern = temp;
00416             }
00417 
00418             m_index = INDEX_NOMATCH;
00419         }
00420     }
00421     while (m_index != INDEX_NOMATCH);
00422 
00423 #ifdef DEBUG_FIND
00424     kdDebug() << k_funcinfo << "NoMatch. m_index=" << m_index << endl;
00425 #endif
00426     m_lastResult = NoMatch;
00427     return NoMatch;
00428 }
00429 
00430 void KFind::startNewIncrementalSearch()
00431 {
00432     Private::Match *match = d->emptyMatch;
00433     if(match == 0)
00434     {
00435         m_text = QString::null;
00436         m_index = 0;
00437         d->currentId = 0;
00438     }
00439     else
00440     {
00441         m_text = d->data[match->dataId]->text;
00442         m_index = match->index;
00443         d->currentId = match->dataId;
00444     }
00445     m_matchedLength = 0;
00446     d->incrementalPath.clear();
00447     delete d->emptyMatch;
00448     d->emptyMatch = 0;
00449     d->matchedPattern = m_pattern;
00450     m_pattern = QString::null;
00451 }
00452 
00453 // static
00454 int KFind::find(const QString &text, const QString &pattern, int index, long options, int *matchedLength)
00455 {
00456     // Handle regular expressions in the appropriate way.
00457     if (options & KFindDialog::RegularExpression)
00458     {
00459         QRegExp regExp(pattern, options & KFindDialog::CaseSensitive);
00460 
00461         return find(text, regExp, index, options, matchedLength);
00462     }
00463 
00464     bool caseSensitive = (options & KFindDialog::CaseSensitive);
00465 
00466     if (options & KFindDialog::WholeWordsOnly)
00467     {
00468         if (options & KFindDialog::FindBackwards)
00469         {
00470             // Backward search, until the beginning of the line...
00471             while (index >= 0)
00472             {
00473                 // ...find the next match.
00474                 index = text.findRev(pattern, index, caseSensitive);
00475                 if (index == -1)
00476                     break;
00477 
00478                 // Is the match delimited correctly?
00479                 *matchedLength = pattern.length();
00480                 if (isWholeWords(text, index, *matchedLength))
00481                     break;
00482                 index--;
00483             }
00484         }
00485         else
00486         {
00487             // Forward search, until the end of the line...
00488             while (index < (int)text.length())
00489             {
00490                 // ...find the next match.
00491                 index = text.find(pattern, index, caseSensitive);
00492                 if (index == -1)
00493                     break;
00494 
00495                 // Is the match delimited correctly?
00496                 *matchedLength = pattern.length();
00497                 if (isWholeWords(text, index, *matchedLength))
00498                     break;
00499                 index++;
00500             }
00501             if (index >= (int)text.length()) // end of line
00502                 index = -1; // not found
00503         }
00504     }
00505     else
00506     {
00507         // Non-whole-word search.
00508         if (options & KFindDialog::FindBackwards)
00509         {
00510             index = text.findRev(pattern, index, caseSensitive);
00511         }
00512         else
00513         {
00514             index = text.find(pattern, index, caseSensitive);
00515         }
00516         if (index != -1)
00517         {
00518             *matchedLength = pattern.length();
00519         }
00520     }
00521     return index;
00522 }
00523 
00524 // static
00525 int KFind::find(const QString &text, const QRegExp &pattern, int index, long options, int *matchedLength)
00526 {
00527     if (options & KFindDialog::WholeWordsOnly)
00528     {
00529         if (options & KFindDialog::FindBackwards)
00530         {
00531             // Backward search, until the beginning of the line...
00532             while (index >= 0)
00533             {
00534                 // ...find the next match.
00535                 index = text.findRev(pattern, index);
00536                 if (index == -1)
00537                     break;
00538 
00539                 // Is the match delimited correctly?
00540                 //pattern.match(text, index, matchedLength, false);
00541                 /*int pos =*/ pattern.search( text.mid(index) );
00542                 *matchedLength = pattern.matchedLength();
00543                 if (isWholeWords(text, index, *matchedLength))
00544                     break;
00545                 index--;
00546             }
00547         }
00548         else
00549         {
00550             // Forward search, until the end of the line...
00551             while (index < (int)text.length())
00552             {
00553                 // ...find the next match.
00554                 index = text.find(pattern, index);
00555                 if (index == -1)
00556                     break;
00557 
00558                 // Is the match delimited correctly?
00559                 //pattern.match(text, index, matchedLength, false);
00560                 /*int pos =*/ pattern.search( text.mid(index) );
00561                 *matchedLength = pattern.matchedLength();
00562                 if (isWholeWords(text, index, *matchedLength))
00563                     break;
00564                 index++;
00565             }
00566             if (index >= (int)text.length()) // end of line
00567                 index = -1; // not found
00568         }
00569     }
00570     else
00571     {
00572         // Non-whole-word search.
00573         if (options & KFindDialog::FindBackwards)
00574         {
00575             index = text.findRev(pattern, index);
00576         }
00577         else
00578         {
00579             index = text.find(pattern, index);
00580         }
00581         if (index != -1)
00582         {
00583             //pattern.match(text, index, matchedLength, false);
00584             /*int pos =*/ pattern.search( text.mid(index) );
00585             *matchedLength = pattern.matchedLength();
00586         }
00587     }
00588     return index;
00589 }
00590 
00591 bool KFind::isInWord(QChar ch)
00592 {
00593     return ch.isLetter() || ch.isDigit() || ch == '_';
00594 }
00595 
00596 bool KFind::isWholeWords(const QString &text, int starts, int matchedLength)
00597 {
00598     if ((starts == 0) || (!isInWord(text[starts - 1])))
00599     {
00600         int ends = starts + matchedLength;
00601 
00602         if ((ends == (int)text.length()) || (!isInWord(text[ends])))
00603             return true;
00604     }
00605     return false;
00606 }
00607 
00608 void KFind::slotFindNext()
00609 {
00610     emit findNext();
00611 }
00612 
00613 void KFind::slotDialogClosed()
00614 {
00615     emit dialogClosed();
00616     m_dialogClosed = true;
00617 }
00618 
00619 void KFind::displayFinalDialog() const
00620 {
00621     QString message;
00622     if ( numMatches() )
00623         message = i18n( "1 match found.", "%n matches found.", numMatches() );
00624     else
00625         message = i18n("<qt>No matches found for '<b>%1</b>'.</qt>").arg(QStyleSheet::escape(m_pattern));
00626     KMessageBox::information(dialogsParent(), message);
00627 }
00628 
00629 bool KFind::shouldRestart( bool forceAsking, bool showNumMatches ) const
00630 {
00631     // Only ask if we did a "find from cursor", otherwise it's pointless.
00632     // Well, unless the user can modify the document during a search operation,
00633     // hence the force boolean.
00634     if ( !forceAsking && (m_options & KFindDialog::FromCursor) == 0 )
00635     {
00636         displayFinalDialog();
00637         return false;
00638     }
00639     QString message;
00640     if ( showNumMatches )
00641     {
00642         if ( numMatches() )
00643             message = i18n( "1 match found.", "%n matches found.", numMatches() );
00644         else
00645             message = i18n("No matches found for '<b>%1</b>'.").arg(QStyleSheet::escape(m_pattern));
00646     }
00647     else
00648     {
00649         if ( m_options & KFindDialog::FindBackwards )
00650             message = i18n( "Beginning of document reached." );
00651         else
00652             message = i18n( "End of document reached." );
00653     }
00654 
00655     message += "<br><br>"; // can't be in the i18n() of the first if() because of the plural form.
00656     // Hope this word puzzle is ok, it's a different sentence
00657     message +=
00658         ( m_options & KFindDialog::FindBackwards ) ?
00659         i18n("Continue from the end?")
00660         : i18n("Continue from the beginning?");
00661 
00662     int ret = KMessageBox::questionYesNo( dialogsParent(), QString("<qt>")+message+QString("</qt>"),
00663                                           QString::null, KStdGuiItem::cont(), KStdGuiItem::stop() );
00664     bool yes = ( ret == KMessageBox::Yes );
00665     if ( yes )
00666         const_cast<KFind*>(this)->m_options &= ~KFindDialog::FromCursor; // clear FromCursor option
00667     return yes;
00668 }
00669 
00670 void KFind::setOptions( long options )
00671 {
00672     m_options = options;
00673 
00674     delete m_regExp;
00675     if (m_options & KFindDialog::RegularExpression)
00676         m_regExp = new QRegExp(m_pattern, m_options & KFindDialog::CaseSensitive);
00677     else
00678         m_regExp = 0;
00679 }
00680 
00681 void KFind::closeFindNextDialog()
00682 {
00683     delete m_dialog;
00684     m_dialog = 0L;
00685     m_dialogClosed = true;
00686 }
00687 
00688 int KFind::index() const
00689 {
00690     return m_index;
00691 }
00692 
00693 void KFind::setPattern( const QString& pattern )
00694 {
00695     if ( m_options & KFindDialog::FindIncremental && m_pattern != pattern )
00696         d->patternChanged = true;
00697 
00698     m_pattern = pattern;
00699     setOptions( options() ); // rebuild m_regExp if necessary
00700 }
00701 
00702 QWidget* KFind::dialogsParent() const
00703 {
00704     // If the find dialog is still up, it should get the focus when closing a message box
00705     // Otherwise, maybe the "find next?" dialog is up
00706     // Otherwise, the "view" is the parent.
00707     return d->findDialog ? (QWidget*)d->findDialog : ( m_dialog ? m_dialog : parentWidget() );
00708 }
00709 
00710 #include "kfind.moc"

KUtils

Skip menu "KUtils"
  • Main Page
  • Modules
  • Namespace List
  • Class Hierarchy
  • Alphabetical List
  • Class List
  • File List
  • Namespace Members
  • Class Members
  • Related Pages

API Reference

Skip menu "API Reference"
  • dcop
  • DNSSD
  • interfaces
  • Kate
  • kconf_update
  • KDECore
  • KDED
  • kdefx
  • KDEsu
  • kdeui
  • KDocTools
  • KHTML
  • KImgIO
  • KInit
  • kio
  • kioslave
  • KJS
  • KNewStuff
  • KParts
  • KUtils
Generated for API Reference by doxygen 1.5.9
This website is maintained by Adriaan de Groot and Allen Winter.
KDE® and the K Desktop Environment® logo are registered trademarks of KDE e.V. | Legal