libstdc++
|
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/find_selectors.h 00026 * @brief Function objects representing different tasks to be plugged 00027 * into the parallel find algorithm. 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_FIND_SELECTORS_H 00034 #define _GLIBCXX_PARALLEL_FIND_SELECTORS_H 1 00035 00036 #include <parallel/tags.h> 00037 #include <parallel/basic_iterator.h> 00038 #include <bits/stl_pair.h> 00039 00040 namespace __gnu_parallel 00041 { 00042 /** @brief Base class of all __gnu_parallel::find_template selectors. */ 00043 struct generic_find_selector 00044 { }; 00045 00046 /** 00047 * @brief Test predicate on a single element, used for std::find() 00048 * and std::find_if (). 00049 */ 00050 struct find_if_selector : public generic_find_selector 00051 { 00052 /** @brief Test on one position. 00053 * @param i1 Iterator on first sequence. 00054 * @param i2 Iterator on second sequence (unused). 00055 * @param pred Find predicate. 00056 */ 00057 template<typename RandomAccessIterator1, typename RandomAccessIterator2, 00058 typename Pred> 00059 bool 00060 operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred) 00061 { return pred(*i1); } 00062 00063 /** @brief Corresponding sequential algorithm on a sequence. 00064 * @param begin1 Begin iterator of first sequence. 00065 * @param end1 End iterator of first sequence. 00066 * @param begin2 Begin iterator of second sequence. 00067 * @param pred Find predicate. 00068 */ 00069 template<typename RandomAccessIterator1, typename RandomAccessIterator2, 00070 typename Pred> 00071 std::pair<RandomAccessIterator1, RandomAccessIterator2> 00072 sequential_algorithm(RandomAccessIterator1 begin1, 00073 RandomAccessIterator1 end1, 00074 RandomAccessIterator2 begin2, Pred pred) 00075 { return std::make_pair(find_if(begin1, end1, pred, 00076 sequential_tag()), begin2); } 00077 }; 00078 00079 /** @brief Test predicate on two adjacent elements. */ 00080 struct adjacent_find_selector : public generic_find_selector 00081 { 00082 /** @brief Test on one position. 00083 * @param i1 Iterator on first sequence. 00084 * @param i2 Iterator on second sequence (unused). 00085 * @param pred Find predicate. 00086 */ 00087 template<typename RandomAccessIterator1, typename RandomAccessIterator2, 00088 typename Pred> 00089 bool 00090 operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred) 00091 { 00092 // Passed end iterator is one short. 00093 return pred(*i1, *(i1 + 1)); 00094 } 00095 00096 /** @brief Corresponding sequential algorithm on a sequence. 00097 * @param begin1 Begin iterator of first sequence. 00098 * @param end1 End iterator of first sequence. 00099 * @param begin2 Begin iterator of second sequence. 00100 * @param pred Find predicate. 00101 */ 00102 template<typename RandomAccessIterator1, typename RandomAccessIterator2, 00103 typename Pred> 00104 std::pair<RandomAccessIterator1, RandomAccessIterator2> 00105 sequential_algorithm(RandomAccessIterator1 begin1, 00106 RandomAccessIterator1 end1, 00107 RandomAccessIterator2 begin2, Pred pred) 00108 { 00109 // Passed end iterator is one short. 00110 RandomAccessIterator1 spot = adjacent_find(begin1, end1 + 1, 00111 pred, sequential_tag()); 00112 if (spot == (end1 + 1)) 00113 spot = end1; 00114 return std::make_pair(spot, begin2); 00115 } 00116 }; 00117 00118 /** @brief Test inverted predicate on a single element. */ 00119 struct mismatch_selector : public generic_find_selector 00120 { 00121 /** 00122 * @brief Test on one position. 00123 * @param i1 Iterator on first sequence. 00124 * @param i2 Iterator on second sequence (unused). 00125 * @param pred Find predicate. 00126 */ 00127 template<typename RandomAccessIterator1, typename RandomAccessIterator2, 00128 typename Pred> 00129 bool 00130 operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred) 00131 { return !pred(*i1, *i2); } 00132 00133 /** 00134 * @brief Corresponding sequential algorithm on a sequence. 00135 * @param begin1 Begin iterator of first sequence. 00136 * @param end1 End iterator of first sequence. 00137 * @param begin2 Begin iterator of second sequence. 00138 * @param pred Find predicate. 00139 */ 00140 template<typename RandomAccessIterator1, typename RandomAccessIterator2, 00141 typename Pred> 00142 std::pair<RandomAccessIterator1, RandomAccessIterator2> 00143 sequential_algorithm(RandomAccessIterator1 begin1, 00144 RandomAccessIterator1 end1, 00145 RandomAccessIterator2 begin2, Pred pred) 00146 { return mismatch(begin1, end1, begin2, pred, sequential_tag()); } 00147 }; 00148 00149 00150 /** @brief Test predicate on several elements. */ 00151 template<typename ForwardIterator> 00152 struct find_first_of_selector : public generic_find_selector 00153 { 00154 ForwardIterator begin; 00155 ForwardIterator end; 00156 00157 explicit find_first_of_selector(ForwardIterator begin, ForwardIterator end) 00158 : begin(begin), end(end) { } 00159 00160 /** @brief Test on one position. 00161 * @param i1 Iterator on first sequence. 00162 * @param i2 Iterator on second sequence (unused). 00163 * @param pred Find predicate. */ 00164 template<typename RandomAccessIterator1, typename RandomAccessIterator2, 00165 typename Pred> 00166 bool 00167 operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred) 00168 { 00169 for (ForwardIterator pos_in_candidates = begin; 00170 pos_in_candidates != end; ++pos_in_candidates) 00171 if (pred(*i1, *pos_in_candidates)) 00172 return true; 00173 return false; 00174 } 00175 00176 /** @brief Corresponding sequential algorithm on a sequence. 00177 * @param begin1 Begin iterator of first sequence. 00178 * @param end1 End iterator of first sequence. 00179 * @param begin2 Begin iterator of second sequence. 00180 * @param pred Find predicate. */ 00181 template<typename RandomAccessIterator1, typename RandomAccessIterator2, 00182 typename Pred> 00183 std::pair<RandomAccessIterator1, RandomAccessIterator2> 00184 sequential_algorithm(RandomAccessIterator1 begin1, 00185 RandomAccessIterator1 end1, 00186 RandomAccessIterator2 begin2, Pred pred) 00187 { return std::make_pair(find_first_of(begin1, end1, begin, end, pred, 00188 sequential_tag()), begin2); } 00189 }; 00190 } 00191 00192 #endif /* _GLIBCXX_PARALLEL_FIND_SELECTORS_H */