metavis/metavis/RunData.cpp

#include "pch.h"
#include "GraphView.h"
#include "RunData.h"
#include <QDebug>
#include <QString>
#include <regex>
#include <algorithm>


RunData::RunData()
{
}

RunData::RunData(std::string filePath) : fileStream(filePath), filePath(filePath)
{
    
    std::string file = filePath.substr(filePath.find_last_of("/\\") + 1);
    name = file.substr(0, file.rfind("."));
    if (!fileStream.is_open())
    {
        //Cant open file
        badFileFlag = true;
        return;
    }
    std::string buffer;
    getLine(buffer);
    qDebug() << QString::fromStdString(buffer);
    /*bool retflag;
    metalogFile(retflag);
    if (retflag) return;*/
    std::string integerRegexString = "([\\+\\-]?\\d+)";
    std::string doubleRegexString = "([\\+\\-]?\\d+(?:\\.\\d+(?:E[\\+\\-]\\d+)?)?)";
    std::string binaryRegexString = "([01]+)";
    std::string seperator = ",";
    std::regex regexLine(integerRegexString
        + seperator + integerRegexString
        + seperator + integerRegexString
        + seperator + doubleRegexString
        + seperator + binaryRegexString);
    while (fileStream.peek() != EOF) {
        std::string buffer;
        getLine(buffer);
        SolutionPointData sol;
        std::smatch match;
        if (!std::regex_search(buffer, match, regexLine)) {
            qDebug() << "Bad formatatted Line[" << actualLine << "].";
            qDebug() << "Failed to matched:";
            qDebug() << QString::fromStdString(buffer);
            return;
        }
        sol.round = std::stoi(match[1]);
        sol.iteration = std::stoi(match[2]);
        sol.particleNumber = std::stoi(match[3]);
        sol.objectiveFunction = std::stod(match[4]);
        sol.bitVec.resize(match[5].length());
        std::string binaryString = match[5];
        for (std::string::size_type i = 0; i < binaryString.size(); ++i) {
            sol.bitVec[i] = (binaryString[i] == '1');
        }
        solutionVec.push_back(sol);
    }
    fileStream.close();
    qDebug() << "Import done";
   


    //Set Runs apart
    int count = 0;
    std::vector<SolutionPointData>::iterator begin = solutionVec.begin();
    for (auto iter = solutionVec.begin(); iter != solutionVec.end(); iter++) {
        if (iter->round != begin->round) {
            std::string endString("[");
            endString += std::to_string(count++);
            endString += "]";
            singleRunList.push_back(SingleRun(name, begin, iter, name +  endString));
            begin = iter;
        }
    }
    std::string endString("[");
    endString += std::to_string(count);
    endString += "]";
    singleRunList.push_back(SingleRun(name, begin, solutionVec.end(), name + endString));



    //Generate PascalTriangle
    std::chrono::high_resolution_clock::time_point start = std::chrono::high_resolution_clock::now();

    int amountOfBits = begin->bitVec.size();
    int lines = amountOfBits + 1;
    std::vector<boost::multiprecision::cpp_int> pascalTriangleVec(((lines + 1) / 2 * (lines / 2 + 1)));
    for (int line = 0; line < lines; line++) {
        for (int number = 0; number < line + 1; number++) {
            if (number > line / 2) break;
            if (number == 0 || number == line) {
                pascalTriangleVec[binominalIndex(line, number)] = 1;
            }
            else {
                pascalTriangleVec[binominalIndex(line, number)] = pascalTriangleVec[binominalIndex(line - 1, number)] + pascalTriangleVec[binominalIndex(line - 1, number - 1)];
            }

        }
    }
    std::chrono::high_resolution_clock::time_point endPoint = std::chrono::high_resolution_clock::now();
    std::chrono::milliseconds time = std::chrono::duration_cast<std::chrono::milliseconds>(endPoint - start);
    qDebug() << "PascalTriangle: " << time.count() << "ms";
    //Calculate Additional Data
    for (SingleRun& srun : singleRunList) {
        srun.calculateAdditionalData(pascalTriangleVec, amountOfBits);
    }
    calculateAverageOverRuns();

}

