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 "kcompletion.h"
00028 #include "kcompletion_private.h"
00029
00030
00031 class KCompletionPrivate
00032 {
00033 public:
00034
00035
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 ) {
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;
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
00122
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 );
00128 }
00129
00130
00131 node = node->insert( 0x0, true );
00132 if ( weighted )
00133 node->confirm( weight -1 );
00134
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
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;
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
00190
00191 d->matches.clear();
00192 myRotationIndex = 0;
00193 myHasMultipleMatches = false;
00194 myLastMatch = myCurrentMatch;
00195
00196
00197
00198 if ( myCompletionMode == KGlobalSettings::CompletionShell &&
00199 string == myLastString ) {
00200
00201
00202
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
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() ) {
00235
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
00249 bool sorted = (myOrder == Weighted);
00250 KCompletionMatchesWrapper allItems( sorted );
00251 extractStringsFromNode( myTreeRoot, QString::null, &allItems, false );
00252
00253 QStringList list = allItems.list();
00254
00255
00256
00257 if ( list.isEmpty() ) {
00258 doBeep( NoMatch );
00259 return list;
00260 }
00261
00262 if ( string.isEmpty() ) {
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 ) {
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
00294
00295
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
00307
00308
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 );
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 );
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
00409 QString KCompletion::findCompletion( const QString& string )
00410 {
00411 QChar ch;
00412 QString completion;
00413 const KCompTreeNode *node = myTreeRoot;
00414
00415
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;
00424 }
00425
00426
00427
00428
00429
00430 while ( node->childrenCount() == 1 ) {
00431 node = node->firstChild();
00432 if ( !node->isNull() )
00433 completion += *node;
00434 }
00435
00436
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
00452
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
00468 if ( hit->isNull() )
00469 break;
00470
00471 node = hit;
00472 completion += *node;
00473 }
00474 }
00475 }
00476
00477 else
00478 doBeep( PartialMatch );
00479 }
00480
00481 return completion;
00482 }
00483
00484
00485 void KCompletion::findAllCompletions(const QString& string,
00486 KCompletionMatchesWrapper *matches,
00487 bool& hasMultipleMatches) const
00488 {
00489
00490
00491 if ( string.isEmpty() )
00492 return;
00493
00494 if ( myIgnoreCase ) {
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
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;
00513 }
00514
00515
00516
00517
00518
00519 while ( node->childrenCount() == 1 ) {
00520 node = node->firstChild();
00521 if ( !node->isNull() )
00522 completion += *node;
00523
00524 }
00525
00526
00527
00528 if ( node->childrenCount() == 0 )
00529 matches->append( node->weight(), completion );
00530
00531 else {
00532
00533
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
00549 const KCompTreeChildren *list = node->children();
00550 QString string;
00551 QString w;
00552
00553
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() ) {
00568 if ( addWeight ) {
00569
00570 string += ':';
00571 w.setNum( node->weight() );
00572 string.append( w );
00573 }
00574 matches->append( node->weight(), string );
00575 }
00576
00577
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 );
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 );
00598 if ( child1 )
00599 extractStringsFromNodeCI( child1, beginning + *child1, newRest,
00600 matches );
00601
00602
00603 if ( ch1.isLetter() ) {
00604
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
00655
00656
00657
00658
00659 KCompTreeNode::~KCompTreeNode()
00660 {
00661
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
00672
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
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
00701
00702 child->confirm();
00703
00704 return child;
00705 }
00706
00707
00708
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
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
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
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 { }
00870
00871 void KCompletionBase::virtual_hook( int, void* )
00872 { }
00873
00874 #include "kcompletion.moc"