Jpp  17.3.0
the software that should make you happy
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
Public Member Functions | Private Types | Private Member Functions | Static Private Member Functions | Private Attributes | List of all members
JTOOLS::JMergeSort< JElement_t, JAllocator_t > Class Template Reference

This class implements a merge and sort algorithm based on the divide-and-conquer concept. More...

#include <JMergeSort.hh>

Public Member Functions

 JMergeSort ()
 Default constructor. More...
 
template<class JSuperContainer_t >
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. More...
 
template<class JSuperContainer_t , class JComparator_t >
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. More...
 
template<class T >
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. More...
 
template<class T , class JComparator_t >
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. More...
 

Private Types

typedef std::pair< std::vector
< JElement_t, JAllocator_t >
, std::vector< JElement_t,
JAllocator_t > > 		pair_type
 

Private Member Functions

std::vector< JElement_t > & getBuffer (const size_t level, const JTwosome side) const
 Get internal buffer. More...
 
template<class _Iterator_t , class JComparator_t >
void merge (_Iterator_t __begin, _Iterator_t __end, const JComparator_t &comparator, const size_t level=0, const JTwosome side=LEFT) const
 Recursive merge. More...
 

Static Private Member Functions

template<class JContainer_t >
static void copy (const JContainer_t &input, std::vector< JElement_t > &output)
 Fast copy of data set. More...
 
template<class JContainer_t , class JComparator_t >
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. More...
 

Private Attributes

std::vector< pair_type > buffer
 
std::vector< JElement_t,
JAllocator_t > 		mirror
 

Detailed Description

template<class JElement_t, class JAllocator_t = std::allocator<JElement_t>>
class JTOOLS::JMergeSort< JElement_t, JAllocator_t >

This class implements a merge and sort algorithm based on the divide-and-conquer concept.

Note that this class heavily uses internal buffers. It should therefore be used as an I/O operator, rather than a constructor.

The template argument refers to the element of the input and output containers.

The input data containers should be compatible with that of STL containers, i.e provide for the following member methods: 

     typedef <constant iterator>    const_iterator;
     size_t size() const;             // number of elements;
     const_iterator begin() const;    // begin of data
     const_iterator end()   const;    // end   of data

The input should consist of a set of sorted data sets, each terminated by an end marker.
In this, an end marker corresponds to a value that is always larger than any physical value.
The end marker is the first element beyond the size but within the capacity of the container.
The output then consists of a single sorted data set which is also terminated by an end marker.

Definition at line 49 of file JMergeSort.hh.

Member Typedef Documentation

template<class JElement_t, class JAllocator_t = std::allocator<JElement_t>>
typedef std::pair<std::vector<JElement_t, JAllocator_t>, std::vector<JElement_t, JAllocator_t> > JTOOLS::JMergeSort< JElement_t, JAllocator_t >::pair_type
private

Definition at line 308 of file JMergeSort.hh.

Constructor & Destructor Documentation

template<class JElement_t, class JAllocator_t = std::allocator<JElement_t>>
JTOOLS::JMergeSort< JElement_t, JAllocator_t >::JMergeSort ( )
inline

Default constructor.

Definition at line 55 of file JMergeSort.hh.

56  {}

Member Function Documentation

template<class JElement_t, class JAllocator_t = std::allocator<JElement_t>>
template<class JSuperContainer_t >
void JTOOLS::JMergeSort< JElement_t, JAllocator_t >::operator() ( const JSuperContainer_t &  input,
std::vector< JElement_t, JAllocator_t > &  output 
) const
inline

Merge set of sorted data sets into single sorted data set.

Parameters
inputinput data sets
outputoutput data set

Definition at line 66 of file JMergeSort.hh.

68  {
69  (*this)(input.begin(), input.end(), output, std::less<JElement_t>());
70  }
template<class JElement_t, class JAllocator_t = std::allocator<JElement_t>>
template<class JSuperContainer_t , class JComparator_t >
void JTOOLS::JMergeSort< JElement_t, JAllocator_t >::operator() ( const JSuperContainer_t &  input,
std::vector< JElement_t, JAllocator_t > &  output,
const JComparator_t &  comparator 
) const
inline

Merge set of sorted data sets into single sorted data set.

Parameters
inputinput data sets
outputoutput data set
comparatorelement comparator

Definition at line 81 of file JMergeSort.hh.

84  {
85  (*this)(input.begin(), input.end(), output, comparator);
86  }
template<class JElement_t, class JAllocator_t = std::allocator<JElement_t>>
template<class T >
void JTOOLS::JMergeSort< JElement_t, JAllocator_t >::operator() ( T  __begin,
T  __end,
std::vector< JElement_t, JAllocator_t > &  output 
) const
inline

Merge set of sorted data sets into single sorted data set.

Parameters
__beginbegin of input data sets
__endend of input data sets
outputoutput data set

Definition at line 97 of file JMergeSort.hh.

100  {
101  (*this)(__begin, __end, output, std::less<JElement_t>());
102  }
template<class JElement_t, class JAllocator_t = std::allocator<JElement_t>>
template<class T , class JComparator_t >
void JTOOLS::JMergeSort< JElement_t, JAllocator_t >::operator() ( T  __begin,
T  __end,
std::vector< JElement_t, JAllocator_t > &  output,
const JComparator_t &  comparator 
) const
inline

Merge set of sorted data sets into single sorted data set.

Parameters
__beginbegin of input data sets
__endend of input data sets
outputoutput data set
comparatorelement comparator