void RunData::metalogFile(bool& retflag)
{
    retflag = true;
    /* Start extracting */
    while (fileStream.peek() != EOF) {
        std::string buffer;
        getLine(buffer);
        SolutionPointData sol;

        std::regex regexIter("i:([\\+\\-]?\\d+)");
        std::regex regexObjectiveFunction("of:([\\+\\-]?\\d+\\.\\d+(?:E[\\+\\-]\\d+)?)");
        std::smatch match;
        if (!std::regex_search(buffer, match, regexIter)) {
            qDebug() << "Bad formatatted Line[" << actualLine << "].";
            qDebug() << "Failed to matched:";
            qDebug() << QString::fromStdString(buffer);
            return;
        }
        sol.iteration = std::stoi(match[1]);
        if (!std::regex_search(buffer, match, regexObjectiveFunction)) {
            qDebug() << "Bad formatatted Line[" << actualLine << "].";
            qDebug() << "Failed to matched:";
            qDebug() << QString::fromStdString(buffer);
            return;
        }
        sol.objectiveFunction = std::stod(match[1]);
        std::regex regexParticleNumber("pN:([\\+\\-]?\\d+)");
        if (!std::regex_search(buffer, match, regexParticleNumber)) {
            qDebug() << "Bad formatatted Line[" << actualLine << "].";
            qDebug() << "Failed to matched:";
            qDebug() << QString::fromStdString(buffer);
            return;
        }
        sol.particleNumber = std::stoi(match[1]);
        std::regex regexBitVec("b:([01]+)");
        if (!std::regex_search(buffer, match, regexBitVec)) {
            qDebug() << "Bad formatatted Line[" << actualLine << "].";
            qDebug() << "Failed to matched:";
            qDebug() << QString::fromStdString(buffer);
            return;
        }
        sol.bitVec.resize(match[1].length());
        int count = 0;
        std::string str = match[1];
        for (std::string::size_type i = 0; i < str.size(); ++i) {
            sol.bitVec[i] = (str[i] == '1');
        }
        solutionVec.push_back(sol);
    }
    retflag = false;
}

void RunData::getLine(std::string& bufferString)
{
    std::getline(fileStream, bufferString);
    actualLine++;
}

void RunData::calculateAverageOverRuns()
{
    qDebug() << "calculateAverageOverRuns";

    {
        std::chrono::high_resolution_clock::time_point start = std::chrono::high_resolution_clock::now();
        int iter = singleRunList.begin()->bestMaxSolutionFoundPerIteration.size();
        double n = singleRunList.size();
        bestAverageMaxSolutionFoundPerIteration.resize(iter);
        for (int i = 0; i < iter; i++) {
            double average = std::accumulate(singleRunList.begin(), singleRunList.end(), 0.0, [i](double a, const SingleRun& b) -> double
                {return a + b.bestMaxSolutionFoundPerIteration[i].y; }) / n;
            bestAverageMaxSolutionFoundPerIteration[i] = GraphDataPoint((double)i, average);
        }
        std::chrono::high_resolution_clock::time_point endPoint = std::chrono::high_resolution_clock::now();
        std::chrono::milliseconds time = std::chrono::duration_cast<std::chrono::milliseconds>(endPoint - start);
        qDebug() << "Time" << time.count() << "ms";
    }

}

SingleRun::SingleRun(std::string uniqueName, const std::vector<SolutionPointData>::iterator begin, const std::vector<SolutionPointData>::iterator end, std::string name = "")
    :begin(begin), end(end), name(name), runDataName(uniqueName)
{

}

void SingleRun::calculateAdditionalData(std::vector<boost::multiprecision::cpp_int>& pascalTriangleVec, int amountOfBits)
{
    calculateBestAndAverageIter();
    calculateParticleSolution();
    calculateDotsForDistribution();
    calculateBitFieldData(pascalTriangleVec, amountOfBits);
    calculateMeanHammingDistance();
}

