3 // Copyright (C) 2007 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
, typename Pred
>
65 operator()(RandomAccessIterator1 i1
, RandomAccessIterator2 i2
, Pred pred
)
68 /** @brief Corresponding sequential algorithm on a sequence.
69 * @param begin1 Begin iterator of first sequence.
70 * @param end1 End iterator of first sequence.
71 * @param begin2 Begin iterator of second sequence.
72 * @param pred Find predicate.
74 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
, typename Pred
>
75 inline std::pair
<RandomAccessIterator1
, RandomAccessIterator2
>
76 sequential_algorithm(RandomAccessIterator1 begin1
, RandomAccessIterator1 end1
, RandomAccessIterator2 begin2
, Pred pred
)
78 return std::make_pair(find_if(begin1
, end1
, pred
, sequential_tag()), begin2
);
82 /** @brief Test predicate on two adjacent elements. */
83 struct adjacent_find_selector
: public generic_find_selector
85 /** @brief Test on one position.
86 * @param i1 Iterator on first sequence.
87 * @param i2 Iterator on second sequence (unused).
88 * @param pred Find predicate.
90 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
, typename Pred
>
92 operator()(RandomAccessIterator1 i1
, RandomAccessIterator2 i2
, Pred pred
)
94 // Passed end iterator is one short.
95 return pred(*i1
, *(i1
+ 1));
98 /** @brief Corresponding sequential algorithm on a sequence.
99 * @param begin1 Begin iterator of first sequence.
100 * @param end1 End iterator of first sequence.
101 * @param begin2 Begin iterator of second sequence.
102 * @param pred Find predicate.
104 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
, typename Pred
>
105 inline std::pair
<RandomAccessIterator1
, RandomAccessIterator2
>
106 sequential_algorithm(RandomAccessIterator1 begin1
, RandomAccessIterator1 end1
, RandomAccessIterator2 begin2
, Pred pred
)
108 // Passed end iterator is one short.
109 RandomAccessIterator1 spot
= adjacent_find(begin1
, end1
+ 1, pred
, sequential_tag());
110 if (spot
== (end1
+ 1))
112 return std::make_pair(spot
, begin2
);
116 /** @brief Test inverted predicate on a single element. */
117 struct mismatch_selector
: public generic_find_selector
120 * @brief Test on one position.
121 * @param i1 Iterator on first sequence.
122 * @param i2 Iterator on second sequence (unused).
123 * @param pred Find predicate.
125 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
, typename Pred
>
127 operator()(RandomAccessIterator1 i1
, RandomAccessIterator2 i2
, Pred pred
)
128 { return !pred(*i1
, *i2
); }
131 * @brief Corresponding sequential algorithm on a sequence.
132 * @param begin1 Begin iterator of first sequence.
133 * @param end1 End iterator of first sequence.
134 * @param begin2 Begin iterator of second sequence.
135 * @param pred Find predicate.
137 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
, typename Pred
>
138 inline std::pair
<RandomAccessIterator1
, RandomAccessIterator2
>
139 sequential_algorithm(RandomAccessIterator1 begin1
, RandomAccessIterator1 end1
, RandomAccessIterator2 begin2
, Pred pred
)
141 return mismatch(begin1
, end1
, begin2
, pred
, sequential_tag());
146 /** @brief Test predicate on several elements. */
147 template<typename ForwardIterator
>
148 struct find_first_of_selector
: public generic_find_selector
150 ForwardIterator begin
;
153 explicit find_first_of_selector(ForwardIterator begin
, ForwardIterator end
)
154 : begin(begin
), end(end
) { }
156 /** @brief Test on one position.
157 * @param i1 Iterator on first sequence.
158 * @param i2 Iterator on second sequence (unused).
159 * @param pred Find predicate. */
160 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
, typename Pred
>
162 operator()(RandomAccessIterator1 i1
, RandomAccessIterator2 i2
, Pred pred
)
164 for (ForwardIterator pos_in_candidates
= begin
; pos_in_candidates
!= end
; pos_in_candidates
++)
165 if (pred(*i1
, *pos_in_candidates
))
170 /** @brief Corresponding sequential algorithm on a sequence.
171 * @param begin1 Begin iterator of first sequence.
172 * @param end1 End iterator of first sequence.
173 * @param begin2 Begin iterator of second sequence.
174 * @param pred Find predicate. */
175 template<typename RandomAccessIterator1
, typename RandomAccessIterator2
, typename Pred
>
176 inline std::pair
<RandomAccessIterator1
, RandomAccessIterator2
>
177 sequential_algorithm(RandomAccessIterator1 begin1
, RandomAccessIterator1 end1
, RandomAccessIterator2 begin2
, Pred pred
)
179 return std::make_pair(find_first_of(begin1
, end1
, begin
, end
, pred
, sequential_tag()), begin2
);