algo/detail/heap_sort.hpp

0001 //////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Ion Gaztanaga 2017-2018.
0004 // Distributed under the Boost Software License, Version 1.0.
0005 // (See accompanying file LICENSE_1_0.txt or copy at
0006 // http://www.boost.org/LICENSE_1_0.txt)
0007 //
0008 // See http://www.boost.org/libs/move for documentation.
0009 //
0010 //////////////////////////////////////////////////////////////////////////////
0011
0012 //! \file
0013
0014 #ifndef BOOST_MOVE_DETAIL_HEAP_SORT_HPP
0015 #define BOOST_MOVE_DETAIL_HEAP_SORT_HPP
0016
0017 #ifndef BOOST_CONFIG_HPP
0018 #  include <boost/config.hpp>
0019 #endif
0020 #
0021 #if defined(BOOST_HAS_PRAGMA_ONCE)
0022 #  pragma once
0023 #endif
0024
0025 #include <boost/move/detail/config_begin.hpp>
0026
0027 #include <boost/move/detail/workaround.hpp>
0028 #include <boost/move/detail/iterator_traits.hpp>
0029 #include <boost/move/algo/detail/is_sorted.hpp>
0030 #include <boost/move/utility_core.hpp>
0031 #include <cassert>
0032
0033 #if defined(BOOST_CLANG) || (defined(BOOST_GCC) && (BOOST_GCC >= 40600))
0034 #pragma GCC diagnostic push
0035 #pragma GCC diagnostic ignored "-Wsign-conversion"
0036 #endif
0037
0038 namespace boost {  namespace movelib{
0039
0040 template <class RandomAccessIterator, class Compare>
0041 class heap_sort_helper
0042 {
0043    typedef typename boost::movelib::iter_size<RandomAccessIterator>::type  size_type;
0044    typedef typename boost::movelib::iterator_traits<RandomAccessIterator>::value_type value_type;
0045
0046    static void adjust_heap(RandomAccessIterator first, size_type hole_index, size_type const len, value_type &value, Compare comp)
0047    {
0048       size_type const top_index = hole_index;
0049       size_type second_child = size_type(2u*(hole_index + 1u));
0050
0051       while (second_child < len) {
0052          if (comp(*(first + second_child), *(first + size_type(second_child - 1u))))
0053             second_child--;
0054          *(first + hole_index) = boost::move(*(first + second_child));
0055          hole_index = second_child;
0056          second_child = size_type(2u * (second_child + 1u));
0057       }
0058       if (second_child == len) {
0059          *(first + hole_index) = boost::move(*(first + size_type(second_child - 1u)));
0060          hole_index = size_type(second_child - 1);
0061       }
0062
0063       {  //push_heap-like ending
0064          size_type parent = size_type((hole_index - 1u) / 2u);
0065          while (hole_index > top_index && comp(*(first + parent), value)) {
0066             *(first + hole_index) = boost::move(*(first + parent));
0067             hole_index = parent;
0068             parent = size_type((hole_index - 1u) / 2u);
0069          }
0070          *(first + hole_index) = boost::move(value);
0071       }
0072    }
0073
0074    static void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
0075    {
0076       size_type const len = size_type(last - first);
0077       if (len > 1) {
0078          size_type parent = size_type(len/2u - 1u);
0079
0080          do {
0081             value_type v(boost::move(*(first + parent)));
0082             adjust_heap(first, parent, len, v, comp);
0083          }while (parent--);
0084       }
0085    }
0086
0087    static void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
0088    {
0089       size_type len = size_type(last - first);
0090       while (len > 1) {
0091          //move biggest to the safe zone
0092          --last;
0093          value_type v(boost::move(*last));
0094          *last = boost::move(*first);
0095          adjust_heap(first, size_type(0), --len, v, comp);
0096       }
0097    }
0098
0099    public:
0100    static void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
0101    {
0102       make_heap(first, last, comp);
0103       sort_heap(first, last, comp);
0104       assert(boost::movelib::is_sorted(first, last, comp));
0105    }
0106 };
0107
0108 template <class RandomAccessIterator, class Compare>
0109 BOOST_MOVE_FORCEINLINE void heap_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
0110 {
0111    heap_sort_helper<RandomAccessIterator, Compare>::sort(first, last, comp);
0112 }
0113
0114 }} //namespace boost {  namespace movelib{
0115
0116 #if defined(BOOST_CLANG) || (defined(BOOST_GCC) && (BOOST_GCC >= 40600))
0117 #pragma GCC diagnostic pop
0118 #endif
0119
0120 #include <boost/move/detail/config_end.hpp>
0121
0122 #endif //#ifndef BOOST_MOVE_DETAIL_HEAP_SORT_HPP