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