| 1 | //---------------------------------------------------------------------------- |
| 2 | /// @file range.hpp |
| 3 | /// @brief Define a range [first, last), and the associated operations |
| 4 | /// |
| 5 | /// @author Copyright (c) 2016 Francisco José Tapia (fjtapia@gmail.com )\n |
| 6 | /// Distributed under the Boost Software License, Version 1.0.\n |
| 7 | /// ( See accompanyingfile LICENSE_1_0.txt or copy at |
| 8 | /// http://www.boost.org/LICENSE_1_0.txt ) |
| 9 | /// @version 0.1 |
| 10 | /// |
| 11 | /// @remarks |
| 12 | //----------------------------------------------------------------------------- |
| 13 | #ifndef __BOOST_SORT_PARALLEL_DETAIL_UTIL_RANGE_HPP |
| 14 | #define __BOOST_SORT_PARALLEL_DETAIL_UTIL_RANGE_HPP |
| 15 | |
| 16 | #include <ciso646> |
| 17 | #include <cassert> |
| 18 | #include <functional> |
| 19 | #include <memory> |
| 20 | #include <vector> |
| 21 | #include <boost/sort/common/util/algorithm.hpp> |
| 22 | #include <boost/sort/common/util/merge.hpp> |
| 23 | #include <boost/sort/common/util/traits.hpp> |
| 24 | |
| 25 | |
| 26 | namespace boost |
| 27 | { |
| 28 | namespace sort |
| 29 | { |
| 30 | namespace common |
| 31 | { |
| 32 | |
| 33 | ///--------------------------------------------------------------------------- |
| 34 | /// @struct range |
| 35 | /// @brief this represent a range between two iterators |
| 36 | /// @remarks |
| 37 | //---------------------------------------------------------------------------- |
| 38 | template <class Iter_t> |
| 39 | struct range |
| 40 | { |
| 41 | Iter_t first, last; |
| 42 | // |
| 43 | //------------------------------------------------------------------------ |
| 44 | // function : range |
| 45 | /// @brief empty constructor |
| 46 | //------------------------------------------------------------------------ |
| 47 | range(void) { }; |
| 48 | // |
| 49 | //------------------------------------------------------------------------ |
| 50 | // function : range |
| 51 | /// @brief constructor with two parameters |
| 52 | /// @param frs : iterator to the first element |
| 53 | /// @param lst : iterator to the last element |
| 54 | //----------------------------------------------------------------------- |
| 55 | range(const Iter_t &frs, const Iter_t &lst): first(frs), last(lst) { }; |
| 56 | // |
| 57 | //----------------------------------------------------------------------- |
| 58 | // function : empty |
| 59 | /// @brief indicate if the range is empty |
| 60 | /// @return true : empty false : not empty |
| 61 | //----------------------------------------------------------------------- |
| 62 | bool empty(void) const { return (first == last); }; |
| 63 | // |
| 64 | //----------------------------------------------------------------------- |
| 65 | // function : not_empty |
| 66 | /// @brief indicate if the range is not empty |
| 67 | /// @return true : not empty false : empty |
| 68 | //----------------------------------------------------------------------- |
| 69 | bool not_empty(void) const {return (first != last); }; |
| 70 | // |
| 71 | //----------------------------------------------------------------------- |
| 72 | // function : valid |
| 73 | /// @brief Indicate if the range is well constructed, and valid |
| 74 | /// @return true : valid, false : not valid |
| 75 | //----------------------------------------------------------------------- |
| 76 | bool valid(void) const { return ((last - first) >= 0); }; |
| 77 | // |
| 78 | //----------------------------------------------------------------------- |
| 79 | // function : size |
| 80 | /// @brief return the size of the range |
| 81 | /// @return size |
| 82 | //----------------------------------------------------------------------- |
| 83 | size_t size(void) const { return (last - first); }; |
| 84 | // |
| 85 | //------------------------------------------------------------------------ |
| 86 | // function : front |
| 87 | /// @brief return an iterator to the first element of the range |
| 88 | /// @return iterator |
| 89 | //----------------------------------------------------------------------- |
| 90 | Iter_t front(void) const { return first; }; |
| 91 | // |
| 92 | //------------------------------------------------------------------------- |
| 93 | // function : back |
| 94 | /// @brief return an iterator to the last element of the range |
| 95 | /// @return iterator |
| 96 | //------------------------------------------------------------------------- |
| 97 | Iter_t back(void) const {return (last - 1); }; |
| 98 | }; |
| 99 | |
| 100 | // |
| 101 | //----------------------------------------------------------------------------- |
| 102 | // function : concat |
| 103 | /// @brief concatenate two contiguous ranges |
| 104 | /// @param it1 : first range |
| 105 | /// @param it2 : second range |
| 106 | /// @return range resulting of the concatenation |
| 107 | //----------------------------------------------------------------------------- |
| 108 | template<class Iter_t> |
| 109 | inline range<Iter_t> concat(const range<Iter_t> &it1, const range<Iter_t> &it2) |
| 110 | { |
| 111 | return range<Iter_t>(it1.first, it2.last); |
| 112 | } |
| 113 | ; |
| 114 | // |
| 115 | //----------------------------------------------------------------------------- |
| 116 | // function : move_forward |
| 117 | /// @brief Move initialized objets from the range src to dest |
| 118 | /// @param dest : range where move the objects |
| 119 | /// @param src : range from where move the objects |
| 120 | /// @return range with the objects moved and the size adjusted |
| 121 | //----------------------------------------------------------------------------- |
| 122 | template <class Iter1_t, class Iter2_t> |
| 123 | inline range<Iter2_t> move_forward(const range<Iter2_t> &dest, |
| 124 | const range<Iter1_t> &src) |
| 125 | { |
| 126 | assert(dest.size() >= src.size()); |
| 127 | Iter2_t it_aux = util::move_forward(dest.first, src.first, src.last); |
| 128 | return range<Iter2_t>(dest.first, it_aux); |
| 129 | }; |
| 130 | // |
| 131 | //----------------------------------------------------------------------------- |
| 132 | // function : move_backward |
| 133 | /// @brief Move initialized objets from the range src to dest |
| 134 | /// @param dest : range where move the objects |
| 135 | /// @param src : range from where move the objects |
| 136 | /// @return range with the objects moved and the size adjusted |
| 137 | //----------------------------------------------------------------------------- |
| 138 | template <class Iter1_t, class Iter2_t> |
| 139 | inline range<Iter2_t> move_backward(const range<Iter2_t> &dest, |
| 140 | const range<Iter1_t> &src) |
| 141 | { |
| 142 | assert(dest.size() >= src.size()); |
| 143 | Iter2_t it_aux = util::move_backward(dest.first + src.size(), src.first, |
| 144 | src.last); |
| 145 | return range<Iter2_t>(dest.first, dest.src.size()); |
| 146 | }; |
| 147 | |
| 148 | //----------------------------------------------------------------------------- |
| 149 | // function : uninit_move |
| 150 | /// @brief Move uninitialized objets from the range src creating them in dest |
| 151 | /// |
| 152 | /// @param dest : range where move and create the objects |
| 153 | /// @param src : range from where move the objects |
| 154 | /// @return range with the objects moved and the size adjusted |
| 155 | //----------------------------------------------------------------------------- |
| 156 | template<class Iter_t, class Value_t = util::value_iter<Iter_t> > |
| 157 | inline range<Value_t*> move_construct(const range<Value_t*> &dest, |
| 158 | const range<Iter_t> &src) |
| 159 | { |
| 160 | Value_t *ptr_aux = util::move_construct(dest.first, src.first, src.last); |
| 161 | return range<Value_t*>(dest.first, ptr_aux); |
| 162 | }; |
| 163 | // |
| 164 | //----------------------------------------------------------------------------- |
| 165 | // function : destroy |
| 166 | /// @brief destroy a range of objects |
| 167 | /// @param rng : range to destroy |
| 168 | //----------------------------------------------------------------------------- |
| 169 | template<class Iter_t> |
| 170 | inline void destroy(range<Iter_t> rng) |
| 171 | { |
| 172 | util::destroy(rng.first, rng.last); |
| 173 | }; |
| 174 | // |
| 175 | //----------------------------------------------------------------------------- |
| 176 | // function : initialize |
| 177 | /// @brief initialize a range of objects with the object val moving across them |
| 178 | /// @param rng : range of elements not initialized |
| 179 | /// @param val : object used for the initialization |
| 180 | /// @return range initialized |
| 181 | //----------------------------------------------------------------------------- |
| 182 | template<class Iter_t, class Value_t = util::value_iter<Iter_t> > |
| 183 | inline range<Iter_t> initialize(const range<Iter_t> &rng, Value_t &val) |
| 184 | { |
| 185 | util::initialize(rng.first, rng.last, val); |
| 186 | return rng; |
| 187 | }; |
| 188 | // |
| 189 | //----------------------------------------------------------------------------- |
| 190 | // function : is_mergeable |
| 191 | /// @brief : indicate if two ranges have a possible merge |
| 192 | /// @param src1 : first range |
| 193 | /// @param src2 : second range |
| 194 | /// @param comp : object for to compare elements |
| 195 | /// @return true : they can be merged |
| 196 | /// false : they can't be merged |
| 197 | //----------------------------------------------------------------------------- |
| 198 | template<class Iter1_t, class Iter2_t, class Compare> |
| 199 | inline bool is_mergeable(const range<Iter1_t> &src1, const range<Iter2_t> &src2, |
| 200 | Compare comp) |
| 201 | { |
| 202 | //------------------------------------------------------------------------ |
| 203 | // Metaprogramming |
| 204 | //------------------------------------------------------------------------ |
| 205 | typedef util::value_iter<Iter1_t> type1; |
| 206 | typedef util::value_iter<Iter2_t> type2; |
| 207 | static_assert (std::is_same< type1, type2 >::value, |
| 208 | "Incompatible iterators\n" ); |
| 209 | //------------------------------------------------------------------------ |
| 210 | // Code |
| 211 | //------------------------------------------------------------------------ |
| 212 | return comp(*(src2.front()), *(src1.back())); |
| 213 | }; |
| 214 | // |
| 215 | //----------------------------------------------------------------------------- |
| 216 | // function : is_mergeable_stable |
| 217 | /// @brief : indicate if two ranges have a possible merge |
| 218 | /// @param src1 : first range |
| 219 | /// @param src2 : second range |
| 220 | /// @param comp : object for to compare elements |
| 221 | /// @return true : they can be merged |
| 222 | /// false : they can't be merged |
| 223 | //----------------------------------------------------------------------------- |
| 224 | template<class Iter1_t, class Iter2_t, class Compare> |
| 225 | inline bool is_mergeable_stable(const range<Iter1_t> &src1, |
| 226 | const range<Iter2_t> &src2, Compare comp) |
| 227 | { |
| 228 | //------------------------------------------------------------------------ |
| 229 | // Metaprogramming |
| 230 | //------------------------------------------------------------------------ |
| 231 | typedef util::value_iter<Iter1_t> type1; |
| 232 | typedef util::value_iter<Iter2_t> type2; |
| 233 | static_assert (std::is_same< type1, type2 >::value, |
| 234 | "Incompatible iterators\n" ); |
| 235 | //------------------------------------------------------------------------ |
| 236 | // Code |
| 237 | //------------------------------------------------------------------------ |
| 238 | return not comp(*(src1.back()), *(src2.front())); |
| 239 | }; |
| 240 | // |
| 241 | //----------------------------------------------------------------------------- |
| 242 | // function : merge |
| 243 | /// @brief Merge two contiguous ranges src1 and src2, and put the result in |
| 244 | /// the range dest, returning the range merged |
| 245 | /// |
| 246 | /// @param dest : range where locate the lements merged. the size of dest |
| 247 | /// must be greater or equal than the sum of the sizes of |
| 248 | /// src1 and src2 |
| 249 | /// @param src1 : first range to merge |
| 250 | /// @param src2 : second range to merge |
| 251 | /// @param comp : comparison object |
| 252 | /// @return range with the elements merged and the size adjusted |
| 253 | //----------------------------------------------------------------------------- |
| 254 | template<class Iter1_t, class Iter2_t, class Iter3_t, class Compare> |
| 255 | inline range<Iter3_t> merge(const range<Iter3_t> &dest, |
| 256 | const range<Iter1_t> &src1, |
| 257 | const range<Iter2_t> &src2, Compare comp) |
| 258 | { |
| 259 | Iter3_t it_aux = util::merge(src1.first, src1.last, src2.first, src2.last, |
| 260 | dest.first, comp); |
| 261 | return range<Iter3_t>(dest.first, it_aux); |
| 262 | }; |
| 263 | |
| 264 | //----------------------------------------------------------------------------- |
| 265 | // function : merge_construct |
| 266 | /// @brief Merge two contiguous uninitialized ranges src1 and src2, and create |
| 267 | /// and move the result in the uninitialized range dest, returning the |
| 268 | /// range merged |
| 269 | // |
| 270 | /// @param dest : range where locate the elements merged. the size of dest |
| 271 | /// must be greater or equal than the sum of the sizes of |
| 272 | /// src1 and src2. Initially is uninitialize memory |
| 273 | /// @param src1 : first range to merge |
| 274 | /// @param src2 : second range to merge |
| 275 | /// @param comp : comparison object |
| 276 | /// @return range with the elements merged and the size adjusted |
| 277 | //----------------------------------------------------------------------------- |
| 278 | template<class Iter1_t, class Iter2_t, class Value_t, class Compare> |
| 279 | inline range<Value_t *> merge_construct(const range<Value_t *> &dest, |
| 280 | const range<Iter1_t> &src1, |
| 281 | const range<Iter2_t> &src2, |
| 282 | Compare comp) |
| 283 | { |
| 284 | Value_t * ptr_aux = util::merge_construct(src1.first, src1.last, src2.first, |
| 285 | src2.last, dest.first, comp); |
| 286 | return range<Value_t*>(dest.first, ptr_aux); |
| 287 | }; |
| 288 | // |
| 289 | //--------------------------------------------------------------------------- |
| 290 | // function : half_merge |
| 291 | /// @brief : Merge two initialized buffers. The first buffer is in a separate |
| 292 | /// memory |
| 293 | // |
| 294 | /// @param dest : range where finish the two buffers merged |
| 295 | /// @param src1 : first range to merge in a separate memory |
| 296 | /// @param src2 : second range to merge, in the final part of the |
| 297 | /// range where deposit the final results |
| 298 | /// @param comp : object for compare two elements of the type pointed |
| 299 | /// by the Iter1_t and Iter2_t |
| 300 | /// @return : range with the two buffers merged |
| 301 | //--------------------------------------------------------------------------- |
| 302 | template<class Iter1_t, class Iter2_t, class Compare> |
| 303 | inline range<Iter2_t> merge_half(const range<Iter2_t> &dest, |
| 304 | const range<Iter1_t> &src1, |
| 305 | const range<Iter2_t> &src2, Compare comp) |
| 306 | { |
| 307 | Iter2_t it_aux = util::merge_half(src1.first, src1.last, src2.first, |
| 308 | src2.last, dest.first, comp); |
| 309 | return range<Iter2_t>(dest.first, it_aux); |
| 310 | }; |
| 311 | // |
| 312 | //----------------------------------------------------------------------------- |
| 313 | // function : merge_uncontiguous |
| 314 | /// @brief : merge two non contiguous ranges src1, src2, using the range |
| 315 | /// aux as auxiliary memory. The results are in the original ranges |
| 316 | // |
| 317 | /// @param src1 : first range to merge |
| 318 | /// @param src2 : second range to merge |
| 319 | /// @param aux : auxiliary range used in the merge |
| 320 | /// @param comp : object for to compare elements |
| 321 | /// @return true : not changes done, false : changes in the buffers |
| 322 | //----------------------------------------------------------------------------- |
| 323 | template<class Iter1_t, class Iter2_t, class Iter3_t, class Compare> |
| 324 | inline bool merge_uncontiguous(const range<Iter1_t> &src1, |
| 325 | const range<Iter2_t> &src2, |
| 326 | const range<Iter3_t> &aux, Compare comp) |
| 327 | { |
| 328 | return util::merge_uncontiguous(src1.first, src1.last, src2.first, |
| 329 | src2.last, aux.first, comp); |
| 330 | }; |
| 331 | // |
| 332 | //----------------------------------------------------------------------------- |
| 333 | // function : merge_contiguous |
| 334 | /// @brief : merge two contiguous ranges ( src1, src2) using buf as |
| 335 | /// auxiliary memory. The results are in the same ranges |
| 336 | /// @param src1 : first range to merge |
| 337 | /// @param src1 : second range to merge |
| 338 | /// @param buf : auxiliary memory used in the merge |
| 339 | /// @param comp : object for to compare elements |
| 340 | /// @return true : not changes done, false : changes in the buffers |
| 341 | //----------------------------------------------------------------------------- |
| 342 | template<class Iter1_t, class Iter2_t, class Compare> |
| 343 | inline range<Iter1_t> merge_contiguous(const range<Iter1_t> &src1, |
| 344 | const range<Iter1_t> &src2, |
| 345 | const range<Iter2_t> &buf, Compare comp) |
| 346 | { |
| 347 | util::merge_contiguous(src1.first, src1.last, src2.last, buf.first, comp); |
| 348 | return concat(src1, src2); |
| 349 | }; |
| 350 | // |
| 351 | //----------------------------------------------------------------------------- |
| 352 | // function : merge_flow |
| 353 | /// @brief : merge two ranges, as part of a merge the ranges in a list. This |
| 354 | /// function reduce the number of movements compared with inplace_merge |
| 355 | /// when you need to merge a sequence of ranges. |
| 356 | /// This function merge the ranges rbuf and rng2, and the results |
| 357 | /// are in rng1 and rbuf |
| 358 | // |
| 359 | /// @param rng1 : range where locate the first elements of the merge |
| 360 | /// @param rbuf : range which provide the first elements, and where store |
| 361 | /// the last results of the merge |
| 362 | /// @param rng2 : range which provide the last elements to merge |
| 363 | /// @param comp : object for to compare elements |
| 364 | /// @return true : not changes done, false : changes in the buffers |
| 365 | //----------------------------------------------------------------------------- |
| 366 | template<class Iter1_t, class Iter2_t, class Compare> |
| 367 | static void merge_flow(range<Iter1_t> rng1, range<Iter2_t> rbuf, |
| 368 | range<Iter1_t> rng2, Compare cmp) |
| 369 | { |
| 370 | //------------------------------------------------------------------------- |
| 371 | // Metaprogramming |
| 372 | //------------------------------------------------------------------------- |
| 373 | typedef util::value_iter<Iter1_t> type1; |
| 374 | typedef util::value_iter<Iter2_t> type2; |
| 375 | static_assert (std::is_same< type1, type2 >::value, |
| 376 | "Incompatible iterators\n" ); |
| 377 | |
| 378 | //------------------------------------------------------------------------- |
| 379 | // Code |
| 380 | //------------------------------------------------------------------------- |
| 381 | range<Iter2_t> rbx(rbuf); |
| 382 | range<Iter1_t> rx1(rng1), rx2(rng2); |
| 383 | assert(rbx.size() == rx1.size() and rx1.size() == rx2.size()); |
| 384 | while (rx1.first != rx1.last) |
| 385 | { |
| 386 | *(rx1.first++) = (cmp(*rbx.first, *rx2.first)) ? |
| 387 | std::move(*(rbx.first++)): |
| 388 | std::move(*(rx2.first++)); |
| 389 | }; |
| 390 | if (rx2.first == rx2.last) return; |
| 391 | if (rbx.first == rbx.last) move_forward(rbuf, rng2); |
| 392 | else merge_half(rbuf, rx2, rbx, cmp); |
| 393 | }; |
| 394 | |
| 395 | //**************************************************************************** |
| 396 | };// End namespace common |
| 397 | };// End namespace sort |
| 398 | };// End namespace boost |
| 399 | //**************************************************************************** |
| 400 | // |
| 401 | #endif |
| 402 | |