boost/algorithm/cxx11/is_sorted.hpp

   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/config.hpp>
  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     BOOST_CXX14_CONSTEXPR 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     BOOST_CXX14_CONSTEXPR 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     BOOST_CXX14_CONSTEXPR 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     BOOST_CXX14_CONSTEXPR 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     BOOST_CXX14_CONSTEXPR 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     BOOST_CXX14_CONSTEXPR 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     BOOST_CXX14_CONSTEXPR 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     BOOST_CXX14_CONSTEXPR 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     BOOST_CXX14_CONSTEXPR 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     BOOST_CXX14_CONSTEXPR 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     BOOST_CXX14_CONSTEXPR 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     BOOST_CXX14_CONSTEXPR 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     BOOST_CXX14_CONSTEXPR 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     BOOST_CXX14_CONSTEXPR 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     BOOST_CXX14_CONSTEXPR 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     BOOST_CXX14_CONSTEXPR 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