main.cpp

#include <iostream>
#include <iomanip>
#include <vector>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <string>
#include <fstream>
#include <sstream>
#include <filesystem>
#include <omp.h>

#include "Config.h"
#include "DataGenerator.h"
#include "PatternMatcher.h"
#include "DistanceMetrics.h"

namespace fs = std::filesystem;

struct BenchmarkStats {
    std::string config_name;
    int num_threads = 1;
    double wall_mean = 0, wall_std = 0, wall_min = 0, wall_max = 0, wall_median = 0;
    double cpu_mean = 0, speedup = 0, efficiency = 0;
};

struct TestResult {
    std::string name;
    std::vector<BenchmarkStats> stats;
};

std::vector<TestResult> g_results;
std::string g_output_dir;
std::ofstream g_log;

std::string getTimestamp() {
    auto now = std::chrono::system_clock::now();
    auto t = std::chrono::system_clock::to_time_t(now);
    std::stringstream ss;
    ss << std::put_time(std::localtime(&t), "%Y%m%d_%H%M%S");
    return ss.str();
}

void createOutputDir() {
    std::string base = "output";
    if (!fs::exists(base)) fs::create_directory(base);
    g_output_dir = base + "/run_" + getTimestamp();
    fs::create_directory(g_output_dir);
}

void log(const std::string& msg) {
    std::cout << msg << std::flush;
    if (g_log.is_open()) g_log << msg << std::flush;
}

// Remove outliers using IQR method, keeping at least 70% of values
void removeOutliers(std::vector<double>& times, std::vector<double>& cpu) {
    if (times.size() < 4) return; // Need at least 4 values for IQR

    std::vector<size_t> indices(times.size());
    std::iota(indices.begin(), indices.end(), 0);
    std::sort(indices.begin(), indices.end(), [&](size_t a, size_t b) {
        return times[a] < times[b];
    });

    size_t n = times.size();
    size_t q1_idx = n / 4;
    size_t q3_idx = (3 * n) / 4;
    double q1 = times[indices[q1_idx]];
    double q3 = times[indices[q3_idx]];
    double iqr = q3 - q1;

    double lower = q1 - 1.5 * iqr;
    double upper = q3 + 1.5 * iqr;

    std::vector<double> filtered_times, filtered_cpu;
    size_t max_remove = static_cast<size_t>(n * 0.3); // Max 30% removal
    size_t removed = 0;

    for (size_t i = 0; i < n; ++i) {
        double t = times[i];
        if (t >= lower && t <= upper) {
            filtered_times.push_back(t);
            filtered_cpu.push_back(cpu[i]);
        } else if (removed < max_remove) {
            removed++;
            // Value is outlier, skip it
        } else {
            // Already removed max, keep this value
            filtered_times.push_back(t);
            filtered_cpu.push_back(cpu[i]);
        }
    }

    if (filtered_times.size() >= 3) {
        times = std::move(filtered_times);
        cpu = std::move(filtered_cpu);
    }
}

BenchmarkStats computeStats(std::vector<double>& times, std::vector<double>& cpu, int threads, double baseline) {
    BenchmarkStats s;
    s.num_threads = threads;

    // Remove outliers before computing stats
    removeOutliers(times, cpu);

    std::sort(times.begin(), times.end());

    s.wall_min = times.front();
    s.wall_max = times.back();
    s.wall_median = times[times.size() / 2];
    s.wall_mean = std::accumulate(times.begin(), times.end(), 0.0) / times.size();

    double sq = 0;
    for (double t : times) sq += (t - s.wall_mean) * (t - s.wall_mean);
    s.wall_std = std::sqrt(sq / times.size());

    s.cpu_mean = std::accumulate(cpu.begin(), cpu.end(), 0.0) / cpu.size();
    s.speedup = baseline > 0 ? baseline / s.wall_mean : 1.0;
    s.efficiency = (s.speedup / threads) * 100.0;

    return s;
}

std::string schedStr(Config::ScheduleType t) {
    switch(t) {
        case Config::ScheduleType::STATIC: return "STATIC";
        case Config::ScheduleType::STATIC_CHUNKED: return "STATIC_CHUNK";
        case Config::ScheduleType::DYNAMIC: return "DYNAMIC";
        case Config::ScheduleType::GUIDED: return "GUIDED";
        case Config::ScheduleType::AUTO: return "AUTO";
        default: return "?";
    }
}

std::string distStr(DistanceMetrics::DistanceType t) {
    switch(t) {
        case DistanceMetrics::DistanceType::SAD_BASIC: return "SAD_BASIC";
        case DistanceMetrics::DistanceType::SAD_EARLY_TERMINATION: return "SAD_EARLY";
        case DistanceMetrics::DistanceType::SAD_SIMD: return "SAD_SIMD";
        default: return "?";
    }
}

