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

   1 // Templated generic hybrid sorting
   2
   3 //          Copyright Steven J. Ross 2001 - 2009.
   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 float_mem_cast fix provided by:
  14 Scott McMurray
  15 */
  16
  17 #ifndef BOOST_SORT_SPREADSORT_HPP
  18 #define BOOST_SORT_SPREADSORT_HPP
  19 #include <algorithm>
  20 #include <vector>
  21 #include <cstring>
  22 #include <string>
  23 #include <limits>
  24 #include <boost/type_traits.hpp>
  25 #include <boost/sort/spreadsort/integer_sort.hpp>
  26 #include <boost/sort/spreadsort/float_sort.hpp>
  27 #include <boost/sort/spreadsort/string_sort.hpp>
  28
  29 namespace boost {
  30 namespace sort {
  31
  32 /*! Namespace for spreadsort sort variants for different data types.
  33 \note Use hyperlinks (coloured) to get detailed information about functions.
  34 */
  35 namespace spreadsort {
  36
  37   /*!
  38     \brief Generic @c spreadsort variant detecting integer-type elements so call to @c integer_sort.
  39     \details If the data type provided is an integer, @c integer_sort is used.
  40     \note Sorting other data types requires picking between @c integer_sort, @c float_sort and @c string_sort directly,
  41     as @c spreadsort won't accept types that don't have the appropriate @c type_traits.
  42     \param[in] first Iterator pointer to first element.
  43     \param[in] last Iterator pointing to one beyond the end of data.
  44
  45     \pre [@c first, @c last) is a valid range.
  46     \pre @c RandomAccessIter @c value_type is mutable.
  47     \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a>
  48     \pre @c RandomAccessIter @c value_type supports the @c operator>>,
  49     which returns an integer-type right-shifted a specified number of bits.
  50     \post The elements in the range [@c first, @c last) are sorted in ascending order.
  51   */
  52
  53   template <class RandomAccessIter>
  54   inline typename boost::enable_if_c< std::numeric_limits<
  55     typename std::iterator_traits<RandomAccessIter>::value_type >::is_integer,
  56     void >::type
  57   spreadsort(RandomAccessIter first, RandomAccessIter last)
  58   {
  59     integer_sort(first, last);
  60   }
  61
  62   /*!
  63     \brief Generic @c spreadsort variant detecting float element type so call to @c float_sort.
  64     \details If the data type provided is a float or castable-float, @c float_sort is used.
  65     \note Sorting other data types requires picking between @c integer_sort, @c float_sort and @c string_sort directly,
  66     as @c spreadsort won't accept types that don't have the appropriate @c type_traits.
  67
  68     \param[in] first Iterator pointer to first element.
  69     \param[in] last Iterator pointing to one beyond the end of data.
  70
  71     \pre [@c first, @c last) is a valid range.
  72     \pre @c RandomAccessIter @c value_type is mutable.
  73     \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a>
  74     \pre @c RandomAccessIter @c value_type supports the @c operator>>,
  75     which returns an integer-type right-shifted a specified number of bits.
  76     \post The elements in the range [@c first, @c last) are sorted in ascending order.
  77   */
  78
  79   template <class RandomAccessIter>
  80   inline typename boost::enable_if_c< !std::numeric_limits<
  81     typename std::iterator_traits<RandomAccessIter>::value_type >::is_integer
  82     && std::numeric_limits<
  83     typename std::iterator_traits<RandomAccessIter>::value_type >::is_iec559,
  84     void >::type
  85   spreadsort(RandomAccessIter first, RandomAccessIter last)
  86   {
  87     float_sort(first, last);
  88   }
  89
  90   /*!
  91     \brief  Generic @c spreadsort variant detecting string element type so call to @c string_sort for @c std::strings.
  92     \details If the data type provided is a string, @c string_sort is used.
  93     \note Sorting other data types requires picking between @c integer_sort, @c float_sort and @c string_sort directly,
  94     as @c spreadsort won't accept types that don't have the appropriate @c type_traits.
  95
  96     \param[in] first Iterator pointer to first element.
  97     \param[in] last Iterator pointing to one beyond the end of data.
  98
  99     \pre [@c first, @c last) is a valid range.
 100     \pre @c RandomAccessIter @c value_type is mutable.
 101     \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a>
 102     \pre @c RandomAccessIter @c value_type supports the @c operator>>,
 103     which returns an integer-type right-shifted a specified number of bits.
 104     \post The elements in the range [@c first, @c last) are sorted in ascending order.
 105   */
 106
 107   template <class RandomAccessIter>
 108   inline typename boost::enable_if_c<
 109     is_same<typename std::iterator_traits<RandomAccessIter>::value_type,
 110             typename std::string>::value, void >::type
 111   spreadsort(RandomAccessIter first, RandomAccessIter last)
 112   {
 113     string_sort(first, last);
 114   }
 115
 116   /*!
 117     \brief  Generic @c spreadsort variant detecting string element type so call to @c string_sort for @c std::wstrings.
 118     \details If the data type provided is a wstring, @c string_sort is used.
 119     \note Sorting other data types requires picking between @c integer_sort, @c float_sort and @c string_sort directly,
 120     as @c spreadsort won't accept types that don't have the appropriate @c type_traits.  Also, 2-byte wide-characters are the limit above which string_sort is inefficient, so on platforms with wider characters, this will not accept wstrings.
 121
 122     \param[in] first Iterator pointer to first element.
 123     \param[in] last Iterator pointing to one beyond the end of data.
 124
 125     \pre [@c first, @c last) is a valid range.
 126     \pre @c RandomAccessIter @c value_type is mutable.
 127     \pre @c RandomAccessIter @c value_type is <a href="http://en.cppreference.com/w/cpp/concept/LessThanComparable">LessThanComparable</a>
 128     \pre @c RandomAccessIter @c value_type supports the @c operator>>,
 129     which returns an integer-type right-shifted a specified number of bits.
 130     \post The elements in the range [@c first, @c last) are sorted in ascending order.
 131   */
 132   template <class RandomAccessIter>
 133   inline typename boost::enable_if_c<
 134     is_same<typename std::iterator_traits<RandomAccessIter>::value_type,
 135             typename std::wstring>::value &&
 136     sizeof(wchar_t) == 2, void >::type
 137   spreadsort(RandomAccessIter first, RandomAccessIter last)
 138   {
 139     boost::uint16_t unused = 0;
 140     string_sort(first, last, unused);
 141   }
 142 } // namespace spreadsort
 143 } // namespace sort
 144 } // namespace boost
 145
 146 #endif