/* Chrysalide - Outil d'analyse de fichiers binaires
 * sort.c - opérations sur des tableaux triés
 *
 * Copyright (C) 2016 Cyrille Bagard
 *
 *  This file is part of Chrysalide.
 *
 *  Chrysalide 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 3 of the License, or
 *  (at your option) any later version.
 *
 *  Chrysalide 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 Foobar.  If not, see <http://www.gnu.org/licenses/>.
 */


#include "sort.h"


#include <malloc.h>
#include <string.h>



/******************************************************************************
*                                                                             *
*  Paramètres  : key    = élément de comparaison à retrouver ou approcher.    *
*                base   = adresse du tableau à parcourir.                     *
*                nmemb  = nombre d'éléments présents au total.                *
*                size   = taille de chaque élément du tableau.                *
*                compar = méthode de comparaison entre éléments.              *
*                index  = indice de cellule d'insertion.                      *
*                                                                             *
*  Description : Effectue une recherche dichotomique dans un tableau.         *
*                                                                             *
*  Retour      : true si l'élément visé à été trouvé, false sinon.            *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

bool bsearch_index(const void *key, const void *base, size_t nmemb, size_t size, __compar_fn_t compar, size_t *index)
{
    bool result;                            /* Bilan à faire remonter      */
    size_t lower;                           /* Borne inférieure de fenêtre */
    size_t upper;                           /* Borne supérieure qde fenêtre*/
    size_t idx;                             /* Indice de cellule analysée  */
    const void *cell;                       /* Cellule en question         */
    int status;                             /* Bilan d'une comparaison     */

    if (nmemb == 0)
    {
        *index = 0;
        return false;
    }

    /* Parcours minimal */

    lower = 0;
    upper = nmemb;

    while (lower < upper)
    {
        idx = (lower + upper) / 2;
        cell = (void *)(((const char *)base) + (idx * size));

        status = (*compar)(key, cell);

        if (status < 0)
            upper = idx;

        else if (status > 0)
            lower = idx + 1;

        else
            break;

    }

    /* Bilan des recherches */

    result = (status == 0);

    if (status < 0)
        *index = idx;

    else if (status > 0)
        *index = idx + 1;

    else
        *index = idx;

    return result;

}


/******************************************************************************
*                                                                             *
*  Paramètres  : base   = adresse du tableau à parcourir.                     *
*                nmemb  = nombre d'éléments présents au total. [OUT]          *
*                size   = taille de chaque élément du tableau.                *
*                compar = méthode de comparaison entre éléments.              *
*                new    = nouvel élément à insérer.                           *
*                                                                             *
*  Description : Ajoute au bon endroit un élément dans un tableau trié.       *
*                                                                             *
*  Retour      : Nouvel emplacement du tableau agrandi.                       *
*                                                                             *
*  Remarques   : -                                                            *
*                                                                             *
******************************************************************************/

void *qinsert(void *base, size_t *nmemb, size_t size, __compar_fn_t compar, void *new)
{
    void *result;                           /* Tableau trié à retourner    */
    size_t index;                           /* Indice du point d'insertion */

    bsearch_index(new, base, *nmemb, size, compar, &index);

    result = realloc(base, (*nmemb + 1) * size);

    if (index < *nmemb)
        memmove((char *)result + (index + 1) * size, (char *)result + index * size, (*nmemb - index) * size);

    (*nmemb)++;

    memcpy((char *)result + index * size, new, size);

    return result;

}