diff options
Diffstat (limited to 'boost/sort/common')
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 |