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