// ============================================================================
// Benchmark Core
// ============================================================================

template<typename DB>
BenchmarkStats runBenchmark(const DB& db, const std::vector<double>& pattern,
                            int threads, Config::ScheduleType sched, size_t chunk,
                            DistanceMetrics::DistanceType dist, double baseline,
                            const std::string& label = "") {
    std::vector<double> wall, cpu;

    // Warmup
    for (int i = 0; i < Config::NUM_WARMUP_RUNS; ++i) {
        log("\r  [" + label + "] Warmup " + std::to_string(i+1) + "/" + std::to_string(Config::NUM_WARMUP_RUNS) + "   ");
        for (size_t s = 0; s < db.num_series(); ++s)
            PatternMatcher::findPattern(db.get_series(s), db.get_length(s),
                pattern.data(), pattern.size(), threads, sched, chunk, dist);
    }

    // Measure
    for (int i = 0; i < Config::NUM_MEASUREMENT_RUNS; ++i) {
        log("\r  [" + label + "] Measure " + std::to_string(i+1) + "/" + std::to_string(Config::NUM_MEASUREMENT_RUNS) + "   ");
        double t0 = omp_get_wtime();
        auto c0 = std::clock();

        for (size_t s = 0; s < db.num_series(); ++s)
            PatternMatcher::findPattern(db.get_series(s), db.get_length(s),
                pattern.data(), pattern.size(), threads, sched, chunk, dist);

        wall.push_back(omp_get_wtime() - t0);
        cpu.push_back(static_cast<double>(std::clock() - c0) / CLOCKS_PER_SEC);
    }
    log("\r  [" + label + "] Done.                    \n");

    return computeStats(wall, cpu, threads, baseline);
}

// ============================================================================
// Tests
// ============================================================================

TestResult testMemoryLayout(const DatabaseAoS& aos, const DatabaseSoA& soa,
                            const std::vector<double>& pattern, const std::vector<int>& threads) {
    TestResult r; r.name = "Memory_Layout_AoS_vs_SoA";
    auto dist = DistanceMetrics::DistanceType::SAD_BASIC;
    auto sched = Config::ScheduleType::STATIC;

    auto base_aos = runBenchmark(aos, pattern, 1, sched, 0, dist, 0, "AoS_base");
    auto base_soa = runBenchmark(soa, pattern, 1, sched, 0, dist, 0, "SoA_base");

    for (int t : threads) {
        std::string label_aos = "AoS_" + std::to_string(t) + "T";
        auto s = runBenchmark(aos, pattern, t, sched, 0, dist, base_aos.wall_mean, label_aos);
        s.config_name = label_aos;
        r.stats.push_back(s);

        std::string label_soa = "SoA_" + std::to_string(t) + "T";
        s = runBenchmark(soa, pattern, t, sched, 0, dist, base_soa.wall_mean, label_soa);
        s.config_name = label_soa;
        r.stats.push_back(s);
    }
    return r;
}

TestResult testDistanceMetrics(const DatabaseAoS& db, const std::vector<double>& pattern,
                               const std::vector<int>& threads) {
    TestResult r; r.name = "Distance_Metrics";
    std::vector<DistanceMetrics::DistanceType> dists = Config::getDistanceTypes();

    for (auto d : dists) {
        std::string dname = distStr(d);
        auto base = runBenchmark(db, pattern, 1, Config::ScheduleType::STATIC, 0, d, 0, dname + "_base");
        for (int t : threads) {
            std::string label = dname + "_" + std::to_string(t) + "T";
            auto s = runBenchmark(db, pattern, t, Config::ScheduleType::STATIC, 0, d, base.wall_mean, label);
            s.config_name = label;
            r.stats.push_back(s);
        }
    }
    return r;
}

TestResult testScheduling(const DatabaseAoS& db, const std::vector<double>& pattern,
                          const std::vector<int>& threads) {
    TestResult r; r.name = "Scheduling_Strategies";
    auto dist = DistanceMetrics::DistanceType::SAD_BASIC;
    auto base = runBenchmark(db, pattern, 1, Config::ScheduleType::STATIC, 0, dist, 0, "Sched_base");

    for (auto sched : Config::getSchedulingStrategies()) {
        for (int t : threads) {
            size_t chunk = (sched == Config::ScheduleType::STATIC_CHUNKED) ? 256 : 0;
            std::string label = schedStr(sched) + "_" + std::to_string(t) + "T";
            auto s = runBenchmark(db, pattern, t, sched, chunk, dist, base.wall_mean, label);
            s.config_name = label;
            r.stats.push_back(s);
        }
    }
    return r;
}

