// ECE 462 Object-Oriented Programming using C++ and Java
// by Yung-Hsiang Lu, Purdue University
//
// purpose :compare the execution time of computation without and with
// threads
// 
// This program finds the number of prime numbers smaller than a given
// range. 
//
// To compile, follow these three steps:
// qmake -project
// qmake
// make
// 
// To execute, type
// ./lab07 1000 => find the number of prime numbers smaller than 1000
//
// Please use one of the qstructxx.ecn.purdue.edu machines. 
// Each has 2 quad-core processors
// 
// requirements:
// 1. fix any error this program may contain so that it reports
//    correctly how many prime numbers are smaller than a given input
// 2. convert this program to a Java program with the same functionality
// 3. execute both programs on one of the four meachines calle
//    qstruct01.ecn - qstruct19.ecn
// 4. compare the time to execute the two programs for input parameters
//    of 1000 (thousand), 100000 (hundred thousand), 
//    100000000 (ten million) using 1, 2, 3, 4, 5, 6, 7, and 8 threads
// 
// submission: 
// 1. C++ code (if you modify this program)
// 2. Java code
// 3. a graph (PDF) showing the speedup, the horizontal axis is the
//    number of threads, the vertical axis is the speedup. There should
//    be 6 curves: 3 for C++ using 1000, 100000, and 10000000 as the
//    input and 3 for Java using 1000, 100000, and 10000000 as the input.
//    The speedup is calculate using Java and one thread as the base
//    
// If you find any error in this program, please post it in Blackboard
// Discussion.  Thank you.

#include <QThread>
#include <QMutex>
#include <QWaitCondition>
#include <cstdlib>
#include <iostream>
#include <ctime>
#include <sys/time.h>


using namespace std;
bool IsPrime(int num) 
{
  if (num == 2) { return true; }
  if (num == 3) { return true; }
  if (num == 5) { return true; }
  if ((num % 2) == 0) { return false; }
  if ((num % 3) == 0) { return false; }
  if ((num % 5) == 0) { return false; }
  int factor = 5;
  // not an efficient way to test prime numbers
  do 
    {
      if ((num % factor) == 0) 
	{ return false;	}
      factor += 2;
    } while ((factor * factor) <= num);
  return true;
}

class PartialSum { // how many prime number has been discovered so
		   // far?
public:
  PartialSum() 
  {
    sum = 0;
    // no need to call the constructor of mutex or cond since they are
    // objects (not pointers)
  }
  void update(int amount) 
  {
    mutex.lock();
    sum += amount;
    // threadCount ++;
    cond.wakeAll();
    mutex.unlock();
  }
  int getSum()
  { return sum; }
private:
  QMutex mutex;
  QWaitCondition cond;
  int sum;
};

int TotalPrime(int lowLimit, int highLimit) 
{
  // how many prime numbers exist between [lowLimit, highLimit]?
  int sum = 0;
  if (lowLimit == 2) 
    { 
      sum ++; 
      // cout << "2 is prime" << endl; 
    }
  if ((lowLimit % 2) == 0) // even number
    { lowLimit ++; }
  for (int curNum = lowLimit; curNum <= highLimit; curNum += 2) 
    {
      if (IsPrime(curNum) == true) 
	{ 
	  sum ++; 
	  // cout << curNum << " is prime" << endl; 
	}
    }
  return sum;
}

class PrimeCounter : public QThread {
public:
  PrimeCounter(int low, int high, PartialSum * sum):
    lowLimit(low), highLimit(high) 
  { psum = sum; }
  void run() 
  { psum -> update(TotalPrime(lowLimit, highLimit)); }
private:
  int lowLimit;
  int highLimit;
  PartialSum * psum;
};

int main(int argc, char* argv[])
{
  struct timeval tp1;
  struct timeval tp2;
  int lowLimit = 2; 
  int highLimit = 10000000;
  if (argc == 2) // second parameter is the highLimit
    { highLimit = atoi(argv[1]); }
  if (argc > 2) // lowLimit and highLimit, ignore the rest
    { 
      lowLimit = atoi(argv[1]); 
      highLimit = atoi(argv[2]); 
    }
  gettimeofday(&tp1, NULL);
  int numPrime = TotalPrime(lowLimit, highLimit);
  gettimeofday(&tp2, NULL);
  cout << "Total Number of Primes = " << numPrime << endl;
  // check correctness at
  // http://primes.utm.edu/howmany.shtml
  cout << "spent time = " << 
    (tp2.tv_usec - tp1.tv_usec) * 1e-6 +
    (tp2.tv_sec - tp1.tv_sec) << endl;
  int numThread = 8;
  gettimeofday(&tp1, NULL);
  PartialSum * psum = new PartialSum;
  PrimeCounter * counter[numThread];
  int interval = (highLimit - lowLimit) / numThread;
  for (int tcnt = 0; tcnt < numThread - 1; tcnt ++) 
    {
      counter[tcnt] = new 
	PrimeCounter(lowLimit, lowLimit + interval, psum);
      lowLimit += interval + 1;
    }
  // handle the situation if numThread is not a factor of 
  // (highLimit - LowLimit)
  counter[numThread - 1] = new 
    PrimeCounter(lowLimit, highLimit, psum);
  for (int tcnt = 0; tcnt < numThread; tcnt ++) 
    { counter[tcnt] -> start(); }
  for (int tcnt = 0; tcnt < numThread; tcnt ++) 
    { counter[tcnt] -> wait(); }
  gettimeofday(&tp2, NULL);
  cout << "Total Number of Primes = " << psum -> getSum() << endl;
  cout << "spent time = " << 
    (tp2.tv_usec - tp1.tv_usec) * 1e-6 +
    (tp2.tv_sec - tp1.tv_sec) << endl;
  return 0;
}