EIC code displayed by LXR |
|
|
|
|||
File indexing completed on 2025-09-17 08:50:39
0001 //---------------------------------------------------------------------------- 0002 /// @file indirect.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_PARALLEL_COMMON_INDIRECT_HPP 0014 #define __BOOST_SORT_PARALLEL_COMMON_INDIRECT_HPP 0015 0016 //#include <boost/sort/common/atomic.hpp> 0017 #include <boost/sort/common/util/traits.hpp> 0018 #include <functional> 0019 #include <iterator> 0020 #include <type_traits> 0021 #include <vector> 0022 0023 namespace boost 0024 { 0025 namespace sort 0026 { 0027 namespace common 0028 { 0029 0030 // 0031 //--------------------------------------------------------------------------- 0032 /// @struct less_ptr_no_null 0033 /// 0034 /// @remarks this is the comparison object for pointers. Compare the objects 0035 /// pointed by the iterators 0036 //--------------------------------------------------------------------------- 0037 template<class Iter_t, class Compare = util::compare_iter<Iter_t> > 0038 struct less_ptr_no_null 0039 { 0040 //----------------------------- Variables ----------------------- 0041 Compare comp; // comparison object of the elements pointed by Iter_t 0042 0043 //------------------------------------------------------------------------ 0044 // function : less_ptr_no_null 0045 /// @brief constructor from a Compare object 0046 /// @param C1 : comparison object 0047 //----------------------------------------------------------------------- 0048 less_ptr_no_null(Compare C1 = Compare()): comp(C1) { }; 0049 0050 //------------------------------------------------------------------------ 0051 // function : operator ( ) 0052 /// @brief Make the comparison of the objects pointed by T1 and T2, using 0053 // the internal comp 0054 // 0055 /// @param T1 : first iterator 0056 /// @param T2 : second iterator 0057 /// @return bool result of the comparison 0058 //----------------------------------------------------------------------- 0059 bool operator( )(Iter_t T1, Iter_t T2) const 0060 { 0061 return comp(*T1, *T2); 0062 }; 0063 }; 0064 // 0065 //----------------------------------------------------------------------------- 0066 // function : create_index 0067 /// @brief From a vector of objects, create a vector of iterators to 0068 /// the objects 0069 /// 0070 /// @param first : iterator to the first element of the range 0071 /// @param last : iterator to the element after the last of the range 0072 /// @param index : vector where store the iterators 0073 //----------------------------------------------------------------------------- 0074 template<class Iter_t> 0075 void create_index(Iter_t first, Iter_t last, std::vector<Iter_t> &index) 0076 { 0077 auto nelem = last - first; 0078 assert(nelem >= 0); 0079 index.clear(); 0080 index.reserve(nelem); 0081 for (; first != last; ++first) index.push_back(first); 0082 } 0083 0084 // 0085 //----------------------------------------------------------------------------- 0086 // function : sort_index 0087 /// @brief This function transform a logical sort of the elements in the index 0088 /// in a physical sort 0089 // 0090 /// @param global_first : iterator to the first element of the data 0091 /// @param [in] index : vector of the iterators 0092 //----------------------------------------------------------------------------- 0093 template<class Iter_t> 0094 void sort_index(Iter_t global_first, std::vector<Iter_t> &index) 0095 { 0096 typedef util::value_iter<Iter_t> value_t; 0097 0098 size_t pos_dest = 0; 0099 size_t pos_src = 0; 0100 size_t pos_in_vector = 0; 0101 size_t nelem = index.size(); 0102 Iter_t it_dest, it_src; 0103 0104 while (pos_in_vector < nelem) 0105 { 0106 while (pos_in_vector < nelem && 0107 (size_t(index[pos_in_vector] - global_first)) == pos_in_vector) 0108 { 0109 ++pos_in_vector; 0110 } 0111 0112 if (pos_in_vector == nelem) return; 0113 pos_dest = pos_src = pos_in_vector; 0114 it_dest = global_first + pos_dest; 0115 value_t Aux = std::move(*it_dest); 0116 0117 while ((pos_src = (size_t(index[pos_dest] - global_first))) 0118 != pos_in_vector) 0119 { 0120 index[pos_dest] = it_dest; 0121 it_src = global_first + pos_src; 0122 *it_dest = std::move(*it_src); 0123 it_dest = it_src; 0124 pos_dest = pos_src; 0125 } 0126 0127 *it_dest = std::move(Aux); 0128 index[pos_dest] = it_dest; 0129 ++pos_in_vector; 0130 } 0131 } 0132 0133 template<class func, class Iter_t, class Compare = util::compare_iter<Iter_t> > 0134 void indirect_sort(func method, Iter_t first, Iter_t last, Compare comp) 0135 { 0136 auto nelem = (last - first); 0137 assert(nelem >= 0); 0138 if (nelem < 2) return; 0139 std::vector<Iter_t> index; 0140 index.reserve((size_t) nelem); 0141 create_index(first, last, index); 0142 less_ptr_no_null<Iter_t, Compare> index_comp(comp); 0143 method(index.begin(), index.end(), index_comp); 0144 sort_index(first, index); 0145 } 0146 0147 // 0148 //**************************************************************************** 0149 }// End namespace common 0150 }// End namespace sort 0151 }// End namespace boost 0152 //**************************************************************************** 0153 // 0154 #endif
| [ Source navigation ] | [ Diff markup ] | [ Identifier search ] | [ general search ] |
|
This page was automatically generated by the 2.3.7 LXR engine. The LXR team |
|