//----------------------------------------------------------------------------
/// @file algorithm.hpp
/// @brief low level functions of create, destroy, move and merge functions
///
/// @author Copyright (c) 2017 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_COMMON_UTIL_ALGORITHM_HPP
#define __BOOST_SORT_COMMON_UTIL_ALGORITHM_HPP
#include <ciso646>
#include <algorithm>
#include <functional>
#include <iterator>
#include <memory>
#include <type_traits>
#include <vector>
#include <boost/sort/common/util/traits.hpp>
namespace boost
{
namespace sort
{
namespace common
{
namespace util
{
//
//###########################################################################
//
// I M P O R T A N T
//
// The functions of this file are for internal use only
// All the operations are done with move operations, because the copy
// operations are unnecesary
//
//###########################################################################
//
//----------------------------------------------------------------------------
//
// F U N C T I O N S I N T H E F I L E
//
//----------------------------------------------------------------------------
//
// static inline uint32_t nbits32 (uint32_t num) noexcept
//
// static inline uint32_t nbits64 (uint64_t num)
//
// template < class Value_t, class... Args >
// inline void construct_object (Value_t *ptr, Args &&... args)
//
// template < class Value_t >
// inline void destroy_object (Value_t *ptr)
//
// template < class Iter_t, class Value_t = value_iter<Iter_t> >
// void initialize (Iter_t first, Iter_t last, Value_t && val)
//
// template < class Iter1_t, class Iter2_t >
// Iter2_t move_forward (Iter2_t it_dest, Iter1_t first, Iter1_t last)
//
// template < class Iter1_t, class Iter2_t >
// Iter2_t move_backward (Iter2_t it_dest, Iter1_t first, Iter1_t last)
//
// template < class Iter_t, class Value_t = value_iter< Iter_t > >
// Value_t * move_construct (Value_t *ptr, Iter_t first, Iter_t last)
//
// template < class Iter_t >
// void destroy (Iter_t first, const Iter_t last)
//
// template < class Iter_t >
// void reverse (Iter_t first, const Iter_t last)
//
//----------------------------------------------------------------------------
//
//--------------------------------------------------------------------------
//
// G L O B A L V A R I B L E S
//
//--------------------------------------------------------------------------
//
// this array represent the number of bits needed for to represent the
// first 256 numbers
static constexpr const uint32_t tmsb[256] =
{ 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 };
//
//---------------------------------------------------------------------------
//
// F U N C T I O N S
//
//---------------------------------------------------------------------------
//
//---------------------------------------------------------------------------
// function : nbits32
/// @brief Obtain the number of bits of a number equal or greater than num
/// @param num : Number to examine
/// @return Number of bits
//---------------------------------------------------------------------------
static inline uint32_t nbits32 (uint32_t num) noexcept
{
int Pos = (num & 0xffff0000U) ? 16 : 0;
if ((num >> Pos) & 0xff00U) Pos += 8;
return (tmsb[num >> Pos] + Pos);
}
//
//---------------------------------------------------------------------------
// function : nbits64
/// @brief Obtain the number of bits of a number equal or greater than num
/// @param num : Number to examine
/// @exception none
/// @return Number of bits
//---------------------------------------------------------------------------
static inline uint32_t nbits64(uint64_t num)noexcept
{
uint32_t Pos = (num & 0xffffffff00000000ULL) ? 32 : 0;
if ((num >> Pos) & 0xffff0000ULL) Pos += 16;
if ((num >> Pos) & 0xff00ULL) Pos += 8;
return (tmsb[num >> Pos] + Pos);
}
//
//-----------------------------------------------------------------------------
// function : construct_object
/// @brief create an object in the memory specified by ptr
///
/// @param ptr : pointer to the memory where to create the object
/// @param args : arguments to the constructor
//-----------------------------------------------------------------------------
template <class Value_t, class ... Args>
inline void construct_object (Value_t *ptr, Args &&... args)
{
(::new (static_cast<void *>(ptr)) Value_t(std::forward< Args > (args)...));
};
//
//-----------------------------------------------------------------------------
// function : destroy_object
/// @brief destroy an object in the memory specified by ptr
/// @param ptr : pointer to the object to destroy
//-----------------------------------------------------------------------------
template<class Value_t>
inline void destroy_object(Value_t *ptr)
{
ptr->~Value_t();
};
//
//-----------------------------------------------------------------------------
// function : initialize
/// @brief initialize a range of objects with the object val moving across them
///
/// @param first : itertor to the first element to initialize
/// @param last : iterator to the last element to initialize
/// @param val : object used for the initialization
//-----------------------------------------------------------------------------
template <class Iter_t, class Value_t = value_iter<Iter_t> >
inline void initialize (Iter_t first, Iter_t last, Value_t & val)
{
//------------------------------------------------------------------------
// Metaprogramming
//------------------------------------------------------------------------
typedef value_iter<Iter_t> value_t;
static_assert (std::is_same< Value_t, value_t >::value,
"Incompatible iterators\n");
//------------------------------------------------------------------------
// Code
//------------------------------------------------------------------------
if (first == last) return;
construct_object(&(*first), std::move(val));
Iter_t it1 = first, it2 = first + 1;
while (it2 != last)
{
construct_object(&(*(it2++)), std::move(*(it1++)));
};
val = std::move(*(last - 1));
};
//
//-----------------------------------------------------------------------------
// function : move_forward
/// @brief Move initialized objets
/// @param it_dest : iterator to the final place of the objects
/// @param first : iterator to the first element to move
/// @param last : iterator to the last element to move
/// @return Output iterator to the element past the last element
/// moved (it_dest + (last - first))
//-----------------------------------------------------------------------------
template <class Iter1_t, class Iter2_t>
inline Iter2_t move_forward (Iter2_t it_dest, Iter1_t first, Iter1_t last)
{
//------------------------------------------------------------------------
// Metaprogramming
//------------------------------------------------------------------------
typedef value_iter<Iter1_t> value1_t;
typedef value_iter<Iter2_t> value2_t;
static_assert (std::is_same< value1_t, value2_t >::value,
"Incompatible iterators\n");
//------------------------------------------------------------------------
// Code
//------------------------------------------------------------------------
while (first != last)
{ *it_dest++ = std::move(*first++);
}
return it_dest;
};
//
//-----------------------------------------------------------------------------
// function : move_backard
/// @brief Move initialized objets in reverse order
/// @param it_dest : last iterator to the final place of the objects
/// @param first : iterator to the first element to move
/// @param last : iterator to the last element to move
//-----------------------------------------------------------------------------
template<class Iter1_t, class Iter2_t>
inline Iter2_t move_backward(Iter2_t it_dest, Iter1_t first, Iter1_t last)
{
//------------------------------------------------------------------------
// Metaprogramming
//------------------------------------------------------------------------
typedef value_iter<Iter1_t> value1_t;
typedef value_iter<Iter2_t> value2_t;
static_assert (std::is_same< value1_t, value2_t >::value,
"Incompatible iterators\n");
//------------------------------------------------------------------------
// Code
//------------------------------------------------------------------------
while (first != last)
{ *(--it_dest) = std::move (*(--last));
}
return it_dest;
};
//
//-----------------------------------------------------------------------------
// function : move_construct
/// @brief Move objets to uninitialized memory
///
/// @param ptr : pointer to the memory where to create the objects
/// @param first : iterator to the first element to move
/// @param last : iterator to the last element to move
//-----------------------------------------------------------------------------
template<class Iter_t, class Value_t = value_iter<Iter_t> >
inline Value_t * move_construct(Value_t *ptr, Iter_t first, Iter_t last)
{
//------------------------------------------------------------------------
// Metaprogramming
//------------------------------------------------------------------------
typedef typename iterator_traits<Iter_t>::value_type value2_t;
static_assert (std::is_same< Value_t, value2_t >::value,
"Incompatible iterators\n");
//------------------------------------------------------------------------
// Code
//------------------------------------------------------------------------
while (first != last)
{
::new (static_cast<void *>(ptr++)) Value_t(std::move(*(first++)));
};
return ptr;
};
//
//-----------------------------------------------------------------------------
// function : destroy
/// @brief destroy the elements between first and last
/// @param first : iterator to the first element to destroy
/// @param last : iterator to the last element to destroy
//-----------------------------------------------------------------------------
template<class Iter_t>
inline void destroy(Iter_t first, const Iter_t last)
{
while (first != last)
destroy_object(&(*(first++)));
};
//
//-----------------------------------------------------------------------------
// function : reverse
/// @brief destroy the elements between first and last
/// @param first : iterator to the first element to destroy
/// @param last : iterator to the last element to destroy
//-----------------------------------------------------------------------------
template<class Iter_t>
inline void reverse(Iter_t first, Iter_t last)
{
std::reverse ( first, last);
};
//
//****************************************************************************
};// End namespace util
};// End namespace common
};// End namespace sort
};// End namespace boost
//****************************************************************************
//
#endif