/*AUTHOR: Ravi Prakash
          pursuing MS in Computer Science
          University of Southern California, Los Angeles
*/
#include<string.h>
#include <map>
#include<iostream>
#include<conio.h>
#include<fstream>
#include<cxcore.h>
#include<cvaux.h>
#include<highgui.h>

#define MAXNUMBER 100
#define TOADD 100

using namespace std;

//Converts a string containing a value to a double
double parseDouble(char *str)
{
       double toret=0.0, toMul=0.01;
       int index=0;
       while(str[index]!='\0')
       {
            toMul*=10;
            if(str[index]=='.') break;
            else index++;
       }
       int i=0;
       while(str[i]!='\0')
       {
               if(str[i]=='.') {i++; continue;}
               toret+=toMul*(str[i]-48);
               toMul/=10;
               i++;
       }
       return toret;
}

//Converts a string containing a value to an integer
int parseInt(char *str)
{
       int toret=0, index=0;
       while(str[index]!='\0')
       {
            toret=toret*10+(str[index]-48);
            index++;
       }
       return toret;
}

//Each feature consists of position (x,y), scale, orientation and a 128 integer vector representing the feature.
class feature
{
      public:
      double x, y, scale, orientation;
      int *featVect, vectDim;
      feature()
      {
           featVect=new int[128];
           vectDim=128;
      }
      feature(int N)
      {
           featVect =new int[N];
           vectDim=N;
      }

};

//Linked list for features. Adds only at the end of the LL. Converts Linked list to array
class ll
{
      //A node in the Linked list
      class node
      {
            public:
            feature *now;
            node *next;
      };

      public:
      int noOfNodes;

      node* Start;
      node* last;

      ll()
      {Start=NULL; last=NULL; noOfNodes=0;}

      //Add a node to the Linked list at the end
      void add(feature *f)
      {
           node *n=new node;
           (*n).now=f;
           (*n).next=NULL;
           if(Start==NULL)
           {
                Start=n;
                last=n;
           }
           else
           {
               (*last).next=n;
               last=n;
           }
           noOfNodes++;
      }

      //Store the pointers to the features in the linked list, in an array
      feature** arrize()
      {
                feature** toret = new feature*[noOfNodes];
                node *temp=Start;
                for(int i=0; i<noOfNodes; i++)
                {
                        toret[i]=(*temp).now;
                        temp=(*temp).next;
                }
                return toret;
      }
};

// Abstracts the image's features.
class image
{
      public:
      int noOfFeatures;
      feature** featArr;

      ~image()
      {
              for(int i=0; i<noOfFeatures; i++) delete featArr[i];
              delete featArr;
      }

      //Read all the features of the image from a file
      void readKeyFile(char *fileName)
      {
           printf("\nReading: %s. ", fileName);
           ifstream file1(fileName);
           if(!file1)
           {
                cout<<"\nFile open failed";
                exit(0);
           }

           ll tempLL;
           char number[MAXNUMBER];
           while(!file1.eof())
           {
                 feature *temp=new feature;
                 file1>>number; (*temp).x=parseDouble(number);
                 file1>>number; (*temp).y=parseDouble(number);
                 file1>>number; (*temp).scale=parseDouble(number);
                 file1>>number; (*temp).orientation=parseDouble(number);
                 for(int i=0; i<128; i++)
                 {
                       file1>>number;
                      (*temp).featVect[i]=parseInt(number);
                 }
                 tempLL.add(temp);
           }
           file1.close();
           featArr=tempLL.arrize();
           noOfFeatures=tempLL.noOfNodes;
      }

      //Print out the position, scale and orientation of all features. For testing only.
      void test()
      {
           feature *f;
           for(int i=0; i<10; i++)
           {
                   f=featArr[i];
                   printf("\n%f %f %f %f ", (*f).x, (*f).y, (*f).scale, (*f).orientation);
                   getch();
           }
      }
};


class trainer
{
      public:
      CvMat *dataArr, *eigenvectors, *eigenvalues, *avg, *result;
      image *i1;
      int *imBounds, nFiles;
      
