ceph/src/boost/libs/sort/include/boost/sort/spreadsort/integer_sort.hpp

   1 //Templated Spreadsort-based implementation of integer_sort
   2
   3 //          Copyright Steven J. Ross 2001 - 2014.
   4 // Distributed under the Boost Software License, Version 1.0.
   5 //    (See accompanying file LICENSE_1_0.txt or copy at
   6 //          http://www.boost.org/LICENSE_1_0.txt)
   7
   8 // See http://www.boost.org/libs/sort/ for library home page.
   9
  10 /*
  11 Some improvements suggested by:
  12 Phil Endecott and Frank Gennari
  13
  14 Doxygen comments by Paul A. Bristow Jan 2015
  15
  16 */
  17
  18 #ifndef BOOST_INTEGER_SORT_HPP
  19 #define BOOST_INTEGER_SORT_HPP
  20 #include <algorithm>
  21 #include <vector>
  22 #include <cstring>
  23 #include <limits>
  24 #include <boost/static_assert.hpp>
  25 #include <boost/sort/spreadsort/detail/constants.hpp>
  26 #include <boost/sort/spreadsort/detail/integer_sort.hpp>
  27
  28 namespace boost {
  29 namespace sort {
  30 namespace spreadsort {
  31   //Top-level sorting call for integers.
  32
  33
  34 /*! \brief Integer sort algorithm using random access iterators.
  35   (All variants fall back to @c std::sort if the data size is too small, < @c detail::min_sort_size).
  36
  37   \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm,
  38 which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n
  39 Worst-case performance is <em>  O(N * (lg(range)/s + s)) </em>,
  40 so @c integer_sort is asymptotically faster
  41 than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11,
  42 so its worst-case with default settings for 32-bit integers is
  43 <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n
  44 Some performance plots of runtime vs. n and log(range) are provided:\n
  45    <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a>
  46    \n
  47    <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a>
  48
  49    \param[in] first Iterator pointer to first element.
  50    \param[in] last Iterator pointing to one beyond the end of data.
  51
  52    \pre [@c first, @c last) is a valid range.
  53    \pre @c RandomAccessIter @c value_type is mutable.
  54    \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a>
  55    \pre @c RandomAccessIter @c value_type supports the @c operator>>,
  56    which returns an integer-type right-shifted a specified number of bits.
  57    \post The elements in the range [@c first, @c last) are sorted in ascending order.
  58
  59    \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves),
  60    the right shift, subtraction of right-shifted elements, functors, or any operations on iterators throw.
  61
  62    \warning Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss.
  63    \warning Invalid arguments cause undefined behaviour.
  64    \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type,
  65    enabling faster generic-programming.
  66
  67    \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where:
  68    \remark  *  N is @c last - @c first,
  69    \remark  *  K is the log of the range in bits (32 for 32-bit integers using their full range),
  70    \remark  *  S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size).
  71
  72 */
  73   template <class RandomAccessIter>
  74   inline void integer_sort(RandomAccessIter first, RandomAccessIter last)
  75   {
  76     // Don't sort if it's too small to optimize.
  77     if (last - first < detail::min_sort_size)
  78       std::sort(first, last);
  79     else
  80       detail::integer_sort(first, last, *first >> 0);
  81   }
  82
  83 /*! \brief Integer sort algorithm using random access iterators with both right-shift and user-defined comparison operator.
  84   (All variants fall back to @c std::sort if the data size is too small, < @c detail::min_sort_size).
  85
  86   \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm,
  87 which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n
  88 Worst-case performance is <em>  O(N * (lg(range)/s + s)) </em>,
  89 so @c integer_sort is asymptotically faster
  90 than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11,
  91 so its worst-case with default settings for 32-bit integers is
  92 <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n
  93 Some performance plots of runtime vs. n and log(range) are provided:\n
  94    <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a>
  95    \n
  96    <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a>
  97
  98    \param[in] first Iterator pointer to first element.
  99    \param[in] last Iterator pointing to one beyond the end of data.
 100    \param[in] shift Functor that returns the result of shifting the value_type right a specified number of bits.
 101    \param[in] comp A binary functor that returns whether the first element passed to it should go before the second in order.
 102
 103    \pre [@c first, @c last) is a valid range.
 104    \pre @c RandomAccessIter @c value_type is mutable.
 105    \post The elements in the range [@c first, @c last) are sorted in ascending order.
 106
 107    \return @c void.
 108
 109    \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves),
 110    the right shift, subtraction of right-shifted elements, functors,
 111    or any operations on iterators throw.
 112
 113    \warning Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss.
 114    \warning Invalid arguments cause undefined behaviour.
 115    \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type,
 116    enabling faster generic-programming.
 117
 118    \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where:
 119    \remark  *  N is @c last - @c first,
 120    \remark  *  K is the log of the range in bits (32 for 32-bit integers using their full range),
 121    \remark  *  S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size).
 122 */
 123   template <class RandomAccessIter, class Right_shift, class Compare>
 124   inline void integer_sort(RandomAccessIter first, RandomAccessIter last,
 125                            Right_shift shift, Compare comp) {
 126     if (last - first < detail::min_sort_size)
 127       std::sort(first, last, comp);
 128     else
 129       detail::integer_sort(first, last, shift(*first, 0), shift, comp);
 130   }
 131
 132 /*! \brief Integer sort algorithm using random access iterators with just right-shift functor.
 133   (All variants fall back to @c std::sort if the data size is too small, < @c detail::min_sort_size).
 134
 135   \details @c integer_sort is a fast templated in-place hybrid radix/comparison algorithm,
 136 which in testing tends to be roughly 50% to 2X faster than @c std::sort for large tests (>=100kB).\n
 137
 138 \par Performance:
 139 Worst-case performance is <em>  O(N * (lg(range)/s + s)) </em>,
 140 so @c integer_sort is asymptotically faster
 141 than pure comparison-based algorithms. @c s is @c max_splits, which defaults to 11,
 142 so its worst-case with default settings for 32-bit integers is
 143 <em> O(N * ((32/11) </em> slow radix-based iterations fast comparison-based iterations).\n\n
 144 Some performance plots of runtime vs. n and log(range) are provided:\n
 145   * <a href="../../doc/graph/windows_integer_sort.htm"> windows_integer_sort</a>\n
 146   * <a href="../../doc/graph/osx_integer_sort.htm"> osx_integer_sort</a>
 147
 148    \param[in] first Iterator pointer to first element.
 149    \param[in] last Iterator pointing to one beyond the end of data.
 150    \param[in] shift A functor that returns the result of shifting the value_type right a specified number of bits.
 151
 152    \pre [@c first, @c last) is a valid range.
 153    \pre @c RandomAccessIter @c value_type is mutable.
 154    \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a>
 155    \post The elements in the range [@c first, @c last) are sorted in ascending order.
 156
 157    \throws std::exception Propagates exceptions if any of the element comparisons, the element swaps (or moves),
 158    the right shift, subtraction of right-shifted elements, functors,
 159    or any operations on iterators throw.
 160
 161    \warning Throwing an exception may cause data loss. This will also throw if a small vector resize throws, in which case there will be no data loss.
 162    \warning Invalid arguments cause undefined behaviour.
 163    \note @c spreadsort function provides a wrapper that calls the fastest sorting algorithm available for a data type,
 164    enabling faster generic-programming.
 165
 166    \remark The lesser of <em> O(N*log(N)) </em> comparisons and <em> O(N*log(K/S + S)) </em>operations worst-case, where:
 167    \remark  *  N is @c last - @c first,
 168    \remark  *  K is the log of the range in bits (32 for 32-bit integers using their full range),
 169    \remark  *  S is a constant called max_splits, defaulting to 11 (except for strings where it is the log of the character size).
 170
 171 */
 172   template <class RandomAccessIter, class Right_shift>
 173   inline void integer_sort(RandomAccessIter first, RandomAccessIter last,
 174                            Right_shift shift) {
 175     if (last - first < detail::min_sort_size)
 176       std::sort(first, last);
 177     else
 178       detail::integer_sort(first, last, shift(*first, 0), shift);
 179   }
 180 }
 181 }
 182 }
 183
 184 #endif
 185