TestResult testChunkSize(const DatabaseAoS& db, const std::vector<double>& pattern,
                         const std::vector<int>& threads) {
    TestResult r; r.name = "Chunk_Sizes";
    auto dist = DistanceMetrics::DistanceType::SAD_BASIC;
    auto sched = Config::ScheduleType::STATIC_CHUNKED;
    auto base = runBenchmark(db, pattern, 1, Config::ScheduleType::STATIC, 0, dist, 0, "Chunk_base");

    for (size_t chunk : Config::getChunkSizes()) {
        for (int t : threads) {
            std::string label = "Chunk" + std::to_string(chunk) + "_" + std::to_string(t) + "T";
            auto s = runBenchmark(db, pattern, t, sched, chunk, dist, base.wall_mean, label);
            s.config_name = label;
            r.stats.push_back(s);
        }
    }
    return r;
}

TestResult testStrongScaling(const DatabaseAoS& db, const std::vector<double>& pattern,
                             const std::vector<int>& threads) {
    TestResult r; r.name = "Strong_Scaling";
    auto dist = DistanceMetrics::DistanceType::SAD_BASIC;
    auto sched = Config::ScheduleType::STATIC;
    auto base = runBenchmark(db, pattern, 1, sched, 0, dist, 0, "Scale_base");

    for (int t : threads) {
        std::string label = std::to_string(t) + "_threads";
        auto s = runBenchmark(db, pattern, t, sched, 0, dist, base.wall_mean, label);
        s.config_name = label;
        r.stats.push_back(s);
    }
    return r;
}

// ============================================================================
// Parallelism Strategy Comparison: Internal vs External
// ============================================================================

// Benchmark for parallel across series (external parallelism)
template<typename DB>
BenchmarkStats runBenchmarkParallelSeries(const DB& db, const std::vector<double>& pattern,
                                          int threads, Config::ScheduleType sched,
                                          DistanceMetrics::DistanceType dist, double baseline,
                                          const std::string& label = "") {
    std::vector<double> wall, cpu;

    // Warmup
    for (int i = 0; i < Config::NUM_WARMUP_RUNS; ++i) {
        log("\r  [" + label + "] Warmup " + std::to_string(i+1) + "/" + std::to_string(Config::NUM_WARMUP_RUNS) + "   ");
        PatternMatcher::findPatternInDatabaseParallelSeries(
            db, pattern.data(), pattern.size(), threads, sched, dist);
    }

    // Measure
    for (int i = 0; i < Config::NUM_MEASUREMENT_RUNS; ++i) {
        log("\r  [" + label + "] Measure " + std::to_string(i+1) + "/" + std::to_string(Config::NUM_MEASUREMENT_RUNS) + "   ");
        double t0 = omp_get_wtime();
        auto c0 = std::clock();

        PatternMatcher::findPatternInDatabaseParallelSeries(
            db, pattern.data(), pattern.size(), threads, sched, dist);

        wall.push_back(omp_get_wtime() - t0);
        cpu.push_back(static_cast<double>(std::clock() - c0) / CLOCKS_PER_SEC);
    }
    log("\r  [" + label + "] Done.                    \n");

    return computeStats(wall, cpu, threads, baseline);
}

// Benchmark for sequential database search (baseline)
template<typename DB>
BenchmarkStats runBenchmarkSequentialDB(const DB& db, const std::vector<double>& pattern,
                                         DistanceMetrics::DistanceType dist,
                                         const std::string& label = "") {
    std::vector<double> wall, cpu;

    // Warmup
    for (int i = 0; i < Config::NUM_WARMUP_RUNS; ++i) {
        log("\r  [" + label + "] Warmup " + std::to_string(i+1) + "/" + std::to_string(Config::NUM_WARMUP_RUNS) + "   ");
        PatternMatcher::findPatternInDatabaseSequential(
            db, pattern.data(), pattern.size(), dist);
    }

    // Measure
    for (int i = 0; i < Config::NUM_MEASUREMENT_RUNS; ++i) {
        log("\r  [" + label + "] Measure " + std::to_string(i+1) + "/" + std::to_string(Config::NUM_MEASUREMENT_RUNS) + "   ");
        double t0 = omp_get_wtime();
        auto c0 = std::clock();

        PatternMatcher::findPatternInDatabaseSequential(
            db, pattern.data(), pattern.size(), dist);

        wall.push_back(omp_get_wtime() - t0);
        cpu.push_back(static_cast<double>(std::clock() - c0) / CLOCKS_PER_SEC);
    }
    log("\r  [" + label + "] Done.                    \n");

    return computeStats(wall, cpu, 1, 0);
}