      trainer(char *iFileName, int N)
      {
           char temp[MAXNUMBER];
           ifstream iFile1(iFileName);
           nFiles=0;
           while(!iFile1.eof()) //count the number of images in training set.
           {
                iFile1>>temp;
                nFiles++;
           }
           iFile1.close();

           printf("\nNumber of files : %d", nFiles);

           imBounds=new int[nFiles+1];
           imBounds[0]=0;
           ifstream iFile(iFileName);
           int count=0;
           i1=new image[nFiles];
           char str[100];
           while(!iFile.eof())
           {
                iFile>>temp;
                strcpy(str, "training_set\\");
                strcat(str, temp);
                strcat(str, ".key");
                i1[count].readKeyFile( str ) ;
                printf("nOfFeatures=%d. ", i1[count].noOfFeatures);
                count++;
                imBounds[count]=imBounds[count-1] + i1[count-1].noOfFeatures;
                printf("imBound=%d", imBounds[count]);
           }
           iFile.close();
           printf("\n\nAll images loaded in memory. No. of Images=%d\nNumber of total features = %d", nFiles, imBounds[nFiles]);
           
           dataArr=cvCreateMat( imBounds[nFiles], 128, CV_64FC1 );
           
           printf("\nMatrix created of size %dx%d", dataArr->rows, dataArr->cols);
           
           for(int i=0; i<nFiles; i++)                   //transfer image[i]'s features into dataArr
                   for(int j=imBounds[i]; j<imBounds[i+1]; j++)
                           for(int k=0; k<128; k++)
                                   ((double*)(dataArr->data.ptr + dataArr->step*j ))[k] = (i1[i].featArr[j-imBounds[i]])->featVect[k];

           avg = cvCreateMat(1, dataArr->cols, CV_64FC1);
           eigenvalues = cvCreateMat(1, min(dataArr->rows, dataArr->cols), CV_64FC1);
           eigenvectors = cvCreateMat(min(dataArr->rows,dataArr->cols), dataArr->cols, CV_64FC1);

           cvCalcPCA(dataArr, avg, eigenvalues, eigenvectors, CV_PCA_DATA_AS_ROW);
           printf("\ncvCalcPCA complete. eigenvectors:%dx%d. eigenvalues:%dx%d", eigenvectors->rows, eigenvectors->cols, eigenvalues->rows, eigenvalues->cols);

           result= cvCreateMat(dataArr->rows, N, CV_64FC1);
           cvProjectPCA(dataArr, avg, eigenvectors, result);
           printf("\ncvProjectPCA complete. Result: %dx%d", result->rows, result->cols);

           delete imBounds;
      }
      
      ~trainer()
      {
           delete i1;
           cvReleaseMat(&dataArr);
           cvReleaseMat(&eigenvalues);
           cvReleaseMat(&eigenvectors);
           cvReleaseMat(&avg);
           cvReleaseMat(&dataArr);
      }

};

class tester
{
      public:

      tester(trainer t1, char *iFileName, int k_nearest, int N, int diameter)
      {
           char temp[MAXNUMBER];
           ifstream iFile1(iFileName);
           ofstream iFile2("output.txt");
           int nFiles=0;
           while(!iFile1.eof()) //count the number of images in training set.
           {
                iFile1>>temp;
                nFiles++;
           }
           iFile1.close();
           
           ifstream iFile(iFileName);
           char str[100];
           image im;
           CvMat *dataArr, *result;

           double *distance=new double[t1.nFiles];
           
           double t1Own[t1.nFiles];
           for(int p=0; p<t1.nFiles; p++)
                  t1Own[p]=computeDist(t1.result, t1.imBounds[p], t1.imBounds[p+1], t1.result, t1.imBounds[p], t1.imBounds[p+1], 512);
           for(int i=0; i<nFiles; i++)
           {
                iFile>>temp;
                strcpy(str, "testing_set\\"); //Start classification
                strcat(str, temp);
                strcat(str, ".key");
                im.readKeyFile( str ) ;
                printf("nOfFeatures=%d. ", im.noOfFeatures);
                dataArr=cvCreateMat(im.noOfFeatures, 128, CV_64FC1 );
                for(int j=0; j<im.noOfFeatures; j++)
                        for(int k=0; k<128; k++)
                                     ((double*)(dataArr->data.ptr + dataArr->step*j ))[k] = (im.featArr[j])->featVect[k];
                result= cvCreateMat(dataArr->rows, N, CV_64FC1);
                cvProjectPCA(dataArr, t1.avg, t1.eigenvectors, result);
                
                double own=computeDist(result, 0, result->rows, result, 0, result->rows, 512);
                for(int p=0; p<t1.nFiles; p++) //NORMALIZED
                {
                       distance[p]=computeDist(result, 0, result->rows, t1.result, t1.imBounds[p], t1.imBounds[p+1], 512)/ sqrt ( own * t1Own[p] );
//                       printf("\nDistance with %d computed : %f, own: %f, t1 : %f, between: %f",p, distance[p], own, t1Own[p], computeDist(result, 0, result->rows, t1.result, t1.imBounds[p], t1.imBounds[p+1], 512) ) ;
                }


                double votes[4]; //Weightage for each of the classes //Classes of objects hard coded :(
                int nVotes[4];
                votes[0]=0.0; votes[1]=0.0; votes[2]=0.0; votes[3]=0.0;
                nVotes[0]=0; nVotes[1]=0; nVotes[2]=0; nVotes[3]=0;
                
                //Now find nearest k-neighbors
                for(int k=0; k<k_nearest; k++)
                {
                        double tempDist=0.0; //CHANGE HERE IF COMPUTEDIST RETURNS SIMILARITY
                        int index;
                        for(int j=0; j<t1.nFiles; j++)
                                if(distance[j]>tempDist) //CHANGE HERE IF COMPUTEDIST RETURNS SIMILARITY
                                     {index=j; tempDist=distance[j];}

                        printf("\nMaximum found with %d : %f", index, tempDist);
                        iFile2<<"\nMaximum found with "<<index<<" : "<<tempDist;
                        if(index<20) {votes[0]+=tempDist; nVotes[0]++;}   //Classes of objects hard coded :(
                        else if(index<40) {votes[1]+=tempDist; nVotes[1]++;}
                        else if(index<60) {votes[2]+=tempDist; nVotes[2]++;}
                        else if(index<80) {votes[3]+=tempDist; nVotes[3]++;}

                        distance[index]=0.0; //CHANGE HERE IF COMPUTEDIST RETURNS SIMILARITY
                }
                if(nVotes[0]!=0) votes[0]=(votes[0]*2)/sqrt(nVotes[0]);
                if(nVotes[1]!=0) votes[1]=(votes[1]*2)/sqrt(nVotes[1]);
                if(nVotes[2]!=0) votes[2]=(votes[2]*2)/sqrt(nVotes[2]);
                if(nVotes[3]!=0) votes[3]=(votes[3]*2)/sqrt(nVotes[3]);
                iFile2<<"\nImage "<<i<<": THIS IMAGE WAS FOUND TO BE A ";
                cout<<"\nImage "<<i<<": THIS IMAGE WAS FOUND TO BE A ";
                if(votes[0]>=votes[1] && votes[0]>=votes[2] && votes[0]>=votes[3] ) {iFile2<<"CAR "; cout<<"CAR";}
                if(votes[1]>=votes[0] && votes[1]>=votes[2] && votes[1]>=votes[3] ) {iFile2<<"FACE "; cout<<"FACE";}
                if(votes[2]>=votes[0] && votes[2]>=votes[1] && votes[2]>=votes[3] ) {iFile2<<"LAPTOP "; cout<<"LAPTOP";}
                if(votes[3]>=votes[0] && votes[3]>=votes[1] && votes[3]>=votes[2] ) {iFile2<<"MOTORBIKE "; cout<<"MOTORBIKE";}
                iFile2<<"\nVote1: "<<votes[0]<<" "<<"Vote2: "<<votes[1]<<" "<<"Vote3: "<<votes[2]<<" "<<"Vote4: "<<votes[3];
                cout<<"\nVote1: "<<votes[0]<<" "<<"Vote2: "<<votes[1]<<" "<<"Vote3: "<<votes[2]<<" "<<"Vote4: "<<votes[3];

           }

           cvDestroyWindow("Testing image");
           iFile.close();
           iFile2.close();
      }

