123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312 |
- //----------------------------------------------------------------------------
- /// @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
|