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