summaryrefslogtreecommitdiff
path: root/boost/sort/common/indirect.hpp
blob: a55ef820239c44d8258f704e9eff96bfce0e5cfe (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
//----------------------------------------------------------------------------
/// @file indirect.hpp
/// @brief Indirect algorithm
///
/// @author Copyright (c) 2016 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_PARALLEL_COMMON_INDIRECT_HPP
#define __BOOST_SORT_PARALLEL_COMMON_INDIRECT_HPP

//#include <boost/sort/common/atomic.hpp>
#include <boost/sort/common/util/traits.hpp>
#include <functional>
#include <iterator>
#include <type_traits>
#include <vector>

namespace boost
{
namespace sort
{
namespace common
{

//
//---------------------------------------------------------------------------
/// @struct less_ptr_no_null
///
/// @remarks this is the comparison object for pointers. Compare the objects
///          pointed by the iterators
//---------------------------------------------------------------------------
template<class Iter_t, class Compare = util::compare_iter<Iter_t> >
struct less_ptr_no_null
{
    //----------------------------- Variables -----------------------
    Compare comp; // comparison object of the elements pointed by Iter_t

    //------------------------------------------------------------------------
    //  function : less_ptr_no_null
    /// @brief constructor from a Compare object
    /// @param C1 : comparison object
    //-----------------------------------------------------------------------
    less_ptr_no_null(Compare C1 = Compare()): comp(C1) { };

    //------------------------------------------------------------------------
    //  function : operator ( )
    /// @brief Make the comparison of the objects pointed by T1 and T2, using
    //         the internal comp
    //
    /// @param  T1 : first iterator
    /// @param  T2 : second iterator
    /// @return bool result of the comparison
    //-----------------------------------------------------------------------
    bool operator( )(Iter_t T1, Iter_t T2) const
    {
        return comp(*T1, *T2);
    };
};
//
//-----------------------------------------------------------------------------
//  function : create_index
/// @brief From a vector of objects, create a vector of iterators to
///        the objects
///
/// @param first : iterator to the first element of the range
/// @param last : iterator to the element after the last of the range
/// @param index : vector where store the iterators
//-----------------------------------------------------------------------------
template<class Iter_t>
static void create_index(Iter_t first, Iter_t last, std::vector<Iter_t> &index)
{
    auto nelem = last - first;
    assert(nelem >= 0);
    index.clear();
    index.reserve(nelem);
    for (; first != last; ++first) index.push_back(first);
};
//
//-----------------------------------------------------------------------------
//  function : sort_index
/// @brief This function transform a logical sort of the elements in the index
///        in a physical sort
//
/// @param global_first : iterator to the first element of the data
/// @param [in] index : vector of the iterators
//-----------------------------------------------------------------------------
template<class Iter_t>
static void sort_index(Iter_t global_first, std::vector<Iter_t> &index)
{
    typedef util::value_iter<Iter_t> value_t;

    size_t pos_dest = 0;
    size_t pos_src = 0;
    size_t pos_in_vector = 0;
    size_t nelem = index.size();
    Iter_t it_dest, it_src;

    while (pos_in_vector < nelem)
    {
        while (pos_in_vector < nelem and
               (size_t(index[pos_in_vector] - global_first)) == pos_in_vector)
        {
            ++pos_in_vector;
        };

        if (pos_in_vector == nelem) return;
        pos_dest = pos_src = pos_in_vector;
        it_dest = global_first + pos_dest;
        value_t Aux = std::move(*it_dest);

        while ((pos_src = (size_t(index[pos_dest] - global_first)))
               != pos_in_vector)
        {
            index[pos_dest] = it_dest;
            it_src = global_first + pos_src;
            *it_dest = std::move(*it_src);
            it_dest = it_src;
            pos_dest = pos_src;
        };

        *it_dest = std::move(Aux);
        index[pos_dest] = it_dest;
        ++pos_in_vector;
    };
};

template<class func, class Iter_t, class Compare = compare_iter<Iter_t> >
static void indirect_sort(func method, Iter_t first, Iter_t last, Compare comp)
{
    auto nelem = (last - first);
    assert(nelem >= 0);
    if (nelem < 2) return;
    std::vector<Iter_t> index;
    index.reserve((size_t) nelem);
    create_index(first, last, index);
    less_ptr_no_null<Iter_t, Compare> index_comp(comp);
    method(index.begin(), index.end(), index_comp);
    sort_index(first, index);
};

//
//****************************************************************************
};//    End namespace common
};//    End namespace sort
};//    End namespace boost
//****************************************************************************
//
#endif