All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Properties Friends Macros Modules Pages
mergesort.cpp
Go to the documentation of this file.
1 
17 #include <boost/threadpool.hpp>
18 #include <boost/thread/mutex.hpp>
19 #include <boost/smart_ptr.hpp>
20 #include <iostream>
21 #include <sstream>
22 #include <algorithm>
23 
24 
25 
26 using namespace std;
27 using namespace boost::threadpool;
28 
29 //
30 // Helpers
31 boost::mutex m_io_monitor;
32 
33 void print(string text)
34 {
35  boost::mutex::scoped_lock lock(m_io_monitor);
36  cout << text;
37 }
38 
39 template<class T>
40 string to_string(const T& value)
41 {
42  ostringstream ost;
43  ost << value;
44  ost.flush();
45  return ost.str();
46 }
47 
48 unsigned long get_ms_diff(boost::xtime& start, boost::xtime& end)
49 {
50  boost::xtime::xtime_sec_t start_ms = start.sec * 1000 + start.nsec/1000000;
51  boost::xtime::xtime_sec_t end_ms = end.sec * 1000 + end.nsec/1000000;
52  return static_cast<unsigned long>(end_ms - start_ms);
53 }
54 
55 class image
56 {
57 public:
58  image() : m_content(0) {}
59  image(int content) : m_content(content) {}
60 
61  image(const image& src)
62  {
63  m_content = src.m_content;
64  }
65 
66  bool operator<(const image& l) const
67  {
68  { // simulate time needed for image comparision
69  boost::xtime xt;
70  boost::xtime_get(&xt, boost::TIME_UTC);
71  int duration = 1+(m_content % 4);
72  xt.nsec += 250 * 1000 * duration;
73  boost::thread::sleep(xt);
74  print(".");
75  }
76  return m_content < l.m_content;
77  }
78 
79 protected:
80  int m_content; // represents image data in this example
81 };
82 
83 
84 template<class T>
85 class merge_job
86 {
87 public:
88  merge_job(boost::shared_array<T> data, unsigned int position, unsigned int length)
89  : m_data(data)
90  , m_position(position)
91  , m_length(length)
92  {
93  print("merge job created : " + to_string(m_position) +", "+ to_string(m_length) +"\n");
94  }
95 
96  void run()
97  {
98  print("merge job running : " + to_string(m_position) +", "+ to_string(m_length) +"\n");
99 
100  T* begin = m_data.get();
101  std::advance(begin, m_position);
102 
103  T* mid = m_data.get();
104  std::advance(mid, m_position + m_length/2);
105 
106  T* end = m_data.get();
107  std::advance(end, m_position + m_length);
108 
109  std::inplace_merge(begin, mid, end);
110 
111  print("\nmerge job finished: " + to_string(m_position) +", "+ to_string(m_length) +"\n");
112  }
113 
114 protected:
115  boost::shared_array<T> m_data;
116  unsigned int m_position;
117  unsigned int m_length;
118 };
119 
120 
121 
122 
123 //
124 // A demonstration of the thread_pool class
125 int main (int argc, char * const argv[])
126 {
127  print("MAIN: construct thread pool\n");
128 
129 
130 
131  boost::xtime start;
132  boost::xtime_get(&start, boost::TIME_UTC);
133 
134  int exponent = 7;
135  int data_len = 1 << exponent; // = pow(2, exponent)
136 
137  print("MAIN: sort array with "+ to_string(data_len) + " elements.\n");
138 
139  boost::shared_array<image> data(new image[data_len]);
140 
141  // fill array with arbitrary values (not sorted ascendingly)
142  for(int i = 0; i < data_len; i++)
143  {
144  data[i] = image((data_len - i - 1) % 23);
145  }
146 
147 
148  /***************************/
149  /* Standard implementation */
150  /***************************/
151 
152  pool tp;
153  tp.size_controller().resize(5);
154 
155 // merge data array
156  for(int step = 1; step <= exponent; step++)
157  {
158  print("\nMAIN: merge step "+ to_string(step)+"\n");
159 
160  // divide array into partitions
161  int partition_size = 1 << step;
162  for(int partition = 0; partition < data_len/partition_size; partition++)
163  {
164  // sort partition
165  boost::shared_ptr<merge_job<image> > job(new merge_job<image>(data, partition*partition_size, partition_size));
166  //tp->schedule(prio_task_func(5, boost::bind(&merge_job<image>::run, job)));
167  schedule(tp, boost::bind(&merge_job<image>::run, job));
168  // schedule(tp, job);
169  }
170  tp.wait(); // wait until all partitions are sorted
171  }
172 
173  boost::xtime end;
174  boost::xtime_get(&end, boost::TIME_UTC);
175 
176  print("\nMAIN: duration " + to_string(get_ms_diff(start, end)) + " ms \n");
177 
178  print("\nMAIN: check if array is sorted... \n");
179 
180  // check if array is sorted ascendingly
181  bool ascending = true;
182  for(int i = 0; i < data_len-1; i++)
183  {
184  if(data[i+1] < data[i])
185  {
186  ascending = false;
187  }
188  }
189 
190  if(ascending)
191  {
192  print("\nMAIN: array is sorted\n");
193  }
194  else
195  {
196  print("\nMAIN: array is NOT sorted!\n");
197  }
198 
199  return 0;
200 }
image(const image &src)
Definition: mergesort.cpp:61
void wait(size_t task_threshold=0) const
The current thread of execution is blocked until the sum of all active and pending tasks is equal or ...
Definition: pool.hpp:176
void run()
Definition: mergesort.cpp:96
unsigned int m_position
Definition: mergesort.cpp:116
merge_job(boost::shared_array< T > data, unsigned int position, unsigned int length)
Definition: mergesort.cpp:88
T inplace_merge(T...args)
unsigned int m_length
Definition: mergesort.cpp:117
image(int content)
Definition: mergesort.cpp:59
int main(int argc, char *const argv[])
Definition: mergesort.cpp:125
list argv
Definition: gaudirun.py:227
T advance(T...args)
unsigned long get_ms_diff(boost::xtime &start, boost::xtime &end)
Definition: mergesort.cpp:48
T to_string(T...args)
STL namespace.
T end(T...args)
int m_content
Definition: mergesort.cpp:80
T partition(T...args)
image()
Definition: mergesort.cpp:58
bool operator<(const image &l) const
Definition: mergesort.cpp:66
boost::shared_array< T > m_data
Definition: mergesort.cpp:115
disable_if< is_void< typename result_of< Function() >::type >, future< typename result_of< Function() >::type >>::type schedule(Pool &pool, const Function &task)
Definition: future.hpp:111
T lock(T...args)
start
Definition: IOTest.py:88
size_controller_type size_controller()
Gets the size controller which manages the number of threads in the pool.
Definition: pool.hpp:111
dictionary l
Definition: gaudirun.py:421
boost::mutex m_io_monitor
Definition: mergesort.cpp:31
T flush(T...args)
T begin(T...args)
void print(string text)
Definition: mergesort.cpp:33
Main include.