Line data    Source code

       1           0 : // Distributed under the MIT License.
       2             : // See LICENSE.txt for details.
       3             : #pragma once
       4             : 
       5             : #include <algorithm>
       6             : #include <functional>
       7             : #include <iterator>
       8             : 
       9             : #include "Utilities/Gsl.hpp"
      10             : 
      11           1 : namespace cpp20 {
      12             : /*!
      13             :  * \ingroup UtilitiesGroup
      14             :  * Reimplementation of std::swap that is constexpr;
      15             :  * taken from the LLVM source at
      16             :  * https://github.com/llvm-mirror/libcxx/blob/master/include/type_traits
      17             :  */
      18             : template <class T>
      19           1 : constexpr void swap(T& a, T& b) {
      20             :   T c(std::move(a));
      21             :   a = std::move(b);
      22             :   b = std::move(c);
      23             : }
      24             : 
      25             : /*!
      26             :  * \ingroup UtilitiesGroup
      27             :  * Reimplementation of std::iter_swap that is constexpr;
      28             :  * taken from the LLVM source at
      29             :  * https://github.com/llvm-mirror/libcxx/blob/master/include/type_traits
      30             :  */
      31             : template <class ForwardIt1, class ForwardIt2>
      32           1 : constexpr void iter_swap(ForwardIt1 a, ForwardIt2 b) {
      33             :   swap(*a, *b);
      34             : }
      35             : 
      36             : namespace detail {
      37             : /*!
      38             :  * \ingroup UtilitiesGroup
      39             :  * Reimplementation of std::reverse that is constexpr, for bidirectional
      40             :  * iterators; taken from the LLVM source at
      41             :  * https://github.com/llvm-mirror/libcxx/blob/master/include/algorithm
      42             :  */
      43             : template <class BidirIt>
      44             : constexpr void reverse(BidirIt first, BidirIt last,
      45             :                        std::bidirectional_iterator_tag /* unused */) {
      46             :   while (first != last) {
      47             :     if (first == --last) {
      48             :       break;
      49             :     }
      50             :     cpp20::iter_swap(first, last);
      51             :     ++first;
      52             :   }
      53             : }
      54             : 
      55             : /*!
      56             :  * \ingroup UtilitiesGroup
      57             :  * Reimplementation of std::reverse that is constexpr, for random access
      58             :  * iterators; taken from the LLVM source at
      59             :  * https://github.com/llvm-mirror/libcxx/blob/master/include/algorithm
      60             :  */
      61             : template <class RandomAccessIterator>
      62             : constexpr void reverse(RandomAccessIterator first, RandomAccessIterator last,
      63             :                        std::random_access_iterator_tag /* unused */) {
      64             :   if (first != last) {
      65             :     for (; first < --last; ++first) {
      66             :       cpp20::iter_swap(first, last);
      67             :     }
      68             :   }
      69             : }
      70             : }  // namespace detail
      71             : 
      72             : /*!
      73             :  * \ingroup UtilitiesGroup
      74             :  * Reimplementation of std::reverse that is constexpr;
      75             :  * taken from the LLVM source at
      76             :  * https://github.com/llvm-mirror/libcxx/blob/master/include/algorithm
      77             :  */
      78             : template <class BidirectionalIterator>
      79           1 : constexpr void reverse(BidirectionalIterator first,
      80             :                        BidirectionalIterator last) {
      81             :   cpp20::detail::reverse(first, last,
      82             :                          typename std::iterator_traits<
      83             :                              BidirectionalIterator>::iterator_category());
      84             : }
      85             : 
      86             : /*!
      87             :  * \ingroup UtilitiesGroup
      88             :  * Reimplementation of std::next_permutation that is constexpr,
      89             :  * for a generic comparator; taken from the LLVM source at
      90             :  * https://github.com/llvm-mirror/libcxx/blob/master/include/algorithm
      91             :  */
      92             : template <class Compare, class BidirectionalIterator>
      93           1 : constexpr bool next_permutation(BidirectionalIterator first,
      94             :                                 BidirectionalIterator last, Compare comp) {
      95             :   BidirectionalIterator i = last;
      96             :   if (first == last || first == --i) {
      97             :     return false;
      98             :   }
      99             :   while (true) {
     100             :     BidirectionalIterator ip1 = i;
     101             :     if (comp(*--i, *ip1)) {
     102             :       BidirectionalIterator j = last;
     103             :       while (!comp(*i, *--j)) {
     104             :       }
     105             :       cpp20::swap(*i, *j);
     106             :       cpp20::reverse(ip1, last);
     107             :       return true;
     108             :     }
     109             :     if (i == first) {
     110             :       cpp20::reverse(first, last);
     111             :       return false;
     112             :     }
     113             :   }
     114             : }
     115             : 
     116             : /*!
     117             :  * \ingroup UtilitiesGroup
     118             :  * Reimplementation of std::next_permutation that is constexpr,
     119             :  * with less as the comparator; taken from the LLVM source at
     120             :  * https://github.com/llvm-mirror/libcxx/blob/master/include/algorithm
     121             :  */
     122             : template <class BidirectionalIterator>
     123           1 : constexpr bool next_permutation(BidirectionalIterator first,
     124             :                                 BidirectionalIterator last) {
     125             :   return cpp20::next_permutation(
     126             :       first, last,
     127             :       std::less<
     128             :           typename std::iterator_traits<BidirectionalIterator>::value_type>());
     129             : }
     130             : 
     131             : /*!
     132             :  * \ingroup UtilitiesGroup
     133             :  * Reimplementation of std::find that is constexpr
     134             :  */
     135             : template <class InputIt, class T>
     136           1 : constexpr InputIt find(InputIt first, InputIt last, const T& value) {
     137             :   for (; first != last; ++first) {
     138             :     if (*first == value) {
     139             :       return first;
     140             :     }
     141             :   }
     142             :   return last;
     143             : }
     144             : 
     145             : /*!
     146             :  * \ingroup UtilitiesGroup
     147             :  * Reimplementation of std::find_if that is constexpr
     148             :  */
     149             : template <class InputIt, class UnaryPredicate>
     150           1 : constexpr InputIt find_if(InputIt first, InputIt last, UnaryPredicate p) {
     151             :   for (; first != last; ++first) {
     152             :     if (p(*first)) {
     153             :       return first;
     154             :     }
     155             :   }
     156             :   return last;
     157             : }
     158             : 
     159             : /*!
     160             :  * \ingroup UtilitiesGroup
     161             :  * Reimplementation of std::find_if_not that is constexpr
     162             :  */
     163             : template <class InputIt, class UnaryPredicate>
     164           1 : constexpr InputIt find_if_not(InputIt first, InputIt last, UnaryPredicate q) {
     165             :   for (; first != last; ++first) {
     166             :     if (!q(*first)) {
     167             :       return first;
     168             :     }
     169             :   }
     170             :   return last;
     171             : }
     172             : }  // namespace cpp20
     173             : 
     174             : /*!
     175             :  * \ingroup UtilitiesGroup
     176             :  * \brief Utility functions wrapping STL algorithms and additional algorithms.
     177             :  */
     178           1 : namespace alg {
     179             : /// Convenience wrapper around std::all_of
     180             : template <class Container, class UnaryPredicate>
     181           1 : decltype(auto) all_of(const Container& c, UnaryPredicate&& unary_predicate) {
     182             :   using std::begin;
     183             :   using std::end;
     184             :   return std::all_of(begin(c), end(c),
     185             :                      std::forward<UnaryPredicate>(unary_predicate));
     186             : }
     187             : 
     188             : /// Convenience wrapper around std::any_of
     189             : template <class Container, class UnaryPredicate>
     190           1 : decltype(auto) any_of(const Container& c, UnaryPredicate&& unary_predicate) {
     191             :   using std::begin;
     192             :   using std::end;
     193             :   return std::any_of(begin(c), end(c),
     194             :                      std::forward<UnaryPredicate>(unary_predicate));
     195             : }
     196             : 
     197             : /// Convenience wrapper around std::none_of
     198             : template <class Container, class UnaryPredicate>
     199           1 : decltype(auto) none_of(const Container& c, UnaryPredicate&& unary_predicate) {
     200             :   using std::begin;
     201             :   using std::end;
     202             :   return std::none_of(begin(c), end(c),
     203             :                       std::forward<UnaryPredicate>(unary_predicate));
     204             : }
     205             : 
     206             : /// Convenience wrapper around std::count
     207             : template <class Container, class T>
     208           1 : decltype(auto) count(const Container& c, const T& value) {
     209             :   using std::begin;
     210             :   using std::end;
     211             :   return std::count(begin(c), end(c), value);
     212             : }
     213             : 
     214             : /// Convenience wrapper around std::count_if
     215             : template <class Container, class UnaryPredicate>
     216           1 : decltype(auto) count_if(const Container& c, UnaryPredicate&& unary_predicate) {
     217             :   using std::begin;
     218             :   using std::end;
     219             :   return std::count_if(begin(c), end(c),
     220             :                        std::forward<UnaryPredicate>(unary_predicate));
     221             : }
     222             : 
     223             : /// Convenience wrapper around constexpr reimplementation of std::find
     224             : template <class Container, class T>
     225           1 : constexpr decltype(auto) find(Container&& c, const T& value) {
     226             :   using std::begin;
     227             :   using std::end;
     228             :   return cpp20::find(begin(std::forward<Container>(c)),
     229             :                      end(std::forward<Container>(c)), value);
     230             : }
     231             : 
     232             : /// Convenience wrapper around constexpr reimplementation of std::find_if
     233             : template <class Container, class UnaryPredicate>
     234           1 : constexpr decltype(auto) find_if(Container&& c,
     235             :                                  UnaryPredicate&& unary_predicate) {
     236             :   using std::begin;
     237             :   using std::end;
     238             :   return cpp20::find_if(begin(std::forward<Container>(c)),
     239             :                         end(std::forward<Container>(c)),
     240             :                         std::forward<UnaryPredicate>(unary_predicate));
     241             : }
     242             : 
     243             : /// Convenience wrapper around constexpr reimplementation of std::find_if_not
     244             : template <class Container, class UnaryPredicate>
     245           1 : constexpr decltype(auto) find_if_not(Container&& c,
     246             :                                      UnaryPredicate&& unary_predicate) {
     247             :   using std::begin;
     248             :   using std::end;
     249             :   return cpp20::find_if_not(begin(std::forward<Container>(c)),
     250             :                             end(std::forward<Container>(c)),
     251             :                             std::forward<UnaryPredicate>(unary_predicate));
     252             : }
     253             : 
     254             : /// Convenience wrapper around constexpr reimplementation of std::find, returns
     255             : /// `true` if `value` is in `c`.
     256             : template <class Container, class T>
     257           1 : constexpr bool found(const Container& c, const T& value) {
     258             :   using std::begin;
     259             :   using std::end;
     260             :   return cpp20::find(begin(c), end(c), value) != end(c);
     261             : }
     262             : 
     263             : /// Convenience wrapper around constexpr reimplementation of std::find_if,
     264             : /// returns `true` if the result of `cpp20::find_if` is not equal to `end(c)`.
     265             : template <class Container, class UnaryPredicate>
     266           1 : constexpr bool found_if(const Container& c, UnaryPredicate&& unary_predicate) {
     267             :   using std::begin;
     268             :   using std::end;
     269             :   return cpp20::find_if(begin(c), end(c),
     270             :                         std::forward<UnaryPredicate>(unary_predicate)) !=
     271             :          end(c);
     272             : }
     273             : 
     274             : /// Convenience wrapper around constexpr reimplementation of std::find_if_not,
     275             : /// returns `true` if the result of `cpp20::find_if_not` is not equal to
     276             : /// `end(c)`.
     277             : template <class Container, class UnaryPredicate>
     278           1 : constexpr bool found_if_not(const Container& c,
     279             :                             UnaryPredicate&& unary_predicate) {
     280             :   using std::begin;
     281             :   using std::end;
     282             :   return cpp20::find_if_not(begin(c), end(c),
     283             :                             std::forward<UnaryPredicate>(unary_predicate)) !=
     284             :          end(c);
     285             : }
     286             : 
     287             : /// @{
     288             : /// Convenience wrapper around std::for_each, returns the result of
     289             : /// `std::for_each(begin(c), end(c), f)`.
     290             : template <class Container, class UnaryFunction>
     291           1 : decltype(auto) for_each(const Container& c, UnaryFunction&& f) {
     292             :   using std::begin;
     293             :   using std::end;
     294             :   return std::for_each(begin(c), end(c), std::forward<UnaryFunction>(f));
     295             : }
     296             : 
     297             : template <class Container, class UnaryFunction>
     298           1 : decltype(auto) for_each(Container& c, UnaryFunction&& f) {
     299             :   using std::begin;
     300             :   using std::end;
     301             :   return std::for_each(begin(c), end(c), std::forward<UnaryFunction>(f));
     302             : }
     303             : /// @}
     304             : 
     305             : /// Convenience wrapper around std::equal, assumes containers `lhs` has at least
     306             : /// as many elements as `rhs`.
     307             : template <class Container, class Container2>
     308           1 : decltype(auto) equal(const Container& lhs, const Container2& rhs) {
     309             :   using std::begin;
     310             :   using std::end;
     311             :   return std::equal(begin(lhs), end(lhs), begin(rhs));
     312             : }
     313             : 
     314             : /// Convenience wrapper around std::equal, assumes containers `lhs` has at least
     315             : /// as many elements as `rhs`.
     316             : template <class Container, class Container2, class BinaryPredicate>
     317           1 : decltype(auto) equal(const Container& lhs, const Container2& rhs,
     318             :                      BinaryPredicate&& p) {
     319             :   using std::begin;
     320             :   using std::end;
     321             :   return std::equal(begin(lhs), end(lhs), begin(rhs),
     322             :                     std::forward<BinaryPredicate>(p));
     323             : }
     324             : 
     325             : /// Convenience wrapper around std::max_element
     326             : template <class Container>
     327           1 : constexpr decltype(auto) max_element(const Container& c) {
     328             :   using std::begin;
     329             :   using std::end;
     330             :   return std::max_element(begin(c), end(c));
     331             : }
     332             : 
     333             : /// Convenience wrapper around std::max_element
     334             : template <class Container, class Compare>
     335           1 : constexpr decltype(auto) max_element(const Container& c, Compare&& comp) {
     336             :   using std::begin;
     337             :   using std::end;
     338             :   return std::max_element(begin(c), end(c), std::forward<Compare>(comp));
     339             : }
     340             : 
     341             : /// Convenience wrapper around std::min_element
     342             : template <class Container>
     343           1 : constexpr decltype(auto) min_element(const Container& c) {
     344             :   using std::begin;
     345             :   using std::end;
     346             :   return std::min_element(begin(c), end(c));
     347             : }
     348             : 
     349             : /// Convenience wrapper around std::min_element
     350             : template <class Container, class Compare>
     351           1 : constexpr decltype(auto) min_element(const Container& c, Compare&& comp) {
     352             :   using std::begin;
     353             :   using std::end;
     354             :   return std::min_element(begin(c), end(c), std::forward<Compare>(comp));
     355             : }
     356             : 
     357             : /// Convenience wrapper around std::minmax_element
     358             : template <class Container>
     359           1 : constexpr decltype(auto) minmax_element(const Container& c) {
     360             :   using std::begin;
     361             :   using std::end;
     362             :   return std::minmax_element(begin(c), end(c));
     363             : }
     364             : 
     365             : /// Convenience wrapper around std::minmax_element
     366             : template <class Container, class Compare>
     367           1 : constexpr decltype(auto) minmax_element(const Container& c, Compare&& comp) {
     368             :   using std::begin;
     369             :   using std::end;
     370             :   return std::minmax_element(begin(c), end(c), std::forward<Compare>(comp));
     371             : }
     372             : 
     373             : /// Convenience wrapper around std::remove
     374             : template <class Container, class T>
     375           1 : decltype(auto) remove(Container& c, const T& value) {
     376             :   using std::begin;
     377             :   using std::end;
     378             :   return std::remove(begin(c), end(c), value);
     379             : }
     380             : 
     381             : /// Convenience wrapper around std::remove_if
     382             : template <class Container, class UnaryPredicate>
     383           1 : decltype(auto) remove_if(Container& c, UnaryPredicate&& unary_predicate) {
     384             :   using std::begin;
     385             :   using std::end;
     386             :   return std::remove_if(begin(c), end(c),
     387             :                         std::forward<UnaryPredicate>(unary_predicate));
     388             : }
     389             : 
     390             : /// Convience wrapper around std::sample
     391             : template <class Container, class OutputIt, class Distance, class URBG>
     392           1 : decltype(auto) sample(Container& c, OutputIt out, Distance n, URBG&& g) {
     393             :   using std::begin;
     394             :   using std::end;
     395             :   return std::sample(begin(c), end(c), out, n, g);
     396             : }
     397             : 
     398             : /// Convenience wrapper around std::sort
     399             : template <class Container>
     400           1 : decltype(auto) sort(Container& c) {
     401             :   using std::begin;
     402             :   using std::end;
     403             :   return std::sort(begin(c), end(c));
     404             : }
     405             : 
     406             : /// Convenience wrapper around std::sort
     407             : template <class Container, class Compare>
     408           1 : decltype(auto) sort(Container& c, Compare&& comp) {
     409             :   using std::begin;
     410             :   using std::end;
     411             :   return std::sort(begin(c), end(c), std::forward<Compare>(comp));
     412             : }
     413             : 
     414             : /// Convenience wrapper around std::transform
     415             : template <class Container, class OutputIt, class UnaryOp>
     416           1 : decltype(auto) transform(const Container& c, OutputIt output_first,
     417             :                          UnaryOp&& unary_op) {
     418             :   using std::begin;
     419             :   using std::end;
     420             :   return std::transform(begin(c), end(c), output_first,
     421             :                         std::forward<UnaryOp>(unary_op));
     422             : }
     423             : 
     424             : /// Convenience wrapper around std::transform
     425             : template <class Container1, class Container2, class OutputIt, class BinaryOp>
     426           1 : decltype(auto) transform(const Container1& c1, const Container2& c2,
     427             :                          OutputIt output_first, BinaryOp&& binary_op) {
     428             :   using std::begin;
     429             :   using std::end;
     430             :   return std::transform(begin(c1), end(c1), begin(c2), output_first,
     431             :                         std::forward<BinaryOp>(binary_op));
     432             : }
     433             : }  // namespace alg