summaryrefslogtreecommitdiff
path: root/boost/sort/common/sort_basic.hpp
blob: 68a6f54048766fafa70f30294d250080874ac16d (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
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
//----------------------------------------------------------------------------
/// @file sort_basic.hpp
/// @brief Spin Sort algorithm
///
/// @author Copyright (c) 2016 Francisco José 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_COMMON_SORT_BASIC_HPP
#define __BOOST_SORT_COMMON_SORT_BASIC_HPP

//#include <boost/sort/spinsort/util/indirect.hpp>
#include <boost/sort/insert_sort/insert_sort.hpp>
#include <boost/sort/common/util/traits.hpp>
#include <boost/sort/common/range.hpp>
#include <cstdlib>
#include <functional>
#include <iterator>
#include <memory>
#include <type_traits>
#include <vector>
#include <cstddef>

namespace boost
{
namespace sort
{
namespace common
{

//----------------------------------------------------------------------------
//                USING SENTENCES
//----------------------------------------------------------------------------
using boost::sort::insert_sort;

//-----------------------------------------------------------------------------
//  function : is_stable_sorted_forward
/// @brief examine the elements in the range first, last if they are stable
///        sorted, and return an iterator to the first element not sorted
/// @param first : iterator to the first element in the range
/// @param last : ierator after the last element of the range
/// @param comp : object for to compare two elements
/// @return iterator to the first element not stable sorted. The number of
///         elements sorted is the iterator returned minus first
//-----------------------------------------------------------------------------
template<class Iter_t, class Compare = std::less<value_iter<Iter_t> > >
inline Iter_t is_stable_sorted_forward (Iter_t first, Iter_t last,
                                        Compare comp = Compare())
{
#ifdef __BS_DEBUG
    assert ( (last- first) >= 0);
#endif
    if ((last - first) < 2) return first;
    Iter_t it2 = first + 1;
    for (Iter_t it1 = first; it2 != last and not comp(*it2, *it1); it1 = it2++);
    return it2;
}
//-----------------------------------------------------------------------------
//  function : is_reverse_stable_sorted_forward
/// @brief examine the elements in the range first, last if they are reverse
///        stable sorted, and return an iterator to the first element not
///        reverse stable sorted
/// @param first : iterator to the first element in the range
/// @param last : ierator after the last element of the range
/// @param comp : object for to compare two elements
/// @return iterator to the first element not  reverse stable sorted. The number
///         of elements sorted is the iterator returned minus first
//-----------------------------------------------------------------------------
template<class Iter_t, class Compare = std::less<value_iter<Iter_t> > >
inline Iter_t is_reverse_stable_sorted_forward(Iter_t first, Iter_t last,
                                               Compare comp = Compare())
{
#ifdef __BS_DEBUG
    assert ( (last- first) >= 0);
#endif
    if ((last - first) < 2) return first;
    Iter_t it2 = first + 1;
    for (Iter_t it1 = first; it2 != last and comp(*it2, *it1); it1 = it2++);
    return it2;
};
//-----------------------------------------------------------------------------
//  function : number_stable_sorted_forward
/// @brief examine the elements in the range first, last if they are stable
///        sorted, and return the number of elements sorted
/// @param first : iterator to the first element in the range
/// @param last : ierator after the last element of the range
/// @param comp : object for to compare two elements
/// @param min_process : minimal number of elements to be consideer
/// @return number of element sorted. I f the number is lower than min_process
///         return 0
//-----------------------------------------------------------------------------
template<class Iter_t, class Compare = std::less<value_iter<Iter_t> > >
size_t number_stable_sorted_forward (Iter_t first, Iter_t last,
		                             size_t min_process,
                                     Compare comp = Compare())
{
#ifdef __BS_DEBUG
    assert ( (last- first) >= 0);
#endif
    if ((last - first) < 2) return 0;

    // sorted elements
    Iter_t it2 = first + 1;
    for (Iter_t it1 = first; it2 != last and not comp(*it2, *it1); it1 = it2++);
    size_t nsorted = size_t ( it2 - first);
    if ( nsorted != 1)
    	return (nsorted >= min_process) ? nsorted: 0;

    // reverse sorted elements
    it2 = first + 1;
    for (Iter_t it1 = first; it2 != last and comp(*it2, *it1); it1 = it2++);
    nsorted = size_t ( it2 - first);

    if ( nsorted < min_process) return 0 ;
    util::reverse ( first , it2);
    return nsorted;
};

//-----------------------------------------------------------------------------
//  function : is_stable_sorted_backward
/// @brief examine the elements in the range first, last beginning at end, and
///        if they are stablesorted, and return an iterator to the last element
///        sorted
/// @param first : iterator to the first element in the range
/// @param last : ierator after the last element of the range
/// @param comp : object for to compare two elements
/// @return iterator to the last element stable sorted. The number of
///         elements sorted is the last minus the iterator returned
//-----------------------------------------------------------------------------
template<class Iter_t, class Compare = std::less<value_iter<Iter_t> > >
inline Iter_t is_stable_sorted_backward(Iter_t first, Iter_t last,
                                        Compare comp = Compare())
{
#ifdef __BS_DEBUG
    assert ( (last- first) >= 0);
#endif
    if ((last - first) < 2) return first;
    Iter_t itaux = last - 1;
    while (itaux != first and not comp(*itaux, *(itaux - 1))) {--itaux; };
    return itaux;
}
//-----------------------------------------------------------------------------
//  function : is_reverse_stable_sorted_backward
/// @brief examine the elements in the range first, last beginning at end, and
///        if they are stablesorted, and return an iterator to the last element
///        sorted
/// @param first : iterator to the first element in the range
/// @param last : ierator after the last element of the range
/// @param comp : object for to compare two elements
/// @return iterator to the last element stable sorted. The number of
///         elements sorted is the last minus the iterator returned
//-----------------------------------------------------------------------------
template<class Iter_t, class Compare = std::less<value_iter<Iter_t> > >
inline Iter_t is_reverse_stable_sorted_backward (Iter_t first, Iter_t last,
                                                 Compare comp = Compare())
{
#ifdef __BS_DEBUG
    assert ( (last- first) >= 0);
#endif
    if ((last - first) < 2) return first;
    Iter_t itaux = last - 1;
    for (; itaux != first and comp(*itaux, *(itaux - 1)); --itaux);
    return itaux;
}

//-----------------------------------------------------------------------------
//  function : number_stable_sorted_backward
/// @brief examine the elements in the range first, last if they are stable
///        sorted, and return the number of elements sorted
/// @param first : iterator to the first element in the range
/// @param last : ierator after the last element of the range
/// @param comp : object for to compare two elements
/// @param min_process : minimal number of elements to be consideer
/// @return number of element sorted. I f the number is lower than min_process
///         return 0
//-----------------------------------------------------------------------------
template<class Iter_t, class Compare = std::less<value_iter<Iter_t> > >
size_t number_stable_sorted_backward (Iter_t first, Iter_t last,
		                             size_t min_process,
                                     Compare comp = Compare())
{
#ifdef __BS_DEBUG
    assert ( (last- first) >= 0);
#endif
    if ((last - first) < 2) return 0;
    Iter_t itaux = last - 1;
    while (itaux != first and not comp(*itaux, *(itaux - 1))) {--itaux; };
    size_t nsorted = size_t ( last - itaux);
    if ( nsorted != 1)
    	return ( nsorted >= min_process)?nsorted: 0 ;

    itaux = last - 1;
    for (; itaux != first and comp(*itaux, *(itaux - 1)); --itaux);
    nsorted = size_t ( last - itaux);
    if ( nsorted < min_process) return 0 ;
    util::reverse ( itaux, last );
    return nsorted;
}
//-----------------------------------------------------------------------------
//  function : internal_sort
/// @brief this function divide r_input in two parts, sort it,and merge moving
///        the elements to range_buf
/// @param range_input : range with the elements to sort
/// @param range_buffer : range with the elements sorted
/// @param comp : object for to compare two elements
/// @param level : when is 1, sort with the insertionsort algorithm
///                if not make a recursive call splitting the ranges
//
//-----------------------------------------------------------------------------
template <class Iter1_t, class Iter2_t, class Compare>
inline void internal_sort (const range<Iter1_t> &rng1,
		                   const range<Iter2_t> &rng2,
                           Compare comp, uint32_t level, bool even = true)
{
    //-----------------------------------------------------------------------
    //                  metaprogram
    //-----------------------------------------------------------------------
    typedef value_iter<Iter1_t> value_t;
    typedef value_iter<Iter2_t> value2_t;
    static_assert (std::is_same< value_t, value2_t>::value,
                    "Incompatible iterators\n");

    //-----------------------------------------------------------------------
    //                  program
    //-----------------------------------------------------------------------
#ifdef __BS_DEBUG
    assert (rng1.size ( ) == rng2.size ( ) );
#endif
    size_t nelem = (rng1.size() + 1) >> 1;

    range<Iter1_t> rng1_left(rng1.first, rng1.first + nelem), 
                   rng1_right(rng1.first + nelem, rng1.last);

    range<Iter2_t> rng2_left(rng2.first, rng2.first + nelem), 
                   rng2_right(rng2.first + nelem, rng2.last);

    if (nelem <= 32 and (level & 1) == even)
    {
        insert_sort(rng1_left.first, rng1_left.last, comp);
        insert_sort(rng1_right.first, rng1_right.last, comp);
    }
    else
    {
        internal_sort(rng2_left, rng1_left, comp, level + 1, even);
        internal_sort(rng2_right, rng1_right, comp, level + 1, even);
    };
    merge(rng2, rng1_left, rng1_right, comp);
};
//-----------------------------------------------------------------------------
//  function : range_sort_data
/// @brief this sort elements using the range_sort function and receiving a
///        buffer of initialized memory
/// @param rng_data : range with the elements to sort
/// @param rng_aux : range of at least the same memory than rng_data used as
///                  auxiliary memory in the sorting
/// @param comp : object for to compare two elements
//-----------------------------------------------------------------------------
template<class Iter1_t, class Iter2_t, class Compare>
static void range_sort_data (const range<Iter1_t> & rng_data,
                             const range<Iter2_t> & rng_aux, Compare comp)
{
    //-----------------------------------------------------------------------
    //                  metaprogram
    //-----------------------------------------------------------------------
    typedef value_iter<Iter1_t> value_t;
    typedef value_iter<Iter2_t> value2_t;
    static_assert (std::is_same< value_t, value2_t>::value,
                    "Incompatible iterators\n");

    //------------------------------------------------------------------------
    //                    program
    //------------------------------------------------------------------------
#ifdef __BS_DEBUG
    assert ( rng_data.size() == rng_aux.size());
#endif
    // minimal number of element before to jump to insertionsort
    const uint32_t sort_min = 32;
    if (rng_data.size() <= sort_min)
    {
        insert_sort(rng_data.first, rng_data.last, comp);
        return;
    };

    internal_sort(rng_aux, rng_data, comp, 0, true);
};
//-----------------------------------------------------------------------------
//  function : range_sort_buffer
/// @brief this sort elements using the range_sort function and receiving a
///        buffer of initialized memory
/// @param rng_data : range with the elements to sort
/// @param rng_aux : range of at least the same memory than rng_data used as
///                  auxiliary memory in the sorting
/// @param comp : object for to compare two elements
//-----------------------------------------------------------------------------
template<class Iter1_t, class Iter2_t, class Compare>
static void range_sort_buffer(const range<Iter1_t> & rng_data,
                              const range<Iter2_t> & rng_aux, Compare comp)
{
    //-----------------------------------------------------------------------
    //                  metaprogram
    //-----------------------------------------------------------------------
    typedef value_iter<Iter1_t> value_t;
    typedef value_iter<Iter2_t> value2_t;
    static_assert (std::is_same< value_t, value2_t>::value,
                    "Incompatible iterators\n");

    //------------------------------------------------------------------------
    //                    program
    //------------------------------------------------------------------------
#ifdef __BS_DEBUG
    assert ( rng_data.size() == rng_aux.size());
#endif
    // minimal number of element before to jump to insertionsort
    const uint32_t sort_min = 32;
    if (rng_data.size() <= sort_min)
    {
        insert_sort(rng_data.first, rng_data.last, comp);
        move_forward(rng_aux, rng_data);
        return;
    };

    internal_sort(rng_data, rng_aux, comp, 0, false);
};
//****************************************************************************
};//    End namespace common
};//    End namespace sort
};//    End namepspace boost
//****************************************************************************
//
#endif