3 // Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
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
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.
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.
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/>.
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.
31 // Written by Felix Putze.
33 #ifndef _GLIBCXX_PARALLEL_FIND_SELECTORS_H
34 #define _GLIBCXX_PARALLEL_FIND_SELECTORS_H 1
36 #include <parallel/tags.h>
37 #include <parallel/basic_iterator.h>
38 #include <bits/stl_pair.h>
40 namespace __gnu_parallel
42 /** @brief Base class of all __gnu_parallel::find_template selectors. */
43 struct generic_find_selector
47 * @brief Test predicate on a single element, used for std::find()
48 * and std::find_if ().
50 struct find_if_selector : public generic_find_selector
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.
57 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
60 operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred)
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.
69 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
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); }
79 /** @brief Test predicate on two adjacent elements. */
80 struct adjacent_find_selector : public generic_find_selector
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.
87 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
90 operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred)
92 // Passed end iterator is one short.
93 return pred(*i1, *(i1 + 1));
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.
102 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
104 std::pair<RandomAccessIterator1, RandomAccessIterator2>
105 sequential_algorithm(RandomAccessIterator1 begin1,
106 RandomAccessIterator1 end1,
107 RandomAccessIterator2 begin2, Pred pred)
109 // Passed end iterator is one short.
110 RandomAccessIterator1 spot = adjacent_find(begin1, end1 + 1,
111 pred, sequential_tag());
112 if (spot == (end1 + 1))
114 return std::make_pair(spot, begin2);
118 /** @brief Test inverted predicate on a single element. */
119 struct mismatch_selector : public generic_find_selector
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.
127 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
130 operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred)
131 { return !pred(*i1, *i2); }
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.
140 template<typename RandomAccessIterator1, typename RandomAccessIterator2,
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()); }
150 /** @brief Test predicate on several elements. */
151 template<typename ForwardIterator>
152 struct find_first_of_selector : public generic_find_selector
154 ForwardIterator begin;
157 explicit find_first_of_selector(ForwardIterator begin, ForwardIterator end)
158 : begin(begin), end(end) { }
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,
167 operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred)
169 for (ForwardIterator pos_in_candidates = begin;
170 pos_in_candidates != end; ++pos_in_candidates)
171 if (pred(*i1, *pos_in_candidates))
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,
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); }
192 #endif /* _GLIBCXX_PARALLEL_FIND_SELECTORS_H */