//----------------------------------------------------------------------------
|
/// @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
|