void SingleRun::calculateBestAndAverageIter()
{
    if (begin == end) {
        return;
    }
    double minObjectiveFunctionInIter = begin->objectiveFunction;
    double maxObjectiveFunctionInIter = begin->objectiveFunction;
    double bestMinObjectiveFunctionFound = begin->objectiveFunction;
    double bestMaxObjectiveFunctionFound = begin->objectiveFunction;
    double actualIterObjectiveFunctionAggregate = begin->objectiveFunction;
    int actualIter = begin->iteration;
    int foundSolutionInIteration = 1; 
    for (auto iter = begin; iter != end; iter++) {
        SolutionPointData& nextData = *iter;
        if (nextData.iteration != actualIter) {
            //save last
            bestMinSolutionFoundPerIteration.push_back(GraphDataPoint((double)actualIter, bestMinObjectiveFunctionFound));
            bestMaxSolutionFoundPerIteration.push_back(GraphDataPoint((double)actualIter, bestMaxObjectiveFunctionFound));
            averageSolutionPerItertion.push_back(GraphDataPoint((double)actualIter, actualIterObjectiveFunctionAggregate / (double)foundSolutionInIteration));
            minSolutionPerItertion.push_back(GraphDataPoint((double)actualIter, minObjectiveFunctionInIter));
            maxSolutionPerItertion.push_back(GraphDataPoint((double)actualIter, maxObjectiveFunctionInIter));
            //init new iteration
            actualIter = nextData.iteration;
            foundSolutionInIteration = 1;
            actualIterObjectiveFunctionAggregate = nextData.objectiveFunction;
            minObjectiveFunctionInIter = nextData.objectiveFunction;
            maxObjectiveFunctionInIter = nextData.objectiveFunction;
        }
        else {
            //increae aggregate
            foundSolutionInIteration++;
            actualIterObjectiveFunctionAggregate += nextData.objectiveFunction;
        }
        //update best min and max if better
        if (nextData.objectiveFunction < bestMinObjectiveFunctionFound) {
            bestMinObjectiveFunctionFound = nextData.objectiveFunction;
        }
        if (nextData.objectiveFunction > bestMaxObjectiveFunctionFound) {
            bestMaxObjectiveFunctionFound = nextData.objectiveFunction;
        }
        if (nextData.objectiveFunction < minObjectiveFunctionInIter) {
            minObjectiveFunctionInIter = nextData.objectiveFunction;
        }
        if (nextData.objectiveFunction > maxObjectiveFunctionInIter) {
            maxObjectiveFunctionInIter = nextData.objectiveFunction;
        }
    }
    //save last iteration
    bestMinSolutionFoundPerIteration.push_back(GraphDataPoint((double)actualIter, bestMinObjectiveFunctionFound));
    bestMaxSolutionFoundPerIteration.push_back(GraphDataPoint((double)actualIter, bestMaxObjectiveFunctionFound));
    averageSolutionPerItertion.push_back(GraphDataPoint((double)actualIter, actualIterObjectiveFunctionAggregate / (double)foundSolutionInIteration));
    minSolutionPerItertion.push_back(GraphDataPoint((double)actualIter, minObjectiveFunctionInIter));
    maxSolutionPerItertion.push_back(GraphDataPoint((double)actualIter, maxObjectiveFunctionInIter));
}

void SingleRun::calculateParticleSolution()
{
    for (auto iter = begin; iter != end; iter++) {
        GraphDataPoint point(iter->iteration, iter->objectiveFunction, &*iter);
        auto treeIter = particleMap.find(iter->particleNumber);
        if (treeIter == particleMap.end()) {
            //create new Entry
            std::vector<GraphDataPoint> vec;
            vec.push_back(point);
            particleMap.insert({ iter->particleNumber, vec});
        }
        else {
            //append to vector in Entry
            treeIter->second.push_back(point);
        }
    }
}

void SingleRun::calculateDotsForDistribution()
{
    for (std::vector<SolutionPointData>::iterator it = begin; it != end; ++it) {
        dotsForDistribution.push_back(GraphDataPoint((double)it->iteration, it->objectiveFunction, &*it));
    }
}

