• Skip to content
  • Skip to link menu
KDE 4.1 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 <QtCore/QMutableVectorIterator>
00029 
00030 class KCompletionPrivate
00031 {
00032 public:
00033     KCompletionPrivate()
00034         : myCompletionMode( KGlobalSettings::completionMode() )
00035         , myTreeRoot( new KCompTreeNode )
00036         , myBeep( true )
00037         , myIgnoreCase( false )
00038         , myHasMultipleMatches( false )
00039         , myRotationIndex( 0 )
00040     {
00041     }
00042     ~KCompletionPrivate()
00043     {
00044         delete myTreeRoot;
00045     }
00046     // list used for nextMatch() and previousMatch()
00047     KCompletionMatchesWrapper matches;
00048 
00049     KGlobalSettings::Completion myCompletionMode;
00050 
00051     KCompletion::CompOrder myOrder;
00052     QString                myLastString;
00053     QString                myLastMatch;
00054     QString                myCurrentMatch;
00055     KCompTreeNode *        myTreeRoot;
00056     //QStringList            myRotations;
00057     bool                   myBeep : 1;
00058     bool                   myIgnoreCase : 1;
00059     bool                   myHasMultipleMatches;
00060     int                    myRotationIndex;
00061 };
00062 
00063 KCompletion::KCompletion()
00064     :d(new KCompletionPrivate)
00065 {
00066     setOrder( Insertion );
00067 }
00068 
00069 KCompletion::~KCompletion()
00070 {
00071     delete d;
00072 }
00073 
00074 void KCompletion::setOrder( CompOrder order )
00075 {
00076     d->myOrder = order;
00077     d->matches.setSorting( order == Weighted );
00078 }
00079 
00080 KCompletion::CompOrder KCompletion::order() const
00081 {
00082     return d->myOrder;
00083 }
00084 
00085 void KCompletion::setIgnoreCase( bool ignoreCase )
00086 {
00087     d->myIgnoreCase = ignoreCase;
00088 }
00089 
00090 bool KCompletion::ignoreCase() const
00091 {
00092     return d->myIgnoreCase;
00093 }
00094 
00095 void KCompletion::setItems( const QStringList& items )
00096 {
00097     clear();
00098     insertItems( items );
00099 }
00100 
00101 
00102 void KCompletion::insertItems( const QStringList& items )
00103 {
00104     bool weighted = (d->myOrder == Weighted);
00105     QStringList::ConstIterator it;
00106     if ( weighted ) { // determine weight
00107         for ( it = items.begin(); it != items.end(); ++it )
00108             addWeightedItem( *it );
00109     }
00110     else {
00111         for ( it = items.begin(); it != items.end(); ++it )
00112             addItem( *it, 0 );
00113     }
00114 }
00115 
00116 QStringList KCompletion::items() const
00117 {
00118     KCompletionMatchesWrapper list; // unsorted
00119     bool addWeight = (d->myOrder == Weighted);
00120     extractStringsFromNode( d->myTreeRoot, QString(), &list, addWeight );
00121 
00122     return list.list();
00123 }
00124 
00125 bool KCompletion::isEmpty() const
00126 {
00127   return (d->myTreeRoot->childrenCount() == 0);
00128 }
00129 
00130 void KCompletion::postProcessMatch( QString * ) const
00131 {
00132 }
00133 
00134 void KCompletion::postProcessMatches( QStringList * ) const
00135 {
00136 }
00137 
00138 void KCompletion::postProcessMatches( KCompletionMatches * ) const
00139 {
00140 }
00141 
00142 void KCompletion::addItem( const QString& item )
00143 {
00144     d->matches.clear();
00145     d->myRotationIndex = 0;
00146     d->myLastString.clear();
00147 
00148     addItem( item, 0 );
00149 }
00150 
00151 void KCompletion::addItem( const QString& item, uint weight )
00152 {
00153     if ( item.isEmpty() )
00154         return;
00155 
00156     KCompTreeNode *node = d->myTreeRoot;
00157     uint len = item.length();
00158 
00159     bool sorted = (d->myOrder == Sorted);
00160     bool weighted = ((d->myOrder == Weighted) && weight > 1);
00161 
00162     // knowing the weight of an item, we simply add this weight to all of its
00163     // nodes.
00164 
00165     for ( uint i = 0; i < len; i++ ) {
00166         node = node->insert( item.at(i), sorted );
00167         if ( weighted )
00168             node->confirm( weight -1 ); // node->insert() sets weighting to 1
00169     }
00170 
00171     // add 0x0-item as delimiter with evtl. weight
00172     node = node->insert( 0x0, true );
00173     if ( weighted )
00174         node->confirm( weight -1 );
00175 //     qDebug("*** added: %s (%i)", item.toLatin1().constData(), node->weight());
00176 }
00177 
00178 void KCompletion::addWeightedItem( const QString& item )
00179 {
00180     if ( d->myOrder != Weighted ) {
00181         addItem( item, 0 );
00182         return;
00183     }
00184 
00185     uint len = item.length();
00186     uint weight = 0;
00187 
00188     // find out the weighting of this item (appended to the string as ":num")
00189     int index = item.lastIndexOf(':');
00190     if ( index > 0 ) {
00191         bool ok;
00192         weight = item.mid( index + 1 ).toUInt( &ok );
00193         if ( !ok )
00194             weight = 0;
00195 
00196         len = index; // only insert until the ':'
00197     }
00198 
00199     addItem( item.left( len ), weight );
00200     return;
00201 }
00202 
00203 
00204 void KCompletion::removeItem( const QString& item )
00205 {
00206     d->matches.clear();
00207     d->myRotationIndex = 0;
00208     d->myLastString.clear();
00209 
00210     d->myTreeRoot->remove( item );
00211 }
00212 
00213 
00214 void KCompletion::clear()
00215 {
00216     d->matches.clear();
00217     d->myRotationIndex = 0;
00218     d->myLastString.clear();
00219 
00220     delete d->myTreeRoot;
00221     d->myTreeRoot = new KCompTreeNode;
00222 }
00223 
00224 
00225 QString KCompletion::makeCompletion( const QString& string )
00226 {
00227     if ( d->myCompletionMode == KGlobalSettings::CompletionNone )
00228         return QString();
00229 
00230     //kDebug(0) << "KCompletion: completing: " << string;
00231 
00232     d->matches.clear();
00233     d->myRotationIndex = 0;
00234     d->myHasMultipleMatches = false;
00235     d->myLastMatch = d->myCurrentMatch;
00236 
00237     // in Shell-completion-mode, emit all matches when we get the same
00238     // complete-string twice
00239     if ( d->myCompletionMode == KGlobalSettings::CompletionShell &&
00240          string == d->myLastString ) {
00241         // Don't use d->matches since calling postProcessMatches()
00242         // on d->matches here would interfere with call to
00243         // postProcessMatch() during rotation
00244 
00245         findAllCompletions( string, &d->matches, d->myHasMultipleMatches );
00246         QStringList l = d->matches.list();
00247         postProcessMatches( &l );
00248         emit matches( l );
00249 
00250         if ( l.isEmpty() )
00251             doBeep( NoMatch );
00252 
00253         return QString();
00254     }
00255 
00256     QString completion;
00257     // in case-insensitive popup mode, we search all completions at once
00258     if ( d->myCompletionMode == KGlobalSettings::CompletionPopup ||
00259          d->myCompletionMode == KGlobalSettings::CompletionPopupAuto ) {
00260         findAllCompletions( string, &d->matches, d->myHasMultipleMatches );
00261         if ( !d->matches.isEmpty() )
00262             completion = d->matches.first();
00263     }
00264     else
00265         completion = findCompletion( string );
00266 
00267     if ( d->myHasMultipleMatches )
00268         emit multipleMatches();
00269 
00270     d->myLastString = string;
00271     d->myCurrentMatch = completion;
00272 
00273     postProcessMatch( &completion );
00274 
00275     if ( !string.isEmpty() ) { // only emit match when string is not empty
00276         //kDebug(0) << "KCompletion: Match: " << completion;
00277         emit match( completion );
00278     }
00279 
00280     if ( completion.isNull() )
00281         doBeep( NoMatch );
00282 
00283     return completion;
00284 }
00285 
00286 
00287 
00288 QStringList KCompletion::substringCompletion( const QString& string ) const
00289 {
00290     // get all items in the tree, eventually in sorted order
00291     bool sorted = (d->myOrder == Weighted);
00292     KCompletionMatchesWrapper allItems( sorted );
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.begin();
00311 
00312     for( ; it != list.end(); ++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 == Weighted );
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 == Weighted );
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 == Weighted );
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 == Weighted );
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 QStringList KCompletionMatchesWrapper::list() const
00810 {
00811     if ( sortedList && dirty ) {
00812         sortedList->sort();
00813         dirty = false;
00814 
00815         stringList.clear();
00816 
00817         // high weight == sorted last -> reverse the sorting here
00818         QList<KSortableItem<QString> >::const_iterator it;
00819         for ( it = sortedList->begin(); it != sortedList->end(); ++it )
00820             stringList.prepend( (*it).value() );
00821     }
00822 
00823     return stringList;
00824 }
00825 
00826 class KCompletionMatchesPrivate
00827 {
00828 public:
00829     KCompletionMatchesPrivate( bool sort )
00830         : sorting( sort )
00831     {}
00832     bool sorting;
00833 };
00834 
00835 KCompletionMatches::KCompletionMatches( const KCompletionMatches &o )
00836  : KSortableList<QString, int>(),
00837    d( new KCompletionMatchesPrivate( o.d->sorting ) )
00838 {
00839     *this = KCompletionMatches::operator=( o );
00840 }
00841 
00842 KCompletionMatches &KCompletionMatches::operator=( const KCompletionMatches &o )
00843 {
00844     if( *this == o )
00845         return *this;
00846     KCompletionMatchesList::operator=( o );
00847     d->sorting = o.d->sorting;
00848 
00849     return *this;
00850 }
00851 
00852 KCompletionMatches::KCompletionMatches( bool sort_P )
00853     : d( new KCompletionMatchesPrivate( sort_P ) )
00854 {
00855 }
00856 
00857 KCompletionMatches::KCompletionMatches( const KCompletionMatchesWrapper& matches )
00858     : d( new KCompletionMatchesPrivate( matches.sorting() ) )
00859 {
00860     if( matches.sortedList != 0L )
00861         KCompletionMatchesList::operator=( *matches.sortedList );
00862     else {
00863         const QStringList l = matches.list();
00864         for( QStringList::ConstIterator it = l.begin();
00865              it != l.end();
00866              ++it )
00867             prepend( KSortableItem<QString, int>( 1, *it ) );
00868     }
00869 }
00870 
00871 KCompletionMatches::~KCompletionMatches()
00872 {
00873     delete d;
00874 }
00875 
00876 QStringList KCompletionMatches::list( bool sort_P ) const
00877 {
00878     if( d->sorting && sort_P )
00879         const_cast< KCompletionMatches* >( this )->sort();
00880     QStringList stringList;
00881     // high weight == sorted last -> reverse the sorting here
00882     for ( ConstIterator it = begin(); it != end(); ++it )
00883         stringList.prepend( (*it).value() );
00884     return stringList;
00885 }
00886 
00887 bool KCompletionMatches::sorting() const
00888 {
00889     return d->sorting;
00890 }
00891 
00892 void KCompletionMatches::removeDuplicates()
00893 {
00894     Iterator it1, it2;
00895     for ( it1 = begin(); it1 != end(); ++it1 ) {
00896         for ( (it2 = it1), ++it2; it2 != end();) {
00897             if( (*it1).value() == (*it2).value()) {
00898                 // use the max height
00899                 (*it1).first = qMax( (*it1).key(), (*it2).key());
00900                 it2 = erase( it2 );
00901                 continue;
00902             }
00903             ++it2;
00904         }
00905     }
00906 }
00907 
00908 void KCompTreeNodeList::append(KCompTreeNode *item)
00909 {
00910     m_count++;
00911     if (!last) {
00912         last = item;
00913         last->next = 0;
00914         first = item;
00915         return;
00916     }
00917     last->next = item;
00918     item->next = 0;
00919     last = item;
00920 }
00921 
00922 void KCompTreeNodeList::prepend(KCompTreeNode *item)
00923 {
00924     m_count++;
00925     if (!last) {
00926         last = item;
00927         last->next = 0;
00928         first = item;
00929         return;
00930     }
00931     item->next = first;
00932     first = item;
00933 }
00934 
00935 void KCompTreeNodeList::insert(KCompTreeNode *after, KCompTreeNode *item)
00936 {
00937     if (!after) {
00938         append(item);
00939         return;
00940     }
00941 
00942     m_count++;
00943 
00944     item->next = after->next;
00945     after->next = item;
00946 
00947     if (after == last)
00948         last = item;
00949 }
00950 
00951 KCompTreeNode *KCompTreeNodeList::remove(KCompTreeNode *item)
00952 {
00953     if (!first || !item)
00954         return 0;
00955     KCompTreeNode *cur = 0;
00956 
00957     if (item == first)
00958         first = first->next;
00959     else {
00960         cur = first;
00961         while (cur && cur->next != item) cur = cur->next;
00962         if (!cur)
00963             return 0;
00964         cur->next = item->next;
00965     }
00966     if (item == last)
00967         last = cur;
00968     m_count--;
00969     return item;
00970 }
00971 
00972 KCompTreeNode *KCompTreeNodeList::at(uint index) const
00973 {
00974     KCompTreeNode *cur = first;
00975     while (index-- && cur) cur = cur->next;
00976     return cur;
00977 }
00978 
00979 KZoneAllocator KCompTreeNode::alloc(8192);
00980 
00981 #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
  • Solid
  • Sonnet
  • ThreadWeaver
Generated for kdelibs by doxygen 1.5.4
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