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 QStringList KCompletion::items() const
00093 {
00094 KCompletionMatchesWrapper list;
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
00127
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 );
00133 }
00134
00135
00136 node = node->insert( 0x0, true );
00137 if ( weighted )
00138 node->confirm( weight -1 );
00139
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
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;
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
00195
00196 d->matches.clear();
00197 myRotationIndex = 0;
00198 myHasMultipleMatches = false;
00199 myLastMatch = myCurrentMatch;
00200
00201
00202
00203 if ( myCompletionMode == KGlobalSettings::CompletionShell &&
00204 string == myLastString ) {
00205
00206
00207
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
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() ) {
00240
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
00254 bool sorted = (myOrder == Weighted);
00255 KCompletionMatchesWrapper allItems( sorted );
00256 extractStringsFromNode( myTreeRoot, QString::null, &allItems, false );
00257
00258 QStringList list = allItems.list();
00259
00260
00261
00262 if ( list.isEmpty() ) {
00263 doBeep( NoMatch );
00264 return list;
00265 }
00266
00267 if ( string.isEmpty() ) {
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 ) {
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
00298
00299
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
00311
00312
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 );
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 );
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
00413 QString KCompletion::findCompletion( const QString& string )
00414 {
00415 QChar ch;
00416 QString completion;
00417 const KCompTreeNode *node = myTreeRoot;
00418
00419
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;
00428 }
00429
00430
00431
00432
00433
00434 while ( node->childrenCount() == 1 ) {
00435 node = node->firstChild();
00436 if ( !node->isNull() )
00437 completion += *node;
00438 }
00439
00440
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
00456
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
00472 if ( hit->isNull() )
00473 break;
00474
00475 node = hit;
00476 completion += *node;
00477 }
00478 }
00479 }
00480
00481 else
00482 doBeep( PartialMatch );
00483 }
00484
00485 return completion;
00486 }
00487
00488
00489 void KCompletion::findAllCompletions(const QString& string,
00490 KCompletionMatchesWrapper *matches,
00491 bool& hasMultipleMatches) const
00492 {
00493
00494
00495 if ( string.isEmpty() )
00496 return;
00497
00498 if ( myIgnoreCase ) {
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
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;
00517 }
00518
00519
00520
00521
00522
00523 while ( node->childrenCount() == 1 ) {
00524 node = node->firstChild();
00525 if ( !node->isNull() )
00526 completion += *node;
00527
00528 }
00529
00530
00531
00532 if ( node->childrenCount() == 0 )
00533 matches->append( node->weight(), completion );
00534
00535 else {
00536
00537
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
00553 const KCompTreeChildren *list = node->children();
00554 QString string;
00555 QString w;
00556
00557
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() ) {
00572 if ( addWeight ) {
00573
00574 string += ':';
00575 w.setNum( node->weight() );
00576 string.append( w );
00577 }
00578 matches->append( node->weight(), string );
00579 }
00580
00581
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 );
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 );
00602 if ( child1 )
00603 extractStringsFromNodeCI( child1, beginning + *child1, newRest,
00604 matches );
00605
00606
00607 if ( ch1.isLetter() ) {
00608
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
00658
00659
00660
00661
00662 KCompTreeNode::~KCompTreeNode()
00663 {
00664
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
00675
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
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
00704
00705 child->confirm();
00706
00707 return child;
00708 }
00709
00710
00711
00712
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
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
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
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 { }
00887
00888 void KCompletionBase::virtual_hook( int, void* )
00889 { }
00890
00891 #include "kcompletion.moc"