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 QtConcurrent 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/*!
41 \page qtconcurrentfilter.html
42 \title Concurrent Filter and Filter-Reduce
43 \ingroup thread
44
45 The QtConcurrent::filter(), QtConcurrent::filtered() and
46 QtConcurrent::filteredReduced() functions filter items in a sequence such
47 as a QList or a QVector in parallel. QtConcurrent::filter() modifies a
48 sequence in-place, QtConcurrent::filtered() returns a new sequence
49 containing the filtered content, and QtConcurrent::filteredReduced()
50 returns a single result.
51
52 These functions are a part of the \l {Qt Concurrent} framework.
53
54 Each of the above functions have a blocking variant that returns the final
55 result instead of a QFuture. You use them in the same way as the
56 asynchronous variants.
57
58 \snippet code/src_concurrent_qtconcurrentfilter.cpp 6
59
60 Note that the result types above are not QFuture objects, but real result
61 types (in this case, QStringList and QSet<QString>).
62
63 \section1 Concurrent Filter
64
65 QtConcurrent::filtered() takes an input sequence and a filter function.
66 This filter function is then called for each item in the sequence, and a
67 new sequence containing the filtered values is returned.
68
69 The filter function must be of the form:
70
71 \snippet code/src_concurrent_qtconcurrentfilter.cpp 0
72
73 T must match the type stored in the sequence. The function returns \c true if
74 the item should be kept, false if it should be discarded.
75
76 This example shows how to keep strings that are all lower-case from a
77 QStringList:
78
79 \snippet code/src_concurrent_qtconcurrentfilter.cpp 1
80
81 The results of the filter are made available through QFuture. See the
82 QFuture and QFutureWatcher documentation for more information on how to
83 use QFuture in your applications.
84
85 If you want to modify a sequence in-place, use QtConcurrent::filter():
86
87 \snippet code/src_concurrent_qtconcurrentfilter.cpp 2
88
89 Since the sequence is modified in place, QtConcurrent::filter() does not
90 return any results via QFuture. However, you can still use QFuture and
91 QFutureWatcher to monitor the status of the filter.
92
93 \section1 Concurrent Filter-Reduce
94
95 QtConcurrent::filteredReduced() is similar to QtConcurrent::filtered(),
96 but instead of returing a sequence with the filtered results, the results
97 are combined into a single value using a reduce function.
98
99 The reduce function must be of the form:
100
101 \snippet code/src_concurrent_qtconcurrentfilter.cpp 3
102
103 T is the type of the final result, U is the type of items being filtered.
104 Note that the return value and return type of the reduce function are not
105 used.
106
107 Call QtConcurrent::filteredReduced() like this:
108
109 \snippet code/src_concurrent_qtconcurrentfilter.cpp 4
110
111 The reduce function will be called once for each result kept by the filter
112 function, and should merge the \e{intermediate} into the \e{result}
113 variable. QtConcurrent::filteredReduced() guarantees that only one thread
114 will call reduce at a time, so using a mutex to lock the result variable
115 is not necessary. The QtConcurrent::ReduceOptions enum provides a way to
116 control the order in which the reduction is done.
117
118 \section1 Additional API Features
119
120 \section2 Using Iterators instead of Sequence
121
122 Each of the above functions has a variant that takes an iterator range
123 instead of a sequence. You use them in the same way as the sequence
124 variants:
125
126 \snippet code/src_concurrent_qtconcurrentfilter.cpp 5
127
128
129 \section2 Using Member Functions
130
131 QtConcurrent::filter(), QtConcurrent::filtered(), and
132 QtConcurrent::filteredReduced() accept pointers to member functions.
133 The member function class type must match the type stored in the sequence:
134
135 \snippet code/src_concurrent_qtconcurrentfilter.cpp 7
136
137 Note that when using QtConcurrent::filteredReduced(), you can mix the use of
138 normal and member functions freely:
139
140 \snippet code/src_concurrent_qtconcurrentfilter.cpp 8
141
142 \section2 Using Function Objects
143
144 QtConcurrent::filter(), QtConcurrent::filtered(), and
145 QtConcurrent::filteredReduced() accept function objects
146 for the filter function. These function objects can be used to
147 add state to a function call. The result_type typedef must define the
148 result type of the function call operator:
149
150 \snippet code/src_concurrent_qtconcurrentfilter.cpp 13
151
152 For the reduce function, function objects are not directly
153 supported. Function objects can, however, be used
154 when the type of the reduction result is explicitly specified:
155
156 \snippet code/src_concurrent_qtconcurrentfilter.cpp 14
157
158 \section2 Wrapping Functions that Take Multiple Arguments
159
160 If you want to use a filter function takes more than one argument, you can
161 use a lambda function or \c std::bind() to transform it onto a function that
162 takes one argument.
163
164 As an example, we use QString::contains():
165
166 \snippet code/src_concurrent_qtconcurrentfilter.cpp 9
167
168 QString::contains() takes 2 arguments (including the "this" pointer) and
169 can't be used with QtConcurrent::filtered() directly, because
170 QtConcurrent::filtered() expects a function that takes one argument. To
171 use QString::contains() with QtConcurrent::filtered() we have to provide a
172 value for the \e regexp argument:
173
174 \snippet code/src_concurrent_qtconcurrentfilter.cpp 12
175*/
176
177/*!
178 \class QtConcurrent::qValueType
179 \inmodule QtConcurrent
180 \internal
181*/
182
183/*!
184 \class QtConcurrent::qValueType<const T*>
185 \inmodule QtConcurrent
186 \internal
187*/
188
189
190/*!
191 \class QtConcurrent::qValueType<T*>
192 \inmodule QtConcurrent
193 \internal
194*/
195
196/*!
197 \class QtConcurrent::FilterKernel
198 \inmodule QtConcurrent
199 \internal
200*/
201
202/*!
203 \class QtConcurrent::FilteredReducedKernel
204 \inmodule QtConcurrent
205 \internal
206*/
207
208/*!
209 \class QtConcurrent::FilteredEachKernel
210 \inmodule QtConcurrent
211 \internal
212*/
213
214/*!
215 \fn [QtConcurrent-1] template <typename Sequence, typename KeepFunctor, typename ReduceFunctor> ThreadEngineStarter<void> QtConcurrent::filterInternal(Sequence &sequence, KeepFunctor keep, ReduceFunctor reduce)
216 \internal
217*/
218
219/*!
220 \fn template <typename Sequence, typename KeepFunctor> QFuture<void> QtConcurrent::filter(Sequence &sequence, KeepFunctor filterFunction)
221
222 Calls \a filterFunction once for each item in \a sequence. If
223 \a filterFunction returns \c true, the item is kept in \a sequence;
224 otherwise, the item is removed from \a sequence.
225
226 \sa {Concurrent Filter and Filter-Reduce}
227*/
228
229/*!
230 \fn template <typename Sequence, typename KeepFunctor> QFuture<Sequence::value_type> QtConcurrent::filtered(const Sequence &sequence, KeepFunctor filterFunction)
231
232 Calls \a filterFunction once for each item in \a sequence and returns a
233 new Sequence of kept items. If \a filterFunction returns \c true, a copy of
234 the item is put in the new Sequence. Otherwise, the item will \e not
235 appear in the new Sequence.
236
237 \sa {Concurrent Filter and Filter-Reduce}
238*/
239
240/*!
241 \fn template <typename Iterator, typename KeepFunctor> QFuture<typename QtConcurrent::qValueType<Iterator>::value_type> QtConcurrent::filtered(Iterator begin, Iterator end, KeepFunctor filterFunction)
242
243 Calls \a filterFunction once for each item from \a begin to \a end and
244 returns a new Sequence of kept items. If \a filterFunction returns \c true, a
245 copy of the item is put in the new Sequence. Otherwise, the item will
246 \e not appear in the new Sequence.
247
248 \sa {Concurrent Filter and Filter-Reduce}
249*/
250
251/*!
252 \fn template <typename ResultType, typename Sequence, typename KeepFunctor, typename ReduceFunctor> QFuture<ResultType> QtConcurrent::filteredReduced(const Sequence &sequence, KeepFunctor filterFunction, ReduceFunctor reduceFunction, QtConcurrent::ReduceOptions reduceOptions)
253
254 Calls \a filterFunction once for each item in \a sequence. If
255 \a filterFunction returns \c true for an item, that item is then passed to
256 \a reduceFunction. In other words, the return value is the result of
257 \a reduceFunction for each item where \a filterFunction returns \c true.
258
259 Note that while \a filterFunction is called concurrently, only one thread
260 at a time will call \a reduceFunction. The order in which \a reduceFunction
261 is called is undefined if \a reduceOptions is
262 QtConcurrent::UnorderedReduce. If \a reduceOptions is
263 QtConcurrent::OrderedReduce, \a reduceFunction is called in the order of
264 the original sequence.
265
266 \sa {Concurrent Filter and Filter-Reduce}
267*/
268
269/*!
270 \fn template <typename ResultType, typename Iterator, typename KeepFunctor, typename ReduceFunctor> QFuture<ResultType> QtConcurrent::filteredReduced(Iterator begin, Iterator end, KeepFunctor filterFunction, ReduceFunctor reduceFunction, QtConcurrent::ReduceOptions reduceOptions)
271
272 Calls \a filterFunction once for each item from \a begin to \a end. If
273 \a filterFunction returns \c true for an item, that item is then passed to
274 \a reduceFunction. In other words, the return value is the result of
275 \a reduceFunction for each item where \a filterFunction returns \c true.
276
277 Note that while \a filterFunction is called concurrently, only one thread
278 at a time will call \a reduceFunction. The order in which
279 \a reduceFunction is called is undefined if \a reduceOptions is
280 QtConcurrent::UnorderedReduce. If \a reduceOptions is
281 QtConcurrent::OrderedReduce, the \a reduceFunction is called in the order
282 of the original sequence.
283
284 \sa {Concurrent Filter and Filter-Reduce}
285*/
286
287/*!
288 \fn template <typename Sequence, typename KeepFunctor> void QtConcurrent::blockingFilter(Sequence &sequence, KeepFunctor filterFunction)
289
290 Calls \a filterFunction once for each item in \a sequence. If
291 \a filterFunction returns \c true, the item is kept in \a sequence;
292 otherwise, the item is removed from \a sequence.
293
294 \note This function will block until all items in the sequence have been processed.
295
296 \sa {Concurrent Filter and Filter-Reduce}
297*/
298
299/*!
300 \fn template <typename Sequence, typename KeepFunctor> Sequence QtConcurrent::blockingFiltered(const Sequence &sequence, KeepFunctor filterFunction)
301
302 Calls \a filterFunction once for each item in \a sequence and returns a
303 new Sequence of kept items. If \a filterFunction returns \c true, a copy of
304 the item is put in the new Sequence. Otherwise, the item will \e not
305 appear in the new Sequence.
306
307 \note This function will block until all items in the sequence have been processed.
308
309 \sa filtered(), {Concurrent Filter and Filter-Reduce}
310*/
311
312/*!
313 \fn template <typename OutputSequence, typename Iterator, typename KeepFunctor> OutputSequence QtConcurrent::blockingFiltered(Iterator begin, Iterator end, KeepFunctor filterFunction)
314
315 Calls \a filterFunction once for each item from \a begin to \a end and
316 returns a new Sequence of kept items. If \a filterFunction returns \c true, a
317 copy of the item is put in the new Sequence. Otherwise, the item will
318 \e not appear in the new Sequence.
319
320 \note This function will block until the iterator reaches the end of the
321 sequence being processed.
322
323 \sa filtered(), {Concurrent Filter and Filter-Reduce}
324*/
325
326/*!
327 \fn template <typename ResultType, typename Sequence, typename KeepFunctor, typename ReduceFunctor> ResultType QtConcurrent::blockingFilteredReduced(const Sequence &sequence, KeepFunctor filterFunction, ReduceFunctor reduceFunction, QtConcurrent::ReduceOptions reduceOptions)
328
329 Calls \a filterFunction once for each item in \a sequence. If
330 \a filterFunction returns \c true for an item, that item is then passed to
331 \a reduceFunction. In other words, the return value is the result of
332 \a reduceFunction for each item where \a filterFunction returns \c true.
333
334 Note that while \a filterFunction is called concurrently, only one thread
335 at a time will call \a reduceFunction. The order in which \a reduceFunction
336 is called is undefined if \a reduceOptions is
337 QtConcurrent::UnorderedReduce. If \a reduceOptions is
338 QtConcurrent::OrderedReduce, \a reduceFunction is called in the order of
339 the original sequence.
340
341 \note This function will block until all items in the sequence have been processed.
342
343 \sa filteredReduced(), {Concurrent Filter and Filter-Reduce}
344*/
345
346/*!
347 \fn template <typename ResultType, typename Iterator, typename KeepFunctor, typename ReduceFunctor> ResultType QtConcurrent::blockingFilteredReduced(Iterator begin, Iterator end, KeepFunctor filterFunction, ReduceFunctor reduceFunction, QtConcurrent::ReduceOptions reduceOptions)
348
349 Calls \a filterFunction once for each item from \a begin to \a end. If
350 \a filterFunction returns \c true for an item, that item is then passed to
351 \a reduceFunction. In other words, the return value is the result of
352 \a reduceFunction for each item where \a filterFunction returns \c true.
353
354 Note that while \a filterFunction is called concurrently, only one thread
355 at a time will call \a reduceFunction. The order in which
356 \a reduceFunction is called is undefined if \a reduceOptions is
357 QtConcurrent::UnorderedReduce. If \a reduceOptions is
358 QtConcurrent::OrderedReduce, the \a reduceFunction is called in the order
359 of the original sequence.
360
361 \note This function will block until the iterator reaches the end of the
362 sequence being processed.
363
364 \sa filteredReduced(), {Concurrent Filter and Filter-Reduce}
365*/
366
367/*!
368 \fn [QtConcurrent-2] ThreadEngineStarter<typename qValueType<Iterator>::value_type> QtConcurrent::startFiltered(Iterator begin, Iterator end, KeepFunctor functor)
369 \internal
370*/
371
372/*!
373 \fn [QtConcurrent-3] ThreadEngineStarter<typename Sequence::value_type> QtConcurrent::startFiltered(const Sequence &sequence, KeepFunctor functor)
374 \internal
375*/
376
377/*!
378 \fn [QtConcurrent-4] ThreadEngineStarter<ResultType> QtConcurrent::startFilteredReduced(const Sequence & sequence, MapFunctor mapFunctor, ReduceFunctor reduceFunctor, ReduceOptions options)
379 \internal
380*/
381
382/*!
383 \fn [QtConcurrent-5] ThreadEngineStarter<ResultType> QtConcurrent::startFilteredReduced(Iterator begin, Iterator end, MapFunctor mapFunctor, ReduceFunctor reduceFunctor, ReduceOptions options)
384 \internal
385*/
386
387