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