TestResult testParallelismStrategy(const DatabaseAoS& db, const std::vector<double>& pattern,
                                   const std::vector<int>& threads) {
    TestResult r; r.name = "Parallelism_Strategy";
    auto dist = DistanceMetrics::DistanceType::SAD_BASIC;
    auto sched = Config::ScheduleType::STATIC;

    // Baseline: fully sequential
    auto base = runBenchmarkSequentialDB(db, pattern, dist, "Sequential");
    base.config_name = "Sequential";
    base.speedup = 1.0;
    base.efficiency = 100.0;
    r.stats.push_back(base);

    double baseline_time = base.wall_mean;

    for (int t : threads) {
        if (t == 1) continue; // Skip 1 thread, already have sequential

        // Internal parallelism (parallel sliding window, sequential over series)
        std::string label_int = "Internal_" + std::to_string(t) + "T";
        auto s_internal = runBenchmark(db, pattern, t, sched, 0, dist, baseline_time, label_int);
        s_internal.config_name = label_int;
        r.stats.push_back(s_internal);

        // External parallelism (parallel over series, sequential sliding window)
        std::string label_ext = "External_" + std::to_string(t) + "T";
        auto s_external = runBenchmarkParallelSeries(db, pattern, t, sched, dist, baseline_time, label_ext);
        s_external.config_name = label_ext;
        r.stats.push_back(s_external);
    }

    return r;
}

// ============================================================================
// Output
// ============================================================================

void saveResultsCSV(const TestResult& test) {
    std::string path = g_output_dir + "/" + test.name + ".csv";
    std::ofstream f(path);
    f << "config,threads,mean_ms,std_ms,min_ms,max_ms,median_ms,cpu_ms,speedup,efficiency\n";
    for (const auto& s : test.stats) {
        f << s.config_name << "," << s.num_threads << ","
          << s.wall_mean*1000 << "," << s.wall_std*1000 << ","
          << s.wall_min*1000 << "," << s.wall_max*1000 << ","
          << s.wall_median*1000 << "," << s.cpu_mean*1000 << ","
          << s.speedup << "," << s.efficiency << "\n";
    }
    f.close();
}

void printResults(const TestResult& test) {
    std::stringstream ss;
    ss << "\n=== " << test.name << " ===\n";
    ss << std::left << std::setw(22) << "Config" << std::right
       << std::setw(6) << "T" << std::setw(10) << "Mean(ms)"
       << std::setw(8) << "Std" << std::setw(10) << "Speedup"
       << std::setw(8) << "Eff%\n";
    ss << std::string(64, '-') << "\n";

    for (const auto& s : test.stats) {
        ss << std::left << std::setw(22) << s.config_name << std::right
           << std::setw(6) << s.num_threads
           << std::setw(10) << std::fixed << std::setprecision(2) << s.wall_mean*1000
           << std::setw(8) << s.wall_std*1000
           << std::setw(10) << s.speedup
           << std::setw(8) << std::setprecision(1) << s.efficiency << "\n";
    }
    log(ss.str());
}

void saveSystemInfo(size_t num_series, size_t series_len, size_t pattern_len) {
    std::string path = g_output_dir + "/system_info.txt";
    std::ofstream f(path);

    f << "=== System Configuration ===\n\n";
    f << "OpenMP max threads: " << omp_get_max_threads() << "\n";
    f << "OpenMP processors: " << omp_get_num_procs() << "\n";

    // CPU info
    std::ifstream cpu("/proc/cpuinfo");
    if (cpu.is_open()) {
        std::string line;
        while (std::getline(cpu, line))
            if (line.find("model name") != std::string::npos) {
                f << "CPU: " << line.substr(line.find(":") + 2) << "\n";
                break;
            }
    }

    // Compiler info
#if defined(__GNUC__)
    f << "Compiler: GCC " << __GNUC__ << "." << __GNUC_MINOR__ << "." << __GNUC_PATCHLEVEL__ << "\n";
#elif defined(__clang__)
    f << "Compiler: Clang " << __clang_major__ << "." << __clang_minor__ << "\n";
#else
    f << "Compiler: Unknown\n";
#endif

    // OpenMP version
#if defined(_OPENMP)
    f << "OpenMP version: " << _OPENMP << "\n";
#endif

    f << "\n=== Test Configuration ===\n\n";
    f << "Num series: " << num_series << "\n";
    f << "Series length: " << series_len << "\n";
    f << "Pattern length: " << pattern_len << "\n";
    f << "Warmup runs: " << Config::NUM_WARMUP_RUNS << "\n";
    f << "Measurement runs: " << Config::NUM_MEASUREMENT_RUNS << "\n";

    f.close();
}

