Jpp  15.0.1-rc.1-highqe
the software that should make you happy
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
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 #include "JLang/JException.hh"
9 
10 
11 /**
12  * \author mdejong
13  */
14 
15 namespace JTOOLS {}
16 namespace JPP { using namespace JTOOLS; }
17 
18 namespace JTOOLS {
19 
20  using JLANG::JTwosome;
21  using JLANG::LEFT;
22  using JLANG::RIGHT;
24 
25 
26  /**
27  * This class implements a merge and sort algorithm based on the divide-and-conquer concept.
28  *
29  * Note that this class heavily uses internal buffers.
30  * It should therefore be used as an I/O operator, rather than a constructor.
31  *
32  * The template argument refers to the element of the input and output containers.
33  *
34  * The input data containers should be compatible with that of STL containers,
35  * i.e provide for the following member methods:
36  * <pre>
37  * typedef <constant iterator> const_iterator;
38 
39  * size_t size() const; // number of elements;
40 
41  * const_iterator begin() const; // begin of data
42  * const_iterator end() const; // end of data
43  * </pre>
44  *
45  * The input should consist of a set of sorted data sets, each terminated by an end marker.\n
46  * In this, an end marker corresponds to a value that is always larger than any physical value.\n
47  * The end marker is the first element beyond the size but within the capacity of the container.\n
48  * The output then consists of a single sorted data set which is also terminated by an end marker.
49  */
50  template<class JElement_t>
51  class JMergeSort
52  {
53  public:
54  /**
55  * Default constructor.
56  */
58  {}
59 
60 
61  /**
62  * Merge set of sorted data sets into single sorted data set.
63  *
64  * \param input input data sets
65  * \param output output data set
66  */
67  template<class JSuperContainer_t, template<class, class> class JContainer_t, class JAllocator_t>
68  inline void operator()(const JSuperContainer_t& input,
69  JContainer_t<JElement_t, JAllocator_t>& output) const
70  {
71  (*this)(input.begin(), input.end(), output, std::less<JElement_t>());
72  }
73 
74 
75  /**
76  * Merge set of sorted data sets into single sorted data set.
77  *
78  * \param input input data sets
79  * \param output output data set
80  * \param comparator element comparator
81  */
82  template<class JSuperContainer_t, template<class, class> class JContainer_t, class JAllocator_t, class JComparator_t>
83  inline void operator()(const JSuperContainer_t& input,
84  JContainer_t<JElement_t, JAllocator_t>& output,
85  const JComparator_t& comparator) const
86  {
87  (*this)(input.begin(), input.end(), output, comparator);
88  }
89 
90 
91  /**
92  * Merge set of sorted data sets into single sorted data set.
93  *
94  * \param __begin begin of input data sets
95  * \param __end end of input data sets
96  * \param output output data set
97  */
98  template<class T, template<class, class> class JContainer_t, class JAllocator_t>
99  inline void operator()(T __begin,
100  T __end,
101  JContainer_t<JElement_t, JAllocator_t>& output) const
102  {
103  (*this)(__begin, __end, output, std::less<JElement_t>());
104  }
105 
106 
107  /**
108  * Merge set of sorted data sets into single sorted data set.
109  *
110  * \param __begin begin of input data sets
111  * \param __end end of input data sets
112  * \param output output data set
113  * \param comparator element comparator
114  */
115  template<class T, template<class, class> class JContainer_t, class JAllocator_t, class JComparator_t>
116  inline void operator()(T __begin,
117  T __end,
118  JContainer_t<JElement_t, JAllocator_t>& output,
119  const JComparator_t& comparator) const
120  {
121  if (__begin != __end) {
122 
123  // configure depth of internal buffer
124 
125  size_t N = 0;
126 
127  for (size_t i = std::distance(__begin, __end); i != 0; i >>= 1) {
128  ++N;
129  }
130 
131  buffer.resize(N - 1);
132 
133  // merge data
134 
135  mirror.swap(output);
136 
137  this->merge(__begin, __end, comparator);
138 
139  mirror.swap(output);
140  }
141  }
142 
143 
144  private:
145  /**
146  * Fast copy of data set.
147  *
148  * \param input input data set
149  * \param output output data set
150  */
151  template<class JContainer_t>
152  static inline void copy(const JContainer_t& input,
153  std::vector<JElement_t>& output)
154  {
155  size_t n = input.size();
156 
157  output.reserve(n + 1); // reserve space for end marker
158  output.resize (n + 0); // reserve space for data
159 
160  typename JContainer_t::const_iterator in = input .begin();
161  typename std::vector<JElement_t>::iterator out = output.begin();
162 
163  for ( ; n != 0; --n, ++in, ++out) {
164  *out = *in;
165  }
166 
167  *out = *in; // copy end marker
168  }
169 
170 
171  /**
172  * Fast merge of two data sets into one data set.
173  *
174  * It is assumed that the input data sets are sorted and terminated by an end marker.
175  * In this, an end marker corresponds to a value that is larger than any physical value.
176  * The output data set will be terminated by the same end marker.
177  *
178  * \param first first data set
179  * \param second second data set
180  * \param output output data set
181  * \param comparator element comparator
182  */
183  template<class JContainer_t, class JComparator_t>
184  static inline void merge(const JContainer_t& first,
185  const JContainer_t& second,
186  std::vector<JElement_t>& output,
187  const JComparator_t& comparator)
188  {
189  size_t n = first.size() + second.size();
190 
191  output.reserve(n + 1); // reserve space for end marker
192  output.resize (n + 0); // reserve space for data
193 
194  typename JContainer_t::const_iterator i = first .begin();
195  typename JContainer_t::const_iterator j = second.begin();
196  typename std::vector<JElement_t>::iterator out = output.begin();
197 
198  for ( ; n != 0; --n, ++out) {
199 
200  if (comparator(*i,*j)) {
201  *out = *i;
202  ++i;
203  } else {
204  *out = *j;
205  ++j;
206  }
207  }
208 
209  *out = *i; // copy end marker
210  }
211 
212 
213  /**
214  * Get internal buffer.
215  *
216  * \param level depth in internal buffer
217  * \param side either of two of a kind (left/right)
218  * \return internal buffer
219  */
220  inline std::vector<JElement_t>& getBuffer(const size_t level,
221  const JTwosome side) const
222  {
223  if (level == 0) {
224 
225  return mirror;
226 
227  } else if (level - 1 < buffer.size()) {
228 
229  switch (side) {
230 
231  case LEFT:
232  return buffer[level - 1].first;
233 
234  case RIGHT:
235  return buffer[level - 1].second;
236  }
237  }
238 
239  THROW(JValueOutOfRange, "Invalid level " << level << " >= " << buffer.size());
240  }
241 
242 
243  /**
244  * Recursive merge.
245  *
246  * \param __begin begin of set of data sets
247  * \param __end end of set of data sets
248  * \param comparator element comparator
249  * \param level depth in internal buffer
250  * \param side either of two of a kind (left/right)
251  */
252  template<class _Iterator_t, class JComparator_t>
253  inline void merge(_Iterator_t __begin,
254  _Iterator_t __end,
255  const JComparator_t& comparator,
256  const size_t level = 0,
257  const JTwosome side = LEFT) const
258  {
259  const size_t N = std::distance(__begin, __end);
260 
261  switch (N) {
262 
263  case 0:
264  break;
265 
266  case 1:
267  copy(__begin[0], getBuffer(level,side));
268  break;
269 
270  case 2:
271  merge(__begin[0], __begin[1], getBuffer(level,side), comparator);
272  break;
273 
274  default:
275 
276  // recursion
277 
278  this->merge(__begin, __begin + N/2, comparator, level + 1, LEFT);
279  this->merge(__begin + N/2, __end, comparator, level + 1, RIGHT);
280 
281  // combination
282 
283  merge(getBuffer(level + 1, LEFT),
284  getBuffer(level + 1, RIGHT),
285  getBuffer(level,side),
286  comparator);
287 
288  break;
289  }
290  }
291 
292 
295 
298  };
299 }
300 
301 #endif
Exceptions.
std::vector< T >::difference_type distance(typename std::vector< T >::const_iterator first, typename PhysicsEvent::const_iterator< T > second)
Specialisation of STL distance.
void operator()(const JSuperContainer_t &input, JContainer_t< JElement_t, JAllocator_t > &output) const
Merge set of sorted data sets into single sorted data set.
Definition: JMergeSort.hh:68
std::vector< JElement_t > & getBuffer(const size_t level, const JTwosome side) const
Get internal buffer.
Definition: JMergeSort.hh:220
#define THROW(JException_t, A)
Marco for throwing exception with std::ostream compatible message.
Definition: JException.hh:670
then JShowerPostfit f $INPUT_FILE o $OUTPUT_FILE N
std::vector< pair > buffer
Definition: JMergeSort.hh:296
JTwosome
Enumeration for two of a kind.
Definition: JTwosome.hh:18
JMergeSort()
Default constructor.
Definition: JMergeSort.hh:57
void operator()(T __begin, T __end, JContainer_t< JElement_t, JAllocator_t > &output, const JComparator_t &comparator) const
Merge set of sorted data sets into single sorted data set.
Definition: JMergeSort.hh:116
void operator()(T __begin, T __end, JContainer_t< JElement_t, JAllocator_t > &output) const
Merge set of sorted data sets into single sorted data set.
Definition: JMergeSort.hh:99
This class implements a merge and sort algorithm based on the divide-and-conquer concept.
Definition: JMergeSort.hh:51
std::pair< std::vector< JElement_t >, std::vector< JElement_t > > pair
Definition: JMergeSort.hh:294
then echo The file $DIR KM3NeT_00000001_00000000 root already please rename or remove it first
const int n
Definition: JPolint.hh:660
void merge(_Iterator_t __begin, _Iterator_t __end, const JComparator_t &comparator, const size_t level=0, const JTwosome side=LEFT) const
Recursive merge.
Definition: JMergeSort.hh:253
do set_variable OUTPUT_DIRECTORY $WORKDIR T
static void copy(const JContainer_t &input, std::vector< JElement_t > &output)
Fast copy of data set.
Definition: JMergeSort.hh:152
void operator()(const JSuperContainer_t &input, JContainer_t< JElement_t, JAllocator_t > &output, const JComparator_t &comparator) const
Merge set of sorted data sets into single sorted data set.
Definition: JMergeSort.hh:83
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.
Definition: JMergeSort.hh:184
int j
Definition: JPolint.hh:666
Exception for accessing a value in a collection that is outside of its range.
Definition: JException.hh:162
then fatal Wrong number of arguments fi set_variable DETECTOR $argv[1] set_variable INPUT_FILE $argv[2] eval JPrintDetector a $DETECTOR O IDENTIFIER eval JPrintDetector a $DETECTOR O SUMMARY source JAcoustics sh $DETECTOR_ID CHECK_EXIT_CODE typeset A TRIPODS get_tripods $WORKDIR tripod txt TRIPODS for EMITTER in
Definition: JCanberra.sh:41
std::vector< JElement_t > mirror
Definition: JMergeSort.hh:297