diff options
Diffstat (limited to 'boost/sort/common/range.hpp')
| -rw-r--r-- | boost/sort/common/range.hpp | 399 |
1 files changed, 399 insertions, 0 deletions
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 |