Definition at line 114 of file JMergeSort.hh.

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  }
JTOOLS::JMergeSort::buffer
std::vector< pair_type > buffer
Definition: JMergeSort.hh:310
JTOOLS::JMergeSort::merge
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:182
distance
std::vector< T >::difference_type distance(typename std::vector< T >::const_iterator first, typename PhysicsEvent::const_iterator< T > second)
Specialisation of STL distance.
Definition: PhysicsEvent.hh:434
N
then JShowerPostfit f $INPUT_FILE o $OUTPUT_FILE N
Definition: JShowerPostfit.sh:95
JTOOLS::JMergeSort::mirror
std::vector< JElement_t, JAllocator_t > mirror
Definition: JMergeSort.hh:311
template<class JElement_t, class JAllocator_t = std::allocator<JElement_t>>
template<class JContainer_t >
static void JTOOLS::JMergeSort< JElement_t, JAllocator_t >::copy ( const JContainer_t &  input,
std::vector< JElement_t > &  output 
)
inlinestaticprivate

Fast copy of data set.

Parameters
inputinput data set
outputoutput data set

Definition at line 150 of file JMergeSort.hh.

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  }
JTOOLS::n
const int n
Definition: JPolint.hh:697
in
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 JAcoustics sh $DETECTOR_ID source JAcousticsToolkit sh CHECK_EXIT_CODE typeset A EMITTERS get_tripods $WORKDIR tripod txt EMITTERS get_transmitters $WORKDIR transmitter txt EMITTERS for EMITTER in
Definition: JCanberra.sh:46
template<class JElement_t, class JAllocator_t = std::allocator<JElement_t>>
template<class JContainer_t , class JComparator_t >
static void JTOOLS::JMergeSort< JElement_t, JAllocator_t >::merge ( const JContainer_t &  first,
const JContainer_t &  second,
std::vector< JElement_t > &  output,
const JComparator_t &  comparator 
)
inlinestaticprivate

Fast merge of two data sets into one data set.

It is assumed that the input data sets are sorted and terminated by an end marker. In this, an end marker corresponds to a value that is larger than any physical value. The output data set will be terminated by the same end marker.

Parameters
firstfirst data set
secondsecond data set
outputoutput data set
comparatorelement comparator

Definition at line 182 of file JMergeSort.hh.

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  }
first
then echo The file $DIR KM3NeT_00000001_00000000 root already please rename or remove it first
Definition: JDOMDAQDriver.sh:57
JTOOLS::n
const int n
Definition: JPolint.hh:697
JTOOLS::j
int j
Definition: JPolint.hh:703
template<class JElement_t, class JAllocator_t = std::allocator<JElement_t>>
std::vector<JElement_t>& JTOOLS::JMergeSort< JElement_t, JAllocator_t >::getBuffer ( const size_t  level,
const JTwosome  side 
) const
inlineprivate

Get internal buffer.

Parameters
leveldepth in internal buffer
sideeither of two of a kind (left/right)
Returns
internal buffer

Definition at line 238 of file JMergeSort.hh.

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  }
JTOOLS::JMergeSort::buffer
std::vector< pair_type > buffer
Definition: JMergeSort.hh:310
JTOOLS::JMergeSort::mirror
std::vector< JElement_t, JAllocator_t > mirror
Definition: JMergeSort.hh:311
template<class JElement_t, class JAllocator_t = std::allocator<JElement_t>>
template<class _Iterator_t , class JComparator_t >
void JTOOLS::JMergeSort< JElement_t, JAllocator_t >::merge ( _Iterator_t  __begin,
_Iterator_t  __end,
const JComparator_t &  comparator,
const size_t  level = 0,
const JTwosome  side = LEFT 
) const
inlineprivate

Recursive merge.

Parameters
__beginbegin of set of data sets
__endend of set of data sets
comparatorelement comparator
leveldepth in internal buffer
sideeither of two of a kind (left/right)

Definition at line 267 of file JMergeSort.hh.

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  }
JTOOLS::JMergeSort::copy
static void copy(const JContainer_t &input, std::vector< JElement_t > &output)
Fast copy of data set.
Definition: JMergeSort.hh:150
JTOOLS::JMergeSort::merge
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:182
distance
std::vector< T >::difference_type distance(typename std::vector< T >::const_iterator first, typename PhysicsEvent::const_iterator< T > second)
Specialisation of STL distance.
Definition: PhysicsEvent.hh:434
N
then JShowerPostfit f $INPUT_FILE o $OUTPUT_FILE N
Definition: JShowerPostfit.sh:95
JTOOLS::JMergeSort::getBuffer
std::vector< JElement_t > & getBuffer(const size_t level, const JTwosome side) const
Get internal buffer.
Definition: JMergeSort.hh:238

Member Data Documentation

template<class JElement_t, class JAllocator_t = std::allocator<JElement_t>>
std::vector<pair_type> JTOOLS::JMergeSort< JElement_t, JAllocator_t >::buffer
mutableprivate

Definition at line 310 of file JMergeSort.hh.

template<class JElement_t, class JAllocator_t = std::allocator<JElement_t>>
std::vector<JElement_t, JAllocator_t> JTOOLS::JMergeSort< JElement_t, JAllocator_t >::mirror
mutableprivate

Definition at line 311 of file JMergeSort.hh.

The documentation for this class was generated from the following file:
Generated by   doxygen 1.8.5