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"