]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | // Copyright (c) 2010 Nuovation System Designs, LLC |
2 | // Grant Erickson <gerickson@nuovations.com> | |
3 | // | |
4 | // Reworked somewhat by Marshall Clow; August 2010 | |
5 | // | |
6 | // Distributed under the Boost Software License, Version 1.0. (See | |
7 | // accompanying file LICENSE_1_0.txt or copy at | |
8 | // http://www.boost.org/LICENSE_1_0.txt) | |
9 | // | |
10 | // See http://www.boost.org/ for latest version. | |
11 | // | |
12 | ||
13 | #ifndef BOOST_ALGORITHM_ORDERED_HPP | |
14 | #define BOOST_ALGORITHM_ORDERED_HPP | |
15 | ||
16 | #include <functional> | |
17 | #include <iterator> | |
18 | ||
19 | #include <boost/range/begin.hpp> | |
20 | #include <boost/range/end.hpp> | |
21 | ||
22 | #include <boost/utility/enable_if.hpp> | |
23 | #include <boost/type_traits/is_same.hpp> | |
24 | #include <boost/mpl/identity.hpp> | |
25 | ||
26 | namespace boost { namespace algorithm { | |
27 | ||
28 | /// \fn is_sorted_until ( ForwardIterator first, ForwardIterator last, Pred p ) | |
29 | /// \return the point in the sequence [first, last) where the elements are unordered | |
30 | /// (according to the comparison predicate 'p'). | |
31 | /// | |
32 | /// \param first The start of the sequence to be tested. | |
33 | /// \param last One past the end of the sequence | |
34 | /// \param p A binary predicate that returns true if two elements are ordered. | |
35 | /// | |
36 | template <typename ForwardIterator, typename Pred> | |
37 | ForwardIterator is_sorted_until ( ForwardIterator first, ForwardIterator last, Pred p ) | |
38 | { | |
39 | if ( first == last ) return last; // the empty sequence is ordered | |
40 | ForwardIterator next = first; | |
41 | while ( ++next != last ) | |
42 | { | |
43 | if ( p ( *next, *first )) | |
44 | return next; | |
45 | first = next; | |
46 | } | |
47 | return last; | |
48 | } | |
49 | ||
50 | /// \fn is_sorted_until ( ForwardIterator first, ForwardIterator last ) | |
51 | /// \return the point in the sequence [first, last) where the elements are unordered | |
52 | /// | |
53 | /// \param first The start of the sequence to be tested. | |
54 | /// \param last One past the end of the sequence | |
55 | /// | |
56 | template <typename ForwardIterator> | |
57 | ForwardIterator is_sorted_until ( ForwardIterator first, ForwardIterator last ) | |
58 | { | |
59 | typedef typename std::iterator_traits<ForwardIterator>::value_type value_type; | |
60 | return boost::algorithm::is_sorted_until ( first, last, std::less<value_type>()); | |
61 | } | |
62 | ||
63 | ||
64 | /// \fn is_sorted ( ForwardIterator first, ForwardIterator last, Pred p ) | |
65 | /// \return whether or not the entire sequence is sorted | |
66 | /// | |
67 | /// \param first The start of the sequence to be tested. | |
68 | /// \param last One past the end of the sequence | |
69 | /// \param p A binary predicate that returns true if two elements are ordered. | |
70 | /// | |
71 | template <typename ForwardIterator, typename Pred> | |
72 | bool is_sorted ( ForwardIterator first, ForwardIterator last, Pred p ) | |
73 | { | |
74 | return boost::algorithm::is_sorted_until (first, last, p) == last; | |
75 | } | |
76 | ||
77 | /// \fn is_sorted ( ForwardIterator first, ForwardIterator last ) | |
78 | /// \return whether or not the entire sequence is sorted | |
79 | /// | |
80 | /// \param first The start of the sequence to be tested. | |
81 | /// \param last One past the end of the sequence | |
82 | /// | |
83 | template <typename ForwardIterator> | |
84 | bool is_sorted ( ForwardIterator first, ForwardIterator last ) | |
85 | { | |
86 | return boost::algorithm::is_sorted_until (first, last) == last; | |
87 | } | |
88 | ||
89 | /// | |
90 | /// -- Range based versions of the C++11 functions | |
91 | /// | |
92 | ||
93 | /// \fn is_sorted_until ( const R &range, Pred p ) | |
94 | /// \return the point in the range R where the elements are unordered | |
95 | /// (according to the comparison predicate 'p'). | |
96 | /// | |
97 | /// \param range The range to be tested. | |
98 | /// \param p A binary predicate that returns true if two elements are ordered. | |
99 | /// | |
100 | template <typename R, typename Pred> | |
101 | typename boost::lazy_disable_if_c< | |
102 | boost::is_same<R, Pred>::value, | |
103 | typename boost::range_iterator<const R> | |
104 | >::type is_sorted_until ( const R &range, Pred p ) | |
105 | { | |
106 | return boost::algorithm::is_sorted_until ( boost::begin ( range ), boost::end ( range ), p ); | |
107 | } | |
108 | ||
109 | ||
110 | /// \fn is_sorted_until ( const R &range ) | |
111 | /// \return the point in the range R where the elements are unordered | |
112 | /// | |
113 | /// \param range The range to be tested. | |
114 | /// | |
115 | template <typename R> | |
116 | typename boost::range_iterator<const R>::type is_sorted_until ( const R &range ) | |
117 | { | |
118 | return boost::algorithm::is_sorted_until ( boost::begin ( range ), boost::end ( range )); | |
119 | } | |
120 | ||
121 | /// \fn is_sorted ( const R &range, Pred p ) | |
122 | /// \return whether or not the entire range R is sorted | |
123 | /// (according to the comparison predicate 'p'). | |
124 | /// | |
125 | /// \param range The range to be tested. | |
126 | /// \param p A binary predicate that returns true if two elements are ordered. | |
127 | /// | |
128 | template <typename R, typename Pred> | |
129 | typename boost::lazy_disable_if_c< boost::is_same<R, Pred>::value, boost::mpl::identity<bool> >::type | |
130 | is_sorted ( const R &range, Pred p ) | |
131 | { | |
132 | return boost::algorithm::is_sorted ( boost::begin ( range ), boost::end ( range ), p ); | |
133 | } | |
134 | ||
135 | ||
136 | /// \fn is_sorted ( const R &range ) | |
137 | /// \return whether or not the entire range R is sorted | |
138 | /// | |
139 | /// \param range The range to be tested. | |
140 | /// | |
141 | template <typename R> | |
142 | bool is_sorted ( const R &range ) | |
143 | { | |
144 | return boost::algorithm::is_sorted ( boost::begin ( range ), boost::end ( range )); | |
145 | } | |
146 | ||
147 | ||
148 | /// | |
149 | /// -- Range based versions of the C++11 functions | |
150 | /// | |
151 | ||
152 | /// \fn is_increasing ( ForwardIterator first, ForwardIterator last ) | |
153 | /// \return true if the entire sequence is increasing; i.e, each item is greater than or | |
154 | /// equal to the previous one. | |
155 | /// | |
156 | /// \param first The start of the sequence to be tested. | |
157 | /// \param last One past the end of the sequence | |
158 | /// | |
159 | /// \note This function will return true for sequences that contain items that compare | |
160 | /// equal. If that is not what you intended, you should use is_strictly_increasing instead. | |
161 | template <typename ForwardIterator> | |
162 | bool is_increasing ( ForwardIterator first, ForwardIterator last ) | |
163 | { | |
164 | typedef typename std::iterator_traits<ForwardIterator>::value_type value_type; | |
165 | return boost::algorithm::is_sorted (first, last, std::less<value_type>()); | |
166 | } | |
167 | ||
168 | ||
169 | /// \fn is_increasing ( const R &range ) | |
170 | /// \return true if the entire sequence is increasing; i.e, each item is greater than or | |
171 | /// equal to the previous one. | |
172 | /// | |
173 | /// \param range The range to be tested. | |
174 | /// | |
175 | /// \note This function will return true for sequences that contain items that compare | |
176 | /// equal. If that is not what you intended, you should use is_strictly_increasing instead. | |
177 | template <typename R> | |
178 | bool is_increasing ( const R &range ) | |
179 | { | |
180 | return is_increasing ( boost::begin ( range ), boost::end ( range )); | |
181 | } | |
182 | ||
183 | ||
184 | ||
185 | /// \fn is_decreasing ( ForwardIterator first, ForwardIterator last ) | |
186 | /// \return true if the entire sequence is decreasing; i.e, each item is less than | |
187 | /// or equal to the previous one. | |
188 | /// | |
189 | /// \param first The start of the sequence to be tested. | |
190 | /// \param last One past the end of the sequence | |
191 | /// | |
192 | /// \note This function will return true for sequences that contain items that compare | |
193 | /// equal. If that is not what you intended, you should use is_strictly_decreasing instead. | |
194 | template <typename ForwardIterator> | |
195 | bool is_decreasing ( ForwardIterator first, ForwardIterator last ) | |
196 | { | |
197 | typedef typename std::iterator_traits<ForwardIterator>::value_type value_type; | |
198 | return boost::algorithm::is_sorted (first, last, std::greater<value_type>()); | |
199 | } | |
200 | ||
201 | /// \fn is_decreasing ( const R &range ) | |
202 | /// \return true if the entire sequence is decreasing; i.e, each item is less than | |
203 | /// or equal to the previous one. | |
204 | /// | |
205 | /// \param range The range to be tested. | |
206 | /// | |
207 | /// \note This function will return true for sequences that contain items that compare | |
208 | /// equal. If that is not what you intended, you should use is_strictly_decreasing instead. | |
209 | template <typename R> | |
210 | bool is_decreasing ( const R &range ) | |
211 | { | |
212 | return is_decreasing ( boost::begin ( range ), boost::end ( range )); | |
213 | } | |
214 | ||
215 | ||
216 | ||
217 | /// \fn is_strictly_increasing ( ForwardIterator first, ForwardIterator last ) | |
218 | /// \return true if the entire sequence is strictly increasing; i.e, each item is greater | |
219 | /// than the previous one | |
220 | /// | |
221 | /// \param first The start of the sequence to be tested. | |
222 | /// \param last One past the end of the sequence | |
223 | /// | |
224 | /// \note This function will return false for sequences that contain items that compare | |
225 | /// equal. If that is not what you intended, you should use is_increasing instead. | |
226 | template <typename ForwardIterator> | |
227 | bool is_strictly_increasing ( ForwardIterator first, ForwardIterator last ) | |
228 | { | |
229 | typedef typename std::iterator_traits<ForwardIterator>::value_type value_type; | |
230 | return boost::algorithm::is_sorted (first, last, std::less_equal<value_type>()); | |
231 | } | |
232 | ||
233 | /// \fn is_strictly_increasing ( const R &range ) | |
234 | /// \return true if the entire sequence is strictly increasing; i.e, each item is greater | |
235 | /// than the previous one | |
236 | /// | |
237 | /// \param range The range to be tested. | |
238 | /// | |
239 | /// \note This function will return false for sequences that contain items that compare | |
240 | /// equal. If that is not what you intended, you should use is_increasing instead. | |
241 | template <typename R> | |
242 | bool is_strictly_increasing ( const R &range ) | |
243 | { | |
244 | return is_strictly_increasing ( boost::begin ( range ), boost::end ( range )); | |
245 | } | |
246 | ||
247 | ||
248 | /// \fn is_strictly_decreasing ( ForwardIterator first, ForwardIterator last ) | |
249 | /// \return true if the entire sequence is strictly decreasing; i.e, each item is less than | |
250 | /// the previous one | |
251 | /// | |
252 | /// \param first The start of the sequence to be tested. | |
253 | /// \param last One past the end of the sequence | |
254 | /// | |
255 | /// \note This function will return false for sequences that contain items that compare | |
256 | /// equal. If that is not what you intended, you should use is_decreasing instead. | |
257 | template <typename ForwardIterator> | |
258 | bool is_strictly_decreasing ( ForwardIterator first, ForwardIterator last ) | |
259 | { | |
260 | typedef typename std::iterator_traits<ForwardIterator>::value_type value_type; | |
261 | return boost::algorithm::is_sorted (first, last, std::greater_equal<value_type>()); | |
262 | } | |
263 | ||
264 | /// \fn is_strictly_decreasing ( const R &range ) | |
265 | /// \return true if the entire sequence is strictly decreasing; i.e, each item is less than | |
266 | /// the previous one | |
267 | /// | |
268 | /// \param range The range to be tested. | |
269 | /// | |
270 | /// \note This function will return false for sequences that contain items that compare | |
271 | /// equal. If that is not what you intended, you should use is_decreasing instead. | |
272 | template <typename R> | |
273 | bool is_strictly_decreasing ( const R &range ) | |
274 | { | |
275 | return is_strictly_decreasing ( boost::begin ( range ), boost::end ( range )); | |
276 | } | |
277 | ||
278 | }} // namespace boost | |
279 | ||
280 | #endif // BOOST_ALGORITHM_ORDERED_HPP |