#include <string>
#include <iostream>
#include <iomanip>
#include <fstream>
#include <sstream>
#include <vector>
#include <cctype>
#include <limits>
#include <ctype.h>
/*-------------------------------------------------------------------------
Usage: lowbowGeodesicDistance namesFile numFiles fout gridLen

Computes the distance between the file whose name is in the first line
of namesFile and other files whose names are in the second through last
row of the file namesFile (row 1 vs row 2, row 1 vs row 3 etc.).

numFiles is the number of rows in namesFile.
fout is the name of the output file.
gridLen is the number of samples in the range [0,1] representing
the document.

Guy Lebanon, June 2006.
--------------------------------------------------------------------------*/
using namespace std;
typedef vector<int> INTVEC;
typedef vector<double> DBLVEC;
void string2INTVEC(const string& line, INTVEC& numVec)
{
    istringstream ss(line);
    numVec.resize(0);
    string currW;
    while (ss>>currW) numVec.push_back((int)atof(currW.c_str()));   
}
void string2DBLVEC(const string& line, DBLVEC& numVec)
{
    istringstream ss(line);
    numVec.resize(0);
    string currW;
    while (ss>>currW) numVec.push_back(atof(currW.c_str()));   
}
void printINTVEC(const INTVEC& db){
    for (int i=0;i<db.size();i++) {
        cout << setw(5) << db[i] <<" "; 
        if ((i+1)%10 == 0) cout <<endl;
    } 
    cout <<endl;
}
void printDBLVEC(const DBLVEC& db){
    for (int i=0;i<db.size();i++) {
        cout << setw(5) << db[i] <<" "; 
        if ((i+1)%10 == 0) cout <<endl;
    } 
    cout <<endl;
}
int geodesicDistance(const string& fname1,const string& fname2,ofstream& fo,int gridLen)
{
    ifstream fx(fname1.c_str()),fy(fname2.c_str());
    if (!fx || !fy) {cerr<<"Error opening Files" <<endl;return -1;}
    int i,j,k;
    double currInnProd,meanDist=0;
    DBLVEC dx,dy;
    INTVEC ix,iy;
    string tx,ty;
    getline(fx,tx);string2INTVEC(tx,ix);
    getline(fy,ty);string2INTVEC(ty,iy);
    for (k=0;k<gridLen;k++) {
        i=0;j=0;currInnProd=0;
        getline(fx,tx);string2DBLVEC(tx,dx);
        getline(fy,ty);string2DBLVEC(ty,dy);
        while(1) {  
            if (i>=ix.size() || j>=iy.size()) break;
			if      (ix[i]==iy[j]) {currInnProd += sqrt(dx[i]*dy[j]);i++;j++;}
            else if (ix[i]< iy[j]) i++;
            else                   j++;
        }
		if (currInnProd<0) currInnProd=0;
		if (currInnProd>1) currInnProd=1;
		meanDist += acos(currInnProd);
    }
	fo << meanDist/((double)gridLen) << endl;
    return 1;
}
int main(int argc,char **argv) 
{
    if (argc!=5) {cerr<<"Incorrect number of arguments"<<endl;return -1;}
    ifstream ifs(argv[1]);
    ofstream  fo(argv[3]);
    int i,numFiles(atoi(argv[2])),gridLen(atoi(argv[4]));
    string fname1,fname2;
    if (!ifs || !fo) {cerr<<"Error opening Files" <<endl;return -1;}
    ifs >> fname1;
    for (i=1;i<numFiles;i++) {
        ifs >> fname2;
        geodesicDistance(fname1,fname2,fo,gridLen);
    }
    return 0;
}