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