diff options
Diffstat (limited to 'boost/sort/common/util/algorithm.hpp')
-rw-r--r-- | boost/sort/common/util/algorithm.hpp | 309 |
1 files changed, 309 insertions, 0 deletions
diff --git a/boost/sort/common/util/algorithm.hpp b/boost/sort/common/util/algorithm.hpp new file mode 100644 index 0000000000..db7607aaeb --- /dev/null +++ b/boost/sort/common/util/algorithm.hpp @@ -0,0 +1,309 @@ +//---------------------------------------------------------------------------- +/// @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 |