Jpp
 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 unsigned int 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 unsigned int 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< pairbuffer
 
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. This class 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 output then consists of a single sorted data set which is also terminated by an end marker.

Definition at line 50 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 290 of file JMergeSort.hh.

Constructor & Destructor Documentation

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

Default constructor.

Definition at line 56 of file JMergeSort.hh.

57  {}

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 67 of file JMergeSort.hh.

69  {
70  (*this)(input.begin(), input.end(), output, std::less<JElement_t>());
71  }
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 82 of file JMergeSort.hh.

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

101  {
102  (*this)(__begin, __end, output, std::less<JElement_t>());
103  }
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() ( __begin,
__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 115 of file JMergeSort.hh.

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  }
std::vector< pair > buffer
Definition: JMergeSort.hh:292
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
std::vector< JElement_t > mirror
Definition: JMergeSort.hh:293
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 151 of file JMergeSort.hh.

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  }
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 180 of file JMergeSort.hh.

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  }
template<class JElement_t >
std::vector<JElement_t>& JTOOLS::JMergeSort< JElement_t >::getBuffer ( const unsigned int  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 216 of file JMergeSort.hh.

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  }
std::vector< pair > buffer
Definition: JMergeSort.hh:292
std::vector< JElement_t > mirror
Definition: JMergeSort.hh:293
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 unsigned int  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 249 of file JMergeSort.hh.

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  }
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
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

Member Data Documentation

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

Definition at line 292 of file JMergeSort.hh.

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

Definition at line 293 of file JMergeSort.hh.


The documentation for this class was generated from the following file: