]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |