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
27namespace 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