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