find_selectors.h

Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2007, 2008 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 2, 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 // You should have received a copy of the GNU General Public License
00017 // along with this library; see the file COPYING.  If not, write to
00018 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
00019 // MA 02111-1307, USA.
00020 
00021 // As a special exception, you may use this file as part of a free
00022 // software library without restriction.  Specifically, if other files
00023 // instantiate templates or use macros or inline functions from this
00024 // file, or you compile this file and link it with other files to
00025 // produce an executable, this file does not by itself cause the
00026 // resulting executable to be covered by the GNU General Public
00027 // License.  This exception does not however invalidate any other
00028 // reasons why the executable file might be covered by the GNU General
00029 // Public License.
00030 
00031 /** @file parallel/find_selectors.h
00032  *  @brief Function objects representing different tasks to be plugged
00033  *  into the parallel find algorithm.
00034  *  This file is a GNU parallel extension to the Standard C++ Library.
00035  */
00036 
00037 // Written by Felix Putze.
00038 
00039 #ifndef _GLIBCXX_PARALLEL_FIND_FUNCTIONS_H
00040 #define _GLIBCXX_PARALLEL_FIND_FUNCTIONS_H 1
00041 
00042 #include <parallel/tags.h>
00043 #include <parallel/basic_iterator.h>
00044 #include <bits/stl_pair.h>
00045 
00046 namespace __gnu_parallel
00047 {
00048   /** @brief Base class of all __gnu_parallel::find_template selectors. */
00049   struct generic_find_selector
00050   { };
00051 
00052   /** 
00053    *  @brief Test predicate on a single element, used for std::find()
00054    *  and std::find_if ().
00055    */
00056   struct find_if_selector : public generic_find_selector
00057   {
00058     /** @brief Test on one position.
00059      * @param i1 Iterator on first sequence.
00060      * @param i2 Iterator on second sequence (unused).
00061      * @param pred Find predicate.
00062      */
00063     template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00064          typename Pred>
00065       bool 
00066       operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred)
00067       { return pred(*i1); }
00068 
00069     /** @brief Corresponding sequential algorithm on a sequence.
00070      *  @param begin1 Begin iterator of first sequence.
00071      *  @param end1 End iterator of first sequence.
00072      *  @param begin2 Begin iterator of second sequence.
00073      *  @param pred Find predicate.
00074      */
00075     template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00076          typename Pred>
00077       std::pair<RandomAccessIterator1, RandomAccessIterator2> 
00078       sequential_algorithm(RandomAccessIterator1 begin1,
00079                RandomAccessIterator1 end1,
00080                RandomAccessIterator2 begin2, Pred pred)
00081       { return std::make_pair(find_if(begin1, end1, pred,
00082                       sequential_tag()), begin2); }
00083   };
00084 
00085   /** @brief Test predicate on two adjacent elements. */
00086   struct adjacent_find_selector : public generic_find_selector
00087   {
00088     /** @brief Test on one position.
00089      *  @param i1 Iterator on first sequence.
00090      *  @param i2 Iterator on second sequence (unused).
00091      *  @param pred Find predicate.
00092      */
00093     template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00094          typename Pred>
00095       bool 
00096       operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred)
00097       {
00098     // Passed end iterator is one short.
00099     return pred(*i1, *(i1 + 1));
00100       }
00101 
00102     /** @brief Corresponding sequential algorithm on a sequence.
00103      *  @param begin1 Begin iterator of first sequence.
00104      *  @param end1 End iterator of first sequence.
00105      *  @param begin2 Begin iterator of second sequence.
00106      *  @param pred Find predicate.
00107      */
00108     template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00109          typename Pred>
00110       std::pair<RandomAccessIterator1, RandomAccessIterator2>
00111       sequential_algorithm(RandomAccessIterator1 begin1,
00112                RandomAccessIterator1 end1,
00113                RandomAccessIterator2 begin2, Pred pred)
00114       {
00115     // Passed end iterator is one short.
00116     RandomAccessIterator1 spot = adjacent_find(begin1, end1 + 1,
00117                            pred, sequential_tag());
00118     if (spot == (end1 + 1))
00119       spot = end1;
00120     return std::make_pair(spot, begin2);
00121       }
00122   };
00123 
00124   /** @brief Test inverted predicate on a single element. */
00125   struct mismatch_selector : public generic_find_selector
00126   {
00127     /** 
00128      *  @brief Test on one position.
00129      *  @param i1 Iterator on first sequence.
00130      *  @param i2 Iterator on second sequence (unused).
00131      *  @param pred Find predicate. 
00132      */
00133     template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00134          typename Pred>
00135       bool 
00136       operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred)
00137       { return !pred(*i1, *i2); }
00138 
00139     /** 
00140      *  @brief Corresponding sequential algorithm on a sequence.
00141      *  @param begin1 Begin iterator of first sequence.
00142      *  @param end1 End iterator of first sequence.
00143      *  @param begin2 Begin iterator of second sequence.
00144      *  @param pred Find predicate. 
00145      */
00146     template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00147          typename Pred>
00148       std::pair<RandomAccessIterator1, RandomAccessIterator2>
00149       sequential_algorithm(RandomAccessIterator1 begin1,
00150                RandomAccessIterator1 end1,
00151                RandomAccessIterator2 begin2, Pred pred)
00152       { return mismatch(begin1, end1, begin2, pred, sequential_tag()); }
00153   };
00154 
00155 
00156   /** @brief Test predicate on several elements. */
00157   template<typename ForwardIterator>
00158   struct find_first_of_selector : public generic_find_selector
00159   {
00160     ForwardIterator begin;
00161     ForwardIterator end;
00162 
00163     explicit find_first_of_selector(ForwardIterator begin, ForwardIterator end)
00164     : begin(begin), end(end) { }
00165 
00166     /** @brief Test on one position.
00167      *  @param i1 Iterator on first sequence.
00168      *  @param i2 Iterator on second sequence (unused).
00169      *  @param pred Find predicate. */
00170     template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00171          typename Pred>
00172       bool 
00173       operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred)
00174       {
00175     for (ForwardIterator pos_in_candidates = begin;
00176          pos_in_candidates != end; ++pos_in_candidates)
00177       if (pred(*i1, *pos_in_candidates))
00178         return true;
00179     return false;
00180       }
00181 
00182     /** @brief Corresponding sequential algorithm on a sequence.
00183      *  @param begin1 Begin iterator of first sequence.
00184      *  @param end1 End iterator of first sequence.
00185      *  @param begin2 Begin iterator of second sequence.
00186      *  @param pred Find predicate. */
00187     template<typename RandomAccessIterator1, typename RandomAccessIterator2,
00188          typename Pred>
00189       std::pair<RandomAccessIterator1, RandomAccessIterator2>
00190       sequential_algorithm(RandomAccessIterator1 begin1,
00191                RandomAccessIterator1 end1,
00192                RandomAccessIterator2 begin2, Pred pred)
00193       { return std::make_pair(find_first_of(begin1, end1, begin, end, pred,
00194                         sequential_tag()), begin2); }
00195   };
00196 }
00197 
00198 #endif

Generated on Sat Dec 12 09:40:10 2009 for libstdc++ by  doxygen 1.5.6