xref: /third_party/boost/boost/sort/common/util/algorithm.hpp

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