1//----------------------------------------------------------------------------
2/// @file algorithm.hpp
3/// @brief low level functions of create, destroy, move and merge functions
4///
5/// @author Copyright (c) 2017 Francisco Jose Tapia (fjtapia@gmail.com )\n
6/// Distributed under the Boost Software License, Version 1.0.\n
7/// ( See accompanying file LICENSE_1_0.txt or copy at
8/// http://www.boost.org/LICENSE_1_0.txt )
9/// @version 0.1
10///
11/// @remarks
12//-----------------------------------------------------------------------------
13#ifndef __BOOST_SORT_COMMON_UTIL_ALGORITHM_HPP
14#define __BOOST_SORT_COMMON_UTIL_ALGORITHM_HPP
15
16#include <ciso646>
17#include <algorithm>
18#include <functional>
19#include <iterator>
20#include <memory>
21#include <type_traits>
22#include <vector>
23#include <boost/sort/common/util/traits.hpp>
24
25namespace boost
26{
27namespace sort
28{
29namespace common
30{
31namespace util
32{
33//
34//###########################################################################
35//
36// I M P O R T A N T
37//
38// The functions of this file are for internal use only
39// All the operations are done with move operations, because the copy
40// operations are unnecesary
41//
42//###########################################################################
43//
44//----------------------------------------------------------------------------
45//
46// F U N C T I O N S I N T H E F I L E
47//
48//----------------------------------------------------------------------------
49//
50// static inline uint32_t nbits32 (uint32_t num) noexcept
51//
52// static inline uint32_t nbits64 (uint64_t num)
53//
54// template < class Value_t, class... Args >
55// inline void construct_object (Value_t *ptr, Args &&... args)
56//
57// template < class Value_t >
58// inline void destroy_object (Value_t *ptr)
59//
60// template < class Iter_t, class Value_t = value_iter<Iter_t> >
61// void initialize (Iter_t first, Iter_t last, Value_t && val)
62//
63// template < class Iter1_t, class Iter2_t >
64// Iter2_t move_forward (Iter2_t it_dest, Iter1_t first, Iter1_t last)
65//
66// template < class Iter1_t, class Iter2_t >
67// Iter2_t move_backward (Iter2_t it_dest, Iter1_t first, Iter1_t last)
68//
69// template < class Iter_t, class Value_t = value_iter< Iter_t > >
70// Value_t * move_construct (Value_t *ptr, Iter_t first, Iter_t last)
71//
72// template < class Iter_t >
73// void destroy (Iter_t first, const Iter_t last)
74//
75// template < class Iter_t >
76// void reverse (Iter_t first, const Iter_t last)
77//
78//----------------------------------------------------------------------------
79//
80//--------------------------------------------------------------------------
81//
82// G L O B A L V A R I B L E S
83//
84//--------------------------------------------------------------------------
85//
86// this array represent the number of bits needed for to represent the
87// first 256 numbers
88static constexpr const uint32_t tmsb[256] =
89{ 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,
90 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
91 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7,
92 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
93 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
94 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8,
95 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
96 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
97 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
98 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
99 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
100 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8 };
101//
102//---------------------------------------------------------------------------
103//
104// F U N C T I O N S
105//
106//---------------------------------------------------------------------------
107//
108//---------------------------------------------------------------------------
109// function : nbits32
110/// @brief Obtain the number of bits of a number equal or greater than num
111/// @param num : Number to examine
112/// @return Number of bits
113//---------------------------------------------------------------------------
114static inline uint32_t nbits32 (uint32_t num) noexcept
115{
116 int Pos = (num & 0xffff0000U) ? 16 : 0;
117 if ((num >> Pos) & 0xff00U) Pos += 8;
118 return (tmsb[num >> Pos] + Pos);
119}
120//
121//---------------------------------------------------------------------------
122// function : nbits64
123/// @brief Obtain the number of bits of a number equal or greater than num
124/// @param num : Number to examine
125/// @exception none
126/// @return Number of bits
127//---------------------------------------------------------------------------
128static inline uint32_t nbits64(uint64_t num)noexcept
129{
130 uint32_t Pos = (num & 0xffffffff00000000ULL) ? 32 : 0;
131 if ((num >> Pos) & 0xffff0000ULL) Pos += 16;
132 if ((num >> Pos) & 0xff00ULL) Pos += 8;
133 return (tmsb[num >> Pos] + Pos);
134}
135//
136//-----------------------------------------------------------------------------
137// function : construct_object
138/// @brief create an object in the memory specified by ptr
139///
140/// @param ptr : pointer to the memory where to create the object
141/// @param args : arguments to the constructor
142//-----------------------------------------------------------------------------
143template <class Value_t, class ... Args>
144inline void construct_object (Value_t *ptr, Args &&... args)
145{
146 (::new (static_cast<void *>(ptr)) Value_t(std::forward< Args > (args)...));
147};
148//
149//-----------------------------------------------------------------------------
150// function : destroy_object
151/// @brief destroy an object in the memory specified by ptr
152/// @param ptr : pointer to the object to destroy
153//-----------------------------------------------------------------------------
154template<class Value_t>
155inline void destroy_object(Value_t *ptr)
156{
157 ptr->~Value_t();
158};
159//
160//-----------------------------------------------------------------------------
161// function : initialize
162/// @brief initialize a range of objects with the object val moving across them
163///
164/// @param first : itertor to the first element to initialize
165/// @param last : iterator to the last element to initialize
166/// @param val : object used for the initialization
167//-----------------------------------------------------------------------------
168template <class Iter_t, class Value_t = value_iter<Iter_t> >
169inline void initialize (Iter_t first, Iter_t last, Value_t & val)
170{
171 //------------------------------------------------------------------------
172 // Metaprogramming
173 //------------------------------------------------------------------------
174 typedef value_iter<Iter_t> value_t;
175 static_assert (std::is_same< Value_t, value_t >::value,
176 "Incompatible iterators\n");
177
178 //------------------------------------------------------------------------
179 // Code
180 //------------------------------------------------------------------------
181 if (first == last) return;
182 construct_object(&(*first), std::move(val));
183
184 Iter_t it1 = first, it2 = first + 1;
185 while (it2 != last)
186 {
187 construct_object(&(*(it2++)), std::move(*(it1++)));
188 };
189 val = std::move(*(last - 1));
190};
191//
192//-----------------------------------------------------------------------------
193// function : move_forward
194/// @brief Move initialized objets
195/// @param it_dest : iterator to the final place of the objects
196/// @param first : iterator to the first element to move
197/// @param last : iterator to the last element to move
198/// @return Output iterator to the element past the last element
199/// moved (it_dest + (last - first))
200//-----------------------------------------------------------------------------
201template <class Iter1_t, class Iter2_t>
202inline Iter2_t move_forward (Iter2_t it_dest, Iter1_t first, Iter1_t last)
203{
204 //------------------------------------------------------------------------
205 // Metaprogramming
206 //------------------------------------------------------------------------
207 typedef value_iter<Iter1_t> value1_t;
208 typedef value_iter<Iter2_t> value2_t;
209 static_assert (std::is_same< value1_t, value2_t >::value,
210 "Incompatible iterators\n");
211
212 //------------------------------------------------------------------------
213 // Code
214 //------------------------------------------------------------------------
215 while (first != last)
216 { *it_dest++ = std::move(*first++);
217 }
218 return it_dest;
219
220};
221//
222//-----------------------------------------------------------------------------
223// function : move_backard
224/// @brief Move initialized objets in reverse order
225/// @param it_dest : last iterator to the final place of the objects
226/// @param first : iterator to the first element to move
227/// @param last : iterator to the last element to move
228//-----------------------------------------------------------------------------
229template<class Iter1_t, class Iter2_t>
230inline Iter2_t move_backward(Iter2_t it_dest, Iter1_t first, Iter1_t last)
231{
232 //------------------------------------------------------------------------
233 // Metaprogramming
234 //------------------------------------------------------------------------
235 typedef value_iter<Iter1_t> value1_t;
236 typedef value_iter<Iter2_t> value2_t;
237 static_assert (std::is_same< value1_t, value2_t >::value,
238 "Incompatible iterators\n");
239
240 //------------------------------------------------------------------------
241 // Code
242 //------------------------------------------------------------------------
243 while (first != last)
244 { *(--it_dest) = std::move (*(--last));
245 }
246 return it_dest;
247};
248
249//
250//-----------------------------------------------------------------------------
251// function : move_construct
252/// @brief Move objets to uninitialized memory
253///
254/// @param ptr : pointer to the memory where to create the objects
255/// @param first : iterator to the first element to move
256/// @param last : iterator to the last element to move
257//-----------------------------------------------------------------------------
258template<class Iter_t, class Value_t = value_iter<Iter_t> >
259inline Value_t * move_construct(Value_t *ptr, Iter_t first, Iter_t last)
260{
261 //------------------------------------------------------------------------
262 // Metaprogramming
263 //------------------------------------------------------------------------
264 typedef typename iterator_traits<Iter_t>::value_type value2_t;
265 static_assert (std::is_same< Value_t, value2_t >::value,
266 "Incompatible iterators\n");
267
268 //------------------------------------------------------------------------
269 // Code
270 //------------------------------------------------------------------------
271 while (first != last)
272 {
273 ::new (static_cast<void *>(ptr++)) Value_t(std::move(*(first++)));
274 };
275 return ptr;
276};
277//
278//-----------------------------------------------------------------------------
279// function : destroy
280/// @brief destroy the elements between first and last
281/// @param first : iterator to the first element to destroy
282/// @param last : iterator to the last element to destroy
283//-----------------------------------------------------------------------------
284template<class Iter_t>
285inline void destroy(Iter_t first, const Iter_t last)
286{
287 while (first != last)
288 destroy_object(&(*(first++)));
289};
290//
291//-----------------------------------------------------------------------------
292// function : reverse
293/// @brief destroy the elements between first and last
294/// @param first : iterator to the first element to destroy
295/// @param last : iterator to the last element to destroy
296//-----------------------------------------------------------------------------
297template<class Iter_t>
298inline void reverse(Iter_t first, Iter_t last)
299{
300 std::reverse ( first, last);
301};
302//
303//****************************************************************************
304};// End namespace util
305};// End namespace common
306};// End namespace sort
307};// End namespace boost
308//****************************************************************************
309//
310#endif
311

source code of boost/libs/sort/include/boost/sort/common/util/algorithm.hpp