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

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

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

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

pair_type

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

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

JMergeSort()

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.

    {}

Member Function Documentation

operator()() [1/4]

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

input	input data sets
output	output data set

Definition at line 66 of file JMergeSort.hh.

    {
      (*this)(input.begin(), input.end(), output, std::less<JElement_t>());
    }

operator()() [2/4]

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

input	input data sets
output	output data set
comparator	element comparator

Definition at line 81 of file JMergeSort.hh.

    {
      (*this)(input.begin(), input.end(), output, comparator);
    }

operator()() [3/4]

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

__begin	begin of input data sets
__end	end of input data sets
output	output data set

Definition at line 97 of file JMergeSort.hh.

    {
      (*this)(__begin, __end, output, std::less<JElement_t>());
    }

operator()() [4/4]

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

__begin	begin of input data sets
__end	end of input data sets
output	output data set
comparator	element comparator

Definition at line 114 of file JMergeSort.hh.

    {
      if (__begin != __end) {
 
        // configure depth of internal buffer
 
        size_t N = 0;
 
        for (size_t i = std::distance(__begin, __end); i != 0; i >>= 1) {
          ++N;
        }
      
        buffer.resize(N - 1);
 
        // merge data
      
        mirror.swap(output);
 
        this->merge(__begin, __end, comparator);
 
        mirror.swap(output);
      }
    }

copy()

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

input	input data set
output	output data set

Definition at line 150 of file JMergeSort.hh.

    {
      size_t n = input.size();
    
      output.reserve(n + 1);         // reserve space for end marker
      output.resize (n + 0);         // reserve space for data
      
      typename JContainer_t::const_iterator      in  = input .begin();
      typename std::vector<JElement_t>::iterator out = output.begin();
 
      for ( ; n != 0; --n) {
        *out++ = *in++;
      }
 
      *out = *in;                    // copy end marker
    }

merge() [1/2]

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

first	first data set
second	second data set
output	output data set
comparator	element comparator

Definition at line 182 of file JMergeSort.hh.

    {
      size_t n = first.size() + second.size();
               
      output.reserve(n + 1);         // reserve space for end marker
      output.resize (n + 0);         // reserve space for data
      
      typename JContainer_t::const_iterator      i   = first .begin();
      typename JContainer_t::const_iterator      j   = second.begin();
      typename std::vector<JElement_t>::iterator out = output.begin();
      
      for ( ; n >= 4; n -= 4) {
        
        if (comparator(*i,*j))
          *out++ = *i++;
        else
          *out++ = *j++;
        
        if (comparator(*i,*j))
          *out++ = *i++;
        else
          *out++ = *j++;
 
        if (comparator(*i,*j))
          *out++ = *i++;
        else
          *out++ = *j++;
        
        if (comparator(*i,*j))
          *out++ = *i++;
        else
          *out++ = *j++;
      }
 
      for ( ; n != 0; --n) {
        
        if (comparator(*i,*j))
          *out++ = *i++;
        else
          *out++ = *j++;
      }
      
      *out = *i;                     // copy end marker
    }

getBuffer()

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

level	depth in internal buffer
side	either of two of a kind (left/right)

Returns

internal buffer

Definition at line 238 of file JMergeSort.hh.

    {
      if (level != 0) {
 
        switch (side) {
          
        case LEFT:
          return buffer[level - 1].first;
          
        case RIGHT:
          return buffer[level - 1].second;
        }
      }
 
      return mirror;
    }

merge() [2/2]

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

__begin	begin of set of data sets
__end	end of set of data sets
comparator	element comparator
level	depth in internal buffer
side	either of two of a kind (left/right)

Definition at line 267 of file JMergeSort.hh.

    {
      const size_t N = std::distance(__begin, __end);
 
      switch (N) {
 
      case 0:
        break;
 
      case 1:
        copy(__begin[0], getBuffer(level,side));
        break;
 
      case 2:
        merge(__begin[0], __begin[1], getBuffer(level,side), comparator);
        break;
 
      default:
 
        // recursion
 
        this->merge(__begin,       __begin + N/2, comparator, level + 1, LEFT);
        this->merge(__begin + N/2, __end,         comparator, level + 1, RIGHT);
 
        // combination
 
        merge(getBuffer(level + 1, LEFT), 
              getBuffer(level + 1, RIGHT), 
              getBuffer(level,side),
              comparator);
 
        break;
      }
    }

Member Data Documentation

buffer

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.

mirror

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:

• JMergeSort.hh