float_sort.hpp

Go to the documentation of this file.

//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 {


  /*!
  \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.
    \tparam RandomAccessIter <a href="http://www.cplusplus.com/reference/iterator/RandomAccessIterator/">Random access iterator</a>

    \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.
    \tparam RandomAccessIter <a href="http://www.cplusplus.com/reference/iterator/RandomAccessIterator/">Random access iterator</a>
    \tparam Right_shift Functor for right-shift by parameter @c shift bits.

    \param[in] first Iterator pointer to first element.
    \param[in] last Iterator pointing to one beyond the end of data.
    \param[in] rshift Number of bits to right-shift (using functor).

  */
  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.

   \tparam RandomAccessIter <a href="http://www.cplusplus.com/reference/iterator/RandomAccessIterator/">Random access iterator</a>
   \tparam Right_shift functor for right-shift by parameter @c shift bits.
   \tparam Comp To provide @c operator< for user-defined comparison.

   \param[in] first Iterator pointer to first element.
   \param[in] last Iterator pointing to one beyond the end of data.
   \param[in] rshift Number of bits to right-shift (using functor).
   \param[in] comp comparison functor.
  */

  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