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

source code of boost/libs/sort/include/boost/sort/spreadsort/spreadsort.hpp