summaryrefslogtreecommitdiff
path: root/boost/sort/common/merge_vector.hpp
blob: 84afea5a5e47bd490830ebce33570a8ceb1c00e2 (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
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
//----------------------------------------------------------------------------
/// @file merge_vector.hpp
/// @brief In this file have the functions for to do a stable merge of
//         ranges, in a vector
///
/// @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_DETAIL_UTIL_MERGE_VECTOR_HPP
#define __BOOST_SORT_PARALLEL_DETAIL_UTIL_MERGE_VECTOR_HPP

#include <boost/sort/common/merge_four.hpp>
#include <functional>
#include <iterator>
#include <memory>
#include <type_traits>
#include <vector>

namespace boost
{
namespace sort
{
namespace common
{

//############################################################################
//                                                                          ##
//                       F U S I O N     O F                                ##
//                                                                          ##
//              A  V E C T O R   O F    R A N G E S                         ##
//                                                                          ##
//############################################################################

//
//-----------------------------------------------------------------------------
//  function : merge_level4
/// @brief merge the ranges in the vector v_input with the full_merge4 function.
///        The v_output vector is used as auxiliary memory in the internal
///        process. The final results is in the dest range.
///        All the ranges of v_output are inside the range dest
/// @param dest : range where move the elements merged
/// @param v_input : vector of ranges to merge
/// @param v_output : vector of ranges obtained
/// @param comp : comparison object
/// @return range with all the elements moved
//-----------------------------------------------------------------------------
template<class Iter1_t, class Iter2_t, class Compare>
void merge_level4(range<Iter1_t> dest, std::vector<range<Iter2_t> > &v_input,
                  std::vector<range<Iter1_t> > &v_output, Compare comp)
{
    typedef range<Iter1_t> range1_t;
    typedef util::value_iter<Iter1_t> type1;
    typedef util::value_iter<Iter2_t> type2;
    static_assert (std::is_same< type1, type2 >::value,
                    "Incompatible iterators\n");

    v_output.clear();
    if (v_input.size() == 0) return;
    if (v_input.size() == 1)
    {
        v_output.emplace_back(move_forward(dest, v_input[0]));
        return;
    };

    uint32_t nrange = v_input.size();
    uint32_t pos_ini = 0;
    while (pos_ini < v_input.size())
    {
        uint32_t nmerge = (nrange + 3) >> 2;
        uint32_t nelem = (nrange + nmerge - 1) / nmerge;
        range1_t rz = full_merge4(dest, &v_input[pos_ini], nelem, comp);
        v_output.emplace_back(rz);
        dest.first = rz.last;
        pos_ini += nelem;
        nrange -= nelem;
    };
    return;
};
//
//-----------------------------------------------------------------------------
//  function : uninit_merge_level4
/// @brief merge the ranges moving the objects and constructing them in
///        uninitialized memory, in the vector v_input
///        using full_merge4. The v_output vector is used as auxiliary memory
///        in the internal process. The final results is in the dest range.
///        All the ranges of v_output are inside the range dest
///
/// @param dest : range where move the elements merged
/// @param v_input : vector of ranges to merge
/// @param v_output : vector of ranges obtained
/// @param comp : comparison object
/// @return range with all the elements moved and constructed
//-----------------------------------------------------------------------------
template<class Value_t, class Iter_t, class Compare>
void uninit_merge_level4(range<Value_t *> dest,
                         std::vector<range<Iter_t> > &v_input,
                         std::vector<range<Value_t *> > &v_output, Compare comp)
{
    typedef range<Value_t *> range1_t;
    typedef util::value_iter<Iter_t> type1;
    static_assert (std::is_same< type1, Value_t >::value,
                    "Incompatible iterators\n");

    v_output.clear();
    if (v_input.size() == 0) return;
    if (v_input.size() == 1)
    {
        v_output.emplace_back(move_construct(dest, v_input[0]));
        return;
    };

    uint32_t nrange = v_input.size();
    uint32_t pos_ini = 0;
    while (pos_ini < v_input.size())
    {
        uint32_t nmerge = (nrange + 3) >> 2;
        uint32_t nelem = (nrange + nmerge - 1) / nmerge;
        range1_t rz = uninit_full_merge4(dest, &v_input[pos_ini], nelem, comp);
        v_output.emplace_back(rz);
        dest.first = rz.last;
        pos_ini += nelem;
        nrange -= nelem;
    };
    return;
};
//
//-----------------------------------------------------------------------------
//  function : merge_vector4
/// @brief merge the ranges in the vector v_input using the merge_level4
///        function. The v_output vector is used as auxiliary memory in the
///        internal process
///        The final results is in the range_output range.
///        All the ranges of v_output are inside the range range_output
///        All the ranges of v_input are inside the range range_input
/// @param range_input : range including all the ranges of v_input
/// @param ange_output : range including all the elements of v_output
/// @param v_input : vector of ranges to merge
/// @param v_output : vector of ranges obtained
/// @param comp : comparison object
/// @return range with all the elements moved
//-----------------------------------------------------------------------------
template<class Iter1_t, class Iter2_t, class Compare>
range<Iter2_t> merge_vector4(range<Iter1_t> range_input,
                             range<Iter2_t> range_output,
                             std::vector<range<Iter1_t> > &v_input,
                             std::vector<range<Iter2_t> > &v_output,
                             Compare comp)
{
    typedef range<Iter2_t> range2_t;
    typedef util::value_iter<Iter1_t> type1;
    typedef util::value_iter<Iter2_t> type2;
    static_assert (std::is_same< type1, type2 >::value,
                    "Incompatible iterators\n");

    v_output.clear();
    if (v_input.size() == 0)
    {
        return range2_t(range_output.first, range_output.first);
    };
    if (v_input.size() == 1)
    {
        return move_forward(range_output, v_input[0]);
    };
    bool sw = false;
    uint32_t nrange = v_input.size();

    while (nrange > 1)
    {
        if (sw)
        {
            merge_level4(range_input, v_output, v_input, comp);
            sw = false;
            nrange = v_input.size();
        }
        else
        {
            merge_level4(range_output, v_input, v_output, comp);
            sw = true;
            nrange = v_output.size();
        };
    };
    return (sw) ? v_output[0] : move_forward(range_output, v_input[0]);
};

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