EIC code displayed by LXR |
|
|
|
|||
File indexing completed on 2025-01-18 09:51:46
0001 //---------------------------------------------------------------------------- 0002 /// @file rearrange.hpp 0003 /// @brief Indirect algorithm 0004 /// 0005 /// @author Copyright (c) 2016 Francisco Jose Tapia (fjtapia@gmail.com )\n 0006 /// Distributed under the Boost Software License, Version 1.0.\n 0007 /// ( See accompanying file LICENSE_1_0.txt or copy at 0008 /// http://www.boost.org/LICENSE_1_0.txt ) 0009 /// @version 0.1 0010 /// 0011 /// @remarks 0012 //----------------------------------------------------------------------------- 0013 #ifndef __BOOST_SORT_COMMON_REARRANGE_HPP 0014 #define __BOOST_SORT_COMMON_REARRANGE_HPP 0015 0016 #include <ciso646> 0017 #include <functional> 0018 #include <iterator> 0019 #include <type_traits> 0020 #include <vector> 0021 #include <cassert> 0022 #include <boost/sort/common/util/traits.hpp> 0023 0024 0025 namespace boost 0026 { 0027 namespace sort 0028 { 0029 namespace common 0030 { 0031 0032 template<class Iter_data> 0033 struct filter_iterator 0034 { 0035 //----------------------------------------------------------------------- 0036 // Variables 0037 //----------------------------------------------------------------------- 0038 Iter_data origin; 0039 0040 //----------------------------------------------------------------------- 0041 // Functions 0042 //----------------------------------------------------------------------- 0043 filter_iterator(Iter_data global_first): origin(global_first) { }; 0044 size_t operator ()(Iter_data itx) const 0045 { 0046 return size_t(itx - origin); 0047 } 0048 }; 0049 0050 struct filter_pos 0051 { 0052 size_t operator ()(size_t pos) const { return pos; }; 0053 }; 0054 0055 // 0056 //----------------------------------------------------------------------------- 0057 // function : rearrange 0058 /// @brief This function transform a logical sort of the elements in the index 0059 /// of iterators in a physical sort. 0060 // 0061 /// @param global_first : iterator to the first element of the data 0062 /// @param [in] index : vector of the iterators 0063 //----------------------------------------------------------------------------- 0064 template<class Iter_data, class Iter_index, class Filter_pos> 0065 void rearrange(Iter_data global_first, Iter_index itx_first, 0066 Iter_index itx_last, Filter_pos pos) 0067 { 0068 //----------------------------------------------------------------------- 0069 // Metaprogramming 0070 //----------------------------------------------------------------------- 0071 typedef util::value_iter<Iter_data> value_data; 0072 typedef util::value_iter<Iter_index> value_index; 0073 0074 //------------------------------------------------------------------------- 0075 // Code 0076 //------------------------------------------------------------------------- 0077 assert((itx_last - itx_first) >= 0); 0078 size_t pos_dest, pos_src, pos_ini; 0079 size_t nelem = size_t(itx_last - itx_first); 0080 Iter_data data = global_first; 0081 Iter_index index = itx_first; 0082 0083 pos_ini = 0; 0084 while (pos_ini < nelem) 0085 { 0086 while (pos_ini < nelem and pos(index[pos_ini]) == pos_ini) 0087 ++pos_ini; 0088 if (pos_ini == nelem) return; 0089 pos_dest = pos_src = pos_ini; 0090 value_data aux = std::move(data[pos_ini]); 0091 value_index itx_src = std::move(index[pos_ini]); 0092 0093 while ((pos_src = pos(itx_src)) != pos_ini) 0094 { 0095 using std::swap; 0096 data[pos_dest] = std::move(data[pos_src]); 0097 swap(itx_src, index[pos_src]); 0098 pos_dest = pos_src; 0099 }; 0100 0101 data[pos_dest] = std::move(aux); 0102 index[pos_ini] = std::move(itx_src); 0103 ++pos_ini; 0104 }; 0105 }; 0106 0107 /* 0108 // 0109 //----------------------------------------------------------------------------- 0110 // function : rearrange_pos 0111 /// @brief This function transform a logical sort of the elements in the index 0112 /// of iterators in a physical sort. 0113 // 0114 /// @param global_first : iterator to the first element of the data 0115 /// @param [in] index : vector of the iterators 0116 //----------------------------------------------------------------------------- 0117 template < class Iter_t, class Number > 0118 void rearrange_pos (Iter_t global_first, std::vector< Number> &index) 0119 { 0120 //------------------------------------------------------------------------- 0121 // METAPROGRAMMING AND DEFINITIONS 0122 //------------------------------------------------------------------------- 0123 static_assert ( std::is_integral<Number>::value, "Incompatible Types"); 0124 typedef iter_value< Iter_t > value_t; 0125 0126 //------------------------------------------------------------------------- 0127 // CODE 0128 //------------------------------------------------------------------------- 0129 size_t pos_dest = 0; 0130 size_t pos_src = 0; 0131 size_t pos_ini = 0; 0132 size_t nelem = index.size ( ); 0133 Iter_t it_dest (global_first), it_src(global_first); 0134 0135 while (pos_ini < nelem) 0136 { 0137 while (pos_ini < nelem and 0138 index[pos_ini] == pos_ini) 0139 { 0140 ++pos_ini; 0141 }; 0142 0143 if (pos_ini == nelem) return; 0144 pos_dest = pos_src = pos_ini; 0145 it_dest = global_first + pos_dest; 0146 value_t Aux = std::move (*it_dest); 0147 0148 while ((pos_src = index[pos_dest]) != pos_ini) 0149 { 0150 index[pos_dest] = it_dest - global_first; 0151 it_src = global_first + pos_src; 0152 *it_dest = std::move (*it_src); 0153 it_dest = it_src; 0154 pos_dest = pos_src; 0155 }; 0156 0157 *it_dest = std::move (Aux); 0158 index[pos_dest] = it_dest - global_first; 0159 ++pos_ini; 0160 }; 0161 }; 0162 */ 0163 // 0164 //**************************************************************************** 0165 };// End namespace common 0166 };// End namespace sort 0167 };// End namespace boost 0168 //**************************************************************************** 0169 // 0170 #endif
| [ Source navigation ] | [ Diff markup ] | [ Identifier search ] | [ general search ] |
|
This page was automatically generated by the 2.3.7 LXR engine. The LXR team |
|