summaryrefslogtreecommitdiff
path: root/boost/sort/spreadsort/float_sort.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/sort/spreadsort/float_sort.hpp')
-rw-r--r--boost/sort/spreadsort/float_sort.hpp134
1 files changed, 134 insertions, 0 deletions
diff --git a/boost/sort/spreadsort/float_sort.hpp b/boost/sort/spreadsort/float_sort.hpp
new file mode 100644
index 0000000..37966c2
--- /dev/null
+++ b/boost/sort/spreadsort/float_sort.hpp
@@ -0,0 +1,134 @@
+//Templated Spreadsort-based implementation of float_sort and float_mem_cast
+
+// Copyright Steven J. Ross 2001 - 2014.
+// Distributed under the Boost Software License, Version 1.0.
+// (See accompanying file LICENSE_1_0.txt or copy at
+// http://www.boost.org/LICENSE_1_0.txt)
+
+// See http://www.boost.org/libs/sort/ for library home page.
+
+/*
+Some improvements suggested by:
+Phil Endecott and Frank Gennari
+float_mem_cast fix provided by:
+Scott McMurray
+*/
+
+#ifndef BOOST_FLOAT_SORT_HPP
+#define BOOST_FLOAT_SORT_HPP
+#include <algorithm>
+#include <vector>
+#include <cstring>
+#include <limits>
+#include <boost/static_assert.hpp>
+#include <boost/sort/spreadsort/detail/constants.hpp>
+#include <boost/sort/spreadsort/detail/float_sort.hpp>
+
+namespace boost {
+namespace sort {
+namespace spreadsort {
+
+ /*!
+ \brief Casts a float to the specified integer type.
+
+ \tparam Data_type Floating-point IEEE 754/IEC559 type.
+ \tparam Cast_type Integer type (same size) to which to cast.
+
+ \par Example:
+ \code
+ struct rightshift {
+ int operator()(const DATA_TYPE &x, const unsigned offset) const {
+ return float_mem_cast<KEY_TYPE, CAST_TYPE>(x.key) >> offset;
+ }
+ };
+ \endcode
+ */
+ template<class Data_type, class Cast_type>
+ inline Cast_type
+ float_mem_cast(const Data_type & data)
+ {
+ // Only cast IEEE floating-point numbers, and only to a same-sized integer.
+ BOOST_STATIC_ASSERT(sizeof(Cast_type) == sizeof(Data_type));
+ BOOST_STATIC_ASSERT(std::numeric_limits<Data_type>::is_iec559);
+ BOOST_STATIC_ASSERT(std::numeric_limits<Cast_type>::is_integer);
+ Cast_type result;
+ std::memcpy(&result, &data, sizeof(Cast_type));
+ return result;
+ }
+
+
+ /*!
+ \brief @c float_sort with casting to the appropriate size.
+
+ \param[in] first Iterator pointer to first element.
+ \param[in] last Iterator pointing to one beyond the end of data.
+
+Some performance plots of runtime vs. n and log(range) are provided:\n
+ <a href="../../doc/graph/windows_float_sort.htm"> windows_float_sort</a>
+ \n
+ <a href="../../doc/graph/osx_float_sort.htm"> osx_float_sort</a>
+
+
+
+ \par A simple example of sorting some floating-point is:
+ \code
+ vector<float> vec;
+ vec.push_back(1.0);
+ vec.push_back(2.3);
+ vec.push_back(1.3);
+ spreadsort(vec.begin(), vec.end());
+ \endcode
+ \par The sorted vector contains ascending values "1.0 1.3 2.3".
+
+ */
+ template <class RandomAccessIter>
+ inline void float_sort(RandomAccessIter first, RandomAccessIter last)
+ {
+ if (last - first < detail::min_sort_size)
+ std::sort(first, last);
+ else
+ detail::float_sort(first, last);
+ }
+
+ /*!
+ \brief Floating-point sort algorithm using random access iterators with just right-shift functor.
+
+ \param[in] first Iterator pointer to first element.
+ \param[in] last Iterator pointing to one beyond the end of data.
+ \param[in] rshift Functor that returns the result of shifting the value_type right a specified number of bits.
+
+ */
+ template <class RandomAccessIter, class Right_shift>
+ inline void float_sort(RandomAccessIter first, RandomAccessIter last,
+ Right_shift rshift)
+ {
+ if (last - first < detail::min_sort_size)
+ std::sort(first, last);
+ else
+ detail::float_sort(first, last, rshift(*first, 0), rshift);
+ }
+
+
+ /*!
+ \brief Float sort algorithm using random access iterators with both right-shift and user-defined comparison operator.
+
+ \param[in] first Iterator pointer to first element.
+ \param[in] last Iterator pointing to one beyond the end of data.
+ \param[in] rshift Functor that returns the result of shifting the value_type right a specified number of bits.
+ \param[in] comp A binary functor that returns whether the first element passed to it should go before the second in order.
+ */
+
+ template <class RandomAccessIter, class Right_shift, class Compare>
+ inline void float_sort(RandomAccessIter first, RandomAccessIter last,
+ Right_shift rshift, Compare comp)
+ {
+ if (last - first < detail::min_sort_size)
+ std::sort(first, last, comp);
+ else
+ detail::float_sort(first, last, rshift(*first, 0), rshift, comp);
+ }
+}
+}
+}
+
+#endif