1 //----------------------------------------------------------------------------
2 /// @file pivot.hpp
3 /// @brief This file contains the description of several low level algorithms
4 ///
5 /// @author Copyright (c) 2010 2015 Francisco José 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_PIVOT_HPP
14 #define __BOOST_SORT_COMMON_PIVOT_HPP
15
16 #include <cstdint>
17
18 namespace boost
19 {
20 namespace sort
21 {
22 namespace common
23 {
24 //
25 //##########################################################################
26 // ##
27 // G L O B A L V A R I B L E S ##
28 // ##
29 //##########################################################################
30 //
31 //-----------------------------------------------------------------------------
32 // function : mid3
33 /// @brief : return the iterator to the mid value of the three values passsed
34 /// as parameters
35 //
36 /// @param iter_1 : iterator to the first value
37 /// @param iter_2 : iterator to the second value
38 /// @param iter_3 : iterator to the third value
39 /// @param comp : object for to compare two values
40 /// @return iterator to mid value
41 //-----------------------------------------------------------------------------
42 template < typename Iter_t, typename Compare >
mid3(Iter_t iter_1,Iter_t iter_2,Iter_t iter_3,Compare comp)43 inline Iter_t mid3 (Iter_t iter_1, Iter_t iter_2, Iter_t iter_3, Compare comp)
44 {
45 if (comp (*iter_2, *iter_1)) std::swap ( *iter_2, *iter_1);
46 if (comp (*iter_3, *iter_2))
47 { std::swap ( *iter_3, *iter_2);
48 if (comp (*iter_2, *iter_1)) std::swap ( *iter_2, *iter_1);
49 };
50 return iter_2;
51 };
52 //
53 //-----------------------------------------------------------------------------
54 // function : pivot3
55 /// @brief : receive a range between first and last, calcule the mid iterator
56 /// with the first, the previous to the last, and the central
57 /// position. With this mid iterator swap with the first position
58 //
59 /// @param first : iterator to the first element
60 /// @param last : iterator to the last element
61 /// @param comp : object for to compare two elements
62 //-----------------------------------------------------------------------------
63 template < class Iter_t, class Compare >
pivot3(Iter_t first,Iter_t last,Compare comp)64 inline void pivot3 (Iter_t first, Iter_t last, Compare comp)
65 {
66 auto N2 = (last - first) >> 1;
67 Iter_t it_val = mid3 (first + 1, first + N2, last - 1, comp);
68 std::swap (*first, *it_val);
69 };
70
71 //
72 //-----------------------------------------------------------------------------
73 // function : mid9
74 /// @brief : return the iterator to the mid value of the nine values passsed
75 /// as parameters
76 //
77 /// @param iter_1 : iterator to the first value
78 /// @param iter_2 : iterator to the second value
79 /// @param iter_3 : iterator to the third value
80 /// @param iter_4 : iterator to the fourth value
81 /// @param iter_5 : iterator to the fifth value
82 /// @param iter_6 : iterator to the sixth value
83 /// @param iter_7 : iterator to the seventh value
84 /// @param iter_8 : iterator to the eighth value
85 /// @param iter_9 : iterator to the ninth value
86 /// @return iterator to the mid value
87 //-----------------------------------------------------------------------------
88 template < class Iter_t, class Compare >
mid9(Iter_t iter_1,Iter_t iter_2,Iter_t iter_3,Iter_t iter_4,Iter_t iter_5,Iter_t iter_6,Iter_t iter_7,Iter_t iter_8,Iter_t iter_9,Compare comp)89 inline Iter_t mid9 (Iter_t iter_1, Iter_t iter_2, Iter_t iter_3, Iter_t iter_4,
90 Iter_t iter_5, Iter_t iter_6, Iter_t iter_7, Iter_t iter_8,
91 Iter_t iter_9, Compare comp)
92 {
93 return mid3 (mid3 (iter_1, iter_2, iter_3, comp),
94 mid3 (iter_4, iter_5, iter_6, comp),
95 mid3 (iter_7, iter_8, iter_9, comp), comp);
96 };
97 //
98 //-----------------------------------------------------------------------------
99 // function : pivot9
100 /// @brief : receive a range between first and last, obtain 9 values between
101 /// the elements including the first and the previous to the last.
102 /// Obtain the iterator to the mid value and swap with the first
103 /// position
104 //
105 /// @param first : iterator to the first element
106 /// @param last : iterator to the last element
107 /// @param comp : object for to compare two elements
108 //-----------------------------------------------------------------------------
109 template < class Iter_t, class Compare >
pivot9(Iter_t first,Iter_t last,Compare comp)110 inline void pivot9 (Iter_t first, Iter_t last, Compare comp)
111 {
112 size_t cupo = (last - first) >> 3;
113 Iter_t itaux = mid9 (first + 1, first + cupo, first + 2 * cupo,
114 first + 3 * cupo, first + 4 * cupo, first + 5 * cupo,
115 first + 6 * cupo, first + 7 * cupo, last - 1, comp);
116 std::swap (*first, *itaux);
117 };
118 //****************************************************************************
119 };// End namespace common
120 };// End namespace sort
121 };// End namespace boost
122 //****************************************************************************
123 #endif
124