#define _CRT_SECURE_NO_WARNINGS

// trim_timers.cpp : Defines the entry point for the console application.
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <utility>

#include "Timer.h"

using namespace std;

struct TrimTest;

struct TestSpec
{
    string name;
    string url;
    TrimTest * test;

    TestSpec(string n, string u, TrimTest * t)
        : name(n), url(u), test(t)
    {}
};

vector<TestSpec> all_tests;

void register_test(string name, string url, TrimTest * test)
{
    all_tests.push_back(TestSpec(name, url, test));
}

struct TrimTest
{
    TrimTest(string test_name, string url)
    {
        register_test(test_name, url, this);
    }

    virtual char* trim_right(char * str) =  0;
};

#define CONCAT(a, b) CONCAT2(a, b)
#define CONCAT2(a, b) a##b
#define TRIM_RIGHT(name, url)    TRIM_RIGHT_IMPL(name, url, CONCAT(test, __LINE__))

#define TRIM_RIGHT_IMPL(name, url, classname) \
struct classname : TrimTest { \
    classname() : TrimTest(name, url) {} \
    char * trim_right(char * str); \
}; \
    classname CONCAT(classname, _obj); \
    char * classname::trim_right(char * str)


TRIM_RIGHT("article", "http://thedailywtf.com/Comments/Recursive-Whitespace-Removal.aspx")
{
    int len = strlen(str) - 1;
    if(len == 0 || str[len] != ' ') return str;
    str[strlen(str)-1] = '\0';
    return trim_right(str);
}


TRIM_RIGHT("gallier2", "http://thedailywtf.com/Comments/Recursive-Whitespace-Removal.aspx#397535")
{
    size_t l = strlen(str);
    while(l && str[--l] == ' ')
        str[l] = 0;
    return str;
}


char *trim_right_r_impl_Aufgehaben(char *str,int len)
{
    if(len == 0 || str[len] != ' ') return str;
    str[len] = '\0';
    return trim_right_r_impl_Aufgehaben(str,len-1);
}

TRIM_RIGHT("Aufgehaben", "http://thedailywtf.com/Comments/Recursive-Whitespace-Removal.aspx#397539")
{
    int len = strlen(str);
    return trim_right_r_impl_Aufgehaben(str,len-1);
}


TRIM_RIGHT("Xarthaneon the Unclear", "http://thedailywtf.com/Comments/Recursive-Whitespace-Removal.aspx#397558")
{
    for(int i = strlen(str) - 1; i >= 0; i--)
        if(str[i] == ' ')
            str[i] = '\0';
    return str;
}


TRIM_RIGHT("PleegWat", "http://thedailywtf.com/Comments/Recursive-Whitespace-Removal.aspx?pg=2#397572")
{
    char * p = NULL;
    while( *str )
    {
        if( p && !isspace(*str) )
            p = NULL;
        if( !p && isspace(*str) )
            p = str;
        str++; // added
    }

    if( p ) *p = '\0';
    return str;
}


TRIM_RIGHT("I DUNNO LOL", "http://thedailywtf.com/Comments/Recursive-Whitespace-Removal.aspx?pg=2#397623")
{
    char * start = str; // added
    char *end = str;
    while (*str) {
        if (*str++ != ' ') {
            end = str;
        }
    }
    *end = 0;
    return start; // added
}


TRIM_RIGHT("LK 1", "http://thedailywtf.com/Comments/Recursive-Whitespace-Removal.aspx?pg=3#397636")
{
    char *stop = NULL ;
    char *cursor = str ;
    char current = *cursor ;
    while (current != '\0') {
        int printable = (current > ' ') ;
        if (printable) { if (stop) stop=NULL ; }
        else if (!stop) { stop=cursor ; }
        cursor++ ;
        current = *cursor ;
    }
    if (stop) *stop = '\0' ;
    return str;
}


#define PRINTABLE(x) (x > ' ')
TRIM_RIGHT("LK 2", "http://thedailywtf.com/Comments/Recursive-Whitespace-Removal.aspx?pg=3#397636")
{
    char *stop = NULL ;
    char *cursor = str ;
    char current ;
    goto First;
NextUnstopped:
    cursor++ ;
First:
    current = *cursor ;
    if (current == '\0') goto End;
    if PRINTABLE(current) goto NextUnstopped;
    stop = cursor ;
FoundMoreWhitespace:
    cursor++ ;
    current = *cursor ;
    if (current == '\0') goto End;
    if (!PRINTABLE(current)) goto FoundMoreWhitespace ;
    stop = NULL ;
    goto NextUnstopped ;
End:
    if (stop) *stop = '\0' ;
    return str;
}
#undef PRINTABLE


TRIM_RIGHT("Scott", "http://thedailywtf.com/Comments/Recursive-Whitespace-Removal.aspx?pg=3#397641")
{
    int i = 0, j = 0;
    while ( str[i] != '\0' )
    {
        if ( str[i] != ' ' )
        {
            j = i;
        }
        ++i;
    }
    str[j + 1] = '\0';
    return str;
}


