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