libstdc++-v3/include/experimental/functional

   1 // <experimental/functional> -*- C++ -*-
   2
   3 // Copyright (C) 2014-2017 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 3, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /** @file experimental/functional
  26  *  This is a TS C++ Library header.
  27  */
  28
  29 #ifndef _GLIBCXX_EXPERIMENTAL_FUNCTIONAL
  30 #define _GLIBCXX_EXPERIMENTAL_FUNCTIONAL 1
  31
  32 #pragma GCC system_header
  33
  34 #if __cplusplus <= 201103L
  35 # include <bits/c++14_warning.h>
  36 #else
  37
  38 #include <functional>
  39 #include <tuple>
  40 #include <iterator>
  41 #include <unordered_map>
  42 #include <vector>
  43 #include <array>
  44 #include <bits/stl_algo.h>
  45 #ifdef _GLIBCXX_PARALLEL
  46 # include <parallel/algorithm> // For std::__parallel::search
  47 #endif
  48 #include <experimental/bits/lfts_config.h>
  49
  50 namespace std _GLIBCXX_VISIBILITY(default)
  51 {
  52 _GLIBCXX_BEGIN_NAMESPACE_VERSION
  53
  54 namespace experimental
  55 {
  56 inline namespace fundamentals_v1
  57 {
  58   // See C++14 §20.9.9, Function object binders
  59
  60   /// Variable template for std::is_bind_expression
  61   template<typename _Tp>
  62     constexpr bool is_bind_expression_v = std::is_bind_expression<_Tp>::value;
  63
  64   /// Variable template for std::is_placeholder
  65   template<typename _Tp>
  66     constexpr int is_placeholder_v = std::is_placeholder<_Tp>::value;
  67
  68 #define __cpp_lib_experimental_boyer_moore_searching 201411
  69
  70   // Searchers
  71
  72   template<typename _ForwardIterator1, typename _BinaryPredicate = equal_to<>>
  73     class default_searcher
  74     {
  75     public:
  76       default_searcher(_ForwardIterator1 __pat_first,
  77                        _ForwardIterator1 __pat_last,
  78                        _BinaryPredicate __pred = _BinaryPredicate())
  79       : _M_m(__pat_first, __pat_last, std::move(__pred))
  80       { }
  81
  82       template<typename _ForwardIterator2>
  83         _ForwardIterator2
  84         operator()(_ForwardIterator2 __first, _ForwardIterator2 __last) const
  85         {
  86           return std::search(__first, __last,
  87                              std::get<0>(_M_m), std::get<1>(_M_m),
  88                              std::get<2>(_M_m));
  89         }
  90
  91     private:
  92       std::tuple<_ForwardIterator1, _ForwardIterator1, _BinaryPredicate> _M_m;
  93     };
  94
  95   template<typename _Key, typename _Tp, typename _Hash, typename _Pred>
  96     struct __boyer_moore_map_base
  97     {
  98       template<typename _RAIter>
  99         __boyer_moore_map_base(_RAIter __pat, size_t __patlen,
 100                                _Hash&& __hf, _Pred&& __pred)
 101         : _M_bad_char{ __patlen, std::move(__hf), std::move(__pred) }
 102         {
 103           if (__patlen > 0)
 104             for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
 105               _M_bad_char[__pat[__i]] = __patlen - 1 - __i;
 106         }
 107
 108       using __diff_type = _Tp;
 109
 110       __diff_type
 111       _M_lookup(_Key __key, __diff_type __not_found) const
 112       {
 113         auto __iter = _M_bad_char.find(__key);
 114         if (__iter == _M_bad_char.end())
 115           return __not_found;
 116         return __iter->second;
 117       }
 118
 119       _Pred
 120       _M_pred() const { return _M_bad_char.key_eq(); }
 121
 122       _GLIBCXX_STD_C::unordered_map<_Key, _Tp, _Hash, _Pred> _M_bad_char;
 123     };
 124
 125   template<typename _Tp, size_t _Len, typename _Pred>
 126     struct __boyer_moore_array_base
 127     {
 128       template<typename _RAIter, typename _Unused>
 129         __boyer_moore_array_base(_RAIter __pat, size_t __patlen,
 130                                  _Unused&&, _Pred&& __pred)
 131         : _M_bad_char{ _GLIBCXX_STD_C::array<_Tp, _Len>{}, std::move(__pred) }
 132         {
 133           std::get<0>(_M_bad_char).fill(__patlen);
 134           if (__patlen > 0)
 135             for (__diff_type __i = 0; __i < __patlen - 1; ++__i)
 136               {
 137                 auto __ch = __pat[__i];
 138                 using _UCh = std::make_unsigned_t<decltype(__ch)>;
 139                 auto __uch = static_cast<_UCh>(__ch);
 140                 std::get<0>(_M_bad_char)[__uch] = __patlen - 1 - __i;
 141               }
 142         }
 143
 144       using __diff_type = _Tp;
 145
 146       template<typename _Key>
 147         __diff_type
 148         _M_lookup(_Key __key, __diff_type __not_found) const
 149         {
 150           auto __ukey = static_cast<std::make_unsigned_t<_Key>>(__key);
 151           if (__ukey >= _Len)
 152             return __not_found;
 153           return std::get<0>(_M_bad_char)[__ukey];
 154         }
 155
 156       const _Pred&
 157       _M_pred() const { return std::get<1>(_M_bad_char); }
 158
 159       std::tuple<_GLIBCXX_STD_C::array<_Tp, _Len>, _Pred> _M_bad_char;
 160     };
 161
 162   template<typename _Pred>
 163     struct __is_std_equal_to : std::false_type { };
 164
 165   template<>
 166     struct __is_std_equal_to<std::equal_to<void>> : std::true_type { };
 167
 168   // Use __boyer_moore_array_base when pattern consists of narrow characters
 169   // and uses std::equal_to as the predicate.
 170   template<typename _RAIter, typename _Hash, typename _Pred,
 171            typename _Val = typename iterator_traits<_RAIter>::value_type,
 172            typename _Diff = typename iterator_traits<_RAIter>::difference_type>
 173     using __boyer_moore_base_t
 174       = std::conditional_t<sizeof(_Val) == 1 && is_integral<_Val>::value
 175                            && __is_std_equal_to<_Pred>::value,
 176                            __boyer_moore_array_base<_Diff, 256, _Pred>,
 177                            __boyer_moore_map_base<_Val, _Diff, _Hash, _Pred>>;
 178
 179   template<typename _RAIter, typename _Hash
 180              = std::hash<typename std::iterator_traits<_RAIter>::value_type>,
 181            typename _BinaryPredicate = std::equal_to<>>
 182     class boyer_moore_searcher
 183     : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
 184     {
 185       using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
 186       using typename _Base::__diff_type;
 187
 188     public:
 189       boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last,
 190                            _Hash __hf = _Hash(),
 191                            _BinaryPredicate __pred = _BinaryPredicate());
 192
 193       template<typename _RandomAccessIterator2>
 194         _RandomAccessIterator2
 195         operator()(_RandomAccessIterator2 __first,
 196                    _RandomAccessIterator2 __last) const;
 197
 198     private:
 199       bool
 200       _M_is_prefix(_RAIter __word, __diff_type __len,
 201                    __diff_type __pos)
 202       {
 203         const auto& __pred = this->_M_pred();
 204         __diff_type __suffixlen = __len - __pos;
 205         for (__diff_type __i = 0; __i < __suffixlen; ++__i)
 206           if (!__pred(__word[__i], __word[__pos + __i]))
 207             return false;
 208         return true;
 209       }
 210
 211       __diff_type
 212       _M_suffix_length(_RAIter __word, __diff_type __len,
 213                        __diff_type __pos)
 214       {
 215         const auto& __pred = this->_M_pred();
 216         __diff_type __i = 0;
 217         while (__pred(__word[__pos - __i], __word[__len - 1 - __i])
 218                && __i < __pos)
 219           {
 220             ++__i;
 221           }
 222         return __i;
 223       }
 224
 225       template<typename _Tp>
 226         __diff_type
 227         _M_bad_char_shift(_Tp __c) const
 228         { return this->_M_lookup(__c, _M_pat_end - _M_pat); }
 229
 230       _RAIter _M_pat;
 231       _RAIter _M_pat_end;
 232       _GLIBCXX_STD_C::vector<__diff_type> _M_good_suffix;
 233     };
 234
 235   template<typename _RAIter, typename _Hash
 236              = std::hash<typename std::iterator_traits<_RAIter>::value_type>,
 237            typename _BinaryPredicate = std::equal_to<>>
 238     class boyer_moore_horspool_searcher
 239     : __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>
 240     {
 241       using _Base = __boyer_moore_base_t<_RAIter, _Hash, _BinaryPredicate>;
 242       using typename _Base::__diff_type;
 243
 244     public:
 245       boyer_moore_horspool_searcher(_RAIter __pat,
 246                                     _RAIter __pat_end,
 247                                     _Hash __hf = _Hash(),
 248                                     _BinaryPredicate __pred
 249                                     = _BinaryPredicate())
 250       : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),
 251         _M_pat(__pat), _M_pat_end(__pat_end)
 252       { }
 253
 254       template<typename _RandomAccessIterator2>
 255         _RandomAccessIterator2
 256         operator()(_RandomAccessIterator2 __first,
 257                    _RandomAccessIterator2 __last) const
 258         {
 259           const auto& __pred = this->_M_pred();
 260           auto __patlen = _M_pat_end - _M_pat;
 261           if (__patlen == 0)
 262             return __first;
 263           auto __len = __last - __first;
 264           while (__len >= __patlen)
 265             {
 266               for (auto __scan = __patlen - 1;
 267                    __pred(__first[__scan], _M_pat[__scan]); --__scan)
 268                 if (__scan == 0)
 269                   return __first;
 270               auto __shift = _M_bad_char_shift(__first[__patlen - 1]);
 271               __len -= __shift;
 272               __first += __shift;
 273             }
 274           return __last;
 275         }
 276
 277     private:
 278       template<typename _Tp>
 279         __diff_type
 280         _M_bad_char_shift(_Tp __c) const
 281         { return this->_M_lookup(__c, _M_pat_end - _M_pat); }
 282
 283       _RAIter _M_pat;
 284       _RAIter _M_pat_end;
 285     };
 286
 287   /// Generator function for default_searcher
 288   template<typename _ForwardIterator,
 289            typename _BinaryPredicate = std::equal_to<>>
 290     inline default_searcher<_ForwardIterator, _BinaryPredicate>
 291     make_default_searcher(_ForwardIterator __pat_first,
 292                           _ForwardIterator __pat_last,
 293                           _BinaryPredicate __pred = _BinaryPredicate())
 294     { return { __pat_first, __pat_last, __pred }; }
 295
 296   /// Generator function for boyer_moore_searcher
 297   template<typename _RAIter, typename _Hash
 298              = std::hash<typename std::iterator_traits<_RAIter>::value_type>,
 299            typename _BinaryPredicate = equal_to<>>
 300     inline boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>
 301     make_boyer_moore_searcher(_RAIter __pat_first, _RAIter __pat_last,
 302                               _Hash __hf = _Hash(),
 303                               _BinaryPredicate __pred = _BinaryPredicate())
 304     { return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; }
 305
 306   /// Generator function for boyer_moore_horspool_searcher
 307   template<typename _RAIter, typename _Hash
 308              = std::hash<typename std::iterator_traits<_RAIter>::value_type>,
 309            typename _BinaryPredicate = equal_to<>>
 310     inline boyer_moore_horspool_searcher<_RAIter, _Hash, _BinaryPredicate>
 311     make_boyer_moore_horspool_searcher(_RAIter __pat_first, _RAIter __pat_last,
 312                                        _Hash __hf = _Hash(),
 313                                        _BinaryPredicate __pred
 314                                        = _BinaryPredicate())
 315     { return { __pat_first, __pat_last, std::move(__hf), std::move(__pred) }; }
 316
 317   template<typename _RAIter, typename _Hash, typename _BinaryPredicate>
 318     boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
 319     boyer_moore_searcher(_RAIter __pat, _RAIter __pat_end,
 320                          _Hash __hf, _BinaryPredicate __pred)
 321     : _Base(__pat, __pat_end - __pat, std::move(__hf), std::move(__pred)),
 322       _M_pat(__pat), _M_pat_end(__pat_end), _M_good_suffix(__pat_end - __pat)
 323     {
 324       auto __patlen = __pat_end - __pat;
 325       if (__patlen == 0)
 326         return;
 327       __diff_type __last_prefix = __patlen - 1;
 328       for (__diff_type __p = __patlen - 1; __p >= 0; --__p)
 329         {
 330           if (_M_is_prefix(__pat, __patlen, __p + 1))
 331             __last_prefix = __p + 1;
 332           _M_good_suffix[__p] = __last_prefix + (__patlen - 1 - __p);
 333         }
 334       for (__diff_type __p = 0; __p < __patlen - 1; ++__p)
 335         {
 336           auto __slen = _M_suffix_length(__pat, __patlen, __p);
 337           auto __pos = __patlen - 1 - __slen;
 338           if (!__pred(__pat[__p - __slen], __pat[__pos]))
 339             _M_good_suffix[__pos] = __patlen - 1 - __p + __slen;
 340         }
 341     }
 342
 343   template<typename _RAIter, typename _Hash, typename _BinaryPredicate>
 344   template<typename _RandomAccessIterator2>
 345     _RandomAccessIterator2
 346     boyer_moore_searcher<_RAIter, _Hash, _BinaryPredicate>::
 347     operator()(_RandomAccessIterator2 __first,
 348                _RandomAccessIterator2 __last) const
 349     {
 350       auto __patlen = _M_pat_end - _M_pat;
 351       if (__patlen == 0)
 352         return __first;
 353       const auto& __pred = this->_M_pred();
 354       __diff_type __i = __patlen - 1;
 355       auto __stringlen = __last - __first;
 356       while (__i < __stringlen)
 357         {
 358           __diff_type __j = __patlen - 1;
 359           while (__j >= 0 && __pred(__first[__i], _M_pat[__j]))
 360             {
 361               --__i;
 362               --__j;
 363             }
 364           if (__j < 0)
 365             return __first + __i + 1;
 366           __i += std::max(_M_bad_char_shift(__first[__i]),
 367                           _M_good_suffix[__j]);
 368         }
 369       return __last;
 370     }
 371 } // namespace fundamentals_v1
 372
 373 inline namespace fundamentals_v2
 374 {
 375 #define __cpp_lib_experimental_not_fn 201406
 376
 377   /// [func.not_fn] Function template not_fn
 378   template<typename _Fn>
 379     inline auto
 380     not_fn(_Fn&& __fn)
 381     noexcept(std::is_nothrow_constructible<std::decay_t<_Fn>, _Fn&&>::value)
 382     {
 383       return std::_Not_fn<std::decay_t<_Fn>>{std::forward<_Fn>(__fn), 0};
 384     }
 385 } // namespace fundamentals_v2
 386 } // namespace experimental
 387
 388 _GLIBCXX_END_NAMESPACE_VERSION
 389 } // namespace std
 390
 391 #endif // C++14
 392
 393 #endif // _GLIBCXX_EXPERIMENTAL_FUNCTIONAL