boost::multiprecision::cpp_int positionInPermutation2(std::vector<boost::multiprecision::cpp_int>& pascalTriangleVec, std::vector<bool>::iterator begin, std::vector<bool>::iterator end, int amountOfUnsetBits)
{
    //recursion base
    if (amountOfUnsetBits == 0) return 1;
    int amountOfBits = end - begin;
    std::vector<bool>::iterator indexIter = std::find(begin, end, false);
    int index = indexIter - begin;
    int amountOfBitsAfterIndex = (amountOfBits - 1) - index;
    //recursion base
    if (amountOfUnsetBits == 1) return (amountOfBits - 1) - index;
    //Step 1 the amount of permutations with the rest amountOfBitsAfterIndex 
    boost::multiprecision::cpp_int before = (amountOfUnsetBits <= amountOfBitsAfterIndex) ? pascalTriangleVec[RunData::binominalIndex(amountOfBitsAfterIndex, amountOfUnsetBits)] : 0;
    //Step 2 the actual position of the rest
    boost::multiprecision::cpp_int after = positionInPermutation2(pascalTriangleVec, ++indexIter, end, amountOfUnsetBits - 1);
    //Step 3 add Step 1 and Step 2
    return before + after;
}

void SingleRun::calculateBitFieldData(std::vector<boost::multiprecision::cpp_int>& pascalTriangleVec, int amountOfBits)
{
    
    std::chrono::high_resolution_clock::time_point start = std::chrono::high_resolution_clock::now();

    for (std::vector<SolutionPointData>::iterator it = begin; it != end; ++it) {
            int amountOfSetBits = std::count(it->bitVec.begin(), it->bitVec.end(), true);
            int amountOfUnsetBits = it->bitVec.size() - amountOfSetBits;
            boost::multiprecision::cpp_dec_float_100 position(positionInPermutation2(pascalTriangleVec, it->bitVec.begin(), it->bitVec.end(), amountOfUnsetBits));
            boost::multiprecision::cpp_dec_float_100 maxAmountOfPermutaions (pascalTriangleVec[RunData::binominalIndex(amountOfBits, amountOfSetBits)] - 1);

            dotsForBitField.push_back(GraphDataPoint((position / maxAmountOfPermutaions).convert_to<double>(), amountOfSetBits, &*it));
    }
   std::chrono::high_resolution_clock::time_point endPoint = std::chrono::high_resolution_clock::now();
   std::chrono::milliseconds time = std::chrono::duration_cast<std::chrono::milliseconds>(endPoint - start);
   qDebug() << "BitFieldBerechnung: " << time.count() << "ms";
}

void SingleRun::calculateMeanHammingDistance()
{
    std::chrono::high_resolution_clock::time_point start = std::chrono::high_resolution_clock::now();
    std::vector<SolutionPointData>::iterator iterBegin = begin;
    for (std::vector<SolutionPointData>::iterator iter = begin; iter != end; iter++) {
        if (iter->iteration != iterBegin->iteration) {
            double mean = RunData::meanHammingDistance(iterBegin, iter);
            meanHammingDistancePerIteration.push_back(GraphDataPoint(iterBegin->iteration, mean));
            iterBegin = iter;
        }
    }
    std::chrono::high_resolution_clock::time_point endPoint = std::chrono::high_resolution_clock::now();
    std::chrono::milliseconds time = std::chrono::duration_cast<std::chrono::milliseconds>(endPoint - start);
    qDebug() << "Mean: " << time.count() << "ms";
}


int RunData::binominalIndex(const int n, int k)
{
    if (k > n / 2) k = n - k;
    return ((n + 1) / 2) * (n / 2 + 1) + k;
}

int RunData::hammingdistance(std::vector<bool>& bitVecA, std::vector<bool>& bitVecB)
{
    //assert((bitVecA.size() == bitVecB.size()));
    int count = 0;
    auto iterB = bitVecB.begin();
    for (auto iterA = bitVecA.begin(); iterA != bitVecA.end(); iterA++) {
        if (*iterA != *iterB) {
            count++;
        }
        iterB++;
    }
    return count;
}

