algorithm.h 14.7 KB
Newer Older
1 2
/****************************************************************************
**
3 4
** Copyright (C) 2016 The Qt Company Ltd.
** Contact: https://www.qt.io/licensing/
5 6 7 8 9 10 11
**
** This file is part of Qt Creator.
**
** Commercial License Usage
** Licensees holding valid commercial Qt licenses may use this file in
** accordance with the commercial license agreement provided with the
** Software or, alternatively, in accordance with the terms contained in
12 13 14
** a written agreement between you and The Qt Company. For licensing terms
** and conditions see https://www.qt.io/terms-conditions. For further
** information use the contact form at https://www.qt.io/contact-us.
15
**
16 17 18 19 20 21 22
** GNU General Public License Usage
** Alternatively, this file may be used under the terms of the GNU
** General Public License version 3 as published by the Free Software
** Foundation with exceptions as appearing in the file LICENSE.GPL3-EXCEPT
** included in the packaging of this file. Please review the following
** information to ensure the GNU General Public License requirements will
** be met: https://www.gnu.org/licenses/gpl-3.0.html.
23 24 25
**
****************************************************************************/

hjk's avatar
hjk committed
26
#pragma once
27

28 29
#include "predicates.h"

Christian Kandeler's avatar
Christian Kandeler committed
30 31
#include <qcompilerdetection.h> // for Q_REQUIRED_RESULT

32
#include <algorithm>
33 34
#include <tuple>

35
#include <QObject>
36
#include <QStringList>
37 38 39

