kdecore Library API Documentation

kcompletion.cpp

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