libstdc++-v3/include/parallel/find_selectors.h

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2007-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 terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 3, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // 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 parallel/find_selectors.h
  26  *  @brief _Function objects representing different tasks to be plugged
  27  *  into the parallel find algorithm.
  28  *  This file is a GNU parallel extension to the Standard C++ Library.
  29  */
  30
  31 // Written by Felix Putze.
  32
  33 #ifndef _GLIBCXX_PARALLEL_FIND_SELECTORS_H
  34 #define _GLIBCXX_PARALLEL_FIND_SELECTORS_H 1
  35
  36 #include <parallel/tags.h>
  37 #include <parallel/basic_iterator.h>
  38 #include <bits/stl_pair.h>
  39
  40 namespace __gnu_parallel
  41 {
  42   /** @brief Base class of all __gnu_parallel::__find_template selectors. */
  43   struct __generic_find_selector
  44   { };
  45
  46   /**
  47    *  @brief Test predicate on a single element, used for std::find()
  48    *  and std::find_if ().
  49    */
  50   struct __find_if_selector : public __generic_find_selector
  51   {
  52     /** @brief Test on one position.
  53      * @param __i1 _Iterator on first sequence.
  54      * @param __i2 _Iterator on second sequence (unused).
  55      * @param __pred Find predicate.
  56      */
  57     template<typename _RAIter1, typename _RAIter2,
  58              typename _Pred>
  59       bool
  60       operator()(_RAIter1 __i1, _RAIter2 __i2, _Pred __pred)
  61       { return __pred(*__i1); }
  62
  63     /** @brief Corresponding sequential algorithm on a sequence.
  64      *  @param __begin1 Begin iterator of first sequence.
  65      *  @param __end1 End iterator of first sequence.
  66      *  @param __begin2 Begin iterator of second sequence.
  67      *  @param __pred Find predicate.
  68      */
  69     template<typename _RAIter1, typename _RAIter2,
  70              typename _Pred>
  71       std::pair<_RAIter1, _RAIter2>
  72       _M_sequential_algorithm(_RAIter1 __begin1,
  73                            _RAIter1 __end1,
  74                            _RAIter2 __begin2, _Pred __pred)
  75       { return std::make_pair(find_if(__begin1, __end1, __pred,
  76                                       sequential_tag()), __begin2); }
  77   };
  78
  79   /** @brief Test predicate on two adjacent elements. */
  80   struct __adjacent_find_selector : public __generic_find_selector
  81   {
  82     /** @brief Test on one position.
  83      *  @param __i1 _Iterator on first sequence.
  84      *  @param __i2 _Iterator on second sequence (unused).
  85      *  @param __pred Find predicate.
  86      */
  87     template<typename _RAIter1, typename _RAIter2,
  88              typename _Pred>
  89       bool
  90       operator()(_RAIter1 __i1, _RAIter2 __i2, _Pred __pred)
  91       {
  92         // Passed end iterator is one short.
  93         return __pred(*__i1, *(__i1 + 1));
  94       }
  95
  96     /** @brief Corresponding sequential algorithm on a sequence.
  97      *  @param __begin1 Begin iterator of first sequence.
  98      *  @param __end1 End iterator of first sequence.
  99      *  @param __begin2 Begin iterator of second sequence.
 100      *  @param __pred Find predicate.
 101      */
 102     template<typename _RAIter1, typename _RAIter2,
 103              typename _Pred>
 104       std::pair<_RAIter1, _RAIter2>
 105       _M_sequential_algorithm(_RAIter1 __begin1,
 106                               _RAIter1 __end1,
 107                               _RAIter2 __begin2, _Pred __pred)
 108       {
 109         // Passed end iterator is one short.
 110         _RAIter1 __spot = adjacent_find(__begin1, __end1 + 1,
 111                                         __pred, sequential_tag());
 112         if (__spot == (__end1 + 1))
 113           __spot = __end1;
 114         return std::make_pair(__spot, __begin2);
 115       }
 116   };
 117
 118   /** @brief Test inverted predicate on a single element. */
 119   struct __mismatch_selector : public __generic_find_selector
 120   {
 121     /**
 122      *  @brief Test on one position.
 123      *  @param __i1 _Iterator on first sequence.
 124      *  @param __i2 _Iterator on second sequence (unused).
 125      *  @param __pred Find predicate.
 126      */
 127     template<typename _RAIter1, typename _RAIter2,
 128              typename _Pred>
 129       bool
 130       operator()(_RAIter1 __i1, _RAIter2 __i2, _Pred __pred)
 131       { return !__pred(*__i1, *__i2); }
 132
 133     /**
 134      *  @brief Corresponding sequential algorithm on a sequence.
 135      *  @param __begin1 Begin iterator of first sequence.
 136      *  @param __end1 End iterator of first sequence.
 137      *  @param __begin2 Begin iterator of second sequence.
 138      *  @param __pred Find predicate.
 139      */
 140     template<typename _RAIter1, typename _RAIter2,
 141              typename _Pred>
 142       std::pair<_RAIter1, _RAIter2>
 143       _M_sequential_algorithm(_RAIter1 __begin1,
 144                               _RAIter1 __end1,
 145                               _RAIter2 __begin2, _Pred __pred)
 146       { return mismatch(__begin1, __end1, __begin2,
 147                         __pred, sequential_tag()); }
 148   };
 149
 150
 151   /** @brief Test predicate on several elements. */
 152   template<typename _FIterator>
 153     struct __find_first_of_selector : public __generic_find_selector
 154     {
 155       _FIterator _M_begin;
 156       _FIterator _M_end;
 157
 158       explicit __find_first_of_selector(_FIterator __begin,
 159                                         _FIterator __end)
 160       : _M_begin(__begin), _M_end(__end) { }
 161
 162       /** @brief Test on one position.
 163        *  @param __i1 _Iterator on first sequence.
 164        *  @param __i2 _Iterator on second sequence (unused).
 165        *  @param __pred Find predicate. */
 166       template<typename _RAIter1, typename _RAIter2,
 167                typename _Pred>
 168         bool
 169         operator()(_RAIter1 __i1, _RAIter2 __i2, _Pred __pred)
 170         {
 171           for (_FIterator __pos_in_candidates = _M_begin;
 172                __pos_in_candidates != _M_end; ++__pos_in_candidates)
 173             if (__pred(*__i1, *__pos_in_candidates))
 174               return true;
 175           return false;
 176         }
 177
 178       /** @brief Corresponding sequential algorithm on a sequence.
 179        *  @param __begin1 Begin iterator of first sequence.
 180        *  @param __end1 End iterator of first sequence.
 181        *  @param __begin2 Begin iterator of second sequence.
 182        *  @param __pred Find predicate. */
 183       template<typename _RAIter1, typename _RAIter2,
 184                typename _Pred>
 185         std::pair<_RAIter1, _RAIter2>
 186         _M_sequential_algorithm(_RAIter1 __begin1,
 187                                 _RAIter1 __end1,
 188                                 _RAIter2 __begin2, _Pred __pred)
 189         {
 190           return std::make_pair(find_first_of(__begin1, __end1,
 191                                               _M_begin, _M_end, __pred,
 192                                               sequential_tag()), __begin2);
 193         }
 194      };
 195 }
 196
 197 #endif /* _GLIBCXX_PARALLEL_FIND_SELECTORS_H */