summaryrefslogtreecommitdiff
path: root/boost/sort/common
diff options
context:
space:
mode:
Diffstat (limited to 'boost/sort/common')
-rw-r--r--boost/sort/common/deque_cnc.hpp366
-rw-r--r--boost/sort/common/file_vector.hpp272
-rw-r--r--boost/sort/common/indirect.hpp153
-rw-r--r--boost/sort/common/int_array.hpp75
-rw-r--r--boost/sort/common/merge_block.hpp418
-rw-r--r--boost/sort/common/merge_four.hpp327
-rw-r--r--boost/sort/common/merge_vector.hpp196
-rw-r--r--boost/sort/common/pivot.hpp122
-rw-r--r--boost/sort/common/range.hpp399
-rw-r--r--boost/sort/common/rearrange.hpp168
-rw-r--r--boost/sort/common/scheduler.hpp276
-rw-r--r--boost/sort/common/sort_basic.hpp334
-rw-r--r--boost/sort/common/spinlock.hpp88
-rw-r--r--boost/sort/common/stack_cnc.hpp142
-rw-r--r--boost/sort/common/time_measure.hpp62
-rw-r--r--boost/sort/common/util/algorithm.hpp309
-rw-r--r--boost/sort/common/util/atomic.hpp98
-rw-r--r--boost/sort/common/util/circular_buffer.hpp572
-rw-r--r--boost/sort/common/util/insert.hpp142
-rw-r--r--boost/sort/common/util/merge.hpp494
-rw-r--r--boost/sort/common/util/search.hpp529
-rw-r--r--boost/sort/common/util/traits.hpp123
22 files changed, 5665 insertions, 0 deletions
diff --git a/boost/sort/common/deque_cnc.hpp b/boost/sort/common/deque_cnc.hpp
new file mode 100644
index 0000000000..eb3b31ee6a
--- /dev/null
+++ b/boost/sort/common/deque_cnc.hpp
@@ -0,0 +1,366 @@
+//----------------------------------------------------------------------------
+/// @file deque_cnc.hpp
+/// @brief This file contains the implementation of the several types of
+/// recursive fastmutex for read and write
+///
+/// @author Copyright (c) 2010 2015 Francisco José Tapia (fjtapia@gmail.com )\n
+/// Distributed under the Boost Software License, Version 1.0.\n
+/// ( See accompanyingfile LICENSE_1_0.txt or copy at
+/// http://www.boost.org/LICENSE_1_0.txt )
+/// @version 0.1
+///
+/// @remarks
+//-----------------------------------------------------------------------------
+#ifndef __TOOLS_DEQUE_CNC_HPP
+#define __TOOLS_DEQUE_CNC_HPP
+
+#include <sort/tools/spinlock.hpp>
+#include <vector>
+#include <deque>
+
+namespace sort
+{
+namespace tools
+{
+
+//###########################################################################
+// ##
+// ################################################################ ##
+// # # ##
+// # C L A S S # ##
+// # S T A C K _ C N C # ##
+// # # ##
+// ################################################################ ##
+// ##
+//###########################################################################
+//
+//---------------------------------------------------------------------------
+/// @class deque_cnc
+/// @brief This class is a concurrent stack controled by a spin_lock
+/// @remarks
+//---------------------------------------------------------------------------
+template<typename T, typename Allocator = std::allocator<T> >
+class deque_cnc
+{
+public:
+ //-----------------------------------------------------------------------
+ // D E F I N I T I O N S
+ //-----------------------------------------------------------------------
+ typedef std::deque<T, Allocator> deque_t;
+ typedef typename deque_t::size_type size_type;
+ typedef typename deque_t::difference_type difference_type;
+ typedef typename deque_t::value_type value_type;
+ typedef typename deque_t::pointer pointer;
+ typedef typename deque_t::const_pointer const_pointer;
+ typedef typename deque_t::reference reference;
+ typedef typename deque_t::const_reference const_reference;
+ typedef typename deque_t::allocator_type allocator_type;
+
+protected:
+ //------------------------------------------------------------------------
+ // VARIABLES
+ //------------------------------------------------------------------------
+ deque_t dq;
+ mutable spinlock spl;
+
+public:
+ //
+ //-----------------------------------------------------------------------
+ // C O N S T R U C T O R S A N D D E S T R U C T O R
+ //-----------------------------------------------------------------------
+ //
+ //-----------------------------------------------------------------------
+ // function : deque_cnc
+ /// @brief constructor
+ //----------------------------------------------------------------------
+ explicit inline deque_cnc(void): dq() { };
+//
+ //----------------------------------------------------------------------
+ // function : deque_cnc
+ /// @brief constructor
+ /// @param [in] ALLC : Allocator
+ //----------------------------------------------------------------------
+ explicit inline deque_cnc(const Allocator &ALLC): dq(ALLC){ };
+ //
+ //----------------------------------------------------------------------
+ // function : ~deque_cnc
+ /// @brief Destructor
+ //----------------------------------------------------------------------
+ virtual ~deque_cnc(void){ dq.clear(); };
+ //
+ //----------------------------------------------------------------------
+ // function : clear
+ /// @brief Delete all the elements of the deque_cnc.
+ //----------------------------------------------------------------------
+ void clear(void)
+ {
+ std::lock_guard < spinlock > S(spl);
+ dq.clear();
+ };
+ //
+ //------------------------------------------------------------------------
+ // function : swap
+ /// @brief swap the data between the two deque_cnc
+ /// @param [in] A : deque_cnc to swap
+ /// @return none
+ //-----------------------------------------------------------------------
+ void swap(deque_cnc & A) noexcept
+ {
+ if (this == &A) return;
+ std::lock_guard < spinlock > S(spl);
+ dq.swap(A.dq);
+ };
+ //
+ //-----------------------------------------------------------------------
+ // S I Z E , M A X _ S I Z E , R E S I Z E
+ // C A P A C I T Y , E M P T Y , R E S E R V E
+ //-----------------------------------------------------------------------
+ //
+ //------------------------------------------------------------------------
+ // function : size
+ /// @brief return the number of elements in the deque_cnc
+ /// @return number of elements in the deque_cnc
+ //------------------------------------------------------------------------
+ size_type size(void) const noexcept
+ {
+ std::lock_guard < spinlock > S(spl);
+ return dq.size();
+ };
+ //
+ //------------------------------------------------------------------------
+ // function :max_size
+ /// @brief return the maximun size of the container
+ /// @return maximun size of the container
+ //------------------------------------------------------------------------
+ size_type max_size(void) const noexcept
+ {
+ std::lock_guard < spinlock > S(spl);
+ return (dq.max_size());
+ };
+ //
+ //-------------------------------------------------------------------------
+ // function : shrink_to_fit
+ /// @brief resize the current vector size and change to size.\n
+ /// If sz is smaller than the current size, delete elements to end\n
+ /// If sz is greater than the current size, insert elements to the
+ /// end with the value c
+ /// @param [in] sz : new size of the deque_cnc after the resize
+ /// @param [in] c : Value to insert if sz is greather than the current size
+ /// @return none
+ //------------------------------------------------------------------------
+ void shrink_to_fit()
+ {
+ std::lock_guard < spinlock > S(spl);
+ dq.shrink_to_fit();
+ };
+ //
+ //------------------------------------------------------------------------
+ // function : empty
+ /// @brief indicate if the map is empty
+ /// @return true if the map is empty, false in any other case
+ //------------------------------------------------------------------------
+ bool empty(void) const noexcept
+ {
+ std::lock_guard < spinlock > S(spl);
+ return (dq.empty());
+ };
+ //---------------------------------------------------------------------------
+ // function : push_back
+ /// @brief Insert one element in the back of the container
+ /// @param [in] D : value to insert. Can ve a value, a reference or an
+ /// rvalue
+ //---------------------------------------------------------------------------
+ void push_back(const value_type & D)
+ {
+ std::lock_guard < spinlock > S(spl);
+ dq.push_back(D);
+ };
+
+ //------------------------------------------------------------------------
+ // function : emplace_back
+ /// @brief Insert one element in the back of the container
+ /// @param [in] args :group of arguments for to build the object to insert
+ //-------------------------------------------------------------------------
+ template<class ... Args>
+ void emplace_back(Args && ... args)
+ {
+ std::lock_guard < spinlock > S(spl);
+ dq.emplace_back(std::forward <Args>(args) ...);
+ };
+ //------------------------------------------------------------------------
+ // function : push_back
+ /// @brief Insert one element in the back of the container
+ /// @param [in] D : deque to insert in the actual deque, inserting a copy
+ /// of the elements
+ /// @return reference to the deque after the insertion
+ //------------------------------------------------------------------------
+ template<class Allocator2>
+ deque_cnc & push_back(const std::deque<value_type, Allocator2> & D)
+ {
+ std::lock_guard < spinlock > S(spl);
+ for (size_type i = 0; i < D.size(); ++i)
+ dq.push_back(D[i]);
+ return *this;
+ };
+ //------------------------------------------------------------------------
+ // function : push_back
+ /// @brief Insert one element in the back of the container
+ /// @param [in] D : deque to insert in the actual deque, inserting a move
+ /// of the elements
+ /// @return reference to the deque after the insertion
+ //------------------------------------------------------------------------
+ deque_cnc & push_back(std::deque<value_type, Allocator> && D)
+ {
+ std::lock_guard < spinlock > S(spl);
+ for (size_type i = 0; i < D.size(); ++i)
+ dq.emplace_back(std::move(D[i]));
+ return *this;
+ };
+ //
+ //------------------------------------------------------------------------
+ // function :pop_back
+ /// @brief erase the last element of the container
+ //-----------------------------------------------------------------------
+ void pop_back(void)
+ {
+ std::lock_guard < spinlock > S(spl);
+ dq.pop_back();
+ };
+ //
+ //------------------------------------------------------------------------
+ // function :pop_copy_back
+ /// @brief erase the last element and return a copy over P
+ /// @param [out] P : reference to a variable where copy the element
+ /// @return code of the operation
+ /// true - Element erased
+ /// false - Empty tree
+ //------------------------------------------------------------------------
+ bool pop_copy_back(value_type & P)
+ { //-------------------------- begin -----------------------------
+ std::lock_guard < spinlock > S(spl);
+ if (dq.size() == 0) return false;
+ P = dq.back();
+ dq.pop_back();
+ return true;
+ };
+ //
+ //------------------------------------------------------------------------
+ // function :pop_move_back
+ /// @brief erase the last element and move over P
+ /// @param [out] P : reference to a variable where move the element
+ /// @return code of the operation
+ /// true - Element erased
+ /// false - Empty tree
+ //------------------------------------------------------------------------
+ bool pop_move_back(value_type & P)
+ { //-------------------------- begin -----------------------------
+ std::lock_guard < spinlock > S(spl);
+ if (dq.size() == 0) return false;
+ P = std::move(dq.back());
+ dq.pop_back();
+ return true;
+ };
+
+ //------------------------------------------------------------------------
+ // function : push_front
+ /// @brief Insert one copy of the element in the front of the container
+ /// @param [in] D : value to insert
+ //------------------------------------------------------------------------
+ void push_front(const value_type & D)
+ {
+ std::lock_guard < spinlock > S(spl);
+ dq.push_front(D);
+ };
+
+ //------------------------------------------------------------------------
+ // function : emplace_front
+ /// @brief Insert one element in the front of the container
+ /// @param [in] args :group of arguments for to build the object to insert
+ //-------------------------------------------------------------------------
+ template<class ... Args>
+ void emplace_front(Args && ... args)
+ {
+ std::lock_guard < spinlock > S(spl);
+ dq.emplace_front(std::forward <Args>(args) ...);
+ };
+ //------------------------------------------------------------------------
+ // function : push_front
+ /// @brief Insert a copy of the elements of the deque V1 in the front
+ /// of the container
+ /// @param [in] V1 : deque with the elements to insert
+ /// @return reference to the deque after the insertion
+ //------------------------------------------------------------------------
+ template<class Allocator2>
+ deque_cnc & push_front(const std::deque<value_type, Allocator2> & V1)
+ {
+ std::lock_guard < spinlock > S(spl);
+ for (size_type i = 0; i < V1.size(); ++i)
+ dq.push_front(V1[i]);
+ return *this;
+ };
+ //-----------------------------------------------------------------------
+ // function : push_front
+ /// @brief Insert a move of the elements of the deque V1 in the front
+ /// of the container
+ /// @param [in] V1 : deque with the elements to insert
+ /// @return reference to the deque after the insertion
+ //-----------------------------------------------------------------------
+ deque_cnc & push_front(std::deque<value_type, Allocator> && V1)
+ {
+ std::lock_guard < spinlock > S(spl);
+ for (size_type i = 0; i < V1.size(); ++i)
+ dq.emplace_front(std::move(V1[i]));
+ return *this;
+ };
+ //
+ //-----------------------------------------------------------------------
+ // function :pop_front
+ /// @brief erase the first element of the container
+ //-----------------------------------------------------------------------
+ void pop_front(void)
+ {
+ std::lock_guard < spinlock > S(spl);
+ dq.pop_front();
+ };
+ //
+ //-----------------------------------------------------------------------
+ // function :pop_copy_front
+ /// @brief erase the first element of the tree and return a copy over P
+ /// @param [out] P : reference to a variable where copy the element
+ /// @return code of the operation
+ /// true- Element erased
+ /// false - Empty tree
+ //-----------------------------------------------------------------------
+ bool pop_copy_front(value_type & P)
+ { //-------------------------- begin -----------------------------
+ std::lock_guard < spinlock > S(spl);
+ if (dq.size() == 0) return false;
+ P = dq.front();
+ dq.pop_front();
+ return true;
+ };
+ //
+ //------------------------------------------------------------------------
+ // function :pop_move_front
+ /// @brief erase the first element of the tree and return a move over P
+ /// @param [out] P : reference to a variable where move the element
+ /// @return code of the operation
+ /// true- Element erased
+ /// false - Empty tree
+ //------------------------------------------------------------------------
+ bool pop_move_front(value_type & P)
+ { //-------------------------- begin -----------------------------
+ std::lock_guard < spinlock > S(spl);
+ if (dq.size() == 0) return false;
+ P = std::move(dq.front());
+ dq.pop_front();
+ return true;
+ };
+};
+// end class deque_cnc
+
+//***************************************************************************
+};// end namespace tools
+};// end namespace sort
+//***************************************************************************
+#endif
diff --git a/boost/sort/common/file_vector.hpp b/boost/sort/common/file_vector.hpp
new file mode 100644
index 0000000000..1dc62fc02f
--- /dev/null
+++ b/boost/sort/common/file_vector.hpp
@@ -0,0 +1,272 @@
+//----------------------------------------------------------------------------
+/// @file file_vector.hpp
+/// @brief This file contains functions for to work with random data and files
+/// Have functions for to create a vector with random data, and
+/// functions for lo load a vector of numbers or strings from the file
+///
+/// @author Copyright (c) 2015 Francisco José Tapia (fjtapia@gmail.com )\n
+/// Distributed under the Boost Software License, Version 1.0.\n
+/// ( See accompanyingfile LICENSE_1_0.txt or copy at
+/// http://www.boost.org/LICENSE_1_0.txt )
+/// @version 0.1
+///
+/// @remarks
+//-----------------------------------------------------------------------------
+#ifndef __BOOST_SORT_COMMON_FILE_VECTOR_HPP
+#define __BOOST_SORT_COMMON_FILE_VECTOR_HPP
+
+#include <ios>
+#include <cstdio>
+#include <cstdlib>
+#include <ciso646>
+#include <vector>
+#include <string>
+#include <fstream>
+#include <sstream>
+#include <iostream>
+#include <random>
+#include <cstdint>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+//
+//-----------------------------------------------------------------------------
+// function : generate_file
+/// @brief Generate a binary file filed with random numbers of 64 bits
+/// @param [in] filename : name of the file
+/// @param [in] NElem : number of 64 bits numbers to insert in the file
+/// @exception
+/// @return
+/// @remarks
+//-----------------------------------------------------------------------------
+static int generate_file(const std::string & filename, size_t NElem)
+{ //------------------------------- begin ----------------------------------
+ std::ofstream ofile;
+ ofile.open(filename, std::ios_base::out | std::ios_base::binary |
+ std::ios_base::trunc);
+ if (ofile.bad())
+ {
+ throw std::ios_base::failure("could not open file \n");
+ };
+ std::mt19937_64 my_rand(0);
+
+ for (size_t i = 0; i < NElem; ++i)
+ {
+ uint64_t Aux = my_rand();
+ ofile.write((char *) &Aux, 8);
+ }
+ ofile.close();
+ return 0;
+};
+//
+//-----------------------------------------------------------------------------
+// function : fill_vector_uint64
+/// @brief : fill a vector of uint64_t elements from a file
+/// @param [in] filename : name of the file
+/// @param [in] V : vector to fill
+/// @param [in] NElem : number of elements for to read from the file
+/// @exception
+/// @return
+/// @remarks
+//-----------------------------------------------------------------------------
+static int fill_vector_uint64(const std::string & filename,
+ std::vector<uint64_t> & V, size_t NElem)
+{ //----------------------- begin ------------------------------------------
+ std::ifstream input(filename, std::ios_base::in | std::ios_base::binary);
+ if (input.fail())
+ {
+ throw std::ios_base::failure("could not open file \n");
+ };
+ //------------------------------------------------------------------------
+ // Calculate the lenght of the file and the number of elements inside
+ //------------------------------------------------------------------------
+ input.seekg(0, std::ios_base::end);
+ size_t length = input.tellg();
+ size_t uCount = length / 8;
+ if (uCount < NElem)
+ {
+ throw std::ios_base::failure("incorrect lenght of the file\n");
+ };
+ V.clear();
+ V.reserve(NElem);
+
+ uint64_t Aux = 0;
+ input.seekg(0, std::ios_base::beg);
+ for (size_t i = 0; i < NElem; ++i)
+ {
+ input.read(reinterpret_cast<char *>(&Aux), 8);
+ V.push_back(Aux);
+ };
+ input.close();
+ return 0;
+};
+
+//
+//-----------------------------------------------------------------------------
+// function :write_file_uint64
+/// @brief Write a file with the contnt of a vector of Uint64_t elements
+/// @param [in] V : vector from read the numbersl
+/// @param [in] filename : name of the file
+/// @exception
+/// @return
+/// @remarks
+//-----------------------------------------------------------------------------
+static int write_file_uint64 (const std::vector<uint64_t> & V,
+ const std::string & filename)
+{ //--------------------------------- begin --------------------------------
+ std::ofstream ofile;
+ ofile.open(filename,
+ std::ios_base::out | std::ios_base::binary
+ | std::ios_base::trunc);
+ if (ofile.bad())
+ {
+ throw std::ios_base::failure("could not open file \n");
+ };
+ for (size_t i = 0; i < V.size(); ++i)
+ {
+ ofile.write((char *) &(V[i]), 8);
+ }
+ ofile.close();
+ return 0;
+};
+//
+//-----------------------------------------------------------------------------
+// function : fill_vector_string
+/// @brief fill a vector of strings from a file
+/// @param [in] filename : name of the file from read the strings
+/// @param [in] V : vector where store the strings
+/// @param [in] NElem : Number of strings for to read from the file
+/// @exception
+/// @return
+/// @remarks
+//-----------------------------------------------------------------------------
+static int fill_vector_string (const std::string & filename,
+ std::vector<std::string> & V, size_t NElem)
+{ //----------------------- begin ------------------------------------------
+ std::ifstream input(filename, std::ios_base::in | std::ios_base::binary);
+ if (input.fail())
+ {
+ throw std::ios_base::failure("could not open file \n");
+ };
+ //------------------------------------------------------------------------
+ // Calculate the lenght of the file and the number of elements inside
+ //------------------------------------------------------------------------
+ input.seekg(0, std::ios_base::end);
+ V.clear();
+ V.reserve(NElem);
+
+ std::string inval;
+ input.seekg(0, std::ios_base::beg);
+
+ for (size_t i = 0; i < NElem; ++i)
+ {
+ if (!input.eof())
+ {
+ input >> inval;
+ V.push_back(inval);
+ inval.clear();
+ }
+ else
+ {
+ throw std::ios_base::failure("Insuficient lenght of the file\n");
+ };
+ };
+ input.close();
+ return 0;
+};
+
+//
+//-----------------------------------------------------------------------------
+// function :write_file_string
+/// @brief : write a file with the strings of a vector
+/// @param [in] V : vector from read the sttrings
+/// @param [in] filename : file where store the strings
+/// @exception
+/// @return
+/// @remarks
+//-----------------------------------------------------------------------------
+static int write_file_string (const std::vector<std::string> & V,
+ const std::string & filename)
+{ //--------------------------------- begin --------------------------------
+ std::ofstream ofile;
+ ofile.open(filename,
+ std::ios_base::out | std::ios_base::binary
+ | std::ios_base::trunc);
+ if (ofile.bad())
+ {
+ throw std::ios_base::failure("could not open file \n");
+ };
+ for (size_t i = 0; i < V.size(); ++i)
+ {
+ ofile.write((char *) &(V[i][0]), V[i].size());
+ ofile.put(0x0);
+ }
+ ofile.close();
+ return 0;
+};
+//---------------------------------------------------------------------------
+/// @struct uint64_file_generator
+/// @brief This struct is a number generator from a file, with several options
+/// for to limit the numbers between 0 and Max_Val
+/// @remarks
+//---------------------------------------------------------------------------
+struct uint64_file_generator
+{ //----------------------------------------------------------------------
+ // VARIABLES
+ //----------------------------------------------------------------------
+ std::ifstream input;
+ size_t NMax, Pos;
+ size_t Max_Val;
+ std::string s;
+
+ //----------------------------------------------------------------------
+ // FUNCTIONS
+ //----------------------------------------------------------------------
+ uint64_file_generator(const std::string & filename)
+ { //---------------------------- begin ---------------------------------
+ s = filename;
+ input.open(filename, std::ios_base::in | std::ios_base::binary);
+ if (input.fail() or input.bad())
+ {
+ throw std::ios_base::failure("could not open file \n");
+ };
+ //--------------------------------------------------------------------
+ // Calculate the lenght of the file and the number of elements inside
+ //--------------------------------------------------------------------
+ input.seekg(0, std::ios_base::end);
+ size_t length = input.tellg();
+ NMax = length / 8;
+ Pos = 0;
+ Max_Val = ~((size_t) 0);
+ input.seekg(0);
+ };
+
+ void set_max_val(size_t MV){ Max_Val = MV; };
+
+ size_t size() const { return NMax; };
+
+ uint64_t get(void)
+ {
+ uint64_t Aux;
+ input.read(reinterpret_cast<char *>(&Aux), 8);
+ return (Aux % Max_Val);
+ };
+
+ uint64_t operator ( )(){ return get(); };
+
+ void reset(void) { input.seekg(0, std::ios_base::beg); };
+
+ ~uint64_file_generator() { if (input.is_open()) input.close(); };
+};
+//
+//****************************************************************************
+};// end namespace benchmark
+};// end namespace sort
+};// end namespace boost
+//****************************************************************************
+//
+#endif
diff --git a/boost/sort/common/indirect.hpp b/boost/sort/common/indirect.hpp
new file mode 100644
index 0000000000..a55ef82023
--- /dev/null
+++ b/boost/sort/common/indirect.hpp
@@ -0,0 +1,153 @@
+//----------------------------------------------------------------------------
+/// @file indirect.hpp
+/// @brief Indirect 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_COMMON_INDIRECT_HPP
+#define __BOOST_SORT_PARALLEL_COMMON_INDIRECT_HPP
+
+//#include <boost/sort/common/atomic.hpp>
+#include <boost/sort/common/util/traits.hpp>
+#include <functional>
+#include <iterator>
+#include <type_traits>
+#include <vector>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+
+//
+//---------------------------------------------------------------------------
+/// @struct less_ptr_no_null
+///
+/// @remarks this is the comparison object for pointers. Compare the objects
+/// pointed by the iterators
+//---------------------------------------------------------------------------
+template<class Iter_t, class Compare = util::compare_iter<Iter_t> >
+struct less_ptr_no_null
+{
+ //----------------------------- Variables -----------------------
+ Compare comp; // comparison object of the elements pointed by Iter_t
+
+ //------------------------------------------------------------------------
+ // function : less_ptr_no_null
+ /// @brief constructor from a Compare object
+ /// @param C1 : comparison object
+ //-----------------------------------------------------------------------
+ less_ptr_no_null(Compare C1 = Compare()): comp(C1) { };
+
+ //------------------------------------------------------------------------
+ // function : operator ( )
+ /// @brief Make the comparison of the objects pointed by T1 and T2, using
+ // the internal comp
+ //
+ /// @param T1 : first iterator
+ /// @param T2 : second iterator
+ /// @return bool result of the comparison
+ //-----------------------------------------------------------------------
+ bool operator( )(Iter_t T1, Iter_t T2) const
+ {
+ return comp(*T1, *T2);
+ };
+};
+//
+//-----------------------------------------------------------------------------
+// function : create_index
+/// @brief From a vector of objects, create a vector of iterators to
+/// the objects
+///
+/// @param first : iterator to the first element of the range
+/// @param last : iterator to the element after the last of the range
+/// @param index : vector where store the iterators
+//-----------------------------------------------------------------------------
+template<class Iter_t>
+static void create_index(Iter_t first, Iter_t last, std::vector<Iter_t> &index)
+{
+ auto nelem = last - first;
+ assert(nelem >= 0);
+ index.clear();
+ index.reserve(nelem);
+ for (; first != last; ++first) index.push_back(first);
+};
+//
+//-----------------------------------------------------------------------------
+// function : sort_index
+/// @brief This function transform a logical sort of the elements in the index
+/// in a physical sort
+//
+/// @param global_first : iterator to the first element of the data
+/// @param [in] index : vector of the iterators
+//-----------------------------------------------------------------------------
+template<class Iter_t>
+static void sort_index(Iter_t global_first, std::vector<Iter_t> &index)
+{
+ typedef util::value_iter<Iter_t> value_t;
+
+ size_t pos_dest = 0;
+ size_t pos_src = 0;
+ size_t pos_in_vector = 0;
+ size_t nelem = index.size();
+ Iter_t it_dest, it_src;
+
+ while (pos_in_vector < nelem)
+ {
+ while (pos_in_vector < nelem and
+ (size_t(index[pos_in_vector] - global_first)) == pos_in_vector)
+ {
+ ++pos_in_vector;
+ };
+
+ if (pos_in_vector == nelem) return;
+ pos_dest = pos_src = pos_in_vector;
+ it_dest = global_first + pos_dest;
+ value_t Aux = std::move(*it_dest);
+
+ while ((pos_src = (size_t(index[pos_dest] - global_first)))
+ != pos_in_vector)
+ {
+ index[pos_dest] = it_dest;
+ it_src = global_first + pos_src;
+ *it_dest = std::move(*it_src);
+ it_dest = it_src;
+ pos_dest = pos_src;
+ };
+
+ *it_dest = std::move(Aux);
+ index[pos_dest] = it_dest;
+ ++pos_in_vector;
+ };
+};
+
+template<class func, class Iter_t, class Compare = compare_iter<Iter_t> >
+static void indirect_sort(func method, Iter_t first, Iter_t last, Compare comp)
+{
+ auto nelem = (last - first);
+ assert(nelem >= 0);
+ if (nelem < 2) return;
+ std::vector<Iter_t> index;
+ index.reserve((size_t) nelem);
+ create_index(first, last, index);
+ less_ptr_no_null<Iter_t, Compare> index_comp(comp);
+ method(index.begin(), index.end(), index_comp);
+ sort_index(first, index);
+};
+
+//
+//****************************************************************************
+};// End namespace common
+};// End namespace sort
+};// End namespace boost
+//****************************************************************************
+//
+#endif
diff --git a/boost/sort/common/int_array.hpp b/boost/sort/common/int_array.hpp
new file mode 100644
index 0000000000..22c3b0c5a4
--- /dev/null
+++ b/boost/sort/common/int_array.hpp
@@ -0,0 +1,75 @@
+//----------------------------------------------------------------------------
+/// @file int_array.hpp
+/// @brief This file contains the struct int_array , which is an array of
+/// uint64_t elements, being the template parameter NN the number of
+/// elements in the array
+///
+/// @author Copyright (c) 2010 2015 Francisco José Tapia (fjtapia@gmail.com )\n
+/// Distributed under the Boost Software License, Version 1.0.\n
+/// ( See accompanyingfile LICENSE_1_0.txt or copy at
+/// http://www.boost.org/LICENSE_1_0.txt )
+/// @version 0.1
+///
+/// @remarks
+//-----------------------------------------------------------------------------
+#ifndef __BOOST_SORT_COMMON_INT_ARRAY_HPP
+#define __BOOST_SORT_COMMON_INT_ARRAY_HPP
+
+#include <cstdint>
+#include <iostream>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+
+template<uint32_t NN>
+struct int_array
+{
+ uint64_t M[NN];
+
+ template<class generator>
+ static int_array<NN> generate(generator & gen)
+ {
+ int_array<NN> result;
+ for (uint32_t i = 0; i < NN; ++i)
+ {
+ result.M[i] = gen();
+ };
+ return result;
+ };
+
+ uint64_t counter(void) const
+ {
+ uint64_t Acc = M[0];
+ for (uint32_t i = 1; i < NN; Acc += M[i++])
+ ;
+ return Acc;
+ };
+};
+
+template<class IA>
+struct H_comp
+{
+ bool operator ( )(const IA & A1, const IA & A2) const
+ {
+ return (A1.counter() < A2.counter());
+ };
+};
+
+template<class IA>
+struct L_comp
+{
+ bool operator ( )(const IA & A1, const IA & A2) const
+ {
+ return (A1.M[0] < A2.M[0]);
+ };
+};
+//***************************************************************************
+};// End namespace benchmark
+};// End namespace sort
+};// End namespace boost
+//***************************************************************************
+#endif // end of int_array.hpp
diff --git a/boost/sort/common/merge_block.hpp b/boost/sort/common/merge_block.hpp
new file mode 100644
index 0000000000..9a7b118270
--- /dev/null
+++ b/boost/sort/common/merge_block.hpp
@@ -0,0 +1,418 @@
+//----------------------------------------------------------------------------
+/// @file merge_block.hpp
+/// @brief This file constains the class merge_block, which is part of the
+/// 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_COMMON_MERGE_BLOCK_HPP
+#define __BOOST_SORT_COMMON_MERGE_BLOCK_HPP
+
+#include <boost/sort/common/range.hpp>
+#include <boost/sort/common/rearrange.hpp>
+#include <boost/sort/common/util/merge.hpp>
+#include <boost/sort/common/util/traits.hpp>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+///---------------------------------------------------------------------------
+/// @struct merge_block
+/// @brief This contains all the information shared betwen the classes of the
+/// block indirect sort algorithm
+
+//----------------------------------------------------------------------------
+template<class Iter_t, class Compare, uint32_t Power2 = 10>
+struct merge_block
+{
+ //-------------------------------------------------------------------------
+ // D E F I N I T I O N S
+ //-------------------------------------------------------------------------
+ typedef util::value_iter<Iter_t> value_t;
+ typedef range<size_t> range_pos;
+ typedef range<Iter_t> range_it;
+ typedef range<value_t *> range_buf;
+ typedef typename std::vector<size_t>::iterator it_index;
+ typedef util::circular_buffer<value_t, Power2 + 1> circular_t;
+
+ //------------------------------------------------------------------------
+ // CONSTANTS
+ //------------------------------------------------------------------------
+ const size_t BLOCK_SIZE = (size_t) 1 << Power2;
+ const size_t LOG_BLOCK = Power2;
+
+ //------------------------------------------------------------------------
+ // V A R I A B L E S
+ //------------------------------------------------------------------------
+ // range with all the element to sort
+ range<Iter_t> global_range;
+
+ // index vector of block_pos elements
+ std::vector<size_t> index;
+
+ // Number of elements to sort
+ size_t nelem;
+
+ // Number of blocks to sort
+ size_t nblock;
+
+ // Number of elements in the last block (tail)
+ size_t ntail;
+
+ // object for to compare two elements
+ Compare cmp;
+
+ // range of elements of the last block (tail)
+ range_it range_tail;
+
+ // circular buffer
+ circular_t * ptr_circ;
+
+ // indicate if the circulr buffer is owned by the data structure
+ // or is received as parameter
+ bool owned;
+
+ //
+ //------------------------------------------------------------------------
+ // F U N C T I O N S
+ //------------------------------------------------------------------------
+ //
+ //------------------------------------------------------------------------
+ // function : merge_block
+ /// @brief constructor of the class
+ //
+ /// @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
+ //------------------------------------------------------------------------
+ merge_block (Iter_t first, Iter_t last, Compare comp,
+ circular_t *pcirc_buffer)
+ : global_range(first, last), cmp(comp), ptr_circ(pcirc_buffer),
+ owned(pcirc_buffer == nullptr)
+ {
+ assert((last - first) >= 0);
+ if (first == last) return; // nothing to do
+
+ nelem = size_t(last - first);
+ nblock = (nelem + BLOCK_SIZE - 1) / BLOCK_SIZE;
+ ntail = (nelem % BLOCK_SIZE);
+ index.reserve(nblock + 1);
+
+ for (size_t i = 0; i < nblock; ++i)
+ index.emplace_back(i);
+
+ range_tail.first = first + ((nblock - 1) << LOG_BLOCK);
+ range_tail.last = last;
+ if (owned)
+ {
+ ptr_circ = new circular_t;
+ ptr_circ->initialize(*first);
+ };
+ }
+
+ merge_block(Iter_t first, Iter_t last, Compare comp)
+ : merge_block(first, last, comp, nullptr) { };
+
+ ~ merge_block()
+ {
+ if (ptr_circ != nullptr and owned)
+ {
+ delete ptr_circ;
+ ptr_circ = nullptr;
+ };
+ };
+ //-------------------------------------------------------------------------
+ // function : get_range
+ /// @brief obtain the range in the position pos
+ /// @param pos : position of the range
+ /// @return range required
+ //-------------------------------------------------------------------------
+ range_it get_range(size_t pos) const
+ {
+ Iter_t it1 = global_range.first + (pos << LOG_BLOCK);
+ Iter_t it2 = (pos == (nblock - 1)) ?
+ global_range.last : it1 + BLOCK_SIZE;
+ return range_it(it1, it2);
+ };
+ //-------------------------------------------------------------------------
+ // function : get_group_range
+ /// @brief obtain the range of the contiguous blocks beginning in the
+ // position pos
+ /// @param pos : position of the first range
+ /// @param nrange : number of ranges of the group
+ /// @return range required
+ //-------------------------------------------------------------------------
+ range_it get_group_range(size_t pos, size_t nrange) const
+ {
+ Iter_t it1 = global_range.first + (pos << LOG_BLOCK);
+
+ Iter_t it2 = ((pos + nrange) == nblock)?global_range.last: global_range.first + ((pos + nrange) << LOG_BLOCK);
+ //Iter_t it2 = global_range.first + ((pos + nrange) << LOG_BLOCK);
+ //if ((pos + nrange) == nblock) it2 = global_range.last;
+
+ return range_it(it1, it2);
+ };
+ //-------------------------------------------------------------------------
+ // function : is_tail
+ /// @brief indicate if a block is the tail
+ /// @param pos : position of the block
+ /// @return true : taiol false : not tail
+ //-------------------------------------------------------------------------
+ bool is_tail(size_t pos) const
+ {
+ return (pos == (nblock - 1) and ntail != 0);
+ };
+ //-------------------------------------------------------------------------
+ // function :
+ /// @brief
+ /// @param
+ /// @return
+ //-------------------------------------------------------------------------
+ void merge_range_pos(it_index itx_first, it_index itx_mid,
+ it_index itx_last);
+
+ //-------------------------------------------------------------------------
+ // function : move_range_pos_backward
+ /// @brief Move backward the elements of a range of blocks in a index
+ /// @param itx_first : iterator to the position of the first block
+ /// @param itx_last : itertor to the position of the last block
+ /// @param npos : number of positions to move. Must be less than BLOCK_SIZE
+ /// @return
+ //-------------------------------------------------------------------------
+ void move_range_pos_backward(it_index itx_first, it_index itx_last,
+ size_t npos);
+
+ //-------------------------------------------------------------------------
+ // function : rearrange_with_index
+ /// @brief rearrange the blocks with the relative positions of the index
+ /// @param
+ /// @param
+ /// @param
+ /// @return
+ //-------------------------------------------------------------------------
+ void rearrange_with_index(void);
+
+//---------------------------------------------------------------------------
+};// end struct merge_block
+//---------------------------------------------------------------------------
+//
+//############################################################################
+// ##
+// N O N I N L I N E F U N C T IO N S ##
+// ##
+//############################################################################
+//
+//-------------------------------------------------------------------------
+// function :
+/// @brief
+/// @param
+/// @return
+//-------------------------------------------------------------------------
+template<class Iter_t, class Compare, uint32_t Power2>
+void merge_block<Iter_t, Compare, Power2>
+::merge_range_pos(it_index itx_first, it_index itx_mid,it_index itx_last)
+{
+ assert((itx_last - itx_mid) >= 0 and (itx_mid - itx_first) >= 0);
+
+ size_t nelemA = (itx_mid - itx_first), nelemB = (itx_last - itx_mid);
+ if (nelemA == 0 or nelemB == 0) return;
+
+ //-------------------------------------------------------------------
+ // Create two index with the position of the blocks to merge
+ //-------------------------------------------------------------------
+ std::vector<size_t> indexA, indexB;
+ indexA.reserve(nelemA + 1);
+ indexB.reserve(nelemB);
+
+ indexA.insert(indexA.begin(), itx_first, itx_mid);
+ indexB.insert(indexB.begin(), itx_mid, itx_last);
+
+ it_index itx_out = itx_first;
+ it_index itxA = indexA.begin(), itxB = indexB.begin();
+ range_it rngA, rngB;
+ Iter_t itA = global_range.first, itB = global_range.first;
+ bool validA = false, validB = false;
+
+ while (itxA != indexA.end() and itxB != indexB.end())
+ { //----------------------------------------------------------------
+ // Load valid ranges from the itxA and ItxB positions
+ //----------------------------------------------------------------
+ if (not validA)
+ {
+ rngA = get_range(*itxA);
+ itA = rngA.first;
+ validA = true;
+ };
+ if (not validB)
+ {
+ rngB = get_range(*itxB);
+ itB = rngB.first;
+ validB = true;
+ };
+ //----------------------------------------------------------------
+ // If don't have merge betweeen the blocks, pass directly the
+ // position of the block to itx_out
+ //----------------------------------------------------------------
+ if (ptr_circ->size() == 0)
+ {
+ if (not cmp(*rngB.front(), *rngA.back()))
+ {
+ *(itx_out++) = *(itxA++);
+ validA = false;
+ continue;
+ };
+ if (cmp(*rngB.back(), *rngA.front()))
+ {
+ if (not is_tail(*itxB))
+ *(itx_out++) = *itxB;
+ else ptr_circ->push_move_back(rngB.first, rngB.size());
+ ++itxB;
+ validB = false;
+ continue;
+ };
+ };
+ //----------------------------------------------------------------
+ // Normal merge
+ //----------------------------------------------------------------
+ bool side = util::merge_circular(itA, rngA.last, itB, rngB.last,
+ *ptr_circ, cmp, itA, itB);
+ if (side)
+ { // rngA is finished
+ ptr_circ->pop_move_front(rngA.first, rngA.size());
+ *(itx_out++) = *(itxA++);
+ validA = false;
+ }
+ else
+ { // rngB is finished
+ if (not is_tail(*itxB))
+ {
+ ptr_circ->pop_move_front(rngB.first, rngB.size());
+ *(itx_out++) = *itxB;
+ };
+ ++itxB;
+ validB = false;
+ };
+ }; // end while
+
+ if (itxA == indexA.end())
+ { // the index A is finished
+ rngB = get_range(*itxB);
+ ptr_circ->pop_move_front(rngB.first, ptr_circ->size());
+ while (itxB != indexB.end())
+ *(itx_out++) = *(itxB++);
+ }
+ else
+ { // The list B is finished
+ rngA = get_range(*itxA);
+ if (ntail != 0 and indexB.back() == (nblock - 1)) // exist tail
+ { // add the tail block to indexA, and shift the element
+ indexA.push_back(indexB.back());
+ size_t numA = size_t(itA - rngA.first);
+ ptr_circ->pop_move_back(rngA.first, numA);
+ move_range_pos_backward(itxA, indexA.end(), ntail);
+ };
+
+ ptr_circ->pop_move_front(rngA.first, ptr_circ->size());
+ while (itxA != indexA.end())
+ *(itx_out++) = *(itxA++);
+ };
+};
+
+//-------------------------------------------------------------------------
+// function : move_range_pos_backward
+/// @brief Move backward the elements of a range of blocks in a index
+/// @param itx_first : iterator to the position of the first block
+/// @param itx_last : itertor to the position of the last block
+/// @param npos : number of positions to move. Must be less than BLOCK_SIZE
+/// @return
+//-------------------------------------------------------------------------
+template<class Iter_t, class Compare, uint32_t Power2>
+void merge_block<Iter_t, Compare, Power2>
+::move_range_pos_backward(it_index itx_first, it_index itx_last, size_t npos)
+{
+ assert((itx_last - itx_first) >= 0 and npos <= BLOCK_SIZE);
+
+ //--------------------------------------------------------------------
+ // Processing the last block. Must be ready fore to accept npos
+ // elements from the upper block
+ //--------------------------------------------------------------------
+ range_it rng1 = get_range(*(itx_last - 1));
+ assert(rng1.size() >= npos);
+ if (rng1.size() > npos)
+ {
+ size_t nmove = rng1.size() - npos;
+ util::move_backward(rng1.last, rng1.first, rng1.first + nmove);
+ };
+ //--------------------------------------------------------------------
+ // Movement of elements between blocks
+ //--------------------------------------------------------------------
+ for (it_index itx = itx_last - 1; itx != itx_first;)
+ {
+ --itx;
+ range_it rng2 = rng1;
+ rng1 = get_range(*itx);
+ Iter_t it_mid1 = rng1.last - npos, it_mid2 = rng2.first + npos;
+ util::move_backward(it_mid2, it_mid1, rng1.last);
+ util::move_backward(rng1.last, rng1.first, it_mid1);
+ };
+};
+//-------------------------------------------------------------------------
+// function : rearrange_with_index
+/// @brief rearrange the blocks with the relative positions of the index
+/// @param
+/// @param
+/// @param
+/// @return
+//-------------------------------------------------------------------------
+template<class Iter_t, class Compare, uint32_t Power2>
+void merge_block<Iter_t, Compare, Power2>
+::rearrange_with_index(void)
+{ //--------------------------------------------------------------------
+ // Code
+ //--------------------------------------------------------------------
+ size_t pos_dest, pos_src, pos_ini;
+ size_t nelem = index.size();
+
+ ptr_circ->clear();
+ value_t * aux = ptr_circ->get_buffer();
+ range_buf rng_buf(aux, aux + ptr_circ->NMAX);
+
+ pos_ini = 0;
+ while (pos_ini < nelem)
+ {
+ while (pos_ini < nelem and index[pos_ini] == pos_ini)
+ ++pos_ini;
+ if (pos_ini == nelem) return;
+ pos_dest = pos_src = pos_ini;
+ rng_buf = move_forward(rng_buf, get_range(pos_ini));
+ pos_src = index[pos_ini];
+
+ while (pos_src != pos_ini)
+ {
+ move_forward(get_range(pos_dest), get_range(pos_src));
+ index[pos_dest] = pos_dest;
+ pos_dest = pos_src;
+ pos_src = index[pos_src];
+ };
+ move_forward(get_range(pos_dest), rng_buf);
+ index[pos_dest] = pos_dest;
+ ++pos_ini;
+ };
+};
+
+//****************************************************************************
+};// End namespace common
+};// End namespace sort
+};// End namespace boost
+//****************************************************************************
+#endif
diff --git a/boost/sort/common/merge_four.hpp b/boost/sort/common/merge_four.hpp
new file mode 100644
index 0000000000..edfb2ffc72
--- /dev/null
+++ b/boost/sort/common/merge_four.hpp
@@ -0,0 +1,327 @@
+//----------------------------------------------------------------------------
+/// @file merge_four.hpp
+/// @brief This file have the functions for to merge 4 buffers
+///
+/// @author Copyright (c) 2016 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_PARALLEL_DETAIL_UTIL_MERGE_FOUR_HPP
+#define __BOOST_SORT_PARALLEL_DETAIL_UTIL_MERGE_FOUR_HPP
+
+#include <boost/sort/common/util/traits.hpp>
+#include <boost/sort/common/range.hpp>
+#include <functional>
+#include <iterator>
+#include <memory>
+#include <vector>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+
+//
+//############################################################################
+// ##
+// F U S I O N O F ##
+// ##
+// F O U R E L E M E N T S R A N G E ##
+// ##
+//############################################################################
+//
+
+//-----------------------------------------------------------------------------
+// function : less_range
+/// @brief Compare the elements pointed by it1 and it2, and if they
+/// are equals, compare their position, doing a stable comparison
+///
+/// @param it1 : iterator to the first element
+/// @param pos1 : position of the object pointed by it1
+/// @param it2 : iterator to the second element
+/// @param pos2 : position of the element pointed by it2
+/// @param comp : comparison object
+/// @return result of the comparison
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Compare = typename util::compare_iter<Iter_t> >
+inline bool less_range(Iter_t it1, uint32_t pos1, Iter_t it2, uint32_t pos2,
+ Compare comp = Compare())
+{
+ return (comp(*it1, *it2)) ? true :
+ (pos2 < pos1) ? false : not (comp(*it2, *it1));
+};
+
+//-----------------------------------------------------------------------------
+// function : full_merge4
+/// @brief Merge four ranges
+///
+/// @param dest: range where move the elements merged. Their size must be
+/// greater or equal than the sum of the sizes of the ranges
+/// in vrange_input
+/// @param vrange_input : array of ranges to merge
+/// @param nrange_input : number of ranges in vrange_input
+/// @param comp : comparison object
+/// @return range with all the elements moved with the size adjusted
+//-----------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, class Compare>
+range<Iter1_t> full_merge4(const range<Iter1_t> &rdest,
+ range<Iter2_t> vrange_input[4],
+ uint32_t nrange_input, Compare comp)
+{
+ typedef range<Iter1_t> range1_t;
+ typedef util::value_iter<Iter1_t> type1;
+ typedef util::value_iter<Iter2_t> type2;
+ static_assert (std::is_same< type1, type2 >::value,
+ "Incompatible iterators\n");
+
+ size_t ndest = 0;
+ uint32_t i = 0;
+ while (i < nrange_input)
+ {
+ if (vrange_input[i].size() != 0)
+ {
+ ndest += vrange_input[i++].size();
+ }
+ else
+ {
+ for (uint32_t k = i + 1; k < nrange_input; ++k)
+ {
+ vrange_input[k - 1] = vrange_input[k];
+ };
+ --nrange_input;
+ };
+ };
+
+ if (nrange_input == 0) return range1_t(rdest.first, rdest.first);
+ if (nrange_input == 1) return move_forward(rdest, vrange_input[0]);
+ if (nrange_input == 2)
+ {
+ return merge(rdest, vrange_input[0], vrange_input[1], comp);
+ };
+
+ //------------------------------------------------------------------------
+ // Initial sort
+ //------------------------------------------------------------------------
+ uint32_t pos[4] =
+ { 0, 1, 2, 3 }, npos = nrange_input;
+
+ //-----------------------------------------------------------------------
+ // thanks to Steven Ross by their suggestion about the optimal
+ // sorting networks
+ //-----------------------------------------------------------------------
+ if (less_range(vrange_input[pos[1]].first, pos[1],
+ vrange_input[pos[0]].first, pos[0], comp))
+ {
+ std::swap(pos[0], pos[1]);
+ };
+ if (npos == 4 and less_range(vrange_input[pos[3]].first, pos[3],
+ vrange_input[pos[2]].first, pos[2], comp))
+ {
+ std::swap(pos[3], pos[2]);
+ };
+ if (less_range (vrange_input[pos[2]].first, pos[2],
+ vrange_input[pos[0]].first, pos[0], comp))
+ {
+ std::swap(pos[0], pos[2]);
+ };
+ if (npos == 4
+ and less_range (vrange_input[pos[3]].first, pos[3],
+ vrange_input[pos[1]].first, pos[1], comp))
+ {
+ std::swap(pos[1], pos[3]);
+ };
+ if (less_range (vrange_input[pos[2]].first, pos[2],
+ vrange_input[pos[1]].first, pos[1], comp))
+ {
+ std::swap(pos[1], pos[2]);
+ };
+
+ Iter1_t it_dest = rdest.first;
+ while (npos > 2)
+ {
+ *(it_dest++) = std::move(*(vrange_input[pos[0]].first++));
+ if (vrange_input[pos[0]].size() == 0)
+ {
+ pos[0] = pos[1];
+ pos[1] = pos[2];
+ pos[2] = pos[3];
+ --npos;
+ }
+ else
+ {
+ if (less_range(vrange_input[pos[1]].first, pos[1],
+ vrange_input[pos[0]].first, pos[0], comp))
+ {
+ std::swap(pos[0], pos[1]);
+ if (less_range(vrange_input[pos[2]].first, pos[2],
+ vrange_input[pos[1]].first, pos[1], comp))
+ {
+ std::swap(pos[1], pos[2]);
+ if (npos == 4
+ and less_range(vrange_input[pos[3]].first,
+ pos[3],
+ vrange_input[pos[2]].first,
+ pos[2], comp))
+ {
+ std::swap(pos[2], pos[3]);
+ };
+ };
+ };
+ };
+ };
+
+ range1_t raux1(rdest.first, it_dest), raux2(it_dest, rdest.last);
+ if (pos[0] < pos[1])
+ {
+ return concat(raux1,merge(raux2, vrange_input[pos[0]],
+ vrange_input[pos[1]], comp));
+ }
+ else
+ {
+ return concat(raux1, merge (raux2, vrange_input[pos[1]],
+ vrange_input[pos[0]], comp));
+ };
+};
+
+//-----------------------------------------------------------------------------
+// function : uninit_full_merge4
+/// @brief Merge four ranges and put the result in uninitialized memory
+///
+/// @param dest: range where create and move the elements merged. Their
+/// size must be greater or equal than the sum of the sizes
+/// of the ranges in the array R
+/// @param vrange_input : array of ranges to merge
+/// @param nrange_input : number of ranges in vrange_input
+/// @param comp : comparison object
+/// @return range with all the elements move with the size adjusted
+//-----------------------------------------------------------------------------
+template<class Value_t, class Iter_t, class Compare>
+range<Value_t *> uninit_full_merge4(const range<Value_t *> &dest,
+ range<Iter_t> vrange_input[4],
+ uint32_t nrange_input, Compare comp)
+{
+ typedef util::value_iter<Iter_t> type1;
+ static_assert (std::is_same< type1, Value_t >::value,
+ "Incompatible iterators\n");
+
+ size_t ndest = 0;
+ uint32_t i = 0;
+ while (i < nrange_input)
+ {
+ if (vrange_input[i].size() != 0)
+ {
+ ndest += vrange_input[i++].size();
+ }
+ else
+ {
+ for (uint32_t k = i + 1; k < nrange_input; ++k)
+ {
+ vrange_input[k - 1] = vrange_input[k];
+ };
+ --nrange_input;
+ };
+ };
+ if (nrange_input == 0) return range<Value_t *>(dest.first, dest.first);
+ if (nrange_input == 1) return move_construct(dest, vrange_input[0]);
+ if (nrange_input == 2)
+ {
+ return merge_construct(dest, vrange_input[0], vrange_input[1], comp);
+ };
+
+ //------------------------------------------------------------------------
+ // Initial sort
+ //------------------------------------------------------------------------
+ uint32_t pos[4] = { 0, 1, 2, 3 }, npos = nrange_input;
+
+ //-----------------------------------------------------------------------
+ // thanks to Steven Ross by their suggestion about the optimal
+ // sorting networks
+ //-----------------------------------------------------------------------
+ if (less_range(vrange_input[pos[1]].first, pos[1],
+ vrange_input[pos[0]].first, pos[0], comp))
+ {
+ std::swap(pos[0], pos[1]);
+ };
+ if (npos == 4 and less_range(vrange_input[pos[3]].first, pos[3],
+ vrange_input[pos[2]].first, pos[2], comp))
+ {
+ std::swap(pos[3], pos[2]);
+ };
+ if (less_range(vrange_input[pos[2]].first, pos[2],
+ vrange_input[pos[0]].first, pos[0], comp))
+ {
+ std::swap(pos[0], pos[2]);
+ };
+ if (npos == 4 and less_range(vrange_input[pos[3]].first, pos[3],
+ vrange_input[pos[1]].first, pos[1], comp))
+ {
+ std::swap(pos[1], pos[3]);
+ };
+ if (less_range(vrange_input[pos[2]].first, pos[2],
+ vrange_input[pos[1]].first, pos[1], comp))
+ {
+ std::swap(pos[1], pos[2]);
+ };
+
+ Value_t *it_dest = dest.first;
+ while (npos > 2)
+ {
+ util::construct_object(&(*(it_dest++)),
+ std::move(*(vrange_input[pos[0]].first++)));
+ if (vrange_input[pos[0]].size() == 0)
+ {
+ pos[0] = pos[1];
+ pos[1] = pos[2];
+ pos[2] = pos[3];
+ --npos;
+ }
+ else
+ {
+ if (less_range (vrange_input[pos[1]].first, pos[1],
+ vrange_input[pos[0]].first, pos[0], comp))
+ {
+ std::swap(pos[0], pos[1]);
+ if (less_range (vrange_input[pos[2]].first, pos[2],
+ vrange_input[pos[1]].first, pos[1], comp))
+ {
+ std::swap(pos[1], pos[2]);
+ if (npos == 4 and less_range(vrange_input[pos[3]].first,
+ pos[3],
+ vrange_input[pos[2]].first,
+ pos[2], comp))
+ {
+ std::swap(pos[2], pos[3]);
+ };
+ };
+ };
+ };
+ }; // end while (npos > 2)
+
+ range<Value_t *> raux1(dest.first, it_dest), raux2(it_dest, dest.last);
+ if (pos[0] < pos[1])
+ {
+ return concat(raux1,
+ merge_construct(raux2, vrange_input[pos[0]],
+ vrange_input[pos[1]], comp));
+ }
+ else
+ {
+ return concat(raux1,
+ merge_construct(raux2, vrange_input[pos[1]],
+ vrange_input[pos[0]], comp));
+ };
+};
+
+//****************************************************************************
+};// End namespace common
+};// End namespace sort
+};// End namespace boost
+//****************************************************************************
+//
+#endif
diff --git a/boost/sort/common/merge_vector.hpp b/boost/sort/common/merge_vector.hpp
new file mode 100644
index 0000000000..84afea5a5e
--- /dev/null
+++ b/boost/sort/common/merge_vector.hpp
@@ -0,0 +1,196 @@
+//----------------------------------------------------------------------------
+/// @file merge_vector.hpp
+/// @brief In this file have the functions for to do a stable merge of
+// ranges, in a vector
+///
+/// @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_UTIL_MERGE_VECTOR_HPP
+#define __BOOST_SORT_PARALLEL_DETAIL_UTIL_MERGE_VECTOR_HPP
+
+#include <boost/sort/common/merge_four.hpp>
+#include <functional>
+#include <iterator>
+#include <memory>
+#include <type_traits>
+#include <vector>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+
+//############################################################################
+// ##
+// F U S I O N O F ##
+// ##
+// A V E C T O R O F R A N G E S ##
+// ##
+//############################################################################
+
+//
+//-----------------------------------------------------------------------------
+// function : merge_level4
+/// @brief merge the ranges in the vector v_input with the full_merge4 function.
+/// The v_output vector is used as auxiliary memory in the internal
+/// process. The final results is in the dest range.
+/// All the ranges of v_output are inside the range dest
+/// @param dest : range where move the elements merged
+/// @param v_input : vector of ranges to merge
+/// @param v_output : vector of ranges obtained
+/// @param comp : comparison object
+/// @return range with all the elements moved
+//-----------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, class Compare>
+void merge_level4(range<Iter1_t> dest, std::vector<range<Iter2_t> > &v_input,
+ std::vector<range<Iter1_t> > &v_output, Compare comp)
+{
+ typedef range<Iter1_t> range1_t;
+ typedef util::value_iter<Iter1_t> type1;
+ typedef util::value_iter<Iter2_t> type2;
+ static_assert (std::is_same< type1, type2 >::value,
+ "Incompatible iterators\n");
+
+ v_output.clear();
+ if (v_input.size() == 0) return;
+ if (v_input.size() == 1)
+ {
+ v_output.emplace_back(move_forward(dest, v_input[0]));
+ return;
+ };
+
+ uint32_t nrange = v_input.size();
+ uint32_t pos_ini = 0;
+ while (pos_ini < v_input.size())
+ {
+ uint32_t nmerge = (nrange + 3) >> 2;
+ uint32_t nelem = (nrange + nmerge - 1) / nmerge;
+ range1_t rz = full_merge4(dest, &v_input[pos_ini], nelem, comp);
+ v_output.emplace_back(rz);
+ dest.first = rz.last;
+ pos_ini += nelem;
+ nrange -= nelem;
+ };
+ return;
+};
+//
+//-----------------------------------------------------------------------------
+// function : uninit_merge_level4
+/// @brief merge the ranges moving the objects and constructing them in
+/// uninitialized memory, in the vector v_input
+/// using full_merge4. The v_output vector is used as auxiliary memory
+/// in the internal process. The final results is in the dest range.
+/// All the ranges of v_output are inside the range dest
+///
+/// @param dest : range where move the elements merged
+/// @param v_input : vector of ranges to merge
+/// @param v_output : vector of ranges obtained
+/// @param comp : comparison object
+/// @return range with all the elements moved and constructed
+//-----------------------------------------------------------------------------
+template<class Value_t, class Iter_t, class Compare>
+void uninit_merge_level4(range<Value_t *> dest,
+ std::vector<range<Iter_t> > &v_input,
+ std::vector<range<Value_t *> > &v_output, Compare comp)
+{
+ typedef range<Value_t *> range1_t;
+ typedef util::value_iter<Iter_t> type1;
+ static_assert (std::is_same< type1, Value_t >::value,
+ "Incompatible iterators\n");
+
+ v_output.clear();
+ if (v_input.size() == 0) return;
+ if (v_input.size() == 1)
+ {
+ v_output.emplace_back(move_construct(dest, v_input[0]));
+ return;
+ };
+
+ uint32_t nrange = v_input.size();
+ uint32_t pos_ini = 0;
+ while (pos_ini < v_input.size())
+ {
+ uint32_t nmerge = (nrange + 3) >> 2;
+ uint32_t nelem = (nrange + nmerge - 1) / nmerge;
+ range1_t rz = uninit_full_merge4(dest, &v_input[pos_ini], nelem, comp);
+ v_output.emplace_back(rz);
+ dest.first = rz.last;
+ pos_ini += nelem;
+ nrange -= nelem;
+ };
+ return;
+};
+//
+//-----------------------------------------------------------------------------
+// function : merge_vector4
+/// @brief merge the ranges in the vector v_input using the merge_level4
+/// function. The v_output vector is used as auxiliary memory in the
+/// internal process
+/// The final results is in the range_output range.
+/// All the ranges of v_output are inside the range range_output
+/// All the ranges of v_input are inside the range range_input
+/// @param range_input : range including all the ranges of v_input
+/// @param ange_output : range including all the elements of v_output
+/// @param v_input : vector of ranges to merge
+/// @param v_output : vector of ranges obtained
+/// @param comp : comparison object
+/// @return range with all the elements moved
+//-----------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, class Compare>
+range<Iter2_t> merge_vector4(range<Iter1_t> range_input,
+ range<Iter2_t> range_output,
+ std::vector<range<Iter1_t> > &v_input,
+ std::vector<range<Iter2_t> > &v_output,
+ Compare comp)
+{
+ typedef range<Iter2_t> range2_t;
+ typedef util::value_iter<Iter1_t> type1;
+ typedef util::value_iter<Iter2_t> type2;
+ static_assert (std::is_same< type1, type2 >::value,
+ "Incompatible iterators\n");
+
+ v_output.clear();
+ if (v_input.size() == 0)
+ {
+ return range2_t(range_output.first, range_output.first);
+ };
+ if (v_input.size() == 1)
+ {
+ return move_forward(range_output, v_input[0]);
+ };
+ bool sw = false;
+ uint32_t nrange = v_input.size();
+
+ while (nrange > 1)
+ {
+ if (sw)
+ {
+ merge_level4(range_input, v_output, v_input, comp);
+ sw = false;
+ nrange = v_input.size();
+ }
+ else
+ {
+ merge_level4(range_output, v_input, v_output, comp);
+ sw = true;
+ nrange = v_output.size();
+ };
+ };
+ return (sw) ? v_output[0] : move_forward(range_output, v_input[0]);
+};
+
+//****************************************************************************
+};// End namespace common
+};// End namespace sort
+};// End namespace boost
+//****************************************************************************
+//
+#endif
diff --git a/boost/sort/common/pivot.hpp b/boost/sort/common/pivot.hpp
new file mode 100644
index 0000000000..5182fbd273
--- /dev/null
+++ b/boost/sort/common/pivot.hpp
@@ -0,0 +1,122 @@
+//----------------------------------------------------------------------------
+/// @file pivot.hpp
+/// @brief This file contains the description of several low level algorithms
+///
+/// @author Copyright (c) 2010 2015 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_COMMON_PIVOT_HPP
+#define __BOOST_SORT_COMMON_PIVOT_HPP
+
+#include <cstdint>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+//
+//##########################################################################
+// ##
+// G L O B A L V A R I B L E S ##
+// ##
+//##########################################################################
+//
+//-----------------------------------------------------------------------------
+// function : mid3
+/// @brief : return the iterator to the mid value of the three values passsed
+/// as parameters
+//
+/// @param iter_1 : iterator to the first value
+/// @param iter_2 : iterator to the second value
+/// @param iter_3 : iterator to the third value
+/// @param comp : object for to compare two values
+/// @return iterator to mid value
+//-----------------------------------------------------------------------------
+template < typename Iter_t, typename Compare >
+inline Iter_t mid3 (Iter_t iter_1, Iter_t iter_2, Iter_t iter_3, Compare comp)
+{
+ return comp (*iter_1, *iter_2)
+ ? (comp (*iter_2, *iter_3)?
+ iter_2 : (comp (*iter_1, *iter_3) ? iter_3 : iter_1))
+ : (comp (*iter_3, *iter_2)?
+ iter_2 : (comp (*iter_3, *iter_1) ? iter_3 : iter_1));
+};
+//
+//-----------------------------------------------------------------------------
+// function : pivot3
+/// @brief : receive a range between first and last, calcule the mid iterator
+/// with the first, the previous to the last, and the central
+/// position. With this mid iterator swap with the first position
+//
+/// @param first : iterator to the first element
+/// @param last : iterator to the last element
+/// @param comp : object for to compare two elements
+//-----------------------------------------------------------------------------
+template < class Iter_t, class Compare >
+inline void pivot3 (Iter_t first, Iter_t last, Compare comp)
+{
+ auto N2 = (last - first) >> 1;
+ Iter_t it_val = mid3 (first + 1, first + N2, last - 1, comp);
+ std::swap (*first, *it_val);
+};
+
+//
+//-----------------------------------------------------------------------------
+// function : mid9
+/// @brief : return the iterator to the mid value of the nine values passsed
+/// as parameters
+//
+/// @param iter_1 : iterator to the first value
+/// @param iter_2 : iterator to the second value
+/// @param iter_3 : iterator to the third value
+/// @param iter_4 : iterator to the fourth value
+/// @param iter_5 : iterator to the fifth value
+/// @param iter_6 : iterator to the sixth value
+/// @param iter_7 : iterator to the seventh value
+/// @param iter_8 : iterator to the eighth value
+/// @param iter_9 : iterator to the ninth value
+/// @return iterator to the mid value
+//-----------------------------------------------------------------------------
+template < class Iter_t, class Compare >
+inline Iter_t mid9 (Iter_t iter_1, Iter_t iter_2, Iter_t iter_3, Iter_t iter_4,
+ Iter_t iter_5, Iter_t iter_6, Iter_t iter_7, Iter_t iter_8,
+ Iter_t iter_9, Compare comp)
+{
+ return mid3 (mid3 (iter_1, iter_2, iter_3, comp),
+ mid3 (iter_4, iter_5, iter_6, comp),
+ mid3 (iter_7, iter_8, iter_9, comp), comp);
+};
+//
+//-----------------------------------------------------------------------------
+// function : pivot9
+/// @brief : receive a range between first and last, obtain 9 values between
+/// the elements including the first and the previous to the last.
+/// Obtain the iterator to the mid value and swap with the first
+/// position
+//
+/// @param first : iterator to the first element
+/// @param last : iterator to the last element
+/// @param comp : object for to compare two elements
+//-----------------------------------------------------------------------------
+template < class Iter_t, class Compare >
+inline void pivot9 (Iter_t first, Iter_t last, Compare comp)
+{
+ size_t cupo = (last - first) >> 3;
+ Iter_t itaux = mid9 (first + 1, first + cupo, first + 2 * cupo,
+ first + 3 * cupo, first + 4 * cupo, first + 5 * cupo,
+ first + 6 * cupo, first + 7 * cupo, last - 1, comp);
+ std::swap (*first, *itaux);
+};
+//****************************************************************************
+}; // End namespace common
+}; // End namespace sort
+}; // End namespace boost
+//****************************************************************************
+#endif
diff --git a/boost/sort/common/range.hpp b/boost/sort/common/range.hpp
new file mode 100644
index 0000000000..072d98a938
--- /dev/null
+++ b/boost/sort/common/range.hpp
@@ -0,0 +1,399 @@
+//----------------------------------------------------------------------------
+/// @file range.hpp
+/// @brief Define a range [first, last), and the associated operations
+///
+/// @author Copyright (c) 2016 Francisco José Tapia (fjtapia@gmail.com )\n
+/// Distributed under the Boost Software License, Version 1.0.\n
+/// ( See accompanyingfile LICENSE_1_0.txt or copy at
+/// http://www.boost.org/LICENSE_1_0.txt )
+/// @version 0.1
+///
+/// @remarks
+//-----------------------------------------------------------------------------
+#ifndef __BOOST_SORT_PARALLEL_DETAIL_UTIL_RANGE_HPP
+#define __BOOST_SORT_PARALLEL_DETAIL_UTIL_RANGE_HPP
+
+#include <boost/sort/common/util/algorithm.hpp>
+#include <boost/sort/common/util/merge.hpp>
+#include <boost/sort/common/util/traits.hpp>
+#include <cassert>
+#include <functional>
+#include <memory>
+#include <vector>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+
+///---------------------------------------------------------------------------
+/// @struct range
+/// @brief this represent a range between two iterators
+/// @remarks
+//----------------------------------------------------------------------------
+template <class Iter_t>
+struct range
+{
+ Iter_t first, last;
+ //
+ //------------------------------------------------------------------------
+ // function : range
+ /// @brief empty constructor
+ //------------------------------------------------------------------------
+ range(void) { };
+ //
+ //------------------------------------------------------------------------
+ // function : range
+ /// @brief constructor with two parameters
+ /// @param frs : iterator to the first element
+ /// @param lst : iterator to the last element
+ //-----------------------------------------------------------------------
+ range(const Iter_t &frs, const Iter_t &lst): first(frs), last(lst) { };
+ //
+ //-----------------------------------------------------------------------
+ // function : empty
+ /// @brief indicate if the range is empty
+ /// @return true : empty false : not empty
+ //-----------------------------------------------------------------------
+ bool empty(void) const { return (first == last); };
+ //
+ //-----------------------------------------------------------------------
+ // function : not_empty
+ /// @brief indicate if the range is not empty
+ /// @return true : not empty false : empty
+ //-----------------------------------------------------------------------
+ bool not_empty(void) const {return (first != last); };
+ //
+ //-----------------------------------------------------------------------
+ // function : valid
+ /// @brief Indicate if the range is well constructed, and valid
+ /// @return true : valid, false : not valid
+ //-----------------------------------------------------------------------
+ bool valid(void) const { return ((last - first) >= 0); };
+ //
+ //-----------------------------------------------------------------------
+ // function : size
+ /// @brief return the size of the range
+ /// @return size
+ //-----------------------------------------------------------------------
+ size_t size(void) const { return (last - first); };
+ //
+ //------------------------------------------------------------------------
+ // function : front
+ /// @brief return an iterator to the first element of the range
+ /// @return iterator
+ //-----------------------------------------------------------------------
+ Iter_t front(void) const { return first; };
+ //
+ //-------------------------------------------------------------------------
+ // function : back
+ /// @brief return an iterator to the last element of the range
+ /// @return iterator
+ //-------------------------------------------------------------------------
+ Iter_t back(void) const {return (last - 1); };
+};
+
+//
+//-----------------------------------------------------------------------------
+// function : concat
+/// @brief concatenate two contiguous ranges
+/// @param it1 : first range
+/// @param it2 : second range
+/// @return range resulting of the concatenation
+//-----------------------------------------------------------------------------
+template<class Iter_t>
+inline range<Iter_t> concat(const range<Iter_t> &it1, const range<Iter_t> &it2)
+{
+ return range<Iter_t>(it1.first, it2.last);
+}
+;
+//
+//-----------------------------------------------------------------------------
+// function : move_forward
+/// @brief Move initialized objets from the range src to dest
+/// @param dest : range where move the objects
+/// @param src : range from where move the objects
+/// @return range with the objects moved and the size adjusted
+//-----------------------------------------------------------------------------
+template <class Iter1_t, class Iter2_t>
+inline range<Iter2_t> move_forward(const range<Iter2_t> &dest,
+ const range<Iter1_t> &src)
+{
+ assert(dest.size() >= src.size());
+ Iter2_t it_aux = util::move_forward(dest.first, src.first, src.last);
+ return range<Iter2_t>(dest.first, it_aux);
+};
+//
+//-----------------------------------------------------------------------------
+// function : move_backward
+/// @brief Move initialized objets from the range src to dest
+/// @param dest : range where move the objects
+/// @param src : range from where move the objects
+/// @return range with the objects moved and the size adjusted
+//-----------------------------------------------------------------------------
+template <class Iter1_t, class Iter2_t>
+inline range<Iter2_t> move_backward(const range<Iter2_t> &dest,
+ const range<Iter1_t> &src)
+{
+ assert(dest.size() >= src.size());
+ Iter2_t it_aux = util::move_backward(dest.first + src.size(), src.first,
+ src.last);
+ return range<Iter2_t>(dest.first, dest.src.size());
+};
+
+//-----------------------------------------------------------------------------
+// function : uninit_move
+/// @brief Move uninitialized objets from the range src creating them in dest
+///
+/// @param dest : range where move and create the objects
+/// @param src : range from where move the objects
+/// @return range with the objects moved and the size adjusted
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Value_t = util::value_iter<Iter_t> >
+inline range<Value_t*> move_construct(const range<Value_t*> &dest,
+ const range<Iter_t> &src)
+{
+ Value_t *ptr_aux = util::move_construct(dest.first, src.first, src.last);
+ return range<Value_t*>(dest.first, ptr_aux);
+};
+//
+//-----------------------------------------------------------------------------
+// function : destroy
+/// @brief destroy a range of objects
+/// @param rng : range to destroy
+//-----------------------------------------------------------------------------
+template<class Iter_t>
+inline void destroy(range<Iter_t> rng)
+{
+ util::destroy(rng.first, rng.last);
+};
+//
+//-----------------------------------------------------------------------------
+// function : initialize
+/// @brief initialize a range of objects with the object val moving across them
+/// @param rng : range of elements not initialized
+/// @param val : object used for the initialization
+/// @return range initialized
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Value_t = util::value_iter<Iter_t> >
+inline range<Iter_t> initialize(const range<Iter_t> &rng, Value_t &val)
+{
+ util::initialize(rng.first, rng.last, val);
+ return rng;
+};
+//
+//-----------------------------------------------------------------------------
+// function : is_mergeable
+/// @brief : indicate if two ranges have a possible merge
+/// @param src1 : first range
+/// @param src2 : second range
+/// @param comp : object for to compare elements
+/// @return true : they can be merged
+/// false : they can't be merged
+//-----------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, class Compare>
+inline bool is_mergeable(const range<Iter1_t> &src1, const range<Iter2_t> &src2,
+ Compare comp)
+{
+ //------------------------------------------------------------------------
+ // Metaprogramming
+ //------------------------------------------------------------------------
+ typedef util::value_iter<Iter1_t> type1;
+ typedef util::value_iter<Iter2_t> type2;
+ static_assert (std::is_same< type1, type2 >::value,
+ "Incompatible iterators\n");
+ //------------------------------------------------------------------------
+ // Code
+ //------------------------------------------------------------------------
+ return comp(*(src2.front()), *(src1.back()));
+};
+//
+//-----------------------------------------------------------------------------
+// function : is_mergeable_stable
+/// @brief : indicate if two ranges have a possible merge
+/// @param src1 : first range
+/// @param src2 : second range
+/// @param comp : object for to compare elements
+/// @return true : they can be merged
+/// false : they can't be merged
+//-----------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, class Compare>
+inline bool is_mergeable_stable(const range<Iter1_t> &src1,
+ const range<Iter2_t> &src2, Compare comp)
+{
+ //------------------------------------------------------------------------
+ // Metaprogramming
+ //------------------------------------------------------------------------
+ typedef util::value_iter<Iter1_t> type1;
+ typedef util::value_iter<Iter2_t> type2;
+ static_assert (std::is_same< type1, type2 >::value,
+ "Incompatible iterators\n");
+ //------------------------------------------------------------------------
+ // Code
+ //------------------------------------------------------------------------
+ return not comp(*(src1.back()), *(src2.front()));
+};
+//
+//-----------------------------------------------------------------------------
+// function : merge
+/// @brief Merge two contiguous ranges src1 and src2, and put the result in
+/// the range dest, returning the range merged
+///
+/// @param dest : range where locate the lements merged. the size of dest
+/// must be greater or equal than the sum of the sizes of
+/// src1 and src2
+/// @param src1 : first range to merge
+/// @param src2 : second range to merge
+/// @param comp : comparison object
+/// @return range with the elements merged and the size adjusted
+//-----------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, class Iter3_t, class Compare>
+inline range<Iter3_t> merge(const range<Iter3_t> &dest,
+ const range<Iter1_t> &src1,
+ const range<Iter2_t> &src2, Compare comp)
+{
+ Iter3_t it_aux = util::merge(src1.first, src1.last, src2.first, src2.last,
+ dest.first, comp);
+ return range<Iter3_t>(dest.first, it_aux);
+};
+
+//-----------------------------------------------------------------------------
+// function : merge_construct
+/// @brief Merge two contiguous uninitialized ranges src1 and src2, and create
+/// and move the result in the uninitialized range dest, returning the
+/// range merged
+//
+/// @param dest : range where locate the elements merged. the size of dest
+/// must be greater or equal than the sum of the sizes of
+/// src1 and src2. Initially is uninitialize memory
+/// @param src1 : first range to merge
+/// @param src2 : second range to merge
+/// @param comp : comparison object
+/// @return range with the elements merged and the size adjusted
+//-----------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, class Value_t, class Compare>
+inline range<Value_t *> merge_construct(const range<Value_t *> &dest,
+ const range<Iter1_t> &src1,
+ const range<Iter2_t> &src2,
+ Compare comp)
+{
+ Value_t * ptr_aux = util::merge_construct(src1.first, src1.last, src2.first,
+ src2.last, dest.first, comp);
+ return range<Value_t*>(dest.first, ptr_aux);
+};
+//
+//---------------------------------------------------------------------------
+// function : half_merge
+/// @brief : Merge two initialized buffers. The first buffer is in a separate
+/// memory
+//
+/// @param dest : range where finish the two buffers merged
+/// @param src1 : first range to merge in a separate memory
+/// @param src2 : second range to merge, in the final part of the
+/// range where deposit the final results
+/// @param comp : object for compare two elements of the type pointed
+/// by the Iter1_t and Iter2_t
+/// @return : range with the two buffers merged
+//---------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, class Compare>
+inline range<Iter2_t> merge_half(const range<Iter2_t> &dest,
+ const range<Iter1_t> &src1,
+ const range<Iter2_t> &src2, Compare comp)
+{
+ Iter2_t it_aux = util::merge_half(src1.first, src1.last, src2.first,
+ src2.last, dest.first, comp);
+ return range<Iter2_t>(dest.first, it_aux);
+};
+//
+//-----------------------------------------------------------------------------
+// function : merge_uncontiguous
+/// @brief : merge two non contiguous ranges src1, src2, using the range
+/// aux as auxiliary memory. The results are in the original ranges
+//
+/// @param src1 : first range to merge
+/// @param src2 : second range to merge
+/// @param aux : auxiliary range used in the merge
+/// @param comp : object for to compare elements
+/// @return true : not changes done, false : changes in the buffers
+//-----------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, class Iter3_t, class Compare>
+inline bool merge_uncontiguous(const range<Iter1_t> &src1,
+ const range<Iter2_t> &src2,
+ const range<Iter3_t> &aux, Compare comp)
+{
+ return util::merge_uncontiguous(src1.first, src1.last, src2.first,
+ src2.last, aux.first, comp);
+};
+//
+//-----------------------------------------------------------------------------
+// function : merge_contiguous
+/// @brief : merge two contiguous ranges ( src1, src2) using buf as
+/// auxiliary memory. The results are in the same ranges
+/// @param src1 : first range to merge
+/// @param src1 : second range to merge
+/// @param buf : auxiliary memory used in the merge
+/// @param comp : object for to compare elements
+/// @return true : not changes done, false : changes in the buffers
+//-----------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, class Compare>
+inline range<Iter1_t> merge_contiguous(const range<Iter1_t> &src1,
+ const range<Iter1_t> &src2,
+ const range<Iter2_t> &buf, Compare comp)
+{
+ util::merge_contiguous(src1.first, src1.last, src2.last, buf.first, comp);
+ return concat(src1, src2);
+};
+//
+//-----------------------------------------------------------------------------
+// function : merge_flow
+/// @brief : merge two ranges, as part of a merge the ranges in a list. This
+/// function reduce the number of movements compared with inplace_merge
+/// when you need to merge a sequence of ranges.
+/// This function merge the ranges rbuf and rng2, and the results
+/// are in rng1 and rbuf
+//
+/// @param rng1 : range where locate the first elements of the merge
+/// @param rbuf : range which provide the first elements, and where store
+/// the last results of the merge
+/// @param rng2 : range which provide the last elements to merge
+/// @param comp : object for to compare elements
+/// @return true : not changes done, false : changes in the buffers
+//-----------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, class Compare>
+static void merge_flow(range<Iter1_t> rng1, range<Iter2_t> rbuf,
+ range<Iter1_t> rng2, Compare cmp)
+{
+ //-------------------------------------------------------------------------
+ // Metaprogramming
+ //-------------------------------------------------------------------------
+ typedef util::value_iter<Iter1_t> type1;
+ typedef util::value_iter<Iter2_t> type2;
+ static_assert (std::is_same< type1, type2 >::value,
+ "Incompatible iterators\n");
+
+ //-------------------------------------------------------------------------
+ // Code
+ //-------------------------------------------------------------------------
+ range<Iter2_t> rbx(rbuf);
+ range<Iter1_t> rx1(rng1), rx2(rng2);
+ assert(rbx.size() == rx1.size() and rx1.size() == rx2.size());
+ while (rx1.first != rx1.last)
+ {
+ *(rx1.first++) = (cmp(*rbx.first, *rx2.first)) ?
+ std::move(*(rbx.first++)):
+ std::move(*(rx2.first++));
+ };
+ if (rx2.first == rx2.last) return;
+ if (rbx.first == rbx.last) move_forward(rbuf, rng2);
+ else merge_half(rbuf, rx2, rbx, cmp);
+};
+
+//****************************************************************************
+};// End namespace common
+};// End namespace sort
+};// End namespace boost
+//****************************************************************************
+//
+#endif
diff --git a/boost/sort/common/rearrange.hpp b/boost/sort/common/rearrange.hpp
new file mode 100644
index 0000000000..5c65c4f2b7
--- /dev/null
+++ b/boost/sort/common/rearrange.hpp
@@ -0,0 +1,168 @@
+//----------------------------------------------------------------------------
+/// @file rearrange.hpp
+/// @brief Indirect 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_COMMON_REARRANGE_HPP
+#define __BOOST_SORT_COMMON_REARRANGE_HPP
+
+//#include <boost/sort/common/atomic.hpp>
+#include <boost/sort/common/util/traits.hpp>
+#include <functional>
+#include <iterator>
+#include <type_traits>
+#include <vector>
+#include <cassert>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+
+template<class Iter_data>
+struct filter_iterator
+{
+ //-----------------------------------------------------------------------
+ // Variables
+ //-----------------------------------------------------------------------
+ Iter_data origin;
+
+ //-----------------------------------------------------------------------
+ // Functions
+ //-----------------------------------------------------------------------
+ filter_iterator(Iter_data global_first): origin(global_first) { };
+ size_t operator ()(Iter_data itx) const
+ {
+ return size_t(itx - origin);
+ }
+};
+
+struct filter_pos
+{
+ size_t operator ()(size_t pos) const { return pos; };
+};
+
+//
+//-----------------------------------------------------------------------------
+// function : rearrange
+/// @brief This function transform a logical sort of the elements in the index
+/// of iterators in a physical sort.
+//
+/// @param global_first : iterator to the first element of the data
+/// @param [in] index : vector of the iterators
+//-----------------------------------------------------------------------------
+template<class Iter_data, class Iter_index, class Filter_pos>
+void rearrange(Iter_data global_first, Iter_index itx_first,
+ Iter_index itx_last, Filter_pos pos)
+{
+ //-----------------------------------------------------------------------
+ // Metaprogramming
+ //-----------------------------------------------------------------------
+ typedef util::value_iter<Iter_data> value_data;
+ typedef util::value_iter<Iter_index> value_index;
+
+ //-------------------------------------------------------------------------
+ // Code
+ //-------------------------------------------------------------------------
+ assert((itx_last - itx_first) >= 0);
+ size_t pos_dest, pos_src, pos_ini;
+ size_t nelem = size_t(itx_last - itx_first);
+ Iter_data data = global_first;
+ Iter_index index = itx_first;
+
+ pos_ini = 0;
+ while (pos_ini < nelem)
+ {
+ while (pos_ini < nelem and pos(index[pos_ini]) == pos_ini)
+ ++pos_ini;
+ if (pos_ini == nelem) return;
+ pos_dest = pos_src = pos_ini;
+ value_data aux = std::move(data[pos_ini]);
+ value_index itx_src = std::move(index[pos_ini]);
+
+ while ((pos_src = pos(itx_src)) != pos_ini)
+ {
+ data[pos_dest] = std::move(data[pos_src]);
+ std::swap(itx_src, index[pos_src]);
+ pos_dest = pos_src;
+ };
+
+ data[pos_dest] = std::move(aux);
+ index[pos_ini] = std::move(itx_src);
+ ++pos_ini;
+ };
+};
+
+/*
+ //
+ //-----------------------------------------------------------------------------
+ // function : rearrange_pos
+ /// @brief This function transform a logical sort of the elements in the index
+ /// of iterators in a physical sort.
+ //
+ /// @param global_first : iterator to the first element of the data
+ /// @param [in] index : vector of the iterators
+ //-----------------------------------------------------------------------------
+ template < class Iter_t, class Number >
+ void rearrange_pos (Iter_t global_first, std::vector< Number> &index)
+ {
+ //-------------------------------------------------------------------------
+ // METAPROGRAMMING AND DEFINITIONS
+ //-------------------------------------------------------------------------
+ static_assert ( std::is_integral<Number>::value, "Incompatible Types");
+ typedef iter_value< Iter_t > value_t;
+
+ //-------------------------------------------------------------------------
+ // CODE
+ //-------------------------------------------------------------------------
+ size_t pos_dest = 0;
+ size_t pos_src = 0;
+ size_t pos_ini = 0;
+ size_t nelem = index.size ( );
+ Iter_t it_dest (global_first), it_src(global_first);
+
+ while (pos_ini < nelem)
+ {
+ while (pos_ini < nelem and
+ index[pos_ini] == pos_ini)
+ {
+ ++pos_ini;
+ };
+
+ if (pos_ini == nelem) return;
+ pos_dest = pos_src = pos_ini;
+ it_dest = global_first + pos_dest;
+ value_t Aux = std::move (*it_dest);
+
+ while ((pos_src = index[pos_dest]) != pos_ini)
+ {
+ index[pos_dest] = it_dest - global_first;
+ it_src = global_first + pos_src;
+ *it_dest = std::move (*it_src);
+ it_dest = it_src;
+ pos_dest = pos_src;
+ };
+
+ *it_dest = std::move (Aux);
+ index[pos_dest] = it_dest - global_first;
+ ++pos_ini;
+ };
+ };
+ */
+//
+//****************************************************************************
+};// End namespace common
+};// End namespace sort
+};// End namespace boost
+//****************************************************************************
+//
+#endif
diff --git a/boost/sort/common/scheduler.hpp b/boost/sort/common/scheduler.hpp
new file mode 100644
index 0000000000..33074a4534
--- /dev/null
+++ b/boost/sort/common/scheduler.hpp
@@ -0,0 +1,276 @@
+//----------------------------------------------------------------------------
+/// @file scheduler.hpp
+/// @brief This file contains the implementation of the scheduler for
+/// dispatch the works stored
+///
+/// @author Copyright (c) 2010 2015 Francisco José Tapia (fjtapia@gmail.com )\n
+/// Distributed under the Boost Software License, Version 1.0.\n
+/// ( See accompanyingfile LICENSE_1_0.txt or copy at
+/// http://www.boost.org/LICENSE_1_0.txt )
+/// @version 0.1
+///
+/// @remarks
+//-----------------------------------------------------------------------------
+#ifndef __BOOST_SORT_COMMON_SCHEDULER_HPP
+#define __BOOST_SORT_COMMON_SCHEDULER_HPP
+
+#include <boost/sort/common/spinlock.hpp>
+#include <boost/sort/common/search.hpp>
+#include <boost/sort/common/compare_traits.hpp>
+#include <scoped_allocator>
+#include <utility>
+#include <vector>
+#include <deque>
+#include <iostream>
+#include <unordered_map>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+
+//
+//###########################################################################
+// ##
+// ################################################################ ##
+// # # ##
+// # C L A S S S C H E D U L E R # ##
+// # # ##
+// ################################################################ ##
+// ##
+//###########################################################################
+
+//
+//---------------------------------------------------------------------------
+/// @class scheduler
+/// @brief This class is a concurrent stack controled by a spin_lock
+/// @remarks
+//---------------------------------------------------------------------------
+template<typename Func_t, typename Allocator = std::allocator<Func_t> >
+struct scheduler
+{
+ //-----------------------------------------------------------------------
+ // D E F I N I T I O N S
+ //-----------------------------------------------------------------------
+ typedef std::scoped_allocator_adaptor <Allocator> scoped_alloc;
+ typedef std::deque <Func_t, scoped_alloc> deque_t;
+ typedef typename deque_t::iterator it_deque;
+ typedef std::thread::id key_t;
+ typedef std::hash <key_t> hash_t;
+ typedef std::equal_to <key_t> equal_t;
+ typedef std::unique_lock <spinlock_t> lock_t;
+ typedef std::unordered_map <key_t, deque_t, hash_t,
+ equal_t, scoped_alloc> map_t;
+ typedef typename map_t::iterator it_map;
+
+ //-----------------------------------------------------------------------
+ // V A R I A B L E S
+ //-----------------------------------------------------------------------
+ map_t mp;
+ size_t nelem;
+ mutable spinlock_t spl;
+
+ //------------------------------------------------------------------------
+ // function : scheduler
+ /// @brief constructor
+ //------------------------------------------------------------------------
+ scheduler(void) : mp(), nelem(0) { };
+ //
+ //-----------------------------------------------------------------------
+ // function : scheduler
+ /// @brief Copy & move constructor
+ /// @param [in] VT : stack_cnc from where copy the data
+ //-----------------------------------------------------------------------
+ scheduler(scheduler && VT) = delete;
+ scheduler(const scheduler & VT) = delete;
+ //
+ //------------------------------------------------------------------------
+ // function : ~scheduler
+ /// @brief Destructor
+ //------------------------------------------------------------------------
+ virtual ~scheduler(void) {mp.clear();};
+ //
+ //------------------------------------------------------------------------
+ // function : operator =
+ /// @brief Asignation operator
+ /// @param [in] VT : stack_cnc from where copy the data
+ /// @return Reference to the stack_cnc after the copy
+ //------------------------------------------------------------------------
+ scheduler & operator=(const scheduler &VT) = delete;
+ //
+ //------------------------------------------------------------------------
+ // function : size
+ /// @brief Asignation operator
+ /// @param [in] VT : stack_cnc from where copy the data
+ /// @return Reference to the stack_cnc after the copy
+ //------------------------------------------------------------------------
+ size_t size(void) const
+ {
+ lock_t s(spl);
+ return nelem;
+ };
+ //
+ //------------------------------------------------------------------------
+ // function : clear
+ /// @brief Delete all the elements of the stack_cnc.
+ //------------------------------------------------------------------------
+ void clear_all(void)
+ {
+ lock_t s(spl);
+ mp.clear();
+ nelem = 0;
+ };
+
+ //
+ //------------------------------------------------------------------------
+ // function : insert
+ /// @brief Insert one element in the back of the container
+ /// @param [in] D : value to insert. Can ve a value, a reference or an
+ /// rvalue
+ /// @return iterator to the element inserted
+ /// @remarks This operation is O ( const )
+ //------------------------------------------------------------------------
+ void insert(Func_t & f)
+ {
+ lock_t s(spl);
+ key_t th_id = std::this_thread::get_id();
+ it_map itmp = mp.find(th_id);
+ if (itmp == mp.end())
+ {
+ auto aux = mp.emplace(th_id, deque_t());
+ if (aux.second == false) throw std::bad_alloc();
+ itmp = aux.first;
+ };
+ itmp->second.emplace_back(std::move(f));
+ nelem++;
+ };
+
+ //
+ //------------------------------------------------------------------------
+ // function :emplace
+ /// @brief Insert one element in the back of the container
+ /// @param [in] args :group of arguments for to build the object to insert
+ /// @return iterator to the element inserted
+ /// @remarks This operation is O ( const )
+ //------------------------------------------------------------------------
+ template<class ... Args>
+ void emplace(Args && ... args)
+ {
+ lock_t s(spl);
+ key_t th_id = std::this_thread::get_id();
+ it_map itmp = mp.find(th_id);
+ if (itmp == mp.end())
+ {
+ auto aux = mp.emplace(th_id, deque_t());
+ if (aux.second == false) throw std::bad_alloc();
+ itmp = aux.first;
+ };
+ itmp->second.emplace_back(std::forward <Args>(args) ...);
+ nelem++;
+ };
+ //
+ //------------------------------------------------------------------------
+ // function : insert
+ /// @brief Insert one element in the back of the container
+ /// @param [in] D : value to insert. Can ve a value, a reference or an rvalue
+ /// @return iterator to the element inserted
+ /// @remarks This operation is O ( const )
+ //------------------------------------------------------------------------
+ template<class it_func>
+ void insert_range(it_func first, it_func last)
+ {
+ //--------------------------------------------------------------------
+ // Metaprogramming
+ //--------------------------------------------------------------------
+ typedef value_iter<it_func> value2_t;
+ static_assert (std::is_same< Func_t, value2_t >::value,
+ "Incompatible iterators\n");
+
+ //--------------------------------------------------------------------
+ // Code
+ //--------------------------------------------------------------------
+ assert((last - first) > 0);
+
+ lock_t s(spl);
+ key_t th_id = std::this_thread::get_id();
+ it_map itmp = mp.find(th_id);
+ if (itmp == mp.end())
+ {
+ auto aux = mp.emplace(th_id, deque_t());
+ if (aux.second == true) throw std::bad_alloc();
+ itmp = aux.first;
+ };
+ while (first != last)
+ {
+ itmp->second.emplace_back(std::move(*(first++)));
+ nelem++;
+ };
+ };
+ //
+ //------------------------------------------------------------------------
+ // function : extract
+ /// @brief erase the last element of the tree and return a copy
+ /// @param [out] V : reference to a variable where copy the element
+ /// @return code of the operation
+ /// 0- Element erased
+ /// 1 - Empty tree
+ /// @remarks This operation is O(1)
+ //------------------------------------------------------------------------
+ bool extract(Func_t & f)
+ {
+ lock_t s(spl);
+ if (nelem == 0) return false;
+ key_t th_id = std::this_thread::get_id();
+ it_map itmp = mp.find(th_id);
+ if (itmp != mp.end() and not itmp->second.empty())
+ {
+ f = std::move(itmp->second.back());
+ itmp->second.pop_back();
+ --nelem;
+ return true;
+ };
+ for (itmp = mp.begin(); itmp != mp.end(); ++itmp)
+ {
+ if (itmp->second.empty()) continue;
+ f = std::move(itmp->second.back());
+ itmp->second.pop_back();
+ --nelem;
+ return true;
+ }
+ return false;
+ };
+};
+// end class scheduler
+//*************************************************************************
+// P R I N T F U N C T I O N S
+//************************************************************************
+template<class ... Args>
+std::ostream & operator <<(std::ostream &out, const std::deque<Args ...> & dq)
+{
+ for (uint32_t i = 0; i < dq.size(); ++i)
+ out << dq[i] << " ";
+ out << std::endl;
+ return out;
+}
+
+template<typename Func_t, typename Allocator = std::allocator<Func_t> >
+std::ostream & operator <<(std::ostream &out,
+ const scheduler<Func_t, Allocator> &sch)
+{
+ std::unique_lock < spinlock_t > s(sch.spl);
+ out << "Nelem :" << sch.nelem << std::endl;
+ for (auto it = sch.mp.begin(); it != sch.mp.end(); ++it)
+ {
+ out << it->first << " :" << it->second << std::endl;
+ }
+ return out;
+}
+
+//***************************************************************************
+};// end namespace common
+};// end namespace sort
+};// end namespace boost
+//***************************************************************************
+#endif
diff --git a/boost/sort/common/sort_basic.hpp b/boost/sort/common/sort_basic.hpp
new file mode 100644
index 0000000000..68a6f54048
--- /dev/null
+++ b/boost/sort/common/sort_basic.hpp
@@ -0,0 +1,334 @@
+//----------------------------------------------------------------------------
+/// @file sort_basic.hpp
+/// @brief Spin Sort algorithm
+///
+/// @author Copyright (c) 2016 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_COMMON_SORT_BASIC_HPP
+#define __BOOST_SORT_COMMON_SORT_BASIC_HPP
+
+//#include <boost/sort/spinsort/util/indirect.hpp>
+#include <boost/sort/insert_sort/insert_sort.hpp>
+#include <boost/sort/common/util/traits.hpp>
+#include <boost/sort/common/range.hpp>
+#include <cstdlib>
+#include <functional>
+#include <iterator>
+#include <memory>
+#include <type_traits>
+#include <vector>
+#include <cstddef>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+
+//----------------------------------------------------------------------------
+// USING SENTENCES
+//----------------------------------------------------------------------------
+using boost::sort::insert_sort;
+
+//-----------------------------------------------------------------------------
+// function : is_stable_sorted_forward
+/// @brief examine the elements in the range first, last if they are stable
+/// sorted, and return an iterator to the first element not sorted
+/// @param first : iterator to the first element in the range
+/// @param last : ierator after the last element of the range
+/// @param comp : object for to compare two elements
+/// @return iterator to the first element not stable sorted. The number of
+/// elements sorted is the iterator returned minus first
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Compare = std::less<value_iter<Iter_t> > >
+inline Iter_t is_stable_sorted_forward (Iter_t first, Iter_t last,
+ Compare comp = Compare())
+{
+#ifdef __BS_DEBUG
+ assert ( (last- first) >= 0);
+#endif
+ if ((last - first) < 2) return first;
+ Iter_t it2 = first + 1;
+ for (Iter_t it1 = first; it2 != last and not comp(*it2, *it1); it1 = it2++);
+ return it2;
+}
+//-----------------------------------------------------------------------------
+// function : is_reverse_stable_sorted_forward
+/// @brief examine the elements in the range first, last if they are reverse
+/// stable sorted, and return an iterator to the first element not
+/// reverse stable sorted
+/// @param first : iterator to the first element in the range
+/// @param last : ierator after the last element of the range
+/// @param comp : object for to compare two elements
+/// @return iterator to the first element not reverse stable sorted. The number
+/// of elements sorted is the iterator returned minus first
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Compare = std::less<value_iter<Iter_t> > >
+inline Iter_t is_reverse_stable_sorted_forward(Iter_t first, Iter_t last,
+ Compare comp = Compare())
+{
+#ifdef __BS_DEBUG
+ assert ( (last- first) >= 0);
+#endif
+ if ((last - first) < 2) return first;
+ Iter_t it2 = first + 1;
+ for (Iter_t it1 = first; it2 != last and comp(*it2, *it1); it1 = it2++);
+ return it2;
+};
+//-----------------------------------------------------------------------------
+// function : number_stable_sorted_forward
+/// @brief examine the elements in the range first, last if they are stable
+/// sorted, and return the number of elements sorted
+/// @param first : iterator to the first element in the range
+/// @param last : ierator after the last element of the range
+/// @param comp : object for to compare two elements
+/// @param min_process : minimal number of elements to be consideer
+/// @return number of element sorted. I f the number is lower than min_process
+/// return 0
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Compare = std::less<value_iter<Iter_t> > >
+size_t number_stable_sorted_forward (Iter_t first, Iter_t last,
+ size_t min_process,
+ Compare comp = Compare())
+{
+#ifdef __BS_DEBUG
+ assert ( (last- first) >= 0);
+#endif
+ if ((last - first) < 2) return 0;
+
+ // sorted elements
+ Iter_t it2 = first + 1;
+ for (Iter_t it1 = first; it2 != last and not comp(*it2, *it1); it1 = it2++);
+ size_t nsorted = size_t ( it2 - first);
+ if ( nsorted != 1)
+ return (nsorted >= min_process) ? nsorted: 0;
+
+ // reverse sorted elements
+ it2 = first + 1;
+ for (Iter_t it1 = first; it2 != last and comp(*it2, *it1); it1 = it2++);
+ nsorted = size_t ( it2 - first);
+
+ if ( nsorted < min_process) return 0 ;
+ util::reverse ( first , it2);
+ return nsorted;
+};
+
+//-----------------------------------------------------------------------------
+// function : is_stable_sorted_backward
+/// @brief examine the elements in the range first, last beginning at end, and
+/// if they are stablesorted, and return an iterator to the last element
+/// sorted
+/// @param first : iterator to the first element in the range
+/// @param last : ierator after the last element of the range
+/// @param comp : object for to compare two elements
+/// @return iterator to the last element stable sorted. The number of
+/// elements sorted is the last minus the iterator returned
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Compare = std::less<value_iter<Iter_t> > >
+inline Iter_t is_stable_sorted_backward(Iter_t first, Iter_t last,
+ Compare comp = Compare())
+{
+#ifdef __BS_DEBUG
+ assert ( (last- first) >= 0);
+#endif
+ if ((last - first) < 2) return first;
+ Iter_t itaux = last - 1;
+ while (itaux != first and not comp(*itaux, *(itaux - 1))) {--itaux; };
+ return itaux;
+}
+//-----------------------------------------------------------------------------
+// function : is_reverse_stable_sorted_backward
+/// @brief examine the elements in the range first, last beginning at end, and
+/// if they are stablesorted, and return an iterator to the last element
+/// sorted
+/// @param first : iterator to the first element in the range
+/// @param last : ierator after the last element of the range
+/// @param comp : object for to compare two elements
+/// @return iterator to the last element stable sorted. The number of
+/// elements sorted is the last minus the iterator returned
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Compare = std::less<value_iter<Iter_t> > >
+inline Iter_t is_reverse_stable_sorted_backward (Iter_t first, Iter_t last,
+ Compare comp = Compare())
+{
+#ifdef __BS_DEBUG
+ assert ( (last- first) >= 0);
+#endif
+ if ((last - first) < 2) return first;
+ Iter_t itaux = last - 1;
+ for (; itaux != first and comp(*itaux, *(itaux - 1)); --itaux);
+ return itaux;
+}
+
+//-----------------------------------------------------------------------------
+// function : number_stable_sorted_backward
+/// @brief examine the elements in the range first, last if they are stable
+/// sorted, and return the number of elements sorted
+/// @param first : iterator to the first element in the range
+/// @param last : ierator after the last element of the range
+/// @param comp : object for to compare two elements
+/// @param min_process : minimal number of elements to be consideer
+/// @return number of element sorted. I f the number is lower than min_process
+/// return 0
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Compare = std::less<value_iter<Iter_t> > >
+size_t number_stable_sorted_backward (Iter_t first, Iter_t last,
+ size_t min_process,
+ Compare comp = Compare())
+{
+#ifdef __BS_DEBUG
+ assert ( (last- first) >= 0);
+#endif
+ if ((last - first) < 2) return 0;
+ Iter_t itaux = last - 1;
+ while (itaux != first and not comp(*itaux, *(itaux - 1))) {--itaux; };
+ size_t nsorted = size_t ( last - itaux);
+ if ( nsorted != 1)
+ return ( nsorted >= min_process)?nsorted: 0 ;
+
+ itaux = last - 1;
+ for (; itaux != first and comp(*itaux, *(itaux - 1)); --itaux);
+ nsorted = size_t ( last - itaux);
+ if ( nsorted < min_process) return 0 ;
+ util::reverse ( itaux, last );
+ return nsorted;
+}
+//-----------------------------------------------------------------------------
+// function : internal_sort
+/// @brief this function divide r_input in two parts, sort it,and merge moving
+/// the elements to range_buf
+/// @param range_input : range with the elements to sort
+/// @param range_buffer : range with the elements sorted
+/// @param comp : object for to compare two elements
+/// @param level : when is 1, sort with the insertionsort algorithm
+/// if not make a recursive call splitting the ranges
+//
+//-----------------------------------------------------------------------------
+template <class Iter1_t, class Iter2_t, class Compare>
+inline void internal_sort (const range<Iter1_t> &rng1,
+ const range<Iter2_t> &rng2,
+ Compare comp, uint32_t level, bool even = true)
+{
+ //-----------------------------------------------------------------------
+ // metaprogram
+ //-----------------------------------------------------------------------
+ typedef value_iter<Iter1_t> value_t;
+ typedef value_iter<Iter2_t> value2_t;
+ static_assert (std::is_same< value_t, value2_t>::value,
+ "Incompatible iterators\n");
+
+ //-----------------------------------------------------------------------
+ // program
+ //-----------------------------------------------------------------------
+#ifdef __BS_DEBUG
+ assert (rng1.size ( ) == rng2.size ( ) );
+#endif
+ size_t nelem = (rng1.size() + 1) >> 1;
+
+ range<Iter1_t> rng1_left(rng1.first, rng1.first + nelem),
+ rng1_right(rng1.first + nelem, rng1.last);
+
+ range<Iter2_t> rng2_left(rng2.first, rng2.first + nelem),
+ rng2_right(rng2.first + nelem, rng2.last);
+
+ if (nelem <= 32 and (level & 1) == even)
+ {
+ insert_sort(rng1_left.first, rng1_left.last, comp);
+ insert_sort(rng1_right.first, rng1_right.last, comp);
+ }
+ else
+ {
+ internal_sort(rng2_left, rng1_left, comp, level + 1, even);
+ internal_sort(rng2_right, rng1_right, comp, level + 1, even);
+ };
+ merge(rng2, rng1_left, rng1_right, comp);
+};
+//-----------------------------------------------------------------------------
+// function : range_sort_data
+/// @brief this sort elements using the range_sort function and receiving a
+/// buffer of initialized memory
+/// @param rng_data : range with the elements to sort
+/// @param rng_aux : range of at least the same memory than rng_data used as
+/// auxiliary memory in the sorting
+/// @param comp : object for to compare two elements
+//-----------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, class Compare>
+static void range_sort_data (const range<Iter1_t> & rng_data,
+ const range<Iter2_t> & rng_aux, Compare comp)
+{
+ //-----------------------------------------------------------------------
+ // metaprogram
+ //-----------------------------------------------------------------------
+ typedef value_iter<Iter1_t> value_t;
+ typedef value_iter<Iter2_t> value2_t;
+ static_assert (std::is_same< value_t, value2_t>::value,
+ "Incompatible iterators\n");
+
+ //------------------------------------------------------------------------
+ // program
+ //------------------------------------------------------------------------
+#ifdef __BS_DEBUG
+ assert ( rng_data.size() == rng_aux.size());
+#endif
+ // minimal number of element before to jump to insertionsort
+ const uint32_t sort_min = 32;
+ if (rng_data.size() <= sort_min)
+ {
+ insert_sort(rng_data.first, rng_data.last, comp);
+ return;
+ };
+
+ internal_sort(rng_aux, rng_data, comp, 0, true);
+};
+//-----------------------------------------------------------------------------
+// function : range_sort_buffer
+/// @brief this sort elements using the range_sort function and receiving a
+/// buffer of initialized memory
+/// @param rng_data : range with the elements to sort
+/// @param rng_aux : range of at least the same memory than rng_data used as
+/// auxiliary memory in the sorting
+/// @param comp : object for to compare two elements
+//-----------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, class Compare>
+static void range_sort_buffer(const range<Iter1_t> & rng_data,
+ const range<Iter2_t> & rng_aux, Compare comp)
+{
+ //-----------------------------------------------------------------------
+ // metaprogram
+ //-----------------------------------------------------------------------
+ typedef value_iter<Iter1_t> value_t;
+ typedef value_iter<Iter2_t> value2_t;
+ static_assert (std::is_same< value_t, value2_t>::value,
+ "Incompatible iterators\n");
+
+ //------------------------------------------------------------------------
+ // program
+ //------------------------------------------------------------------------
+#ifdef __BS_DEBUG
+ assert ( rng_data.size() == rng_aux.size());
+#endif
+ // minimal number of element before to jump to insertionsort
+ const uint32_t sort_min = 32;
+ if (rng_data.size() <= sort_min)
+ {
+ insert_sort(rng_data.first, rng_data.last, comp);
+ move_forward(rng_aux, rng_data);
+ return;
+ };
+
+ internal_sort(rng_data, rng_aux, comp, 0, false);
+};
+//****************************************************************************
+};// End namespace common
+};// End namespace sort
+};// End namepspace boost
+//****************************************************************************
+//
+#endif
diff --git a/boost/sort/common/spinlock.hpp b/boost/sort/common/spinlock.hpp
new file mode 100644
index 0000000000..450ba6b53e
--- /dev/null
+++ b/boost/sort/common/spinlock.hpp
@@ -0,0 +1,88 @@
+//----------------------------------------------------------------------------
+/// @file spinlock_t.hpp
+/// @brief
+///
+/// @author Copyright (c) 2010 2015 Francisco José Tapia (fjtapia@gmail.com )\n
+/// Distributed under the Boost Software License, Version 1.0.\n
+/// ( See accompanyingfile LICENSE_1_0.txt or copy at
+/// http://www.boost.org/LICENSE_1_0.txt )
+/// @version 0.1
+///
+/// @remarks
+//-----------------------------------------------------------------------------
+#ifndef __BOOST_SORT_PARALLEL_DETAIL_UTIL_SPINLOCK_HPP
+#define __BOOST_SORT_PARALLEL_DETAIL_UTIL_SPINLOCK_HPP
+
+#include <atomic>
+#include <ctime>
+#include <functional>
+#include <memory>
+#include <mutex>
+#include <thread>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+//
+//---------------------------------------------------------------------------
+/// @class spinlock_t
+/// @brief This class implement, from atomic variables, a spinlock
+/// @remarks This class meet the BasicLockable requirements ( lock, unlock )
+//---------------------------------------------------------------------------
+class spinlock_t
+{
+ private:
+ //------------------------------------------------------------------------
+ // P R I V A T E V A R I A B L E S
+ //------------------------------------------------------------------------
+ std::atomic_flag af;
+
+ public:
+ //
+ //-------------------------------------------------------------------------
+ // function : spinlock_t
+ /// @brief class constructor
+ /// @param [in]
+ //-------------------------------------------------------------------------
+ explicit spinlock_t ( ) noexcept { af.clear ( ); };
+ //
+ //-------------------------------------------------------------------------
+ // function : lock
+ /// @brief Lock the spinlock_t
+ //-------------------------------------------------------------------------
+ void lock ( ) noexcept
+ {
+ while (af.test_and_set (std::memory_order_acquire))
+ {
+ std::this_thread::yield ( );
+ };
+ };
+ //
+ //-------------------------------------------------------------------------
+ // function : try_lock
+ /// @brief Try to lock the spinlock_t, if not, return false
+ /// @return true : locked
+ /// false: not previous locked
+ //-------------------------------------------------------------------------
+ bool try_lock ( ) noexcept
+ {
+ return not af.test_and_set (std::memory_order_acquire);
+ };
+ //
+ //-------------------------------------------------------------------------
+ // function : unlock
+ /// @brief unlock the spinlock_t
+ //-------------------------------------------------------------------------
+ void unlock ( ) noexcept { af.clear (std::memory_order_release); };
+
+}; // E N D C L A S S S P I N L O C K
+//
+//***************************************************************************
+}; // end namespace common
+}; // end namespace sort
+}; // end namespace boost
+//***************************************************************************
+#endif
diff --git a/boost/sort/common/stack_cnc.hpp b/boost/sort/common/stack_cnc.hpp
new file mode 100644
index 0000000000..d4d6e53b25
--- /dev/null
+++ b/boost/sort/common/stack_cnc.hpp
@@ -0,0 +1,142 @@
+//----------------------------------------------------------------------------
+/// @file stack_cnc.hpp
+/// @brief This file contains the implementation concurrent stack
+///
+/// @author Copyright (c) 2010 2015 Francisco José Tapia (fjtapia@gmail.com )\n
+/// Distributed under the Boost Software License, Version 1.0.\n
+/// ( See accompanyingfile LICENSE_1_0.txt or copy at
+/// http://www.boost.org/LICENSE_1_0.txt )
+/// @version 0.1
+///
+/// @remarks
+//-----------------------------------------------------------------------------
+#ifndef __BOOST_SORT_PARALLEL_DETAIL_UTIL_STACK_CNC_HPP
+#define __BOOST_SORT_PARALLEL_DETAIL_UTIL_STACK_CNC_HPP
+
+#include <boost/sort/common/spinlock.hpp>
+#include <vector>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+
+//
+//###########################################################################
+// ##
+// ################################################################ ##
+// # # ##
+// # C L A S S # ##
+// # S T A C K _ C N C # ##
+// # # ##
+// ################################################################ ##
+// ##
+//###########################################################################
+//
+//---------------------------------------------------------------------------
+/// @class stack_cnc
+/// @brief This class is a concurrent stack controled by a spin_lock
+/// @remarks
+//---------------------------------------------------------------------------
+template<typename T, typename Allocator = std::allocator<T> >
+class stack_cnc
+{
+public:
+ //------------------------------------------------------------------------
+ // D E F I N I T I O N S
+ //------------------------------------------------------------------------
+ typedef std::vector<T, Allocator> vector_t;
+ typedef typename vector_t::size_type size_type;
+ typedef typename vector_t::difference_type difference_type;
+ typedef typename vector_t::value_type value_type;
+ typedef typename vector_t::pointer pointer;
+ typedef typename vector_t::const_pointer const_pointer;
+ typedef typename vector_t::reference reference;
+ typedef typename vector_t::const_reference const_reference;
+ typedef typename vector_t::allocator_type allocator_type;
+ typedef Allocator alloc_t;
+
+protected:
+ //-------------------------------------------------------------------------
+ // INTERNAL VARIABLES
+ //-------------------------------------------------------------------------
+ vector_t v_t;
+ mutable spinlock_t spl;
+
+public:
+ //
+ //-------------------------------------------------------------------------
+ // function : stack_cnc
+ /// @brief constructor
+ //-------------------------------------------------------------------------
+ explicit stack_cnc(void): v_t() { };
+
+ //
+ //-------------------------------------------------------------------------
+ // function : stack_cnc
+ /// @brief Move constructor
+ //-------------------------------------------------------------------------
+ stack_cnc(stack_cnc &&) = delete;
+ //
+ //-------------------------------------------------------------------------
+ // function : ~stack_cnc
+ /// @brief Destructor
+ //-------------------------------------------------------------------------
+ virtual ~stack_cnc(void) { v_t.clear(); };
+
+ //-------------------------------------------------------------------------
+ // function : emplace_back
+ /// @brief Insert one element in the back of the container
+ /// @param args : group of arguments for to build the object to insert. Can
+ /// be values, references or rvalues
+ //-------------------------------------------------------------------------
+ template<class ... Args>
+ void emplace_back(Args &&... args)
+ {
+ std::lock_guard < spinlock_t > guard(spl);
+ v_t.emplace_back(std::forward< Args > (args)...);
+ };
+
+ //
+ //-------------------------------------------------------------------------
+ // function :pop_move_back
+ /// @brief if exist, move the last element to P, and delete it
+ /// @param P : reference to a variable where move the element
+ /// @return true - Element moved and deleted
+ /// false - Empty stack_cnc
+ //-------------------------------------------------------------------------
+ bool pop_move_back(value_type &P)
+ {
+ std::lock_guard < spinlock_t > S(spl);
+ if (v_t.size() == 0) return false;
+ P = std::move(v_t.back());
+ v_t.pop_back();
+ return true;
+ };
+ //-------------------------------------------------------------------------
+ // function : push_back
+ /// @brief Insert one vector at the end of the container
+ /// @param v_other : vector to insert
+ /// @return reference to the stack_cnc after the insertion
+ //-------------------------------------------------------------------------
+ template<class Allocator2>
+ stack_cnc &push_back(const std::vector<value_type, Allocator2> &v_other)
+ {
+ std::lock_guard < spinlock_t > guard(spl);
+ for (size_type i = 0; i < v_other.size(); ++i)
+ {
+ v_t.push_back(v_other[i]);
+ }
+ return *this;
+ };
+};
+// end class stack_cnc
+
+//***************************************************************************
+};// end namespace common
+};// end namespace sort
+};// end namespace boost
+//***************************************************************************
+#endif
diff --git a/boost/sort/common/time_measure.hpp b/boost/sort/common/time_measure.hpp
new file mode 100644
index 0000000000..ef00dd4930
--- /dev/null
+++ b/boost/sort/common/time_measure.hpp
@@ -0,0 +1,62 @@
+//----------------------------------------------------------------------------
+/// @file time_measure.hpp
+/// @brief This class is done in order to simplify the time measure in the
+/// benchmaark programs
+///
+/// @author Copyright (c) 2010 2015 Francisco José Tapia (fjtapia@gmail.com )\n
+/// Distributed under the Boost Software License, Version 1.0.\n
+/// ( See accompanyingfile LICENSE_1_0.txt or copy at
+/// http://www.boost.org/LICENSE_1_0.txt )
+/// @version 0.1
+///
+/// @remarks
+//-----------------------------------------------------------------------------
+#ifndef __BOOST_SORT_PARALLEL_TOOLS_TIME_MEASURE_HPP
+#define __BOOST_SORT_PARALLEL_TOOLS_TIME_MEASURE_HPP
+
+#include <chrono>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+
+namespace chrn = std::chrono;
+//
+//***************************************************************************
+// D E F I N I T I O N S
+//***************************************************************************
+typedef chrn::steady_clock::time_point time_point;
+
+time_point now ( );
+double subtract_time ( const time_point & t1, const time_point & t2 );
+//
+//---------------------------------------------------------------------------
+// function : now
+/// @brief return the time system in a internal format ( steady_clock)
+/// @return time in steady_clock format
+//---------------------------------------------------------------------------
+time_point now ( ) { return chrn::steady_clock::now( ); };
+//
+//---------------------------------------------------------------------------
+// function : subtract_time
+/// @brief return the time in double format
+/// @param [in] t1 : first time in time_point format
+/// @param [in] t2 : second time in time_point format
+/// @return time in seconds of the difference of t1 - t2
+//---------------------------------------------------------------------------
+double subtract_time ( const time_point & t1, const time_point & t2 )
+{ //------------------------ begin ---------------------------------
+ chrn::duration<double> time_span =
+ chrn::duration_cast < chrn::duration < double > > ( t1 - t2 );
+ return time_span.count( );
+};
+
+//***************************************************************************
+};// End namespace benchmark
+};// End namespace sort
+};// End namespace boost
+//***************************************************************************
+#endif
diff --git a/boost/sort/common/util/algorithm.hpp b/boost/sort/common/util/algorithm.hpp
new file mode 100644
index 0000000000..db7607aaeb
--- /dev/null
+++ b/boost/sort/common/util/algorithm.hpp
@@ -0,0 +1,309 @@
+//----------------------------------------------------------------------------
+/// @file algorithm.hpp
+/// @brief low level functions of create, destroy, move and merge functions
+///
+/// @author Copyright (c) 2017 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_COMMON_UTIL_ALGORITHM_HPP
+#define __BOOST_SORT_COMMON_UTIL_ALGORITHM_HPP
+
+#include <algorithm>
+#include <functional>
+#include <iterator>
+#include <memory>
+#include <type_traits>
+#include <vector>
+#include <boost/sort/common/util/traits.hpp>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+namespace util
+{
+//
+//###########################################################################
+//
+// I M P O R T A N T
+//
+// The functions of this file are for internal use only
+// All the operations are done with move operations, because the copy
+// operations are unnecesary
+//
+//###########################################################################
+//
+//----------------------------------------------------------------------------
+//
+// F U N C T I O N S I N T H E F I L E
+//
+//----------------------------------------------------------------------------
+//
+// static inline uint32_t nbits32 (uint32_t num) noexcept
+//
+// static inline uint32_t nbits64 (uint64_t num)
+//
+// template < class Value_t, class... Args >
+// inline void construct_object (Value_t *ptr, Args &&... args)
+//
+// template < class Value_t >
+// inline void destroy_object (Value_t *ptr)
+//
+// template < class Iter_t, class Value_t = value_iter<Iter_t> >
+// void initialize (Iter_t first, Iter_t last, Value_t && val)
+//
+// template < class Iter1_t, class Iter2_t >
+// Iter2_t move_forward (Iter2_t it_dest, Iter1_t first, Iter1_t last)
+//
+// template < class Iter1_t, class Iter2_t >
+// Iter2_t move_backward (Iter2_t it_dest, Iter1_t first, Iter1_t last)
+//
+// template < class Iter_t, class Value_t = value_iter< Iter_t > >
+// Value_t * move_construct (Value_t *ptr, Iter_t first, Iter_t last)
+//
+// template < class Iter_t >
+// void destroy (Iter_t first, const Iter_t last)
+//
+// template < class Iter_t >
+// void reverse (Iter_t first, const Iter_t last)
+//
+//----------------------------------------------------------------------------
+//
+//--------------------------------------------------------------------------
+//
+// G L O B A L V A R I B L E S
+//
+//--------------------------------------------------------------------------
+//
+// this array represent the number of bits needed for to represent the
+// first 256 numbers
+static constexpr const uint32_t tmsb[256] =
+{ 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
+ 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
+ 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7,
+ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
+ 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8,
+ 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
+ 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
+ 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
+ 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
+ 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
+ 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 };
+//
+//---------------------------------------------------------------------------
+//
+// F U N C T I O N S
+//
+//---------------------------------------------------------------------------
+//
+//---------------------------------------------------------------------------
+// function : nbits32
+/// @brief Obtain the number of bits of a number equal or greater than num
+/// @param num : Number to examine
+/// @return Number of bits
+//---------------------------------------------------------------------------
+static inline uint32_t nbits32 (uint32_t num) noexcept
+{
+ int Pos = (num & 0xffff0000U) ? 16 : 0;
+ if ((num >> Pos) & 0xff00U) Pos += 8;
+ return (tmsb[num >> Pos] + Pos);
+}
+//
+//---------------------------------------------------------------------------
+// function : nbits64
+/// @brief Obtain the number of bits of a number equal or greater than num
+/// @param num : Number to examine
+/// @exception none
+/// @return Number of bits
+//---------------------------------------------------------------------------
+static inline uint32_t nbits64(uint64_t num)noexcept
+{
+ uint32_t Pos = (num & 0xffffffff00000000ULL) ? 32 : 0;
+ if ((num >> Pos) & 0xffff0000ULL) Pos += 16;
+ if ((num >> Pos) & 0xff00ULL) Pos += 8;
+ return (tmsb[num >> Pos] + Pos);
+}
+//
+//-----------------------------------------------------------------------------
+// function : construct_object
+/// @brief create an object in the memory specified by ptr
+///
+/// @param ptr : pointer to the memory where to create the object
+/// @param args : arguments to the constructor
+//-----------------------------------------------------------------------------
+template <class Value_t, class ... Args>
+inline void construct_object (Value_t *ptr, Args &&... args)
+{
+ (::new (static_cast<void *>(ptr)) Value_t(std::forward< Args > (args)...));
+};
+//
+//-----------------------------------------------------------------------------
+// function : destroy_object
+/// @brief destroy an object in the memory specified by ptr
+/// @param ptr : pointer to the object to destroy
+//-----------------------------------------------------------------------------
+template<class Value_t>
+inline void destroy_object(Value_t *ptr)
+{
+ ptr->~Value_t();
+};
+//
+//-----------------------------------------------------------------------------
+// function : initialize
+/// @brief initialize a range of objects with the object val moving across them
+///
+/// @param first : itertor to the first element to initialize
+/// @param last : iterator to the last element to initialize
+/// @param val : object used for the initialization
+//-----------------------------------------------------------------------------
+template <class Iter_t, class Value_t = value_iter<Iter_t> >
+inline void initialize (Iter_t first, Iter_t last, Value_t & val)
+{
+ //------------------------------------------------------------------------
+ // Metaprogramming
+ //------------------------------------------------------------------------
+ typedef value_iter<Iter_t> value_t;
+ static_assert (std::is_same< Value_t, value_t >::value,
+ "Incompatible iterators\n");
+
+ //------------------------------------------------------------------------
+ // Code
+ //------------------------------------------------------------------------
+ if (first == last) return;
+ construct_object(&(*first), std::move(val));
+
+ Iter_t it1 = first, it2 = first + 1;
+ while (it2 != last)
+ {
+ construct_object(&(*(it2++)), std::move(*(it1++)));
+ };
+ val = std::move(*(last - 1));
+};
+//
+//-----------------------------------------------------------------------------
+// function : move_forward
+/// @brief Move initialized objets
+/// @param it_dest : iterator to the final place of the objects
+/// @param first : iterator to the first element to move
+/// @param last : iterator to the last element to move
+/// @return Output iterator to the element past the last element
+/// moved (it_dest + (last - first))
+//-----------------------------------------------------------------------------
+template <class Iter1_t, class Iter2_t>
+inline Iter2_t move_forward (Iter2_t it_dest, Iter1_t first, Iter1_t last)
+{
+ //------------------------------------------------------------------------
+ // Metaprogramming
+ //------------------------------------------------------------------------
+ typedef value_iter<Iter1_t> value1_t;
+ typedef value_iter<Iter2_t> value2_t;
+ static_assert (std::is_same< value1_t, value2_t >::value,
+ "Incompatible iterators\n");
+
+ //------------------------------------------------------------------------
+ // Code
+ //------------------------------------------------------------------------
+ while (first != last)
+ { *it_dest++ = std::move(*first++);
+ }
+ return it_dest;
+
+};
+//
+//-----------------------------------------------------------------------------
+// function : move_backard
+/// @brief Move initialized objets in reverse order
+/// @param it_dest : last iterator to the final place of the objects
+/// @param first : iterator to the first element to move
+/// @param last : iterator to the last element to move
+//-----------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t>
+inline Iter2_t move_backward(Iter2_t it_dest, Iter1_t first, Iter1_t last)
+{
+ //------------------------------------------------------------------------
+ // Metaprogramming
+ //------------------------------------------------------------------------
+ typedef value_iter<Iter1_t> value1_t;
+ typedef value_iter<Iter2_t> value2_t;
+ static_assert (std::is_same< value1_t, value2_t >::value,
+ "Incompatible iterators\n");
+
+ //------------------------------------------------------------------------
+ // Code
+ //------------------------------------------------------------------------
+ while (first != last)
+ { *(--it_dest) = std::move (*(--last));
+ }
+ return it_dest;
+};
+
+//
+//-----------------------------------------------------------------------------
+// function : move_construct
+/// @brief Move objets to uninitialized memory
+///
+/// @param ptr : pointer to the memory where to create the objects
+/// @param first : iterator to the first element to move
+/// @param last : iterator to the last element to move
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Value_t = value_iter<Iter_t> >
+inline Value_t * move_construct(Value_t *ptr, Iter_t first, Iter_t last)
+{
+ //------------------------------------------------------------------------
+ // Metaprogramming
+ //------------------------------------------------------------------------
+ typedef typename iterator_traits<Iter_t>::value_type value2_t;
+ static_assert (std::is_same< Value_t, value2_t >::value,
+ "Incompatible iterators\n");
+
+ //------------------------------------------------------------------------
+ // Code
+ //------------------------------------------------------------------------
+ while (first != last)
+ {
+ ::new (static_cast<void *>(ptr++)) Value_t(std::move(*(first++)));
+ };
+ return ptr;
+};
+//
+//-----------------------------------------------------------------------------
+// function : destroy
+/// @brief destroy the elements between first and last
+/// @param first : iterator to the first element to destroy
+/// @param last : iterator to the last element to destroy
+//-----------------------------------------------------------------------------
+template<class Iter_t>
+inline void destroy(Iter_t first, const Iter_t last)
+{
+ while (first != last)
+ destroy_object(&(*(first++)));
+};
+//
+//-----------------------------------------------------------------------------
+// function : reverse
+/// @brief destroy the elements between first and last
+/// @param first : iterator to the first element to destroy
+/// @param last : iterator to the last element to destroy
+//-----------------------------------------------------------------------------
+template<class Iter_t>
+inline void reverse(Iter_t first, Iter_t last)
+{
+ std::reverse ( first, last);
+};
+//
+//****************************************************************************
+};// End namespace util
+};// End namespace common
+};// End namespace sort
+};// End namespace boost
+//****************************************************************************
+//
+#endif
diff --git a/boost/sort/common/util/atomic.hpp b/boost/sort/common/util/atomic.hpp
new file mode 100644
index 0000000000..15906fe52a
--- /dev/null
+++ b/boost/sort/common/util/atomic.hpp
@@ -0,0 +1,98 @@
+//----------------------------------------------------------------------------
+/// @file atomic.hpp
+/// @brief Basic layer for to simplify the use of atomic functions
+/// @author Copyright(c) 2016 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_PARALLEL_DETAIL_UTIL_ATOMIC_HPP
+#define __BOOST_SORT_PARALLEL_DETAIL_UTIL_ATOMIC_HPP
+
+#include <atomic>
+#include <cassert>
+#include <type_traits>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+namespace util
+{
+//-----------------------------------------------------------------------------
+// function : atomic_read
+/// @brief make the atomic read of an atomic variable, using a memory model
+/// @param at_var : atomic variable to read
+/// @return value obtained
+//-----------------------------------------------------------------------------
+template<typename T>
+inline T atomic_read(std::atomic<T> &at_var)
+{
+ return std::atomic_load_explicit < T > (&at_var, std::memory_order_acquire);
+};
+//
+//-----------------------------------------------------------------------------
+// function : atomic_add
+/// @brief Add a number to an atomic variable, using a memory model
+/// @param at_var : variable to add
+/// @param num : value to add to at_var
+/// @return result of the operation
+//-----------------------------------------------------------------------------
+template<typename T, typename T2>
+inline T atomic_add(std::atomic<T> &at_var, T2 num)
+{
+ static_assert (std::is_integral< T2 >::value, "Bad parameter");
+ return std::atomic_fetch_add_explicit <T>
+ (&at_var, (T) num, std::memory_order_acq_rel);
+};
+//
+//-----------------------------------------------------------------------------
+// function : atomic_sub
+/// @brief Atomic subtract of an atomic variable using memory model
+/// @param at_var : Varibale to subtract
+/// @param num : value to sub to at_var
+/// @return result of the operation
+//-----------------------------------------------------------------------------
+template<typename T, typename T2>
+inline T atomic_sub(std::atomic<T> &at_var, T2 num)
+{
+ static_assert (std::is_integral< T2 >::value, "Bad parameter");
+ return std::atomic_fetch_sub_explicit <T>
+ (&at_var, (T) num, std::memory_order_acq_rel);
+};
+//
+//-----------------------------------------------------------------------------
+// function : atomic_write
+/// @brief Write a value in an atomic variable using memory model
+/// @param at_var : varible to write
+/// @param num : value to write in at_var
+//-----------------------------------------------------------------------------
+template<typename T, typename T2>
+inline void atomic_write(std::atomic<T> &at_var, T2 num)
+{
+ static_assert (std::is_integral< T2 >::value, "Bad parameter");
+ std::atomic_store_explicit <T>
+ (&at_var, (T) num, std::memory_order_release);
+};
+template<typename T>
+struct counter_guard
+{
+ typedef std::atomic<T> atomic_t;
+ atomic_t &count;
+
+ counter_guard(atomic_t & counter): count(counter) { };
+ ~counter_guard() {atomic_sub(count, 1); };
+};
+//
+//****************************************************************************
+};// End namespace util
+};// End namespace common
+};// End namespace sort
+};// End namespace boost
+//****************************************************************************
+#endif
diff --git a/boost/sort/common/util/circular_buffer.hpp b/boost/sort/common/util/circular_buffer.hpp
new file mode 100644
index 0000000000..2fc7e973e1
--- /dev/null
+++ b/boost/sort/common/util/circular_buffer.hpp
@@ -0,0 +1,572 @@
+//----------------------------------------------------------------------------
+/// @file circular_buffer.hpp
+/// @brief This file contains the implementation of the circular buffer
+///
+/// @author Copyright (c) 2010 2015 Francisco José Tapia (fjtapia@gmail.com )\n
+/// Distributed under the Boost Software License, Version 1.0.\n
+/// ( See accompanyingfile LICENSE_1_0.txt or copy at
+/// http://www.boost.org/LICENSE_1_0.txt )
+/// @version 0.1
+///
+/// @remarks
+//-----------------------------------------------------------------------------
+#ifndef __BOOST_SORT_COMMON_UTIL_CIRCULAR_BUFFER_HPP
+#define __BOOST_SORT_COMMON_UTIL_CIRCULAR_BUFFER_HPP
+
+#include <memory>
+#include <cassert>
+#include <exception>
+#include <boost/sort/common/util/algorithm.hpp>
+#include <boost/sort/common/util/traits.hpp>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+namespace util
+{
+
+//---------------------------------------------------------------------------
+/// @class circular_buffer
+/// @brief This class implement a circular buffer
+/// @remarks
+//---------------------------------------------------------------------------
+template <class Value_t, uint32_t Power2 = 11>
+struct circular_buffer
+{
+ //------------------------------------------------------------------------
+ // STATIC CHECK
+ //------------------------------------------------------------------------
+ static_assert ( Power2 != 0, "Wrong Power2");
+
+ //------------------------------------------------------------------------
+ // DEFINITIONS
+ //------------------------------------------------------------------------
+ typedef Value_t value_t;
+
+ //------------------------------------------------------------------------
+ // VARIABLES
+ //------------------------------------------------------------------------
+ const size_t NMAX = (size_t) 1 << Power2;
+ const size_t MASK = (NMAX - 1);
+ const size_t BLOCK_SIZE = NMAX >> 1;
+ const size_t LOG_BLOCK = Power2 - 1;
+ Value_t * ptr = nullptr;
+
+ //------------------------------------------------------------------------
+ // first and last are the position of the first and last elements
+ // always are in the range [0, NMAX - 1]
+ //------------------------------------------------------------------------
+ size_t nelem, first_pos;
+ bool initialized;
+
+ //
+ //------------------------------------------------------------------------
+ // function : circular_buffer
+ /// @brief constructor of the class
+ //-----------------------------------------------------------------------
+ circular_buffer(void)
+ : ptr(nullptr), nelem(0), first_pos(0), initialized(false)
+ {
+ ptr = std::get_temporary_buffer < Value_t > (NMAX).first;
+ if (ptr == nullptr) throw std::bad_alloc();
+ };
+ //
+ //------------------------------------------------------------------------
+ // function : ~circular_buffer
+ /// @brief destructor of the class
+ //-----------------------------------------------------------------------
+ ~circular_buffer()
+ {
+ if (initialized)
+ { for (size_t i = 0; i < NMAX; ++i) (ptr + i)->~Value_t();
+ initialized = false;
+ };
+ std::return_temporary_buffer(ptr);
+ }
+ ;
+ //
+ //------------------------------------------------------------------------
+ // function : initialize
+ /// @brief : initialize the memory of the buffer from the uninitialize
+ // memory obtained from the temporary buffer
+ /// @param val : value used to initialize the memory
+ //-----------------------------------------------------------------------
+ void initialize(Value_t & val)
+ {
+ assert (initialized == false);
+ ::new (static_cast<void*>(ptr)) Value_t(std::move(val));
+ for (size_t i = 1; i < NMAX; ++i)
+ ::new (static_cast<void*>(ptr + i)) Value_t(std::move(ptr[i - 1]));
+ val = std::move(ptr[NMAX - 1]);
+ initialized = true;
+ };
+ //
+ //------------------------------------------------------------------------
+ // function : destroy_all
+ /// @brief : destroy all the objects in the internal memory
+ //-----------------------------------------------------------------------
+ void destroy_all(void) { destroy(ptr, ptr + NMAX); };
+ //
+ //------------------------------------------------------------------------
+ // function : get_buffer
+ /// @brief return the internal memory of the circular buffer
+ /// @return pointer to the internal memory of the buffer
+ //-----------------------------------------------------------------------
+ Value_t * get_buffer(void) { return ptr; };
+ //
+ //------------------------------------------------------------------------
+ // function : empty
+ /// @brief return if the buffer is empty
+ /// @return true : empty
+ //-----------------------------------------------------------------------
+ bool empty(void) const {return (nelem == 0); };
+ //
+ //------------------------------------------------------------------------
+ // function : full
+ /// @brief return if the buffer is full
+ /// @return true : full
+ //-----------------------------------------------------------------------
+ bool full(void) const { return (nelem == NMAX); };
+ //
+ //------------------------------------------------------------------------
+ // function : size
+ /// @brief return the number of elements stored in the buffer
+ /// @return number of elements stored
+ //-----------------------------------------------------------------------
+ size_t size(void) const { return nelem;};
+ //
+ //------------------------------------------------------------------------
+ // function : capacity
+ /// @brief : return the maximun capacity of the buffer
+ /// @return number of elements
+ //-----------------------------------------------------------------------
+ size_t capacity(void) const { return NMAX;};
+ //
+ //------------------------------------------------------------------------
+ // function : free_size
+ /// @brief return the free positions in the buffer
+ /// @return number of elements
+ //-----------------------------------------------------------------------
+ size_t free_size(void) const { return (NMAX - nelem); };
+ //
+ //------------------------------------------------------------------------
+ // function : clear
+ /// @brief clear the buffer
+ //-----------------------------------------------------------------------
+ void clear(void) { nelem = first_pos = 0; };
+ //
+ //------------------------------------------------------------------------
+ // function : front
+ /// @brief return the first element of the buffer
+ /// @return reference to the first value
+ //-----------------------------------------------------------------------
+ Value_t & front(void)
+ {
+#ifdef __BS_DEBUG
+ assert (nelem > 0);
+#endif
+ return (ptr[first_pos]);
+ };
+ //
+ //------------------------------------------------------------------------
+ // function :front
+ /// @brief return the first element of the buffer
+ /// @return const reference to the first value
+ //-----------------------------------------------------------------------
+ const Value_t & front(void) const
+ {
+#ifdef __BS_DEBUG
+ assert ( nelem > 0 );
+#endif
+ return (ptr[first_pos]);
+ };
+ //
+ //------------------------------------------------------------------------
+ // function : back
+ /// @brief reference to the last value of the buffer
+ /// @return reference to the last value
+ //-----------------------------------------------------------------------
+ Value_t & back(void)
+ {
+#ifdef __BS_DEBUG
+ assert ( nelem > 0 );
+#endif
+ return (ptr[(first_pos + nelem - 1) & MASK]);
+ };
+ //
+ //------------------------------------------------------------------------
+ // function : back
+ /// @brief reference to the last value of the buffer
+ /// @return const reference to the last value
+ //-----------------------------------------------------------------------
+ const Value_t & back(void) const
+ {
+#ifdef __BS_DEBUG
+ assert ( nelem > 0 );
+#endif
+ return (ptr[(first_pos + nelem - 1) & MASK]);
+ };
+ //
+ //------------------------------------------------------------------------
+ // function : operator []
+ /// @brief positional access to the elements
+ /// @param pos rquested
+ /// @return reference to the element
+ //-----------------------------------------------------------------------
+ Value_t & operator[](uint32_t pos)
+ {
+#ifdef __BS_DEBUG
+ assert ( nelem > 0 );
+#endif
+ return ptr[(first_pos + pos) & MASK];
+ };
+ //
+ //------------------------------------------------------------------------
+ // function : operator []
+ /// @brief positional access to the elements
+ /// @param pos rquested
+ /// @return const reference to the element
+ //-----------------------------------------------------------------------
+ const Value_t & operator[](uint32_t pos) const
+ {
+
+#ifdef __BS_DEBUG
+ assert ( nelem > 0 );
+#endif
+ return ptr[(first_pos + pos) & MASK];
+ };
+ //
+ //------------------------------------------------------------------------
+ // function : push_front
+ /// @brief insert an element in the first position of the buffer
+ /// @param val : const value to insert
+ //-----------------------------------------------------------------------
+ void push_front(const Value_t & val)
+ {
+#ifdef __BS_DEBUG
+ assert ( nelem != NMAX);
+#endif
+ ++nelem;
+ first_pos = ((first_pos + MASK) & MASK);
+ ptr[first_pos] = val;
+
+ };
+ //
+ //------------------------------------------------------------------------
+ // function : push_front
+ /// @brief insert an element in the first position of the buffer
+ /// @param val : rvalue to insert
+ //-----------------------------------------------------------------------
+ void push_front(Value_t && val)
+ {
+#ifdef __BS_DEBUG
+ assert ( nelem != NMAX);
+#endif
+ ++nelem;
+ first_pos = ((first_pos + MASK) & MASK);
+ ptr[first_pos] = val;
+ };
+ //
+ //------------------------------------------------------------------------
+ // function : push_back
+ /// @brief insert an element in the last position of the buffer
+ /// @param val : value to insert
+ //-----------------------------------------------------------------------
+ void push_back(const Value_t & val)
+ {
+#ifdef __BS_DEBUG
+ assert ( nelem != NMAX);
+#endif
+ ptr[(first_pos + (nelem++)) & MASK] = val;
+ };
+ //
+ //------------------------------------------------------------------------
+ // function : push_back
+ /// @brief insert an element in the last position of the buffer
+ /// @param val : value to insert
+ //-----------------------------------------------------------------------
+ void push_back(Value_t && val)
+ {
+#ifdef __BS_DEBUG
+ assert ( nelem != NMAX);
+#endif
+ ptr[(first_pos + (nelem++)) & MASK] = std::move(val);
+ };
+ //
+ //------------------------------------------------------------------------
+ // function : pop_front
+ /// @brief remove the first element of the buffer
+ //-----------------------------------------------------------------------
+ void pop_front(void)
+ {
+#ifdef __BS_DEBUG
+ assert ( nelem > 0 );
+#endif
+ --nelem;
+ (++first_pos) &= MASK;
+ };
+ //
+ //------------------------------------------------------------------------
+ // function : pop_back
+ /// @brief remove the last element of the buffer
+ //-----------------------------------------------------------------------
+ void pop_back(void)
+ {
+#ifdef __BS_DEBUG
+ assert ( nelem > 0 );
+#endif
+ --nelem;
+ };
+
+ template<class iter_t>
+ void pop_copy_front(iter_t it_dest, size_t num);
+
+ template<class iter_t>
+ void pop_move_front(iter_t it_dest, size_t num);
+
+ template<class iter_t>
+ void pop_copy_back(iter_t it_dest, size_t num);
+
+ template<class iter_t>
+ void pop_move_back(iter_t it_dest, size_t num);
+
+ template<class iter_t>
+ void push_copy_front(iter_t it_src, size_t num);
+
+ template<class iter_t>
+ void push_move_front(iter_t it_src, size_t num);
+
+ template<class iter_t>
+ void push_copy_back(iter_t it_src, size_t num);
+
+ template<class iter_t>
+ void push_move_back(iter_t it_src, size_t num);
+
+//---------------------------------------------------------------------------
+};// End of class circular_buffer
+//---------------------------------------------------------------------------
+//
+//
+//############################################################################
+// ##
+// N O N I N L I N E F U N C T I O N S ##
+// ##
+//############################################################################
+//
+//------------------------------------------------------------------------
+// function : pop_copy_front
+/// @brief copy and delete num elements from the front of the buffer
+/// @param it_dest : iterator to the first position where copy the elements
+/// @param num : number of elements to copy
+//-----------------------------------------------------------------------
+template <class Value_t, uint32_t Power2>
+template<class iter_t>
+void circular_buffer<Value_t, Power2>
+::pop_copy_front(iter_t it_dest, size_t num)
+{
+ static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
+ "Incompatible iterator");
+ if (num == 0) return;
+#ifdef __BS_DEBUG
+ assert ( num <= nelem);
+#endif
+ nelem -= num;
+ size_t pos = first_pos;
+ first_pos = (first_pos + num) & MASK;
+ for (size_t i = 0; i < num; ++i)
+ {
+ *(it_dest++) = ptr[pos++ & MASK];
+ };
+ first_pos &= MASK;
+};
+//
+//------------------------------------------------------------------------
+// function : pop_move_front
+/// @brief move num elements from the front of the buffer to the place
+// pointed by it_dest
+/// @param it_dest : iterator to the first position where move the elements
+/// @param num : number of elements to move
+//-----------------------------------------------------------------------
+template <class Value_t, uint32_t Power2>
+template<class iter_t>
+void circular_buffer<Value_t, Power2>
+:: pop_move_front(iter_t it_dest, size_t num)
+{
+ static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
+ "Incompatible iterator");
+ if (num == 0) return;
+#ifdef __BS_DEBUG
+ assert ( num <= nelem);
+#endif
+ nelem -= num;
+ size_t pos = first_pos;
+ first_pos = (first_pos + num) & MASK;
+ for (size_t i = 0; i < num; ++i)
+ {
+ *(it_dest++) = std::move(ptr[pos++ & MASK]);
+ };
+ first_pos &= MASK;
+};
+//
+//------------------------------------------------------------------------
+// function : pop_copy_back
+/// @brief copy and delete num elements from the back of the buffer
+/// @param p1 : iterator where begin to copy the elements
+/// @param num : number of elements to copy
+//-----------------------------------------------------------------------
+template <class Value_t, uint32_t Power2>
+template<class iter_t>
+void circular_buffer<Value_t, Power2>
+::pop_copy_back(iter_t it_dest, size_t num)
+{
+ static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
+ "Incompatible iterator");
+ if (num == 0) return;
+#ifdef __BS_DEBUG
+ assert ( num <= nelem);
+#endif
+ nelem -= num;
+ size_t pos = (first_pos + nelem) & MASK;
+ for (size_t i = 0; i < num; ++i)
+ {
+ *(it_dest++) = ptr[pos++ & MASK];
+ };
+};
+//
+//------------------------------------------------------------------------
+// function : pop_move_back
+/// @brief move and delete num elements from the back of the buffer
+/// @param p1 : iterator where begin to move the elements
+/// @param num : number of elements to move
+//-----------------------------------------------------------------------
+template <class Value_t, uint32_t Power2>
+template<class iter_t>
+void circular_buffer<Value_t, Power2>
+::pop_move_back(iter_t it_dest, size_t num)
+{
+ static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
+ "Incompatible iterator");
+ if (num == 0) return;
+#ifdef __BS_DEBUG
+ assert ( num <= nelem);
+#endif
+ nelem -= num;
+ size_t pos = (first_pos + nelem) & MASK;
+ for (size_t i = 0; i < num; ++i)
+ {
+ *(it_dest++) = std::move(ptr[pos++ & MASK]);
+ };
+};
+//
+//------------------------------------------------------------------------
+// function : push_copy_front
+/// @brief copy num elements in the front of the buffer
+/// @param it_src : iterator from where begin to copy the elements
+/// @param mun : number of element to copy
+//-----------------------------------------------------------------------
+template <class Value_t, uint32_t Power2>
+template<class iter_t>
+void circular_buffer<Value_t, Power2>
+::push_copy_front(iter_t it_src, size_t num)
+{
+ static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
+ "Incompatible iterator");
+ if (num == 0) return;
+#ifdef __BS_DEBUG
+ assert ( free_size() >= num);
+#endif
+ nelem += num;
+
+ first_pos = (first_pos + NMAX - num) & MASK;
+ size_t pos = first_pos;
+ for (size_t i = 0; i < num; ++i)
+ {
+ ptr[(pos++) & MASK] = *(it_src++);
+ };
+};
+//
+//------------------------------------------------------------------------
+// function : push_move_front
+/// @brief move num elements in the front of the buffer
+/// @param p1 : iterator from where begin to move the elements
+/// @param mun : number of element to move
+//-----------------------------------------------------------------------
+template <class Value_t, uint32_t Power2>
+template<class iter_t>
+void circular_buffer<Value_t, Power2>
+::push_move_front(iter_t it_src, size_t num)
+{
+ static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
+ "Incompatible iterator");
+ if (num == 0) return;
+#ifdef __BS_DEBUG
+ assert ( free_size() >= num);
+#endif
+ nelem += num;
+ size_t pos = first_pos;
+ for (size_t i = 0; i < num; ++i)
+ {
+ ptr[(pos++) & MASK] = std::move(*(it_src++));
+ };
+};
+//
+//------------------------------------------------------------------------
+// function : push_copy_back
+/// @brief copy num elements in the back of the buffer
+/// @param p1 : iterator from where begin to copy the elements
+/// @param mun : number of element to copy
+//-----------------------------------------------------------------------
+template <class Value_t, uint32_t Power2>
+template<class iter_t>
+void circular_buffer<Value_t, Power2>
+::push_copy_back(iter_t it_src, size_t num)
+{
+ static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
+ "Incompatible iterator");
+ if (num == 0) return;
+#ifdef __BS_DEBUG
+ assert ( free_size() >= num);
+#endif
+ size_t pos = first_pos + nelem;
+ nelem += num;
+ for (size_t i = 0; i < num; ++i)
+ {
+ ptr[(pos++) & MASK] = *(it_src++);
+ };
+};
+//
+//------------------------------------------------------------------------
+// function : push_move_back
+/// @brief move num elements in the back of the buffer
+/// @param p1 : iterator from where begin to move the elements
+/// @param mun : number of element to move
+//-----------------------------------------------------------------------
+template <class Value_t, uint32_t Power2>
+template<class iter_t>
+void circular_buffer<Value_t, Power2>
+::push_move_back(iter_t it_src, size_t num)
+{
+ static_assert ( std::is_same <value_iter<iter_t>, Value_t>::value,
+ "Incompatible iterator");
+ if (num == 0) return;
+#ifdef __BS_DEBUG
+ assert ( free_size() >= num);
+#endif
+ size_t pos = first_pos + nelem;
+ nelem += num;
+ for (size_t i = 0; i < num; ++i)
+ {
+ ptr[(pos++) & MASK] = std::move(*(it_src++));
+ };
+};
+
+//****************************************************************************
+};// End namespace util
+};// End namespace common
+};// End namespace sort
+};// End namespace boost
+//****************************************************************************
+#endif
diff --git a/boost/sort/common/util/insert.hpp b/boost/sort/common/util/insert.hpp
new file mode 100644
index 0000000000..219fa8a351
--- /dev/null
+++ b/boost/sort/common/util/insert.hpp
@@ -0,0 +1,142 @@
+//----------------------------------------------------------------------------
+/// @file insert.hpp
+/// @brief
+///
+/// @author Copyright (c) 2016 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_COMMON_UTIL_INSERT_HPP
+#define __BOOST_SORT_COMMON_UTIL_INSERT_HPP
+
+//#include <boost/sort/spinsort/util/indirect.hpp>
+#include <boost/sort/common/util/insert.hpp>
+#include <boost/sort/common/util/traits.hpp>
+#include <boost/sort/common/util/algorithm.hpp>
+#include <cstdlib>
+#include <functional>
+#include <iterator>
+#include <memory>
+#include <type_traits>
+#include <vector>
+#include <cstddef>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+namespace util
+{
+namespace here = boost::sort::common::util;
+//
+//############################################################################
+//
+// D E F I N I T I O N S O F F U N C T I O N S
+//
+// template < class Iter1_t, class Iter2_t, typename Compare>
+// void insert_sorted (Iter1_t first, Iter1_t mid, Iter1_t last,
+// Compare comp, Iter2_t it_aux)
+//
+//############################################################################
+//
+//-----------------------------------------------------------------------------
+// function : insert_sorted
+/// @brief : Insertion sort of elements sorted
+/// @param first: iterator to the first element of the range
+/// @param mid : last pointer of the sorted data, and first pointer to the
+/// elements to insert
+/// @param last : iterator to the next element of the last in the range
+/// @param comp :
+/// @comments : the two ranges are sorted and in it_aux there is spave for
+/// to store temporally the elements to insert
+//-----------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, typename Compare>
+static void insert_sorted(Iter1_t first, Iter1_t mid, Iter1_t last,
+ Compare comp, Iter2_t it_aux)
+{
+ //------------------------------------------------------------------------
+ // metaprogram
+ //------------------------------------------------------------------------
+ typedef value_iter<Iter1_t> value_t;
+ typedef value_iter<Iter2_t> value2_t;
+ static_assert (std::is_same< value_t, value2_t>::value,
+ "Incompatible iterators\n");
+
+ //--------------------------------------------------------------------
+ // program
+ //--------------------------------------------------------------------
+ if (mid == last) return;
+ if (first == mid) return;
+
+ //------------------------------------------------------------------------
+ // creation of the vector of elements to insert and their position in the
+ // sorted part
+ // the data are inserted in it_aux
+ //-----------------------------------------------------------------------
+ move_forward(it_aux, mid, last);
+
+ // search of the iterators where insert the new elements
+ size_t ndata = last - mid;
+ Iter1_t mv_first = mid, mv_last = mid;
+
+ for (size_t i = ndata; i > 0; --i)
+ {
+ mv_last = mv_first;
+ mv_first = std::upper_bound(first, mv_last, it_aux[i - 1], comp);
+ Iter1_t it1 = here::move_backward(mv_last + i, mv_first, mv_last);
+ *(it1 - 1) = std::move(it_aux[i - 1]);
+ };
+};
+
+template<class Iter1_t, class Iter2_t, typename Compare>
+static void insert_sorted_backward(Iter1_t first, Iter1_t mid, Iter1_t last,
+ Compare comp, Iter2_t it_aux)
+{
+ //------------------------------------------------------------------------
+ // metaprogram
+ //------------------------------------------------------------------------
+ typedef value_iter<Iter1_t> value_t;
+ typedef value_iter<Iter2_t> value2_t;
+ static_assert (std::is_same< value_t, value2_t>::value,
+ "Incompatible iterators\n");
+
+ //--------------------------------------------------------------------
+ // program
+ //--------------------------------------------------------------------
+ if (mid == last) return;
+ if (first == mid) return;
+ //------------------------------------------------------------------------
+ // creation of the vector of elements to insert and their position in the
+ // sorted part
+ // the data are inserted in it_aux
+ //-----------------------------------------------------------------------
+ move_forward(it_aux, first, mid);
+
+ // search of the iterators where insert the new elements
+ size_t ndata = mid - first;
+ Iter1_t mv_first = mid, mv_last = mid;
+
+ for (size_t i = 0; i < ndata; ++i)
+ {
+ mv_first = mv_last;
+ mv_last = std::lower_bound(mv_first, last, it_aux[i], comp);
+ Iter1_t it1 = move_forward(mv_first - (ndata - i), mv_first, mv_last);
+ *(it1) = std::move(it_aux[i]);
+ };
+
+};
+//
+//****************************************************************************
+};// End namespace util
+};// End namepspace common
+};// End namespace sort
+};// End namepspace boost
+//****************************************************************************
+//
+#endif
diff --git a/boost/sort/common/util/merge.hpp b/boost/sort/common/util/merge.hpp
new file mode 100644
index 0000000000..5fc90c0fd4
--- /dev/null
+++ b/boost/sort/common/util/merge.hpp
@@ -0,0 +1,494 @@
+//----------------------------------------------------------------------------
+/// @file merge.hpp
+/// @brief low level merge functions
+///
+/// @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_COMMON_UTIL_MERGE_HPP
+#define __BOOST_SORT_COMMON_UTIL_MERGE_HPP
+
+#include <algorithm>
+#include <functional>
+#include <iterator>
+#include <memory>
+
+#include <boost/sort/common/util/algorithm.hpp>
+#include <boost/sort/common/util/traits.hpp>
+#include <boost/sort/common/util/circular_buffer.hpp>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+namespace util
+{
+namespace here = boost::sort::common::util;
+//----------------------------------------------------------------------------
+//
+// F U N C T I O N S I N T H E F I L E
+//----------------------------------------------------------------------------
+//
+// template < class Iter1_t, class Iter2_t, class Compare >
+// Iter2_t merge (Iter1_t buf1, const Iter1_t end_buf1, Iter1_t buf2,
+// const Iter1_t end_buf2, Iter2_t buf_out, Compare comp)
+//
+// template < class Iter_t, class Value_t, class Compare >
+// Value_t *merge_construct (Iter_t first1, const Iter_t last1, Iter_t first2,
+// const Iter_t last2, Value_t *it_out, Compare comp)
+//
+// template < class Iter1_t, class Iter2_t, class Compare >
+// Iter2_t merge_half (Iter1_t buf1, const Iter1_t end_buf1, Iter2_t buf2,
+// const Iter2_t end_buf2, Iter2_t buf_out, Compare comp)
+//
+// template < class Iter1_t, class Iter2_t, class Compare >
+// Iter2_t merge_half_backward (Iter1_t buf1, Iter1_t end_buf1,
+// Iter2_t buf2, Iter2_t end_buf2,
+// Iter1_t end_buf_out, Compare comp)
+//
+// template < class Iter1_t, class Iter2_t, class Iter3_t, class Compare >
+// bool merge_uncontiguous (Iter1_t src1, const Iter1_t end_src1,
+// Iter2_t src2, const Iter2_t end_src2,
+// Iter3_t aux, Compare comp)
+//
+// template < class Iter1_t, class Iter2_t, class Compare >
+// bool merge_contiguous (Iter1_t src1, Iter1_t src2, Iter1_t end_src2,
+// Iter2_t buf, Compare comp)
+//
+// template < class Iter_t, class Circular ,class Compare >
+// bool merge_circular (Iter_t buf1, Iter_t end_buf1,
+// Iter_t buf2, Iter_t end_buf2,
+// Circular &circ, Compare comp, Iter_t &it_aux)
+//
+//----------------------------------------------------------------------------
+//
+//-----------------------------------------------------------------------------
+// function : merge
+/// @brief Merge two contiguous buffers pointed by buf1 and buf2, and put
+/// in the buffer pointed by buf_out
+///
+/// @param buf1 : iterator to the first element in the first buffer
+/// @param end_buf1 : final iterator of first buffer
+/// @param buf2 : iterator to the first iterator to the second buffer
+/// @param end_buf2 : final iterator of the second buffer
+/// @param buf_out : buffer where move the elements merged
+/// @param comp : comparison object
+//-----------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, class Iter3_t, class Compare>
+static Iter3_t merge(Iter1_t buf1, const Iter1_t end_buf1, Iter2_t buf2,
+ const Iter2_t end_buf2, Iter3_t buf_out, Compare comp)
+{
+ //-------------------------------------------------------------------------
+ // Metaprogramming
+ //-------------------------------------------------------------------------
+ typedef value_iter<Iter1_t> value1_t;
+ typedef value_iter<Iter2_t> value2_t;
+ typedef value_iter<Iter3_t> value3_t;
+ static_assert (std::is_same< value1_t, value2_t >::value,
+ "Incompatible iterators\n");
+ static_assert (std::is_same< value3_t, value2_t >::value,
+ "Incompatible iterators\n");
+
+ //-------------------------------------------------------------------------
+ // Code
+ //-------------------------------------------------------------------------
+ const size_t MIN_CHECK = 1024;
+
+ if (size_t((end_buf1 - buf1) + (end_buf2 - buf2)) >= MIN_CHECK)
+ {
+ if (buf1 == end_buf1) return move_forward(buf_out, buf2, end_buf2);
+ if (buf2 == end_buf2) return move_forward(buf_out, buf1, end_buf1);
+
+ if (not comp(*buf2, *(end_buf1 - 1)))
+ {
+ Iter3_t mid = move_forward(buf_out, buf1, end_buf1);
+ return move_forward(mid, buf2, end_buf2);
+ };
+
+ if (comp(*(end_buf2 - 1), *buf1))
+ {
+ Iter3_t mid = move_forward(buf_out, buf2, end_buf2);
+ return move_forward(mid, buf1, end_buf1);
+ };
+ };
+ while ((buf1 != end_buf1) and (buf2 != end_buf2))
+ {
+ *(buf_out++) = (not comp(*buf2, *buf1)) ?
+ std::move(*(buf1++)) : std::move(*(buf2++));
+ };
+
+ return (buf1 == end_buf1) ?
+ move_forward(buf_out, buf2, end_buf2) :
+ move_forward(buf_out, buf1, end_buf1);
+}
+;
+//
+//-----------------------------------------------------------------------------
+// function : merge_construct
+/// @brief Merge two contiguous buffers pointed by first1 and first2, and put
+/// in the uninitialized buffer pointed by it_out
+///
+/// @param first1 : iterator to the first element in the first buffer
+/// @param last1 : last iterator of the first buffer
+/// @param first2 : iterator to the first element to the second buffer
+/// @param last2 : final iterator of the second buffer
+/// @param it_out : uninitialized buffer where move the elements merged
+/// @param comp : comparison object
+//-----------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, class Value_t, class Compare>
+static Value_t *merge_construct(Iter1_t first1, const Iter1_t last1,
+ Iter2_t first2, const Iter2_t last2,
+ Value_t *it_out, Compare comp)
+{
+ //-------------------------------------------------------------------------
+ // Metaprogramming
+ //-------------------------------------------------------------------------
+ typedef value_iter<Iter1_t> type1;
+ typedef value_iter<Iter2_t> type2;
+ static_assert (std::is_same< Value_t, type1 >::value,
+ "Incompatible iterators\n");
+ static_assert (std::is_same< Value_t, type2 >::value,
+ "Incompatible iterators\n");
+
+ //-------------------------------------------------------------------------
+ // Code
+ //-------------------------------------------------------------------------
+ const size_t MIN_CHECK = 1024;
+
+ if (size_t((last1 - first1) + (last2 - first2)) >= MIN_CHECK)
+ {
+ if (first1 == last1) return move_construct(it_out, first2, last2);
+ if (first2 == last2) return move_construct(it_out, first1, last1);
+
+ if (not comp(*first2, *(last1 - 1)))
+ {
+ Value_t* mid = move_construct(it_out, first1, last1);
+ return move_construct(mid, first2, last2);
+ };
+
+ if (comp(*(last2 - 1), *first1))
+ {
+ Value_t* mid = move_construct(it_out, first2, last2);
+ return move_construct(mid, first1, last1);
+ };
+ };
+ while (first1 != last1 and first2 != last2)
+ {
+ construct_object((it_out++),
+ (not comp(*first2, *first1)) ?
+ std::move(*(first1++)) :
+ std::move(*(first2++)));
+ };
+ return (first1 == last1) ?
+ move_construct(it_out, first2, last2) :
+ move_construct(it_out, first1, last1);
+};
+//
+//---------------------------------------------------------------------------
+// function : merge_half
+/// @brief : Merge two buffers. The first buffer is in a separate memory.
+/// The second buffer have a empty space before buf2 of the same size
+/// than the (end_buf1 - buf1)
+///
+/// @param buf1 : iterator to the first element of the first buffer
+/// @param end_buf1 : iterator to the last element of the first buffer
+/// @param buf2 : iterator to the first element of the second buffer
+/// @param end_buf2 : iterator to the last element of the second buffer
+/// @param buf_out : iterator to the first element to the buffer where put
+/// the result
+/// @param comp : object for Compare two elements of the type pointed
+/// by the Iter1_t and Iter2_t
+//---------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, class Compare>
+static Iter2_t merge_half(Iter1_t buf1, const Iter1_t end_buf1, Iter2_t buf2,
+ const Iter2_t end_buf2, Iter2_t buf_out, Compare comp)
+{
+ //-------------------------------------------------------------------------
+ // Metaprogramming
+ //-------------------------------------------------------------------------
+ typedef value_iter<Iter1_t> value1_t;
+ typedef value_iter<Iter2_t> value2_t;
+ static_assert (std::is_same< value1_t, value2_t >::value,
+ "Incompatible iterators\n");
+
+ //-------------------------------------------------------------------------
+ // Code
+ //-------------------------------------------------------------------------
+#ifdef __BS_DEBUG
+ assert ( (buf2 - buf_out) == ( end_buf1 - buf1));
+#endif
+ const size_t MIN_CHECK = 1024;
+
+ if (size_t((end_buf1 - buf1) + (end_buf2 - buf2)) >= MIN_CHECK)
+ {
+ if (buf1 == end_buf1) return end_buf2;
+ if (buf2 == end_buf2) return move_forward(buf_out, buf1, end_buf1);
+
+ if (not comp(*buf2, *(end_buf1 - 1)))
+ {
+ move_forward(buf_out, buf1, end_buf1);
+ return end_buf2;
+ };
+
+ if (comp(*(end_buf2 - 1), *buf1))
+ {
+ Iter2_t mid = move_forward(buf_out, buf2, end_buf2);
+ return move_forward(mid, buf1, end_buf1);
+ };
+ };
+ while ((buf1 != end_buf1) and (buf2 != end_buf2))
+ {
+ *(buf_out++) = (not comp(*buf2, *buf1)) ?
+ std::move(*(buf1++)) : std::move(*(buf2++));
+ };
+ return (buf2 == end_buf2)? move_forward(buf_out, buf1, end_buf1) : end_buf2;
+};
+
+//
+//---------------------------------------------------------------------------
+// function : merge_half_backward
+/// @brief : Merge two buffers. The first buffer is in a separate memory.
+/// The second buffer have a empty space before buf2 of the same size
+/// than the (end_buf1 - buf1)
+///
+/// @param buf1 : iterator to the first element of the first buffer
+/// @param end_buf1 : iterator to the last element of the first buffer
+/// @param buf2 : iterator to the first element of the second buffer
+/// @param end_buf2 : iterator to the last element of the second buffer
+/// @param buf_out : iterator to the first element to the buffer where put
+/// the result
+/// @param comp : object for Compare two elements of the type pointed
+/// by the Iter1_t and Iter2_t
+//---------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, class Compare>
+static Iter2_t merge_half_backward(Iter1_t buf1, Iter1_t end_buf1, Iter2_t buf2,
+ Iter2_t end_buf2, Iter1_t end_buf_out,
+ Compare comp)
+{
+ //-------------------------------------------------------------------------
+ // Metaprogramming
+ //-------------------------------------------------------------------------
+ typedef value_iter<Iter1_t> value1_t;
+ typedef value_iter<Iter2_t> value2_t;
+ static_assert (std::is_same< value1_t, value2_t >::value,
+ "Incompatible iterators\n");
+
+ //-------------------------------------------------------------------------
+ // Code
+ //-------------------------------------------------------------------------
+#ifdef __BS_DEBUG
+ assert ((end_buf_out - end_buf1) == (end_buf2 - buf2) );
+#endif
+ const size_t MIN_CHECK = 1024;
+
+ if (size_t((end_buf1 - buf1) + (end_buf2 - buf2)) >= MIN_CHECK)
+ {
+ if (buf2 == end_buf2) return buf1;
+ if (buf1 == end_buf1)
+ return here::move_backward(end_buf_out, buf2, end_buf2);
+
+ if (not comp(*buf2, *(end_buf1 - 1)))
+ {
+ here::move_backward(end_buf_out, buf2, end_buf2);
+ return buf1;
+ };
+
+ if (comp(*(end_buf2 - 1), *buf1))
+ {
+ Iter1_t mid = here::move_backward(end_buf_out, buf1, end_buf1);
+ return here::move_backward(mid, buf2, end_buf2);
+ };
+ };
+ while ((buf1 != end_buf1) and (buf2 != end_buf2))
+ {
+ *(--end_buf_out) =
+ (not comp(*(end_buf2 - 1), *(end_buf1 - 1))) ?
+ std::move(*(--end_buf2)):
+ std::move(*(--end_buf1));
+ };
+ return (buf1 == end_buf1) ?
+ here::move_backward(end_buf_out, buf2, end_buf2) : buf1;
+};
+
+//
+//-----------------------------------------------------------------------------
+// function : merge_uncontiguous
+/// @brief : merge two uncontiguous buffers, placing the results in the buffers
+/// Use an auxiliary buffer pointed by aux
+///
+/// @param src1 : iterator to the first element of the first buffer
+/// @param end_src1 : last iterator of the first buffer
+/// @param src2 : iterator to the first element of the second buffer
+/// @param end_src2 : last iterator of the second buffer
+/// @param aux : iterator to the first element of the auxiliary buffer
+/// @param comp : object for to Compare elements
+/// @return true : not changes done, false : changes in the buffers
+/// @remarks
+//-----------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, class Iter3_t, class Compare>
+static bool merge_uncontiguous(Iter1_t src1, const Iter1_t end_src1,
+ Iter2_t src2, const Iter2_t end_src2,
+ Iter3_t aux, Compare comp)
+{
+ //-------------------------------------------------------------------------
+ // Metaprogramming
+ //-------------------------------------------------------------------------
+ typedef value_iter<Iter1_t> type1;
+ typedef value_iter<Iter2_t> type2;
+ typedef value_iter<Iter3_t> type3;
+ static_assert (std::is_same< type1, type2 >::value,
+ "Incompatible iterators\n");
+ static_assert (std::is_same< type3, type2 >::value,
+ "Incompatible iterators\n");
+
+ //-------------------------------------------------------------------------
+ // Code
+ //-------------------------------------------------------------------------
+ if (src1 == end_src1 or src2 == end_src2
+ or not comp(*src2, *(end_src1 - 1))) return true;
+
+ while (src1 != end_src1 and not comp(*src2, *src1))
+ ++src1;
+
+ Iter3_t const end_aux = aux + (end_src1 - src1);
+ Iter2_t src2_first = src2;
+ move_forward(aux, src1, end_src1);
+
+ while ((src1 != end_src1) and (src2 != end_src2))
+ {
+ *(src1++) = std::move((not comp(*src2, *aux)) ? *(aux++) : *(src2++));
+ }
+
+ if (src2 == end_src2)
+ {
+ while (src1 != end_src1)
+ *(src1++) = std::move(*(aux++));
+ move_forward(src2_first, aux, end_aux);
+ }
+ else
+ {
+ merge_half(aux, end_aux, src2, end_src2, src2_first, comp);
+ };
+ return false;
+};
+
+//
+//-----------------------------------------------------------------------------
+// function : merge_contiguous
+/// @brief : merge two contiguous buffers,using an auxiliary buffer pointed
+/// by buf. The results are in src1 and src2
+///
+/// @param src1: iterator to the first position of the first buffer
+/// @param src2: final iterator of the first buffer and first iterator
+/// of the second buffer
+/// @param end_src2 : final iterator of the second buffer
+/// @param buf : iterator to buffer used as auxiliary memory
+/// @param comp : object for to Compare elements
+/// @return true : not changes done, false : changes in the buffers
+//-----------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, class Compare>
+static bool merge_contiguous(Iter1_t src1, Iter1_t src2, Iter1_t end_src2,
+ Iter2_t buf, Compare comp)
+{
+ //-------------------------------------------------------------------------
+ // Metaprogramming
+ //-------------------------------------------------------------------------
+ typedef value_iter<Iter1_t> type1;
+ typedef value_iter<Iter2_t> type2;
+ static_assert (std::is_same< type1, type2 >::value,
+ "Incompatible iterators\n");
+
+ //-------------------------------------------------------------------------
+ // Code
+ //-------------------------------------------------------------------------
+ if (src1 == src2 or src2 == end_src2 or not comp(*src2, *(src2 - 1)))
+ return true;
+
+ Iter1_t end_src1 = src2;
+ while (src1 != end_src1 and not comp(*src2, *src1))
+ ++src1;
+
+ if (src1 == end_src1) return false;
+
+ size_t nx = end_src1 - src1;
+ move_forward(buf, src1, end_src1);
+ merge_half(buf, buf + nx, src2, end_src2, src1, comp);
+ return false;
+};
+//
+//-----------------------------------------------------------------------------
+// function : merge_circular
+/// @brief : merge two buffers,using a circular buffer
+/// This function don't check the parameters
+/// @param buf1: iterator to the first position of the first buffer
+/// @param end_buf1: iterator after the last element of the first buffer
+/// @param buf2: iterator to the first element of the secind buffer
+/// @param end_buf2: iterator to the first element of the secind buffer
+/// @param circ : circular buffer
+/// @param comp : comparison object
+/// @return true : finished buf1, false : finished buf2
+/// @comments : be carefully because the iterators buf1 and buf2 are modified
+//-----------------------------------------------------------------------------
+template<class Iter1_t, class Iter2_t, class Circular, class Compare>
+static bool merge_circular(Iter1_t buf1, Iter1_t end_buf1, Iter2_t buf2,
+ Iter2_t end_buf2, Circular &circ, Compare comp,
+ Iter1_t &it1_out, Iter2_t &it2_out)
+{
+ //-------------------------------------------------------------------------
+ // Metaprogramming
+ //-------------------------------------------------------------------------
+ typedef value_iter<Iter1_t> type1;
+ typedef value_iter<Iter2_t> type2;
+ static_assert (std::is_same< type1, type2 >::value,
+ "Incompatible iterators\n");
+ typedef typename Circular::value_t type3;
+ static_assert (std::is_same<type1, type3>::value,
+ "Incompatible iterators\n");
+
+ //-------------------------------------------------------------------------
+ // Code
+ //-------------------------------------------------------------------------
+#ifdef __BS_DEBUG
+ assert ( circ.free_size() >= size_t ((end_buf1-buf1) + (end_buf2-buf2)));
+#endif
+
+ if (not comp(*buf2, *(end_buf1 - 1)))
+ {
+ circ.push_move_back(buf1, (end_buf1 - buf1));
+ it1_out = end_buf1;
+ it2_out = buf2;
+ return true;
+ };
+ if (comp(*(end_buf2 - 1), *buf1))
+ {
+ circ.push_move_back(buf2, (end_buf2 - buf2));
+ it1_out = buf1;
+ it2_out = end_buf2;
+ return false;
+ }
+ while (buf1 != end_buf1 and buf2 != end_buf2)
+ {
+ circ.push_back(comp(*buf2, *buf1) ? std::move(*(buf2++))
+ : std::move(*(buf1++)));
+ };
+ it2_out = buf2;
+ it1_out = buf1;
+ bool ret = (buf1 == end_buf1);
+ return ret;
+};
+//
+//****************************************************************************
+};// End namespace util
+};// End namespace common
+};// End namespace sort
+};// End namespace boost
+//****************************************************************************
+//
+#endif
diff --git a/boost/sort/common/util/search.hpp b/boost/sort/common/util/search.hpp
new file mode 100644
index 0000000000..fbe056e2f8
--- /dev/null
+++ b/boost/sort/common/util/search.hpp
@@ -0,0 +1,529 @@
+//----------------------------------------------------------------------------
+/// @file search.hpp
+/// @brief
+/// @author Copyright (c) 2017 Francisco José Tapia (fjtapia@gmail.com )\n
+/// Distributed under the Boost Software License, Version 1.0.\n
+/// ( See copy at http://www.boost.org/LICENSE_1_0.txt )
+/// @remarks
+//-----------------------------------------------------------------------------
+#ifndef __BOOST_SORT_COMMON_SEARCH_HPP
+#define __BOOST_SORT_COMMON_SEARCH_HPP
+
+#include <boost/sort/common/util/traits.hpp>
+#include <cassert>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+namespace util
+{
+
+template<class T>
+struct filter_pass
+{
+ typedef T key;
+ const key & operator()(const T & val) const
+ {
+ return val;
+ };
+};
+
+//
+//###########################################################################
+// ##
+// ################################################################ ##
+// # # ##
+// # I N T E R N A L F U N C T I O N S # ##
+// # # ##
+// ################################################################ ##
+// ##
+// I M P O R T A N T ##
+// ##
+// These functions are not directly callable by the user, are for internal ##
+// use only. ##
+// These functions don't check the parameters ##
+// ##
+//###########################################################################
+//
+//-----------------------------------------------------------------------------
+// function : internal_find_first
+/// @brief find if a value exist in the range [first, last).
+/// Always return as valid iterator in the range [first, last-1]
+/// If exist return the iterator to the first occurrence. If don't exist
+/// return the first greater than val.
+/// If val is greater than the *(last-1), return (last-1)
+/// If val is lower than (*first), return first
+//
+/// @param [in] first : iterator to the first element of the range
+/// @param [in] last : iterator to the last element of the range
+/// @param [in] val : value to find
+/// @param [in] comp : object for to compare two value_t objects
+/// @return iterator to the element found,
+//-----------------------------------------------------------------------------
+template <class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
+ class Compare = std::less<typename Filter::key> >
+inline Iter_t internal_find_first(Iter_t first, Iter_t last,
+ const typename Filter::key &val,
+ const Compare & comp = Compare(),
+ Filter flt = Filter())
+{
+ Iter_t LI = first, LS = last - 1, it_out = first;
+ while (LI != LS)
+ {
+ it_out = LI + ((LS - LI) >> 1);
+ if (comp(flt(*it_out), val))
+ LI = it_out + 1;
+ else LS = it_out;
+ };
+ return LS;
+};
+//
+//-----------------------------------------------------------------------------
+// function : internal_find_last
+/// @brief find if a value exist in the range [first, last).
+/// Always return as valid iterator in the range [first, last-1]
+/// If exist return the iterator to the last occurrence.
+/// If don't exist return the first lower than val.
+/// If val is greater than *(last-1) return (last-1).
+/// If is lower than the first, return first
+//
+/// @param [in] first : iterator to the first element of the range
+/// @param [in] last : iterator to the last element of the range
+/// @param [in] val : value to find
+/// @param [in] comp : object for to compare two value_t objects
+/// @return iterator to the element found, if not found return last
+
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
+ class Compare = std::less<typename Filter::key> >
+inline Iter_t internal_find_last(Iter_t first, Iter_t last,
+ const typename Filter::key &val,
+ const Compare & comp = Compare(), Filter flt =
+ Filter())
+{
+ Iter_t LI = first, LS = last - 1, it_out = first;
+ while (LI != LS)
+ {
+ it_out = LI + ((LS - LI + 1) >> 1);
+ if (comp(val, flt(*it_out))) LS = it_out - 1;
+ else LI = it_out;
+ };
+ return LS;
+};
+
+//
+//###########################################################################
+// ##
+// ################################################################ ##
+// # # ##
+// # P U B L I C F U N C T I O N S # ##
+// # # ##
+// ################################################################ ##
+// ##
+//###########################################################################
+//
+//-----------------------------------------------------------------------------
+// function : find_first
+/// @brief find if a value exist in the range [first, last). If exist return the
+/// iterator to the first occurrence. If don't exist return last
+//
+/// @param [in] first : iterator to the first element of the range
+/// @param [in] last : iterator to the last element of the range
+/// @param [in] val : value to find
+/// @param [in] comp : object for to compare two value_t objects
+/// @return iterator to the element found, and if not last
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
+ class Compare = std::less<typename Filter::key> >
+inline Iter_t find_first(Iter_t first, Iter_t last,
+ const typename Filter::key &val,
+ const Compare & comp = Compare(),
+ Filter flt = Filter())
+{
+ assert((last - first) >= 0);
+ if (first == last) return last;
+ Iter_t LS = internal_find_first(first, last, val, comp, flt);
+ return (comp(flt(*LS), val) or comp(val, flt(*LS))) ? last : LS;
+};
+//
+//-----------------------------------------------------------------------------
+// function : find_last
+/// @brief find if a value exist in the range [first, last). If exist return the
+/// iterator to the last occurrence. If don't exist return last
+//
+/// @param [in] first : iterator to the first element of the range
+/// @param [in] last : iterator to the last element of the range
+/// @param [in] val : value to find
+/// @param [in] comp : object for to compare two value_t objects
+/// @return iterator to the element found, if not found return last
+
+//-----------------------------------------------------------------------------
+template <class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
+ class Compare = std::less<typename Filter::key> >
+inline Iter_t find_last(Iter_t first, Iter_t last,
+ const typename Filter::key &val,
+ const Compare & comp = Compare(),
+ Filter flt = Filter())
+{
+ assert((last - first) >= 0);
+ if (last == first) return last;
+ Iter_t LS = internal_find_last(first, last, val, comp, flt);
+ return (comp(flt(*LS), val) or comp(val, flt(*LS))) ? last : LS;
+};
+
+//----------------------------------------------------------------------------
+// function : lower_bound
+/// @brief Returns an iterator pointing to the first element in the range
+/// [first, last) that is not less than (i.e. greater or equal to) val.
+/// @param [in] last : iterator to the last element of the range
+/// @param [in] val : value to find
+/// @param [in] comp : object for to compare two value_t objects
+/// @return iterator to the element found
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
+ class Compare = std::less<typename Filter::key> >
+inline Iter_t lower_bound(Iter_t first, Iter_t last,
+ const typename Filter::key &val,
+ const Compare & comp = Compare(),
+ Filter flt = Filter())
+{
+ assert((last - first) >= 0);
+ if (last == first) return last;
+ Iter_t itaux = internal_find_first(first, last, val, comp, flt);
+ return (itaux == (last - 1) and comp(flt(*itaux), val)) ? last : itaux;
+};
+//----------------------------------------------------------------------------
+// function :upper_bound
+/// @brief return the first element greather than val.If don't exist
+/// return last
+//
+/// @param [in] first : iterator to the first element of the range
+/// @param [in] last : iterator to the last element of the range
+/// @param [in] val : value to find
+/// @param [in] comp : object for to compare two value_t objects
+/// @return iterator to the element found
+/// @remarks
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
+ class Compare = std::less<typename Filter::key> >
+inline Iter_t upper_bound(Iter_t first, Iter_t last,
+ const typename Filter::key &val,
+ const Compare & comp = Compare(),
+ Filter flt = Filter())
+{
+ assert((last - first) >= 0);
+ if (last == first) return last;
+ Iter_t itaux = internal_find_last(first, last, val, comp, flt);
+ return (itaux == first and comp(val, flt(*itaux))) ? itaux : itaux + 1;
+}
+;
+//----------------------------------------------------------------------------
+// function :equal_range
+/// @brief return a pair of lower_bound and upper_bound with the value val.If
+/// don't exist return last in the two elements of the pair
+//
+/// @param [in] first : iterator to the first element of the range
+/// @param [in] last : iterator to the last element of the range
+/// @param [in] val : value to find
+/// @param [in] comp : object for to compare two value_t objects
+/// @return pair of iterators
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
+ class Compare = std::less<typename Filter::key> >
+inline std::pair<Iter_t, Iter_t> equal_range(Iter_t first, Iter_t last,
+ const typename Filter::key &val,
+ const Compare & comp = Compare(),
+ Filter flt = Filter())
+{
+ return std::make_pair(lower_bound(first, last, val, comp, flt),
+ upper_bound(first, last, val, comp, flt));
+};
+//
+//-----------------------------------------------------------------------------
+// function : insert_first
+/// @brief find if a value exist in the range [first, last). If exist return the
+/// iterator to the first occurrence. If don't exist return last
+//
+/// @param [in] first : iterator to the first element of the range
+/// @param [in] last : iterator to the last element of the range
+/// @param [in] val : value to find
+/// @param [in] comp : object for to compare two value_t objects
+/// @return iterator to the element found, and if not last
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
+ class Compare = std::less<typename Filter::key> >
+inline Iter_t insert_first(Iter_t first, Iter_t last,
+ const typename Filter::key &val,
+ const Compare & comp = Compare(), Filter flt =
+ Filter())
+{
+ return lower_bound(first, last, val, comp, flt);
+};
+//
+//-----------------------------------------------------------------------------
+// function : insert_last
+/// @brief find if a value exist in the range [first, last). If exist return the
+/// iterator to the last occurrence. If don't exist return last
+//
+/// @param [in] first : iterator to the first element of the range
+/// @param [in] last : iterator to the last element of the range
+/// @param [in] val : value to find
+/// @param [in] comp : object for to compare two value_t objects
+/// @return iterator to the element found, if not found return last
+
+//-----------------------------------------------------------------------------
+template<class Iter_t, class Filter = filter_pass<value_iter<Iter_t> >,
+ class Compare = std::less<typename Filter::key> >
+inline Iter_t insert_last(Iter_t first, Iter_t last,
+ const typename Filter::key &val,
+ const Compare & comp = Compare(), Filter flt =
+ Filter())
+{
+ return upper_bound(first, last, val, comp, flt);
+};
+
+/*
+
+ //
+ //###########################################################################
+ // ##
+ // ################################################################ ##
+ // # # ##
+ // # I N T E R N A L F U N C T I O N S # ##
+ // # # ##
+ // ################################################################ ##
+ // ##
+ // I M P O R T A N T ##
+ // ##
+ // These functions are not directly callable by the user, are for internal ##
+ // use only. ##
+ // These functions don't check the parameters ##
+ // ##
+ //###########################################################################
+ //
+ //-----------------------------------------------------------------------------
+ // function : internal_find_first
+ /// @brief find if a value exist in the range [first, last).
+ /// Always return as valid iterator in the range [first, last-1]
+ /// If exist return the iterator to the first occurrence. If don't exist
+ /// return the first greater than val.
+ /// If val is greater than the *(last-1), return (last-1)
+ /// If val is lower than (*first), return first
+ //
+ /// @param [in] first : iterator to the first element of the range
+ /// @param [in] last : iterator to the last element of the range
+ /// @param [in] val : value to find
+ /// @param [in] comp : object for to compare two value_t objects
+ /// @return iterator to the element found,
+ //-----------------------------------------------------------------------------
+ template < class Iter_t, class Compare = compare_iter<Iter_t> >
+ inline Iter_t internal_find_first ( Iter_t first, Iter_t last,
+ const value_iter<Iter_t> &val,
+ const Compare & comp= Compare() )
+ {
+ Iter_t LI = first , LS = last - 1, it_out = first;
+ while ( LI != LS)
+ { it_out = LI + ( (LS - LI) >> 1);
+ if ( comp ( *it_out, val)) LI = it_out + 1 ; else LS = it_out ;
+ };
+ return LS ;
+ };
+ //
+ //-----------------------------------------------------------------------------
+ // function : internal_find_last
+ /// @brief find if a value exist in the range [first, last).
+ /// Always return as valid iterator in the range [first, last-1]
+ /// If exist return the iterator to the last occurrence.
+ /// If don't exist return the first lower than val.
+ /// If val is greater than *(last-1) return (last-1).
+ /// If is lower than the first, return first
+ //
+ /// @param [in] first : iterator to the first element of the range
+ /// @param [in] last : iterator to the last element of the range
+ /// @param [in] val : value to find
+ /// @param [in] comp : object for to compare two value_t objects
+ /// @return iterator to the element found, if not found return last
+
+ //-----------------------------------------------------------------------------
+ template < class Iter_t, class Compare = compare_iter<Iter_t> >
+ inline Iter_t internal_find_last ( Iter_t first, Iter_t last ,
+ const value_iter<Iter_t> &val,
+ const Compare &comp= Compare() )
+ {
+ Iter_t LI = first , LS = last - 1, it_out = first ;
+ while ( LI != LS)
+ { it_out = LI + ( (LS - LI + 1) >> 1);
+ if ( comp (val, *it_out)) LS = it_out - 1 ; else LI = it_out ;
+ };
+ return LS ;
+ };
+
+ //
+ //###########################################################################
+ // ##
+ // ################################################################ ##
+ // # # ##
+ // # P U B L I C F U N C T I O N S # ##
+ // # # ##
+ // ################################################################ ##
+ // ##
+ //###########################################################################
+ //
+ //-----------------------------------------------------------------------------
+ // function : find_first
+ /// @brief find if a value exist in the range [first, last). If exist return the
+ /// iterator to the first occurrence. If don't exist return last
+ //
+ /// @param [in] first : iterator to the first element of the range
+ /// @param [in] last : iterator to the last element of the range
+ /// @param [in] val : value to find
+ /// @param [in] comp : object for to compare two value_t objects
+ /// @return iterator to the element found, and if not last
+ //-----------------------------------------------------------------------------
+ template < class Iter_t, class Compare = compare_iter<Iter_t> >
+ inline Iter_t find_first ( Iter_t first, Iter_t last,
+ const value_iter<Iter_t> &val,
+ Compare comp = Compare() )
+ {
+ assert ( (last - first) >= 0 );
+ if ( first == last) return last ;
+ Iter_t LS = internal_find_first ( first, last, val, comp);
+ return (comp (*LS, val) or comp (val, *LS))?last:LS;
+ };
+ //
+ //-----------------------------------------------------------------------------
+ // function : find_last
+ /// @brief find if a value exist in the range [first, last). If exist return the
+ /// iterator to the last occurrence. If don't exist return last
+ //
+ /// @param [in] first : iterator to the first element of the range
+ /// @param [in] last : iterator to the last element of the range
+ /// @param [in] val : value to find
+ /// @param [in] comp : object for to compare two value_t objects
+ /// @return iterator to the element found, if not found return last
+
+ //-----------------------------------------------------------------------------
+ template < class Iter_t, class Compare = compare_iter<Iter_t> >
+ inline Iter_t find_last ( Iter_t first, Iter_t last ,
+ const value_iter<Iter_t> &val,
+ Compare comp = Compare())
+ {
+ assert ( (last - first ) >= 0 );
+ if ( last == first ) return last ;
+ Iter_t LS = internal_find_last (first, last, val, comp);
+ return (comp (*LS, val) or comp (val, *LS))?last:LS ;
+ };
+
+ //----------------------------------------------------------------------------
+ // function : lower_bound
+ /// @brief Returns an iterator pointing to the first element in the range
+ /// [first, last) that is not less than (i.e. greater or equal to) val.
+ /// @param [in] last : iterator to the last element of the range
+ /// @param [in] val : value to find
+ /// @param [in] comp : object for to compare two value_t objects
+ /// @return iterator to the element found
+ //-----------------------------------------------------------------------------
+ template < class Iter_t, class Compare = compare_iter<Iter_t> >
+ inline Iter_t lower_bound ( Iter_t first, Iter_t last ,
+ const value_iter<Iter_t> &val,
+ Compare &comp = Compare() )
+ {
+ assert ( (last - first ) >= 0 );
+ if ( last == first ) return last ;
+ Iter_t itaux = internal_find_first( first, last, val,comp);
+ return (itaux == (last - 1) and comp (*itaux, val))?last: itaux;
+ };
+ //----------------------------------------------------------------------------
+ // function :upper_bound
+ /// @brief return the first element greather than val.If don't exist
+ /// return last
+ //
+ /// @param [in] first : iterator to the first element of the range
+ /// @param [in] last : iterator to the last element of the range
+ /// @param [in] val : value to find
+ /// @param [in] comp : object for to compare two value_t objects
+ /// @return iterator to the element found
+ /// @remarks
+ //-----------------------------------------------------------------------------
+ template < class Iter_t, class Compare = compare_iter<Iter_t> >
+ inline Iter_t upper_bound ( Iter_t first, Iter_t last ,
+ const value_iter<Iter_t> &val,
+ Compare &comp = Compare() )
+ {
+ assert ( (last - first ) >= 0 );
+ if ( last == first ) return last ;
+ Iter_t itaux = internal_find_last( first, last, val,comp);
+ return ( itaux == first and comp (val,*itaux))? itaux: itaux + 1;
+ };
+ //----------------------------------------------------------------------------
+ // function :equal_range
+ /// @brief return a pair of lower_bound and upper_bound with the value val.If
+ /// don't exist return last in the two elements of the pair
+ //
+ /// @param [in] first : iterator to the first element of the range
+ /// @param [in] last : iterator to the last element of the range
+ /// @param [in] val : value to find
+ /// @param [in] comp : object for to compare two value_t objects
+ /// @return pair of iterators
+ //-----------------------------------------------------------------------------
+ template < class Iter_t, class Compare = compare_iter<Iter_t> >
+ inline std::pair<Iter_t, Iter_t> equal_range ( Iter_t first, Iter_t last ,
+ const value_iter<Iter_t> &val,
+ Compare &comp = Compare() )
+ {
+ return std::make_pair(lower_bound(first, last, val,comp),
+ upper_bound(first, last, val,comp));
+ };
+ //
+ //-----------------------------------------------------------------------------
+ // function : insert_first
+ /// @brief find if a value exist in the range [first, last). If exist return the
+ /// iterator to the first occurrence. If don't exist return last
+ //
+ /// @param [in] first : iterator to the first element of the range
+ /// @param [in] last : iterator to the last element of the range
+ /// @param [in] val : value to find
+ /// @param [in] comp : object for to compare two value_t objects
+ /// @return iterator to the element found, and if not last
+ //-----------------------------------------------------------------------------
+ template < class Iter_t, class Compare = compare_iter<Iter_t> >
+ inline Iter_t insert_first ( Iter_t first, Iter_t last,
+ const value_iter<Iter_t> &val,
+ Compare comp = Compare() )
+ {
+ return lower_bound (first, last, val, comp);
+ };
+ //
+ //-----------------------------------------------------------------------------
+ // function : insert_last
+ /// @brief find if a value exist in the range [first, last). If exist return the
+ /// iterator to the last occurrence. If don't exist return last
+ //
+ /// @param [in] first : iterator to the first element of the range
+ /// @param [in] last : iterator to the last element of the range
+ /// @param [in] val : value to find
+ /// @param [in] comp : object for to compare two value_t objects
+ /// @return iterator to the element found, if not found return last
+
+ //-----------------------------------------------------------------------------
+ template < class Iter_t, class Compare = compare_iter<Iter_t> >
+ inline Iter_t insert_last ( Iter_t first, Iter_t last ,
+ const value_iter<Iter_t> &val,
+ Compare comp = Compare())
+ {
+ return upper_bound (first, last, val, comp);
+ };
+
+ */
+//
+//****************************************************************************
+};// End namespace util
+};// End namespace common
+};// End namespace sort
+};// End namespace boost
+//****************************************************************************
+//
+#endif
diff --git a/boost/sort/common/util/traits.hpp b/boost/sort/common/util/traits.hpp
new file mode 100644
index 0000000000..68e5cf0359
--- /dev/null
+++ b/boost/sort/common/util/traits.hpp
@@ -0,0 +1,123 @@
+//----------------------------------------------------------------------------
+/// @file traits.hpp
+/// @brief this file contains the metaprogramming classes compare_iter and
+/// enable_if_not_integral
+/// @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
+///
+//-----------------------------------------------------------------------------
+#ifndef __BOOST_SORT_COMMON_UTIL_TRAITS_HPP
+#define __BOOST_SORT_COMMON_UTIL_TRAITS_HPP
+
+#include <functional>
+#include <iterator>
+#include <type_traits>
+
+namespace boost
+{
+namespace sort
+{
+namespace common
+{
+namespace util
+{
+//----------------------------------------------------------------------------
+// USING SENTENCES
+//----------------------------------------------------------------------------
+using std::iterator_traits;
+
+//
+//---------------------------------------------------------------------------
+/// @class value_iter
+/// @brief From the iterator, obtain the type pointed by it
+/// @remarks The main utility of this, is simplify the default template
+/// parameter of comparison
+//---------------------------------------------------------------------------
+template<class iter_t>
+using value_iter = typename iterator_traits< iter_t >::value_type;
+//
+//---------------------------------------------------------------------------
+/// @class compare_iter
+/// @brief From the iterator, received as template parameter, obtain the type
+/// of the object pointed by the iterator, and with this define the
+/// std::less with this type obtained
+/// @remarks The main utility of this, is simplify the default template
+/// parameter of comparison
+//---------------------------------------------------------------------------
+template<class iter_t>
+using compare_iter = std::less< value_iter< iter_t > >;
+
+//
+//---------------------------------------------------------------------------
+/// @class enable_if_not_integral
+/// @brief This is a SFINAE class for to detect if the third parameter in the
+/// invocation of the parallel sorting algorithms is an integer
+/// representing the number of threads to use or is a comparison object
+/// @remarks
+//---------------------------------------------------------------------------
+template<class T>
+using enable_if_not_integral =
+ typename std::enable_if< !std::is_integral< T >::value >::type;
+//
+//---------------------------------------------------------------------------
+/// @class enable_if_integral
+/// @brief This is a SFINAE class for to detect if the third parameter in the
+/// invocation of the parallel sorting algorithms is an integer
+/// representing the number of threads to use or is a comparison object
+/// @remarks
+//---------------------------------------------------------------------------
+template<class T>
+using enable_if_integral =
+ typename std::enable_if< std::is_integral< T >::value >::type;
+
+//
+//---------------------------------------------------------------------------
+/// @class enable_if_string
+/// @brief This is a SFINAE class for to detect if the parameter is a
+/// std::string for to apply specialized parameters in the invocation
+/// of the block_indirect_sort algorithm
+/// @remarks
+//---------------------------------------------------------------------------
+template<class T>
+using enable_if_string =
+ typename std::enable_if< std::is_same< T, std::string >::value >::type;
+
+//
+//---------------------------------------------------------------------------
+/// @class enable_if_not_string
+/// @brief This is a SFINAE class for to detect if the parameter is a
+/// std::string for to apply specialized parameters in the invocation
+/// of the block_indirect_sort algorithm
+/// @remarks
+//---------------------------------------------------------------------------
+template<class T>
+using enable_if_not_string =
+ typename std::enable_if<! std::is_same< T, std::string >::value >::type;
+
+//
+//---------------------------------------------------------------------------
+/// @class constructor
+/// @brief create a functor with the constructor of a class for to be invoked
+/// from a bind or a lambda
+/// @remarks
+//---------------------------------------------------------------------------
+template<class T>
+struct constructor
+{
+ template<class ... Args>
+ void operator()(Args && ... args)
+ {
+ T(std::forward<Args> (args) ...);
+ };
+};
+//
+//****************************************************************************
+};// End namespace util
+};// End namespace common
+};// End namespace sort
+};// End namespace boost
+//****************************************************************************
+#endif