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

using namespace std;

// Represents one thread's working information
struct ThreadInfo {
   int *vals;             // Array to check for inversions.
   int numVals;           // Size of vals
   int base;              // Our thread id.  Also our starting index.
   int skip;              // Number of threads total, and amount we should skip
   long long *counter;    // Common inversion count

   ThreadInfo(int *v, int nV, int b, int s, long long *c) 
    : vals(v), numVals(nV), base(b), skip(s), counter(c) {}
};


void *ThreadMain(void *vInfo) {
   ThreadInfo *info = (ThreadInfo *)vInfo;
   int baseIdx, cmpIdx;      

   for (baseIdx = info->base; baseIdx < info->numVals; baseIdx += info->skip)
      for (cmpIdx = baseIdx + 1; cmpIdx < info->numVals; cmpIdx++)
         if (info->vals[baseIdx] > info->vals[cmpIdx]) 
            (*info->counter)++;

   return NULL;
}

// 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;
   pthread_t *threads;
   int *vals;

   String s1, s2;

   s1 = new String();

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

   threads = (pthread_t *)calloc(sizeof(pthread_t), 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++)
      pthread_create(&threads[idx], NULL, ThreadMain, 
       new ThreadInfo(vals, numVals, idx, numThreads, &numInvs));

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