#include <sys/time.h>
#include <sys/resource.h>

#include "Library.h"

// LCS Implementations
#include "Naive.h"
#include "Memo.h"
#include "Dynamic.h"
#include "LinearSpace.h"

// Test Data
Pair<const char *, const char *>
    my_pair_1 =  {
        "hello lcs are you ok ?",
        "hello lcs! how are you today?"
    },
    my_pair_2 = {
        "hello lcs algorithm are you ok today? i'm doing pretty well myself",
        "hello LCS algorithm how are you today? i am doing pretty bad myself"
    };

extern Pair<const char *,const char *>
    test_pair_20, test_pair_100, test_pair_500, 
    test_pair_1000, test_pair_5000, 
    test_pair_10000, test_pair_20000, test_pair_40000,
    test_binary_pair_20, test_binary_pair_100, test_binary_pair_500, 
    test_binary_pair_1000, test_binary_pair_5000, 
    test_binary_pair_10000, test_binary_pair_20000, test_binary_pair_40000;

Pair<const char *, const char *> *examples[] = {
    &my_pair_1, &my_pair_2,
    &test_pair_20, &test_binary_pair_20,
    &test_pair_100, &test_binary_pair_100,
    &test_pair_500, &test_binary_pair_500,
    &test_pair_1000, &test_binary_pair_1000,
    &test_pair_5000, &test_binary_pair_5000,
    &test_pair_10000, &test_binary_pair_10000,
    &test_pair_20000, &test_binary_pair_20000,
    &test_pair_40000, &test_binary_pair_40000
};

static struct {
    Pair<List<char>*,int> (*f)(const char *a, int alen, const char *b, int blen);
    const char *name;
    bool linear_space;
} algorithms[] = {
    { naive_lcs<char,eq>, "naive_lcs", false },
    { memo_lcs<char,eq>, "memo_lcs", false },
    { dynamic_lcs<char,eq>, "dynamic_lcs", false },
    { linear_space_lcs<char,eq>, "linear_space_lcs", true }
};

// Test function
int main(int argc, char **argv) {
    Pair<List<char>*,int> ret;
    unsigned int i,j;
    struct timeval start,end;
    struct rusage rusage_start, rusage_end;
    unsigned long wall_diff,user_diff,sys_diff;
    int alen, blen;
    const char *a;
    bool quick = argc > 1 && strcmp(argv[1],"quick")==0;
    bool veryquick = argc > 1 && strcmp(argv[1],"veryquick")==0;
    bool skip[sizeof(examples)/sizeof(examples[0])] = { false };
    List<char> *firstResult;
    int reqExample;
    const char *reqAlg;
    int reqLength;
    reqAlg = (argc > 1 && !quick && !veryquick)  ? argv[1] : NULL;
    reqExample = argc > 2 ? strtol(argv[2],NULL,10) : -1;
    reqLength = argc > 3 ? strtol(argv[3],NULL,10) : -1;
    for(i=0;i<sizeof(examples)/sizeof(examples[0]);i++) {
        if(reqExample != -1 && (int)i != reqExample) continue;
        a = examples[i]->a;
        alen = strlen(examples[i]->a);
        blen = strlen(examples[i]->b);
        if(reqLength != -1) {
            alen = alen > reqLength ? reqLength : alen;
            blen = blen > reqLength ? reqLength : blen;
        }
        firstResult = 0;
        printf("Running example: %d (%d/%d, %s)\n",i,alen,blen,a[0]=='0'||a[0]=='1'?"{0,1}":"{A,C,G,T}");
        for(j=0;j<sizeof(algorithms)/sizeof(algorithms[0]);j++) {
            if(reqAlg && strcmp(algorithms[j].name,reqAlg)!=0) continue;
            if(skip[j]) continue;
            if(!algorithms[j].linear_space) {
                if(quick && (alen > 1500 || blen > 1500)) continue;
                if(alen > 15000 || blen > 15000) {
                    printf("WARNING: skipping %s because input is too large\n", algorithms[j].name);
                    continue;
                }
            }
            printf("Runing algorithm: %s\n",algorithms[j].name);
            
            getrusage(RUSAGE_SELF,&rusage_start);
            gettimeofday(&start,NULL);
            ret = algorithms[j].f(examples[i]->a,alen,examples[i]->b,blen);
            gettimeofday(&end,NULL);
            getrusage(RUSAGE_SELF,&rusage_end);
            
            wall_diff = timeval_diff_ms(end,start);
            user_diff = timeval_diff_ms(rusage_end.ru_utime,rusage_start.ru_utime);
            sys_diff  = timeval_diff_ms(rusage_end.ru_stime,rusage_start.ru_stime);

            printf("LCS Length: %d\n",ret.b);
            printf("LCS String: ");
            put(take(72,ret.a));
            printf("Wallclock Time (ms): %li\n",wall_diff);
            printf("CPU Time (ms): %li\n",user_diff+sys_diff);
            printf("User Time (ms): %li\n", user_diff);
            printf("System Time (ms): %li\n", sys_diff);
            //printf("Cons cell count: %d\n",consCount); consCount=0;
            if(wall_diff > (unsigned long) 10*alen) {
                printf("WARNING: %s is too slow, not running again\n",algorithms[j].name);
                skip[j] = true;
            }
            if(firstResult) {
                if(!eq(ret.a,firstResult)) {
                    fprintf(stderr,"ERROR: Different algorithms returned different results\n");
                    exit(1);
                }
            } else {
                firstResult = ret.a;
            }
            printf("===================================\n");
        }
        printf("\n");
        if(veryquick) break;
    }
    return 0;
}