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
26namespace boost
27{
28namespace sort
29{
30namespace common
31{
32
33///---------------------------------------------------------------------------
34/// @struct range
35/// @brief this represent a range between two iterators
36/// @remarks
37//----------------------------------------------------------------------------
38template <class Iter_t>
39struct 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//-----------------------------------------------------------------------------
108template<class Iter_t>
109inline 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//-----------------------------------------------------------------------------
122template <class Iter1_t, class Iter2_t>
123inline 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//-----------------------------------------------------------------------------
138template <class Iter1_t, class Iter2_t>
139inline 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//-----------------------------------------------------------------------------
156template<class Iter_t, class Value_t = util::value_iter<Iter_t> >
157inline 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//-----------------------------------------------------------------------------
169template<class Iter_t>
170inline 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//-----------------------------------------------------------------------------
182template<class Iter_t, class Value_t = util::value_iter<Iter_t> >
183inline 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//-----------------------------------------------------------------------------
198template<class Iter1_t, class Iter2_t, class Compare>
199inline 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//-----------------------------------------------------------------------------
224template<class Iter1_t, class Iter2_t, class Compare>
225inline 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//-----------------------------------------------------------------------------
254template<class Iter1_t, class Iter2_t, class Iter3_t, class Compare>
255inline 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//-----------------------------------------------------------------------------
278template<class Iter1_t, class Iter2_t, class Value_t, class Compare>
279inline 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//---------------------------------------------------------------------------
302template<class Iter1_t, class Iter2_t, class Compare>
303inline 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//-----------------------------------------------------------------------------
323template<class Iter1_t, class Iter2_t, class Iter3_t, class Compare>
324inline 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//-----------------------------------------------------------------------------
342template<class Iter1_t, class Iter2_t, class Compare>
343inline 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//-----------------------------------------------------------------------------
366template<class Iter1_t, class Iter2_t, class Compare>
367static 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

source code of boost/libs/sort/include/boost/sort/common/range.hpp