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

#include "stdafx.h"

#include <vector>
#include <algorithm>
#include <iostream>
#include <chrono>
#include "ArrayTestProject.h"

std::vector<uint8_t> main_arr_reg;

std::vector<uint8_t> main_arr;
std::vector<uint32_t> sec_arr;

std::vector<int> rand_access_order;

static constexpr int NUMBER = 10000000;

int main()
{
    rand_access_order.resize(NUMBER);

    main_arr.resize(NUMBER/4);
    main_arr_reg.resize(NUMBER);

    for (int i = 0; i < NUMBER; i++) {

        rand_access_order[i] = ((double)rand() / (double)RAND_MAX) * (NUMBER-1);

        float val = ((float) rand() / (float) RAND_MAX);

        int mainIndex = i >> 2;

        if (val < 0.5f) {
            main_arr_reg[i] = 0;
            main_arr[mainIndex] |= 0 << ((i & 3) * 2);
        }
        else if (val < 0.95f) {
            main_arr_reg[i] = 1;
            main_arr[mainIndex] |= 1 << ((i & 3) * 2);
        }
        else if (val < 0.99f) {
            main_arr_reg[i] = 2;
            main_arr[mainIndex] |= 2 << ((i & 3) * 2);
        }
        else {
            main_arr[mainIndex] |= 3 << ((i & 3) * 2);

            uint8_t randNew = ((float)rand() / (float)RAND_MAX) * 200 + 4;

            sec_arr.push_back((i << 8) | randNew);

            main_arr_reg[i] = randNew;

        }

    }

    {
        std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();

        DoTest0();

        std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();

        std::cout << "0 Time difference = " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << std::endl;
    }

    {
        std::chrono::steady_clock::time_point begin = std::chrono::steady_clock::now();

        DoTest1();

        std::chrono::steady_clock::time_point end = std::chrono::steady_clock::now();

        std::cout << "1 Time difference = " << std::chrono::duration_cast<std::chrono::microseconds>(end - begin).count() << std::endl;
    }


    return 0;
}

void DoTest0() {

    uint64_t sum = 0;

    for (int i = 0; i < NUMBER; ++i) {

        int randnum = ((double)rand() / (double)RAND_MAX) * (NUMBER - 1);

        sum += main_arr_reg[randnum];

    }

    std::cout << "0 Sum: " << sum << std::endl;
}

void DoTest1() {

    uint64_t sum = 0;

    for (int i = 0; i < NUMBER; ++i) {

        int randnum = ((double)rand() / (double)RAND_MAX) * (NUMBER - 1);

        sum += lookup(randnum);

    }

    std::cout << "1 Sum: " << sum << std::endl;
}



uint8_t lookup(unsigned idx) {
    // extract the 2 bits of our interest from the main array
    uint8_t v = (main_arr[idx >> 2] >> (2 * (idx & 3))) & 3;
    // usual (likely) case: value between 0 and 2
    if (v != 3) return v;
    // bad case: lookup the index<<8 in the secondary array
    // lower_bound finds the first >=, so we don't need to mask out the value
    auto ptr = std::lower_bound(sec_arr.begin(), sec_arr.end(), idx << 8);
#ifdef _DEBUG
    // some coherency checks
    if (ptr == sec_arr.end()) {
        std::cout << "ERROR: " << uint8_t(idx << 8) << std::endl;
        std::abort();
    }
    if ((*ptr >> 8) != idx) std::abort();
#endif
    // extract our 8-bit value from the 32 bit (index, value) thingie
    return (*ptr) & 0xff;
}