double RunData::meanHammingDistance(std::vector<SolutionPointData>::iterator begin, std::vector<SolutionPointData>::iterator end)
{
    if (std::distance(begin, end)  <= 1) {
        return 0.0;
    }
    std::vector<SolutionPointData>::iterator startParticle(begin);
    double hammingValuesAccumulated = 0.0;
    int count = 0;
    for (std::vector<SolutionPointData>::iterator iter = begin; iter != end; iter++) {
        for (std::vector<SolutionPointData>::iterator iterParticle = iter + 1; iterParticle != end; iterParticle++) {
            hammingValuesAccumulated += hammingdistance(iter->bitVec, iterParticle->bitVec);
            count++;
        }
    }
    return hammingValuesAccumulated / (double) count;
}

boost::multiprecision::cpp_int RunData::binominal(const int n,int k)
{
    boost::multiprecision::cpp_int value(1);
    if (k > n / 2) k = n - k;
    for (int i = 0; i < k; i++) {
        value *= boost::multiprecision::cpp_int(n - i);
        value /= boost::multiprecision::cpp_int(i + 1);
    }
    return value;
}

boost::multiprecision::cpp_int RunData::positionInPermutation(std::vector<bool>::iterator begin, std::vector<bool>::iterator end, int setBits)
{
    int amountOfBits = end - begin;
    //recursion base
    if (setBits == 0) return 1;
    std::vector<bool>::iterator indexIter = std::find(begin, end, true);//TODO:false könnte andersrum sortieren!
    int index = indexIter - begin;
    int bitsAfterIndex = (amountOfBits - 1) - index;
    //recursion base
    if (setBits == 1) return (amountOfBits - 1) - index;
    //Step 1 the amount of permutations with the rest amountOfBitsAfterIndex 
    boost::multiprecision::cpp_int before = binominal(bitsAfterIndex, setBits);
    //Step 2 teh actual position of the rest
    boost::multiprecision::cpp_int after = positionInPermutation(++indexIter, end, setBits - 1);
    //setp 3 add Step 1 and Step 2
    return before + after;
}

boost::multiprecision::cpp_int RunData::positionInPermutation_reversed(std::vector<bool>::iterator begin, std::vector<bool>::iterator end, int amountOfUnsetBits)
{
    qDebug() << "Method()";
    int amountOfBits = end - begin;
    //recursion base
    if (amountOfUnsetBits == 0) return 1;
    std::vector<bool>::iterator indexIter = std::find(begin, end, false);
    int index = indexIter - begin;
    qDebug() << "index: " << index;
    int bitsAfterIndex = (amountOfBits - 1) - index;
    //recursion base
    if (amountOfUnsetBits == 1) return (amountOfBits - 1) - index;
    //Step 1 the amount of permutations with the rest amountOfBitsAfterIndex 
    boost::multiprecision::cpp_int before = (amountOfUnsetBits <= bitsAfterIndex)? binominal(bitsAfterIndex, amountOfUnsetBits):0;
    qDebug() << "before: " << "binominal("<< bitsAfterIndex << "," << amountOfUnsetBits  << ")" << before.convert_to<int>();
    //Step 2 teh actual position of the rest
    boost::multiprecision::cpp_int after = positionInPermutation_reversed(++indexIter, end, amountOfUnsetBits - 1);
    qDebug() << "after: " << after.convert_to<int>();
    qDebug() << "return:" << before.convert_to<int>() << "+" << after.convert_to<int>();
    //setp 3 add Step 1 and Step 2
    return before + after;
}


GraphDataPoint::GraphDataPoint(double x, double y, SolutionPointData* orginalPoint) : x(x), y(y), orginalPoint(orginalPoint)
{

}

GraphDataPoint::GraphDataPoint(double x, double y, QColor color, SolutionPointData* orginalPoint)
    : x(x), y(y), orginalPoint(orginalPoint), color(color)
{
}

bool GraphDataPoint::existLink() const
{
    return orginalPoint != nullptr;
}

QPointF GraphDataPoint::toQPointF() const
{
    return QPointF(x, y);
}

double GraphDataPoint::squaredDistance(QPointF& graphPoint) const
{
    return std::pow(graphPoint.x() - x, 2) + std::pow(graphPoint.y() - y, 2);
}

std::string SolutionPointData::bitstringToStdString()
{
    std::string str(bitVec.size(), 0);
    std::transform(bitVec.begin(), bitVec.end(), str.begin(),
        [](bool b) -> char { return b ? '1' : '0'; });
    return str;
}