Diffstat (limited to 'libopie2/qt3/opiecore/ocompletion.cpp') (more/less context) (ignore whitespace changes)
-rw-r--r-- | libopie2/qt3/opiecore/ocompletion.cpp | 1061 |
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 | |||
33 | class OCompTreeNode; | ||
34 | |||
35 | /**************************************************************************************************/ | ||
36 | /* OCompTreeNodeList | ||
37 | /**************************************************************************************************/ | ||
38 | |||
39 | class OCompTreeNodeList | ||
40 | { | ||
41 | public: | ||
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 | |||
53 | private: | ||
54 | OCompTreeNode *first, *last; | ||
55 | uint m_count; | ||
56 | }; | ||
57 | |||
58 | typedef OCompTreeNodeList OCompTreeChildren; | ||
59 | typedef 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 | |||
95 | class OCompTreeNode : public QChar | ||
96 | { | ||
97 | public: | ||
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 | |||
139 | private: | ||
140 | uint myWeight; | ||
141 | OCompTreeNodeListmyChildren; | ||
142 | //static OZoneAllocator alloc; // FIXME: Do we need this for Opie? | ||
143 | }; | ||
144 | |||
145 | /**************************************************************************************************/ | ||
146 | /* OCompletionMatchesWrapper | ||
147 | /**************************************************************************************************/ | ||
148 | |||
149 | class OCompletionMatchesWrapper | ||
150 | { | ||
151 | public: | ||
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 | |||
219 | class OCompletionPrivate | ||
220 | { | ||
221 | public: | ||
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 | |||
231 | OCompletion::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 | |||
245 | OCompletion::~OCompletion() | ||
246 | { | ||
247 | delete d; | ||
248 | delete myTreeRoot; | ||
249 | } | ||
250 | |||
251 | |||
252 | void OCompletion::setOrder( CompOrder order ) | ||
253 | { | ||
254 | myOrder = order; | ||
255 | d->matches.setSorting( order == Weighted ); | ||
256 | } | ||
257 | |||
258 | |||
259 | void OCompletion::setIgnoreCase( bool ignoreCase ) | ||
260 | { | ||
261 | myIgnoreCase = ignoreCase; | ||
262 | } | ||
263 | |||
264 | |||
265 | void OCompletion::setItems( const QStringList& items ) | ||
266 | { | ||
267 | clear(); | ||
268 | insertItems( items ); | ||
269 | } | ||
270 | |||
271 | |||
272 | void 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 | |||
285 | QStringList 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 | |||
295 | void 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 | |||
305 | void 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 | |||
331 | void 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 | |||
357 | void 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 | |||
367 | void 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 | |||
378 | QString 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 | |||
439 | QStringList 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 | |||
478 | void OCompletion::setCompletionMode( OGlobalSettings::Completion mode ) | ||
479 | { | ||
480 | myCompletionMode = mode; | ||
481 | } | ||
482 | |||
483 | |||
484 | QStringList 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 | |||
498 | OCompletionMatches 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 | |||
511 | QStringList 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 | |||
521 | OCompletionMatches 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 | |||
535 | QString 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 | |||
568 | QString 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 | ||
603 | QString 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 | |||
679 | void 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 | |||
734 | void 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 | |||
775 | void 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 | |||
811 | void 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 | |||
846 | OCompTreeNode::~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. | ||
860 | OCompTreeNode * 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 :-) | ||
896 | void 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 | |||
916 | QStringList 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 | |||
932 | OCompletionMatches::OCompletionMatches( bool sort_P ) | ||
933 | : _sorting( sort_P ) | ||
934 | { | ||
935 | } | ||
936 | |||
937 | OCompletionMatches::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 | |||
951 | OCompletionMatches::~OCompletionMatches() | ||
952 | { | ||
953 | } | ||
954 | |||
955 | QStringList 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 | |||
966 | void 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 | |||
983 | void 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 | |||
997 | void 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 | |||
1010 | void 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 | |||
1026 | OCompTreeNode *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 | |||
1047 | OCompTreeNode *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 );*/ } | ||