summaryrefslogtreecommitdiff
path: root/boost/sort/common/rearrange.hpp
blob: 5c65c4f2b749f68a43c5502d40bc9af927cf4631 (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
//----------------------------------------------------------------------------
/// @file rearrange.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_COMMON_REARRANGE_HPP
#define __BOOST_SORT_COMMON_REARRANGE_HPP

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

namespace boost
{
namespace sort
{
namespace common
{

template<class Iter_data>
struct filter_iterator
{
    //-----------------------------------------------------------------------
    //                   Variables
    //-----------------------------------------------------------------------
    Iter_data origin;

    //-----------------------------------------------------------------------
    //                   Functions
    //-----------------------------------------------------------------------
    filter_iterator(Iter_data global_first): origin(global_first) { };
    size_t operator ()(Iter_data itx) const
    {
        return size_t(itx - origin);
    }
};

struct filter_pos
{
    size_t operator ()(size_t pos) const {  return pos; };
};

//
//-----------------------------------------------------------------------------
//  function : rearrange
/// @brief This function transform a logical sort of the elements in the index  
///        of iterators 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_data, class Iter_index, class Filter_pos>
void rearrange(Iter_data global_first, Iter_index itx_first,
               Iter_index itx_last, Filter_pos pos)
{
    //-----------------------------------------------------------------------
    //                    Metaprogramming
    //-----------------------------------------------------------------------
    typedef util::value_iter<Iter_data>     value_data;
    typedef util::value_iter<Iter_index>    value_index;

    //-------------------------------------------------------------------------
    //                     Code
    //-------------------------------------------------------------------------	
    assert((itx_last - itx_first) >= 0);
    size_t pos_dest, pos_src, pos_ini;
    size_t nelem = size_t(itx_last - itx_first);
    Iter_data data = global_first;
    Iter_index index = itx_first;

    pos_ini = 0;
    while (pos_ini < nelem)
    {
        while (pos_ini < nelem and pos(index[pos_ini]) == pos_ini)
            ++pos_ini;
        if (pos_ini == nelem) return;
        pos_dest = pos_src = pos_ini;
        value_data aux = std::move(data[pos_ini]);
        value_index itx_src = std::move(index[pos_ini]);

        while ((pos_src = pos(itx_src)) != pos_ini)
        {
            data[pos_dest] = std::move(data[pos_src]);
            std::swap(itx_src, index[pos_src]);
            pos_dest = pos_src;
        };

        data[pos_dest] = std::move(aux);
        index[pos_ini] = std::move(itx_src);
        ++pos_ini;
    };
};

/*
 //
 //-----------------------------------------------------------------------------
 //  function : rearrange_pos
 /// @brief This function transform a logical sort of the elements in the index  
 ///        of iterators 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, class Number >
 void rearrange_pos (Iter_t global_first, std::vector< Number> &index)
 {	
 //-------------------------------------------------------------------------
 //          METAPROGRAMMING AND DEFINITIONS
 //-------------------------------------------------------------------------
 static_assert ( std::is_integral<Number>::value, "Incompatible Types");
 typedef iter_value< Iter_t > value_t;

 //-------------------------------------------------------------------------
 //                     CODE
 //-------------------------------------------------------------------------
 size_t pos_dest = 0;
 size_t pos_src = 0;
 size_t pos_ini = 0;
 size_t nelem = index.size ( );
 Iter_t it_dest (global_first), it_src(global_first);

 while (pos_ini < nelem)
 {
 while (pos_ini < nelem and
 index[pos_ini] == pos_ini)
 {
 ++pos_ini;
 };

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

 while ((pos_src = index[pos_dest]) != pos_ini)
 {
 index[pos_dest] = it_dest - global_first;
 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 - global_first;
 ++pos_ini;
 };
 };
 */
//
//****************************************************************************
};//    End namespace common
};//    End namespace sort
};//    End namespace boost
//****************************************************************************
//
#endif