JMergeSort.cc

Go to the documentation of this file.

 
#include <iostream>
#include <iomanip>
#include <functional>
#include <limits>
#include <vector>
#include <algorithm>
 
#include "TRandom3.h"
 
#include "JTools/JMergeSort.hh"
 
#include "Jeep/JTimer.hh"
#include "Jeep/JParser.hh"
#include "Jeep/JMessage.hh"
 
 
namespace JTOOLS {
 
  /**
   * Merge multiple sorted ranges.
   *
   * \param  __begin            begin of data
   * \param  N                  number of delimiters (equals number of ranges plus one)
   * \param  delimiter          incremental delimiters
   */
  template<class T>
  void inplace_merge(T __begin, const size_t N, const size_t* delimiter)
  {
    switch (N - 1) {
 
    case 0:
    case 1:
      break;
 
    case 2:
 
      std::inplace_merge(__begin + delimiter[0],
                         __begin + delimiter[1],
                         __begin + delimiter[2]);
 
      break;
 
    default:
      
      const size_t n = (N - 1) >> 1;
 
      inplace_merge(__begin, n + 1, delimiter);
      inplace_merge(__begin, N - n, delimiter + n);
 
      std::inplace_merge(__begin + delimiter[ 0 ],
                         __begin + delimiter[ n ],
                         __begin + delimiter[N-1]);
 
      break;
    };
  }
 
 
  /**
   * Auxiliary class to convert value to element.
   */
  template<class T>
  struct JGetElement
  {
    /**
     * Default constructor.
     */
    JGetElement()
    {}
    
 
    /**
     * Type conversion operator.
     *
     * \param  x                  value
     * \return                    element
     */
    inline T operator()(const double x) const
    {
      return (T) x;
    }
 
 
    /**
     * Get end marker.
     *
     * \return                    element
     */
    static inline T getEndMarker()
    {
      return std::numeric_limits<T>::max();
    }
  };
 
 
  /**
   * Test whether range is sorted.
   *
   * \param  __begin            begin of data
   * \param  __end              end   of data
   * \return                    true if sorted; else false
   */
  template<class T>
  inline bool is_sorted(T __begin, T __end)
  {
    if (std::distance(__begin, __end) > 1) {
      for (T q = __begin, p = q++; q != __end; ++p, ++q) {
        if (*p > *q) {
          return false;
        }
      }
    }
 
    return true;
  }
}
 
 
/**
 * \file
 *
 * Example program to test performance of JTOOLS::JMergeSort.
 * \author mdejong
 */
int main(int argc, char **argv)
{
  using namespace std;
 
  double         rate_Hz;
  bool           do_test;
  int            debug;
 
  try {
 
    JParser<> zap("Example program to test performance of merge sort.");
 
    zap['B'] = make_field(rate_Hz);
    zap['D'] = make_field(do_test);
    zap['d'] = make_field(debug)               = 0;
 
    zap(argc, argv);
  }
  catch(const exception &error) {
    FATAL(error.what() << endl);
  }
 
 
  using namespace JPP;
 
  if (rate_Hz <= 0.0) {
    FATAL("Rate " << rate_Hz << " < 0 Hz." << endl);
  }
 
  const double period = 1.0e9 / rate_Hz;      // [ns]
 
  const double Tmin   = 0.0;                  // [ns]
  const double Tmax   = 1.0e8;                // [ns]
 
  const int NUMBER_OF_PMTS    =       31;
  const int NUMBER_OF_MODULES = 115 * 18;
 
 
  //typedef int                        hit_type; 
  typedef double                     hit_type; 
  typedef JGetElement<hit_type>      JGetElement_t;
  const   JGetElement_t              getElement;
  typedef std::vector<hit_type>      JBuffer1D;
  typedef std::vector<JBuffer1D>     JBuffer2D;
 
 
  // generate random data
 
  JBuffer2D input(NUMBER_OF_PMTS);
 
  for (int i = 0; i != NUMBER_OF_PMTS; ++i) {
 
    for (double t1 = Tmin + gRandom->Exp(period); t1 < Tmax; t1 += gRandom->Exp(period)) {
      input[i].push_back(getElement(t1));
    }
 
    NOTICE("PMT[" << setw(2) << i << "]  " << input[i].size() << endl);
 
    input[i].push_back(JGetElement_t::getEndMarker());
  }
 
 
  if (true) {
 
    JTimer timer("std::sort");
 
    JBuffer1D buffer;
 
    timer.start();
 
    for (int i = 0; i != NUMBER_OF_MODULES; ++i) {
 
      buffer.clear();
 
      for (int i = 0; i != NUMBER_OF_PMTS; ++i) {
        copy(input[i].begin(), input[i].end() - 1, back_inserter(buffer));
      }
 
      std::sort(buffer.begin(), buffer.end());
 
      if (do_test && !JTOOLS::is_sorted(buffer.begin(), buffer.end())) { 
        FATAL("std::sort failed." << endl);
      }
    }
 
    timer.stop();
    timer.print(cout, false);
  }
 
  if (true) {
 
    JTimer timer("std::inplace_merge");
 
    JBuffer1D buffer;
 
    vector<size_t> delimiter(NUMBER_OF_PMTS + 1);
 
    timer.start();
 
    for (int i = 0; i != NUMBER_OF_MODULES; ++i) {
 
      size_t n = 0;
 
      for (int i = 0; i != NUMBER_OF_PMTS; ++i) {
        n += input[i].size() - 1;
      }
 
      buffer.resize(n);
 
      JBuffer1D::iterator out = buffer.begin();      
 
      delimiter[0] = 0;
 
      for (int i = 0; i != NUMBER_OF_PMTS; ++i) {
 
        out = copy(input[i].begin(), input[i].end() - 1, out);
 
        delimiter[i+1] = distance(buffer.begin(), out);
      }
 
      inplace_merge(buffer.begin(), delimiter.size(), delimiter.data());
 
      if (do_test && !JTOOLS::is_sorted(buffer.begin(), buffer.end())) {
        FATAL("std::inplace_merge failed." << endl);
      }
    }
 
    timer.stop();
    timer.print(cout, false);
  }
 
  if (true) {
 
    JTimer timer("JMergeSort");
 
    JBuffer1D            buffer;
    JMergeSort<hit_type> merge;
 
    timer.start();
 
    for (int i = 0; i != NUMBER_OF_MODULES; ++i) {
 
      buffer.clear();
      
      merge(input, buffer);
 
      if (do_test && !JTOOLS::is_sorted(buffer.begin(), buffer.end())) {
        FATAL("JMergeSort failed." << endl);
      }
    }
 
    timer.stop();
    timer.print(cout, false);
  }
}