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