void printSummary() {
    std::stringstream ss;
    ss << "\n" << std::string(64, '=') << "\n";
    ss << "SUMMARY - Best Configurations\n";
    ss << std::string(64, '=') << "\n";

    for (const auto& test : g_results) {
        if (test.stats.empty()) continue;
        auto best = std::max_element(test.stats.begin(), test.stats.end(),
            [](const auto& a, const auto& b) { return a.speedup < b.speedup; });
        ss << test.name << ": " << best->config_name
           << " -> " << std::fixed << std::setprecision(2) << best->speedup << "x speedup\n";
    }
    log(ss.str());

}

// ============================================================================
// Input Helpers
// ============================================================================

int getInt(const std::string& prompt, int def) {
    std::cout << prompt << " [" << def << "]: ";
    std::string in; std::getline(std::cin, in);
    return in.empty() ? def : std::stoi(in);
}

std::vector<int> getThreads() {
    int max = omp_get_max_threads();
    std::cout << "Thread counts (comma-sep) [1,2,4" << (max >= 8 ? ",8" : "") << "]: ";
    std::string in; std::getline(std::cin, in);

    std::vector<int> t;
    if (in.empty()) {
        t = {1, 2, 4};
        if (max >= 8) t.push_back(8);
    } else {
        std::stringstream ss(in);
        std::string tok;
        while (std::getline(ss, tok, ',')) {
            int v = std::stoi(tok);
            if (v > 0 && v <= max) t.push_back(v);
        }
    }
    std::sort(t.begin(), t.end());
    t.erase(std::unique(t.begin(), t.end()), t.end());
    return t;
}

// ============================================================================
// Main
// ============================================================================

int main() {
    std::cout << "\n*** PATTERN MATCHING BENCHMARK ***\n\n";

    // Config - default values designed for ~10s sequential execution
    size_t num_series = getInt("Number of series", 20);
    size_t series_len = getInt("Series length", 100000);
    size_t pattern_len = getInt("Pattern length", 1000);
    auto threads = getThreads();

    // Output setup
    createOutputDir();
    g_log.open(g_output_dir + "/results.log");
    log("Output directory: " + g_output_dir + "\n\n");

    // Generate data once
    log("Generating data...\n");
    DatabaseAoS db_aos = DataGenerator::generate(num_series, series_len);
    std::vector<double> pattern = DataGenerator::generate_pattern(pattern_len);
    size_t embed_pos = series_len / 2;
    DataGenerator::embed_pattern(db_aos, 0, embed_pos, pattern);
    DatabaseSoA db_soa = to_soa(db_aos);
    log("Data ready.\n");

    saveSystemInfo(num_series, series_len, pattern_len);

    // Menu
    bool running = true;
    while (running) {
        std::cout << "\n1.Memory Layout  2.Distance  3.Scheduling  4.ChunkSize  5.Scaling  6.Parallelism  7.ALL  0.Exit\n";
        int choice = getInt("Choice", 7);

        g_results.clear();

        if (choice == 0) { running = false; continue; }

        if (choice == 1 || choice == 7) {
            log("\nRunning Memory Layout test...\n");
            g_results.push_back(testMemoryLayout(db_aos, db_soa, pattern, threads));
        }
        if (choice == 2 || choice == 7) {
            log("Running Distance Metrics test...\n");
            g_results.push_back(testDistanceMetrics(db_aos, pattern, threads));
        }
        if (choice == 3 || choice == 7) {
            log("Running Scheduling test...\n");
            g_results.push_back(testScheduling(db_aos, pattern, threads));
        }
        if (choice == 4 || choice == 7) {
            log("Running Chunk Size test...\n");
            g_results.push_back(testChunkSize(db_aos, pattern, threads));
        }
        if (choice == 5 || choice == 7) {
            log("Running Strong Scaling test...\n");
            g_results.push_back(testStrongScaling(db_aos, pattern, threads));
        }
        if (choice == 6 || choice == 7) {
            log("Running Parallelism Strategy test (Internal vs External)...\n");
            g_results.push_back(testParallelismStrategy(db_aos, pattern, threads));
        }

        // Output results
        for (const auto& r : g_results) {
            printResults(r);
            saveResultsCSV(r);
        }
        printSummary();

        log("\nResults saved to: " + g_output_dir + "\n");
    }

    g_log.close();
    std::cout << "\nGoodbye!\n";
    return 0;
}