1/*
2 This file is part of the KDE libraries
3 SPDX-FileCopyrightText: 1999 Carsten Pfeiffer <pfeiffer@kde.org>
4
5 SPDX-License-Identifier: LGPL-2.0-or-later
6*/
7
8#ifndef KCOMPLETIONMATCHESWRAPPER_P_H
9#define KCOMPLETIONMATCHESWRAPPER_P_H
10
11#include "kcompletion.h"
12#include "kcomptreenode_p.h"
13
14#include <kcompletionmatches.h>
15
16class KCOMPLETION_EXPORT KCompletionMatchesWrapper
17{
18public:
19 explicit KCompletionMatchesWrapper(KCompletion::SorterFunction const &sorterFunction, KCompletion::CompOrder compOrder = KCompletion::Insertion)
20 : m_sortedListPtr(compOrder == KCompletion::Weighted ? new KCompletionMatchesList : nullptr)
21 , m_dirty(false)
22 , m_compOrder(compOrder)
23 , m_sorterFunction(sorterFunction)
24 {
25 }
26
27 KCompletionMatchesWrapper(const KCompletionMatchesWrapper &) = delete;
28 KCompletionMatchesWrapper &operator=(const KCompletionMatchesWrapper &) = delete;
29
30 void setSorting(KCompletion::CompOrder compOrder)
31 {
32 if (compOrder == KCompletion::Weighted && !m_sortedListPtr) {
33 m_sortedListPtr = std::make_unique<KCompletionMatchesList>();
34 } else if (compOrder != KCompletion::Weighted) {
35 m_sortedListPtr.reset();
36 }
37 m_compOrder = compOrder;
38 m_stringList.clear();
39 m_dirty = false;
40 }
41
42 KCompletion::CompOrder sorting() const
43 {
44 return m_compOrder;
45 }
46
47 void append(int i, const QString &string)
48 {
49 if (m_sortedListPtr) {
50 m_sortedListPtr->insert(i, t: string);
51 } else {
52 m_stringList.append(t: string);
53 }
54 m_dirty = true;
55 }
56
57 void clear()
58 {
59 if (m_sortedListPtr) {
60 m_sortedListPtr->clear();
61 }
62 m_stringList.clear();
63 m_dirty = false;
64 }
65
66 uint size() const
67 {
68 if (m_sortedListPtr) {
69 return m_sortedListPtr->size();
70 }
71 return m_stringList.size();
72 }
73
74 bool isEmpty() const
75 {
76 return size() == 0;
77 }
78
79 QString first() const
80 {
81 return list().constFirst();
82 }
83
84 QString last() const
85 {
86 return list().constLast();
87 }
88
89 inline QStringList list() const;
90
91 inline void findAllCompletions(const KCompTreeNode *, const QString &, bool ignoreCase, bool &hasMultipleMatches);
92
93 inline void extractStringsFromNode(const KCompTreeNode *, const QString &beginning, bool addWeight = false);
94
95 inline void extractStringsFromNodeCI(const KCompTreeNode *, const QString &beginning, const QString &restString);
96
97 mutable QStringList m_stringList;
98 std::unique_ptr<KCompletionMatchesList> m_sortedListPtr;
99 mutable bool m_dirty;
100 KCompletion::CompOrder m_compOrder;
101 KCompletion::SorterFunction const &m_sorterFunction;
102};
103
104void KCompletionMatchesWrapper::findAllCompletions(const KCompTreeNode *treeRoot, const QString &string, bool ignoreCase, bool &hasMultipleMatches)
105{
106 // qDebug() << "*** finding all completions for " << string;
107
108 if (string.isEmpty()) {
109 return;
110 }
111
112 if (ignoreCase) { // case insensitive completion
113 extractStringsFromNodeCI(treeRoot, beginning: QString(), restString: string);
114 hasMultipleMatches = (size() > 1);
115 return;
116 }
117
118 QString completion;
119 const KCompTreeNode *node = treeRoot;
120
121 // start at the tree-root and try to find the search-string
122 for (const QChar ch : string) {
123 node = node->find(ch);
124
125 if (node) {
126 completion += ch;
127 } else {
128 return; // no completion -> return empty list
129 }
130 }
131
132 // Now we have the last node of the to be completed string.
133 // Follow it as long as it has exactly one child (= longest possible
134 // completion)
135
136 while (node->childrenCount() == 1) {
137 node = node->firstChild();
138 if (!node->isNull()) {
139 completion += *node;
140 }
141 // qDebug() << completion << node->latin1();
142 }
143
144 // there is just one single match)
145 if (node->childrenCount() == 0) {
146 append(i: node->weight(), string: completion);
147 }
148
149 else {
150 // node has more than one child
151 // -> recursively find all remaining completions
152 hasMultipleMatches = true;
153 extractStringsFromNode(node, beginning: completion);
154 }
155}
156
157QStringList KCompletionMatchesWrapper::list() const
158{
159 if (m_sortedListPtr && m_dirty) {
160 m_sortedListPtr->sort();
161 m_dirty = false;
162
163 m_stringList.clear();
164 m_stringList.reserve(asize: m_sortedListPtr->size());
165 // high weight == sorted last -> reverse the sorting here
166 std::transform(first: m_sortedListPtr->crbegin(), last: m_sortedListPtr->crend(), result: std::back_inserter(x&: m_stringList), unary_op: [](const KSortableItem<QString> &item) {
167 return item.value();
168 });
169 } else if (m_compOrder == KCompletion::Sorted) {
170 m_sorterFunction(m_stringList);
171 }
172
173 return m_stringList;
174}
175
176void KCompletionMatchesWrapper::extractStringsFromNode(const KCompTreeNode *node, const QString &beginning, bool addWeight)
177{
178 if (!node) {
179 return;
180 }
181
182 // qDebug() << "Beginning: " << beginning;
183 const KCompTreeChildren *list = node->children();
184 QString string;
185 QString w;
186
187 // loop thru all children
188 for (KCompTreeNode *cur = list->begin(); cur; cur = cur->m_next) {
189 string = beginning;
190 node = cur;
191 if (!node->isNull()) {
192 string += *node;
193 }
194
195 while (node && node->childrenCount() == 1) {
196 node = node->firstChild();
197 if (node->isNull()) {
198 break;
199 }
200 string += *node;
201 }
202
203 if (node && node->isNull()) { // we found a leaf
204 if (addWeight) {
205 // add ":num" to the string to store the weighting
206 string += QLatin1Char(':');
207 w.setNum(n: node->weight());
208 string.append(s: w);
209 }
210 append(i: node->weight(), string);
211 }
212
213 // recursively find all other strings.
214 if (node && node->childrenCount() > 1) {
215 extractStringsFromNode(node, beginning: string, addWeight);
216 }
217 }
218}
219
220void KCompletionMatchesWrapper::extractStringsFromNodeCI(const KCompTreeNode *node, const QString &beginning, const QString &restString)
221{
222 if (restString.isEmpty()) {
223 extractStringsFromNode(node, beginning, addWeight: false /*noweight*/);
224 return;
225 }
226
227 QChar ch1 = restString.at(i: 0);
228 QString newRest = restString.mid(position: 1);
229 KCompTreeNode *child1;
230 KCompTreeNode *child2;
231
232 child1 = node->find(ch: ch1); // the correct match
233 if (child1) {
234 extractStringsFromNodeCI(node: child1, beginning: beginning + QChar(*child1), restString: newRest);
235 }
236
237 // append the case insensitive matches, if available
238 if (ch1.isLetter()) {
239 // find out if we have to lower or upper it. Is there a better way?
240 QChar ch2 = ch1.toLower();
241 if (ch1 == ch2) {
242 ch2 = ch1.toUpper();
243 }
244 if (ch1 != ch2) {
245 child2 = node->find(ch: ch2);
246 if (child2) {
247 extractStringsFromNodeCI(node: child2, beginning: beginning + QChar(*child2), restString: newRest);
248 }
249 }
250 }
251}
252
253#endif // KCOMPLETIONMATCHESWRAPPER_P_H
254

source code of kcompletion/src/kcompletionmatcheswrapper_p.h