Jpp  15.0.0-rc.2
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 > 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 , template< class, class > class JContainer_t, class JAllocator_t >
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. More...
 
template<class JSuperContainer_t , template< class, class > class JContainer_t, class JAllocator_t , class JComparator_t >
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. More...
 
template<class T , template< class, class > class JContainer_t, class JAllocator_t >
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. More...
 
template<class T , template< class, class > class JContainer_t, class JAllocator_t , class JComparator_t >
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. More...
 

Private Types

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

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 > buffer
 
std::vector< JElement_t > mirror
 

Detailed Description

template<class JElement_t>
class JTOOLS::JMergeSort< JElement_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 51 of file JMergeSort.hh.

Member Typedef Documentation

template<class JElement_t >
typedef std::pair<std::vector<JElement_t>, std::vector<JElement_t> > JTOOLS::JMergeSort< JElement_t >::pair
private

Definition at line 294 of file JMergeSort.hh.

Constructor & Destructor Documentation

template<class JElement_t >
JTOOLS::JMergeSort< JElement_t >::JMergeSort ( )
inline

Default constructor.

Definition at line 57 of file JMergeSort.hh.

58  {}

Member Function Documentation

template<class JElement_t >
template<class JSuperContainer_t , template< class, class > class JContainer_t, class JAllocator_t >
void JTOOLS::JMergeSort< JElement_t >::operator() ( const JSuperContainer_t &  input,
JContainer_t< 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 68 of file JMergeSort.hh.

70  {
71  (*this)(input.begin(), input.end(), output, std::less<JElement_t>());
72  }
template<class JElement_t >
template<class JSuperContainer_t , template< class, class > class JContainer_t, class JAllocator_t , class JComparator_t >
void JTOOLS::JMergeSort< JElement_t >::operator() ( const JSuperContainer_t &  input,
JContainer_t< 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 83 of file JMergeSort.hh.

86  {
87  (*this)(input.begin(), input.end(), output, comparator);
88  }
template<class JElement_t >
template<class T , template< class, class > class JContainer_t, class JAllocator_t >
void JTOOLS::JMergeSort< JElement_t >::operator() ( T  __begin,
T  __end,
JContainer_t< 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 99 of file JMergeSort.hh.

102  {
103  (*this)(__begin, __end, output, std::less<JElement_t>());
104  }
template<class JElement_t >
template<class T , template< class, class > class JContainer_t, class JAllocator_t , class JComparator_t >
void JTOOLS::JMergeSort< JElement_t >::operator() ( T  __begin,
T  __end,
JContainer_t< 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 116 of file JMergeSort.hh.

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  }
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::buffer
std::vector< pair > buffer
Definition: JMergeSort.hh:296
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:184
JTOOLS::JMergeSort::mirror
std::vector< JElement_t > mirror
Definition: JMergeSort.hh:297
template<class JElement_t >
template<class JContainer_t >
static void JTOOLS::JMergeSort< JElement_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 152 of file JMergeSort.hh.

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  }
JTOOLS::n
const int n
Definition: JPolint.hh:660
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 source JAcoustics sh $DETECTOR_ID CHECK_EXIT_CODE typeset A TRIPODS get_tripods $WORKDIR tripod txt TRIPODS for EMITTER in
Definition: JCanberra.sh:41
template<class JElement_t >
template<class JContainer_t , class JComparator_t >
static void JTOOLS::JMergeSort< JElement_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 184 of file JMergeSort.hh.

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  }
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:660
JTOOLS::j
int j
Definition: JPolint.hh:666
template<class JElement_t >
std::vector<JElement_t>& JTOOLS::JMergeSort< JElement_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 220 of file JMergeSort.hh.

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  }
THROW
#define THROW(JException_t, A)
Marco for throwing exception with std::ostream compatible message.
Definition: JException.hh:670
JTOOLS::JMergeSort::buffer
std::vector< pair > buffer
Definition: JMergeSort.hh:296
JTOOLS::JMergeSort::mirror
std::vector< JElement_t > mirror
Definition: JMergeSort.hh:297
template<class JElement_t >
template<class _Iterator_t , class JComparator_t >
void JTOOLS::JMergeSort< JElement_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 253 of file JMergeSort.hh.

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  }
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
JTOOLS::JMergeSort::getBuffer
std::vector< JElement_t > & getBuffer(const size_t level, const JTwosome side) const
Get internal buffer.
Definition: JMergeSort.hh:220
N
then JShowerPostfit f $INPUT_FILE o $OUTPUT_FILE N
Definition: JShowerPostfit.sh:95
JTOOLS::JMergeSort::copy
static void copy(const JContainer_t &input, std::vector< JElement_t > &output)
Fast copy of data set.
Definition: JMergeSort.hh:152
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:184

Member Data Documentation

template<class JElement_t >
std::vector<pair> JTOOLS::JMergeSort< JElement_t >::buffer
mutableprivate

Definition at line 296 of file JMergeSort.hh.

template<class JElement_t >
std::vector<JElement_t> JTOOLS::JMergeSort< JElement_t >::mirror
mutableprivate

Definition at line 297 of file JMergeSort.hh.

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