| ////////////////////////////////////////////////////////////////////////////// |
| // |
| // (C) Copyright Ion Gaztanaga 2017-2018. |
| // 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/move for documentation. |
| // |
| ////////////////////////////////////////////////////////////////////////////// |
| |
| //! \file |
| |
| #ifndef BOOST_MOVE_DETAIL_HEAP_SORT_HPP |
| #define BOOST_MOVE_DETAIL_HEAP_SORT_HPP |
| |
| #ifndef BOOST_CONFIG_HPP |
| # include <boost/config.hpp> |
| #endif |
| # |
| #if defined(BOOST_HAS_PRAGMA_ONCE) |
| # pragma once |
| #endif |
| |
| #include <boost/move/detail/config_begin.hpp> |
| #include <boost/move/detail/workaround.hpp> |
| #include <boost/move/detail/iterator_traits.hpp> |
| #include <boost/move/algo/detail/is_sorted.hpp> |
| #include <boost/move/utility_core.hpp> |
| |
| namespace boost { namespace movelib{ |
| |
| template <class RandomAccessIterator, class Compare> |
| class heap_sort_helper |
| { |
| typedef typename boost::movelib::iterator_traits<RandomAccessIterator>::size_type size_type; |
| typedef typename boost::movelib::iterator_traits<RandomAccessIterator>::value_type value_type; |
| |
| static void adjust_heap(RandomAccessIterator first, size_type hole_index, size_type const len, value_type &value, Compare comp) |
| { |
| size_type const top_index = hole_index; |
| size_type second_child = 2 * (hole_index + 1); |
| |
| while (second_child < len) { |
| if (comp(*(first + second_child), *(first + (second_child - 1)))) |
| second_child--; |
| *(first + hole_index) = boost::move(*(first + second_child)); |
| hole_index = second_child; |
| second_child = 2 * (second_child + 1); |
| } |
| if (second_child == len) { |
| *(first + hole_index) = boost::move(*(first + (second_child - 1))); |
| hole_index = second_child - 1; |
| } |
| |
| { //push_heap-like ending |
| size_type parent = (hole_index - 1) / 2; |
| while (hole_index > top_index && comp(*(first + parent), value)) { |
| *(first + hole_index) = boost::move(*(first + parent)); |
| hole_index = parent; |
| parent = (hole_index - 1) / 2; |
| } |
| *(first + hole_index) = boost::move(value); |
| } |
| } |
| |
| static void make_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp) |
| { |
| size_type const len = size_type(last - first); |
| if (len > 1) { |
| size_type parent = len/2u - 1u; |
| |
| do { |
| value_type v(boost::move(*(first + parent))); |
| adjust_heap(first, parent, len, v, comp); |
| }while (parent--); |
| } |
| } |
| |
| static void sort_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp) |
| { |
| size_type len = size_type(last - first); |
| while (len > 1) { |
| //move biggest to the safe zone |
| --last; |
| value_type v(boost::move(*last)); |
| *last = boost::move(*first); |
| adjust_heap(first, size_type(0), --len, v, comp); |
| } |
| } |
| |
| public: |
| static void sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp) |
| { |
| make_heap(first, last, comp); |
| sort_heap(first, last, comp); |
| BOOST_ASSERT(boost::movelib::is_sorted(first, last, comp)); |
| } |
| }; |
| |
| template <class RandomAccessIterator, class Compare> |
| BOOST_MOVE_FORCEINLINE void heap_sort(RandomAccessIterator first, RandomAccessIterator last, Compare comp) |
| { |
| heap_sort_helper<RandomAccessIterator, Compare>::sort(first, last, comp); |
| } |
| |
| }} //namespace boost { namespace movelib{ |
| |
| #include <boost/move/detail/config_end.hpp> |
| |
| #endif //#ifndef BOOST_MOVE_DETAIL_HEAP_SORT_HPP |