diff options
Diffstat (limited to 'boost/algorithm/cxx11/is_sorted.hpp')
-rw-r--r-- | boost/algorithm/cxx11/is_sorted.hpp | 287 |
1 files changed, 287 insertions, 0 deletions
diff --git a/boost/algorithm/cxx11/is_sorted.hpp b/boost/algorithm/cxx11/is_sorted.hpp new file mode 100644 index 0000000000..c9bc65fbe9 --- /dev/null +++ b/boost/algorithm/cxx11/is_sorted.hpp @@ -0,0 +1,287 @@ +// Copyright (c) 2010 Nuovation System Designs, LLC +// Grant Erickson <gerickson@nuovations.com> +// +// Reworked somewhat by Marshall Clow; August 2010 +// +// Distributed under the Boost Software License, Version 1.0. (See +// accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) +// +// See http://www.boost.org/ for latest version. +// + +#ifndef BOOST_ALGORITHM_ORDERED_HPP +#define BOOST_ALGORITHM_ORDERED_HPP + +#include <algorithm> +#include <functional> +#include <iterator> + +#include <boost/range/begin.hpp> +#include <boost/range/end.hpp> + +#include <boost/utility/enable_if.hpp> +#include <boost/type_traits/is_same.hpp> +#include <boost/mpl/identity.hpp> + +namespace boost { namespace algorithm { + +#if __cplusplus >= 201103L +// Use the C++11 versions of is_sorted/is_sorted_until if they are available +using std::is_sorted_until; // Section 25.4.1.5 +using std::is_sorted; // Section 25.4.1.5 +#else +/// \fn is_sorted_until ( ForwardIterator first, ForwardIterator last, Pred p ) +/// \return the point in the sequence [first, last) where the elements are unordered +/// (according to the comparison predicate 'p'). +/// +/// \param first The start of the sequence to be tested. +/// \param last One past the end of the sequence +/// \param p A binary predicate that returns true if two elements are ordered. +/// + template <typename ForwardIterator, typename Pred> + ForwardIterator is_sorted_until ( ForwardIterator first, ForwardIterator last, Pred p ) + { + if ( first == last ) return last; // the empty sequence is ordered + ForwardIterator next = first; + while ( ++next != last ) + { + if ( p ( *next, *first )) + return next; + first = next; + } + return last; + } + +/// \fn is_sorted_until ( ForwardIterator first, ForwardIterator last ) +/// \return the point in the sequence [first, last) where the elements are unordered +/// +/// \param first The start of the sequence to be tested. +/// \param last One past the end of the sequence +/// + template <typename ForwardIterator> + ForwardIterator is_sorted_until ( ForwardIterator first, ForwardIterator last ) + { + typedef typename std::iterator_traits<ForwardIterator>::value_type value_type; + return boost::algorithm::is_sorted_until ( first, last, std::less<value_type>()); + } + + +/// \fn is_sorted ( ForwardIterator first, ForwardIterator last, Pred p ) +/// \return whether or not the entire sequence is sorted +/// +/// \param first The start of the sequence to be tested. +/// \param last One past the end of the sequence +/// \param p A binary predicate that returns true if two elements are ordered. +/// + template <typename ForwardIterator, typename Pred> + bool is_sorted ( ForwardIterator first, ForwardIterator last, Pred p ) + { + return boost::algorithm::is_sorted_until (first, last, p) == last; + } + +/// \fn is_sorted ( ForwardIterator first, ForwardIterator last ) +/// \return whether or not the entire sequence is sorted +/// +/// \param first The start of the sequence to be tested. +/// \param last One past the end of the sequence +/// + template <typename ForwardIterator> + bool is_sorted ( ForwardIterator first, ForwardIterator last ) + { + return boost::algorithm::is_sorted_until (first, last) == last; + } +#endif + +/// +/// -- Range based versions of the C++11 functions +/// + +/// \fn is_sorted_until ( const R &range, Pred p ) +/// \return the point in the range R where the elements are unordered +/// (according to the comparison predicate 'p'). +/// +/// \param range The range to be tested. +/// \param p A binary predicate that returns true if two elements are ordered. +/// + template <typename R, typename Pred> + typename boost::lazy_disable_if_c< + boost::is_same<R, Pred>::value, + typename boost::range_iterator<const R> + >::type is_sorted_until ( const R &range, Pred p ) + { + return boost::algorithm::is_sorted_until ( boost::begin ( range ), boost::end ( range ), p ); + } + + +/// \fn is_sorted_until ( const R &range ) +/// \return the point in the range R where the elements are unordered +/// +/// \param range The range to be tested. +/// + template <typename R> + typename boost::range_iterator<const R>::type is_sorted_until ( const R &range ) + { + return boost::algorithm::is_sorted_until ( boost::begin ( range ), boost::end ( range )); + } + +/// \fn is_sorted ( const R &range, Pred p ) +/// \return whether or not the entire range R is sorted +/// (according to the comparison predicate 'p'). +/// +/// \param range The range to be tested. +/// \param p A binary predicate that returns true if two elements are ordered. +/// + template <typename R, typename Pred> + typename boost::lazy_disable_if_c< boost::is_same<R, Pred>::value, boost::mpl::identity<bool> >::type + is_sorted ( const R &range, Pred p ) + { + return boost::algorithm::is_sorted ( boost::begin ( range ), boost::end ( range ), p ); + } + + +/// \fn is_sorted ( const R &range ) +/// \return whether or not the entire range R is sorted +/// +/// \param range The range to be tested. +/// + template <typename R> + bool is_sorted ( const R &range ) + { + return boost::algorithm::is_sorted ( boost::begin ( range ), boost::end ( range )); + } + + +/// +/// -- Range based versions of the C++11 functions +/// + +/// \fn is_increasing ( ForwardIterator first, ForwardIterator last ) +/// \return true if the entire sequence is increasing; i.e, each item is greater than or +/// equal to the previous one. +/// +/// \param first The start of the sequence to be tested. +/// \param last One past the end of the sequence +/// +/// \note This function will return true for sequences that contain items that compare +/// equal. If that is not what you intended, you should use is_strictly_increasing instead. + template <typename ForwardIterator> + bool is_increasing ( ForwardIterator first, ForwardIterator last ) + { + typedef typename std::iterator_traits<ForwardIterator>::value_type value_type; + return boost::algorithm::is_sorted (first, last, std::less<value_type>()); + } + + +/// \fn is_increasing ( const R &range ) +/// \return true if the entire sequence is increasing; i.e, each item is greater than or +/// equal to the previous one. +/// +/// \param range The range to be tested. +/// +/// \note This function will return true for sequences that contain items that compare +/// equal. If that is not what you intended, you should use is_strictly_increasing instead. + template <typename R> + bool is_increasing ( const R &range ) + { + return is_increasing ( boost::begin ( range ), boost::end ( range )); + } + + + +/// \fn is_decreasing ( ForwardIterator first, ForwardIterator last ) +/// \return true if the entire sequence is decreasing; i.e, each item is less than +/// or equal to the previous one. +/// +/// \param first The start of the sequence to be tested. +/// \param last One past the end of the sequence +/// +/// \note This function will return true for sequences that contain items that compare +/// equal. If that is not what you intended, you should use is_strictly_decreasing instead. + template <typename ForwardIterator> + bool is_decreasing ( ForwardIterator first, ForwardIterator last ) + { + typedef typename std::iterator_traits<ForwardIterator>::value_type value_type; + return boost::algorithm::is_sorted (first, last, std::greater<value_type>()); + } + +/// \fn is_decreasing ( const R &range ) +/// \return true if the entire sequence is decreasing; i.e, each item is less than +/// or equal to the previous one. +/// +/// \param range The range to be tested. +/// +/// \note This function will return true for sequences that contain items that compare +/// equal. If that is not what you intended, you should use is_strictly_decreasing instead. + template <typename R> + bool is_decreasing ( const R &range ) + { + return is_decreasing ( boost::begin ( range ), boost::end ( range )); + } + + + +/// \fn is_strictly_increasing ( ForwardIterator first, ForwardIterator last ) +/// \return true if the entire sequence is strictly increasing; i.e, each item is greater +/// than the previous one +/// +/// \param first The start of the sequence to be tested. +/// \param last One past the end of the sequence +/// +/// \note This function will return false for sequences that contain items that compare +/// equal. If that is not what you intended, you should use is_increasing instead. + template <typename ForwardIterator> + bool is_strictly_increasing ( ForwardIterator first, ForwardIterator last ) + { + typedef typename std::iterator_traits<ForwardIterator>::value_type value_type; + return boost::algorithm::is_sorted (first, last, std::less_equal<value_type>()); + } + +/// \fn is_strictly_increasing ( const R &range ) +/// \return true if the entire sequence is strictly increasing; i.e, each item is greater +/// than the previous one +/// +/// \param range The range to be tested. +/// +/// \note This function will return false for sequences that contain items that compare +/// equal. If that is not what you intended, you should use is_increasing instead. + template <typename R> + bool is_strictly_increasing ( const R &range ) + { + return is_strictly_increasing ( boost::begin ( range ), boost::end ( range )); + } + + +/// \fn is_strictly_decreasing ( ForwardIterator first, ForwardIterator last ) +/// \return true if the entire sequence is strictly decreasing; i.e, each item is less than +/// the previous one +/// +/// \param first The start of the sequence to be tested. +/// \param last One past the end of the sequence +/// +/// \note This function will return false for sequences that contain items that compare +/// equal. If that is not what you intended, you should use is_decreasing instead. + template <typename ForwardIterator> + bool is_strictly_decreasing ( ForwardIterator first, ForwardIterator last ) + { + typedef typename std::iterator_traits<ForwardIterator>::value_type value_type; + return boost::algorithm::is_sorted (first, last, std::greater_equal<value_type>()); + } + +/// \fn is_strictly_decreasing ( const R &range ) +/// \return true if the entire sequence is strictly decreasing; i.e, each item is less than +/// the previous one +/// +/// \param range The range to be tested. +/// +/// \note This function will return false for sequences that contain items that compare +/// equal. If that is not what you intended, you should use is_decreasing instead. + template <typename R> + bool is_strictly_decreasing ( const R &range ) + { + return is_strictly_decreasing ( boost::begin ( range ), boost::end ( range )); + } + +}} // namespace boost + +#endif // BOOST_ALGORITHM_ORDERED_HPP |