1 | // (C) Copyright Gennadiy Rozental 2001. |
2 | // Distributed under the Boost Software License, Version 1.0. |
3 | // (See accompanying file LICENSE_1_0.txt or copy at |
4 | // http://www.boost.org/LICENSE_1_0.txt) |
5 | |
6 | // See http://www.boost.org/libs/test for the library home page. |
7 | // |
8 | /// @file |
9 | /// Addition to STL algorithms |
10 | // *************************************************************************** |
11 | |
12 | #ifndef BOOST_TEST_UTILS_ALGORITHM_HPP |
13 | #define BOOST_TEST_UTILS_ALGORITHM_HPP |
14 | |
15 | // STL |
16 | #include <utility> |
17 | #include <algorithm> // std::find |
18 | #include <functional> // std::bind1st |
19 | |
20 | #include <boost/test/detail/suppress_warnings.hpp> |
21 | |
22 | //____________________________________________________________________________// |
23 | |
24 | namespace boost { |
25 | namespace unit_test { |
26 | namespace utils { |
27 | |
28 | /// @brief this algorithm search through two collections for first mismatch position that get returned as a pair |
29 | /// of iterators, first pointing to the mismatch position in first collection, second iterator in second one |
30 | /// |
31 | /// @param first1 - first collection begin iterator |
32 | /// @param last1 - first collection end iterator |
33 | /// @param first2 - second collection begin iterator |
34 | /// @param last2 - second collection end iterator |
35 | template <class InputIter1, class InputIter2> |
36 | inline std::pair<InputIter1, InputIter2> |
37 | mismatch( InputIter1 first1, InputIter1 last1, |
38 | InputIter2 first2, InputIter2 last2 ) |
39 | { |
40 | while( first1 != last1 && first2 != last2 && *first1 == *first2 ) { |
41 | ++first1; |
42 | ++first2; |
43 | } |
44 | |
45 | return std::pair<InputIter1, InputIter2>(first1, first2); |
46 | } |
47 | |
48 | //____________________________________________________________________________// |
49 | |
50 | /// @brief this algorithm search through two collections for first mismatch position that get returned as a pair |
51 | /// of iterators, first pointing to the mismatch position in first collection, second iterator in second one. This algorithms |
52 | /// uses supplied predicate for collection elements comparison |
53 | /// |
54 | /// @param first1 - first collection begin iterator |
55 | /// @param last1 - first collection end iterator |
56 | /// @param first2 - second collection begin iterator |
57 | /// @param last2 - second collection end iterator |
58 | /// @param pred - predicate to be used for search |
59 | template <class InputIter1, class InputIter2, class Predicate> |
60 | inline std::pair<InputIter1, InputIter2> |
61 | mismatch( InputIter1 first1, InputIter1 last1, |
62 | InputIter2 first2, InputIter2 last2, |
63 | Predicate pred ) |
64 | { |
65 | while( first1 != last1 && first2 != last2 && pred( *first1, *first2 ) ) { |
66 | ++first1; |
67 | ++first2; |
68 | } |
69 | |
70 | return std::pair<InputIter1, InputIter2>(first1, first2); |
71 | } |
72 | |
73 | //____________________________________________________________________________// |
74 | |
75 | /// @brief this algorithm search through first collection for first element that does not belong a second one |
76 | /// |
77 | /// @param first1 - first collection begin iterator |
78 | /// @param last1 - first collection end iterator |
79 | /// @param first2 - second collection begin iterator |
80 | /// @param last2 - second collection end iterator |
81 | template<class ForwardIterator1, class ForwardIterator2> |
82 | inline ForwardIterator1 |
83 | find_first_not_of( ForwardIterator1 first1, ForwardIterator1 last1, |
84 | ForwardIterator2 first2, ForwardIterator2 last2 ) |
85 | { |
86 | while( first1 != last1 ) { |
87 | if( std::find( first2, last2, *first1 ) == last2 ) |
88 | break; |
89 | ++first1; |
90 | } |
91 | |
92 | return first1; |
93 | } |
94 | |
95 | //____________________________________________________________________________// |
96 | |
97 | /// @brief this algorithm search through first collection for first element that does not satisfy binary |
98 | /// predicate in conjunction will any element in second collection |
99 | /// |
100 | /// @param first1 - first collection begin iterator |
101 | /// @param last1 - first collection end iterator |
102 | /// @param first2 - second collection begin iterator |
103 | /// @param last2 - second collection end iterator |
104 | /// @param pred - predicate to be used for search |
105 | template<class ForwardIterator1, class ForwardIterator2, class Predicate> |
106 | inline ForwardIterator1 |
107 | find_first_not_of( ForwardIterator1 first1, ForwardIterator1 last1, |
108 | ForwardIterator2 first2, ForwardIterator2 last2, |
109 | Predicate pred ) |
110 | { |
111 | while( first1 != last1 ) { |
112 | if( std::find_if( first2, last2, std::bind1st( pred, *first1 ) ) == last2 ) |
113 | break; |
114 | ++first1; |
115 | } |
116 | |
117 | return first1; |
118 | } |
119 | |
120 | //____________________________________________________________________________// |
121 | |
122 | /// @brief this algorithm search through first collection for last element that belongs to a second one |
123 | /// |
124 | /// @param first1 - first collection begin iterator |
125 | /// @param last1 - first collection end iterator |
126 | /// @param first2 - second collection begin iterator |
127 | /// @param last2 - second collection end iterator |
128 | template<class BidirectionalIterator1, class ForwardIterator2> |
129 | inline BidirectionalIterator1 |
130 | find_last_of( BidirectionalIterator1 first1, BidirectionalIterator1 last1, |
131 | ForwardIterator2 first2, ForwardIterator2 last2 ) |
132 | { |
133 | if( first1 == last1 || first2 == last2 ) |
134 | return last1; |
135 | |
136 | BidirectionalIterator1 it1 = last1; |
137 | while( --it1 != first1 && std::find( first2, last2, *it1 ) == last2 ) {} |
138 | |
139 | return it1 == first1 && std::find( first2, last2, *it1 ) == last2 ? last1 : it1; |
140 | } |
141 | |
142 | //____________________________________________________________________________// |
143 | |
144 | /// @brief this algorithm search through first collection for last element that satisfy binary |
145 | /// predicate in conjunction will at least one element in second collection |
146 | /// |
147 | /// @param first1 - first collection begin iterator |
148 | /// @param last1 - first collection end iterator |
149 | /// @param first2 - second collection begin iterator |
150 | /// @param last2 - second collection end iterator |
151 | /// @param pred - predicate to be used for search |
152 | template<class BidirectionalIterator1, class ForwardIterator2, class Predicate> |
153 | inline BidirectionalIterator1 |
154 | find_last_of( BidirectionalIterator1 first1, BidirectionalIterator1 last1, |
155 | ForwardIterator2 first2, ForwardIterator2 last2, |
156 | Predicate pred ) |
157 | { |
158 | if( first1 == last1 || first2 == last2 ) |
159 | return last1; |
160 | |
161 | BidirectionalIterator1 it1 = last1; |
162 | while( --it1 != first1 && std::find_if( first2, last2, std::bind1st( pred, *it1 ) ) == last2 ) {} |
163 | |
164 | return it1 == first1 && std::find_if( first2, last2, std::bind1st( pred, *it1 ) ) == last2 ? last1 : it1; |
165 | } |
166 | |
167 | //____________________________________________________________________________// |
168 | |
169 | /// @brief this algorithm search through first collection for last element that does not belong to a second one |
170 | /// |
171 | /// @param first1 - first collection begin iterator |
172 | /// @param last1 - first collection end iterator |
173 | /// @param first2 - second collection begin iterator |
174 | /// @param last2 - second collection end iterator |
175 | template<class BidirectionalIterator1, class ForwardIterator2> |
176 | inline BidirectionalIterator1 |
177 | find_last_not_of( BidirectionalIterator1 first1, BidirectionalIterator1 last1, |
178 | ForwardIterator2 first2, ForwardIterator2 last2 ) |
179 | { |
180 | if( first1 == last1 || first2 == last2 ) |
181 | return last1; |
182 | |
183 | BidirectionalIterator1 it1 = last1; |
184 | while( --it1 != first1 && std::find( first2, last2, *it1 ) != last2 ) {} |
185 | |
186 | return it1 == first1 && std::find( first2, last2, *it1 ) != last2 ? last1 : it1; |
187 | } |
188 | |
189 | //____________________________________________________________________________// |
190 | |
191 | /// @brief this algorithm search through first collection for last element that does not satisfy binary |
192 | /// predicate in conjunction will any element in second collection |
193 | /// |
194 | /// @param first1 - first collection begin iterator |
195 | /// @param last1 - first collection end iterator |
196 | /// @param first2 - second collection begin iterator |
197 | /// @param last2 - second collection end iterator |
198 | /// @param pred - predicate to be used for search |
199 | template<class BidirectionalIterator1, class ForwardIterator2, class Predicate> |
200 | inline BidirectionalIterator1 |
201 | find_last_not_of( BidirectionalIterator1 first1, BidirectionalIterator1 last1, |
202 | ForwardIterator2 first2, ForwardIterator2 last2, |
203 | Predicate pred ) |
204 | { |
205 | if( first1 == last1 || first2 == last2 ) |
206 | return last1; |
207 | |
208 | BidirectionalIterator1 it1 = last1; |
209 | while( --it1 != first1 && std::find_if( first2, last2, std::bind1st( pred, *it1 ) ) != last2 ) {} |
210 | |
211 | return it1 == first1 && std::find_if( first2, last2, std::bind1st( pred, *it1 ) ) == last2 ? last1 : it1; |
212 | } |
213 | |
214 | //____________________________________________________________________________// |
215 | |
216 | } // namespace utils |
217 | } // namespace unit_test |
218 | } // namespace boost |
219 | |
220 | #include <boost/test/detail/enable_warnings.hpp> |
221 | |
222 | #endif // BOOST_TEST_UTILS_ALGORITHM_HPP |
223 | |