diff options
Diffstat (limited to 'boost/move/algo/detail/bufferless_merge_sort.hpp')
-rw-r--r-- | boost/move/algo/detail/bufferless_merge_sort.hpp | 120 |
1 files changed, 0 insertions, 120 deletions
diff --git a/boost/move/algo/detail/bufferless_merge_sort.hpp b/boost/move/algo/detail/bufferless_merge_sort.hpp deleted file mode 100644 index a8e2763d7c..0000000000 --- a/boost/move/algo/detail/bufferless_merge_sort.hpp +++ /dev/null @@ -1,120 +0,0 @@ -////////////////////////////////////////////////////////////////////////////// -// -// (C) Copyright Ion Gaztanaga 2015-2016. -// 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_ALGO_BUFFERLESS_MERGE_SORT_HPP -#define BOOST_MOVE_ALGO_BUFFERLESS_MERGE_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/utility_core.hpp> -#include <boost/move/adl_move_swap.hpp> - -#include <boost/move/algo/move.hpp> -#include <boost/move/algo/detail/merge.hpp> - -#include <boost/move/detail/iterator_traits.hpp> -#include <boost/move/algo/detail/insertion_sort.hpp> -#include <cassert> - -namespace boost { -namespace movelib { -// @cond -namespace detail_bufferless_mergesort { - -static const std::size_t UnbufferedMergeSortInsertionSortThreshold = 16; - -//A in-placed version based on: -//Jyrki Katajainen, Tomi Pasanen, Jukka Teuhola. -//``Practical in-place mergesort''. Nordic Journal of Computing, 1996. - -template<class RandIt, class Compare> -void bufferless_merge_sort(RandIt first, RandIt last, Compare comp); - -template<class RandIt, class Compare> -void swap_sort(RandIt const first, RandIt const last, RandIt const buffer_first, RandIt const buffer_last, Compare comp, bool buffer_at_right) -{ - typedef typename iterator_traits<RandIt>::size_type size_type; - if (size_type(last - first) > UnbufferedMergeSortInsertionSortThreshold) { - RandIt m = first + (last - first) / 2; - bufferless_merge_sort(first, m, comp); - bufferless_merge_sort(m, last, comp); - if(buffer_at_right){ - //Use antistable to minimize movements (if equal, move first half elements - //to maximize the chance last half elements are already in place. - boost::movelib::swap_merge_right(first, m, last, buffer_last, boost::movelib::antistable<Compare>(comp)); - } - else{ - boost::movelib::swap_merge_left(buffer_first, first, m, last, comp); - } - } - else - boost::movelib::insertion_sort_swap(first, last, buffer_first, comp); -} - -template<class RandIt, class Compare> -void bufferless_merge_sort(RandIt const first, RandIt const last, Compare comp) -{ - typedef typename iterator_traits<RandIt>::size_type size_type; - size_type len = size_type(last - first); - if (len > size_type(UnbufferedMergeSortInsertionSortThreshold)) { - len /= 2; - RandIt h = last - len; //ceil(half) - RandIt f = h - len; //ceil(first) - swap_sort(f, h, h, last, comp, true); //[h, last) contains sorted elements - - //Divide unsorted first half in two - len = size_type(h - first); - while (len > size_type(UnbufferedMergeSortInsertionSortThreshold)) { - len /= 2; - RandIt n = h; //new end - h = n - len; //ceil(half') - f = h - len; //ceil(first') - swap_sort(h, n, f, h, comp, false); // the first half of the previous working area [f, h) - //contains sorted elements: working area in the middle [h, n) - //Now merge small (left) sorted with big (right) sorted (buffer is between them) - swap_merge_with_right_placed(f, h, h, n, last, comp); - } - - boost::movelib::insertion_sort(first, h, comp); - boost::movelib::merge_bufferless(first, h, last, comp); - } - else{ - boost::movelib::insertion_sort(first, last, comp); - } -} - -} //namespace detail_bufferless_mergesort { - -// @endcond - -//Unstable bufferless merge sort -template<class RandIt, class Compare> -void bufferless_merge_sort(RandIt first, RandIt last, Compare comp) -{ - detail_bufferless_mergesort::bufferless_merge_sort(first, last, comp); -} - -}} //namespace boost::movelib - -#include <boost/move/detail/config_end.hpp> - -#endif //#ifndef BOOST_MOVE_ALGO_BUFFERLESS_MERGE_SORT_HPP |