summaryrefslogtreecommitdiff
path: root/boost/sort/common/util/algorithm.hpp
diff options
context:
space:
mode:
Diffstat (limited to 'boost/sort/common/util/algorithm.hpp')
-rw-r--r--boost/sort/common/util/algorithm.hpp309
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