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 ">#
0022 #if defined(BOOST_HAS_PRAGMA_ONCE)
0023 #  pragma once
0024 #endif
0025
0026 #include <boost/move/detail/config_begin.hpp>
0027
0028 #include <boost/move/detail/workaround.hpp>
0029 #include <boost/move/detail/iterator_traits.hpp>
0030 #include <boost/move/algo/detail/is_sorted.hpp>
0031 #include <boost/move/utility_core.hpp>
0032 #include <cassert>
0033
0034 #if defined(BOOST_CLANG) || (defined(BOOST_GCC) && (BOOST_GCC >= 40600))
0035 #pragma GCC diagnostic push
0036 #pragma GCC diagnostic ignored "-Wsign-conversion"
0037 #endif
0038
0039 namespace boost {  namespace movelib{
0040
0041 template <class RandomAccessIterator, class Compare>
0042 class heap_sort_helper
0043 {
0044    typedef typename boost::movelib::iter_size<RandomAccessIterator>::type  size_type;
0045    typedef typename boost::movelib::iterator_traits<RandomAccessIterator>::value_type value_type;
0046
0047    static void adjust_heap(RandomAccessIterator first, size_type hole_index, size_type const len, value_type &value, Compare comp)
0048    {
0049       size_type const top_index = hole_index;
0050       size_type second_child = size_type(2u*(hole_index + 1u));
0051
0052       while (second_child < len) {
0053          if (comp(*(first + second_child), *(first + size_type(second_child - 1u))))
0054             second_child--;
0055          *(first + hole_index) = boost::move(*(first + second_child));
0056          hole_index = second_child;
0057          second_child = size_type(2u * (second_child + 1u));
0058       }
0059       if (second_child == len) {
0060          *(first + hole_index) = boost::move(*(first + size_type(second_child - 1u)));
0061          hole_index = size_type(second_child - 1);
0062       }
0063
0064       {  //push_heap-like ending
0065          size_type parent = size_type((hole_index - 1u) / 2u);
0066          while (hole_index > top_index && comp(*(first + parent), value)) {
0067             *(first + hole_index) = boost::move(*(first + parent));
0068             hole_index = parent;
0069             parent = size_type((hole_index - 1u) / 2u);
0070          }
0071          *(first + hole_index) = boost::move(value);
0072       }
0073    }
0074
0075    static void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
0076    {
0077       size_type const len = size_type(last - first);
0078       if (len > 1) {
0079          size_type parent = size_type(len/2u - 1u);
0080
0081          do {
0082             value_type v(boost::move(*(first + parent)));
0083             adjust_heap(first, parent, len, v, comp);
0084          }while (parent--);
0085       }
0086    }
0087
0088    static void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
0089    {
0090       size_type len = size_type(last - first);
0091       while (len > 1) {
0092          //move biggest to the safe zone
0093          --last;
0094          value_type v(boost::move(*last));
0095          *last = boost::move(*first);
0096          adjust_heap(first, size_type(0), --len, v, comp);
0097       }
0098    }
0099
0100    public:
0101    static void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
0102    {
0103       make_heap(first, last, comp);
0104       sort_heap(first, last, comp);
0105       assert(boost::movelib::is_sorted(first, last, comp));
0106    }
0107 };
0108
0109 template <class RandomAccessIterator, class Compare>
0110 inline void heap_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
0111 {
0112    heap_sort_helper<RandomAccessIterator, Compare>::sort(first, last, comp);
0113 }
0114
0115 }} //namespace boost {  namespace movelib{
0116
0117 #if defined(BOOST_CLANG) || (defined(BOOST_GCC) && (BOOST_GCC >= 40600))
0118 #pragma GCC diagnostic pop
0119 #endif
0120
0121 #include <boost/move/detail/config_end.hpp>
0122
0123 #endif //#ifndef BOOST_MOVE_DETAIL_HEAP_SORT_HPP