#include <assert.h>
#include <string.h>
#include "ramjet.h"
#include "bitboard.h"
#include "quadboard.h"
#include "move.h"
#include "position.h"
#include "sort.h"

// bubble the best move to the top
void sort_2_top(MOVE* mv, int best)
{
    int i;

    MOVE top = mv[best];
    for(i = best; i > 0; --i)
        mv[i] = mv[i - 1];
    mv[i] = top;
}

// sort the moves in decreasing order
void sort_array(MOVE* mv, int n)
{
    int i, j;

    // good old insertion sort
    for(i = 1; i < n; ++i) {
        MOVE temp = mv[i];
        for(j = i; j > 0 && temp > mv[j - 1]; --j)
            mv[j] = mv[j - 1];
        mv[j] = temp;
    }
}

// gather the forcing moves: smallest recapture first, MVV and delta pruning
int sort_forcing(const POSITION* pos, MOVE* mv, int n, int delta)
{
    // MVV-LVA values
    static int val_vict[8] = {0, 100, 300, 300, 500, 900, 0, 0};
    static int val_atk[9] =  {0,   4,   3,   3,   2,   1, 5, 0};

    // occupancy and recapture square
    BITBOARD bb_all = qb_get_bb_tot(&pos->qb);
    SQUARE sq = MV_GET_TO(pos->lmv);

    int f, i, m, r;

    // evaluate the forcing moves and gather them at the top
    for(i = 0, m = 0, r = 0; i < n; ++i) {
        SQUARE to = MV_GET_TO(mv[i]);
        f = 0;

        // castle and enpassant
        if(IS_MV_SPECIAL(mv[i])) {
            mv[i] = MV_ADD_SCORE(mv[i], val_vict[PAWN]);
            f = 1;
        } else {

            // capture
            if((bb_all & BB_SQ(to))) {
                mv[i] = MV_ADD_SCORE(mv[i], val_vict[qb_get_sq_pt(&pos->qb, to)]);
                f = 1;
            }

            // promotion
            if(IS_MV_PROMO(mv[i])) {
                mv[i] = MV_ADD_SCORE(mv[i], val_vict[MV_GET_PROMO(mv[i])] - 100);
                f = 1;
            }
        }

        // delta pruning
        if(f && (int) MV_GET_SCORE(mv[i]) > delta) {
            MOVE temp = mv[i];
            mv[i] = mv[m];

            // least recapture first (implicit SEE)
            int v = val_atk[qb_get_sq_pt(&pos->qb, MV_GET_FROM(temp))];
            if(to == sq && v > r) {
                r = v;
                mv[m++] = mv[0];
                mv[0] = temp;

            // other forcing moves
            } else
                mv[m++] = temp;
        }
    }

    // sort the forcing moves (except the least recapture)
    i = (r > 0)? 1 : 0;
    sort_array(&mv[i], m - i);

    return m;
}

// sort by history heuristic
void sort_quiet(const POSITION* pos, MOVE* mv, HISTORYTABLE* hy, int n)
{
    PLAYER pl = ST_GET_PL(pos->st);
    int i;

    // evaluate the quiet moves by their history value
    for(i = 0; i < n; ++i) {

        SQUARE from = MV_GET_FROM(mv[i]);
        SQUARE to = MV_GET_TO(mv[i]);
        PIECETYPE pt = qb_get_sq_pt(&pos->qb, from);

        mv[i] = MV_ADD_SCORE(mv[i], hy->entry[pl][pt - 1][to]);
    }

    // sort the quiet moves
    sort_array(mv, n);

    return;
}

// generate and sort moves on the fly
int sort_more_mv(const POSITION* pos, MOVE* mv, HISTORYTABLE* hy, SORTSTATE* ss, int i)
{
    assert(!is_pos_bad(pos));

    // the current stage has more moves
    if(i < SS_GET_N1(*ss))
        return 1;

    // generate and sort the next stage
    else switch(SS_GET_GS(*ss)) {
        int n1, n2;

        // validate the hash move in mv[0] or move to the next stage
        case GS_START:
            *ss = SS_NEW(GS_HASH, 1, 0);
            if(!is_mv_bad(&pos->qb, pos->st, mv[0]))
                return 1;

        // generate all moves, sort only the forcing ones
        case GS_HASH:
            n2 = pos_gen_mv(pos, &mv[i]);
            n1 = sort_forcing(pos, &mv[i], n2, 0);
            *ss = SS_NEW(GS_FORCING, n1 + i, n2 + i);
            if(n1 > 0) return 1;

        // sort the remaining moves
        case GS_FORCING:
            n2 = SS_GET_N2(*ss);
            sort_quiet(pos, &mv[i], hy, n2 - i);
            *ss = SS_NEW(GS_OTHER, n2, 0);
            if(n2 > i) return 1;
    }

    return 0;
}

// test the functions above
int sort_test()
{
    char mv0[8], mv1[8], mv2[8], mv3[8], mv4[8], mv5[8], mv6[8];
    char fen[] = "k2B1r2/p3P3/8/1P6/8/8/8/R3K3 b Q - 0 1";
    POSITION pos;
    MOVE mv[256];

    // generate position and moves
    pos_scan_fen(fen, &pos);
    pos_make_mv(&pos, mv_scan_uci("a7a5", &pos.qb, pos.st, 0));
    int n = pos_gen_mv(&pos, mv);

    // sorting forcing moves
    int m = sort_forcing(&pos, mv, n, 0);
    mv_print_uci(mv0, &pos.qb, pos.st, 0, mv[0]);
    mv_print_uci(mv1, &pos.qb, pos.st, 0, mv[1]);
    mv_print_uci(mv2, &pos.qb, pos.st, 0, mv[2]);
    mv_print_uci(mv3, &pos.qb, pos.st, 0, mv[3]);
    mv_print_uci(mv4, &pos.qb, pos.st, 0, mv[9]);
    mv_print_uci(mv5, &pos.qb, pos.st, 0, mv[10]);
    mv_print_uci(mv6, &pos.qb, pos.st, 0, mv[11]);
    if(m != 12 || strcmp(mv0, "d8a5") ||
                  strcmp(mv1, "e7f8q") ||
                  strcmp(mv2, "e7f8r") ||
                  strcmp(mv3, "e7e8q") ||
                  strcmp(mv4, "e1c1") ||
                  strcmp(mv5, "b5a6") ||
                  strcmp(mv6, "a1a5"))
        return 1;

    // stage generation: hash and forcing moves
    SORTSTATE ss = SS_START;
    if(!sort_more_mv(&pos, mv, NULL, &ss, 0) || SS_GET_GS(ss) != GS_HASH ||
       !sort_more_mv(&pos, mv, NULL, &ss, 1) || SS_GET_N1(ss) != 13 || SS_GET_N2(ss) != 27)
        return 2;

    // stage generation: no moves left behind
    HISTORYTABLE hy;
    int i;
    ss = SS_START;
    mv[0] = MV_NULL;
    for(i = 0; sort_more_mv(&pos, mv, &hy, &ss, i); ++i);
    if(i != n)
        return 3;

    return 0;
}
