Jpp - 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  * This class 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.
46  * In this, an end marker corresponds to a value that is always larger than any physical value.
47  * The output then consists of a single sorted data set which is also terminated by an end marker.
48  */
49  template<class JElement_t>
50  class JMergeSort
51  {
52  public:
53  /**
54  * Default constructor.
55  */
57  {}
58 
59 
60  /**
61  * Merge set of sorted data sets into single sorted data set.
62  *
63  * \param input input data sets
64  * \param output output data set
65  */
66  template<class JSuperContainer_t, template<class, class> class JContainer_t, class JAllocator_t>
67  inline void operator()(const JSuperContainer_t& input,
68  JContainer_t<JElement_t, JAllocator_t>& output) const
69  {
70  (*this)(input.begin(), input.end(), output, std::less<JElement_t>());
71  }
72 
73 
74  /**
75  * Merge set of sorted data sets into single sorted data set.
76  *
77  * \param input input data sets
78  * \param output output data set
79  * \param comparator element comparator
80  */
81  template<class JSuperContainer_t, template<class, class> class JContainer_t, class JAllocator_t, class JComparator_t>
82  inline void operator()(const JSuperContainer_t& input,
83  JContainer_t<JElement_t, JAllocator_t>& output,
84  const JComparator_t& comparator) const
85  {
86  (*this)(input.begin(), input.end(), output, comparator);
87  }
88 
89 
90  /**
91  * Merge set of sorted data sets into single sorted data set.
92  *
93  * \param __begin begin of input data sets
94  * \param __end end of input data sets
95  * \param output output data set
96  */
97  template<class T, template<class, class> class JContainer_t, class JAllocator_t>
98  inline void operator()(T __begin,
99  T __end,
100  JContainer_t<JElement_t, JAllocator_t>& output) const
101  {
102  (*this)(__begin, __end, output, std::less<JElement_t>());
103  }
104 
105 
106  /**
107  * Merge set of sorted data sets into single sorted data set.
108  *
109  * \param __begin begin of input data sets
110  * \param __end end of input data sets
111  * \param output output data set
112  * \param comparator element comparator
113  */
114  template<class T, template<class, class> class JContainer_t, class JAllocator_t, class JComparator_t>
115  inline void operator()(T __begin,
116  T __end,
117  JContainer_t<JElement_t, JAllocator_t>& output,
118  const JComparator_t& comparator) const
119  {
120  // configure depth of internal buffer
121 
122  unsigned int N = 0;
123 
124  for (unsigned int i = std::distance(__begin, __end); i != 0; i >>= 1) {
125  ++N;
126  }
127 
128  if (N != 0) {
129 
130  buffer.resize(N - 1);
131 
132  // merge data
133 
134  mirror.swap(output);
135 
136  this->merge(__begin, __end, comparator);
137 
138  mirror.swap(output);
139  }
140  }
141 
142 
143  private:
144  /**
145  * Fast copy of data set.
146  *
147  * \param input input data set
148  * \param output output data set
149  */
150  template<class JContainer_t>
151  static inline void copy(const JContainer_t& input,
152  std::vector<JElement_t>& output)
153  {
154  int n = input.size();
155 
156  output.resize(n); // allocate memory
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, ++in, ++out) {
162  *out = *in; // copy including end marker
163  }
164  }
165 
166 
167  /**
168  * Fast merge of two data sets into one data set.
169  *
170  * It is assumed that the input data sets are sorted and terminated by an end marker.
171  * In this, an end marker corresponds to a value that is larger than any physical value.
172  * The output data set will be terminated by the same end marker.
173  *
174  * \param first first data set
175  * \param second second data set
176  * \param output output data set
177  * \param comparator element comparator
178  */
179  template<class JContainer_t, class JComparator_t>
180  static inline void merge(const JContainer_t& first,
181  const JContainer_t& second,
182  std::vector<JElement_t>& output,
183  const JComparator_t& comparator)
184  {
185  int n = (first .size() - 1 + // correct for end markers
186  second.size() - 1);
187 
188  output.resize(n + 1); // allocate memory
189 
190  typename JContainer_t::const_iterator i = first .begin();
191  typename JContainer_t::const_iterator j = second.begin();
192  typename std::vector <JElement_t>::iterator out = output.begin();
193 
194  for ( ; n != 0; --n, ++out) {
195 
196  if (comparator(*i,*j)) {
197  *out = *i;
198  ++i;
199  } else {
200  *out = *j;
201  ++j;
202  }
203  }
204 
205  *out = *i; // copy end marker
206  }
207 
208 
209  /**
210  * Get internal buffer.
211  *
212  * \param level depth in internal buffer
213  * \param side either of two of a kind (left/right)
214  * \return internal buffer
215  */
216  inline std::vector<JElement_t>& getBuffer(const unsigned int level,
217  const JTwosome side) const
218  {
219  if (level == 0) {
220 
221  return mirror;
222 
223  } else if (level - 1 < buffer.size()) {
224 
225  switch (side) {
226 
227  case LEFT:
228  return buffer[level - 1].first;
229 
230  case RIGHT:
231  return buffer[level - 1].second;
232  }
233  }
234 
235  throw JValueOutOfRange("JMergeSort::getBuffer() illegal argument value.");
236  }
237 
238 
239  /**
240  * Recursive merge.
241  *
242  * \param __begin begin of set of data sets
243  * \param __end end of set of data sets
244  * \param comparator element comparator
245  * \param level depth in internal buffer
246  * \param side either of two of a kind (left/right)
247  */
248  template<class _Iterator_t, class JComparator_t>
249  inline void merge(_Iterator_t __begin,
250  _Iterator_t __end,
251  const JComparator_t& comparator,
252  const unsigned int level = 0,
253  const JTwosome side = LEFT) const
254  {
255  const int N = std::distance(__begin, __end);
256 
257  switch (N) {
258 
259  case 0:
260  break;
261 
262  case 1:
263  copy(__begin[0], getBuffer(level,side));
264  break;
265 
266  case 2:
267  merge(__begin[0], __begin[1], getBuffer(level,side), comparator);
268  break;
269 
270  default:
271 
272  // recursion
273 
274  this->merge(__begin, __begin + N/2, comparator, level + 1, LEFT);
275  this->merge(__begin + N/2, __end, comparator, level + 1, RIGHT);
276 
277  // combination
278 
279  merge(getBuffer(level + 1, LEFT),
280  getBuffer(level + 1, RIGHT),
281  getBuffer(level,side),
282  comparator);
283 
284  break;
285  }
286  }
287 
288 
291 
294  };
295 }
296 
297 #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:67
void merge(_Iterator_t __begin, _Iterator_t __end, const JComparator_t &comparator, const unsigned int level=0, const JTwosome side=LEFT) const
Recursive merge.
Definition: JMergeSort.hh:249
std::vector< pair > buffer
Definition: JMergeSort.hh:292
JTwosome
Enumeration for two of a kind.
Definition: JTwosome.hh:18
JMergeSort()
Default constructor.
Definition: JMergeSort.hh:56
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:115
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:98
This class implements a merge and sort algorithm based on the divide-and-conquer concept.
Definition: JMergeSort.hh:50
std::pair< std::vector< JElement_t >, std::vector< JElement_t > > pair
Definition: JMergeSort.hh:290
then echo The file $DIR KM3NeT_00000001_00000000 root already please rename or remove it first
do set_variable OUTPUT_DIRECTORY $WORKDIR T
std::vector< JElement_t > & getBuffer(const unsigned int level, const JTwosome side) const
Get internal buffer.
Definition: JMergeSort.hh:216
static void copy(const JContainer_t &input, std::vector< JElement_t > &output)
Fast copy of data set.
Definition: JMergeSort.hh:151
alias put_queue eval echo n
Definition: qlib.csh:19
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:82
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:180
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:38
then usage $script[input file[working directory[option]]] nWhere option can be N
Definition: JMuonPostfit.sh:37
std::vector< JElement_t > mirror
Definition: JMergeSort.hh:293