//! To compile on GCC: g++ -std=gnu++0x tests.cpp

#include <vector>
#include <iomanip>
#include <iostream>
#include <cstring>

#include "inversions.hpp"

using namespace std;

ostream& operator<<(ostream& out, const std::vector<int>& v) {
    typedef std::vector<int>::const_iterator iterator;
    for (iterator it = v.begin(); it != v.end(); ++it) {
        out << *it << " ";
    }
    return out;
}

//! \bref Check both algorithms against a given instance.
//! \param instance The problem instance, an interger list.
//! \param expected_count The expected number of inversions.
void check(const std::vector<int>& instance, int expected_count) {

    int quad_count = inversions::quadratic(instance);
    int nlogn_count = inversions::nlogn(instance);

    if (quad_count != expected_count) {
        cout << "Expected " << expected_count << " but found "
            << quad_count << " inversions using quad algo on "
            << instance << endl;
    }

    if (nlogn_count != expected_count) {
        cout << "Expected " << expected_count << " but found "
            << nlogn_count << " inversions using nlogn algo on "
            << instance << endl;
    }
}

int main() {

    check(std::vector<int>({}), 0);
    check(std::vector<int>({2, 1}), 1);
    check(std::vector<int>({6, 2, 4, 1, 3, 5}), 8);
    check(std::vector<int>({8, 3, 2, 9, 7, 1, 5, 4}), 17);
    check(std::vector<int>({1, 2, 3}), 0);
    check(std::vector<int>({5, 4, 3, 2, 1, 0}), 15);
    check(std::vector<int>({1, 2, 3, 4, 4, 9, 3}), 3);
    check(std::vector<int>({0, 1, 2, 3, 2, 1, 0}), 9);

    return 0;
}