namespace Utils
{
40 41 42
//////////////////
// anyOf
/////////////////
43 44 45 46 47
template<typename T, typename F>
bool anyOf(const T &container, F predicate)
{
    return std::any_of(std::begin(container), std::end(container), predicate);
}
48 49 50 51 52

// anyOf taking a member function pointer
template<typename T, typename R, typename S>
bool anyOf(const T &container, R (S::*predicate)() const)
{
53
    return std::any_of(std::begin(container), std::end(container), std::mem_fn(predicate));
54
}
55

56 57 58
// anyOf taking a member pointer
template<typename T, typename R, typename S>
bool anyOf(const T &container, R S::*member)
59
{
60
    return std::any_of(std::begin(container), std::end(container), std::mem_fn(member));
61 62
}

63 64 65 66

//////////////////
// count
/////////////////
67 68 69
template<typename T, typename F>
int count(const T &container, F predicate)
{
70
    return std::count_if(std::begin(container), std::end(container), predicate);
71 72
}

73 74 75
//////////////////
// allOf
/////////////////
76 77 78
template<typename T, typename F>
bool allOf(const T &container, F predicate)
{
79
    return std::all_of(std::begin(container), std::end(container), predicate);
80 81
}

82 83 84
//////////////////
// erase
/////////////////
85
template<typename T, typename F>
86
void erase(T &container, F predicate)
87
{
88 89
    container.erase(std::remove_if(std::begin(container), std::end(container), predicate),
                    std::end(container));
90 91
}

92

93 94 95
//////////////////
// contains
/////////////////
96 97 98
template<typename T, typename F>
bool contains(const T &container, F function)
{
Tobias Hunger's avatar
Tobias Hunger committed
99 100
    return anyOf(container, function);
}
101

Tobias Hunger's avatar
Tobias Hunger committed
102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118
// Contains for normal pointers in std::vector<std::unique_ptr>
template<template<typename, typename...> class C, typename T, typename... Args>
bool contains(const C<T, Args...> &container, typename T::element_type *other)
{
    return anyOf(container, [other](const typename C<T, Args...>::value_type &value) { return value.get() == other; });
}

template<typename T, typename R, typename S>
bool contains(const T &container, R (S::*function)() const)
{
    return anyOf(container, function);
}

template<template<typename, typename...> class C, typename... Args, typename T, typename R, typename S>
bool contains(const C<T, Args...> &container, R (S::*function)() const)
{
    return anyOf(container, function);
119 120
}

121 122 123
//////////////////
// findOr
/////////////////
124 125 126
template<typename T, typename F>
typename T::value_type findOr(const T &container, typename T::value_type other, F function)
{
127 128
    typename T::const_iterator begin = std::begin(container);
    typename T::const_iterator end = std::end(container);
129 130 131 132 133 134 135

    typename T::const_iterator it = std::find_if(begin, end, function);
    if (it == end)
        return other;
    return *it;
}

136 137 138 139 140 141 142 143 144 145 146 147 148 149
// container of unique_ptr (with element_type and get()),
// and with two template arguments like std::vector
template<template<typename, typename> class C, typename AllocC, typename T, typename F>
typename T::element_type *findOr(const C<T, AllocC> &container, typename T::element_type *other, F function)
{
    typename C<T, AllocC>::const_iterator begin = std::begin(container);
    typename C<T, AllocC>::const_iterator end = std::end(container);

    typename C<T, AllocC>::const_iterator it = std::find_if(begin, end, function);
    if (it == end)
        return other;
    return it->get();
}

150 151 152 153 154 155
template<typename T, typename R, typename S>
typename T::value_type findOr(const T &container, typename T::value_type other, R (S::*function)() const)
{
    return findOr(container, other, std::mem_fn(function));
}

156 157 158 159 160 161 162
// container of unique_ptr (with element_type and get()),
// and with two template arguments like std::vector
template<template<typename, typename> class C, typename AllocC, typename T, typename R, typename S>
typename T::element_type *findOr(const C<T, AllocC> &container, typename T::element_type *other, R (S::*function)() const)
{
    return findOr(container, other, std::mem_fn(function));
}
163

164
template<typename T, typename F>
165
typename T::value_type findOrDefault(const T &container, F function)
166
{
167 168
    return findOr(container, typename T::value_type(), function);
}
169

170 171 172 173 174 175
template<typename T, typename R, typename S>
typename T::value_type findOrDefault(const T &container, R (S::*function)() const)
{
    return findOr(container, typename T::value_type(), function);
}

176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192
// container of unique_ptr (with element_type and get()),
// and with two template arguments like std::vector
template<template<typename, typename> class C, typename AllocC, typename T, typename F>
typename T::element_type *findOrDefault(const C<T, AllocC> &container, F function)
{
    return findOr(container, nullptr, function);
}

// container of unique_ptr (with element_type and get()),
// and with two template arguments like std::vector
template<template<typename, typename> class C, typename AllocC, typename T, typename R, typename S>
typename T::element_type *findOrDefault(const C<T, AllocC> &container, R (S::*function)() const)
{
    return findOr(container, nullptr, std::mem_fn(function));
}


193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208
//////////////////
// index of:
//////////////////

template<typename C, typename F>
Q_REQUIRED_RESULT
int indexOf(const C& container, F function)
{
    typename C::const_iterator begin = std::begin(container);
    typename C::const_iterator end = std::end(container);

    typename C::const_iterator it = std::find_if(begin, end, function);
    return it == end ? -1 : std::distance(begin, it);
}


209 210 211 212 213 214 215
//////////////////
// max element
//////////////////

template<typename T>
typename T::value_type maxElementOr(const T &container, typename T::value_type other)
{
216 217
    typename T::const_iterator begin = std::begin(container);
    typename T::const_iterator end = std::end(container);
218 219 220 221 222 223

    typename T::const_iterator it = std::max_element(begin, end);
    if (it == end)
        return other;
    return *it;
}
224

225 226 227 228
//////////////////
// transform
/////////////////

229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275
namespace {
/////////////////
// helper code for transform to use back_inserter and thus push_back for everything
// and insert for QSet<>
//

// QSetInsertIterator, straight from the standard for insert_iterator
// just without the additional parameter to insert
template <class Container>
  class QSetInsertIterator :
    public std::iterator<std::output_iterator_tag,void,void,void,void>
{
protected:
  Container *container;

public:
  typedef Container container_type;
  explicit QSetInsertIterator (Container &x)
    : container(&x) {}
  QSetInsertIterator<Container> &operator=(const typename Container::value_type &value)
    { container->insert(value); return *this; }
  QSetInsertIterator<Container> &operator= (typename Container::value_type &&value)
    { container->insert(std::move(value)); return *this; }
  QSetInsertIterator<Container >&operator*()
    { return *this; }
  QSetInsertIterator<Container> &operator++()
    { return *this; }
  QSetInsertIterator<Container> operator++(int)
    { return *this; }
};

// inserter helper function, returns a std::back_inserter for most containers
// and is overloaded for QSet<> to return a QSetInsertIterator
template<typename C>
inline std::back_insert_iterator<C>
inserter(C &container)
{
    return std::back_inserter(container);
}

template<typename X>
inline QSetInsertIterator<QSet<X>>
inserter(QSet<X> &container)
{
    return QSetInsertIterator<QSet<X>>(container);
}

276
// Result type of transform operation
277

278 279
template<template<typename> class Container, template<typename> class InputContainer, typename IT, typename Function>
using ResultContainer = Container<std::decay_t<std::result_of_t<Function(IT)>>>;
280

281
} // anonymous
282

283 284 285 286 287 288 289
// different container types for input and output, e.g. transforming a QList into a QSet
template<template<typename> class C, // result container type
         template<typename> class SC, // input container type
         typename T, // input value type
         typename F> // function type
Q_REQUIRED_RESULT
decltype(auto) transform(const SC<T> &container, F function)
290
{
291 292 293 294 295 296
    ResultContainer<C, SC, T, F> result;
    result.reserve(container.size());
    std::transform(container.begin(), container.end(),
                   inserter(result),
                   function);
    return result;
297
}
298

299 300 301 302 303 304 305 306 307 308 309 310
// different container types for input and output, e.g. transforming a QList into a QSet
// for member function pointers
template<template<typename> class C, // result container type
         template<typename> class SC, // input container type
         typename T, // input value type
         typename R,
         typename S>
Q_REQUIRED_RESULT
decltype(auto) transform(const SC<T> &container, R (S::*p)() const)
{
    return transform<C, SC, T>(container, std::mem_fn(p));
}
311

312 313
// same container type for input and output, e.g. transforming a QList<QString> into QList<int>
// or QStringList -> QList<>
314 315
template<template<typename> class C, // container
         typename T, // container value type
316
         typename F>
317
Q_REQUIRED_RESULT
318
decltype(auto) transform(const C<T> &container, F function)
319
{
320
    return transform<C, C, T>(container, function);
321 322
}

323
// same container type for member function pointer
324 325 326 327
template<template<typename> class C, // container
         typename T, // container value type
         typename R,
         typename S>
328
Q_REQUIRED_RESULT
329
decltype(auto) transform(const C<T> &container, R (S::*p)() const)
330
{
331
    return transform<C, C, T>(container, std::mem_fn(p));
332 333
}

334 335 336
// same container type for members
template<template<typename> class C, // container
         typename T, // container value type
337 338 339
         typename R,
         typename S>
Q_REQUIRED_RESULT
340
decltype(auto) transform(const C<T> &container, R S::*member)
341
{
342
    return transform<C, C, T>(container, std::mem_fn(member));
343 344
}

345
// QStringList different containers
346
template<template<typename> class C, // result container type
347
         typename F>
348
Q_REQUIRED_RESULT
349
decltype(auto) transform(const QStringList &container, F function)
350
{
351
    return transform<C, QList, QString>(container, function);
352 353
}

354 355
// QStringList -> QList
template<typename F>
356
Q_REQUIRED_RESULT
357
decltype(auto) transform(const QStringList &container, F function)
358
{
359
    return Utils::transform<QList, QList, QString>(container, function);
360 361
}

362 363 364 365
//////////////////
// filtered
/////////////////
template<typename C, typename F>
366
Q_REQUIRED_RESULT
367 368
C filtered(const C &container, F predicate)
{
Tobias Hunger's avatar
Tobias Hunger committed
369
    C out;
370
    std::copy_if(std::begin(container), std::end(container),
Tobias Hunger's avatar
Tobias Hunger committed
371 372
                 inserter(out), predicate);
    return out;
373 374
}

375 376 377 378
template<typename C, typename R, typename S>
Q_REQUIRED_RESULT
C filtered(const C &container, R (S::*predicate)() const)
{
Tobias Hunger's avatar
Tobias Hunger committed
379
    C out;
380
    std::copy_if(std::begin(container), std::end(container),
Tobias Hunger's avatar
Tobias Hunger committed
381 382
                 inserter(out), std::mem_fn(predicate));
    return out;
383 384
}

385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401
//////////////////
// partition
/////////////////

// Recommended usage:
// C hit;
// C miss;
// std::tie(hit, miss) = Utils::partition(container, predicate);

template<typename C, typename F>
Q_REQUIRED_RESULT
std::tuple<C, C> partition(const C &container, F predicate)
{
    C hit;
    C miss;
    auto hitIns = inserter(hit);
    auto missIns = inserter(miss);
402
    for (auto i : container) {
403 404 405 406 407 408 409 410 411 412 413 414 415 416 417
        if (predicate(i))
            hitIns = i;
        else
            missIns = i;
    }
    return std::make_tuple(hit, miss);
}

template<typename C, typename R, typename S>
Q_REQUIRED_RESULT
std::tuple<C, C> partition(const C &container, R (S::*predicate)() const)
{
    return partition(container, std::mem_fn(predicate));
}

Tobias Hunger's avatar
Tobias Hunger committed
418 419 420 421 422 423 424 425 426 427 428 429 430 431
//////////////////
// filteredUnique
/////////////////

template<typename C>
Q_REQUIRED_RESULT
C filteredUnique(const C &container)
{
    C result;
    auto ins = inserter(result);

    QSet<typename C::value_type> seen;
    int setSize = 0;

432 433
    auto endIt = std::end(container);
    for (auto it = std::begin(container); it != endIt; ++it) {
Tobias Hunger's avatar
Tobias Hunger committed
434 435 436 437 438 439 440 441 442
        seen.insert(*it);
        if (setSize == seen.size()) // unchanged size => was already seen
            continue;
        ++setSize;
        ins = *it;
    }
    return result;
}

443 444 445 446 447 448 449 450 451 452 453 454 455 456 457
//////////////////
// qobject_container_cast
/////////////////
template <class T, template<typename> class Container, typename Base>
Container<T> qobject_container_cast(const Container<Base> &container)
{
    Container<T> result;
    auto ins = inserter(result);
    for (Base val : container) {
        if (T target = qobject_cast<T>(val))
            ins = target;
    }
    return result;
}

458 459 460
//////////////////
// sort
/////////////////
461
template <typename Container>
462
inline void sort(Container &container)
463
{
464
    std::sort(std::begin(container), std::end(container));
465 466 467
}

template <typename Container, typename Predicate>
468
inline void sort(Container &container, Predicate p)
469
{
470
    std::sort(std::begin(container), std::end(container), p);
471 472
}

473 474
// pointer to member
template <typename Container, typename R, typename S>
475
inline void sort(Container &container, R S::*member)
476
{
477 478
    auto f = std::mem_fn(member);
    using const_ref = typename Container::const_reference;
479 480
    std::sort(std::begin(container), std::end(container),
              [&f](const_ref a, const_ref b) {
481
        return f(a) < f(b);
482 483 484 485 486
    });
}

// pointer to member function
template <typename Container, typename R, typename S>
487
inline void sort(Container &container, R (S::*function)() const)
488
{
489 490
    auto f = std::mem_fn(function);
    using const_ref = typename Container::const_reference;
491 492
    std::sort(std::begin(container), std::end(container),
              [&f](const_ref a, const_ref b) {
493
        return f(a) < f(b);
494 495 496
    });
}

Eike Ziller's avatar
Eike Ziller committed
497 498 499 500 501 502 503 504 505 506 507
//////////////////
// reverseForeach
/////////////////
template <typename Container, typename Op>
inline void reverseForeach(const Container &c, const Op &operation)
{
    auto rend = c.rend();
    for (auto it = c.rbegin(); it != rend; ++it)
        operation(*it);
}

508
}