Jpp test-rotations-old
the software that should make you happy
Loading...
Searching...
No Matches
JMergeSort.hh
Go to the documentation of this file.
1#ifndef __JTOOLS__JMERGESORT__
2#define __JTOOLS__JMERGESORT__
3
4#include <vector>
5#include <functional>
6
7#include "JLang/JTwosome.hh"
8
9
10/**
11 * \author mdejong
12 */
13
14namespace JTOOLS {}
15namespace JPP { using namespace JTOOLS; }
16
17namespace JTOOLS {
18
19 using JLANG::JTwosome;
20 using JLANG::LEFT;
21 using JLANG::RIGHT;
22
23
24 /**
25 * This class implements a merge and sort algorithm based on the divide-and-conquer concept.
26 *
27 * Note that this class heavily uses internal buffers.
28 * It should therefore be used as an I/O operator, rather than a constructor.
29 *
30 * The template argument refers to the element of the input and output containers.
31 *
32 * The input data containers should be compatible with that of STL containers,
33 * i.e provide for the following member methods:
34 * <pre>
35 * typedef <constant iterator> const_iterator;
36 *
37 * size_t size() const; // number of elements;
38 *
39 * const_iterator begin() const; // begin of data
40 * const_iterator end() const; // end of data
41 * </pre>
42 *
43 * The input should consist of a set of sorted data sets, each terminated by an end marker.\n
44 * In this, an end marker corresponds to a value that is always larger than any physical value.\n
45 * The end marker is the first element beyond the size but within the capacity of the container.\n
46 * The output then consists of a single sorted data set which is also terminated by an end marker.
47 */
48 template<class JElement_t, class JAllocator_t = std::allocator<JElement_t> >
50 {
51 public:
52 /**
53 * Default constructor.
54 */
56 {}
57
58
59 /**
60 * Merge set of sorted data sets into single sorted data set.
61 *
62 * \param input input data sets
63 * \param output output data set
64 */
65 template<class JSuperContainer_t>
66 inline void operator()(const JSuperContainer_t& input,
68 {
69 (*this)(input.begin(), input.end(), output, std::less<JElement_t>());
70 }
71
72
73 /**
74 * Merge set of sorted data sets into single sorted data set.
75 *
76 * \param input input data sets
77 * \param output output data set
78 * \param comparator element comparator
79 */
80 template<class JSuperContainer_t, class JComparator_t>
81 inline void operator()(const JSuperContainer_t& input,
83 const JComparator_t& comparator) const
84 {
85 (*this)(input.begin(), input.end(), output, comparator);
86 }
87
88
89 /**
90 * Merge set of sorted data sets into single sorted data set.
91 *
92 * \param __begin begin of input data sets
93 * \param __end end of input data sets
94 * \param output output data set
95 */
96 template<class T>
97 inline void operator()(T __begin,
98 T __end,
100 {
101 (*this)(__begin, __end, output, std::less<JElement_t>());
102 }
103
104
105 /**
106 * Merge set of sorted data sets into single sorted data set.
107 *
108 * \param __begin begin of input data sets
109 * \param __end end of input data sets
110 * \param output output data set
111 * \param comparator element comparator
112 */
113 template<class T, class JComparator_t>
114 inline void operator()(T __begin,
115 T __end,
117 const JComparator_t& comparator) const
118 {
119 if (__begin != __end) {
120
121 // configure depth of internal buffer
122
123 size_t N = 0;
124
125 for (size_t i = std::distance(__begin, __end); i != 0; i >>= 1) {
126 ++N;
127 }
128
129 buffer.resize(N - 1);
130
131 // merge data
132
133 mirror.swap(output);
134
135 this->merge(__begin, __end, comparator);
136
137 mirror.swap(output);
138 }
139 }
140
141
142 private:
143 /**
144 * Fast copy of data set.
145 *
146 * \param input input data set
147 * \param output output data set
148 */
149 template<class JContainer_t>
150 static inline void copy(const JContainer_t& input,
152 {
153 size_t n = input.size();
154
155 output.reserve(n + 1); // reserve space for end marker
156 output.resize (n + 0); // reserve space for data
157
158 typename JContainer_t::const_iterator in = input .begin();
159 typename std::vector<JElement_t>::iterator out = output.begin();
160
161 for ( ; n != 0; --n) {
162 *out++ = *in++;
163 }
164
165 *out = *in; // copy end marker
166 }
167
168
169 /**
170 * Fast merge of two data sets into one data set.
171 *
172 * It is assumed that the input data sets are sorted and terminated by an end marker.
173 * In this, an end marker corresponds to a value that is larger than any physical value.
174 * The output data set will be terminated by the same end marker.
175 *
176 * \param first first data set
177 * \param second second data set
178 * \param output output data set
179 * \param comparator element comparator
180 */
181 template<class JContainer_t, class JComparator_t>
182 static inline void merge(const JContainer_t& first,
183 const JContainer_t& second,
185 const JComparator_t& comparator)
186 {
187 size_t n = first.size() + second.size();
188
189 output.reserve(n + 1); // reserve space for end marker
190 output.resize (n + 0); // reserve space for data
191
192 typename JContainer_t::const_iterator i = first .begin();
193 typename JContainer_t::const_iterator j = second.begin();
194 typename std::vector<JElement_t>::iterator out = output.begin();
195
196 for ( ; n >= 4; n -= 4) {
197
198 if (comparator(*i,*j))
199 *out++ = *i++;
200 else
201 *out++ = *j++;
202
203 if (comparator(*i,*j))
204 *out++ = *i++;
205 else
206 *out++ = *j++;
207
208 if (comparator(*i,*j))
209 *out++ = *i++;
210 else
211 *out++ = *j++;
212
213 if (comparator(*i,*j))
214 *out++ = *i++;
215 else
216 *out++ = *j++;
217 }
218
219 for ( ; n != 0; --n) {
220
221 if (comparator(*i,*j))
222 *out++ = *i++;
223 else
224 *out++ = *j++;
225 }
226
227 *out = *i; // copy end marker
228 }
229
230
231 /**
232 * Get internal buffer.
233 *
234 * \param level depth in internal buffer
235 * \param side either of two of a kind (left/right)
236 * \return internal buffer
237 */
238 inline std::vector<JElement_t>& getBuffer(const size_t level,
239 const JTwosome side) const
240 {
241 if (level != 0) {
242
243 switch (side) {
244
245 case LEFT:
246 return buffer[level - 1].first;
247
248 case RIGHT:
249 return buffer[level - 1].second;
250 }
251 }
252
253 return mirror;
254 }
255
256
257 /**
258 * Recursive merge.
259 *
260 * \param __begin begin of set of data sets
261 * \param __end end of set of data sets
262 * \param comparator element comparator
263 * \param level depth in internal buffer
264 * \param side either of two of a kind (left/right)
265 */
266 template<class _Iterator_t, class JComparator_t>
267 inline void merge(_Iterator_t __begin,
268 _Iterator_t __end,
269 const JComparator_t& comparator,
270 const size_t level = 0,
271 const JTwosome side = LEFT) const
272 {
273 const size_t N = std::distance(__begin, __end);
274
275 switch (N) {
276
277 case 0:
278 break;
279
280 case 1:
281 copy(__begin[0], getBuffer(level,side));
282 break;
283
284 case 2:
285 merge(__begin[0], __begin[1], getBuffer(level,side), comparator);
286 break;
287
288 default:
289
290 // recursion
291
292 this->merge(__begin, __begin + N/2, comparator, level + 1, LEFT);
293 this->merge(__begin + N/2, __end, comparator, level + 1, RIGHT);
294
295 // combination
296
297 merge(getBuffer(level + 1, LEFT),
298 getBuffer(level + 1, RIGHT),
299 getBuffer(level,side),
300 comparator);
301
302 break;
303 }
304 }
305
306
309
312 };
313}
314
315#endif
This class implements a merge and sort algorithm based on the divide-and-conquer concept.
Definition JMergeSort.hh:50
static void copy(const JContainer_t &input, std::vector< JElement_t > &output)
Fast copy of data set.
std::vector< pair_type > buffer
std::pair< std::vector< JElement_t, JAllocator_t >, std::vector< JElement_t, JAllocator_t > > pair_type
static void merge(const JContainer_t &first, const JContainer_t &second, std::vector< JElement_t > &output, const JComparator_t &comparator)
Fast merge of two data sets into one data set.
void operator()(T __begin, T __end, std::vector< JElement_t, JAllocator_t > &output, const JComparator_t &comparator) const
Merge set of sorted data sets into single sorted data set.
std::vector< JElement_t > & getBuffer(const size_t level, const JTwosome side) const
Get internal buffer.
void merge(_Iterator_t __begin, _Iterator_t __end, const JComparator_t &comparator, const size_t level=0, const JTwosome side=LEFT) const
Recursive merge.
void operator()(const JSuperContainer_t &input, std::vector< JElement_t, JAllocator_t > &output) const
Merge set of sorted data sets into single sorted data set.
Definition JMergeSort.hh:66
void operator()(const JSuperContainer_t &input, std::vector< JElement_t, JAllocator_t > &output, const JComparator_t &comparator) const
Merge set of sorted data sets into single sorted data set.
Definition JMergeSort.hh:81
void operator()(T __begin, T __end, std::vector< JElement_t, JAllocator_t > &output) const
Merge set of sorted data sets into single sorted data set.
Definition JMergeSort.hh:97
JMergeSort()
Default constructor.
Definition JMergeSort.hh:55
std::vector< JElement_t, JAllocator_t > mirror
JTwosome
Enumeration for two of a kind.
Definition JTwosome.hh:18
@ LEFT
Definition JTwosome.hh:18
@ RIGHT
Definition JTwosome.hh:18
This name space includes all other name spaces (except KM3NETDAQ, KM3NET and ANTARES).
Auxiliary classes and methods for multi-dimensional interpolations and histograms.
const int n
Definition JPolint.hh:791
int j
Definition JPolint.hh:801