/* Pepito v1.59  -- file: sort.c --
   Copyright (c) 2000-01 Carlos del Cacho

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License as published by
   the Free Software Foundation; either version 2, or (at your option)
   any later version.

   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
   GNU General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; see the file COPYING.  If not, write to
   the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
   Boston, MA 02111-1307, USA.

   Contact the author: guggenjaimito@yahoo.com
*/

#ifndef UNIQUE_SOURCE_FILE
#  include "datos.h"
#endif

#define minimo   tab.max_stack[ply-1]
#define maximo   tab.max_stack[ply]

#define TWO_KILLERS

#define PURGE_HASH_MV       1
#define PURGE_KILLER_1      2
#define PURGE_KILLER_2      4
#define SEE_SORT
int             PurgeMove(entero32 jug, char purge, entero32 trayecto_hash,
                                        entero32 killer1, entero32 killer2);


void            PurgeList(list_jug * min, list_jug ** max, char purge, unsigned int trayecto_hash,
                                unsigned int killer1, unsigned int killer2);


//-----------------------------------------------------------------------------------
list_jug       *EligeJugada(int ply)
{
    list_jug       *jug;

    switch (tab.proxima_fase[ply]) {

    case GEN_CAPS:

        maximo = GenCaps(minimo);
        if (maximo == minimo)
            goto KILLERS;
        else
            tab.proxima_fase[ply] = ELIGE_CAPS_MVV_LVA;

    case ELIGE_CAPS_MVV_LVA:

        while (maximo > minimo && (jug = Next_Upon_Value(minimo, maximo, -1)) != NULL) {
            if (tab.jug_hash[ply] != jug->jug) {
                return jug;
            }
            *jug = *(--tab.max_stack[ply]);
        }

#ifdef SEE_SORT
    case GEN_SEE:

        Calc_SSE(minimo, maximo);
        tab.proxima_fase[ply] = ELIGE_CAPS_SEE;

    case ELIGE_CAPS_SEE:

        while (maximo > minimo && (jug = Next_Upon_Value(minimo, maximo, -50)) != NULL) {
            if (tab.jug_hash[ply] != jug->jug) {
                return jug;
            }
            *jug = *(--tab.max_stack[ply]);
        }

#endif

//        tab.purge_list[ply] = 0;

    case KILLER_1:

KILLERS:

        if (tab.jug_hash[ply] != tab.killer[ply][0].mov.jug &&
            JugadaExtValida(&(tab.killer[ply][0].mov))) {
            maximo->jug = tab.killer[ply][0].mov.jug;
            tab.purge_list[ply] |= PURGE_KILLER_1;
            tab.proxima_fase[ply] = KILLER_2;
            return maximo++;
        }
    case KILLER_2:

        if (tab.jug_hash[ply] != tab.killer[ply][1].mov.jug &&
            JugadaExtValida(&(tab.killer[ply][1].mov))) {
            maximo->jug = tab.killer[ply][1].mov.jug;
            tab.purge_list[ply] |= PURGE_KILLER_2;
            tab.proxima_fase[ply] = GEN_NO_CAPS;//OTRAS_CAPS;
            return maximo++;
        }

/*    case OTRAS_CAPS:

        while (maximo > minimo && (jug = Next_Upon_Value(minimo, maximo, -INFINITO)) != NULL) {
            if (tab.jug_hash[ply] != jug->jug) {
                return jug;
            }
            *jug = *(--tab.max_stack[ply]);
        }*/

    case GEN_NO_CAPS:

        maximo = GenNoCaps(maximo);
        ShellSort(minimo, maximo);
        tab.proxima_fase[ply] = ELIGE_NO_CAPS;

    case ELIGE_NO_CAPS:

        if (maximo == minimo)
            return NULL;
        while (PurgeMove((maximo - 1)->jug, tab.purge_list[ply], tab.jug_hash[ply],
                  tab.killer[ply][0].mov.jug, tab.killer[ply][1].mov.jug)) {
            if ((--maximo) == minimo)
                return NULL;
        }

        return (maximo-1);

    case GEN_JAQS:

        maximo = GenJaqJugs(minimo);
        Calc_SSE(minimo, maximo);
        tab.proxima_fase[ply] = ELIGE_JAQS;

    case ELIGE_JAQS:

        if ((jug = Next_Upon_Value(minimo, maximo, -INFINITO)) != NULL) {
            return jug;
        } else
            return NULL;

    case ELIGE_HASH:
        if (tab.jaque[ply])
            tab.proxima_fase[ply] = GEN_JAQS;
        else
            tab.proxima_fase[ply] = GEN_CAPS;

        maximo->jug = tab.jug_hash[ply];
        tab.purge_list[ply] |= PURGE_HASH_MV;

        return maximo++;

    default:
        return NULL;            // nada por hacer
    }
}
//---------------------------------------------------------------------------------
int             PurgeMove(entero32 jug, char purge, entero32 trayecto_hash,
                                          entero32 killer1, entero32 killer2)
{
    if (purge & PURGE_HASH_MV && trayecto_hash == jug)
        return 1;
    if (purge & PURGE_KILLER_1 && killer1 == jug)
        return 1;
    if (purge & PURGE_KILLER_2 && killer2 == jug)
        return 1;
    return 0;
}
//---------------------------------------------------------------------------------
list_jug       *Next_Upon_Value(list_jug * ptrjug, list_jug * ptrjug_lim, int drop_margin)
{
    list_jug       *index,
                   *ibest;

    if (ptrjug >= ptrjug_lim)
        return NULL;

    for (index = ptrjug_lim - 2, ibest = ptrjug_lim - 1; index >= ptrjug; index--) {
        if (index->valor > ibest->valor)
            ibest = index;
    }

    if (ibest->valor > drop_margin)
        return ibest;
    else
        return NULL;
}
//----------------------------------------------------------------------------------------
void            Calc_SSE(list_jug * ptrjug, list_jug * ptrjug_lim)
{
    int             i,
                    limite = ptrjug_lim - ptrjug;

    for (i = 0; i < limite; i++)
        (ptrjug + i)->valor = SSE((ptrjug + i)->jug);
}
//----------------------------------------------------------------------------------------
/*
** The h-constants for this version of Shell-sort come from:
** Handbook of Algorithms and Data Structures in Pascal and C
** By Gaston Gonnet, Ricardo Baeza-Yates
** Addison Wesley; ISBN: 0201416077
** These h-increments work better for me than Sedgewick's under
** full optimization.  Your mileage may vary, so I suggest you
** try Sedgewick's suggestions as well.  The h-increment arena
** is a rich environment for exploration.  I suggest attempting
** all possible permutations below 20, since that is where a
** good shell-sort is crucuial.  If you find something wonderul
** you may get your name up in lights.
** -- D. Corbit
*/
int             ShellSort(list_jug ptrjug[], list_jug ptrlim[])
{
    int             i,
                    j,
                    h;
    size_t          n = (ptrlim - ptrjug);
    list_jug        key;
    for (h = n; h > 0;) {
        for (i = h; (unsigned)i < n; i++) {
            j = i;
            key = ptrjug[i];
            while ((j >= h) & (key.valor < ptrjug[j - h].valor)) {
                ptrjug[j] = ptrjug[j - h];
                j -= h;
            }
            ptrjug[j] = key;
        }
        h = (size_t) ((h > 1) & (h < 5)) ? 1 : 5 * h / 11;
    }

    return 0;
}

//----------------------------------------------------------------------------------------
/* el mayor abajo */

int             InsertSort(list_jug * ptrjug, list_jug * ptrlim)
{
    int             i,
                    j;
    list_jug        key;

    for (i = 1; i < (ptrlim - ptrjug); i++) {
        key = ptrjug[i];
        j = i;
        for (j = i; j && ptrjug[j - 1].valor < key.valor; j--)
            ptrjug[j] = ptrjug[j - 1];
        ptrjug[j] = key;
    }
    return 0;
}
