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