summaryrefslogtreecommitdiff
path: root/boost/sort/common/util
diff options
context:
space:
mode:
Diffstat (limited to 'boost/sort/common/util')
-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
7 files changed, 2267 insertions, 0 deletions
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