#include <iostream>
#include <iomanip>
#include <cstdlib>
#include "exp_sp.h"
#include "dgraph.h"
#include "dgraphp.h"
#include "dijkstra.h"
#include "timing.h"
/* Experiment Class for Measuring the Performance of Different Dijkstra's
 * Algorithm Implementations
 * ----------------------------------------------------------------------------
 * Author:  Shane Saunders
 */
using namespace std;
 
/*--- Functions -------------------------------------------------------------*/

/* --- printDistances() ---
 * Print the distance array d to the standard output.  Parameter n is the
 * size of the array.
 */
void SpExperiment::printDistances(long *d, int n)
{
    cout << "d =";
    for(int i = 0; i < n; i++) {
        cout << " " << d[i];
    }
    cout << "\n";
}

/* --- copyDistances() ---
 * Copy the distance array src to distance array dest.  Parameter n is
 * the size of the arrays.
 */
void SpExperiment::copyDistances(long *dest, long *src, int n)
{
    for(int i = 0; i < n; i++) {
        dest[i] = src[i];
    }
}

/* --- initSingleSourceDistances() ---
 * Fill the distance array d with initial distances for single-source.
 * This assigns infinity to all array entries except that of the source vertex,
 * vertex 0, which has an initial distance of zero.
 */
void SpExperiment::initSingleSourceDistances(long *d, int n)
{
    d[0] = 0;
    for(int i = 1; i < n; i++) {
        d[i] = INFINITE_DIST;
    }
}

/* --- verifyDistances() ---
 * Verify that the computed distances are the same in each of the arrays the
 * arrays distArrays[0], ... , distArrays[nArrays-1].  The parameter n
 * is the size of each of the arrays.
 */
void SpExperiment::verifyDistances(long *distArrays[], int nArrays, int n)
{
    long *d;

    long *d0 = distArrays[0];
    for(int i = 1; i < nArrays; i++) {
        d = distArrays[i];
        for(int j = 0; j < n; j++) {
            if(d[j] != d0[j]) {
                 cout << "error - incorrect distance in distArrays["
                      << i << "][" << j <<"]\n";
                 exit(1);
            }
        }
    }
}

void SpExperiment::run(
  DGraphProvider *graphP, SpAlgSpec *algSpecs, int nAlgs)
{
    cout << "Enter data for " << graphP->description() << ".\n";
    graphP->inputParameters();

    cout << " - number of samples: ";
    int nSamples;
    cin >> nSamples;

    /*
     * output result description
     */
    cout << "\nCPU time for Dijkstra's algorithm on " << graphP->description()
         << ".\n\n";

    const int labelWidth = 10;
    const int dataWidth = 8;
    cout << setw(labelWidth) << left << "Columns:&";
    cout << setw(dataWidth) << right << graphP->varLabel();
    for(int i = 0; i < nAlgs; i++) {
        cout << "&" << right << setw(dataWidth) << algSpecs[i].name;
    }
    cout << "\n";
    
    /*
     * run experiment
     */

    /* timing information */
    Timings totalTimings(nAlgs);
    
    /* experiment over the different graphs */
    graphP->initVar();
    while(!graphP->varLimitReached()) {
        int k = graphP->currentGraphSize();
    
        /* allocate distance arrays */
        long *initDists = new long[k];
        long *algDists[nAlgs];
        for(int i = 0; i < nAlgs; i++) algDists[i] = new long[k];

        /* reset timing object */
        totalTimings.reset();

        /* use several sample graphs of the current graph size */
        for(int i = 0; i < nSamples; i++) {

            /* construct graph */
            DGraph *g = graphP->generateGraph();
            initSingleSourceDistances(initDists, k);

            /* run each algorithm on the current graph */
            for(int algNo = 0; algNo < nAlgs; algNo++) {
                DijkstraDesc *algDesc = algSpecs[algNo].algDesc;

                /* run once to settle any caching */
                initSingleSourceDistances(algDists[algNo], k);
                Dijkstra *alg = algDesc->newInstance(k);
                alg->init(g);
                alg->run(algDists[algNo]);
                delete alg;  /* free the constructed algorithm */

                /* run at least 1/10th second worth of samples */
                ClockValue stopTime = readclock() + CLOCK_SECOND/10;
                do {
                    initSingleSourceDistances(algDists[algNo], k);
                    totalTimings.start();
                    Dijkstra *alg = algDesc->newInstance(k);
                    alg->init(g);
                    alg->run(algDists[algNo]);
                    delete alg;  /* free the constructed algorithm */
                    totalTimings.stop(algNo);
                } while(readclock() < stopTime);
            }

            /* verify that all algorithms compute the same distances */
            verifyDistances(algDists, nAlgs, k);
            
            /* delete the constructed graph */
            delete g;
        }

        /* free the allocated distance arrays */
        delete [] initDists;
        for(int i = 0; i < nAlgs; i++) delete [] algDists[i];

        /* print main algorithm time */
        const int outPrecision = 5;
        cout.flags(ios::fixed);
        cout.precision(outPrecision);
        const double varVal = graphP->varValue();       
        cout << "\n";
        cout << setw(labelWidth) << "total:&";
        cout << setw(dataWidth) << varVal;
        for(int i = 0; i < nAlgs; i++) {
            cout << "&" << setw(dataWidth)
                 << totalTimings.average(i) / CLOCK_SECOND;
        }
        cout << "\n";

        graphP->updateVar();
    }
}