1 // -*- C++ -*- 2 3 // Copyright (C) 2007, 2008, 2009 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 RandomAccessIterator1, typename RandomAccessIterator2, 58 typename Pred> 59 bool 60 operator()(RandomAccessIterator1 i1, RandomAccessIterator2 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 RandomAccessIterator1, typename RandomAccessIterator2, 70 typename Pred> 71 std::pair<RandomAccessIterator1, RandomAccessIterator2> 72 sequential_algorithm(RandomAccessIterator1 begin1, 73 RandomAccessIterator1 end1, 74 RandomAccessIterator2 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 RandomAccessIterator1, typename RandomAccessIterator2, 88 typename Pred> 89 bool 90 operator()(RandomAccessIterator1 i1, RandomAccessIterator2 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 RandomAccessIterator1, typename RandomAccessIterator2, 103 typename Pred> 104 std::pair<RandomAccessIterator1, RandomAccessIterator2> 105 sequential_algorithm(RandomAccessIterator1 begin1, 106 RandomAccessIterator1 end1, 107 RandomAccessIterator2 begin2, Pred pred) 108 { 109 // Passed end iterator is one short. 110 RandomAccessIterator1 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 RandomAccessIterator1, typename RandomAccessIterator2, 128 typename Pred> 129 bool 130 operator()(RandomAccessIterator1 i1, RandomAccessIterator2 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 RandomAccessIterator1, typename RandomAccessIterator2, 141 typename Pred> 142 std::pair<RandomAccessIterator1, RandomAccessIterator2> 143 sequential_algorithm(RandomAccessIterator1 begin1, 144 RandomAccessIterator1 end1, 145 RandomAccessIterator2 begin2, Pred pred) 146 { return mismatch(begin1, end1, begin2, pred, sequential_tag()); } 147 }; 148 149 150 /** @brief Test predicate on several elements. */ 151 template<typename ForwardIterator> 152 struct find_first_of_selector : public generic_find_selector 153 { 154 ForwardIterator begin; 155 ForwardIterator end; 156 157 explicit find_first_of_selector(ForwardIterator begin, ForwardIterator end) 158 : begin(begin), end(end) { } 159 160 /** @brief Test on one position. 161 * @param i1 Iterator on first sequence. 162 * @param i2 Iterator on second sequence (unused). 163 * @param pred Find predicate. */ 164 template<typename RandomAccessIterator1, typename RandomAccessIterator2, 165 typename Pred> 166 bool 167 operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred) 168 { 169 for (ForwardIterator pos_in_candidates = begin; 170 pos_in_candidates != end; ++pos_in_candidates) 171 if (pred(*i1, *pos_in_candidates)) 172 return true; 173 return false; 174 } 175 176 /** @brief Corresponding sequential algorithm on a sequence. 177 * @param begin1 Begin iterator of first sequence. 178 * @param end1 End iterator of first sequence. 179 * @param begin2 Begin iterator of second sequence. 180 * @param pred Find predicate. */ 181 template<typename RandomAccessIterator1, typename RandomAccessIterator2, 182 typename Pred> 183 std::pair<RandomAccessIterator1, RandomAccessIterator2> 184 sequential_algorithm(RandomAccessIterator1 begin1, 185 RandomAccessIterator1 end1, 186 RandomAccessIterator2 begin2, Pred pred) 187 { return std::make_pair(find_first_of(begin1, end1, begin, end, pred, 188 sequential_tag()), begin2); } 189 }; 190 } 191 192 #endif /* _GLIBCXX_PARALLEL_FIND_SELECTORS_H */ 193
