diff options
Diffstat (limited to 'src/third_party/boost-1.69.0/boost/move/algo/detail/heap_sort.hpp')
-rw-r--r-- | src/third_party/boost-1.69.0/boost/move/algo/detail/heap_sort.hpp | 111 |
1 files changed, 111 insertions, 0 deletions
diff --git a/src/third_party/boost-1.69.0/boost/move/algo/detail/heap_sort.hpp b/src/third_party/boost-1.69.0/boost/move/algo/detail/heap_sort.hpp new file mode 100644 index 00000000000..5474d9f5c42 --- /dev/null +++ b/src/third_party/boost-1.69.0/boost/move/algo/detail/heap_sort.hpp @@ -0,0 +1,111 @@ +////////////////////////////////////////////////////////////////////////////// +// +// (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 |