ceph/src/boost/libs/algorithm/include/boost/algorithm/sort_subrange.hpp

   1 /*
   2    Copyright (c) Marshall Clow 2008-2012.
   3
   4    Distributed under the Boost Software License, Version 1.0. (See accompanying
   5    file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   6
   7  Revision history:
   8    28 Sep 2015 mtc First version
   9
  10 */
  11
  12 /// \file sort_subrange.hpp
  13 /// \brief Sort a subrange
  14 /// \author Marshall Clow
  15 ///
  16 /// Suggested by Sean Parent in his CppCon 2015 keynote
  17
  18 #ifndef BOOST_ALGORITHM_SORT_SUBRANGE_HPP
  19 #define BOOST_ALGORITHM_SORT_SUBRANGE_HPP
  20
  21 #include <functional>       // For std::less
  22 #include <iterator>         // For std::iterator_traits
  23 #include <algorithm>        // For nth_element and partial_sort
  24
  25 #include <boost/range/begin.hpp>
  26 #include <boost/range/end.hpp>
  27
  28 namespace boost { namespace algorithm {
  29
  30 /// \fn sort_subrange ( T const& val,
  31 ///               Iterator first,     Iterator last,
  32 ///               Iterator sub_first, Iterator sub_last,
  33 ///               Pred p )
  34 /// \brief Sort the subrange [sub_first, sub_last) that is inside
  35 ///     the range [first, last) as if you had sorted the entire range.
  36 ///
  37 /// \param first       The start of the larger range
  38 /// \param last        The end of the larger range
  39 /// \param sub_first   The start of the sub range
  40 /// \param sub_last    The end of the sub range
  41 /// \param p           A predicate to use to compare the values.
  42 ///                        p ( a, b ) returns a boolean.
  43 ///
  44   template<typename Iterator, typename Pred>
  45   void sort_subrange (
  46         Iterator first,     Iterator last,
  47         Iterator sub_first, Iterator sub_last,
  48         Pred p)
  49   {
  50         if (sub_first == sub_last) return; // the empty sub-range is already sorted.
  51
  52         if (sub_first != first) { // sub-range is at the start, don't need to partition
  53                 (void) std::nth_element(first, sub_first, last, p);
  54                 ++sub_first;
  55                 }
  56         std::partial_sort(sub_first, sub_last, last, p);
  57   }
  58
  59
  60
  61   template<typename Iterator>
  62   void sort_subrange (Iterator first, Iterator last, Iterator sub_first, Iterator sub_last)
  63   {
  64         typedef typename std::iterator_traits<Iterator>::value_type value_type;
  65         return sort_subrange(first, last, sub_first, sub_last, std::less<value_type>());
  66   }
  67
  68 /// range versions?
  69
  70
  71 /// \fn partition_subrange ( T const& val,
  72 ///               Iterator first,     Iterator last,
  73 ///               Iterator sub_first, Iterator sub_last,
  74 ///               Pred p )
  75 /// \brief Gather the elements of the subrange [sub_first, sub_last) that is
  76 ///     inside the range [first, last) as if you had sorted the entire range.
  77 ///
  78 /// \param first       The start of the larger range
  79 /// \param last        The end of the larger range
  80 /// \param sub_first   The start of the sub range
  81 /// \param sub_last    The end of the sub range
  82 /// \param p           A predicate to use to compare the values.
  83 ///                        p ( a, b ) returns a boolean.
  84 ///
  85   template<typename Iterator, typename Pred>
  86   void partition_subrange (
  87         Iterator first,     Iterator last,
  88         Iterator sub_first, Iterator sub_last,
  89         Pred p)
  90   {
  91         if (sub_first != first) {
  92                 (void) std::nth_element(first, sub_first, last, p);
  93                 ++sub_first;
  94                 }
  95
  96         if (sub_last != last)
  97                 (void) std::nth_element(sub_first, sub_last, last, p);
  98   }
  99
 100   template<typename Iterator>
 101   void partition_subrange (Iterator first, Iterator last, Iterator sub_first, Iterator sub_last)
 102   {
 103         typedef typename std::iterator_traits<Iterator>::value_type value_type;
 104         return partition_subrange(first, last, sub_first, sub_last, std::less<value_type>());
 105   }
 106
 107 }}
 108
 109 #endif // BOOST_ALGORITHM_SORT_SUBRANGE_HPP