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

source code of boost/libs/sort/include/boost/sort/common/pivot.hpp