TRIM_RIGHT("Brendan", "http://thedailywtf.com/Comments/Recursive-Whitespace-Removal.aspx?rnd=344357517&pg=L#397673")
{
    char * start = str; // added
    char *stop;
next:
    while(!isspace(*str)) {
        if(*str == '\0') return start; // modified
        str++;
    }
    stop = str;
    do {
        str++;
        if(*str == '\0') {
            *stop = '\0';
            return start; // modified
        }
    } while(isspace(*str));
    goto next;
}


// I'll use this type for two things: for correctness tests, it will hold pairs of <input, expected answer>.
// For performance tests, it will hold pairs of <input, short description>.
typedef pair<string, string> StringPair;

StringPair correctness_tests[] = {
    StringPair("", ""),
    StringPair(" ", ""),
    StringPair("   ", ""),
    StringPair("  a", "  a"),
    StringPair("a ", "a"),
    StringPair("a   ", "a"),
    StringPair("a b c", "a b c"),
    StringPair("a b ", "a b")
};

const int thousand = 1000;
int lengths[] = { 1 * thousand, 10 * thousand, 100 * thousand, 500 * thousand };

string repeat(string base, int num)
{
    stringstream ss;
    for (int i=0; i<num; ++i) {
        ss << base;
    }
    return ss.str();
}

string exp_description(string base, int exp)
{
    stringstream ss;
    ss << base << "<sup>" << exp << "</sup>";
    return ss.str();
}

StringPair repeated_test(string base, int exp)
{
    return StringPair(repeat(base, exp), exp_description(base, exp));
}

StringPair make_englishy_test(int length)
{
    return repeated_test("aaaa ", length / 5);
}

StringPair make_all_spaces_test(int length)
{
    return repeated_test(" ", length);
}

StringPair make_alternating_test(int length)
{
    return repeated_test("a ", length / 2);
}

StringPair make_no_spaces_test(int length)
{
    return repeated_test("a", length);
}

StringPair make_spaces_then_non_space(int length)
{
    StringPair spaces = make_all_spaces_test(length - 1);
    return StringPair(spaces.first + "a", spaces.second + "a");
}

StringPair make_one_final_space(int length)
{
    StringPair spaces = make_no_spaces_test(length - 1);
    return StringPair(spaces.first + " ", spaces.second + " ");
}

StringPair make_five_final_space(int length)
{
    StringPair spaces = make_no_spaces_test(length - 5);
    return StringPair(spaces.first + "     ", spaces.second + " <sup>5</sup>");
}

typedef StringPair (*PerformanceTestMaker)(int);
PerformanceTestMaker performance_test_makers[] = {
    make_englishy_test,
    make_all_spaces_test,
    make_alternating_test,
    make_no_spaces_test,
    make_spaces_then_non_space,
    make_one_final_space,
    make_five_final_space
};

void do_correctness_test(TestSpec const & spec)
{
    std::cout << "    { \"name\": \"" << spec.name << "\", \"url\": \"" << spec.url << "\", \"results\": {";
    for (auto test: correctness_tests) {
        char * copy = new char[test.first.size() + 9];
        copy += 8;
        copy[-1] = ' ';
        strcpy(copy, test.first.c_str());
        string actual = spec.test->trim_right(copy);
        if (copy[-1] != ' ') {
            std::cout << "\"" << test.first << "\": \"<underflow>\", ";
        }
        else if (actual == test.second) {
            std::cout << "\"" << test.first << "\": \"<OK>\", ";
        }
        else {
            std::cout << "\"" << test.first << "\": \"" << actual << "\", ";
        }
    }
    std::cout << "\"dummy\":\"dummy\"}},\n";
}

void do_correctness_tests()
{
    std::cout << "{\"correctness\": [\n";
    for (auto implementation: all_tests) {
        do_correctness_test(implementation);
    }
    std::cout << "    {}],\n";
}


void do_timing_test(TestSpec const & spec)
{
    Timer timer;
    std::cout << "    { \"name\": \"" << spec.name << "\", \"url\": \"" << spec.url << "\", \"results\": {";
    for (auto test_maker : performance_test_makers) {
        for (int length : lengths) {
            StringPair this_test = test_maker(length);
            char * input = strdup(this_test.first.c_str());
            timer.start();
            spec.test->trim_right(input);
            timer.stop();
            std::cout << "\"" << this_test.second << "\": " << timer.getElapsedTimeInSec() << ", ";
        }
    }
    std::cout << "\"dummy\":\"dummy\"}},\n";
}


void do_timing_tests()
{
    std::cout << "\"timing\": [\n";
    for (auto implementation: all_tests) {
        do_timing_test(implementation);
    }
    std::cout << "{}]}\n";
}

int main()
{
    do_correctness_tests();
    do_timing_tests();
    return 0;
}