00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021 #include "kcompletion.h"
00022 #include "kcompletion_p.h"
00023
00024 #include <kdebug.h>
00025 #include <klocale.h>
00026 #include <knotification.h>
00027 #include <kglobal.h>
00028 #include <kstringhandler.h>
00029 #include <QtCore/QMutableVectorIterator>
00030
00031 class KCompletionPrivate
00032 {
00033 public:
00034 KCompletionPrivate()
00035 : myCompletionMode( KGlobalSettings::completionMode() )
00036 , myTreeRoot( new KCompTreeNode )
00037 , myBeep( true )
00038 , myIgnoreCase( false )
00039 , myHasMultipleMatches( false )
00040 , myRotationIndex( 0 )
00041 {
00042 }
00043 ~KCompletionPrivate()
00044 {
00045 delete myTreeRoot;
00046 }
00047
00048 KCompletionMatchesWrapper matches;
00049
00050 KGlobalSettings::Completion myCompletionMode;
00051
00052 KCompletion::CompOrder myOrder;
00053 QString myLastString;
00054 QString myLastMatch;
00055 QString myCurrentMatch;
00056 KCompTreeNode * myTreeRoot;
00057
00058 bool myBeep : 1;
00059 bool myIgnoreCase : 1;
00060 bool myHasMultipleMatches;
00061 int myRotationIndex;
00062 };
00063
00064 KCompletion::KCompletion()
00065 :d(new KCompletionPrivate)
00066 {
00067 setOrder( Insertion );
00068 }
00069
00070 KCompletion::~KCompletion()
00071 {
00072 delete d;
00073 }
00074
00075 void KCompletion::setOrder( CompOrder order )
00076 {
00077 d->myOrder = order;
00078 d->matches.setSorting( order );
00079 }
00080
00081 KCompletion::CompOrder KCompletion::order() const
00082 {
00083 return d->myOrder;
00084 }
00085
00086 void KCompletion::setIgnoreCase( bool ignoreCase )
00087 {
00088 d->myIgnoreCase = ignoreCase;
00089 }
00090
00091 bool KCompletion::ignoreCase() const
00092 {
00093 return d->myIgnoreCase;
00094 }
00095
00096 void KCompletion::setItems( const QStringList& items )
00097 {
00098 clear();
00099 insertItems( items );
00100 }
00101
00102
00103 void KCompletion::insertItems( const QStringList& items )
00104 {
00105 bool weighted = (d->myOrder == Weighted);
00106 QStringList::ConstIterator it;
00107 if ( weighted ) {
00108 for ( it = items.begin(); it != items.end(); ++it )
00109 addWeightedItem( *it );
00110 }
00111 else {
00112 for ( it = items.begin(); it != items.end(); ++it )
00113 addItem( *it, 0 );
00114 }
00115 }
00116
00117 QStringList KCompletion::items() const
00118 {
00119 KCompletionMatchesWrapper list;
00120 bool addWeight = (d->myOrder == Weighted);
00121 extractStringsFromNode( d->myTreeRoot, QString(), &list, addWeight );
00122
00123 return list.list();
00124 }
00125
00126 bool KCompletion::isEmpty() const
00127 {
00128 return (d->myTreeRoot->childrenCount() == 0);
00129 }
00130
00131 void KCompletion::postProcessMatch( QString * ) const
00132 {
00133 }
00134
00135 void KCompletion::postProcessMatches( QStringList * ) const
00136 {
00137 }
00138
00139 void KCompletion::postProcessMatches( KCompletionMatches * ) const
00140 {
00141 }
00142
00143 void KCompletion::addItem( const QString& item )
00144 {
00145 d->matches.clear();
00146 d->myRotationIndex = 0;
00147 d->myLastString.clear();
00148
00149 addItem( item, 0 );
00150 }
00151
00152 void KCompletion::addItem( const QString& item, uint weight )
00153 {
00154 if ( item.isEmpty() )
00155 return;
00156
00157 KCompTreeNode *node = d->myTreeRoot;
00158 uint len = item.length();
00159
00160 bool sorted = (d->myOrder == Sorted);
00161 bool weighted = ((d->myOrder == Weighted) && weight > 1);
00162
00163
00164
00165
00166 for ( uint i = 0; i < len; i++ ) {
00167 node = node->insert( item.at(i), sorted );
00168 if ( weighted )
00169 node->confirm( weight -1 );
00170 }
00171
00172
00173 node = node->insert( 0x0, true );
00174 if ( weighted )
00175 node->confirm( weight -1 );
00176
00177 }
00178
00179 void KCompletion::addWeightedItem( const QString& item )
00180 {
00181 if ( d->myOrder != Weighted ) {
00182 addItem( item, 0 );
00183 return;
00184 }
00185
00186 uint len = item.length();
00187 uint weight = 0;
00188
00189
00190 int index = item.lastIndexOf(':');
00191 if ( index > 0 ) {
00192 bool ok;
00193 weight = item.mid( index + 1 ).toUInt( &ok );
00194 if ( !ok )
00195 weight = 0;
00196
00197 len = index;
00198 }
00199
00200 addItem( item.left( len ), weight );
00201 return;
00202 }
00203
00204
00205 void KCompletion::removeItem( const QString& item )
00206 {
00207 d->matches.clear();
00208 d->myRotationIndex = 0;
00209 d->myLastString.clear();
00210
00211 d->myTreeRoot->remove( item );
00212 }
00213
00214
00215 void KCompletion::clear()
00216 {
00217 d->matches.clear();
00218 d->myRotationIndex = 0;
00219 d->myLastString.clear();
00220
00221 delete d->myTreeRoot;
00222 d->myTreeRoot = new KCompTreeNode;
00223 }
00224
00225
00226 QString KCompletion::makeCompletion( const QString& string )
00227 {
00228 if ( d->myCompletionMode == KGlobalSettings::CompletionNone )
00229 return QString();
00230
00231
00232
00233 d->matches.clear();
00234 d->myRotationIndex = 0;
00235 d->myHasMultipleMatches = false;
00236 d->myLastMatch = d->myCurrentMatch;
00237
00238
00239
00240 if ( d->myCompletionMode == KGlobalSettings::CompletionShell &&
00241 string == d->myLastString ) {
00242
00243
00244
00245
00246 findAllCompletions( string, &d->matches, d->myHasMultipleMatches );
00247 QStringList l = d->matches.list();
00248 postProcessMatches( &l );
00249 emit matches( l );
00250
00251 if ( l.isEmpty() )
00252 doBeep( NoMatch );
00253
00254 return QString();
00255 }
00256
00257 QString completion;
00258
00259 if ( d->myCompletionMode == KGlobalSettings::CompletionPopup ||
00260 d->myCompletionMode == KGlobalSettings::CompletionPopupAuto ) {
00261 findAllCompletions( string, &d->matches, d->myHasMultipleMatches );
00262 if ( !d->matches.isEmpty() )
00263 completion = d->matches.first();
00264 }
00265 else
00266 completion = findCompletion( string );
00267
00268 if ( d->myHasMultipleMatches )
00269 emit multipleMatches();
00270
00271 d->myLastString = string;
00272 d->myCurrentMatch = completion;
00273
00274 postProcessMatch( &completion );
00275
00276 if ( !string.isEmpty() ) {
00277
00278 emit match( completion );
00279 }
00280
00281 if ( completion.isNull() )
00282 doBeep( NoMatch );
00283
00284 return completion;
00285 }
00286
00287
00288
00289 QStringList KCompletion::substringCompletion( const QString& string ) const
00290 {
00291
00292 KCompletionMatchesWrapper allItems( d->myOrder );
00293 extractStringsFromNode( d->myTreeRoot, QString(), &allItems, false );
00294
00295 QStringList list = allItems.list();
00296
00297
00298
00299 if ( list.isEmpty() ) {
00300 doBeep( NoMatch );
00301 return list;
00302 }
00303
00304 if ( string.isEmpty() ) {
00305 postProcessMatches( &list );
00306 return list;
00307 }
00308
00309 QStringList matches;
00310 QStringList::ConstIterator it = list.constBegin();
00311
00312 for( ; it != list.constEnd(); ++it ) {
00313 QString item = *it;
00314 if ( item.indexOf( string, 0, Qt::CaseInsensitive ) != -1 ) {
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
00339
00340
00341 KCompletionMatchesWrapper matches( d->myOrder );
00342 bool dummy;
00343 findAllCompletions( d->myLastString, &matches, dummy );
00344 QStringList l = matches.list();
00345 postProcessMatches( &l );
00346 return l;
00347 }
00348
00349 KCompletionMatches KCompletion::allWeightedMatches()
00350 {
00351
00352
00353
00354 KCompletionMatchesWrapper matches( d->myOrder );
00355 bool dummy;
00356 findAllCompletions( d->myLastString, &matches, dummy );
00357 KCompletionMatches ret( matches );
00358 postProcessMatches( &ret );
00359 return ret;
00360 }
00361
00362 QStringList KCompletion::allMatches( const QString &string )
00363 {
00364 KCompletionMatchesWrapper matches( d->myOrder );
00365 bool dummy;
00366 findAllCompletions( string, &matches, dummy );
00367 QStringList l = matches.list();
00368 postProcessMatches( &l );
00369 return l;
00370 }
00371
00372 KCompletionMatches KCompletion::allWeightedMatches( const QString &string )
00373 {
00374 KCompletionMatchesWrapper matches( d->myOrder );
00375 bool dummy;
00376 findAllCompletions( string, &matches, dummy );
00377 KCompletionMatches ret( matches );
00378 postProcessMatches( &ret );
00379 return ret;
00380 }
00381
00382 void KCompletion::setSoundsEnabled( bool enable )
00383 {
00384 d->myBeep = enable;
00385 }
00386
00387 bool KCompletion::soundsEnabled() const
00388 {
00389 return d->myBeep;
00390 }
00391
00392 bool KCompletion::hasMultipleMatches() const
00393 {
00394 return d->myHasMultipleMatches;
00395 }
00396
00399
00400
00401 QString KCompletion::nextMatch()
00402 {
00403 QString completion;
00404 d->myLastMatch = d->myCurrentMatch;
00405
00406 if ( d->matches.isEmpty() ) {
00407 findAllCompletions( d->myLastString, &d->matches, d->myHasMultipleMatches );
00408 if ( !d->matches.isEmpty() )
00409 completion = d->matches.first();
00410 d->myCurrentMatch = completion;
00411 d->myRotationIndex = 0;
00412 postProcessMatch( &completion );
00413 emit match( completion );
00414 return completion;
00415 }
00416
00417 QStringList matches = d->matches.list();
00418 d->myLastMatch = matches[ d->myRotationIndex++ ];
00419
00420 if ( d->myRotationIndex == matches.count() -1 )
00421 doBeep( Rotation );
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 );
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
00475 QString KCompletion::findCompletion( const QString& string )
00476 {
00477 QChar ch;
00478 QString completion;
00479 const KCompTreeNode *node = d->myTreeRoot;
00480
00481
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();
00490 }
00491
00492
00493
00494
00495
00496 while ( node->childrenCount() == 1 ) {
00497 node = node->firstChild();
00498 if ( !node->isNull() )
00499 completion += *node;
00500 }
00501
00502
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
00518
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
00534 if ( hit->isNull() )
00535 break;
00536
00537 node = hit;
00538 completion += *node;
00539 }
00540 }
00541 }
00542
00543 else
00544 doBeep( PartialMatch );
00545 }
00546
00547 return completion;
00548 }
00549
00550
00551 void KCompletion::findAllCompletions(const QString& string,
00552 KCompletionMatchesWrapper *matches,
00553 bool& hasMultipleMatches) const
00554 {
00555
00556
00557 if ( string.isEmpty() )
00558 return;
00559
00560 if ( d->myIgnoreCase ) {
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
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;
00579 }
00580
00581
00582
00583
00584
00585 while ( node->childrenCount() == 1 ) {
00586 node = node->firstChild();
00587 if ( !node->isNull() )
00588 completion += *node;
00589
00590 }
00591
00592
00593
00594 if ( node->childrenCount() == 0 )
00595 matches->append( node->weight(), completion );
00596
00597 else {
00598
00599
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
00615 const KCompTreeChildren *list = node->children();
00616 QString string;
00617 QString w;
00618
00619
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() ) {
00634 if ( addWeight ) {
00635
00636 string += ':';
00637 w.setNum( node->weight() );
00638 string.append( w );
00639 }
00640 matches->append( node->weight(), string );
00641 }
00642
00643
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 );
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 );
00664 if ( child1 )
00665 extractStringsFromNodeCI( child1, beginning + *child1, newRest,
00666 matches );
00667
00668
00669 if ( ch1.isLetter() ) {
00670
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
00722
00723
00724
00725
00726 KCompTreeNode::~KCompTreeNode()
00727 {
00728
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
00739
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
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
00768
00769 child->confirm();
00770
00771 return child;
00772 }
00773
00774
00775
00776
00777 void KCompTreeNode::remove( const QString& str )
00778 {
00779 QString string = str;
00780 string += QChar(0x0);
00781
00782 QVector<KCompTreeNode *> deletables( string.length() + 1 );
00783
00784 KCompTreeNode *child = 0L;
00785 KCompTreeNode *parent = this;
00786 deletables.replace( 0, parent );
00787
00788 int i = 0;
00789 for ( ; i < string.length(); i++ )
00790 {
00791 child = parent->find( string.at( i ) );
00792 if ( child )
00793 deletables.replace( i + 1, child );
00794 else
00795 break;
00796
00797 parent = child;
00798 }
00799
00800 for ( ; i >= 1; i-- )
00801 {
00802 parent = deletables.at( i - 1 );
00803 child = deletables.at( i );
00804 if ( child->myChildren.count() == 0 )
00805 delete parent->myChildren.remove( child );
00806 }
00807 }
00808
00809 bool lessThan( const QString &left, const QString &right )
00810 {
00811 return KStringHandler::naturalCompare( left, right ) < 0;
00812 }
00813
00814 QStringList KCompletionMatchesWrapper::list() const
00815 {
00816 if ( sortedList && dirty ) {
00817 sortedList->sort();
00818 dirty = false;
00819
00820 stringList.clear();
00821
00822
00823 QList<KSortableItem<QString> >::const_iterator it;
00824 for ( it = sortedList->constBegin(); it != sortedList->constEnd(); ++it )
00825 stringList.prepend( (*it).value() );
00826 } else if ( compOrder == KCompletion::Sorted ) {
00827 qStableSort(stringList.begin(), stringList.end(), lessThan);
00828 }
00829
00830 return stringList;
00831 }
00832
00833 class KCompletionMatchesPrivate
00834 {
00835 public:
00836 KCompletionMatchesPrivate( bool sort )
00837 : sorting( sort )
00838 {}
00839 bool sorting;
00840 };
00841
00842 KCompletionMatches::KCompletionMatches( const KCompletionMatches &o )
00843 : KSortableList<QString, int>(),
00844 d( new KCompletionMatchesPrivate( o.d->sorting ) )
00845 {
00846 *this = KCompletionMatches::operator=( o );
00847 }
00848
00849 KCompletionMatches &KCompletionMatches::operator=( const KCompletionMatches &o )
00850 {
00851 if( *this == o )
00852 return *this;
00853 KCompletionMatchesList::operator=( o );
00854 d->sorting = o.d->sorting;
00855
00856 return *this;
00857 }
00858
00859 KCompletionMatches::KCompletionMatches( bool sort_P )
00860 : d( new KCompletionMatchesPrivate( sort_P ) )
00861 {
00862 }
00863
00864 KCompletionMatches::KCompletionMatches( const KCompletionMatchesWrapper& matches )
00865 : d( new KCompletionMatchesPrivate( matches.sorting() ) )
00866 {
00867 if( matches.sortedList != 0L )
00868 KCompletionMatchesList::operator=( *matches.sortedList );
00869 else {
00870 const QStringList l = matches.list();
00871 for( QStringList::ConstIterator it = l.begin();
00872 it != l.end();
00873 ++it )
00874 prepend( KSortableItem<QString, int>( 1, *it ) );
00875 }
00876 }
00877
00878 KCompletionMatches::~KCompletionMatches()
00879 {
00880 delete d;
00881 }
00882
00883 QStringList KCompletionMatches::list( bool sort_P ) const
00884 {
00885 if( d->sorting && sort_P )
00886 const_cast< KCompletionMatches* >( this )->sort();
00887 QStringList stringList;
00888
00889 for ( ConstIterator it = begin(); it != end(); ++it )
00890 stringList.prepend( (*it).value() );
00891 return stringList;
00892 }
00893
00894 bool KCompletionMatches::sorting() const
00895 {
00896 return d->sorting;
00897 }
00898
00899 void KCompletionMatches::removeDuplicates()
00900 {
00901 Iterator it1, it2;
00902 for ( it1 = begin(); it1 != end(); ++it1 ) {
00903 for ( (it2 = it1), ++it2; it2 != end();) {
00904 if( (*it1).value() == (*it2).value()) {
00905
00906 (*it1).first = qMax( (*it1).key(), (*it2).key());
00907 it2 = erase( it2 );
00908 continue;
00909 }
00910 ++it2;
00911 }
00912 }
00913 }
00914
00915 void KCompTreeNodeList::append(KCompTreeNode *item)
00916 {
00917 m_count++;
00918 if (!last) {
00919 last = item;
00920 last->next = 0;
00921 first = item;
00922 return;
00923 }
00924 last->next = item;
00925 item->next = 0;
00926 last = item;
00927 }
00928
00929 void KCompTreeNodeList::prepend(KCompTreeNode *item)
00930 {
00931 m_count++;
00932 if (!last) {
00933 last = item;
00934 last->next = 0;
00935 first = item;
00936 return;
00937 }
00938 item->next = first;
00939 first = item;
00940 }
00941
00942 void KCompTreeNodeList::insert(KCompTreeNode *after, KCompTreeNode *item)
00943 {
00944 if (!after) {
00945 append(item);
00946 return;
00947 }
00948
00949 m_count++;
00950
00951 item->next = after->next;
00952 after->next = item;
00953
00954 if (after == last)
00955 last = item;
00956 }
00957
00958 KCompTreeNode *KCompTreeNodeList::remove(KCompTreeNode *item)
00959 {
00960 if (!first || !item)
00961 return 0;
00962 KCompTreeNode *cur = 0;
00963
00964 if (item == first)
00965 first = first->next;
00966 else {
00967 cur = first;
00968 while (cur && cur->next != item) cur = cur->next;
00969 if (!cur)
00970 return 0;
00971 cur->next = item->next;
00972 }
00973 if (item == last)
00974 last = cur;
00975 m_count--;
00976 return item;
00977 }
00978
00979 KCompTreeNode *KCompTreeNodeList::at(uint index) const
00980 {
00981 KCompTreeNode *cur = first;
00982 while (index-- && cur) cur = cur->next;
00983 return cur;
00984 }
00985
00986 KZoneAllocator KCompTreeNode::alloc(8192);
00987
00988 #include "kcompletion.moc"