libstdc++
find_selectors.h
Go to the documentation of this file.
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>
38 #include <bits/stl_pair.h>
39 
40 namespace __gnu_parallel
41 {
42  /** @brief Base class of all __gnu_parallel::find_template selectors. */
44  { };
45 
46  /**
47  * @brief Test predicate on a single element, used for std::find()
48  * and std::find_if ().
49  */
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>
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. */
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>
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. */
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>
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>
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>
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 */
std::pair< RandomAccessIterator1, RandomAccessIterator2 > sequential_algorithm(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred)
Corresponding sequential algorithm on a sequence.
std::pair< RandomAccessIterator1, RandomAccessIterator2 > sequential_algorithm(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred)
Corresponding sequential algorithm on a sequence.
Forces sequential execution at compile time.
Definition: tags.h:42
GNU parallel code for public use.
pair holds two objects of arbitrary type.
Definition: stl_pair.h:67
Test predicate on two adjacent elements.
Test inverted predicate on a single element.
Test predicate on a single element, used for std::find() and std::find_if ().
bool operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred)
Test on one position.
std::pair< RandomAccessIterator1, RandomAccessIterator2 > sequential_algorithm(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred)
Corresponding sequential algorithm on a sequence.
std::pair< RandomAccessIterator1, RandomAccessIterator2 > sequential_algorithm(RandomAccessIterator1 begin1, RandomAccessIterator1 end1, RandomAccessIterator2 begin2, Pred pred)
Corresponding sequential algorithm on a sequence.
Includes the original header files concerned with iterators except for stream iterators. This file is a GNU parallel extension to the Standard C++ Library.
Tags for compile-time selection. This file is a GNU parallel extension to the Standard C++ Library...
bool operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred)
Test on one position.
Test predicate on several elements.
bool operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred)
Test on one position.
bool operator()(RandomAccessIterator1 i1, RandomAccessIterator2 i2, Pred pred)
Test on one position.
Base class of all __gnu_parallel::find_template selectors.