#include "HandEvaluator.h"

#include "OffsetTable.hxx"
#include "Util.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>
#include <cstring>

namespace omp {

// Rank multipliers that guarantee a unique key for every rank combination in a 0-7 card hand.
const unsigned HandEvaluator::RANKS[]{0x2000, 0x8001, 0x11000, 0x3a000, 0x91000, 0x176005, 0x366000,
        0x41a013, 0x47802e, 0x479068, 0x48c0e4, 0x48f211, 0x494493};

// Rank multipliers for flush hands where only 1 of each rank is allowed. We could choose smaller numbers here but
// we want to get the key from a bitmask, so powers of 2 are used.
const unsigned HandEvaluator::FLUSH_RANKS[]{1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096};

Hand Hand::CARDS[]{};
const Hand Hand::EMPTY(0x3333ull << SUITS_SHIFT, 0);
uint16_t HandEvaluator::LOOKUP[]{};
uint16_t* HandEvaluator::ORIG_LOOKUP = nullptr;
uint16_t HandEvaluator::FLUSH_LOOKUP[]{};
const unsigned HandEvaluator::MAX_KEY = 4 * RANKS[12] + 3 * RANKS[11];
bool HandEvaluator::cardInit = (initCardConstants(), true);

// Does a thread-safe (guaranteed by C++11) one time initialization of static data.
HandEvaluator::HandEvaluator()
{
    static bool initVar = (staticInit(), true);
    (void)initVar;
}

// Initialize card constants.
void HandEvaluator::initCardConstants()
{
    for (unsigned c = 0; c < CARD_COUNT; ++c) {
        unsigned rank = c / 4, suit = c % 4;
        Hand::CARDS[c] = Hand((1ull << (4 * suit + Hand::SUITS_SHIFT)) + (1ull << Hand::CARD_COUNT_SHIFT)
                              + RANKS[rank], 1ull << ((3 - suit) * 16 + rank));
    }
}

// Initialize static class data.
void HandEvaluator::staticInit()
{
    // Temporary table for hash recalculation.
    if (RECALCULATE_PERF_HASH_OFFSETS)
        ORIG_LOOKUP = new uint16_t[MAX_KEY + 1];

    static const unsigned RC = RANK_COUNT;

    // 1. High card
    unsigned handValue = HIGH_CARD;
    handValue = populateLookup(0, 0, handValue, RC, 0, 0, 0);

    // 2. Pair
    handValue = PAIR;
    for (unsigned r = 0; r < RC; ++r)
        handValue = populateLookup(2ull << 4 * r, 2, handValue, RC, 0, 0, 0);

    // 3. Two pairs
    handValue = TWO_PAIR;
    for (unsigned r1 = 0; r1 < RC; ++r1)
        for (unsigned r2 = 0; r2 < r1; ++r2)
            handValue = populateLookup((2ull << 4 * r1) + (2ull << 4 * r2), 4, handValue, RC, r2, 0, 0);

    // 4. Three of a kind
    handValue = THREE_OF_A_KIND;
    for (unsigned r = 0; r < RC; ++r)
        handValue = populateLookup(3ull << 4 * r, 3, handValue, RC, 0, r, 0);

    // 4. Straight
    handValue = STRAIGHT;
    handValue = populateLookup(0x1000000001111ull, 5, handValue, RC, RC, RC, 3); // wheel
    for (unsigned r = 4; r < RC; ++r)
        handValue = populateLookup(0x11111ull << 4 * (r - 4), 5, handValue, RC, RC, RC, r);

    // 6. FLUSH
    handValue = FLUSH;
    handValue = populateLookup(0, 0, handValue, RC, 0, 0, 0, true);

    // 7. Full house
    handValue = FULL_HOUSE;
    for (unsigned r1 = 0; r1 < RC; ++r1)
        for (unsigned r2 = 0; r2 < RC; ++r2)
            if (r2 != r1)
                handValue = populateLookup((3ull << 4 * r1) + (2ull << 4 * r2), 5, handValue, RC, r2, r1, RC);

    // 8. Quads
    handValue = FOUR_OF_A_KIND;
    for (unsigned r = 0; r < RC; ++r)
        handValue = populateLookup(4ull << 4 * r, 4, handValue, RC, RC, RC, RC);

    // 9. Straight flush
    handValue = STRAIGHT_FLUSH;
    handValue = populateLookup(0x1000000001111ull, 5, handValue, RC, 0, 0, 3, true); // low straight flush
    for (unsigned r = 4; r < RC; ++r)
        handValue = populateLookup(0x11111ull << 4 * (r - 4), 5, handValue, RC, 0, 0, r, true);

    if (RECALCULATE_PERF_HASH_OFFSETS) {
        calculatePerfectHashOffsets();
        delete[] ORIG_LOOKUP;
    }
}

// Iterates recursively over the the remaining cards ranks in a hand and writes the hand values for each combination
// to lookup table. Parameters maxPair, maxTrips, maxStraight are used for checking that the hand
// doesn't improve (except kickers).
unsigned HandEvaluator::populateLookup(uint64_t ranks, unsigned ncards, unsigned handValue, unsigned endRank,
                                            unsigned maxPair, unsigned maxTrips, unsigned maxStraight, bool flush)
{
    // Only increment hand value counter for every valid 5 card combination. (Or smaller hands if enabled.)
    if (ncards <= 5 && ncards >= (MIN_CARDS < 5 ? MIN_CARDS : 5))
        ++handValue;

    // Write hand value to lookup when we have required number of cards.
    if (ncards >= MIN_CARDS || (flush && ncards >= 5)) {
        unsigned key = getKey(ranks, flush);

        // Write flush and non-flush hands in different tables
        if (flush) {
            FLUSH_LOOKUP[key] = handValue;
        } else if (RECALCULATE_PERF_HASH_OFFSETS) {
            ORIG_LOOKUP[key] = handValue;
        } else {
            omp_assert(LOOKUP[perfHash(key)] == 0 || LOOKUP[perfHash(key)] == handValue);
            LOOKUP[perfHash(key)] = handValue;
        }

        if (ncards == 7)
            return handValue;
    }

    // Iterate next card rank.
    for (unsigned r = 0; r < endRank; ++r) {
        uint64_t newRanks = ranks + (1ull << (4 * r));

        // Check that hand doesn't improve.
        unsigned rankCount = ((newRanks >> (r * 4)) & 0xf);
        if (rankCount == 2 && r >= maxPair)
            continue;
        if (rankCount == 3 && r >= maxTrips)
            continue;
        if (rankCount >= 4) // Don't allow new quads or more than 4 of same rank.
            continue;
        if (getBiggestStraight(newRanks) > maxStraight)
            continue;

        handValue = populateLookup(newRanks, ncards + 1, handValue, r + 1, maxPair, maxTrips, maxStraight, flush);
    }

    return handValue;
}

// Calculate lookup table key from rank counts.
unsigned HandEvaluator::getKey(uint64_t ranks, bool flush)
{
    unsigned key = 0;
    for (unsigned r = 0; r < RANK_COUNT; ++r)
        key += ((ranks >> r * 4) & 0xf) * (flush ? FLUSH_RANKS[r] : RANKS[r]);
    return key;
}

// Returns index of the highest straight card or 0 when no straight.
unsigned HandEvaluator::getBiggestStraight(uint64_t ranks)
{
    uint64_t rankMask = (0x1111111111111 & ranks) | (0x2222222222222 & ranks) >> 1 | (0x4444444444444 & ranks) >> 2;
    for (unsigned i = 9; i-- > 0; )
        if (((rankMask >> 4 * i) & 0x11111ull) == 0x11111ull)
            return i + 4;
    if ((rankMask & 0x1000000001111) == 0x1000000001111)
        return 3;
    return 0;
}

// Perfect hashing based on the algorithm described in
// http://www.drdobbs.com/architecture-and-design/generating-perfect-hash-functions/184404506
void HandEvaluator::calculatePerfectHashOffsets()
{
    // Store locations of all non-zero elements in original lookup table, divided into rows.
    std::vector<std::pair<size_t,std::vector<size_t>>> rows;
    for (size_t i = 0; i < MAX_KEY + 1; ++i) {
        if (ORIG_LOOKUP[i]) {
            size_t rowIdx = i >> PERF_HASH_ROW_SHIFT;
            if (rowIdx >= rows.size())
                rows.resize(rowIdx + 1);
            rows[rowIdx].second.push_back(i);
        }
    }

    // Need to store the original row indexes because we need them after sorting.
    for (size_t i = 0; i < rows.size(); ++i)
        rows[i].first = i;

    // Try to fit the densest rows first. Results in slightly smaller table.
    std::sort(rows.begin(), rows.end(), [](const std::pair<size_t,std::vector<size_t>>& lhs,
              const std::pair<size_t,std::vector<size_t>> & rhs){
        return lhs.second.size() > rhs.second.size();
    });

    // Goes through every row and for each of them try to find the first offset that doesn't cause any collisions with
    // previous rows. Does a very naive brute force search.
    size_t maxIdx = 0;
    for (size_t i = 0; i < rows.size(); ++i) {
        size_t offset = 0; //-(rows[i].second[0] & PERF_HASH_COLUMN_MASK); makes no difference so let's avoid negative
        for (;;++offset) {
            bool ok = true;
            for (auto x : rows[i].second) {
                unsigned val = LOOKUP[(x & PERF_HASH_COLUMN_MASK) + offset];
                if (val && val != ORIG_LOOKUP[x]) { // Allow collisions if value is the same
                    ok = false;
                    break;
                }
            }
            if (ok)
                break;
        }
        //std::cout << "row=" << i << " size=" << rows[i].second.size() << " offset=" << offset << std::endl;
        PERF_HASH_ROW_OFFSETS[rows[i].first] = (uint32_t)(offset - (rows[i].first << PERF_HASH_ROW_SHIFT));
        for (size_t key : rows[i].second) {
            size_t newIdx = (key & PERF_HASH_COLUMN_MASK) + offset;
            maxIdx = std::max<size_t>(maxIdx, newIdx);
            LOOKUP[newIdx] = ORIG_LOOKUP[key];
        }
    }

    // Output offset array.
    std::cout << "offsets: " << std::endl;
    for (size_t i = 0; i < rows.size(); ++i) {
        if (i % 8 == 0)
            std::cout << std::endl;
        std::cout << std::hex << "0x" << PERF_HASH_ROW_OFFSETS[i] << std::dec << ", ";
    }

    // Output stats.
    std::cout << std::endl;
    outputTableStats("FLUSH_LOOKUP", FLUSH_LOOKUP, 2, FLUSH_LOOKUP_SIZE);
    outputTableStats("ORIG_LOOKUP", ORIG_LOOKUP, 2, MAX_KEY + 1);
    outputTableStats("LOOKUP", LOOKUP, 2, maxIdx + 1);
    outputTableStats("OFFSETS", PERF_HASH_ROW_OFFSETS, 4, rows.size());
    std::cout << "lookup table size: " << maxIdx + 1 << std::endl;
    std::cout << "offset table size: " << rows.size() << std::endl;
}

// Output stats about memory usage of a lookup table.
void HandEvaluator::outputTableStats(const char* name, const void* p, size_t elementSize, size_t count)
{
    char dummy[64]{};
    size_t totalCacheLines = 0, usedCacheLines = 0, usedElements = 0;
    for (size_t i = 0; i < elementSize * count; i += 64) {
        ++totalCacheLines;
        bool used = false;
        for (size_t j = 0; j < 64 && i + j < elementSize * count; j += elementSize) {
            if (std::memcmp((const char*)p + i + j, dummy, elementSize)) {
                ++usedElements;
                used = true;
            }
        }
        usedCacheLines += used;
    }
    std::cout << name << ": cachelines: " << usedCacheLines << "/" << totalCacheLines
         << "  kbytes: " << usedCacheLines / 16  << "/" << totalCacheLines / 16
         << "  elements: " << usedElements << "/" << count
         << std::endl;
}

}