diff options
Diffstat (limited to 'boost/sort/flat_stable_sort')
| -rw-r--r-- | boost/sort/flat_stable_sort/flat_stable_sort.hpp | 312 |
1 files changed, 312 insertions, 0 deletions
diff --git a/boost/sort/flat_stable_sort/flat_stable_sort.hpp b/boost/sort/flat_stable_sort/flat_stable_sort.hpp new file mode 100644 index 0000000000..ee48e7b9a0 --- /dev/null +++ b/boost/sort/flat_stable_sort/flat_stable_sort.hpp @@ -0,0 +1,312 @@ +//---------------------------------------------------------------------------- +/// @file flat_stable_sort.hpp +/// @brief Flat stable sort algorithm +/// +/// @author Copyright (c) 2017 Francisco José Tapia (fjtapia@gmail.com )\n +/// Distributed under the Boost Software License, Version 1.0.\n +/// ( See accompanying file LICENSE_1_0.txt or copy at +/// http://www.boost.org/LICENSE_1_0.txt ) +/// @version 0.1 +/// +/// @remarks +//----------------------------------------------------------------------------- +#ifndef __BOOST_SORT_FLAT_STABLE_SORT_HPP +#define __BOOST_SORT_FLAT_STABLE_SORT_HPP + +#include <boost/sort/insert_sort/insert_sort.hpp> +#include <boost/sort/common/util/insert.hpp> +#include <boost/sort/common/merge_block.hpp> +#include <boost/sort/common/sort_basic.hpp> +#include <boost/sort/common/range.hpp> +#include <boost/sort/common/util/traits.hpp> +#include <boost/sort/common/indirect.hpp> + +#include <cstdlib> +#include <functional> +#include <iterator> +#include <memory> +#include <type_traits> +#include <vector> + +namespace boost +{ +namespace sort +{ +namespace flat_internal +{ +namespace bsc = boost::sort::common; +namespace bscu = boost::sort::common::util; +//--------------------------------------------------------------------------- +/// @struct flat_stable_sort +/// @brief This class implement s stable sort algorithm with 1 thread, with +/// an auxiliary memory of N/2 elements +//---------------------------------------------------------------------------- +template <class Iter_t, typename Compare = bscu::compare_iter<Iter_t>, + uint32_t Power2 = 10> +class flat_stable_sort: public bsc::merge_block<Iter_t, Compare, Power2> +{ + //------------------------------------------------------------------------ + // DEFINITIONS AND CONSTANTS + //------------------------------------------------------------------------ + typedef bsc::merge_block<Iter_t, Compare, Power2> merge_block_t; + + //------------------------------------------------------------------------- + // D E F I N I T I O N S + //------------------------------------------------------------------------- + typedef typename merge_block_t::value_t value_t; + typedef typename merge_block_t::range_pos range_pos; + typedef typename merge_block_t::range_it range_it; + typedef typename merge_block_t::range_buf range_buf; + typedef typename merge_block_t::it_index it_index; + typedef typename merge_block_t::circular_t circular_t; + + //------------------------------------------------------------------------ + // CONSTANTS + //------------------------------------------------------------------------ + using merge_block_t::BLOCK_SIZE; + using merge_block_t::LOG_BLOCK; + + using merge_block_t::index; + using merge_block_t::cmp; + using merge_block_t::ptr_circ; + + using merge_block_t::get_range; + using merge_block_t::get_group_range; + using merge_block_t::merge_range_pos; + using merge_block_t::move_range_pos_backward; + using merge_block_t::rearrange_with_index; + +public: + //------------------------------------------------------------------------ + // PUBLIC FUNCTIONS + //------------------------------------------------------------------------- + flat_stable_sort(Iter_t first, Iter_t last, Compare comp, + circular_t *ptr_circ) + : merge_block_t(first, last, comp, ptr_circ) + { + divide(index.begin(), index.end()); + rearrange_with_index(); + }; + + flat_stable_sort(Iter_t first, Iter_t last, Compare comp = Compare()) + : flat_stable_sort(first, last, comp, nullptr) { }; + + void divide(it_index itx_first, it_index itx_last); + + void sort_small(it_index itx_first, it_index itx_last); + + bool is_sorted_forward(it_index itx_first, it_index itx_last); + + bool is_sorted_backward(it_index itx_first, it_index itx_last); +}; +//---------------------------------------------------------------------------- +// End of class flat_stable_sort +//---------------------------------------------------------------------------- +// +//------------------------------------------------------------------------ +// function : +/// @brief : +/// @param Pos : +/// @return +//------------------------------------------------------------------------ +template <class Iter_t, typename Compare, uint32_t Power2> +void flat_stable_sort <Iter_t, Compare, Power2> +::divide(it_index itx_first, it_index itx_last) +{ + size_t nblock = size_t(itx_last - itx_first); + if (nblock < 5) + { sort_small(itx_first, itx_last); + return; + }; + if ( nblock > 7) + { if (is_sorted_forward(itx_first, itx_last)) return; + if (is_sorted_backward(itx_first, itx_last)) return; + }; + size_t nblock1 = (nblock + 1) >> 1; + divide(itx_first, itx_first + nblock1); + divide(itx_first + nblock1, itx_last); + merge_range_pos(itx_first, itx_first + nblock1, itx_last); +}; +// +//------------------------------------------------------------------------ +// function : sort_small +/// @brief : +/// @param +/// @param +/// @param +//------------------------------------------------------------------------ +template <class Iter_t, typename Compare, uint32_t Power2> +void flat_stable_sort <Iter_t, Compare, Power2> +::sort_small(it_index itx_first, it_index itx_last) +{ + size_t nblock = size_t(itx_last - itx_first); + assert(nblock > 0 and nblock < 5); + value_t *paux = ptr_circ->get_buffer(); + range_it rng_data = get_group_range(*itx_first, nblock); + + if (nblock < 3) + { + range_buf rng_aux(paux, paux + rng_data.size()); + range_sort_data(rng_data, rng_aux, cmp); + return; + }; + + //-------------------------------------------------------------------- + // division of range_data in two ranges for be sorted and merged + //-------------------------------------------------------------------- + size_t nblock1 = (nblock + 1) >> 1; + range_it rng_data1 = get_group_range(*itx_first, nblock1); + range_it rng_data2(rng_data1.last, rng_data.last); + range_buf rng_aux1(paux, paux + rng_data1.size()); + range_buf rng_aux2(paux, paux + rng_data2.size()); + + range_sort_data(rng_data2, rng_aux2, cmp); + range_sort_buffer(rng_data1, rng_aux1, cmp); + merge_half(rng_data, rng_aux1, rng_data2, cmp); +}; +// +//------------------------------------------------------------------------ +// function : is_sorted_forward +/// @brief : return if the data are ordered, +/// @param itx_first : iterator to the first block in the index +/// @param itx_last : iterator to the last block in the index +/// @return : true : the data are ordered false : not ordered +//------------------------------------------------------------------------ +template <class Iter_t, typename Compare, uint32_t Power2> +bool flat_stable_sort <Iter_t, Compare, Power2> +::is_sorted_forward(it_index itx_first, it_index itx_last) +{ + size_t nblock = size_t(itx_last - itx_first); + range_it rng = get_group_range(*itx_first, nblock); + size_t nelem = rng.size(); + size_t min_process = std::max(BLOCK_SIZE, (nelem >> 3)); + + size_t nsorted1 = bsc::number_stable_sorted_forward (rng.first, rng.last, + min_process, cmp); + if (nsorted1 == nelem) return true; + if (nsorted1 == 0) return false; + + size_t nsorted2 = nelem - nsorted1; + Iter_t itaux = rng.first + nsorted1; + if (nsorted2 <= (BLOCK_SIZE << 1)) + { + flat_stable_sort(itaux, rng.last, cmp, ptr_circ); + bscu::insert_sorted(rng.first, itaux, rng.last, cmp, + ptr_circ->get_buffer()); + } + else + { // Adjust the size of the sorted data to a number of blocks + size_t mask = ~(BLOCK_SIZE - 1); + size_t nsorted1_adjust = nsorted1 & mask; + flat_stable_sort(rng.first + nsorted1_adjust, rng.last, cmp, + ptr_circ); + size_t nblock1 = nsorted1_adjust >> Power2; + merge_range_pos(itx_first, itx_first + nblock1, itx_last); + }; + return true; +}; +// +//------------------------------------------------------------------------ +// function : is_sorted_backward +/// @brief : return if the data are ordered, +/// @param itx_first : iterator to the first block in the index +/// @param itx_last : iterator to the last block in the index +/// @return : true : the data are ordered false : not ordered +//------------------------------------------------------------------------ +template <class Iter_t, typename Compare, uint32_t Power2> +bool flat_stable_sort <Iter_t, Compare, Power2> +::is_sorted_backward(it_index itx_first, it_index itx_last) +{ + size_t nblock = size_t(itx_last - itx_first); + range_it rng = get_group_range(*itx_first, nblock); + + size_t nelem = rng.size(); + size_t min_process = std::max(BLOCK_SIZE, (nelem >> 3)); + + size_t nsorted2 = bsc::number_stable_sorted_backward(rng.first, rng.last, + min_process, cmp); + if (nsorted2 == nelem) return true; + if (nsorted2 == 0 ) return false; + Iter_t itaux = rng.last - nsorted2; + size_t nsorted1 = nelem - nsorted2; + + if (nsorted1 <= (BLOCK_SIZE << 1)) + { + flat_stable_sort(rng.first, itaux, cmp, ptr_circ); + bscu::insert_sorted_backward(rng.first, itaux, rng.last, cmp, + ptr_circ->get_buffer()); + } + else + { // Adjust the size of nsorted2 for to be a number of blocks + size_t nblock1 = (nsorted1 + BLOCK_SIZE - 1) >> Power2; + size_t nsorted1_adjust = (nblock1 << Power2); + flat_stable_sort(rng.first, rng.first + nsorted1_adjust, cmp, + ptr_circ); + merge_range_pos(itx_first, itx_first + nblock1, itx_last); + }; + return true; +}; +//**************************************************************************** +};// End namespace flat_internal +//**************************************************************************** +// +namespace bscu = boost::sort::common::util; +namespace flat = boost::sort::flat_internal; +// +///--------------------------------------------------------------------------- +// function flat_stable_sort +/// @brief This class is select the block size in the block_indirect_sort +/// algorithm depending of the type and size of the data to sort +/// +//---------------------------------------------------------------------------- +template <class Iter_t, class Compare = bscu::compare_iter<Iter_t>, + bscu::enable_if_string<value_iter<Iter_t> > * = nullptr> +inline void flat_stable_sort (Iter_t first, Iter_t last, + Compare cmp = Compare()) +{ + flat::flat_stable_sort<Iter_t, Compare, 6> (first, last, cmp); +}; + +template<size_t Size> +struct block_size_fss +{ + static constexpr const uint32_t BitsSize = + (Size == 0) ? 0 : (Size > 128) ? 7 : bscu::tmsb[Size - 1]; + static constexpr const uint32_t sz[10] = + { 10, 10, 10, 9, 8, 7, 6, 6 }; + static constexpr const uint32_t data = sz[BitsSize]; +}; + +// +///--------------------------------------------------------------------------- +// function flat_stable_sort +/// @brief This class is select the block size in the flat_stable_sort +/// algorithm depending of the type and size of the data to sort +/// +//---------------------------------------------------------------------------- +template <class Iter_t, class Compare = bscu::compare_iter<Iter_t>, + bscu::enable_if_not_string<value_iter<Iter_t> >* = nullptr> +inline void flat_stable_sort (Iter_t first, Iter_t last, + Compare cmp = Compare()) +{ + flat::flat_stable_sort<Iter_t, Compare, + block_size_fss<sizeof(value_iter<Iter_t> )>::data> + (first, last, cmp); +}; + +template<class Iter_t, class Compare = compare_iter<Iter_t> > +inline void indirect_flat_stable_sort (Iter_t first, Iter_t last, + Compare comp = Compare()) +{ + typedef typename std::vector<Iter_t>::iterator itx_iter; + typedef common::less_ptr_no_null<Iter_t, Compare> itx_comp; + common::indirect_sort ( flat_stable_sort<itx_iter, itx_comp>, + first, last, comp); +}; + +//**************************************************************************** +};// End namespace sort +};// End namepspace boost +//**************************************************************************** +// +#endif |