EIC code displayed by LXR |
|
|
|
|||
File indexing completed on 2025-09-18 09:05:00
0001 //---------------------------------------------------------------------------- 0002 /// @file range.hpp 0003 /// @brief Define a range [first, last), and the associated operations 0004 /// 0005 /// @author Copyright (c) 2016 Francisco José Tapia (fjtapia@gmail.com )\n 0006 /// Distributed under the Boost Software License, Version 1.0.\n 0007 /// ( See accompanyingfile 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_DETAIL_UTIL_RANGE_HPP 0014 #define __BOOST_SORT_PARALLEL_DETAIL_UTIL_RANGE_HPP 0015 0016 #include <cassert> 0017 #include <functional> 0018 #include <memory> 0019 #include <vector> 0020 #include <boost/sort/common/util/algorithm.hpp> 0021 #include <boost/sort/common/util/merge.hpp> 0022 #include <boost/sort/common/util/traits.hpp> 0023 0024 0025 namespace boost 0026 { 0027 namespace sort 0028 { 0029 namespace common 0030 { 0031 0032 ///--------------------------------------------------------------------------- 0033 /// @struct range 0034 /// @brief this represent a range between two iterators 0035 /// @remarks 0036 //---------------------------------------------------------------------------- 0037 template <class Iter_t> 0038 struct range 0039 { 0040 Iter_t first, last; 0041 // 0042 //------------------------------------------------------------------------ 0043 // function : range 0044 /// @brief empty constructor 0045 //------------------------------------------------------------------------ 0046 range(void) { }; 0047 // 0048 //------------------------------------------------------------------------ 0049 // function : range 0050 /// @brief constructor with two parameters 0051 /// @param frs : iterator to the first element 0052 /// @param lst : iterator to the last element 0053 //----------------------------------------------------------------------- 0054 range(const Iter_t &frs, const Iter_t &lst): first(frs), last(lst) { }; 0055 // 0056 //----------------------------------------------------------------------- 0057 // function : empty 0058 /// @brief indicate if the range is empty 0059 /// @return true : empty false : not empty 0060 //----------------------------------------------------------------------- 0061 bool empty(void) const { return (first == last); }; 0062 // 0063 //----------------------------------------------------------------------- 0064 // function : not_empty 0065 /// @brief indicate if the range is not empty 0066 /// @return true : not empty false : empty 0067 //----------------------------------------------------------------------- 0068 bool not_empty(void) const {return (first != last); }; 0069 // 0070 //----------------------------------------------------------------------- 0071 // function : valid 0072 /// @brief Indicate if the range is well constructed, and valid 0073 /// @return true : valid, false : not valid 0074 //----------------------------------------------------------------------- 0075 bool valid(void) const { return ((last - first) >= 0); }; 0076 // 0077 //----------------------------------------------------------------------- 0078 // function : size 0079 /// @brief return the size of the range 0080 /// @return size 0081 //----------------------------------------------------------------------- 0082 size_t size(void) const { return (last - first); }; 0083 // 0084 //------------------------------------------------------------------------ 0085 // function : front 0086 /// @brief return an iterator to the first element of the range 0087 /// @return iterator 0088 //----------------------------------------------------------------------- 0089 Iter_t front(void) const { return first; }; 0090 // 0091 //------------------------------------------------------------------------- 0092 // function : back 0093 /// @brief return an iterator to the last element of the range 0094 /// @return iterator 0095 //------------------------------------------------------------------------- 0096 Iter_t back(void) const {return (last - 1); }; 0097 }; 0098 0099 // 0100 //----------------------------------------------------------------------------- 0101 // function : concat 0102 /// @brief concatenate two contiguous ranges 0103 /// @param it1 : first range 0104 /// @param it2 : second range 0105 /// @return range resulting of the concatenation 0106 //----------------------------------------------------------------------------- 0107 template<class Iter_t> 0108 inline range<Iter_t> concat(const range<Iter_t> &it1, const range<Iter_t> &it2) 0109 { 0110 return range<Iter_t>(it1.first, it2.last); 0111 } 0112 0113 // 0114 //----------------------------------------------------------------------------- 0115 // function : move_forward 0116 /// @brief Move initialized objets from the range src to dest 0117 /// @param dest : range where move the objects 0118 /// @param src : range from where move the objects 0119 /// @return range with the objects moved and the size adjusted 0120 //----------------------------------------------------------------------------- 0121 template <class Iter1_t, class Iter2_t> 0122 inline range<Iter2_t> move_forward(const range<Iter2_t> &dest, 0123 const range<Iter1_t> &src) 0124 { 0125 assert(dest.size() >= src.size()); 0126 Iter2_t it_aux = util::move_forward(dest.first, src.first, src.last); 0127 return range<Iter2_t>(dest.first, it_aux); 0128 } 0129 0130 // 0131 //----------------------------------------------------------------------------- 0132 // function : move_backward 0133 /// @brief Move initialized objets from the range src to dest 0134 /// @param dest : range where move the objects 0135 /// @param src : range from where move the objects 0136 /// @return range with the objects moved and the size adjusted 0137 //----------------------------------------------------------------------------- 0138 template <class Iter1_t, class Iter2_t> 0139 inline range<Iter2_t> move_backward(const range<Iter2_t> &dest, 0140 const range<Iter1_t> &src) 0141 { 0142 assert(dest.size() >= src.size()); 0143 Iter2_t it_aux = util::move_backward(dest.first + src.size(), src.first, 0144 src.last); 0145 return range<Iter2_t>(dest.first, dest.src.size()); 0146 } 0147 0148 //----------------------------------------------------------------------------- 0149 // function : uninit_move 0150 /// @brief Move uninitialized objets from the range src creating them in dest 0151 /// 0152 /// @param dest : range where move and create the objects 0153 /// @param src : range from where move the objects 0154 /// @return range with the objects moved and the size adjusted 0155 //----------------------------------------------------------------------------- 0156 template<class Iter_t, class Value_t = util::value_iter<Iter_t> > 0157 inline range<Value_t*> move_construct(const range<Value_t*> &dest, 0158 const range<Iter_t> &src) 0159 { 0160 Value_t *ptr_aux = util::move_construct(dest.first, src.first, src.last); 0161 return range<Value_t*>(dest.first, ptr_aux); 0162 } 0163 0164 // 0165 //----------------------------------------------------------------------------- 0166 // function : destroy 0167 /// @brief destroy a range of objects 0168 /// @param rng : range to destroy 0169 //----------------------------------------------------------------------------- 0170 template<class Iter_t> 0171 inline void destroy(range<Iter_t> rng) 0172 { 0173 util::destroy(rng.first, rng.last); 0174 } 0175 0176 // 0177 //----------------------------------------------------------------------------- 0178 // function : initialize 0179 /// @brief initialize a range of objects with the object val moving across them 0180 /// @param rng : range of elements not initialized 0181 /// @param val : object used for the initialization 0182 /// @return range initialized 0183 //----------------------------------------------------------------------------- 0184 template<class Iter_t, class Value_t = util::value_iter<Iter_t> > 0185 inline range<Iter_t> initialize(const range<Iter_t> &rng, Value_t &val) 0186 { 0187 util::initialize(rng.first, rng.last, val); 0188 return rng; 0189 } 0190 0191 // 0192 //----------------------------------------------------------------------------- 0193 // function : is_mergeable 0194 /// @brief : indicate if two ranges have a possible merge 0195 /// @param src1 : first range 0196 /// @param src2 : second range 0197 /// @param comp : object for to compare elements 0198 /// @return true : they can be merged 0199 /// false : they can't be merged 0200 //----------------------------------------------------------------------------- 0201 template<class Iter1_t, class Iter2_t, class Compare> 0202 inline bool is_mergeable(const range<Iter1_t> &src1, const range<Iter2_t> &src2, 0203 Compare comp) 0204 { 0205 //------------------------------------------------------------------------ 0206 // Metaprogramming 0207 //------------------------------------------------------------------------ 0208 typedef util::value_iter<Iter1_t> type1; 0209 typedef util::value_iter<Iter2_t> type2; 0210 static_assert (std::is_same< type1, type2 >::value, 0211 "Incompatible iterators\n"); 0212 //------------------------------------------------------------------------ 0213 // Code 0214 //------------------------------------------------------------------------ 0215 return comp(*(src2.front()), *(src1.back())); 0216 } 0217 0218 // 0219 //----------------------------------------------------------------------------- 0220 // function : is_mergeable_stable 0221 /// @brief : indicate if two ranges have a possible merge 0222 /// @param src1 : first range 0223 /// @param src2 : second range 0224 /// @param comp : object for to compare elements 0225 /// @return true : they can be merged 0226 /// false : they can't be merged 0227 //----------------------------------------------------------------------------- 0228 template<class Iter1_t, class Iter2_t, class Compare> 0229 inline bool is_mergeable_stable(const range<Iter1_t> &src1, 0230 const range<Iter2_t> &src2, Compare comp) 0231 { 0232 //------------------------------------------------------------------------ 0233 // Metaprogramming 0234 //------------------------------------------------------------------------ 0235 typedef util::value_iter<Iter1_t> type1; 0236 typedef util::value_iter<Iter2_t> type2; 0237 static_assert (std::is_same< type1, type2 >::value, 0238 "Incompatible iterators\n"); 0239 //------------------------------------------------------------------------ 0240 // Code 0241 //------------------------------------------------------------------------ 0242 return ! comp(*(src1.back()), *(src2.front())); 0243 } 0244 0245 // 0246 //----------------------------------------------------------------------------- 0247 // function : merge 0248 /// @brief Merge two contiguous ranges src1 and src2, and put the result in 0249 /// the range dest, returning the range merged 0250 /// 0251 /// @param dest : range where locate the lements merged. the size of dest 0252 /// must be greater or equal than the sum of the sizes of 0253 /// src1 and src2 0254 /// @param src1 : first range to merge 0255 /// @param src2 : second range to merge 0256 /// @param comp : comparison object 0257 /// @return range with the elements merged and the size adjusted 0258 //----------------------------------------------------------------------------- 0259 template<class Iter1_t, class Iter2_t, class Iter3_t, class Compare> 0260 inline range<Iter3_t> merge(const range<Iter3_t> &dest, 0261 const range<Iter1_t> &src1, 0262 const range<Iter2_t> &src2, Compare comp) 0263 { 0264 Iter3_t it_aux = util::merge(src1.first, src1.last, src2.first, src2.last, 0265 dest.first, comp); 0266 return range<Iter3_t>(dest.first, it_aux); 0267 } 0268 0269 //----------------------------------------------------------------------------- 0270 // function : merge_construct 0271 /// @brief Merge two contiguous uninitialized ranges src1 and src2, and create 0272 /// and move the result in the uninitialized range dest, returning the 0273 /// range merged 0274 // 0275 /// @param dest : range where locate the elements merged. the size of dest 0276 /// must be greater or equal than the sum of the sizes of 0277 /// src1 and src2. Initially is uninitialize memory 0278 /// @param src1 : first range to merge 0279 /// @param src2 : second range to merge 0280 /// @param comp : comparison object 0281 /// @return range with the elements merged and the size adjusted 0282 //----------------------------------------------------------------------------- 0283 template<class Iter1_t, class Iter2_t, class Value_t, class Compare> 0284 inline range<Value_t *> merge_construct(const range<Value_t *> &dest, 0285 const range<Iter1_t> &src1, 0286 const range<Iter2_t> &src2, 0287 Compare comp) 0288 { 0289 Value_t * ptr_aux = util::merge_construct(src1.first, src1.last, src2.first, 0290 src2.last, dest.first, comp); 0291 return range<Value_t*>(dest.first, ptr_aux); 0292 } 0293 0294 // 0295 //--------------------------------------------------------------------------- 0296 // function : half_merge 0297 /// @brief : Merge two initialized buffers. The first buffer is in a separate 0298 /// memory 0299 // 0300 /// @param dest : range where finish the two buffers merged 0301 /// @param src1 : first range to merge in a separate memory 0302 /// @param src2 : second range to merge, in the final part of the 0303 /// range where deposit the final results 0304 /// @param comp : object for compare two elements of the type pointed 0305 /// by the Iter1_t and Iter2_t 0306 /// @return : range with the two buffers merged 0307 //--------------------------------------------------------------------------- 0308 template<class Iter1_t, class Iter2_t, class Compare> 0309 inline range<Iter2_t> merge_half(const range<Iter2_t> &dest, 0310 const range<Iter1_t> &src1, 0311 const range<Iter2_t> &src2, Compare comp) 0312 { 0313 Iter2_t it_aux = util::merge_half(src1.first, src1.last, src2.first, 0314 src2.last, dest.first, comp); 0315 return range<Iter2_t>(dest.first, it_aux); 0316 } 0317 0318 // 0319 //----------------------------------------------------------------------------- 0320 // function : merge_uncontiguous 0321 /// @brief : merge two non contiguous ranges src1, src2, using the range 0322 /// aux as auxiliary memory. The results are in the original ranges 0323 // 0324 /// @param src1 : first range to merge 0325 /// @param src2 : second range to merge 0326 /// @param aux : auxiliary range used in the merge 0327 /// @param comp : object for to compare elements 0328 /// @return true : not changes done, false : changes in the buffers 0329 //----------------------------------------------------------------------------- 0330 template<class Iter1_t, class Iter2_t, class Iter3_t, class Compare> 0331 inline bool merge_uncontiguous(const range<Iter1_t> &src1, 0332 const range<Iter2_t> &src2, 0333 const range<Iter3_t> &aux, Compare comp) 0334 { 0335 return util::merge_uncontiguous(src1.first, src1.last, src2.first, 0336 src2.last, aux.first, comp); 0337 } 0338 0339 // 0340 //----------------------------------------------------------------------------- 0341 // function : merge_contiguous 0342 /// @brief : merge two contiguous ranges ( src1, src2) using buf as 0343 /// auxiliary memory. The results are in the same ranges 0344 /// @param src1 : first range to merge 0345 /// @param src1 : second range to merge 0346 /// @param buf : auxiliary memory used in the merge 0347 /// @param comp : object for to compare elements 0348 /// @return true : not changes done, false : changes in the buffers 0349 //----------------------------------------------------------------------------- 0350 template<class Iter1_t, class Iter2_t, class Compare> 0351 inline range<Iter1_t> merge_contiguous(const range<Iter1_t> &src1, 0352 const range<Iter1_t> &src2, 0353 const range<Iter2_t> &buf, Compare comp) 0354 { 0355 util::merge_contiguous(src1.first, src1.last, src2.last, buf.first, comp); 0356 return concat(src1, src2); 0357 } 0358 0359 // 0360 //----------------------------------------------------------------------------- 0361 // function : merge_flow 0362 /// @brief : merge two ranges, as part of a merge the ranges in a list. This 0363 /// function reduce the number of movements compared with inplace_merge 0364 /// when you need to merge a sequence of ranges. 0365 /// This function merge the ranges rbuf and rng2, and the results 0366 /// are in rng1 and rbuf 0367 // 0368 /// @param rng1 : range where locate the first elements of the merge 0369 /// @param rbuf : range which provide the first elements, and where store 0370 /// the last results of the merge 0371 /// @param rng2 : range which provide the last elements to merge 0372 /// @param comp : object for to compare elements 0373 /// @return true : not changes done, false : changes in the buffers 0374 //----------------------------------------------------------------------------- 0375 template<class Iter1_t, class Iter2_t, class Compare> 0376 static void merge_flow(range<Iter1_t> rng1, range<Iter2_t> rbuf, 0377 range<Iter1_t> rng2, Compare cmp) 0378 { 0379 //------------------------------------------------------------------------- 0380 // Metaprogramming 0381 //------------------------------------------------------------------------- 0382 typedef util::value_iter<Iter1_t> type1; 0383 typedef util::value_iter<Iter2_t> type2; 0384 static_assert (std::is_same< type1, type2 >::value, 0385 "Incompatible iterators\n"); 0386 0387 //------------------------------------------------------------------------- 0388 // Code 0389 //------------------------------------------------------------------------- 0390 range<Iter2_t> rbx(rbuf); 0391 range<Iter1_t> rx1(rng1), rx2(rng2); 0392 assert(rbx.size() == rx1.size() && rx1.size() == rx2.size()); 0393 while (rx1.first != rx1.last) 0394 { 0395 *(rx1.first++) = (cmp(*rbx.first, *rx2.first)) ? 0396 std::move(*(rbx.first++)): 0397 std::move(*(rx2.first++)); 0398 }; 0399 if (rx2.first == rx2.last) return; 0400 if (rbx.first == rbx.last) move_forward(rbuf, rng2); 0401 else merge_half(rbuf, rx2, rbx, cmp); 0402 } 0403 0404 //**************************************************************************** 0405 }// End namespace common 0406 }// End namespace sort 0407 }// End namespace boost 0408 //**************************************************************************** 0409 // 0410 #endif
| [ Source navigation ] | [ Diff markup ] | [ Identifier search ] | [ general search ] |
|
This page was automatically generated by the 2.3.7 LXR engine. The LXR team |
|