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"