libstdc++
for_each_selectors.h
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 3, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file parallel/for_each_selectors.h
00026  *  @brief Functors representing different tasks to be plugged into the
00027  *  generic parallelization methods for embarrassingly parallel functions.
00028  *  This file is a GNU parallel extension to the Standard C++ Library.
00029  */
00030 
00031 // Written by Felix Putze.
00032 
00033 #ifndef _GLIBCXX_PARALLEL_FOR_EACH_SELECTORS_H
00034 #define _GLIBCXX_PARALLEL_FOR_EACH_SELECTORS_H 1
00035 
00036 #include <parallel/basic_iterator.h>
00037 
00038 namespace __gnu_parallel
00039 {
00040   /** @brief Generic __selector for embarrassingly parallel functions. */
00041   template<typename _It>
00042     struct __generic_for_each_selector
00043     {
00044       /** @brief _Iterator on last element processed; needed for some
00045        *  algorithms (e. g. std::transform()).
00046        */
00047       _It _M_finish_iterator;
00048     };
00049 
00050   /** @brief std::for_each() selector. */
00051   template<typename _It>
00052     struct __for_each_selector : public __generic_for_each_selector<_It>
00053     {
00054       /** @brief Functor execution.
00055        *  @param __o Operator.
00056        *  @param __i iterator referencing object. */
00057       template<typename _Op>
00058         bool
00059         operator()(_Op& __o, _It __i)
00060         {
00061           __o(*__i);
00062           return true;
00063         }
00064     };
00065 
00066   /** @brief std::generate() selector. */
00067   template<typename _It>
00068     struct __generate_selector : public __generic_for_each_selector<_It>
00069     {
00070       /** @brief Functor execution.
00071        *  @param __o Operator.
00072        *  @param __i iterator referencing object. */
00073       template<typename _Op>
00074         bool
00075         operator()(_Op& __o, _It __i)
00076         {
00077           *__i = __o();
00078           return true;
00079         }
00080     };
00081 
00082   /** @brief std::fill() selector. */
00083   template<typename _It>
00084     struct __fill_selector : public __generic_for_each_selector<_It>
00085     {
00086       /** @brief Functor execution.
00087        *  @param __v Current value.
00088        *  @param __i iterator referencing object. */
00089       template<typename _ValueType>
00090         bool
00091         operator()(_ValueType& __v, _It __i)
00092         {
00093           *__i = __v;
00094           return true;
00095         }
00096     };
00097 
00098   /** @brief std::transform() __selector, one input sequence variant. */
00099   template<typename _It>
00100     struct __transform1_selector : public __generic_for_each_selector<_It>
00101     {
00102       /** @brief Functor execution.
00103        *  @param __o Operator.
00104        *  @param __i iterator referencing object. */
00105       template<typename _Op>
00106         bool
00107         operator()(_Op& __o, _It __i)
00108         {
00109           *__i.second = __o(*__i.first);
00110           return true;
00111         }
00112     };
00113 
00114   /** @brief std::transform() __selector, two input sequences variant. */
00115   template<typename _It>
00116     struct __transform2_selector : public __generic_for_each_selector<_It>
00117     {
00118       /** @brief Functor execution.
00119        *  @param __o Operator.
00120        *  @param __i iterator referencing object. */
00121       template<typename _Op>
00122         bool
00123         operator()(_Op& __o, _It __i)
00124         {
00125           *__i._M_third = __o(*__i._M_first, *__i._M_second);
00126           return true;
00127         }
00128     };
00129 
00130   /** @brief std::replace() selector. */
00131   template<typename _It, typename _Tp>
00132     struct __replace_selector : public __generic_for_each_selector<_It>
00133     {
00134       /** @brief Value to replace with. */
00135       const _Tp& __new_val;
00136 
00137       /** @brief Constructor
00138        *  @param __new_val Value to replace with. */
00139       explicit
00140       __replace_selector(const _Tp &__new_val) : __new_val(__new_val) {}
00141 
00142       /** @brief Functor execution.
00143        *  @param __v Current value.
00144        *  @param __i iterator referencing object. */
00145       bool
00146       operator()(_Tp& __v, _It __i)
00147       {
00148         if (*__i == __v)
00149           *__i = __new_val;
00150         return true;
00151       }
00152     };
00153 
00154   /** @brief std::replace() selector. */
00155   template<typename _It, typename _Op, typename _Tp>
00156     struct __replace_if_selector : public __generic_for_each_selector<_It>
00157     {
00158       /** @brief Value to replace with. */
00159       const _Tp& __new_val;
00160 
00161       /** @brief Constructor.
00162        *  @param __new_val Value to replace with. */
00163       explicit
00164       __replace_if_selector(const _Tp &__new_val) : __new_val(__new_val) { }
00165 
00166       /** @brief Functor execution.
00167        *  @param __o Operator.
00168        *  @param __i iterator referencing object. */
00169       bool
00170       operator()(_Op& __o, _It __i)
00171       {
00172         if (__o(*__i))
00173           *__i = __new_val;
00174         return true;
00175       }
00176     };
00177 
00178   /** @brief std::count() selector. */
00179   template<typename _It, typename _Diff>
00180     struct __count_selector : public __generic_for_each_selector<_It>
00181     {
00182       /** @brief Functor execution.
00183        *  @param __v Current value.
00184        *  @param __i iterator referencing object.
00185        *  @return 1 if count, 0 if does not count. */
00186       template<typename _ValueType>
00187         _Diff
00188         operator()(_ValueType& __v, _It __i)
00189         { return (__v == *__i) ? 1 : 0; }
00190     };
00191 
00192   /** @brief std::count_if () selector. */
00193   template<typename _It, typename _Diff>
00194     struct __count_if_selector : public __generic_for_each_selector<_It>
00195     {
00196       /** @brief Functor execution.
00197        *  @param __o Operator.
00198        *  @param __i iterator referencing object.
00199        *  @return 1 if count, 0 if does not count. */
00200       template<typename _Op>
00201         _Diff
00202         operator()(_Op& __o, _It __i)
00203         { return (__o(*__i)) ? 1 : 0; }
00204     };
00205 
00206   /** @brief std::accumulate() selector. */
00207   template<typename _It>
00208     struct __accumulate_selector : public __generic_for_each_selector<_It>
00209     {
00210       /** @brief Functor execution.
00211        *  @param __o Operator (unused).
00212        *  @param __i iterator referencing object.
00213        *  @return The current value. */
00214       template<typename _Op>
00215         typename std::iterator_traits<_It>::value_type
00216         operator()(_Op __o, _It __i)
00217         { return *__i; }
00218     };
00219 
00220   /** @brief std::inner_product() selector. */
00221   template<typename _It, typename _It2, typename _Tp>
00222     struct __inner_product_selector : public __generic_for_each_selector<_It>
00223     {
00224       /** @brief Begin iterator of first sequence. */
00225       _It  __begin1_iterator;
00226 
00227       /** @brief Begin iterator of second sequence. */
00228       _It2 __begin2_iterator;
00229 
00230       /** @brief Constructor.
00231        *  @param __b1 Begin iterator of first sequence.
00232        *  @param __b2 Begin iterator of second sequence. */
00233       explicit
00234       __inner_product_selector(_It __b1, _It2 __b2)
00235       : __begin1_iterator(__b1), __begin2_iterator(__b2) { }
00236 
00237       /** @brief Functor execution.
00238        *  @param __mult Multiplication functor.
00239        *  @param __current iterator referencing object.
00240        *  @return Inner product elemental __result. */
00241       template<typename _Op>
00242         _Tp
00243         operator()(_Op __mult, _It __current)
00244         {
00245           typename std::iterator_traits<_It>::difference_type __position
00246             = __current - __begin1_iterator;
00247           return __mult(*__current, *(__begin2_iterator + __position));
00248         }
00249     };
00250 
00251   /** @brief Selector that just returns the passed iterator. */
00252   template<typename _It>
00253     struct __identity_selector : public __generic_for_each_selector<_It>
00254     {
00255       /** @brief Functor execution.
00256        *  @param __o Operator (unused).
00257        *  @param __i iterator referencing object.
00258        *  @return Passed iterator. */
00259       template<typename _Op>
00260         _It
00261         operator()(_Op __o, _It __i)
00262         { return __i; }
00263     };
00264 
00265   /** @brief Selector that returns the difference between two adjacent
00266    *  __elements.
00267    */
00268   template<typename _It>
00269     struct __adjacent_difference_selector
00270     : public __generic_for_each_selector<_It>
00271     {
00272       template<typename _Op>
00273         bool
00274         operator()(_Op& __o, _It __i)
00275         {
00276           typename _It::first_type __go_back_one = __i.first;
00277           --__go_back_one;
00278           *__i.second = __o(*__i.first, *__go_back_one);
00279           return true;
00280         }
00281     };
00282 
00283   /** @brief Functor doing nothing
00284    *
00285    *  For some __reduction tasks (this is not a function object, but is
00286    *  passed as __selector __dummy parameter.
00287    */
00288   struct _Nothing
00289   {
00290     /** @brief Functor execution.
00291      *  @param __i iterator referencing object. */
00292     template<typename _It>
00293       void
00294       operator()(_It __i) { }
00295   };
00296 
00297   /** @brief Reduction function doing nothing. */
00298   struct _DummyReduct
00299   {
00300     bool
00301     operator()(bool, bool) const
00302     { return true; }
00303   };
00304 
00305   /** @brief Reduction for finding the maximum element, using a comparator. */
00306   template<typename _Compare, typename _It>
00307     struct __min_element_reduct
00308     {
00309       _Compare& __comp;
00310 
00311       explicit
00312       __min_element_reduct(_Compare &__c) : __comp(__c) { }
00313 
00314       _It
00315       operator()(_It __x, _It __y)
00316       { return (__comp(*__x, *__y)) ? __x : __y; }
00317     };
00318 
00319   /** @brief Reduction for finding the maximum element, using a comparator. */
00320   template<typename _Compare, typename _It>
00321     struct __max_element_reduct
00322     {
00323       _Compare& __comp;
00324 
00325       explicit
00326       __max_element_reduct(_Compare& __c) : __comp(__c) { }
00327 
00328       _It
00329       operator()(_It __x, _It __y)
00330       { return (__comp(*__x, *__y)) ? __y : __x; }
00331     };
00332 
00333   /** @brief General reduction, using a binary operator. */
00334   template<typename _BinOp>
00335     struct __accumulate_binop_reduct
00336     {
00337       _BinOp& __binop;
00338 
00339       explicit
00340       __accumulate_binop_reduct(_BinOp& __b) : __binop(__b) { }
00341 
00342       template<typename _Result, typename _Addend>
00343         _Result
00344         operator()(const _Result& __x, const _Addend& __y)
00345         { return __binop(__x, __y); }
00346     };
00347 }
00348 
00349 #endif /* _GLIBCXX_PARALLEL_FOR_EACH_SELECTORS_H */