summaryrefslogtreecommitdiff
path: root/boost/sort/common/merge_vector.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/sort/common/merge_vector.hpp')
-rw-r--r--boost/sort/common/merge_vector.hpp196
1 files changed, 196 insertions, 0 deletions
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