1 /****************************************************************************
2 **
3 ** Copyright (C) 2016 The Qt Company Ltd.
4 ** Contact: https://www.qt.io/licensing/
5 **
6 ** This file is part of Qt Creator.
7 **
8 ** Commercial License Usage
9 ** Licensees holding valid commercial Qt licenses may use this file in
10 ** accordance with the commercial license agreement provided with the
11 ** Software or, alternatively, in accordance with the terms contained in
12 ** a written agreement between you and The Qt Company. For licensing terms
13 ** and conditions see https://www.qt.io/terms-conditions. For further
14 ** information use the contact form at https://www.qt.io/contact-us.
15 **
16 ** GNU General Public License Usage
17 ** Alternatively, this file may be used under the terms of the GNU
18 ** General Public License version 3 as published by the Free Software
19 ** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT
20 ** included in the packaging of this file. Please review the following
21 ** information to ensure the GNU General Public License requirements will
22 ** be met: https://www.gnu.org/licenses/gpl-3.0.html.
23 **
24 ****************************************************************************/
25 
26 #pragma once
27 
28 #include "predicates.h"
29 #include "optional.h"
30 
31 #include <qcompilerdetection.h> // for Q_REQUIRED_RESULT
32 
33 #include <algorithm>
34 #include <map>
35 #include <memory>
36 #include <set>
37 #include <tuple>
38 #include <unordered_map>
39 #include <unordered_set>
40 
41 #include <QHash>
42 #include <QObject>
43 #include <QSet>
44 #include <QStringList>
45 
46 #include <memory>
47 #include <type_traits>
48 
49 namespace Utils
50 {
51 
52 /////////////////////////
53 // anyOf
54 /////////////////////////
55 template<typename T, typename F>
56 bool anyOf(const T &container, F predicate);
57 template<typename T, typename R, typename S>
58 bool anyOf(const T &container, R (S::*predicate)() const);
59 template<typename T, typename R, typename S>
60 bool anyOf(const T &container, R S::*member);
61 
62 /////////////////////////
63 // count
64 /////////////////////////
65 template<typename T, typename F>
66 int count(const T &container, F predicate);
67 
68 /////////////////////////
69 // allOf
70 /////////////////////////
71 template<typename T, typename F>
72 bool allOf(const T &container, F predicate);
73 
74 /////////////////////////
75 // erase
76 /////////////////////////
77 template<typename T, typename F>
78 void erase(T &container, F predicate);
79 
80 /////////////////////////
81 // contains
82 /////////////////////////
83 template<typename T, typename F>
84 bool contains(const T &container, F function);
85 template<typename T, typename R, typename S>
86 bool contains(const T &container, R (S::*function)() const);
87 template<typename C, typename R, typename S>
88 bool contains(const C &container, R S::*member);
89 
90 /////////////////////////
91 // findOr
92 /////////////////////////
93 template<typename C, typename F>
94 Q_REQUIRED_RESULT typename C::value_type findOr(const C &container,
95                                                 typename C::value_type other,
96                                                 F function);
97 template<typename T, typename R, typename S>
98 Q_REQUIRED_RESULT typename T::value_type findOr(const T &container,
99                                                 typename T::value_type other,
100                                                 R (S::*function)() const);
101 template<typename T, typename R, typename S>
102 Q_REQUIRED_RESULT typename T::value_type findOr(const T &container,
103                                                 typename T::value_type other,
104                                                 R S::*member);
105 
106 /////////////////////////
107 // findOrDefault
108 /////////////////////////
109 template<typename C, typename F>
110 Q_REQUIRED_RESULT typename std::enable_if_t<std::is_copy_assignable<typename C::value_type>::value,
111                                             typename C::value_type>
112 findOrDefault(const C &container, F function);
113 template<typename C, typename R, typename S>
114 Q_REQUIRED_RESULT typename std::enable_if_t<std::is_copy_assignable<typename C::value_type>::value,
115                                             typename C::value_type>
116 findOrDefault(const C &container, R (S::*function)() const);
117 template<typename C, typename R, typename S>
118 Q_REQUIRED_RESULT typename std::enable_if_t<std::is_copy_assignable<typename C::value_type>::value,
119                                             typename C::value_type>
120 findOrDefault(const C &container, R S::*member);
121 
122 /////////////////////////
123 // indexOf
124 /////////////////////////
125 template<typename C, typename F>
126 Q_REQUIRED_RESULT int indexOf(const C &container, F function);
127 
128 /////////////////////////
129 // maxElementOr
130 /////////////////////////
131 template<typename T>
132 typename T::value_type maxElementOr(const T &container, typename T::value_type other);
133 
134 /////////////////////////
135 // filtered
136 /////////////////////////
137 template<typename C, typename F>
138 Q_REQUIRED_RESULT C filtered(const C &container, F predicate);
139 template<typename C, typename R, typename S>
140 Q_REQUIRED_RESULT C filtered(const C &container, R (S::*predicate)() const);
141 
142 /////////////////////////
143 // partition
144 /////////////////////////
145 // Recommended usage:
146 // C hit;
147 // C miss;
148 // std::tie(hit, miss) = Utils::partition(container, predicate);
149 template<typename C, typename F>
150 Q_REQUIRED_RESULT std::tuple<C, C> partition(const C &container, F predicate);
151 template<typename C, typename R, typename S>
152 Q_REQUIRED_RESULT std::tuple<C, C> partition(const C &container, R (S::*predicate)() const);
153 
154 /////////////////////////
155 // filteredUnique
156 /////////////////////////
157 template<typename C>
158 Q_REQUIRED_RESULT C filteredUnique(const C &container);
159 
160 /////////////////////////
161 // qobject_container_cast
162 /////////////////////////
163 template<class T, template<typename> class Container, typename Base>
164 Container<T> qobject_container_cast(const Container<Base> &container);
165 
166 /////////////////////////
167 // static_container_cast
168 /////////////////////////
169 template<class T, template<typename> class Container, typename Base>
170 Container<T> static_container_cast(const Container<Base> &container);
171 
172 /////////////////////////
173 // sort
174 /////////////////////////
175 template<typename Container>
176 inline void sort(Container &container);
177 template<typename Container, typename Predicate>
178 inline void sort(Container &container, Predicate p);
179 template<typename Container, typename R, typename S>
180 inline void sort(Container &container, R S::*member);
181 template<typename Container, typename R, typename S>
182 inline void sort(Container &container, R (S::*function)() const);
183 
184 /////////////////////////
185 // reverseForeach
186 /////////////////////////
187 template<typename Container, typename Op>
188 inline void reverseForeach(const Container &c, const Op &operation);
189 
190 /////////////////////////
191 // toReferences
192 /////////////////////////
193 template<template<typename...> class ResultContainer, typename SourceContainer>
194 auto toReferences(SourceContainer &sources);
195 template<typename SourceContainer>
196 auto toReferences(SourceContainer &sources);
197 
198 /////////////////////////
199 // toConstReferences
200 /////////////////////////
201 template<template<typename...> class ResultContainer, typename SourceContainer>
202 auto toConstReferences(const SourceContainer &sources);
203 template<typename SourceContainer>
204 auto toConstReferences(const SourceContainer &sources);
205 
206 /////////////////////////
207 // take
208 /////////////////////////
209 template<class C, typename P>
210 Q_REQUIRED_RESULT optional<typename C::value_type> take(C &container, P predicate);
211 template<typename C, typename R, typename S>
212 Q_REQUIRED_RESULT decltype(auto) take(C &container, R S::*member);
213 template<typename C, typename R, typename S>
214 Q_REQUIRED_RESULT decltype(auto) take(C &container, R (S::*function)() const);
215 
216 /////////////////////////
217 // setUnionMerge
218 /////////////////////////
219 // Works like std::set_union but provides a merge function for items that match
220 // !(a > b) && !(b > a) which normally means that there is an "equal" match.
221 // It uses iterators to support move_iterators.
222 template<class InputIt1, class InputIt2, class OutputIt, class Merge, class Compare>
223 OutputIt setUnionMerge(InputIt1 first1,
224                        InputIt1 last1,
225                        InputIt2 first2,
226                        InputIt2 last2,
227                        OutputIt d_first,
228                        Merge merge,
229                        Compare comp);
230 template<class InputIt1, class InputIt2, class OutputIt, class Merge>
231 OutputIt setUnionMerge(
232     InputIt1 first1, InputIt1 last1, InputIt2 first2, InputIt2 last2, OutputIt d_first, Merge merge);
233 template<class OutputContainer, class InputContainer1, class InputContainer2, class Merge, class Compare>
234 OutputContainer setUnionMerge(InputContainer1 &&input1,
235                               InputContainer2 &&input2,
236                               Merge merge,
237                               Compare comp);
238 template<class OutputContainer, class InputContainer1, class InputContainer2, class Merge>
239 OutputContainer setUnionMerge(InputContainer1 &&input1, InputContainer2 &&input2, Merge merge);
240 
241 /////////////////////////
242 // usize / ssize
243 /////////////////////////
244 template<typename Container>
245 std::make_unsigned_t<typename Container::size_type> usize(Container container);
246 template<typename Container>
247 std::make_signed_t<typename Container::size_type> ssize(Container container);
248 
249 /////////////////////////
250 // setUnion
251 /////////////////////////
252 template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Compare>
253 OutputIterator set_union(InputIterator1 first1,
254                          InputIterator1 last1,
255                          InputIterator2 first2,
256                          InputIterator2 last2,
257                          OutputIterator result,
258                          Compare comp);
259 template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
260 OutputIterator set_union(InputIterator1 first1,
261                          InputIterator1 last1,
262                          InputIterator2 first2,
263                          InputIterator2 last2,
264                          OutputIterator result);
265 
266 /////////////////////////
267 // transform
268 /////////////////////////
269 // function without result type deduction:
270 template<typename ResultContainer, // complete result container type
271          typename SC,              // input container type
272          typename F>               // function type
273 Q_REQUIRED_RESULT decltype(auto) transform(SC &&container, F function);
274 
275 // function with result type deduction:
276 template<template<typename> class C, // result container type
277          typename SC,                // input container type
278          typename F,                 // function type
279          typename Value = typename std::decay_t<SC>::value_type,
280          typename Result = std::decay_t<std::result_of_t<F(Value &)>>,
281          typename ResultContainer = C<Result>>
282 Q_REQUIRED_RESULT decltype(auto) transform(SC &&container, F function);
283 #ifdef Q_CC_CLANG
284 // "Matching of template template-arguments excludes compatible templates"
285 // http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2016/p0522r0.html (P0522R0)
286 // in C++17 makes the above match e.g. C=std::vector even though that takes two
287 // template parameters. Unfortunately the following one matches too, and there is no additional
288 // partial ordering rule, resulting in an ambiguous call for this previously valid code.
289 // GCC and MSVC ignore that issue and follow the standard to the letter, but Clang only
290 // enables the new behavior when given -frelaxed-template-template-args .
291 // To avoid requiring everyone using this header to enable that feature, keep the old implementation
292 // for Clang.
293 template<template<typename, typename> class C, // result container type
294          typename SC,                          // input container type
295          typename F,                           // function type
296          typename Value = typename std::decay_t<SC>::value_type,
297          typename Result = std::decay_t<std::result_of_t<F(Value &)>>,
298          typename ResultContainer = C<Result, std::allocator<Result>>>
299 Q_REQUIRED_RESULT decltype(auto) transform(SC &&container, F function);
300 #endif
301 
302 // member function without result type deduction:
303 template<template<typename...> class C, // result container type
304          typename SC,                   // input container type
305          typename R,
306          typename S>
307 Q_REQUIRED_RESULT decltype(auto) transform(SC &&container, R (S::*p)() const);
308 
309 // member function with result type deduction:
310 template<typename ResultContainer, // complete result container type
311          typename SC,              // input container type
312          typename R,
313          typename S>
314 Q_REQUIRED_RESULT decltype(auto) transform(SC &&container, R (S::*p)() const);
315 
316 // member without result type deduction:
317 template<typename ResultContainer, // complete result container type
318          typename SC,              // input container
319          typename R,
320          typename S>
321 Q_REQUIRED_RESULT decltype(auto) transform(SC &&container, R S::*p);
322 
323 // member with result type deduction:
324 template<template<typename...> class C, // result container
325          typename SC,                   // input container
326          typename R,
327          typename S>
328 Q_REQUIRED_RESULT decltype(auto) transform(SC &&container, R S::*p);
329 
330 // same container types for input and output, const input
331 // function:
332 template<template<typename...> class C, // container type
333          typename F,                    // function type
334          typename... CArgs>             // Arguments to SC
335 Q_REQUIRED_RESULT decltype(auto) transform(const C<CArgs...> &container, F function);
336 
337 // same container types for input and output, const input
338 // member function:
339 template<template<typename...> class C, // container type
340          typename R,
341          typename S,
342          typename... CArgs> // Arguments to SC
343 Q_REQUIRED_RESULT decltype(auto) transform(const C<CArgs...> &container, R (S::*p)() const);
344 
345 // same container types for input and output, const input
346 // members:
347 template<template<typename...> class C, // container
348          typename R,
349          typename S,
350          typename... CArgs> // Arguments to SC
351 Q_REQUIRED_RESULT decltype(auto) transform(const C<CArgs...> &container, R S::*p);
352 
353 // same container types for input and output, non-const input
354 // function:
355 template<template<typename...> class C, // container type
356          typename F,                    // function type
357          typename... CArgs>             // Arguments to SC
358 Q_REQUIRED_RESULT decltype(auto) transform(C<CArgs...> &container, F function);
359 
360 // same container types for input and output, non-const input
361 // member function:
362 template<template<typename...> class C, // container type
363          typename R,
364          typename S,
365          typename... CArgs> // Arguments to SC
366 Q_REQUIRED_RESULT decltype(auto) transform(C<CArgs...> &container, R (S::*p)() const);
367 
368 // same container types for input and output, non-const input
369 // members:
370 template<template<typename...> class C, // container
371          typename R,
372          typename S,
373          typename... CArgs> // Arguments to SC
374 Q_REQUIRED_RESULT decltype(auto) transform(C<CArgs...> &container, R S::*p);
375 
376 /////////////////////////////////////////////////////////////////////////////
377 ////////    Implementations    //////////////////////////////////////////////
378 /////////////////////////////////////////////////////////////////////////////
379 
380 //////////////////
381 // anyOf
382 /////////////////
383 template<typename T, typename F>
anyOf(const T & container,F predicate)384 bool anyOf(const T &container, F predicate)
385 {
386     return std::any_of(std::begin(container), std::end(container), predicate);
387 }
388 
389 // anyOf taking a member function pointer
390 template<typename T, typename R, typename S>
anyOf(const T & container,R (S::* predicate)()const)391 bool anyOf(const T &container, R (S::*predicate)() const)
392 {
393     return std::any_of(std::begin(container), std::end(container), std::mem_fn(predicate));
394 }
395 
396 // anyOf taking a member pointer
397 template<typename T, typename R, typename S>
anyOf(const T & container,R S::* member)398 bool anyOf(const T &container, R S::*member)
399 {
400     return std::any_of(std::begin(container), std::end(container), std::mem_fn(member));
401 }
402 
403 
404 //////////////////
405 // count
406 /////////////////
407 template<typename T, typename F>
count(const T & container,F predicate)408 int count(const T &container, F predicate)
409 {
410     return std::count_if(std::begin(container), std::end(container), predicate);
411 }
412 
413 //////////////////
414 // allOf
415 /////////////////
416 template<typename T, typename F>
allOf(const T & container,F predicate)417 bool allOf(const T &container, F predicate)
418 {
419     return std::all_of(std::begin(container), std::end(container), predicate);
420 }
421 
422 // allOf taking a member function pointer
423 template<typename T, typename R, typename S>
allOf(const T & container,R (S::* predicate)()const)424 bool allOf(const T &container, R (S::*predicate)() const)
425 {
426     return std::all_of(std::begin(container), std::end(container), std::mem_fn(predicate));
427 }
428 
429 // allOf taking a member pointer
430 template<typename T, typename R, typename S>
allOf(const T & container,R S::* member)431 bool allOf(const T &container, R S::*member)
432 {
433     return std::all_of(std::begin(container), std::end(container), std::mem_fn(member));
434 }
435 
436 //////////////////
437 // erase
438 /////////////////
439 template<typename T, typename F>
erase(T & container,F predicate)440 void erase(T &container, F predicate)
441 {
442     container.erase(std::remove_if(std::begin(container), std::end(container), predicate),
443                     std::end(container));
444 }
445 
446 
447 //////////////////
448 // contains
449 /////////////////
450 template<typename T, typename F>
contains(const T & container,F function)451 bool contains(const T &container, F function)
452 {
453     return anyOf(container, function);
454 }
455 
456 template<typename T, typename R, typename S>
contains(const T & container,R (S::* function)()const)457 bool contains(const T &container, R (S::*function)() const)
458 {
459     return anyOf(container, function);
460 }
461 
462 template<typename C, typename R, typename S>
contains(const C & container,R S::* member)463 bool contains(const C &container, R S::*member)
464 {
465     return anyOf(container, std::mem_fn(member));
466 }
467 
468 //////////////////
469 // findOr
470 /////////////////
471 template<typename C, typename F>
472 Q_REQUIRED_RESULT
findOr(const C & container,typename C::value_type other,F function)473 typename C::value_type findOr(const C &container, typename C::value_type other, F function)
474 {
475     typename C::const_iterator begin = std::begin(container);
476     typename C::const_iterator end = std::end(container);
477 
478     typename C::const_iterator it = std::find_if(begin, end, function);
479     return it == end ? other : *it;
480 }
481 
482 template<typename T, typename R, typename S>
483 Q_REQUIRED_RESULT
findOr(const T & container,typename T::value_type other,R (S::* function)()const)484 typename T::value_type findOr(const T &container, typename T::value_type other, R (S::*function)() const)
485 {
486     return findOr(container, other, std::mem_fn(function));
487 }
488 
489 template<typename T, typename R, typename S>
490 Q_REQUIRED_RESULT
findOr(const T & container,typename T::value_type other,R S::* member)491 typename T::value_type findOr(const T &container, typename T::value_type other, R S::*member)
492 {
493     return findOr(container, other, std::mem_fn(member));
494 }
495 
496 //////////////////
497 // findOrDefault
498 //////////////////
499 // Default implementation:
500 template<typename C, typename F>
501 Q_REQUIRED_RESULT
502 typename std::enable_if_t<std::is_copy_assignable<typename C::value_type>::value, typename C::value_type>
findOrDefault(const C & container,F function)503 findOrDefault(const C &container, F function)
504 {
505     return findOr(container, typename C::value_type(), function);
506 }
507 
508 template<typename C, typename R, typename S>
509 Q_REQUIRED_RESULT
510 typename std::enable_if_t<std::is_copy_assignable<typename C::value_type>::value, typename C::value_type>
findOrDefault(const C & container,R (S::* function)()const)511 findOrDefault(const C &container, R (S::*function)() const)
512 {
513     return findOr(container, typename C::value_type(), std::mem_fn(function));
514 }
515 
516 template<typename C, typename R, typename S>
517 Q_REQUIRED_RESULT
518 typename std::enable_if_t<std::is_copy_assignable<typename C::value_type>::value, typename C::value_type>
findOrDefault(const C & container,R S::* member)519 findOrDefault(const C &container, R S::*member)
520 {
521     return findOr(container, typename C::value_type(), std::mem_fn(member));
522 }
523 
524 //////////////////
525 // index of:
526 //////////////////
527 
528 template<typename C, typename F>
529 Q_REQUIRED_RESULT
indexOf(const C & container,F function)530 int indexOf(const C& container, F function)
531 {
532     typename C::const_iterator begin = std::begin(container);
533     typename C::const_iterator end = std::end(container);
534 
535     typename C::const_iterator it = std::find_if(begin, end, function);
536     return it == end ? -1 : std::distance(begin, it);
537 }
538 
539 
540 //////////////////
541 // max element
542 //////////////////
543 
544 template<typename T>
maxElementOr(const T & container,typename T::value_type other)545 typename T::value_type maxElementOr(const T &container, typename T::value_type other)
546 {
547     typename T::const_iterator begin = std::begin(container);
548     typename T::const_iterator end = std::end(container);
549 
550     typename T::const_iterator it = std::max_element(begin, end);
551     if (it == end)
552         return other;
553     return *it;
554 }
555 
556 
557 //////////////////
558 // transform
559 /////////////////
560 
561 namespace {
562 /////////////////
563 // helper code for transform to use back_inserter and thus push_back for everything
564 // and insert for QSet<>
565 //
566 
567 // SetInsertIterator, straight from the standard for insert_iterator
568 // just without the additional parameter to insert
569 template<class Container>
570 class SetInsertIterator
571 {
572 protected:
573   Container *container;
574 
575 public:
576     using iterator_category = std::output_iterator_tag;
577     using container_type = Container;
SetInsertIterator(Container & x)578     explicit SetInsertIterator(Container &x)
579         : container(&x)
580     {}
581     SetInsertIterator<Container> &operator=(const typename Container::value_type &value)
582     {
583         container->insert(value);
584         return *this;
585     }
586     SetInsertIterator<Container> &operator=(typename Container::value_type &&value)
587     {
588         container->insert(std::move(value));
589         return *this;
590     }
591     SetInsertIterator<Container> &operator*() { return *this; }
592     SetInsertIterator<Container> &operator++() { return *this; }
593     SetInsertIterator<Container> operator++(int) { return *this; }
594 };
595 
596 // for QMap / QHash, inserting a std::pair / QPair
597 template<class Container>
598 class MapInsertIterator
599 {
600 protected:
601     Container *container;
602 
603 public:
604     using iterator_category = std::output_iterator_tag;
605     using container_type = Container;
MapInsertIterator(Container & x)606     explicit MapInsertIterator(Container &x)
607         : container(&x)
608     {}
609     MapInsertIterator<Container> &operator=(
610         const std::pair<const typename Container::key_type, typename Container::mapped_type> &value)
611     { container->insert(value.first, value.second); return *this; }
612     MapInsertIterator<Container> &operator=(
613         const QPair<typename Container::key_type, typename Container::mapped_type> &value)
614     { container->insert(value.first, value.second); return *this; }
615     MapInsertIterator<Container> &operator*() { return *this; }
616     MapInsertIterator<Container> &operator++() { return *this; }
617     MapInsertIterator<Container> operator++(int) { return *this; }
618 };
619 
620 // inserter helper function, returns a std::back_inserter for most containers
621 // and is overloaded for QSet<> and other containers without push_back, returning custom inserters
622 template<typename C>
623 inline std::back_insert_iterator<C>
inserter(C & container)624 inserter(C &container)
625 {
626     return std::back_inserter(container);
627 }
628 
629 template<typename X>
630 inline SetInsertIterator<QSet<X>>
inserter(QSet<X> & container)631 inserter(QSet<X> &container)
632 {
633     return SetInsertIterator<QSet<X>>(container);
634 }
635 
636 template<typename K, typename C, typename A>
637 inline SetInsertIterator<std::set<K, C, A>>
inserter(std::set<K,C,A> & container)638 inserter(std::set<K, C, A> &container)
639 {
640     return SetInsertIterator<std::set<K, C, A>>(container);
641 }
642 
643 template<typename K, typename H, typename C, typename A>
644 inline SetInsertIterator<std::unordered_set<K, H, C, A>>
inserter(std::unordered_set<K,H,C,A> & container)645 inserter(std::unordered_set<K, H, C, A> &container)
646 {
647     return SetInsertIterator<std::unordered_set<K, H, C, A>>(container);
648 }
649 
650 template<typename K, typename V, typename C, typename A>
651 inline SetInsertIterator<std::map<K, V, C, A>>
inserter(std::map<K,V,C,A> & container)652 inserter(std::map<K, V, C, A> &container)
653 {
654     return SetInsertIterator<std::map<K, V, C, A>>(container);
655 }
656 
657 template<typename K, typename V, typename H, typename C, typename A>
658 inline SetInsertIterator<std::unordered_map<K, V, H, C, A>>
inserter(std::unordered_map<K,V,H,C,A> & container)659 inserter(std::unordered_map<K, V, H, C, A> &container)
660 {
661     return SetInsertIterator<std::unordered_map<K, V, H, C, A>>(container);
662 }
663 
664 template<typename K, typename V>
665 inline MapInsertIterator<QMap<K, V>>
inserter(QMap<K,V> & container)666 inserter(QMap<K, V> &container)
667 {
668     return MapInsertIterator<QMap<K, V>>(container);
669 }
670 
671 template<typename K, typename V>
672 inline MapInsertIterator<QHash<K, V>>
inserter(QHash<K,V> & container)673 inserter(QHash<K, V> &container)
674 {
675     return MapInsertIterator<QHash<K, V>>(container);
676 }
677 
678 // Helper code for container.reserve that makes it possible to effectively disable it for
679 // specific cases
680 
681 // default: do reserve
682 // Template arguments are more specific than the second version below, so this is tried first
683 template<template<typename...> class C, typename... CArgs,
684          typename = decltype(&C<CArgs...>::reserve)>
reserve(C<CArgs...> & c,typename C<CArgs...>::size_type s)685 void reserve(C<CArgs...> &c, typename C<CArgs...>::size_type s)
686 {
687     c.reserve(s);
688 }
689 
690 // containers that don't have reserve()
691 template<typename C>
reserve(C &,typename C::size_type)692 void reserve(C &, typename C::size_type) { }
693 
694 } // anonymous
695 
696 // --------------------------------------------------------------------
697 // Different containers for input and output:
698 // --------------------------------------------------------------------
699 
700 // different container types for input and output, e.g. transforming a QList into a QSet
701 
702 // function without result type deduction:
703 template<typename ResultContainer, // complete result container type
704          typename SC, // input container type
705          typename F> // function type
706 Q_REQUIRED_RESULT
decltype(auto)707 decltype(auto) transform(SC &&container, F function)
708 {
709     ResultContainer result;
710     reserve(result, typename ResultContainer::size_type(container.size()));
711     std::transform(std::begin(container), std::end(container), inserter(result), function);
712     return result;
713 }
714 
715 // function with result type deduction:
716 template<template<typename> class C, // result container type
717          typename SC,                // input container type
718          typename F,                 // function type
719          typename Value,
720          typename Result,
721          typename ResultContainer>
decltype(auto)722 Q_REQUIRED_RESULT decltype(auto) transform(SC &&container, F function)
723 {
724     return transform<ResultContainer>(std::forward<SC>(container), function);
725 }
726 
727 #ifdef Q_CC_CLANG
728 template<template<typename, typename> class C, // result container type
729          typename SC,                          // input container type
730          typename F,                           // function type
731          typename Value,
732          typename Result,
733          typename ResultContainer>
decltype(auto)734 Q_REQUIRED_RESULT decltype(auto) transform(SC &&container, F function)
735 {
736     return transform<ResultContainer>(std::forward<SC>(container), function);
737 }
738 #endif
739 
740 // member function without result type deduction:
741 template<template<typename...> class C, // result container type
742          typename SC, // input container type
743          typename R,
744          typename S>
745 Q_REQUIRED_RESULT
decltype(auto)746 decltype(auto) transform(SC &&container, R (S::*p)() const)
747 {
748     return transform<C>(std::forward<SC>(container), std::mem_fn(p));
749 }
750 
751 // member function with result type deduction:
752 template<typename ResultContainer, // complete result container type
753          typename SC, // input container type
754          typename R,
755          typename S>
756 Q_REQUIRED_RESULT
decltype(auto)757 decltype(auto) transform(SC &&container, R (S::*p)() const)
758 {
759     return transform<ResultContainer>(std::forward<SC>(container), std::mem_fn(p));
760 }
761 
762 // member without result type deduction:
763 template<typename ResultContainer, // complete result container type
764          typename SC, // input container
765          typename R,
766          typename S>
767 Q_REQUIRED_RESULT
decltype(auto)768 decltype(auto) transform(SC &&container, R S::*p)
769 {
770     return transform<ResultContainer>(std::forward<SC>(container), std::mem_fn(p));
771 }
772 
773 // member with result type deduction:
774 template<template<typename...> class C, // result container
775          typename SC, // input container
776          typename R,
777          typename S>
778 Q_REQUIRED_RESULT
decltype(auto)779 decltype(auto) transform(SC &&container, R S::*p)
780 {
781     return transform<C>(std::forward<SC>(container), std::mem_fn(p));
782 }
783 
784 // same container types for input and output, const input
785 
786 // function:
787 template<template<typename...> class C, // container type
788          typename F, // function type
789          typename... CArgs> // Arguments to SC
790 Q_REQUIRED_RESULT
decltype(auto)791 decltype(auto) transform(const C<CArgs...> &container, F function)
792 {
793     return transform<C, const C<CArgs...> &>(container, function);
794 }
795 
796 // member function:
797 template<template<typename...> class C, // container type
798          typename R,
799          typename S,
800          typename... CArgs> // Arguments to SC
801 Q_REQUIRED_RESULT
decltype(auto)802 decltype(auto) transform(const C<CArgs...> &container, R (S::*p)() const)
803 {
804     return transform<C, const C<CArgs...> &>(container, std::mem_fn(p));
805 }
806 
807 // members:
808 template<template<typename...> class C, // container
809          typename R,
810          typename S,
811          typename... CArgs> // Arguments to SC
812 Q_REQUIRED_RESULT
decltype(auto)813 decltype(auto) transform(const C<CArgs...> &container, R S::*p)
814 {
815     return transform<C, const C<CArgs...> &>(container, std::mem_fn(p));
816 }
817 
818 // same container types for input and output, non-const input
819 
820 // function:
821 template<template<typename...> class C, // container type
822          typename F, // function type
823          typename... CArgs> // Arguments to SC
824 Q_REQUIRED_RESULT
decltype(auto)825 decltype(auto) transform(C<CArgs...> &container, F function)
826 {
827     return transform<C, C<CArgs...> &>(container, function);
828 }
829 
830 // member function:
831 template<template<typename...> class C, // container type
832          typename R,
833          typename S,
834          typename... CArgs> // Arguments to SC
835 Q_REQUIRED_RESULT
decltype(auto)836 decltype(auto) transform(C<CArgs...> &container, R (S::*p)() const)
837 {
838     return transform<C, C<CArgs...> &>(container, std::mem_fn(p));
839 }
840 
841 // members:
842 template<template<typename...> class C, // container
843          typename R,
844          typename S,
845          typename... CArgs> // Arguments to SC
846 Q_REQUIRED_RESULT
decltype(auto)847 decltype(auto) transform(C<CArgs...> &container, R S::*p)
848 {
849     return transform<C, C<CArgs...> &>(container, std::mem_fn(p));
850 }
851 
852 // Specialization for QStringList:
853 
854 template<template<typename...> class C = QList, // result container
855          typename F> // Arguments to C
856 Q_REQUIRED_RESULT
decltype(auto)857 decltype(auto) transform(const QStringList &container, F function)
858 {
859     return transform<C, const QList<QString> &>(static_cast<QList<QString>>(container), function);
860 }
861 
862 // member function:
863 template<template<typename...> class C = QList, // result container type
864          typename R,
865          typename S>
866 Q_REQUIRED_RESULT
decltype(auto)867 decltype(auto) transform(const QStringList &container, R (S::*p)() const)
868 {
869     return transform<C, const QList<QString> &>(static_cast<QList<QString>>(container), std::mem_fn(p));
870 }
871 
872 // members:
873 template<template<typename...> class C = QList, // result container
874          typename R,
875          typename S>
876 Q_REQUIRED_RESULT
decltype(auto)877 decltype(auto) transform(const QStringList &container, R S::*p)
878 {
879     return transform<C, const QList<QString> &>(static_cast<QList<QString>>(container), std::mem_fn(p));
880 }
881 
882 //////////////////
883 // filtered
884 /////////////////
885 template<typename C, typename F>
886 Q_REQUIRED_RESULT
filtered(const C & container,F predicate)887 C filtered(const C &container, F predicate)
888 {
889     C out;
890     std::copy_if(std::begin(container), std::end(container),
891                  inserter(out), predicate);
892     return out;
893 }
894 
895 template<typename C, typename R, typename S>
896 Q_REQUIRED_RESULT
filtered(const C & container,R (S::* predicate)()const)897 C filtered(const C &container, R (S::*predicate)() const)
898 {
899     C out;
900     std::copy_if(std::begin(container), std::end(container),
901                  inserter(out), std::mem_fn(predicate));
902     return out;
903 }
904 
905 //////////////////
906 // partition
907 /////////////////
908 
909 // Recommended usage:
910 // C hit;
911 // C miss;
912 // std::tie(hit, miss) = Utils::partition(container, predicate);
913 
914 template<typename C, typename F>
915 Q_REQUIRED_RESULT
partition(const C & container,F predicate)916 std::tuple<C, C> partition(const C &container, F predicate)
917 {
918     C hit;
919     C miss;
920     reserve(hit, container.size());
921     reserve(miss, container.size());
922     auto hitIns = inserter(hit);
923     auto missIns = inserter(miss);
924     for (const auto &i : container) {
925         if (predicate(i))
926             hitIns = i;
927         else
928             missIns = i;
929     }
930     return std::make_tuple(hit, miss);
931 }
932 
933 template<typename C, typename R, typename S>
934 Q_REQUIRED_RESULT
partition(const C & container,R (S::* predicate)()const)935 std::tuple<C, C> partition(const C &container, R (S::*predicate)() const)
936 {
937     return partition(container, std::mem_fn(predicate));
938 }
939 
940 //////////////////
941 // filteredUnique
942 /////////////////
943 
944 template<typename C>
945 Q_REQUIRED_RESULT
filteredUnique(const C & container)946 C filteredUnique(const C &container)
947 {
948     C result;
949     auto ins = inserter(result);
950 
951     QSet<typename C::value_type> seen;
952     int setSize = 0;
953 
954     auto endIt = std::end(container);
955     for (auto it = std::begin(container); it != endIt; ++it) {
956         seen.insert(*it);
957         if (setSize == seen.size()) // unchanged size => was already seen
958             continue;
959         ++setSize;
960         ins = *it;
961     }
962     return result;
963 }
964 
965 //////////////////
966 // qobject_container_cast
967 /////////////////
968 template <class T, template<typename> class Container, typename Base>
qobject_container_cast(const Container<Base> & container)969 Container<T> qobject_container_cast(const Container<Base> &container)
970 {
971     Container<T> result;
972     auto ins = inserter(result);
973     for (Base val : container) {
974         if (T target = qobject_cast<T>(val))
975             ins = target;
976     }
977     return result;
978 }
979 
980 //////////////////
981 // static_container_cast
982 /////////////////
983 template <class T, template<typename> class Container, typename Base>
static_container_cast(const Container<Base> & container)984 Container<T> static_container_cast(const Container<Base> &container)
985 {
986     Container<T> result;
987     reserve(result, container.size());
988     auto ins = inserter(result);
989     for (Base val : container)
990         ins = static_cast<T>(val);
991     return result;
992 }
993 
994 //////////////////
995 // sort
996 /////////////////
997 template <typename Container>
sort(Container & container)998 inline void sort(Container &container)
999 {
1000     std::stable_sort(std::begin(container), std::end(container));
1001 }
1002 
1003 template <typename Container, typename Predicate>
sort(Container & container,Predicate p)1004 inline void sort(Container &container, Predicate p)
1005 {
1006     std::stable_sort(std::begin(container), std::end(container), p);
1007 }
1008 
1009 // pointer to member
1010 template <typename Container, typename R, typename S>
sort(Container & container,R S::* member)1011 inline void sort(Container &container, R S::*member)
1012 {
1013     auto f = std::mem_fn(member);
1014     using const_ref = typename Container::const_reference;
1015     std::stable_sort(std::begin(container), std::end(container),
1016               [&f](const_ref a, const_ref b) {
1017         return f(a) < f(b);
1018     });
1019 }
1020 
1021 // pointer to member function
1022 template <typename Container, typename R, typename S>
sort(Container & container,R (S::* function)()const)1023 inline void sort(Container &container, R (S::*function)() const)
1024 {
1025     auto f = std::mem_fn(function);
1026     using const_ref = typename Container::const_reference;
1027     std::stable_sort(std::begin(container), std::end(container),
1028               [&f](const_ref a, const_ref b) {
1029         return f(a) < f(b);
1030     });
1031 }
1032 
1033 //////////////////
1034 // reverseForeach
1035 /////////////////
1036 template <typename Container, typename Op>
reverseForeach(const Container & c,const Op & operation)1037 inline void reverseForeach(const Container &c, const Op &operation)
1038 {
1039     auto rend = c.rend();
1040     for (auto it = c.rbegin(); it != rend; ++it)
1041         operation(*it);
1042 }
1043 
1044 //////////////////
1045 // toReferences
1046 /////////////////
1047 template <template<typename...> class ResultContainer,
1048           typename SourceContainer>
toReferences(SourceContainer & sources)1049 auto toReferences(SourceContainer &sources)
1050 {
1051     return transform<ResultContainer>(sources, [] (auto &value) { return std::ref(value); });
1052 }
1053 
1054 template <typename SourceContainer>
toReferences(SourceContainer & sources)1055 auto toReferences(SourceContainer &sources)
1056 {
1057     return transform(sources, [] (auto &value) { return std::ref(value); });
1058 }
1059 
1060 //////////////////
1061 // toConstReferences
1062 /////////////////
1063 template <template<typename...> class ResultContainer,
1064           typename SourceContainer>
toConstReferences(const SourceContainer & sources)1065 auto toConstReferences(const SourceContainer &sources)
1066 {
1067     return transform<ResultContainer>(sources, [] (const auto &value) { return std::cref(value); });
1068 }
1069 
1070 template <typename SourceContainer>
toConstReferences(const SourceContainer & sources)1071 auto toConstReferences(const SourceContainer &sources)
1072 {
1073     return transform(sources, [] (const auto &value) { return std::cref(value); });
1074 }
1075 
1076 //////////////////
1077 // take:
1078 /////////////////
1079 
1080 template<class C, typename P>
take(C & container,P predicate)1081 Q_REQUIRED_RESULT optional<typename C::value_type> take(C &container, P predicate)
1082 {
1083     const auto end = std::end(container);
1084 
1085     const auto it = std::find_if(std::begin(container), end, predicate);
1086     if (it == end)
1087         return nullopt;
1088 
1089     optional<typename C::value_type> result = Utils::make_optional(std::move(*it));
1090     container.erase(it);
1091     return result;
1092 }
1093 
1094 // pointer to member
1095 template <typename C, typename R, typename S>
decltype(auto)1096 Q_REQUIRED_RESULT decltype(auto) take(C &container, R S::*member)
1097 {
1098     return take(container, std::mem_fn(member));
1099 }
1100 
1101 // pointer to member function
1102 template <typename C, typename R, typename S>
decltype(auto)1103 Q_REQUIRED_RESULT decltype(auto) take(C &container, R (S::*function)() const)
1104 {
1105     return take(container, std::mem_fn(function));
1106 }
1107 
1108 //////////////////
1109 // setUnionMerge: Works like std::set_union but provides a merge function for items that match
1110 //                !(a > b) && !(b > a) which normally means that there is an "equal" match.
1111 //                It uses iterators to support move_iterators.
1112 /////////////////
1113 
1114 template<class InputIt1,
1115          class InputIt2,
1116          class OutputIt,
1117          class Merge,
1118          class Compare>
setUnionMerge(InputIt1 first1,InputIt1 last1,InputIt2 first2,InputIt2 last2,OutputIt d_first,Merge merge,Compare comp)1119 OutputIt setUnionMerge(InputIt1 first1,
1120                        InputIt1 last1,
1121                        InputIt2 first2,
1122                        InputIt2 last2,
1123                        OutputIt d_first,
1124                        Merge merge,
1125                        Compare comp)
1126 {
1127     for (; first1 != last1; ++d_first) {
1128         if (first2 == last2)
1129             return std::copy(first1, last1, d_first);
1130         if (comp(*first2, *first1)) {
1131             *d_first = *first2++;
1132         } else {
1133             if (comp(*first1, *first2)) {
1134                 *d_first = *first1;
1135             } else {
1136                 *d_first = merge(*first1, *first2);
1137                 ++first2;
1138             }
1139             ++first1;
1140         }
1141     }
1142     return std::copy(first2, last2, d_first);
1143 }
1144 
1145 template<class InputIt1,
1146          class InputIt2,
1147          class OutputIt,
1148          class Merge>
setUnionMerge(InputIt1 first1,InputIt1 last1,InputIt2 first2,InputIt2 last2,OutputIt d_first,Merge merge)1149 OutputIt setUnionMerge(InputIt1 first1,
1150                        InputIt1 last1,
1151                        InputIt2 first2,
1152                        InputIt2 last2,
1153                        OutputIt d_first,
1154                        Merge merge)
1155 {
1156     return setUnionMerge(first1,
1157                          last1,
1158                          first2,
1159                          last2,
1160                          d_first,
1161                          merge,
1162                          std::less<std::decay_t<decltype(*first1)>>{});
1163 }
1164 
1165 template<class OutputContainer,
1166          class InputContainer1,
1167          class InputContainer2,
1168          class Merge,
1169          class Compare>
setUnionMerge(InputContainer1 && input1,InputContainer2 && input2,Merge merge,Compare comp)1170 OutputContainer setUnionMerge(InputContainer1 &&input1,
1171                               InputContainer2 &&input2,
1172                               Merge merge,
1173                               Compare comp)
1174 {
1175     OutputContainer results;
1176     results.reserve(input1.size() + input2.size());
1177 
1178     setUnionMerge(std::make_move_iterator(std::begin(input1)),
1179                   std::make_move_iterator(std::end(input1)),
1180                   std::make_move_iterator(std::begin(input2)),
1181                   std::make_move_iterator(std::end(input2)),
1182                   std::back_inserter(results),
1183                   merge,
1184                   comp);
1185 
1186     return results;
1187 }
1188 
1189 template<class OutputContainer,
1190          class InputContainer1,
1191          class InputContainer2,
1192          class Merge>
setUnionMerge(InputContainer1 && input1,InputContainer2 && input2,Merge merge)1193 OutputContainer setUnionMerge(InputContainer1 &&input1,
1194                               InputContainer2 &&input2,
1195                               Merge merge)
1196 {
1197     return setUnionMerge<OutputContainer>(std::forward<InputContainer1>(input1),
1198                                           std::forward<InputContainer2>(input2),
1199                                           merge,
1200                                           std::less<std::decay_t<decltype(*std::begin(input1))>>{});
1201 }
1202 
1203 template<typename Container>
usize(Container container)1204 std::make_unsigned_t<typename Container::size_type> usize(Container container)
1205 {
1206     return static_cast<std::make_unsigned_t<typename Container::size_type>>(container.size());
1207 }
1208 
1209 template<typename Container>
ssize(Container container)1210 std::make_signed_t<typename Container::size_type> ssize(Container container)
1211 {
1212     return static_cast<std::make_signed_t<typename Container::size_type>>(container.size());
1213 }
1214 
1215 template<typename Compare>
1216 struct CompareIter
1217 {
1218     Compare compare;
1219 
CompareIterCompareIter1220     explicit constexpr CompareIter(Compare compare)
1221         : compare(std::move(compare))
1222     {}
1223 
1224     template<typename Iterator1, typename Iterator2>
operatorCompareIter1225     constexpr bool operator()(Iterator1 it1, Iterator2 it2)
1226     {
1227         return bool(compare(*it1, *it2));
1228     }
1229 };
1230 
1231 template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Compare>
set_union_impl(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2,InputIterator2 last2,OutputIterator result,Compare comp)1232 OutputIterator set_union_impl(InputIterator1 first1,
1233                               InputIterator1 last1,
1234                               InputIterator2 first2,
1235                               InputIterator2 last2,
1236                               OutputIterator result,
1237                               Compare comp)
1238 {
1239     auto compare = CompareIter<Compare>(comp);
1240 
1241     while (first1 != last1 && first2 != last2) {
1242         if (compare(first1, first2)) {
1243             *result = *first1;
1244             ++first1;
1245         } else if (compare(first2, first1)) {
1246             *result = *first2;
1247             ++first2;
1248         } else {
1249             *result = *first1;
1250             ++first1;
1251             ++first2;
1252         }
1253         ++result;
1254     }
1255 
1256     return std::copy(first2, last2, std::copy(first1, last1, result));
1257 }
1258 
1259 template<typename InputIterator1, typename InputIterator2, typename OutputIterator, typename Compare>
set_union(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2,InputIterator2 last2,OutputIterator result,Compare comp)1260 OutputIterator set_union(InputIterator1 first1,
1261                          InputIterator1 last1,
1262                          InputIterator2 first2,
1263                          InputIterator2 last2,
1264                          OutputIterator result,
1265                          Compare comp)
1266 {
1267     return Utils::set_union_impl(first1, last1, first2, last2, result, comp);
1268 }
1269 
1270 template<typename InputIterator1, typename InputIterator2, typename OutputIterator>
set_union(InputIterator1 first1,InputIterator1 last1,InputIterator2 first2,InputIterator2 last2,OutputIterator result)1271 OutputIterator set_union(InputIterator1 first1,
1272                          InputIterator1 last1,
1273                          InputIterator2 first2,
1274                          InputIterator2 last2,
1275                          OutputIterator result)
1276 {
1277     return Utils::set_union_impl(
1278         first1, last1, first2, last2, result, std::less<typename InputIterator1::value_type>{});
1279 }
1280 
1281 // Replacement for deprecated Qt functionality
1282 
1283 template <class T>
toSet(const QList<T> & list)1284 QSet<T> toSet(const QList<T> &list)
1285 {
1286     return QSet<T>(list.begin(), list.end());
1287 }
1288 
1289 #if QT_VERSION < QT_VERSION_CHECK(6, 0, 0)
1290 template<class T>
toSet(const QVector<T> & vec)1291 QSet<T> toSet(const QVector<T> &vec)
1292 {
1293     return QSet<T>(vec.begin(), vec.end());
1294 }
1295 #endif
1296 
1297 template<class T>
toList(const QSet<T> & set)1298 QList<T> toList(const QSet<T> &set)
1299 {
1300     return QList<T>(set.begin(), set.end());
1301 }
1302 
1303 template <class Key, class T>
addToHash(QHash<Key,T> * result,const QHash<Key,T> & additionalContents)1304 void addToHash(QHash<Key, T> *result, const QHash<Key, T> &additionalContents)
1305 {
1306 #if (QT_VERSION < QT_VERSION_CHECK(5, 15, 0))
1307     result->unite(additionalContents);
1308 #else
1309     result->insert(additionalContents);
1310 #endif
1311 }
1312 
1313 } // namespace Utils
1314