EIC code displayed by LXR |
|
|
|
|||
File indexing completed on 2025-01-18 09:51:46
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 // function : sort_index 0086 /// @brief This function transform a logical sort of the elements in the index 0087 /// in a physical sort 0088 // 0089 /// @param global_first : iterator to the first element of the data 0090 /// @param [in] index : vector of the iterators 0091 //----------------------------------------------------------------------------- 0092 template<class Iter_t> 0093 void sort_index(Iter_t global_first, std::vector<Iter_t> &index) 0094 { 0095 typedef util::value_iter<Iter_t> value_t; 0096 0097 size_t pos_dest = 0; 0098 size_t pos_src = 0; 0099 size_t pos_in_vector = 0; 0100 size_t nelem = index.size(); 0101 Iter_t it_dest, it_src; 0102 0103 while (pos_in_vector < nelem) 0104 { 0105 while (pos_in_vector < nelem and 0106 (size_t(index[pos_in_vector] - global_first)) == pos_in_vector) 0107 { 0108 ++pos_in_vector; 0109 }; 0110 0111 if (pos_in_vector == nelem) return; 0112 pos_dest = pos_src = pos_in_vector; 0113 it_dest = global_first + pos_dest; 0114 value_t Aux = std::move(*it_dest); 0115 0116 while ((pos_src = (size_t(index[pos_dest] - global_first))) 0117 != pos_in_vector) 0118 { 0119 index[pos_dest] = it_dest; 0120 it_src = global_first + pos_src; 0121 *it_dest = std::move(*it_src); 0122 it_dest = it_src; 0123 pos_dest = pos_src; 0124 }; 0125 0126 *it_dest = std::move(Aux); 0127 index[pos_dest] = it_dest; 0128 ++pos_in_vector; 0129 }; 0130 }; 0131 0132 template<class func, class Iter_t, class Compare = util::compare_iter<Iter_t> > 0133 void indirect_sort(func method, Iter_t first, Iter_t last, Compare comp) 0134 { 0135 auto nelem = (last - first); 0136 assert(nelem >= 0); 0137 if (nelem < 2) return; 0138 std::vector<Iter_t> index; 0139 index.reserve((size_t) nelem); 0140 create_index(first, last, index); 0141 less_ptr_no_null<Iter_t, Compare> index_comp(comp); 0142 method(index.begin(), index.end(), index_comp); 0143 sort_index(first, index); 0144 }; 0145 0146 // 0147 //**************************************************************************** 0148 };// End namespace common 0149 };// End namespace sort 0150 };// End namespace boost 0151 //**************************************************************************** 0152 // 0153 #endif
| [ Source navigation ] | [ Diff markup ] | [ Identifier search ] | [ general search ] |
|
This page was automatically generated by the 2.3.7 LXR engine. The LXR team |
|