      inline void concat(char *str, int i)
      {
//             printf("\nReceived str: %s AND i: %d", str, i);
             strcat(str, " ");
             if(i==0)
             {
                     strcat(str, "0");
                     return;
             }
             if(i<0)
             {
                    strcat(str, "-");
                    i*=-1;
             }
             char temps[10];
             temps[0]='\0';
             char c[2]; c[1]='\0';
             while(i>0)
             {
                  c[0]=48+(i%10);
                  strcat(temps, c);
                  i/=10;
             }
             for(int i=strlen(temps)-1; i>=0; i--)
             {
                     c[0]=temps[i];
                     strcat(str, c);
             }
      }

      double computeDist(CvMat *set1, int i1, int l1, CvMat *set2, int init, int last, int diameter)
      {
             //compute distance using PMK
//             printf("\nReceived set 1 %d to %d AND set 2 %d to %d", i1, l1, init, last);
             map<string,int> hashtable1;    //Courtesy: Mr. Li Zhang, USC
             map<string,int> hashtable2;
             
             double dist=0.0;
             
             int resol=1;

             char str[500]; int lastMatched=0, numMatches;
             while(resol<diameter)
             {
                   numMatches=0;
                   for(int i=i1; i<l1; i++)
                   {
                           strcpy(str, "");
                           for(int j=0; j<set1->cols; j++)
                           {
                                   concat(str, (int) (((double*)(set1->data.ptr + set1->step*i ))[j] / resol)  );
                           }
//                           printf("\nString at: %s", str); getch();
                           hashtable1[str]++;
                   }
                   for(int i=init; i<last; i++)
                   {
                           strcpy(str, "");
                           for(int j=0; j<set2->cols; j++)
                           {
                                   concat(str, (int) (((double*)(set2->data.ptr + set2->step*i ))[j] / resol)  );
                           }
//                           printf("\nString at: %s", str); getch();
                           hashtable2[str]++;
                   }
                   resol*=2;
                   map<string,int>::iterator hi;                               //Courtesy: Mr. Li Zhang, USC
                   for( hi = hashtable1.begin(); hi!=hashtable1.end(); ++ hi )
                   {
                        int a=hi->second, b;
                        if ( hashtable2.find(hi->first)==hashtable2.end() ) b=0;
                        else b=(hashtable2.find(hi->first))->second;
//                        printf("\na: %d AND b: %d", a, b); getch();
                        numMatches+= min(a,b);
                   }
                   dist+=((double)(numMatches-lastMatched))/resol;
//                   printf("\nResol: %d numMatches=%d. Dist=%f", resol, numMatches, dist); getch();
                   lastMatched=numMatches;
             }
             
             return dist;
      }


};

int main()
{
    trainer t1("training_set\\index.txt", 20);
    printf("\nTraining complete\n\n");
    
    tester(t1, "testing_set\\index.txt", 20, 20, 64);

}