00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
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
00037
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 ) {
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;
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
00124
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 );
00130 }
00131
00132
00133 node = node->insert( 0x0, true );
00134 if ( weighted )
00135 node->confirm( weight -1 );
00136
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
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;
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
00192
00193 d->matches.clear();
00194 myRotationIndex = 0;
00195 myHasMultipleMatches = false;
00196 myLastMatch = myCurrentMatch;
00197
00198
00199
00200 if ( myCompletionMode == KGlobalSettings::CompletionShell &&
00201 string == myLastString ) {
00202
00203
00204
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
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() ) {
00237
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
00251 bool sorted = (myOrder == Weighted);
00252 KCompletionMatchesWrapper allItems( sorted );
00253 extractStringsFromNode( myTreeRoot, QString::null, &allItems, false );
00254
00255 QStringList list = allItems.list();
00256
00257
00258
00259 if ( list.isEmpty() ) {
00260 doBeep( NoMatch );
00261 return list;
00262 }
00263
00264 if ( string.isEmpty() ) {
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 ) {
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
00296
00297
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
00309
00310
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 );
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 );
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
00411 QString KCompletion::findCompletion( const QString& string )
00412 {
00413 QChar ch;
00414 QString completion;
00415 const KCompTreeNode *node = myTreeRoot;
00416
00417
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;
00426 }
00427
00428
00429
00430
00431
00432 while ( node->childrenCount() == 1 ) {
00433 node = node->firstChild();
00434 if ( !node->isNull() )
00435 completion += *node;
00436 }
00437
00438
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
00454
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
00470 if ( hit->isNull() )
00471 break;
00472
00473 node = hit;
00474 completion += *node;
00475 }
00476 }
00477 }
00478
00479 else
00480 doBeep( PartialMatch );
00481 }
00482
00483 return completion;
00484 }
00485
00486
00487 void KCompletion::findAllCompletions(const QString& string,
00488 KCompletionMatchesWrapper *matches,
00489 bool& hasMultipleMatches) const
00490 {
00491
00492
00493 if ( string.isEmpty() )
00494 return;
00495
00496 if ( myIgnoreCase ) {
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
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;
00515 }
00516
00517
00518
00519
00520
00521 while ( node->childrenCount() == 1 ) {
00522 node = node->firstChild();
00523 if ( !node->isNull() )
00524 completion += *node;
00525
00526 }
00527
00528
00529
00530 if ( node->childrenCount() == 0 )
00531 matches->append( node->weight(), completion );
00532
00533 else {
00534
00535
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
00551 const KCompTreeChildren *list = node->children();
00552 QString string;
00553 QString w;
00554
00555
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() ) {
00570 if ( addWeight ) {
00571
00572 string += ':';
00573 w.setNum( node->weight() );
00574 string.append( w );
00575 }
00576 matches->append( node->weight(), string );
00577 }
00578
00579
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 );
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 );
00600 if ( child1 )
00601 extractStringsFromNodeCI( child1, beginning + *child1, newRest,
00602 matches );
00603
00604
00605 if ( ch1.isLetter() ) {
00606
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
00657
00658
00659
00660
00661 KCompTreeNode::~KCompTreeNode()
00662 {
00663
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
00674
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
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
00703
00704 child->confirm();
00705
00706 return child;
00707 }
00708
00709
00710
00711
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
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
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
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 { }
00886
00887 void KCompletionBase::virtual_hook( int, void* )
00888 { }
00889
00890 #include "kcompletion.moc"