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

KDEUI

kcompletion.cpp

Go to the documentation of this file.
00001 /* This file is part of the KDE libraries
00002    Copyright (C) 1999,2000,2001 Carsten Pfeiffer <pfeiffer@kde.org>
00003 
00004    This library is free software; you can redistribute it and/or
00005    modify it under the terms of the GNU Library General Public
00006    License as published by the Free Software Foundation; either
00007    version 2 of the License, or (at your option) any later version.
00008 
00009    This library is distributed in the hope that it will be useful,
00010    but WITHOUT ANY WARRANTY; without even the implied warranty of
00011    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012    Library General Public License for more details.
00013 
00014    You should have received a copy of the GNU Library General Public License
00015    along with this library; see the file COPYING.LIB.  If not, write to
00016    the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
00017    Boston, MA 02110-1301, USA.
00018 */
00019 
00020 
00021 #include "kcompletion.h"
00022 #include "kcompletion_p.h"
00023 
00024 #include <kdebug.h>
00025 #include <klocale.h>
00026 #include <knotification.h>
00027 #include <kglobal.h>
00028 #include <kstringhandler.h>
00029 #include <QtCore/QMutableVectorIterator>
00030 
00031 class KCompletionPrivate
00032 {
00033 public:
00034     KCompletionPrivate()
00035         : myCompletionMode( KGlobalSettings::completionMode() )
00036         , myTreeRoot( new KCompTreeNode )
00037         , myBeep( true )
00038         , myIgnoreCase( false )
00039         , myHasMultipleMatches( false )
00040         , myRotationIndex( 0 )
00041     {
00042     }
00043     ~KCompletionPrivate()
00044     {
00045         delete myTreeRoot;
00046     }
00047     // list used for nextMatch() and previousMatch()
00048     KCompletionMatchesWrapper matches;
00049 
00050     KGlobalSettings::Completion myCompletionMode;
00051 
00052     KCompletion::CompOrder myOrder;
00053     QString                myLastString;
00054     QString                myLastMatch;
00055     QString                myCurrentMatch;
00056     KCompTreeNode *        myTreeRoot;
00057     //QStringList            myRotations;
00058     bool                   myBeep : 1;
00059     bool                   myIgnoreCase : 1;
00060     bool                   myHasMultipleMatches;
00061     int                    myRotationIndex;
00062 };
00063 
00064 KCompletion::KCompletion()
00065     :d(new KCompletionPrivate)
00066 {
00067     setOrder( Insertion );
00068 }
00069 
00070 KCompletion::~KCompletion()
00071 {
00072     delete d;
00073 }
00074 
00075 void KCompletion::setOrder( CompOrder order )
00076 {
00077     d->myOrder = order;
00078     d->matches.setSorting( order );
00079 }
00080 
00081 KCompletion::CompOrder KCompletion::order() const
00082 {
00083     return d->myOrder;
00084 }
00085 
00086 void KCompletion::setIgnoreCase( bool ignoreCase )
00087 {
00088     d->myIgnoreCase = ignoreCase;
00089 }
00090 
00091 bool KCompletion::ignoreCase() const
00092 {
00093     return d->myIgnoreCase;
00094 }
00095 
00096 void KCompletion::setItems( const QStringList& items )
00097 {
00098     clear();
00099     insertItems( items );
00100 }
00101 
00102 
00103 void KCompletion::insertItems( const QStringList& items )
00104 {
00105     bool weighted = (d->myOrder == Weighted);
00106     QStringList::ConstIterator it;
00107     if ( weighted ) { // determine weight
00108         for ( it = items.begin(); it != items.end(); ++it )
00109             addWeightedItem( *it );
00110     }
00111     else {
00112         for ( it = items.begin(); it != items.end(); ++it )
00113             addItem( *it, 0 );
00114     }
00115 }
00116 
00117 QStringList KCompletion::items() const
00118 {
00119     KCompletionMatchesWrapper list; // unsorted
00120     bool addWeight = (d->myOrder == Weighted);
00121     extractStringsFromNode( d->myTreeRoot, QString(), &list, addWeight );
00122 
00123     return list.list();
00124 }
00125 
00126 bool KCompletion::isEmpty() const
00127 {
00128   return (d->myTreeRoot->childrenCount() == 0);
00129 }
00130 
00131 void KCompletion::postProcessMatch( QString * ) const
00132 {
00133 }
00134 
00135 void KCompletion::postProcessMatches( QStringList * ) const
00136 {
00137 }
00138 
00139 void KCompletion::postProcessMatches( KCompletionMatches * ) const
00140 {
00141 }
00142 
00143 void KCompletion::addItem( const QString& item )
00144 {
00145     d->matches.clear();
00146     d->myRotationIndex = 0;
00147     d->myLastString.clear();
00148 
00149     addItem( item, 0 );
00150 }
00151 
00152 void KCompletion::addItem( const QString& item, uint weight )
00153 {
00154     if ( item.isEmpty() )
00155         return;
00156 
00157     KCompTreeNode *node = d->myTreeRoot;
00158     uint len = item.length();
00159 
00160     bool sorted = (d->myOrder == Sorted);
00161     bool weighted = ((d->myOrder == Weighted) && weight > 1);
00162 
00163     // knowing the weight of an item, we simply add this weight to all of its
00164     // nodes.
00165 
00166     for ( uint i = 0; i < len; i++ ) {
00167         node = node->insert( item.at(i), sorted );
00168         if ( weighted )
00169             node->confirm( weight -1 ); // node->insert() sets weighting to 1
00170     }
00171 
00172     // add 0x0-item as delimiter with evtl. weight
00173     node = node->insert( 0x0, true );
00174     if ( weighted )
00175         node->confirm( weight -1 );
00176 //     qDebug("*** added: %s (%i)", item.toLatin1().constData(), node->weight());
00177 }
00178 
00179 void KCompletion::addWeightedItem( const QString& item )
00180 {
00181     if ( d->myOrder != Weighted ) {
00182         addItem( item, 0 );
00183         return;
00184     }
00185 
00186     uint len = item.length();
00187     uint weight = 0;
00188 
00189     // find out the weighting of this item (appended to the string as ":num")
00190     int index = item.lastIndexOf(':');
00191     if ( index > 0 ) {
00192         bool ok;
00193         weight = item.mid( index + 1 ).toUInt( &ok );
00194         if ( !ok )
00195             weight = 0;
00196 
00197         len = index; // only insert until the ':'
00198     }
00199 
00200     addItem( item.left( len ), weight );
00201     return;
00202 }
00203 
00204 
00205 void KCompletion::removeItem( const QString& item )
00206 {
00207     d->matches.clear();
00208     d->myRotationIndex = 0;
00209     d->myLastString.clear();
00210 
00211     d->myTreeRoot->remove( item );
00212 }
00213 
00214 
00215 void KCompletion::clear()
00216 {
00217     d->matches.clear();
00218     d->myRotationIndex = 0;
00219     d->myLastString.clear();
00220 
00221     delete d->myTreeRoot;
00222     d->myTreeRoot = new KCompTreeNode;
00223 }
00224 
00225 
00226 QString KCompletion::makeCompletion( const QString& string )
00227 {
00228     if ( d->myCompletionMode == KGlobalSettings::CompletionNone )
00229         return QString();
00230 
00231     //kDebug(0) << "KCompletion: completing: " << string;
00232 
00233     d->matches.clear();
00234     d->myRotationIndex = 0;
00235     d->myHasMultipleMatches = false;
00236     d->myLastMatch = d->myCurrentMatch;
00237 
00238     // in Shell-completion-mode, emit all matches when we get the same
00239     // complete-string twice
00240     if ( d->myCompletionMode == KGlobalSettings::CompletionShell &&
00241          string == d->myLastString ) {
00242         // Don't use d->matches since calling postProcessMatches()
00243         // on d->matches here would interfere with call to
00244         // postProcessMatch() during rotation
00245 
00246         findAllCompletions( string, &d->matches, d->myHasMultipleMatches );
00247         QStringList l = d->matches.list();
00248         postProcessMatches( &l );
00249         emit matches( l );
00250 
00251         if ( l.isEmpty() )
00252             doBeep( NoMatch );
00253 
00254         return QString();
00255     }
00256 
00257     QString completion;
00258     // in case-insensitive popup mode, we search all completions at once
00259     if ( d->myCompletionMode == KGlobalSettings::CompletionPopup ||
00260          d->myCompletionMode == KGlobalSettings::CompletionPopupAuto ) {
00261         findAllCompletions( string, &d->matches, d->myHasMultipleMatches );
00262         if ( !d->matches.isEmpty() )
00263             completion = d->matches.first();
00264     }
00265     else
00266         completion = findCompletion( string );
00267 
00268     if ( d->myHasMultipleMatches )
00269         emit multipleMatches();
00270 
00271     d->myLastString = string;
00272     d->myCurrentMatch = completion;
00273 
00274     postProcessMatch( &completion );
00275 
00276     if ( !string.isEmpty() ) { // only emit match when string is not empty
00277         //kDebug(0) << "KCompletion: Match: " << completion;
00278         emit match( completion );
00279     }
00280 
00281     if ( completion.isNull() )
00282         doBeep( NoMatch );
00283 
00284     return completion;
00285 }
00286 
00287 
00288 
00289 QStringList KCompletion::substringCompletion( const QString& string ) const
00290 {
00291     // get all items in the tree, eventually in sorted order
00292     KCompletionMatchesWrapper allItems( d->myOrder );
00293     extractStringsFromNode( d->myTreeRoot, QString(), &allItems, false );
00294 
00295     QStringList list = allItems.list();
00296 
00297     // subStringMatches is invoked manually, via a shortcut, so we should
00298     // beep here, if necessary.
00299     if ( list.isEmpty() ) {
00300         doBeep( NoMatch );
00301         return list;
00302     }
00303 
00304     if ( string.isEmpty() ) { // shortcut
00305         postProcessMatches( &list );
00306         return list;
00307     }
00308 
00309     QStringList matches;
00310     QStringList::ConstIterator it = list.constBegin();
00311 
00312     for( ; it != list.constEnd(); ++it ) {
00313         QString item = *it;
00314         if ( item.indexOf( string, 0, Qt::CaseInsensitive ) != -1 ) { // always case insensitive
00315             postProcessMatch( &item );
00316             matches.append( item );
00317         }
00318     }
00319 
00320     if ( matches.isEmpty() )
00321         doBeep( NoMatch );
00322 
00323     return matches;
00324 }
00325 
00326 
00327 void KCompletion::setCompletionMode( KGlobalSettings::Completion mode )
00328 {
00329     d->myCompletionMode = mode;
00330 }
00331 
00332 KGlobalSettings::Completion KCompletion::completionMode() const {
00333     return d->myCompletionMode;
00334 }
00335 
00336 QStringList KCompletion::allMatches()
00337 {
00338     // Don't use d->matches since calling postProcessMatches()
00339     // on d->matches here would interfere with call to
00340     // postProcessMatch() during rotation
00341     KCompletionMatchesWrapper matches( d->myOrder );
00342     bool dummy;
00343     findAllCompletions( d->myLastString, &matches, dummy );
00344     QStringList l = matches.list();
00345     postProcessMatches( &l );
00346     return l;
00347 }
00348 
00349 KCompletionMatches KCompletion::allWeightedMatches()
00350 {
00351     // Don't use d->matches since calling postProcessMatches()
00352     // on d->matches here would interfere with call to
00353     // postProcessMatch() during rotation
00354     KCompletionMatchesWrapper matches( d->myOrder );
00355     bool dummy;
00356     findAllCompletions( d->myLastString, &matches, dummy );
00357     KCompletionMatches ret( matches );
00358     postProcessMatches( &ret );
00359     return ret;
00360 }
00361 
00362 QStringList KCompletion::allMatches( const QString &string )
00363 {
00364     KCompletionMatchesWrapper matches( d->myOrder );
00365     bool dummy;
00366     findAllCompletions( string, &matches, dummy );
00367     QStringList l = matches.list();
00368     postProcessMatches( &l );
00369     return l;
00370 }
00371 
00372 KCompletionMatches KCompletion::allWeightedMatches( const QString &string )
00373 {
00374     KCompletionMatchesWrapper matches( d->myOrder );
00375     bool dummy;
00376     findAllCompletions( string, &matches, dummy );
00377     KCompletionMatches ret( matches );
00378     postProcessMatches( &ret );
00379     return ret;
00380 }
00381 
00382 void KCompletion::setSoundsEnabled( bool enable )
00383 {
00384     d->myBeep = enable;
00385 }
00386 
00387 bool KCompletion::soundsEnabled() const
00388 {
00389     return d->myBeep;
00390 }
00391 
00392 bool KCompletion::hasMultipleMatches() const
00393 {
00394     return d->myHasMultipleMatches;
00395 }
00396 
00399 
00400 
00401 QString KCompletion::nextMatch()
00402 {
00403     QString completion;
00404     d->myLastMatch = d->myCurrentMatch;
00405 
00406     if ( d->matches.isEmpty() ) {
00407         findAllCompletions( d->myLastString, &d->matches, d->myHasMultipleMatches );
00408         if ( !d->matches.isEmpty() )
00409         completion = d->matches.first();
00410         d->myCurrentMatch = completion;
00411         d->myRotationIndex = 0;
00412         postProcessMatch( &completion );
00413         emit match( completion );
00414         return completion;
00415     }
00416 
00417     QStringList matches = d->matches.list();
00418     d->myLastMatch = matches[ d->myRotationIndex++ ];
00419 
00420     if ( d->myRotationIndex == matches.count() -1 )
00421         doBeep( Rotation ); // indicate last matching item -> rotating
00422 
00423     else if ( d->myRotationIndex == matches.count() )
00424         d->myRotationIndex = 0;
00425 
00426     completion = matches[ d->myRotationIndex ];
00427     d->myCurrentMatch = completion;
00428     postProcessMatch( &completion );
00429     emit match( completion );
00430     return completion;
00431 }
00432 
00433 const QString& KCompletion::lastMatch() const
00434 {
00435     return d->myLastMatch;
00436 }
00437 
00438 
00439 QString KCompletion::previousMatch()
00440 {
00441     QString completion;
00442     d->myLastMatch = d->myCurrentMatch;
00443 
00444     if ( d->matches.isEmpty() ) {
00445         findAllCompletions( d->myLastString, &d->matches, d->myHasMultipleMatches );
00446         if ( !d->matches.isEmpty() )
00447             completion = d->matches.last();
00448         d->myCurrentMatch = completion;
00449         d->myRotationIndex = 0;
00450         postProcessMatch( &completion );
00451         emit match( completion );
00452         return completion;
00453     }
00454 
00455     QStringList matches = d->matches.list();
00456     d->myLastMatch = matches[ d->myRotationIndex ];
00457     if ( d->myRotationIndex == 1 )
00458         doBeep( Rotation ); // indicate first item -> rotating
00459 
00460     else if ( d->myRotationIndex == 0 )
00461         d->myRotationIndex = matches.count();
00462 
00463     d->myRotationIndex--;
00464 
00465     completion = matches[ d->myRotationIndex ];
00466     d->myCurrentMatch = completion;
00467     postProcessMatch( &completion );
00468     emit match( completion );
00469     return completion;
00470 }
00471 
00472 
00473 
00474 // tries to complete "string" from the tree-root
00475 QString KCompletion::findCompletion( const QString& string )
00476 {
00477     QChar ch;
00478     QString completion;
00479     const KCompTreeNode *node = d->myTreeRoot;
00480 
00481     // start at the tree-root and try to find the search-string
00482     for( int i = 0; i < string.length(); i++ ) {
00483         ch = string.at( i );
00484         node = node->find( ch );
00485 
00486         if ( node )
00487             completion += ch;
00488         else
00489             return QString(); // no completion
00490     }
00491 
00492     // Now we have the last node of the to be completed string.
00493     // Follow it as long as it has exactly one child (= longest possible
00494     // completion)
00495 
00496     while ( node->childrenCount() == 1 ) {
00497         node = node->firstChild();
00498         if ( !node->isNull() )
00499             completion += *node;
00500     }
00501     // if multiple matches and auto-completion mode
00502     // -> find the first complete match
00503     if ( node && node->childrenCount() > 1 ) {
00504         d->myHasMultipleMatches = true;
00505 
00506         if ( d->myCompletionMode == KGlobalSettings::CompletionAuto ) {
00507             d->myRotationIndex = 1;
00508             if (d->myOrder != Weighted) {
00509                 while ( (node = node->firstChild()) ) {
00510                     if ( !node->isNull() )
00511                         completion += *node;
00512                     else
00513                         break;
00514                 }
00515             }
00516             else {
00517                 // don't just find the "first" match, but the one with the
00518                 // highest priority
00519 
00520                 const KCompTreeNode* temp_node = 0L;
00521                 while(1) {
00522                     int count = node->childrenCount();
00523                     temp_node = node->firstChild();
00524                     uint weight = temp_node->weight();
00525                     const KCompTreeNode* hit = temp_node;
00526                     for( int i = 1; i < count; i++ ) {
00527                         temp_node = node->childAt(i);
00528                         if( temp_node->weight() > weight ) {
00529                             hit = temp_node;
00530                             weight = hit->weight();
00531                         }
00532                     }
00533                     // 0x0 has the highest priority -> we have the best match
00534                     if ( hit->isNull() )
00535                         break;
00536 
00537                     node = hit;
00538                     completion += *node;
00539                 }
00540             }
00541         }
00542 
00543         else
00544             doBeep( PartialMatch ); // partial match -> beep
00545     }
00546 
00547     return completion;
00548 }
00549 
00550 
00551 void KCompletion::findAllCompletions(const QString& string,
00552                                      KCompletionMatchesWrapper *matches,
00553                                      bool& hasMultipleMatches) const
00554 {
00555     //kDebug(0) << "*** finding all completions for " << string;
00556 
00557     if ( string.isEmpty() )
00558         return;
00559 
00560     if ( d->myIgnoreCase ) { // case insensitive completion
00561         extractStringsFromNodeCI( d->myTreeRoot, QString(), string, matches );
00562         hasMultipleMatches = (matches->count() > 1);
00563         return;
00564     }
00565 
00566     QChar ch;
00567     QString completion;
00568     const KCompTreeNode *node = d->myTreeRoot;
00569 
00570     // start at the tree-root and try to find the search-string
00571     for( int i = 0; i < string.length(); i++ ) {
00572         ch = string.at( i );
00573         node = node->find( ch );
00574 
00575         if ( node )
00576             completion += ch;
00577         else
00578             return; // no completion -> return empty list
00579     }
00580 
00581     // Now we have the last node of the to be completed string.
00582     // Follow it as long as it has exactly one child (= longest possible
00583     // completion)
00584 
00585     while ( node->childrenCount() == 1 ) {
00586         node = node->firstChild();
00587         if ( !node->isNull() )
00588             completion += *node;
00589         // kDebug() << completion << node->latin1();
00590     }
00591 
00592 
00593     // there is just one single match)
00594     if ( node->childrenCount() == 0 )
00595         matches->append( node->weight(), completion );
00596 
00597     else {
00598         // node has more than one child
00599         // -> recursively find all remaining completions
00600         hasMultipleMatches = true;
00601         extractStringsFromNode( node, completion, matches );
00602     }
00603 }
00604 
00605 
00606 void KCompletion::extractStringsFromNode( const KCompTreeNode *node,
00607                                           const QString& beginning,
00608                                           KCompletionMatchesWrapper *matches,
00609                                           bool addWeight ) const
00610 {
00611     if ( !node || !matches )
00612         return;
00613 
00614     // kDebug() << "Beginning: " << beginning;
00615     const KCompTreeChildren *list = node->children();
00616     QString string;
00617     QString w;
00618 
00619     // loop thru all children
00620     for ( KCompTreeNode *cur = list->begin(); cur ; cur = cur->next) {
00621         string = beginning;
00622         node = cur;
00623         if ( !node->isNull() )
00624             string += *node;
00625 
00626         while ( node && node->childrenCount() == 1 ) {
00627             node = node->firstChild();
00628             if ( node->isNull() )
00629                 break;
00630             string += *node;
00631         }
00632 
00633         if ( node && node->isNull() ) { // we found a leaf
00634             if ( addWeight ) {
00635                 // add ":num" to the string to store the weighting
00636                 string += ':';
00637                 w.setNum( node->weight() );
00638                 string.append( w );
00639             }
00640             matches->append( node->weight(), string );
00641         }
00642 
00643         // recursively find all other strings.
00644         if ( node && node->childrenCount() > 1 )
00645             extractStringsFromNode( node, string, matches, addWeight );
00646     }
00647 }
00648 
00649 void KCompletion::extractStringsFromNodeCI( const KCompTreeNode *node,
00650                                             const QString& beginning,
00651                                             const QString& restString,
00652                                             KCompletionMatchesWrapper *matches ) const
00653 {
00654     if ( restString.isEmpty() ) {
00655         extractStringsFromNode( node, beginning, matches, false /*noweight*/ );
00656         return;
00657     }
00658 
00659     QChar ch1 = restString.at(0);
00660     QString newRest = restString.mid(1);
00661     KCompTreeNode *child1, *child2;
00662 
00663     child1 = node->find( ch1 ); // the correct match
00664     if ( child1 )
00665         extractStringsFromNodeCI( child1, beginning + *child1, newRest,
00666                                   matches );
00667 
00668     // append the case insensitive matches, if available
00669     if ( ch1.isLetter() ) {
00670         // find out if we have to lower or upper it. Is there a better way?
00671         QChar ch2 = ch1.toLower();
00672         if ( ch1 == ch2 )
00673             ch2 = ch1.toUpper();
00674         if ( ch1 != ch2 ) {
00675             child2 = node->find( ch2 );
00676             if ( child2 )
00677                 extractStringsFromNodeCI( child2, beginning + *child2, newRest,
00678                                           matches );
00679         }
00680     }
00681 }
00682 
00683 void KCompletion::doBeep( BeepMode mode ) const
00684 {
00685     if ( !d->myBeep )
00686         return;
00687 
00688     QString text, event;
00689 
00690     switch ( mode ) {
00691         case Rotation:
00692             event = QLatin1String("Textcompletion: rotation");
00693             text = i18n("You reached the end of the list\nof matching items.\n");
00694             break;
00695         case PartialMatch:
00696             if ( d->myCompletionMode == KGlobalSettings::CompletionShell ||
00697                  d->myCompletionMode == KGlobalSettings::CompletionMan ) {
00698                 event = QLatin1String("Textcompletion: partial match");
00699                 text = i18n("The completion is ambiguous, more than one\nmatch is available.\n");
00700             }
00701             break;
00702         case NoMatch:
00703             if ( d->myCompletionMode == KGlobalSettings::CompletionShell ) {
00704                 event = QLatin1String("Textcompletion: no match");
00705                 text = i18n("There is no matching item available.\n");
00706             }
00707             break;
00708     }
00709 
00710     if ( !text.isEmpty() )
00711     {
00712         KNotification::event( event, text , QPixmap() , 0L , KNotification::DefaultEvent  );
00713     }
00714 }
00715 
00716 
00719 
00720 
00721 // Implements the tree. Every node is a QChar and has a list of children, which
00722 // are Nodes as well.
00723 // QChar( 0x0 ) is used as the delimiter of a string; the last child of each
00724 // inserted string is 0x0.
00725 
00726 KCompTreeNode::~KCompTreeNode()
00727 {
00728     // delete all children
00729     KCompTreeNode *cur = myChildren.begin();
00730     while (cur) {
00731         KCompTreeNode * next = cur->next;
00732         delete myChildren.remove(cur);
00733         cur = next;
00734     }
00735 }
00736 
00737 
00738 // Adds a child-node "ch" to this node. If such a node is already existent,
00739 // it will not be created. Returns the new/existing node.
00740 KCompTreeNode * KCompTreeNode::insert( const QChar& ch, bool sorted )
00741 {
00742     KCompTreeNode *child = find( ch );
00743     if ( !child ) {
00744         child = new KCompTreeNode( ch );
00745 
00746         // FIXME, first (slow) sorted insertion implementation
00747         if ( sorted ) {
00748             KCompTreeNode * prev = 0;
00749             KCompTreeNode * cur = myChildren.begin();
00750             while ( cur ) {
00751                 if ( ch > *cur ) {
00752                     prev = cur;
00753                     cur = cur->next;
00754                 } else
00755                     break;
00756             }
00757             if (prev)
00758                 myChildren.insert( prev, child );
00759             else
00760                 myChildren.prepend(child);
00761         }
00762 
00763         else
00764             myChildren.append( child );
00765     }
00766 
00767     // implicit weighting: the more often an item is inserted, the higher
00768     // priority it gets.
00769     child->confirm();
00770 
00771     return child;
00772 }
00773 
00774 
00775 // Iteratively removes a string from the tree. The nicer recursive
00776 // version apparently was a little memory hungry (see #56757)
00777 void KCompTreeNode::remove( const QString& str )
00778 {
00779     QString string = str;
00780     string += QChar(0x0);
00781 
00782     QVector<KCompTreeNode *> deletables( string.length() + 1 );
00783 
00784     KCompTreeNode *child = 0L;
00785     KCompTreeNode *parent = this;
00786     deletables.replace( 0, parent );
00787 
00788     int i = 0;
00789     for ( ; i < string.length(); i++ )
00790     {
00791         child = parent->find( string.at( i ) );
00792         if ( child )
00793             deletables.replace( i + 1, child );
00794         else
00795             break;
00796 
00797         parent = child;
00798     }
00799 
00800     for ( ; i >= 1; i-- )
00801     {
00802         parent = deletables.at( i - 1 );
00803         child = deletables.at( i );
00804         if ( child->myChildren.count() == 0 )
00805             delete parent->myChildren.remove( child );
00806     }
00807 }
00808 
00809 bool lessThan( const QString &left, const QString &right )
00810 {
00811     return KStringHandler::naturalCompare( left, right ) < 0;
00812 }
00813 
00814 QStringList KCompletionMatchesWrapper::list() const
00815 {
00816     if ( sortedList && dirty ) {
00817         sortedList->sort();
00818         dirty = false;
00819 
00820         stringList.clear();
00821 
00822         // high weight == sorted last -> reverse the sorting here
00823         QList<KSortableItem<QString> >::const_iterator it;
00824         for ( it = sortedList->constBegin(); it != sortedList->constEnd(); ++it )
00825             stringList.prepend( (*it).value() );
00826     } else if ( compOrder == KCompletion::Sorted ) {
00827         qStableSort(stringList.begin(), stringList.end(), lessThan);
00828     }
00829 
00830     return stringList;
00831 }
00832 
00833 class KCompletionMatchesPrivate
00834 {
00835 public:
00836     KCompletionMatchesPrivate( bool sort )
00837         : sorting( sort )
00838     {}
00839     bool sorting;
00840 };
00841 
00842 KCompletionMatches::KCompletionMatches( const KCompletionMatches &o )
00843  : KSortableList<QString, int>(),
00844    d( new KCompletionMatchesPrivate( o.d->sorting ) )
00845 {
00846     *this = KCompletionMatches::operator=( o );
00847 }
00848 
00849 KCompletionMatches &KCompletionMatches::operator=( const KCompletionMatches &o )
00850 {
00851     if( *this == o )
00852         return *this;
00853     KCompletionMatchesList::operator=( o );
00854     d->sorting = o.d->sorting;
00855 
00856     return *this;
00857 }
00858 
00859 KCompletionMatches::KCompletionMatches( bool sort_P )
00860     : d( new KCompletionMatchesPrivate( sort_P ) )
00861 {
00862 }
00863 
00864 KCompletionMatches::KCompletionMatches( const KCompletionMatchesWrapper& matches )
00865     : d( new KCompletionMatchesPrivate( matches.sorting() ) )
00866 {
00867     if( matches.sortedList != 0L )
00868         KCompletionMatchesList::operator=( *matches.sortedList );
00869     else {
00870         const QStringList l = matches.list();
00871         for( QStringList::ConstIterator it = l.begin();
00872              it != l.end();
00873              ++it )
00874             prepend( KSortableItem<QString, int>( 1, *it ) );
00875     }
00876 }
00877 
00878 KCompletionMatches::~KCompletionMatches()
00879 {
00880     delete d;
00881 }
00882 
00883 QStringList KCompletionMatches::list( bool sort_P ) const
00884 {
00885     if( d->sorting && sort_P )
00886         const_cast< KCompletionMatches* >( this )->sort();
00887     QStringList stringList;
00888     // high weight == sorted last -> reverse the sorting here
00889     for ( ConstIterator it = begin(); it != end(); ++it )
00890         stringList.prepend( (*it).value() );
00891     return stringList;
00892 }
00893 
00894 bool KCompletionMatches::sorting() const
00895 {
00896     return d->sorting;
00897 }
00898 
00899 void KCompletionMatches::removeDuplicates()
00900 {
00901     Iterator it1, it2;
00902     for ( it1 = begin(); it1 != end(); ++it1 ) {
00903         for ( (it2 = it1), ++it2; it2 != end();) {
00904             if( (*it1).value() == (*it2).value()) {
00905                 // use the max height
00906                 (*it1).first = qMax( (*it1).key(), (*it2).key());
00907                 it2 = erase( it2 );
00908                 continue;
00909             }
00910             ++it2;
00911         }
00912     }
00913 }
00914 
00915 void KCompTreeNodeList::append(KCompTreeNode *item)
00916 {
00917     m_count++;
00918     if (!last) {
00919         last = item;
00920         last->next = 0;
00921         first = item;
00922         return;
00923     }
00924     last->next = item;
00925     item->next = 0;
00926     last = item;
00927 }
00928 
00929 void KCompTreeNodeList::prepend(KCompTreeNode *item)
00930 {
00931     m_count++;
00932     if (!last) {
00933         last = item;
00934         last->next = 0;
00935         first = item;
00936         return;
00937     }
00938     item->next = first;
00939     first = item;
00940 }
00941 
00942 void KCompTreeNodeList::insert(KCompTreeNode *after, KCompTreeNode *item)
00943 {
00944     if (!after) {
00945         append(item);
00946         return;
00947     }
00948 
00949     m_count++;
00950 
00951     item->next = after->next;
00952     after->next = item;
00953 
00954     if (after == last)
00955         last = item;
00956 }
00957 
00958 KCompTreeNode *KCompTreeNodeList::remove(KCompTreeNode *item)
00959 {
00960     if (!first || !item)
00961         return 0;
00962     KCompTreeNode *cur = 0;
00963 
00964     if (item == first)
00965         first = first->next;
00966     else {
00967         cur = first;
00968         while (cur && cur->next != item) cur = cur->next;
00969         if (!cur)
00970             return 0;
00971         cur->next = item->next;
00972     }
00973     if (item == last)
00974         last = cur;
00975     m_count--;
00976     return item;
00977 }
00978 
00979 KCompTreeNode *KCompTreeNodeList::at(uint index) const
00980 {
00981     KCompTreeNode *cur = first;
00982     while (index-- && cur) cur = cur->next;
00983     return cur;
00984 }
00985 
00986 KZoneAllocator KCompTreeNode::alloc(8192);
00987 
00988 #include "kcompletion.moc"

KDEUI

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

kdelibs

Skip menu "kdelibs"
  • DNSSD
  • Interfaces
  •   KHexEdit
  •   KMediaPlayer
  •   KSpeech
  •   KTextEditor
  • Kate
  • kconf_update
  • KDE3Support
  •   KUnitTest
  • KDECore
  • KDED
  • KDEsu
  • KDEUI
  • KDocTools
  • KFile
  • KHTML
  • KImgIO
  • KInit
  • kio
  • KIOSlave
  • KJS
  •   KJS-API
  •   WTF
  • kjsembed
  • KNewStuff
  • KParts
  • Kross
  • KUtils
  • Nepomuk
  • Plasma
  • Solid
  • Sonnet
  • ThreadWeaver
Generated for kdelibs by doxygen 1.5.7
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