#include <iostream>
#include <stdlib.h>
#include <string.h>
#include <pthread.h>

using namespace std;

// Represents one worker thread, including full pthread status, mutex, 
// and computational information
struct Thread {
   pthread_t id;        // ID of created thread
   int *vals;           // Array to check for inversions.
   int numVals;         // Size of vals
   int base;            // Our thread id, and starting index.
   int skip;            // Number of threads total, and amount we should skip
   long long *counter;  // Common inversion count
   
   // Mutex to protect against simultaneous access to *counter
   static pthread_mutex_t mutex;

   Thread(int *v, int nV, int b, int s, long long *c) : vals(v), numVals(nV),
    base(b), skip(s), counter(c)   {
      pthread_create(&id, NULL, ThreadMain, this);
   }

   static void *ThreadMain(void *vThread) {
      ((Thread *)vThread)->Run();
   }

   void Run() {
      int baseIdx, cmpIdx;
      long long invCount = 0;      

      for (baseIdx = base; baseIdx < numVals; baseIdx += skip)
         for (cmpIdx = baseIdx + 1; cmpIdx < numVals; cmpIdx++)
            if (vals[baseIdx] > vals[cmpIdx])
               invCount++;

      pthread_mutex_lock(&mutex);
      *counter += invCount;
      pthread_mutex_unlock(&mutex);
   }

   void Join() {
      pthread_join(id, NULL);
   }
};

pthread_mutex_t Thread::mutex = PTHREAD_MUTEX_INITIALIZER;

// Count number of inversions in an array of size specified by commandline
// argument, and filled with inverse-order values.  Spread the work among 
// a number of threads also specified in commandline arguments.
int main(int argc, char* argv[]) {
   int idx, numVals, numThreads;
   long long numInvs = 0;
   Thread **threads;
   int *vals;

   if (argc != 3)
      cout << "Usage: InvCounter <numVals> <numThreads>" << endl;
   else {
      numVals = atoi(argv[1]);
      numThreads = atoi(argv[2]);
   }

   threads = (Thread **)calloc(sizeof(Thread *), numThreads);
   vals = (int *)calloc(sizeof(int), numVals);

   // Fill array in inverted order to maximize number of inversions
   for (idx = 0; idx < numVals; idx++)
      vals[idx] = numVals - idx;

   for (idx = 0; idx < numThreads; idx++)
      threads[idx] = new Thread(vals, numVals, idx, numThreads, &numInvs);

   // Thread constructor also starts threads.  Just wait for completion.
   for (idx = 0; idx < numThreads; idx++)
      threads[idx]->Join();

   cout << "Number of inversions: " << numInvs << endl;
   return 0;
}