mergesort.cpp

Go to the documentation of this file.

#include <algorithm>
#include <boost/smart_ptr.hpp>
#include <boost/thread/mutex.hpp>
#include <boost/threadpool.hpp>
#include <iostream>
#include <sstream>

using namespace std;
using namespace boost::threadpool;

//
// Helpers
boost::mutex m_io_monitor;

void print( string text )
{
  boost::mutex::scoped_lock lock( m_io_monitor );
  cout << text;
}

template <class T>
string to_string( const T& value )
{
  ostringstream ost;
  ost << value;
  ost.flush();
  return ost.str();
}

unsigned long get_ms_diff( boost::xtime& start, boost::xtime& end )
{
  boost::xtime::xtime_sec_t start_ms = start.sec * 1000 + start.nsec / 1000000;
  boost::xtime::xtime_sec_t end_ms   = end.sec * 1000 + end.nsec / 1000000;
  return static_cast<unsigned long>( end_ms - start_ms );
}

class image
{
public:
  image() : m_content( 0 ) {}
  image( int content ) : m_content( content ) {}

  image( const image& src ) { m_content = src.m_content; }

  bool operator<( const image& l ) const
  {
    { // simulate time needed for image comparision
      boost::xtime xt;
      boost::xtime_get( &xt, boost::TIME_UTC );
      int duration = 1 + ( m_content % 4 );
      xt.nsec += 250 * 1000 * duration;
      boost::thread::sleep( xt );
      print( "." );
    }
    return m_content < l.m_content;
  }

protected:
  int m_content; // represents image data in this example
};

template <class T>
class merge_job
{
public:
  merge_job( boost::shared_array<T> data, unsigned int position, unsigned int length )
      : m_data( data ), m_position( position ), m_length( length )
  {
    print( "merge job created : " + to_string( m_position ) + ", " + to_string( m_length ) + "\n" );
  }

  void run()
  {
    print( "merge job running :   " + to_string( m_position ) + ", " + to_string( m_length ) + "\n" );

    T* begin = m_data.get();
    std::advance( begin, m_position );

    T* mid = m_data.get();
    std::advance( mid, m_position + m_length / 2 );

    T* end = m_data.get();
    std::advance( end, m_position + m_length );

    std::inplace_merge( begin, mid, end );

    print( "\nmerge job finished:     " + to_string( m_position ) + ", " + to_string( m_length ) + "\n" );
  }

protected:
  boost::shared_array<T> m_data;
  unsigned int m_position;
  unsigned int m_length;
};

//
// A demonstration of the thread_pool class
int main( int argc, char* const argv[] )
{
  print( "MAIN: construct thread pool\n" );

  boost::xtime start;
  boost::xtime_get( &start, boost::TIME_UTC );

  int exponent = 7;
  int data_len = 1 << exponent; // = pow(2, exponent)

  print( "MAIN: sort array with " + to_string( data_len ) + " elements.\n" );

  boost::shared_array<image> data( new image[data_len] );

  // fill array with arbitrary values (not sorted ascendingly)
  for ( int i = 0; i < data_len; i++ ) {
    data[i] = image( ( data_len - i - 1 ) % 23 );
  }

  /***************************/
  /* Standard implementation */
  /***************************/

  pool tp;
  tp.size_controller().resize( 5 );

  // merge data array
  for ( int step = 1; step <= exponent; step++ ) {
    print( "\nMAIN: merge step " + to_string( step ) + "\n" );

    // divide array into partitions
    int partition_size = 1 << step;
    for ( int partition = 0; partition < data_len / partition_size; partition++ ) {
      // sort partition
      boost::shared_ptr<merge_job<image>> job(
          new merge_job<image>( data, partition * partition_size, partition_size ) );
      // tp->schedule(prio_task_func(5, boost::bind(&merge_job<image>::run, job)));
      schedule( tp, boost::bind( &merge_job<image>::run, job ) );
      // schedule(tp, job);
    }
    tp.wait(); // wait until all partitions are sorted
  }

  boost::xtime end;
  boost::xtime_get( &end, boost::TIME_UTC );

  print( "\nMAIN: duration " + to_string( get_ms_diff( start, end ) ) + " ms \n" );

  print( "\nMAIN: check if array is sorted... \n" );

  // check if array is sorted ascendingly
  bool ascending = true;
  for ( int i = 0; i < data_len - 1; i++ ) {
    if ( data[i + 1] < data[i] ) {
      ascending = false;
    }
  }

  if ( ascending ) {
    print( "\nMAIN: array is sorted\n" );
  } else {
    print( "\nMAIN: array is NOT sorted!\n" );
  }

  return 0;
}