3 // Copyright (C) 2007, 2008 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 2, 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 // You should have received a copy of the GNU General Public License
17 // along with this library; see the file COPYING. If not, write to
18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
19 // MA 02111-1307, USA.
21 // As a special exception, you may use this file as part of a free
22 // software library without restriction. Specifically, if other files
23 // instantiate templates or use macros or inline functions from this
24 // file, or you compile this file and link it with other files to
25 // produce an executable, this file does not by itself cause the
26 // resulting executable to be covered by the GNU General Public
27 // License. This exception does not however invalidate any other
28 // reasons why the executable file might be covered by the GNU General
31 /** @file parallel/find_selectors.h
32 * @brief Function objects representing different tasks to be plugged
33 * into the parallel find algorithm.
34 * This file is a GNU parallel extension to the Standard C++ Library.
37 // Written by Felix Putze.
39 #ifndef _GLIBCXX_PARALLEL_FIND_FUNCTIONS_H
40 #define _GLIBCXX_PARALLEL_FIND_FUNCTIONS_H 1
42 #include <parallel/tags.h>
43 #include <parallel/basic_iterator.h>
44 #include <bits/stl_pair.h>
46 namespace __gnu_parallel
48 /** @brief Base class of all __gnu_parallel::find_template selectors. */
49 struct generic_find_selector
53 * @brief Test predicate on a single element, used for std::find()
54 * and std::find_if ().
56 struct find_if_selector
: public generic_find_selector
58 /** @brief Test on one position.
59 * @param i1 Iterator on first sequence.
60 * @param i2 Iterator on second sequence (unused).
61 * @param pred Find predicate.
63 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
,
66 operator()(RandomAccessIterator1 i1
, RandomAccessIterator2 i2
, Pred pred
)
69 /** @brief Corresponding sequential algorithm on a sequence.
70 * @param begin1 Begin iterator of first sequence.
71 * @param end1 End iterator of first sequence.
72 * @param begin2 Begin iterator of second sequence.
73 * @param pred Find predicate.
75 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
,
77 std::pair
<RandomAccessIterator1
, RandomAccessIterator2
>
78 sequential_algorithm(RandomAccessIterator1 begin1
,
79 RandomAccessIterator1 end1
,
80 RandomAccessIterator2 begin2
, Pred pred
)
81 { return std::make_pair(find_if(begin1
, end1
, pred
,
82 sequential_tag()), begin2
); }
85 /** @brief Test predicate on two adjacent elements. */
86 struct adjacent_find_selector
: public generic_find_selector
88 /** @brief Test on one position.
89 * @param i1 Iterator on first sequence.
90 * @param i2 Iterator on second sequence (unused).
91 * @param pred Find predicate.
93 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
,
96 operator()(RandomAccessIterator1 i1
, RandomAccessIterator2 i2
, Pred pred
)
98 // Passed end iterator is one short.
99 return pred(*i1
, *(i1
+ 1));
102 /** @brief Corresponding sequential algorithm on a sequence.
103 * @param begin1 Begin iterator of first sequence.
104 * @param end1 End iterator of first sequence.
105 * @param begin2 Begin iterator of second sequence.
106 * @param pred Find predicate.
108 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
,
110 std::pair
<RandomAccessIterator1
, RandomAccessIterator2
>
111 sequential_algorithm(RandomAccessIterator1 begin1
,
112 RandomAccessIterator1 end1
,
113 RandomAccessIterator2 begin2
, Pred pred
)
115 // Passed end iterator is one short.
116 RandomAccessIterator1 spot
= adjacent_find(begin1
, end1
+ 1,
117 pred
, sequential_tag());
118 if (spot
== (end1
+ 1))
120 return std::make_pair(spot
, begin2
);
124 /** @brief Test inverted predicate on a single element. */
125 struct mismatch_selector
: public generic_find_selector
128 * @brief Test on one position.
129 * @param i1 Iterator on first sequence.
130 * @param i2 Iterator on second sequence (unused).
131 * @param pred Find predicate.
133 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
,
136 operator()(RandomAccessIterator1 i1
, RandomAccessIterator2 i2
, Pred pred
)
137 { return !pred(*i1
, *i2
); }
140 * @brief Corresponding sequential algorithm on a sequence.
141 * @param begin1 Begin iterator of first sequence.
142 * @param end1 End iterator of first sequence.
143 * @param begin2 Begin iterator of second sequence.
144 * @param pred Find predicate.
146 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
,
148 std::pair
<RandomAccessIterator1
, RandomAccessIterator2
>
149 sequential_algorithm(RandomAccessIterator1 begin1
,
150 RandomAccessIterator1 end1
,
151 RandomAccessIterator2 begin2
, Pred pred
)
152 { return mismatch(begin1
, end1
, begin2
, pred
, sequential_tag()); }
156 /** @brief Test predicate on several elements. */
157 template<typename ForwardIterator
>
158 struct find_first_of_selector
: public generic_find_selector
160 ForwardIterator begin
;
163 explicit find_first_of_selector(ForwardIterator begin
, ForwardIterator end
)
164 : begin(begin
), end(end
) { }
166 /** @brief Test on one position.
167 * @param i1 Iterator on first sequence.
168 * @param i2 Iterator on second sequence (unused).
169 * @param pred Find predicate. */
170 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
,
173 operator()(RandomAccessIterator1 i1
, RandomAccessIterator2 i2
, Pred pred
)
175 for (ForwardIterator pos_in_candidates
= begin
;
176 pos_in_candidates
!= end
; ++pos_in_candidates
)
177 if (pred(*i1
, *pos_in_candidates
))
182 /** @brief Corresponding sequential algorithm on a sequence.
183 * @param begin1 Begin iterator of first sequence.
184 * @param end1 End iterator of first sequence.
185 * @param begin2 Begin iterator of second sequence.
186 * @param pred Find predicate. */
187 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
,
189 std::pair
<RandomAccessIterator1
, RandomAccessIterator2
>
190 sequential_algorithm(RandomAccessIterator1 begin1
,
191 RandomAccessIterator1 end1
,
192 RandomAccessIterator2 begin2
, Pred pred
)
193 { return std::make_pair(find_first_of(begin1
, end1
, begin
, end
, pred
,
194 sequential_tag()), begin2
); }