CountInversion.cpp

#include "CountInversion.h"

int main( int argc, char* argv[] ){

 string inFile = "";
 bool printHelp = false;
 for(int i = 1; i < argc; i++){ 
 bool validCmd = false;
 string cmd = argv[i];
 if( !strcmp(argv[i],"--inFile") ){
 if( checkOpt(argv[i],argv[i+1]) ) { inFile = argv[i+1]; } validCmd = true; }
 else if( !strcmp(argv[i],"--brutal") ){ m_brutal = true; validCmd = true; }
 else if( !strcmp(argv[i],"--debug") ){ m_debug = true; validCmd = true; }
 else if( !strcmp(argv[i],"--verbose") ){ m_verbose = true; validCmd = true; }
 else if( !strcmp(argv[i],"--help") ){ printHelp = true; validCmd = true; }
 if( !validCmd && cmd.find("--")!=string::npos){
 cout << "\033[1;31m ERROR:: Option " << cmd << " not valid. Type ./CountInversion"
	 << " --help and check the available options, exit!\033[0m" << endl;
 exit(0);
 }
 }
 if( printHelp ){
 cout << "CountInversion Algorithm: count number of inversions in the array" << endl;
 cout << " usage: ./CountInversion [--help] [--inFile] [--brutal] " << endl;
 cout << " [--debug] [--verbose]" << endl;
 cout << " arguments (default value): " << endl;
 cout << " --help print this help and exit" << endl;
 cout << " --inFile define input file with the array (None)" << endl;
 cout << " --brutal enable brute forse mode - double loop (false)" << endl;
 cout << " --debug enable debug mode (false)" << endl;
 cout << " --verbose enable verbose mode (false)" << endl;
 exit(0);
 }

 vector<int> tmpVec;
 int num = 0;
 if(inFile=="" ){
 cout << " WARNING:: inFile is a needed argument!! \n"
	 << " Please type name and path to it" << endl;
 cin >> inFile;
 }

 m_inStream.open( inFile.c_str() );
 if( !m_inStream.good() ){
 cout << " ERROR:: inFile " << inFile << " doesn't exist \n"
	 << " Please enter the array manually! \n"
	 << " Type the size of the array " << endl;
 int size = 0;
 cin >> size;
 for(int i=0; i<size; i++){
 cout << " Type an integer " << endl;
 cin >> num;
 tmpVec.push_back( num );
 num = 0;
 }
 } 
 else{
 cout << " File containing the array is : " << inFile << endl;
 while( m_inStream.good() ){
 m_inStream>>num;
 tmpVec.push_back(num);
 num=0;
 }
 }
 m_inStream.close();

 int array[tmpVec.size()];
 for(uint i=0; i<tmpVec.size(); i++){
 array[i] = tmpVec[i];
 }
 
 if(m_debug){
 cout << " Size of the (vec , array) = (" << tmpVec.size()
	 << " , " << sizeof(array) / sizeof(*array) << ")" << endl;
 cout << " DEBUG:: values in the array are : " << endl;
 printArray(array,sizeof(array) / sizeof(*array));
 cout << " DEBUG:: values in the vector are: " << endl;
 printVector(tmpVec);
 }
 if(tmpVec.size()!=sizeof(array) / sizeof(*array)){
 cout << " ERROR:: wrong conversion from vector to array! Exiting" << endl;
 exit(0);
 }
 tmpVec.clear();
 
 long unsigned int Ninv = 0;
 if(m_brutal)
 Ninv = countInversions( array, sizeof(array) / sizeof(*array) );
 else
 Ninv = countInversions( array, sizeof(array) / sizeof(*array) );
 cout << " Number of inversions is : "<< Ninv << endl;
 
 return 0;

}

long unsigned int countInversions(int array[], int size){

 int tmp[size];
 return countInv(array, tmp, 0, size -1 );
 
}

long unsigned int countInv(int array[], int tmp[], int left, int right){
 
 // initialize n. inversions to 0;
 long unsigned int linv = 0;
 long unsigned int rinv = 0;
 long unsigned int sinv = 0;
 long unsigned int total = 0;

 if(right>left){

 // define middle point of the array
 int mid = (right+left)/2;
 
 // count left/right inversions
 linv = countInv( array, tmp, left, mid);
 rinv = countInv( array, tmp, mid+1, right);

 //count split inversion
 sinv = countSplitInv( array, tmp, left, mid+1, right );

 //sum up inversions
 total = linv+rinv+sinv;

 if(m_debug){
 cout << " DEBUG:: left inversions = " << linv << endl;
 cout << " DEBUG:: right inversions = " << rinv << endl;
 cout << " DEBUG:: split inversions = " << sinv << endl;
 cout << " DEBUG:: total inversions = " << total << endl;
 }
 }
 
 return total;
 
}

long unsigned int countSplitInv(int array[], int tmp[], int left, int mid, int right){

 // Fill the resultant vector with sorted results from both vectors

 int splitInv = 0;
 int i = left; // i -> index for left subarray
 int j = mid; // j -> index for right subarray
 int k = left; // k -> index for resultant merged subarray
 
 while ( (i<=mid-1) && (j<=right)) { 
 if (array[i] <= array[j]) { 
 tmp[k++] = array[i++]; 
 } 
 else { 
 tmp[k++] = array[j++];
 //split inversion = remaining element in left subarray at this point
 splitInv += (mid-i); 
 } 
 } 
 
 //Copy remaining elements of left subarray (if any) to resultant array
 while (i <= mid - 1) 
 tmp[k++] = array[i++]; 

 // Copy remaining elements of right subarray (if any) to resultant array
 while (j <= right) 
 tmp[k++] = array[j++]; 
 
 // Copy back the merged elements to original array
 for (i = left; i <= right; i++) 
 array[i] = tmp[i]; 
 
 return splitInv;
 
}

bool checkOpt(char* opt, char* value){

 std::string val = value;
 if( 0==val.find("--") ){
 cout << "WARNING:: Option " << opt <<
 " requires value -> skipping " << endl;
 return false;
 }
 return true;
 
}

void printArray(int array [], int size){
 
 for(int i=0; i<size; i++){
 if(i==0) cout << " " << array[i];
 else cout << " , " << array[i];
 }
 cout << endl;
 
}

void printVector(vector<int> vec){
 
 for(uint i=0; i<vec.size(); i++){
 if(i==0) cout << " " << vec[i];
 else cout << " , " << vec[i];
 }
 cout << endl;
 
}

long unsigned int getInvCount(int arr[], int n){ 

 long unsigned int invs = 0; 
 for(int i=0; i <n-1; i++) 
 for(int j=i+1; j<n; j++) 
 if (arr[i] > arr[j]) 
	invs++; 
 
 return invs;
 
}