summaryrefslogtreecommitdiff
path: root/libopie2/qt3/opiecore/ocompletion.cpp
Unidiff
Diffstat (limited to 'libopie2/qt3/opiecore/ocompletion.cpp') (more/less context) (ignore whitespace changes)
-rw-r--r--libopie2/qt3/opiecore/ocompletion.cpp1061
1 files changed, 1061 insertions, 0 deletions
diff --git a/libopie2/qt3/opiecore/ocompletion.cpp b/libopie2/qt3/opiecore/ocompletion.cpp
new file mode 100644
index 0000000..7b263ab
--- a/dev/null
+++ b/libopie2/qt3/opiecore/ocompletion.cpp
@@ -0,0 +1,1061 @@
1/*
2                 This file is part of the Opie Project
3 Originally part of the KDE Project
4 Copyright (C) 1999,2000,2001 Carsten Pfeiffer <pfeiffer@kde.org>
5 =.
6 .=l.
7           .>+-=
8 _;:,     .>    :=|. This program is free software; you can
9.> <`_,   >  .   <= redistribute it and/or modify it under
10:`=1 )Y*s>-.--   : the terms of the GNU Library General Public
11.="- .-=="i,     .._ License as published by the Free Software
12 - .   .-<_>     .<> Foundation; either version 2 of the License,
13     ._= =}       : or (at your option) any later version.
14    .%`+i>       _;_.
15    .i_,=:_.      -<s. This program is distributed in the hope that
16     +  .  -:.       = it will be useful, but WITHOUT ANY WARRANTY;
17    : ..    .:,     . . . without even the implied warranty of
18    =_        +     =;=|` MERCHANTABILITY or FITNESS FOR A
19  _.=:.       :    :=>`: PARTICULAR PURPOSE. See the GNU
20..}^=.=       =       ; Library General Public License for more
21++=   -.     .`     .: details.
22 :     =  ...= . :.=-
23 -.   .:....=;==+<; You should have received a copy of the GNU
24  -_. . .   )=.  = Library General Public License along with
25    --        :-=` this library; see the file COPYING.LIB.
26 If not, write to the Free Software Foundation,
27 Inc., 59 Temple Place - Suite 330,
28 Boston, MA 02111-1307, USA.
29*/
30
31#include <opie2/ocompletion.h>
32
33class OCompTreeNode;
34
35/**************************************************************************************************/
36/* OCompTreeNodeList
37/**************************************************************************************************/
38
39class OCompTreeNodeList
40{
41public:
42 OCompTreeNodeList() : first(0), last(0), m_count(0) {}
43 OCompTreeNode *begin() const { return first; }
44 OCompTreeNode *end() const { return last; }
45
46 OCompTreeNode *at(uint index) const;
47 void append(OCompTreeNode *item);
48 void prepend(OCompTreeNode *item);
49 void insert(OCompTreeNode *after, OCompTreeNode *item);
50 OCompTreeNode *remove(OCompTreeNode *item);
51 uint count() const { return m_count; }
52
53private:
54 OCompTreeNode *first, *last;
55 uint m_count;
56};
57
58typedef OCompTreeNodeList OCompTreeChildren;
59typedef OSortableValueList<QString> OCompletionMatchesList;
60
61/**
62 * A helper class for OCompletion. Implements a tree of QChar.
63 *
64 * The tree looks like this (containing the items "kde", "kde-ui",
65 * "kde-core" and "pfeiffer". Every item is delimited with QChar( 0x0 )
66 *
67 * some_root_node
68 * / \
69 * k p
70 * | |
71 * d f
72 * | |
73 * e e
74 * /| |
75 * 0x0 - i
76 * / \ |
77 * u c f
78 * | | |
79 * i o f
80 * | | |
81 * 0x0 r e
82 * | |
83 * e r
84 * | |
85 * 0x0 0x0
86 *
87 * @author Carsten Pfeiffer <pfeiffer@kde.org>
88 * @internal
89 */
90
91/**************************************************************************************************/
92/* OCompTreeNode
93/**************************************************************************************************/
94
95class OCompTreeNode : public QChar
96{
97public:
98 OCompTreeNode():QChar(), myWeight(0) {}
99 OCompTreeNode( const QChar& ch, uint weight = 0 ):QChar( ch ), myWeight( weight ) {}
100 ~OCompTreeNode();
101
102 // FIXME: Do we need this for Opie? [see also the static ZoneAllocater below]
103 //void * operator new( size_t s ) {
104 // return alloc.allocate( s );
105 //}
106 //void operator delete( void * s ) {
107 // alloc.deallocate( s );
108 //}
109
110 // Returns a child of this node matching ch, if available.
111 // Otherwise, returns 0L
112 inline OCompTreeNode * find( const QChar& ch ) const {
113 OCompTreeNode * cur = myChildren.begin();
114 while (cur && (*cur != ch)) cur = cur->next;
115 return cur;
116 }
117
118 OCompTreeNode * insert( const QChar&, bool sorted );
119 void remove( const QString& );
120
121 inline int childrenCount() const { return myChildren.count(); };
122
123 // weighting
124 inline void confirm() { myWeight++; };
125 inline void confirm(uint w) { myWeight += w; };
126 inline void decline() { myWeight--; };
127 inline uint weight() const { return myWeight; };
128
129 inline const OCompTreeChildren * children() const { return &myChildren; };
130 inline const OCompTreeNode * childAt(int index) const { return myChildren.at(index); };
131 inline const OCompTreeNode * firstChild() const { return myChildren.begin(); };
132 inline const OCompTreeNode * lastChild() const { return myChildren.end(); };
133
134 /* We want to handle a list of OCompTreeNodes on our own, to not
135 need to use QValueList<>. And to make it even more fast we don't
136 use an accessor, but just a public member. */
137 OCompTreeNode *next;
138
139private:
140 uint myWeight;
141 OCompTreeNodeListmyChildren;
142 //static OZoneAllocator alloc; // FIXME: Do we need this for Opie?
143};
144
145/**************************************************************************************************/
146/* OCompletionMatchesWrapper
147/**************************************************************************************************/
148
149class OCompletionMatchesWrapper
150{
151public:
152 OCompletionMatchesWrapper( bool sort = false )
153 : sortedList( sort ? new OCompletionMatchesList : 0L ),
154 dirty( false )
155 {}
156 ~OCompletionMatchesWrapper() {
157 delete sortedList;
158 }
159
160 void setSorting( bool sort ) {
161 if ( sort && !sortedList )
162 sortedList = new OCompletionMatchesList;
163 else if ( !sort ) {
164 delete sortedList;
165 sortedList = 0L;
166 }
167 stringList.clear();
168 dirty = false;
169 }
170
171 bool sorting() const {
172 return sortedList != 0L;
173 }
174
175 void append( int i, const QString& string ) {
176 if ( sortedList )
177 sortedList->insert( i, string );
178 else
179 stringList.append( string );
180 dirty = true;
181 }
182
183 void clear() {
184 if ( sortedList )
185 sortedList->clear();
186 stringList.clear();
187 dirty = false;
188 }
189
190 uint count() const {
191 if ( sortedList )
192 return sortedList->count();
193 return stringList.count();
194 }
195
196 bool isEmpty() const {
197 return count() == 0;
198 }
199
200 QString first() const {
201 return list().first();
202 }
203
204 QString last() const {
205 return list().last();
206 }
207
208 QStringList list() const;
209
210 mutable QStringList stringList;
211 OCompletionMatchesList *sortedList;
212 mutable bool dirty;
213};
214
215/**************************************************************************************************/
216/* OCompletionPrivate
217/**************************************************************************************************/
218
219class OCompletionPrivate
220{
221public:
222 // not a member to avoid #including kcompletion_private.h from kcompletion.h
223 // list used for nextMatch() and previousMatch()
224 OCompletionMatchesWrapper matches;
225};
226
227/**************************************************************************************************/
228/* OCompletion
229/**************************************************************************************************/
230
231OCompletion::OCompletion()
232{
233 d = new OCompletionPrivate;
234
235 myCompletionMode = OGlobalSettings::completionMode();
236 myTreeRoot = new OCompTreeNode;
237 myBeep = true;
238 myIgnoreCase = false;
239 myHasMultipleMatches = false;
240 myRotationIndex = 0;
241 setOrder( Insertion );
242}
243
244
245OCompletion::~OCompletion()
246{
247 delete d;
248 delete myTreeRoot;
249}
250
251
252void OCompletion::setOrder( CompOrder order )
253{
254 myOrder = order;
255 d->matches.setSorting( order == Weighted );
256}
257
258
259void OCompletion::setIgnoreCase( bool ignoreCase )
260{
261 myIgnoreCase = ignoreCase;
262}
263
264
265void OCompletion::setItems( const QStringList& items )
266{
267 clear();
268 insertItems( items );
269}
270
271
272void OCompletion::insertItems( const QStringList& items )
273{
274 bool weighted = (myOrder == Weighted);
275 QStringList::ConstIterator it;
276 if ( weighted ) { // determine weight
277 for ( it = items.begin(); it != items.end(); ++it ) addWeightedItem( *it );
278 }
279 else {
280 for ( it = items.begin(); it != items.end(); ++it ) addItem( *it, 0 );
281 }
282}
283
284
285QStringList OCompletion::items() const
286{
287 OCompletionMatchesWrapper list; // unsorted
288 bool addWeight = (myOrder == Weighted);
289 extractStringsFromNode( myTreeRoot, QString::null, &list, addWeight );
290
291 return list.list();
292}
293
294
295void OCompletion::addItem( const QString& item )
296{
297 d->matches.clear();
298 myRotationIndex = 0;
299 myLastString = QString::null;
300
301 addItem( item, 0 );
302}
303
304
305void OCompletion::addItem( const QString& item, uint weight )
306{
307 if ( item.isEmpty() ) return;
308
309 OCompTreeNode *node = myTreeRoot;
310 uint len = item.length();
311
312 bool sorted = (myOrder == Sorted);
313 bool weighted = ((myOrder == Weighted) && weight > 1);
314
315 // knowing the weight of an item, we simply add this weight to all of its
316 // nodes.
317
318 for ( uint i = 0; i < len; i++ ) {
319 node = node->insert( item.at(i), sorted );
320 if ( weighted ) node->confirm( weight -1 ); // node->insert() sets weighting to 1
321 }
322
323 // add 0x0-item as delimiter with evtl. weight
324 node = node->insert( 0x0, true );
325 if ( weighted )
326 node->confirm( weight -1 );
327 //qDebug( "OCompletion: added: %s (%i)", item.latin1(), node->weight());
328}
329
330
331void OCompletion::addWeightedItem( const QString& item )
332{
333 if ( myOrder != Weighted ) {
334 addItem( item, 0 );
335 return;
336 }
337
338 uint len = item.length();
339 uint weight = 0;
340
341 // find out the weighting of this item (appended to the string as ":num")
342 int index = item.findRev(':');
343 if ( index > 0 ) {
344 bool ok;
345 weight = item.mid( index + 1 ).toUInt( &ok );
346 if ( !ok )
347 weight = 0;
348
349 len = index; // only insert until the ':'
350 }
351
352 addItem( item.left( len ), weight );
353 return;
354}
355
356
357void OCompletion::removeItem( const QString& item )
358{
359 d->matches.clear();
360 myRotationIndex = 0;
361 myLastString = QString::null;
362
363 myTreeRoot->remove( item );
364}
365
366
367void OCompletion::clear()
368{
369 d->matches.clear();
370 myRotationIndex = 0;
371 myLastString = QString::null;
372
373 delete myTreeRoot;
374 myTreeRoot = new OCompTreeNode;
375}
376
377
378QString OCompletion::makeCompletion( const QString& string )
379{
380 if ( myCompletionMode == OGlobalSettings::CompletionNone )
381 return QString::null;
382
383 //qDebug( "OCompletion: completing: %s", string );
384
385 d->matches.clear();
386 myRotationIndex = 0;
387 myHasMultipleMatches = false;
388 myLastMatch = myCurrentMatch;
389
390 // in Shell-completion-mode, emit all matches when we get the same
391 // complete-string twice
392 if ( myCompletionMode == OGlobalSettings::CompletionShell &&
393 string == myLastString ) {
394 // Don't use d->matches since calling postProcessMatches()
395 // on d->matches here would interfere with call to
396 // postProcessMatch() during rotation
397
398 findAllCompletions( string, &d->matches, myHasMultipleMatches );
399 QStringList l = d->matches.list();
400 postProcessMatches( &l );
401 emit matches( l );
402
403 if ( l.isEmpty() )
404 doBeep( NoMatch );
405
406 return QString::null;
407 }
408
409 QString completion;
410 // in case-insensitive popup mode, we search all completions at once
411 if ( myCompletionMode == OGlobalSettings::CompletionPopup ||
412 myCompletionMode == OGlobalSettings::CompletionPopupAuto ) {
413 findAllCompletions( string, &d->matches, myHasMultipleMatches );
414 if ( !d->matches.isEmpty() )
415 completion = d->matches.first();
416 }
417 else
418 completion = findCompletion( string );
419
420 if ( myHasMultipleMatches )
421 emit multipleMatches();
422
423 myLastString = string;
424 myCurrentMatch = completion;
425
426 postProcessMatch( &completion );
427
428 if ( !string.isEmpty() ) { // only emit match when string != ""
429 //qDebug( "OCompletion: Match: %s", completion );
430 emit match( completion );
431 }
432
433 if ( completion.isNull() )
434 doBeep( NoMatch );
435
436 return completion;
437}
438
439QStringList OCompletion::substringCompletion( const QString& string ) const
440{
441 // get all items in the tree, eventually in sorted order
442 bool sorted = (myOrder == Weighted);
443 OCompletionMatchesWrapper allItems( sorted );
444 extractStringsFromNode( myTreeRoot, QString::null, &allItems, false );
445
446 QStringList list = allItems.list();
447
448 // subStringMatches is invoked manually, via a shortcut, so we should
449 // beep here, if necessary.
450 if ( list.isEmpty() ) {
451 doBeep( NoMatch );
452 return list;
453 }
454
455 if ( string.isEmpty() ) { // shortcut
456 postProcessMatches( &list );
457 return list;
458 }
459
460 QStringList matches;
461 QStringList::ConstIterator it = list.begin();
462
463 for( ; it != list.end(); ++it ) {
464 QString item = *it;
465 if ( item.find( string, 0, false ) != -1 ) { // always case insensitive
466 postProcessMatch( &item );
467 matches.append( item );
468 }
469 }
470
471 if ( matches.isEmpty() )
472 doBeep( NoMatch );
473
474 return matches;
475}
476
477
478void OCompletion::setCompletionMode( OGlobalSettings::Completion mode )
479{
480 myCompletionMode = mode;
481}
482
483
484QStringList OCompletion::allMatches()
485{
486 // Don't use d->matches since calling postProcessMatches()
487 // on d->matches here would interfere with call to
488 // postProcessMatch() during rotation
489 OCompletionMatchesWrapper matches( myOrder == Weighted );
490 bool dummy;
491 findAllCompletions( myLastString, &matches, dummy );
492 QStringList l = matches.list();
493 postProcessMatches( &l );
494 return l;
495}
496
497
498OCompletionMatches OCompletion::allWeightedMatches()
499{
500 // Don't use d->matches since calling postProcessMatches()
501 // on d->matches here would interfere with call to
502 // postProcessMatch() during rotation
503 OCompletionMatchesWrapper matches( myOrder == Weighted );
504 bool dummy;
505 findAllCompletions( myLastString, &matches, dummy );
506 OCompletionMatches ret( matches );
507 postProcessMatches( &ret );
508 return ret;
509}
510
511QStringList OCompletion::allMatches( const QString &string )
512{
513 OCompletionMatchesWrapper matches( myOrder == Weighted );
514 bool dummy;
515 findAllCompletions( string, &matches, dummy );
516 QStringList l = matches.list();
517 postProcessMatches( &l );
518 return l;
519}
520
521OCompletionMatches OCompletion::allWeightedMatches( const QString &string )
522{
523 OCompletionMatchesWrapper matches( myOrder == Weighted );
524 bool dummy;
525 findAllCompletions( string, &matches, dummy );
526 OCompletionMatches ret( matches );
527 postProcessMatches( &ret );
528 return ret;
529}
530
531/////////////////////////////////////////////////////
532///////////////// tree operations ///////////////////
533
534
535QString OCompletion::nextMatch()
536{
537 QString completion;
538 myLastMatch = myCurrentMatch;
539
540 if ( d->matches.isEmpty() ) {
541 findAllCompletions( myLastString, &d->matches, myHasMultipleMatches );
542 completion = d->matches.first();
543 myCurrentMatch = completion;
544 myRotationIndex = 0;
545 postProcessMatch( &completion );
546 emit match( completion );
547 return completion;
548 }
549
550 QStringList matches = d->matches.list();
551 myLastMatch = matches[ myRotationIndex++ ];
552
553 if ( myRotationIndex == matches.count() -1 )
554 doBeep( Rotation ); // indicate last matching item -> rotating
555
556 else if ( myRotationIndex == matches.count() )
557 myRotationIndex = 0;
558
559 completion = matches[ myRotationIndex ];
560 myCurrentMatch = completion;
561 postProcessMatch( &completion );
562 emit match( completion );
563 return completion;
564}
565
566
567
568QString OCompletion::previousMatch()
569{
570 QString completion;
571 myLastMatch = myCurrentMatch;
572
573 if ( d->matches.isEmpty() ) {
574 findAllCompletions( myLastString, &d->matches, myHasMultipleMatches );
575 completion = d->matches.last();
576 myCurrentMatch = completion;
577 myRotationIndex = 0;
578 postProcessMatch( &completion );
579 emit match( completion );
580 return completion;
581 }
582
583 QStringList matches = d->matches.list();
584 myLastMatch = matches[ myRotationIndex ];
585 if ( myRotationIndex == 1 )
586 doBeep( Rotation ); // indicate first item -> rotating
587
588 else if ( myRotationIndex == 0 )
589 myRotationIndex = matches.count();
590
591 myRotationIndex--;
592
593 completion = matches[ myRotationIndex ];
594 myCurrentMatch = completion;
595 postProcessMatch( &completion );
596 emit match( completion );
597 return completion;
598}
599
600
601
602// tries to complete "string" from the tree-root
603QString OCompletion::findCompletion( const QString& string )
604{
605 QChar ch;
606 QString completion;
607 const OCompTreeNode *node = myTreeRoot;
608
609 // start at the tree-root and try to find the search-string
610 for( uint i = 0; i < string.length(); i++ ) {
611 ch = string.at( i );
612 node = node->find( ch );
613
614 if ( node )
615 completion += ch;
616 else
617 return QString::null; // no completion
618 }
619
620 // Now we have the last node of the to be completed string.
621 // Follow it as long as it has exactly one child (= longest possible
622 // completion)
623
624 while ( node->childrenCount() == 1 ) {
625 node = node->firstChild();
626 if ( !node->isNull() )
627 completion += *node;
628 }
629 // if multiple matches and auto-completion mode
630 // -> find the first complete match
631 if ( node && node->childrenCount() > 1 ) {
632 myHasMultipleMatches = true;
633
634 if ( myCompletionMode == OGlobalSettings::CompletionAuto ) {
635 myRotationIndex = 1;
636 if (myOrder != Weighted) {
637 while ( (node = node->firstChild()) ) {
638 if ( !node->isNull() )
639 completion += *node;
640 else
641 break;
642 }
643 }
644 else {
645 // don't just find the "first" match, but the one with the
646 // highest priority
647
648 const OCompTreeNode* temp_node = 0L;
649 while(1) {
650 int count = node->childrenCount();
651 temp_node = node->firstChild();
652 uint weight = temp_node->weight();
653 const OCompTreeNode* hit = temp_node;
654 for( int i = 1; i < count; i++ ) {
655 temp_node = node->childAt(i);
656 if( temp_node->weight() > weight ) {
657 hit = temp_node;
658 weight = hit->weight();
659 }
660 }
661 // 0x0 has the highest priority -> we have the best match
662 if ( hit->isNull() )
663 break;
664
665 node = hit;
666 completion += *node;
667 }
668 }
669 }
670
671 else
672 doBeep( PartialMatch ); // partial match -> beep
673 }
674
675 return completion;
676}
677
678
679void OCompletion::findAllCompletions(const QString& string,
680 OCompletionMatchesWrapper *matches,
681 bool& hasMultipleMatches) const
682{
683 //qDebug( "OCompletion: finding all completions for %s", (const char*) string );
684
685 if ( string.isEmpty() )
686 return;
687
688 if ( myIgnoreCase ) { // case insensitive completion
689 extractStringsFromNodeCI( myTreeRoot, QString::null, string, matches );
690 hasMultipleMatches = (matches->count() > 1);
691 return;
692 }
693
694 QChar ch;
695 QString completion;
696 const OCompTreeNode *node = myTreeRoot;
697
698 // start at the tree-root and try to find the search-string
699 for( uint i = 0; i < string.length(); i++ ) {
700 ch = string.at( i );
701 node = node->find( ch );
702
703 if ( node )
704 completion += ch;
705 else
706 return; // no completion -> return empty list
707 }
708
709 // Now we have the last node of the to be completed string.
710 // Follow it as long as it has exactly one child (= longest possible
711 // completion)
712
713 while ( node->childrenCount() == 1 ) {
714 node = node->firstChild();
715 if ( !node->isNull() )
716 completion += *node;
717 // kdDebug() << completion << node->latin1();
718 }
719
720
721 // there is just one single match)
722 if ( node->childrenCount() == 0 )
723 matches->append( node->weight(), completion );
724
725 else {
726 // node has more than one child
727 // -> recursively find all remaining completions
728 hasMultipleMatches = true;
729 extractStringsFromNode( node, completion, matches );
730 }
731}
732
733
734void OCompletion::extractStringsFromNode( const OCompTreeNode *node,
735 const QString& beginning,
736 OCompletionMatchesWrapper *matches,
737 bool addWeight ) const
738{
739 if ( !node || !matches ) return;
740
741 // kDebug() << "Beginning: " << beginning << endl;
742 const OCompTreeChildren *list = node->children();
743 QString string;
744 QString w;
745
746 // loop thru all children
747 for ( OCompTreeNode *cur = list->begin(); cur ; cur = cur->next) {
748 string = beginning;
749 node = cur;
750 if ( !node->isNull() )
751 string += *node;
752
753 while ( node && node->childrenCount() == 1 ) {
754 node = node->firstChild();
755 if ( node->isNull() ) break;
756 string += *node;
757 }
758
759 if ( node && node->isNull() ) { // we found a leaf
760 if ( addWeight ) {
761 // add ":num" to the string to store the weighting
762 string += ':';
763 w.setNum( node->weight() );
764 string.append( w );
765 }
766 matches->append( node->weight(), string );
767 }
768
769 // recursively find all other strings.
770 if ( node && node->childrenCount() > 1 )
771 extractStringsFromNode( node, string, matches, addWeight );
772 }
773}
774
775void OCompletion::extractStringsFromNodeCI( const OCompTreeNode *node,
776 const QString& beginning,
777 const QString& restString,
778 OCompletionMatchesWrapper *matches ) const
779{
780 if ( restString.isEmpty() ) {
781 extractStringsFromNode( node, beginning, matches, false /*noweight*/ );
782 return;
783 }
784
785 QChar ch1 = restString.at(0);
786 QString newRest = restString.mid(1);
787 OCompTreeNode *child1, *child2;
788
789 child1 = node->find( ch1 ); // the correct match
790 if ( child1 )
791 extractStringsFromNodeCI( child1, beginning + *child1, newRest,
792 matches );
793
794 // append the case insensitive matches, if available
795 if ( ch1.isLetter() ) {
796 // find out if we have to lower or upper it. Is there a better way?
797 QChar ch2 = ch1.lower();
798 if ( ch1 == ch2 )
799 ch2 = ch1.upper();
800 if ( ch1 != ch2 ) {
801 child2 = node->find( ch2 );
802 if ( child2 )
803 extractStringsFromNodeCI( child2, beginning + *child2, newRest,
804 matches );
805 }
806 }
807}
808
809// FIXME: Revise this for Opie?
810
811void OCompletion::doBeep( BeepMode mode ) const
812{
813 if ( !myBeep ) return;
814
815 QString text, event;
816
817 switch ( mode ) {
818 case Rotation:
819 event = QString::fromLatin1("Textcompletion: rotation");
820 text = tr("You reached the end of the list\nof matching items.\n");
821 break;
822 case PartialMatch:
823 if ( myCompletionMode == OGlobalSettings::CompletionShell ||
824 myCompletionMode == OGlobalSettings::CompletionMan ) {
825 event = QString::fromLatin1("Textcompletion: partial match");
826 text = tr("The completion is ambiguous, more than one\nmatch is available.\n");
827 }
828 break;
829 case NoMatch:
830 if ( myCompletionMode == OGlobalSettings::CompletionShell ) {
831 event = QString::fromLatin1("Textcompletion: no match");
832 text = tr("There is no matching item available.\n");
833 }
834 break;
835 }
836
837 //if ( !text.isEmpty() )
838 //ONotifyClient::event( event, text ); // FIXME: Revise for Opie?
839}
840
841// Implements the tree. Every node is a QChar and has a list of children, which
842// are Nodes as well.
843// QChar( 0x0 ) is used as the delimiter of a string; the last child of each
844// inserted string is 0x0.
845
846OCompTreeNode::~OCompTreeNode()
847{
848 // delete all children
849 OCompTreeNode *cur = myChildren.begin();
850 while (cur) {
851 OCompTreeNode * next = cur->next;
852 delete myChildren.remove(cur);
853 cur = next;
854 }
855}
856
857
858// Adds a child-node "ch" to this node. If such a node is already existant,
859// it will not be created. Returns the new/existing node.
860OCompTreeNode * OCompTreeNode::insert( const QChar& ch, bool sorted )
861{
862 OCompTreeNode *child = find( ch );
863 if ( !child ) {
864 child = new OCompTreeNode( ch );
865
866 // FIXME, first (slow) sorted insertion implementation
867 if ( sorted ) {
868 OCompTreeNode * prev = 0;
869 OCompTreeNode * cur = myChildren.begin();
870 while ( cur ) {
871 if ( ch > *cur ) {
872 prev = cur;
873 cur = cur->next;
874 } else
875 break;
876 }
877 if (prev)
878 myChildren.insert( prev, child );
879 else
880 myChildren.prepend(child);
881 }
882
883 else
884 myChildren.append( child );
885 }
886
887 // implicit weighting: the more often an item is inserted, the higher
888 // priority it gets.
889 child->confirm();
890
891 return child;
892}
893
894
895// Recursively removes a string from the tree (untested :-)
896void OCompTreeNode::remove( const QString& string )
897{
898 OCompTreeNode *child = 0L;
899
900 if ( string.isEmpty() ) {
901 child = find( 0x0 );
902 delete myChildren.remove( child );
903 return;
904 }
905
906 QChar ch = string.at(0);
907 child = find( ch );
908 if ( child ) {
909 child->remove( string.right( string.length() -1 ) );
910 if ( child->myChildren.count() == 0 ) {
911 delete myChildren.remove( child );
912 }
913 }
914}
915
916QStringList OCompletionMatchesWrapper::list() const {
917 if ( sortedList && dirty ) {
918 sortedList->sort();
919 dirty = false;
920
921 stringList.clear();
922
923 // high weight == sorted last -> reverse the sorting here
924 QValueListConstIterator<OSortableItem<QString> > it;
925 for ( it = sortedList->begin(); it != sortedList->end(); ++it )
926 stringList.prepend( (*it).value() );
927 }
928
929 return stringList;
930}
931
932OCompletionMatches::OCompletionMatches( bool sort_P )
933 : _sorting( sort_P )
934{
935}
936
937OCompletionMatches::OCompletionMatches( const OCompletionMatchesWrapper& matches )
938 : _sorting( matches.sorting())
939{
940 if( matches.sortedList != 0L )
941 OCompletionMatchesList::operator=( *matches.sortedList );
942 else {
943 QStringList l = matches.list();
944 for( QStringList::ConstIterator it = l.begin();
945 it != l.end();
946 ++it )
947 prepend( OSortableItem<QString, int>( 1, *it ) );
948 }
949}
950
951OCompletionMatches::~OCompletionMatches()
952{
953}
954
955QStringList OCompletionMatches::list( bool sort_P ) const
956{
957 if( _sorting && sort_P )
958 const_cast< OCompletionMatches* >( this )->sort();
959 QStringList stringList;
960 // high weight == sorted last -> reverse the sorting here
961 for ( ConstIterator it = begin(); it != end(); ++it )
962 stringList.prepend( (*it).value() );
963 return stringList;
964}
965
966void OCompletionMatches::removeDuplicates()
967{
968 Iterator it1, it2;
969 for ( it1 = begin(); it1 != end(); ++it1 ) {
970 for ( (it2 = it1), ++it2; it2 != end();) {
971 if( (*it1).value() == (*it2).value()) {
972 // use the max height
973 //(*it1).first = kMax( (*it1).index(), (*it2).index());
974 (*it1).first = (*it2).index() < (*it1).index() ? (*it1).index() : (*it2).index();
975 it2 = remove( it2 );
976 continue;
977 }
978 ++it2;
979 }
980 }
981}
982
983void OCompTreeNodeList::append(OCompTreeNode *item)
984{
985 m_count++;
986 if (!last) {
987 last = item;
988 last->next = 0;
989 first = item;
990 return;
991 }
992 last->next = item;
993 item->next = 0;
994 last = item;
995}
996
997void OCompTreeNodeList::prepend(OCompTreeNode *item)
998{
999 m_count++;
1000 if (!last) {
1001 last = item;
1002 last->next = 0;
1003 first = item;
1004 return;
1005 }
1006 item->next = first;
1007 first = item;
1008}
1009
1010void OCompTreeNodeList::insert(OCompTreeNode *after, OCompTreeNode *item)
1011{
1012 if (!after) {
1013 append(item);
1014 return;
1015 }
1016
1017 m_count++;
1018
1019 item->next = after->next;
1020 after->next = item;
1021
1022 if (after == last)
1023 last = item;
1024}
1025
1026OCompTreeNode *OCompTreeNodeList::remove(OCompTreeNode *item)
1027{
1028 if (!first || !item)
1029 return 0;
1030 OCompTreeNode *cur = 0;
1031
1032 if (item == first)
1033 first = first->next;
1034 else {
1035 cur = first;
1036 while (cur && cur->next != item) cur = cur->next;
1037 if (!cur)
1038 return 0;
1039 cur->next = item->next;
1040 }
1041 if (item == last)
1042 last = cur;
1043 m_count--;
1044 return item;
1045}
1046
1047OCompTreeNode *OCompTreeNodeList::at(uint index) const
1048{
1049 OCompTreeNode *cur = first;
1050 while (index-- && cur) cur = cur->next;
1051 return cur;
1052}
1053
1054// FIXME: Revise for Opie?
1055//OZoneAllocator OCompTreeNode::alloc(8192);
1056
1057//void OCompletion::virtual_hook( int, void* )
1058//{ /*BASE::virtual_hook( id, data );*/ }
1059
1060//void OCompletionBase::virtual_hook( int, void* )
1061//{ /*BASE::virtual_hook( id, data );*/ }