JMergeSort.hh

Go to the documentation of this file.

#ifndef __JTOOLS__JMERGESORT__
#define __JTOOLS__JMERGESORT__

#include <vector>
#include <functional>

#include "JLang/JTwosome.hh"
#include "JLang/JException.hh"


/**
 * \author mdejong
 */

namespace JTOOLS {}
namespace JPP { using namespace JTOOLS; }

namespace JTOOLS {

  using JLANG::JTwosome;
  using JLANG::LEFT;
  using JLANG::RIGHT;
  using JLANG::JValueOutOfRange;


  /**
   * 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:
   * <pre>
   *      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
   * </pre>
   *
   * The input should consist of a set of sorted data sets, each terminated by an end marker.\n
   * In this, an end marker corresponds to a value that is always larger than any physical value.\n
   * The end marker is the first element beyond the size but within the capacity of the container.\n
   * The output then consists of a single sorted data set which is also terminated by an end marker.
   */
  template<class JElement_t>
  class JMergeSort 
  {
  public:
    /**
     * Default constructor.
     */
    JMergeSort()
    {}


    /**
     * Merge set of sorted data sets into single sorted data set.
     *
     * \param  input         input  data sets
     * \param  output        output data set
     */
    template<class JSuperContainer_t, template<class, class> class JContainer_t, class JAllocator_t>
    inline void operator()(const JSuperContainer_t&                input,
                           JContainer_t<JElement_t, JAllocator_t>& output) const
    {
      (*this)(input.begin(), input.end(), output, std::less<JElement_t>());
    }


    /**
     * Merge set of sorted data sets into single sorted data set.
     *
     * \param  input         input  data sets
     * \param  output        output data set
     * \param  comparator    element comparator
     */
    template<class JSuperContainer_t, template<class, class> class JContainer_t, class JAllocator_t, class JComparator_t>
    inline void operator()(const JSuperContainer_t&                input,
                           JContainer_t<JElement_t, JAllocator_t>& output,
                           const JComparator_t&                    comparator) const
    {
      (*this)(input.begin(), input.end(), output, comparator);
    }


    /**
     * Merge set of sorted data sets into single sorted data set.
     *
     * \param  __begin       begin of input data sets
     * \param  __end         end   of input data sets
     * \param  output        output data set
     */
    template<class T, template<class, class> class JContainer_t, class JAllocator_t>
    inline void operator()(T __begin,
                           T __end,
                           JContainer_t<JElement_t, JAllocator_t>& output) const
    {
      (*this)(__begin, __end, output, std::less<JElement_t>());
    }


    /**
     * Merge set of sorted data sets into single sorted data set.
     *
     * \param  __begin       begin of input data sets
     * \param  __end         end   of input data sets
     * \param  output        output data set
     * \param  comparator    element comparator
     */
    template<class T, template<class, class> class JContainer_t, class JAllocator_t, class JComparator_t>
    inline void operator()(T __begin,
                           T __end,
                           JContainer_t<JElement_t, JAllocator_t>& output,
                           const JComparator_t&                    comparator) const
    {
      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);
      }
    }
    
    
  private:
    /**
     * Fast copy of data set.
     *
     * \param  input         input  data set
     * \param  output        output data set
     */
    template<class JContainer_t>
    static inline void copy(const JContainer_t&      input,
                            std::vector<JElement_t>& output)
    {
      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, ++in, ++out) {
        *out = *in;
      }

      *out = *in;                    // copy end marker
    }


    /**
     * 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.
     *
     * \param  first         first  data set
     * \param  second        second data set
     * \param  output        output data set
     * \param  comparator    element comparator
     */
    template<class JContainer_t, class JComparator_t>
    static inline void merge(const JContainer_t&      first,
                             const JContainer_t&      second,
                             std::vector<JElement_t>& output,
                             const JComparator_t&     comparator)
    {
      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 != 0; --n, ++out) {
        
        if (comparator(*i,*j)) {
          *out = *i;
          ++i;
        } else {
          *out = *j;
          ++j;
        }
      }
      
      *out = *i;                     // copy end marker
    }


    /**
     * Get internal buffer.
     *
     * \param  level         depth in internal buffer
     * \param  side          either of two of a kind (left/right)
     * \return               internal buffer
     */
    inline std::vector<JElement_t>& getBuffer(const size_t   level,
                                              const JTwosome side) const
    {
      if        (level == 0) {

        return mirror;

      } else if (level - 1 < buffer.size()) {

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

      THROW(JValueOutOfRange, "Invalid level " << level << " >= " << buffer.size());
    }


    /**
     * Recursive merge.
     *
     * \param  __begin       begin of set of data sets
     * \param  __end         end   of set of data sets
     * \param  comparator    element comparator
     * \param  level         depth in internal buffer
     * \param  side          either of two of a kind (left/right)
     */
    template<class _Iterator_t, class JComparator_t>
    inline void merge(_Iterator_t          __begin,
                      _Iterator_t          __end,
                      const JComparator_t& comparator,
                      const size_t         level = 0,
                      const JTwosome       side  = LEFT) const
    {
      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;
      }
    }
  

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

    mutable std::vector<pair>       buffer;
    mutable std::vector<JElement_t> mirror;
  };
}

#endif