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>
is_sorted_until(ForwardIterator first,ForwardIterator last)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>
is_sorted(ForwardIterator first,ForwardIterator last,Pred p)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>
is_sorted(ForwardIterator first,ForwardIterator last)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>
is_sorted_until(const R & range,Pred p)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>
is_sorted_until(const R & range)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
is_sorted(const R & range,Pred p)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>
is_sorted(const R & range)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>
is_increasing(ForwardIterator first,ForwardIterator last)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>
is_increasing(const R & range)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>
is_decreasing(ForwardIterator first,ForwardIterator last)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>
is_decreasing(const R & range)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>
is_strictly_increasing(ForwardIterator first,ForwardIterator last)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>
is_strictly_increasing(const R & range)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>
is_strictly_decreasing(ForwardIterator first,ForwardIterator last)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>
is_strictly_decreasing(const R & range)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