text: //----------------------------------------------------------------------------
  /// @file block_indirect_sort.hpp
  /// @brief block indirect sort algorithm
  ///
  /// @author Copyright (c) 2016 Francisco Jose 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_PARALLEL_DETAIL_BLOCK_INDIRECT_SORT_HPP
  #define __BOOST_SORT_PARALLEL_DETAIL_BLOCK_INDIRECT_SORT_HPP
  
  #include <atomic>
  #include <boost/sort/block_indirect_sort/blk_detail/merge_blocks.hpp>
  #include <boost/sort/block_indirect_sort/blk_detail/move_blocks.hpp>
  #include <boost/sort/block_indirect_sort/blk_detail/parallel_sort.hpp>
  #include <boost/sort/pdqsort/pdqsort.hpp>
  #include <boost/sort/common/util/traits.hpp>
  #include <boost/sort/common/util/algorithm.hpp>
  #include <future>
  #include <iterator>
  
  // This value is the minimal number of threads for to use the
  // block_indirect_sort algorithm
  #define BOOST_NTHREAD_BORDER 6
  
  namespace boost
  {
  namespace sort
  {
  namespace blk_detail
  {
  //---------------------------------------------------------------------------
  //         USING SENTENCES
  //---------------------------------------------------------------------------
  namespace bs = boost::sort;
  namespace bsc = bs::common;
  namespace bscu = bsc::util;
  using bscu::compare_iter;
  using bscu::value_iter;
  using bsc::range;
  using bsc::destroy;
  using bsc::initialize;
  using bscu::nbits64;
  using bs::pdqsort;
  using bscu::enable_if_string;
  using bscu::enable_if_not_string;
  using bscu::tmsb;
  //
  ///---------------------------------------------------------------------------
  /// @struct block_indirect_sort
  /// @brief This class is the entry point of the block indirect sort. The code
  ///        of this algorithm is divided in several classes:
  ///        bis/block.hpp : basic structures used in the algorithm
  ///        bis/backbone.hpp : data used by all the classes
  ///        bis/merge_blocks.hpp : merge the internal blocks
  ///        bis/move_blocks.hpp : move the blocks, and obtain all the elements
  ///                              phisicaly sorted
  ///        bis/parallel_sort.hpp : make the parallel sort of each part in the
  ///                                initial division of the data
  ///
  //----------------------------------------------------------------------------
  template<uint32_t Block_size, uint32_t Group_size, class Iter_t,
                  class Compare = compare_iter<Iter_t> >
  struct block_indirect_sort
  {
      //------------------------------------------------------------------------
      //                  D E F I N I T I O N S
      //------------------------------------------------------------------------
      typedef typename std::iterator_traits<Iter_t>::value_type value_t;
      typedef std::atomic<uint32_t> atomic_t;
      typedef range<size_t> range_pos;
      typedef range<Iter_t> range_it;
      typedef range<value_t *> range_buf;
      typedef std::function<void(void)> function_t;
  
      // classes used in the internal operations of the algorithm
      typedef block_pos block_pos_t;
      typedef block<Block_size, Iter_t> block_t;
      typedef backbone<Block_size, Iter_t, Compare> backbone_t;
      typedef parallel_sort<Block_size, Iter_t, Compare> parallel_sort_t;
  
      typedef merge_blocks<Block_size, Group_size, Iter_t, Compare> merge_blocks_t;
      typedef move_blocks<Block_size, Group_size, Iter_t, Compare> move_blocks_t;
      typedef compare_block_pos<Block_size, Iter_t, Compare> compare_block_pos_t;
      //
      //------------------------------------------------------------------------
      //       V A R I A B L E S   A N D  C O N S T A N T S
      //------------------------------------------------------------------------
      // contains the data and the internal data structures of the algorithm for
      // to be shared between the classes which are part of the algorithm
      backbone_t bk;
      // atomic counter for to detect the end of the works created inside
      // the object
      atomic_t counter;
      // pointer to the uninitialized memory used for the thread buffers
      value_t *ptr;
      // indicate if the memory pointed by ptr is initialized
      bool construct;
      // range from extract the buffers for the threads
      range_buf rglobal_buf;
      // number of threads to use
      uint32_t nthread;
      //
      //------------------------------------------------------------------------
      //                F U N C T I O N S
      //------------------------------------------------------------------------
  
      block_indirect_sort(Iter_t first, Iter_t last, Compare cmp, uint32_t nthr);
  
      block_indirect_sort(Iter_t first, Iter_t last) :
                          block_indirect_sort(first, last, Compare(),
                          std::thread::hardware_concurrency()) { }
  
  
      block_indirect_sort(Iter_t first, Iter_t last, Compare cmp) :
                          block_indirect_sort(first, last, cmp,
                          std::thread::hardware_concurrency()) { }
  
  
      block_indirect_sort(Iter_t first, Iter_t last, uint32_t nthread) :
                          block_indirect_sort(first, last, Compare(), nthread){}
  
  
      //
      //------------------------------------------------------------------------
      //  function :destroy_all
      /// @brief destructor all the data structures of the class (if the memory
      ///        is constructed, is destroyed) and  return the uninitialized
      ///        memory
      //------------------------------------------------------------------------
      void destroy_all(void)
      {
          if (ptr != nullptr)
          {
              if (construct)
              {
                  destroy(rglobal_buf);
                  construct = false;
              };
              std::return_temporary_buffer(ptr);
              ptr = nullptr;
          };
      }
      //
      //------------------------------------------------------------------------
      //  function :~block_indirect_sort
      /// @brief destructor of the class (if the memory is constructed, is
      ///        destroyed) and  return the uninitialized memory
      //------------------------------------------------------------------------
      ~block_indirect_sort(void)
      {
          destroy_all();
      }
  
      void split_range(size_t pos_index1, size_t pos_index2,
                      uint32_t level_thread);
  
      void start_function(void);
  
  //-------------------------------------------------------------------------
  }; // End class block_indirect_sort
  //----------------------------------------------------------------------------
  //
  //############################################################################
  //                                                                          ##
  //                                                                          ##
  //            N O N     I N L I N E      F U N C T I O N S                  ##
  //                                                                          ##
  //                                                                          ##
  //############################################################################
  //
  //-------------------------------------------------------------------------
  //  function : block_indirect_sort
  /// @brief begin with the execution of the functions stored in works
  /// @param first : iterator to the first element of the range to sort
  /// @param last : iterator after the last element to the range to sort
  /// @param comp : object for to compare two elements pointed by Iter_t
  ///               iterators
  /// @param nthr : Number of threads to use in the process.When this value
  ///               is lower than 2, the sorting is done with 1 thread
  //-------------------------------------------------------------------------
  template<uint32_t Block_size, uint32_t Group_size, class Iter_t, class Compare>
  block_indirect_sort<Block_size, Group_size, Iter_t, Compare>
  ::block_indirect_sort(Iter_t first, Iter_t last, Compare cmp, uint32_t nthr)
  : bk(first, last, cmp), counter(0), ptr(nullptr), construct(false),
    nthread(nthr)
  {
      try
      {
          assert((last - first) >= 0);
          size_t nelem = size_t(last - first);
          if (nelem == 0) return;
  
          //------------------- check if sort -----------------------------------
          bool sorted = true;
          for (Iter_t it1 = first, it2 = first + 1; it2 != last and (sorted =
                          not bk.cmp(*it2, *it1)); it1 = it2++);
          if (sorted) return;
  
          //------------------- check if reverse sort ---------------------------
          sorted = true;
          for (Iter_t it1 = first, it2 = first + 1; it2 != last and (sorted =
                          not bk.cmp(*it1, *it2)); it1 = it2++);
  
          if (sorted)
          {
              size_t nelem2 = nelem >> 1;
              Iter_t it1 = first, it2 = last - 1;
              for (size_t i = 0; i < nelem2; ++i)
              {
                  std::swap(*(it1++), *(it2--));
              };
              return;
          };
  
          //---------------- check if only single thread -----------------------
          size_t nthreadmax = nelem / (Block_size * Group_size) + 1;
          if (nthread > nthreadmax) nthread = (uint32_t) nthreadmax;
  
          uint32_t nbits_size = (nbits64(sizeof(value_t)) >> 1);
          if (nbits_size > 5) nbits_size = 5;
          size_t max_per_thread = 1 << (18 - nbits_size);
  
          if (nelem < (max_per_thread) or nthread < 2)
          {
              //intro_sort (first, last, bk.cmp);
              pdqsort(first, last, bk.cmp);
              return;
          };
  
          //----------- creation of the temporary buffer --------------------
          ptr = std::get_temporary_buffer<value_t>(Block_size * nthread).first;
          if (ptr == nullptr)
          {
              bk.error = true;
              throw std::bad_alloc();
          };
  
          rglobal_buf = range_buf(ptr, ptr + (Block_size * nthread));
          initialize(rglobal_buf, *first);
          construct = true;
  
          // creation of the buffers for the threads
          std::vector<value_t *> vbuf(nthread);
          for (uint32_t i = 0; i < nthread; ++i)
          {
              vbuf[i] = ptr + (i * Block_size);
          };
  
          // Insert the first work in the stack
          bscu::atomic_write(counter, 1);
          function_t f1 = [&]( )
          {
              start_function ( );
              bscu::atomic_sub (counter, 1);
          };
          bk.works.emplace_back(f1);
  
          //---------------------------------------------------------------------
          //                    PROCESS
          //---------------------------------------------------------------------
          std::vector<std::future<void> > vfuture(nthread);
  
          // The function launched with the futures is "execute the functions of
          // the stack until this->counter is zero
          // vbuf[i] is the memory from the main thread for to configure the
          // thread local buffer
          for (uint32_t i = 0; i < nthread; ++i)
          {
              auto f1 = [=, &vbuf]( )
              {   bk.exec (vbuf[i], this->counter);};
              vfuture[i] = std::async(std::launch::async, f1);
          };
          for (uint32_t i = 0; i < nthread; ++i)
              vfuture[i].get();
          if (bk.error) throw std::bad_alloc();
      }
      catch (std::bad_alloc &)
      {
          destroy_all();
          throw;
      }
  };
  //
  //-----------------------------------------------------------------------------
  //  function : split_rage
  /// @brief this function splits a range of positions in the index, and
  ///        depending of the size, sort directly or make to a recursive call
  ///        to split_range
  /// @param pos_index1 : first position in the index
  /// @param pos_index2 : position after the last in the index
  /// @param level_thread : depth of the call. When 0 sort the blocks
  //-----------------------------------------------------------------------------
  template<uint32_t Block_size, uint32_t Group_size, class Iter_t, class Compare>
  void block_indirect_sort<Block_size, Group_size, Iter_t, Compare>
  ::split_range(size_t pos_index1, size_t pos_index2, uint32_t level_thread)
  {
      size_t nblock = pos_index2 - pos_index1;
  
      //-------------------------------------------------------------------------
      // In the blocks not sorted, the physical position is the logical position
      //-------------------------------------------------------------------------
      Iter_t first = bk.get_block(pos_index1).first;
      Iter_t last = bk.get_range(pos_index2 - 1).last;
  
      if (nblock < Group_size)
      {
          pdqsort(first, last, bk.cmp);
          return;
      };
  
      size_t pos_index_mid = pos_index1 + (nblock >> 1);
      atomic_t son_counter(1);
  
      //-------------------------------------------------------------------------
      // Insert in the stack the work for the second part, and the actual thread,
      // execute the first part
      //-------------------------------------------------------------------------
      if (level_thread != 0)
      {
          auto f1 = [=, &son_counter]( )
          {
              split_range (pos_index_mid, pos_index2, level_thread - 1);
              bscu::atomic_sub (son_counter, 1);
          };
          bk.works.emplace_back(f1);
          if (bk.error) return;
          split_range(pos_index1, pos_index_mid, level_thread - 1);
      }
      else
      {
          Iter_t mid = first + ((nblock >> 1) * Block_size);
          auto f1 = [=, &son_counter]( )
          {
              parallel_sort_t (bk, mid, last);
              bscu::atomic_sub (son_counter, 1);
          };
          bk.works.emplace_back(f1);
          if (bk.error) return;
          parallel_sort_t(bk, first, mid);
      };
      bk.exec(son_counter);
      if (bk.error) return;
      merge_blocks_t(bk, pos_index1, pos_index_mid, pos_index2);
  };
  
  //
  //-----------------------------------------------------------------------------
  //  function : start_function
  /// @brief this function init the process. When the number of threads is lower
  ///        than a predefined value, sort the elements with a parallel pdqsort.
  //-----------------------------------------------------------------------------
  template<uint32_t Block_size, uint32_t Group_size, class Iter_t, class Compare>
  void block_indirect_sort<Block_size, Group_size, Iter_t, Compare>
  ::start_function(void)
  {
      if (nthread < BOOST_NTHREAD_BORDER)
      {
          parallel_sort_t(bk, bk.global_range.first, bk.global_range.last);
      }
      else
      {
          size_t level_thread = nbits64(nthread - 1) - 1;
          split_range(0, bk.nblock, level_thread - 1);
          if (bk.error) return;
          move_blocks_t k(bk);
      };
  };
  
  ///---------------------------------------------------------------------------
  //  function block_indirect_sort_call
  /// @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,
           enable_if_string<value_iter<Iter_t>> * = nullptr>
  inline void block_indirect_sort_call(Iter_t first, Iter_t last, Compare cmp,
                  uint32_t nthr)
  {
      block_indirect_sort<128, 128, Iter_t, Compare>(first, last, cmp, nthr);
  };
  
  template<size_t Size>
  struct block_size
  {
      static constexpr const uint32_t BitsSize =
                      (Size == 0) ? 0 : (Size > 256) ? 9 : tmsb[Size - 1];
      static constexpr const uint32_t sz[10] =
      { 4096, 4096, 4096, 4096, 2048, 1024, 768, 512, 256, 128 };
      static constexpr const uint32_t data = sz[BitsSize];
  };
  //
  ///---------------------------------------------------------------------------
  /// @struct block_indirect_sort_call
  /// @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,
            enable_if_not_string<value_iter<Iter_t>> * = nullptr>
  inline void block_indirect_sort_call (Iter_t first, Iter_t last, Compare cmp,
                                        uint32_t nthr)
  {
      block_indirect_sort<block_size<sizeof (value_iter<Iter_t> )>::data, 64,
                          Iter_t, Compare> (first, last, cmp, nthr);
  };
  
  //
  //****************************************************************************
  }; //    End namespace blk_detail
  //****************************************************************************
  //
  namespace bscu = boost::sort::common::util;
  //
  //############################################################################
  //                                                                          ##
  //                                                                          ##
  //               B L O C K _ I N D I R E C T _ S O R T                      ##
  //                                                                          ##
  //                                                                          ##
  //############################################################################
  //
  //-----------------------------------------------------------------------------
  //  function : block_indirect_sort
  /// @brief parallel sample sort  algorithm (stable sort)
  ///
  /// @param first : iterator to the first element of the range to sort
  /// @param last : iterator after the last element to the range to sort
  //-----------------------------------------------------------------------------
  template<class Iter_t>
  void block_indirect_sort(Iter_t first, Iter_t last)
  {
      typedef bscu::compare_iter<Iter_t> Compare;
      blk_detail::block_indirect_sort_call (first, last, Compare(),
                                            std::thread::hardware_concurrency());
  }
  
  //
  //-----------------------------------------------------------------------------
  //  function : block_indirect_sort
  /// @brief parallel sample sort  algorithm (stable sort)
  ///
  /// @param first : iterator to the first element of the range to sort
  /// @param last : iterator after the last element to the range to sort
  /// @param nthread : Number of threads to use in the process. When this value
  ///                  is lower than 2, the sorting is done with 1 thread
  //-----------------------------------------------------------------------------
  template<class Iter_t>
  void block_indirect_sort(Iter_t first, Iter_t last, uint32_t nthread)
  {
      typedef bscu::compare_iter<Iter_t> Compare;
      blk_detail::block_indirect_sort_call(first, last, Compare(), nthread);
  }
  //
  //-----------------------------------------------------------------------------
  //  function : block_indirect_sort
  /// @brief parallel sample sort  algorithm (stable sort)
  ///
  /// @param first : iterator to the first element of the range to sort
  /// @param last : iterator after the last element to the range to sort
  /// @param comp : object for to compare two elements pointed by Iter_t
  ///               iterators
  //-----------------------------------------------------------------------------
  template <class Iter_t, class Compare,
            bscu::enable_if_not_integral<Compare> * = nullptr>
  void block_indirect_sort(Iter_t first, Iter_t last, Compare comp)
  {
      blk_detail::block_indirect_sort_call (first, last, comp,
                                        std::thread::hardware_concurrency());
  }
  
  //
  //-----------------------------------------------------------------------------
  //  function : block_indirect_sort
  /// @brief parallel sample sort  algorithm (stable sort)
  ///
  /// @param first : iterator to the first element of the range to sort
  /// @param last : iterator after the last element to the range to sort
  /// @param comp : object for to compare two elements pointed by Iter_t
  ///               iterators
  /// @param nthread : Number of threads to use in the process. When this value
  ///                  is lower than 2, the sorting is done with 1 thread
  //-----------------------------------------------------------------------------
  template<class Iter_t, class Compare>
  void block_indirect_sort (Iter_t first, Iter_t last, Compare comp,
                            uint32_t nthread)
  {
      blk_detail::block_indirect_sort_call(first, last, comp, nthread);
  }
  //
  //****************************************************************************
  }; //    End namespace sort
  }; //    End namespace boost
  //****************************************************************************
  //
  #endif
  