/******************************************************************************
 * This program computes the number of primes function π(x).
 * 
 * Copyright © 2021 Richard Lesh.  All rights reserved.
 *****************************************************************************/

#undef NDEBUG

#include "Utils.hpp"
#include <clocale>
#include <cmath>
#include <codecvt>
#include <fmt/format.h>
#include <fmt/xchar.h>
#include <fstream>
#include <iostream>
#include <string>
#include <vector>

std::locale utf8loc(std::locale(), new std::codecvt_utf8<wchar_t>);
using namespace Utils;
using namespace std;

static wstring const PRIME_FILE = L"../../data/text/primes1M.txt";
static vector<int> PRIMES = {};

void read_primes(wstring filename) {
    wcout << L"Reading prime file " << filename << L"..." << endl;
    wifstream ifh(filesystem::path(filename).c_str());
    if (!ifh.good()) {
        throw ios_base::failure(Utils::wchar_to_UTF8(L"Problem opening input file!"));
    }
    ifh.imbue(utf8loc);
    wstring line;
    while (getline(ifh, line)) {
        int p = Utils::stoiWithDefault(line, 0);
        if (p != 0) {
            Utils::push(PRIMES, p);
        }
    }
    ifh.close();
}

int binary_search(const vector<int> list, int value) noexcept {
    if (value < PRIMES.front()) {
        return -1;
    }
    if (value > PRIMES.back()) {
        return PRIMES.size();
    }
    int left = 0;
    int right = list.size() - 1;
    while (left <= right) {
        int const m = (left + right) / 2;
        if (list[m] < value) {
            left = m + 1;
        } else if (list[m] > value) {
            right = m - 1;
        } else {
            return m + 1;
        }
    }
    return left;
}

long π(int x) noexcept {
    int pos = PRIMES.size();
    if (pos != 0) {
        pos = binary_search(PRIMES, x);
    }
    if (pos == PRIMES.size()) {
        return floor(x / (log(x) - 1) + 0.5);
    } else {
        return pos;
    }
}

int main(int argc, char **argv) {
    setlocale(LC_ALL, "en_US.UTF-8");
    wcout.imbue(utf8loc);
    wcin.imbue(utf8loc);

    try {
        read_primes(PRIME_FILE);
        int x = 1;
        for (int i = 1; i <= 30; ++i) {
            x *= 2;
            wcout << fmt::format(L"π({0:d}) = {1:d}", x, π(x)) << endl;
        }
    } catch (exception ex) {
        wcout << L"Error reading input file!" << endl;
    }
    return 0;
}