1/****************************************************************************
2**
3** Copyright (C) 2016 The Qt Company Ltd.
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the QtCore module of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:LGPL$
9** Commercial License Usage
10** Licensees holding valid commercial Qt licenses may use this file in
11** accordance with the commercial license agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and The Qt Company. For licensing terms
14** and conditions see https://www.qt.io/terms-conditions. For further
15** information use the contact form at https://www.qt.io/contact-us.
16**
17** GNU Lesser General Public License Usage
18** Alternatively, this file may be used under the terms of the GNU Lesser
19** General Public License version 3 as published by the Free Software
20** Foundation and appearing in the file LICENSE.LGPL3 included in the
21** packaging of this file. Please review the following information to
22** ensure the GNU Lesser General Public License version 3 requirements
23** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
24**
25** GNU General Public License Usage
26** Alternatively, this file may be used under the terms of the GNU
27** General Public License version 2.0 or (at your option) the GNU General
28** Public license version 3 or any later version approved by the KDE Free
29** Qt Foundation. The licenses are as published by the Free Software
30** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
31** included in the packaging of this file. Please review the following
32** information to ensure the GNU General Public License requirements will
33** be met: https://www.gnu.org/licenses/gpl-2.0.html and
34** https://www.gnu.org/licenses/gpl-3.0.html.
35**
36** $QT_END_LICENSE$
37**
38****************************************************************************/
39
40#include <qstringlist.h>
41#include <qset.h>
42#if QT_CONFIG(regularexpression)
43# include <qregularexpression.h>
44#endif
45#include <private/qduplicatetracker_p.h>
46
47#include <algorithm>
48QT_BEGIN_NAMESPACE
49
50/*! \typedef QStringListIterator
51 \relates QStringList
52
53 The QStringListIterator type definition provides a Java-style const
54 iterator for QStringList.
55
56 QStringList provides both \l{Java-style iterators} and
57 \l{STL-style iterators}. The Java-style const iterator is simply
58 a type definition for QListIterator<QString>.
59
60 \sa QMutableStringListIterator, QStringList::const_iterator
61*/
62
63/*! \typedef QMutableStringListIterator
64 \relates QStringList
65
66 The QStringListIterator type definition provides a Java-style
67 non-const iterator for QStringList.
68
69 QStringList provides both \l{Java-style iterators} and
70 \l{STL-style iterators}. The Java-style non-const iterator is
71 simply a type definition for QMutableListIterator<QString>.
72
73 \sa QStringListIterator, QStringList::iterator
74*/
75
76/*!
77 \class QStringList
78 \inmodule QtCore
79 \brief The QStringList class provides a list of strings.
80
81 \ingroup tools
82 \ingroup shared
83 \ingroup string-processing
84
85 \reentrant
86
87 QStringList inherits from QList<QString>. Like QList, QStringList is
88 \l{implicitly shared}. It provides fast index-based access as well as fast
89 insertions and removals. Passing string lists as value parameters is both
90 fast and safe.
91
92 All of QList's functionality also applies to QStringList. For example, you
93 can use isEmpty() to test whether the list is empty, and you can call
94 functions like append(), prepend(), insert(), replace(), removeAll(),
95 removeAt(), removeFirst(), removeLast(), and removeOne() to modify a
96 QStringList. In addition, QStringList provides a few convenience
97 functions that make handling lists of strings easier:
98
99 \tableofcontents
100
101 \section1 Initializing
102
103 The default constructor creates an empty list. You can use the
104 initializer-list constructor to create a list with elements:
105
106 \snippet qstringlist/main.cpp 0a
107
108 \section1 Adding Strings
109
110 Strings can be added to a list using the \l
111 {QList::insert()}{insert()} \l
112 {QList::append()}{append()}, \l
113 {QList::operator+=()}{operator+=()} and \l
114 {operator<<()} functions.
115
116 \l{operator<<()} can be used to
117 conveniently add multiple elements to a list:
118
119 \snippet qstringlist/main.cpp 0b
120
121 \section1 Iterating Over the Strings
122
123 To iterate over a list, you can either use index positions or
124 QList's Java-style and STL-style iterator types:
125
126 Indexing:
127
128 \snippet qstringlist/main.cpp 1
129
130 Java-style iterator:
131
132 \snippet qstringlist/main.cpp 2
133
134 STL-style iterator:
135
136 \snippet qstringlist/main.cpp 3
137
138 The QStringListIterator class is simply a type definition for
139 QListIterator<QString>. QStringList also provide the
140 QMutableStringListIterator class which is a type definition for
141 QMutableListIterator<QString>.
142
143 \section1 Manipulating the Strings
144
145 QStringList provides several functions allowing you to manipulate
146 the contents of a list. You can concatenate all the strings in a
147 string list into a single string (with an optional separator)
148 using the join() function. For example:
149
150 \snippet qstringlist/main.cpp 4
151
152 The argument to join can be a single character or a string.
153
154 To break up a string into a string list, use the QString::split()
155 function:
156
157 \snippet qstringlist/main.cpp 6
158
159 The argument to split can be a single character, a string or a
160 QRegularExpression.
161
162 In addition, the \l {QStringList::operator+()}{operator+()}
163 function allows you to concatenate two string lists into one. To
164 sort a string list, use the sort() function.
165
166 QString list also provides the filter() function which lets you
167 to extract a new list which contains only those strings which
168 contain a particular substring (or match a particular regular
169 expression):
170
171 \snippet qstringlist/main.cpp 7
172
173 The contains() function tells you whether the list contains a
174 given string, while the indexOf() function returns the index of
175 the first occurrence of the given string. The lastIndexOf()
176 function on the other hand, returns the index of the last
177 occurrence of the string.
178
179 Finally, the replaceInStrings() function calls QString::replace()
180 on each string in the string list in turn. For example:
181
182 \snippet qstringlist/main.cpp 8
183
184 \sa QString
185*/
186
187/*!
188 \fn QStringList::QStringList(const QString &str)
189
190 Constructs a string list that contains the given string, \a
191 str. Longer lists are easily created like this:
192
193 \snippet qstringlist/main.cpp 9
194
195 \sa append()
196*/
197
198/*!
199 \fn QStringList::QStringList(const QList<QString> &other)
200
201 Constructs a copy of \a other.
202
203 This operation takes \l{constant time}, because QStringList is
204 \l{implicitly shared}. This makes returning a QStringList from a
205 function very fast. If a shared instance is modified, it will be
206 copied (copy-on-write), and that takes \l{linear time}.
207
208 \sa operator=()
209*/
210
211/*!
212 \fn QStringList::QStringList(QList<QString> &&other)
213 \overload
214 \since 5.4
215
216 Move-constructs from QList<QString>.
217
218 After a successful construction, \a other will be empty.
219*/
220
221/*!
222 \fn QStringList &QStringList::operator=(const QList<QString> &other)
223 \since 5.4
224
225 Copy assignment operator from QList<QString>. Assigns the \a other
226 list of strings to this string list.
227
228 After the operation, \a other and \c *this will be equal.
229*/
230
231/*!
232 \fn QStringList &QStringList::operator=(QList<QString> &&other)
233 \overload
234 \since 5.4
235
236 Move assignment operator from QList<QString>. Moves the \a other
237 list of strings to this string list.
238
239 After the operation, \a other will be empty.
240*/
241
242/*!
243 \fn void QStringList::sort(Qt::CaseSensitivity cs)
244
245 Sorts the list of strings in ascending order.
246 If \a cs is \l Qt::CaseSensitive (the default), the string comparison
247 is case sensitive; otherwise the comparison is case insensitive.
248
249 Sorting is performed using the STL's std::sort() algorithm,
250 which averages \l{linear-logarithmic time}, i.e. O(\e{n} log \e{n}).
251
252 If you want to sort your strings in an arbitrary order, consider
253 using the QMap class. For example, you could use a QMap<QString,
254 QString> to create a case-insensitive ordering (e.g. with the keys
255 being lower-case versions of the strings, and the values being the
256 strings), or a QMap<int, QString> to sort the strings by some
257 integer index.
258*/
259
260namespace {
261struct CaseInsensitiveLessThan {
262 typedef bool result_type;
263 result_type operator()(const QString &s1, const QString &s2) const
264 {
265 return s1.compare(s2, Qt::CaseInsensitive) < 0;
266 }
267};
268}
269
270void QtPrivate::QStringList_sort(QStringList *that, Qt::CaseSensitivity cs)
271{
272 if (cs == Qt::CaseSensitive)
273 std::sort(that->begin(), that->end());
274 else
275 std::sort(that->begin(), that->end(), CaseInsensitiveLessThan());
276}
277
278
279#if QT_STRINGVIEW_LEVEL < 2
280/*!
281 \fn QStringList QStringList::filter(const QString &str, Qt::CaseSensitivity cs) const
282
283 Returns a list of all the strings containing the substring \a str.
284
285 If \a cs is \l Qt::CaseSensitive (the default), the string
286 comparison is case sensitive; otherwise the comparison is case
287 insensitive.
288
289 \snippet qstringlist/main.cpp 5
290 \snippet qstringlist/main.cpp 10
291
292 This is equivalent to
293
294 \snippet qstringlist/main.cpp 11
295 \snippet qstringlist/main.cpp 12
296
297 \sa contains()
298*/
299#endif
300
301/*!
302 \fn QStringList QStringList::filter(QStringView str, Qt::CaseSensitivity cs) const
303 \overload
304 \since 5.14
305*/
306QStringList QtPrivate::QStringList_filter(const QStringList *that, QStringView str,
307 Qt::CaseSensitivity cs)
308{
309 QStringMatcher matcher(str, cs);
310 QStringList res;
311 for (qsizetype i = 0; i < that->size(); ++i)
312 if (matcher.indexIn(that->at(i)) != -1)
313 res << that->at(i);
314 return res;
315}
316
317template<typename T>
318static bool stringList_contains(const QStringList &stringList, const T &str, Qt::CaseSensitivity cs)
319{
320 for (const auto &string : stringList) {
321 if (string.size() == str.size() && string.compare(str, cs) == 0)
322 return true;
323 }
324 return false;
325}
326
327
328#if QT_STRINGVIEW_LEVEL < 2
329/*!
330 \fn bool QStringList::contains(const QString &str, Qt::CaseSensitivity cs) const
331
332 Returns \c true if the list contains the string \a str; otherwise
333 returns \c false. The search is case insensitive if \a cs is
334 Qt::CaseInsensitive; the search is case sensitive by default.
335
336 \sa indexOf(), lastIndexOf(), QString::contains()
337 */
338#endif
339
340/*!
341 \fn bool QStringList::contains(QStringView str, Qt::CaseSensitivity cs) const
342 \overload
343 \since 5.12
344
345 Returns \c true if the list contains the string \a str; otherwise
346 returns \c false. The search is case insensitive if \a cs is
347 Qt::CaseInsensitive; the search is case sensitive by default.
348 */
349bool QtPrivate::QStringList_contains(const QStringList *that, QStringView str,
350 Qt::CaseSensitivity cs)
351{
352 return stringList_contains(*that, str, cs);
353}
354
355/*!
356 \fn bool QStringList::contains(QLatin1String str, Qt::CaseSensitivity cs) const
357 \overload
358 \since 5.10
359
360 Returns \c true if the list contains the string \a str; otherwise
361 returns \c false. The search is case insensitive if \a cs is
362 Qt::CaseInsensitive; the search is case sensitive by default.
363
364 \sa indexOf(), lastIndexOf(), QString::contains()
365 */
366bool QtPrivate::QStringList_contains(const QStringList *that, QLatin1String str,
367 Qt::CaseSensitivity cs)
368{
369 return stringList_contains(*that, str, cs);
370}
371
372
373#if QT_CONFIG(regularexpression)
374/*!
375 \fn QStringList QStringList::filter(const QRegularExpression &re) const
376 \overload
377 \since 5.0
378
379 Returns a list of all the strings that match the regular
380 expression \a re.
381*/
382QStringList QtPrivate::QStringList_filter(const QStringList *that, const QRegularExpression &re)
383{
384 QStringList res;
385 for (qsizetype i = 0; i < that->size(); ++i) {
386 if (that->at(i).contains(re))
387 res << that->at(i);
388 }
389 return res;
390}
391#endif // QT_CONFIG(regularexpression)
392
393#if QT_STRINGVIEW_LEVEL < 2
394/*!
395 \fn QStringList &QStringList::replaceInStrings(const QString &before, const QString &after, Qt::CaseSensitivity cs)
396
397 Returns a string list where every string has had the \a before
398 text replaced with the \a after text wherever the \a before text
399 is found. The \a before text is matched case-sensitively or not
400 depending on the \a cs flag.
401
402 For example:
403
404 \snippet qstringlist/main.cpp 5
405 \snippet qstringlist/main.cpp 13
406
407 \sa QString::replace()
408*/
409
410/*!
411 \fn QStringList &QStringList::replaceInStrings(QStringView before, const QString &after, Qt::CaseSensitivity cs)
412 \overload
413 \since 5.14
414*/
415
416/*!
417 \fn QStringList &QStringList::replaceInStrings(const QString &before, QStringView after, Qt::CaseSensitivity cs)
418 \overload
419 \since 5.14
420*/
421#endif
422
423/*!
424 \fn QStringList &QStringList::replaceInStrings(QStringView before, QStringView after, Qt::CaseSensitivity cs)
425 \overload
426 \since 5.14
427*/
428void QtPrivate::QStringList_replaceInStrings(QStringList *that, QStringView before,
429 QStringView after, Qt::CaseSensitivity cs)
430{
431 for (qsizetype i = 0; i < that->size(); ++i)
432 (*that)[i].replace(before.data(), before.length(), after.data(), after.length(), cs);
433}
434
435#if QT_CONFIG(regularexpression)
436/*!
437 \fn QStringList &QStringList::replaceInStrings(const QRegularExpression &re, const QString &after)
438 \overload
439 \since 5.0
440
441 Replaces every occurrence of the regular expression \a re, in each of the
442 string lists's strings, with \a after. Returns a reference to the string
443 list.
444
445 For example:
446
447 \snippet qstringlist/main.cpp 5
448 \snippet qstringlist/main.cpp 16
449
450 For regular expressions that contain capturing groups,
451 occurrences of \b{\\1}, \b{\\2}, ..., in \a after are
452 replaced with the string captured by the corresponding capturing group.
453
454 For example:
455
456 \snippet qstringlist/main.cpp 5
457 \snippet qstringlist/main.cpp 17
458*/
459void QtPrivate::QStringList_replaceInStrings(QStringList *that, const QRegularExpression &re, const QString &after)
460{
461 for (qsizetype i = 0; i < that->size(); ++i)
462 (*that)[i].replace(re, after);
463}
464#endif // QT_CONFIG(regularexpression)
465
466static qsizetype accumulatedSize(const QStringList &list, qsizetype seplen)
467{
468 qsizetype result = 0;
469 if (!list.isEmpty()) {
470 for (const auto &e : list)
471 result += e.size() + seplen;
472 result -= seplen;
473 }
474 return result;
475}
476
477#if QT_STRINGVIEW_LEVEL < 2
478/*!
479 \fn QString QStringList::join(const QString &separator) const
480
481 Joins all the string list's strings into a single string with each
482 element separated by the given \a separator (which can be an
483 empty string).
484
485 \sa QString::split()
486*/
487#endif
488
489/*!
490 \fn QString QStringList::join(QChar separator) const
491 \since 5.0
492 \overload join()
493*/
494QString QtPrivate::QStringList_join(const QStringList *that, const QChar *sep, qsizetype seplen)
495{
496 const qsizetype totalLength = accumulatedSize(*that, seplen);
497 const qsizetype size = that->size();
498
499 QString res;
500 if (totalLength == 0)
501 return res;
502 res.reserve(totalLength);
503 for (qsizetype i = 0; i < size; ++i) {
504 if (i)
505 res.append(sep, seplen);
506 res += that->at(i);
507 }
508 return res;
509}
510
511/*!
512 \fn QString QStringList::join(QLatin1String separator) const
513 \since 5.8
514 \overload join()
515*/
516QString QtPrivate::QStringList_join(const QStringList &list, QLatin1String sep)
517{
518 QString result;
519 if (!list.isEmpty()) {
520 result.reserve(accumulatedSize(list, sep.size()));
521 const auto end = list.end();
522 auto it = list.begin();
523 result += *it;
524 while (++it != end) {
525 result += sep;
526 result += *it;
527 }
528 }
529 return result;
530}
531
532/*!
533 \fn QString QStringList::join(QStringView separator) const
534 \overload
535 \since 5.14
536*/
537QString QtPrivate::QStringList_join(const QStringList *that, QStringView sep)
538{
539 return QStringList_join(that, sep.data(), sep.length());
540}
541
542/*!
543 \fn QStringList QStringList::operator+(const QStringList &other) const
544
545 Returns a string list that is the concatenation of this string
546 list with the \a other string list.
547
548 \sa append()
549*/
550
551/*!
552 \fn QStringList &QStringList::operator<<(const QString &str)
553
554 Appends the given string, \a str, to this string list and returns
555 a reference to the string list.
556
557 \sa append()
558*/
559
560/*!
561 \fn QStringList &QStringList::operator<<(const QStringList &other)
562
563 \overload
564
565 Appends the \a other string list to the string list and returns a reference to
566 the latter string list.
567*/
568
569/*!
570 \fn QStringList &QStringList::operator<<(const QList<QString> &other)
571 \since 5.4
572
573 \overload
574
575 Appends the \a other string list to the string list and returns a reference to
576 the latter string list.
577*/
578
579#if QT_CONFIG(regularexpression)
580/*!
581 \fn qsizetype QStringList::indexOf(const QRegularExpression &re, qsizetype from) const
582 \overload
583 \since 5.0
584
585 Returns the index position of the first exact match of \a re in
586 the list, searching forward from index position \a from. Returns
587 -1 if no item matched.
588
589 \sa lastIndexOf()
590*/
591qsizetype QtPrivate::QStringList_indexOf(const QStringList *that, const QRegularExpression &re, qsizetype from)
592{
593 if (from < 0)
594 from = qMax(from + that->size(), qsizetype(0));
595
596 QString exactPattern = QRegularExpression::anchoredPattern(re.pattern());
597 QRegularExpression exactRe(exactPattern, re.patternOptions());
598
599 for (qsizetype i = from; i < that->size(); ++i) {
600 QRegularExpressionMatch m = exactRe.match(that->at(i));
601 if (m.hasMatch())
602 return i;
603 }
604 return -1;
605}
606
607/*!
608 \fn qsizetype QStringList::lastIndexOf(const QRegularExpression &re, qsizetype from) const
609 \overload
610 \since 5.0
611
612 Returns the index position of the last exact match of \a re in
613 the list, searching backward from index position \a from. If \a
614 from is -1 (the default), the search starts at the last item.
615 Returns -1 if no item matched.
616
617 \sa indexOf()
618*/
619qsizetype QtPrivate::QStringList_lastIndexOf(const QStringList *that, const QRegularExpression &re, qsizetype from)
620{
621 if (from < 0)
622 from += that->size();
623 else if (from >= that->size())
624 from = that->size() - 1;
625
626 QString exactPattern = QRegularExpression::anchoredPattern(re.pattern());
627 QRegularExpression exactRe(exactPattern, re.patternOptions());
628
629 for (qsizetype i = from; i >= 0; --i) {
630 QRegularExpressionMatch m = exactRe.match(that->at(i));
631 if (m.hasMatch())
632 return i;
633 }
634 return -1;
635}
636#endif // QT_CONFIG(regularexpression)
637
638/*!
639 \fn qsizetype QStringList::removeDuplicates()
640
641 \since 4.5
642
643 This function removes duplicate entries from a list.
644 The entries do not have to be sorted. They will retain their
645 original order.
646
647 Returns the number of removed entries.
648*/
649qsizetype QtPrivate::QStringList_removeDuplicates(QStringList *that)
650{
651 qsizetype n = that->size();
652 qsizetype j = 0;
653
654 QDuplicateTracker<QString> seen;
655 seen.reserve(n);
656 for (qsizetype i = 0; i < n; ++i) {
657 const QString &s = that->at(i);
658 if (seen.hasSeen(s))
659 continue;
660 if (j != i)
661 that->swapItemsAt(i, j);
662 ++j;
663 }
664 if (n != j)
665 that->erase(that->begin() + j, that->end());
666 return n - j;
667}
668
669QT_END_NAMESPACE
670