/*
                                    ALGORITHME DE RAYROLE

Ce module implémente l'algorithme de Rayrole (gestion d'un calendrier de ressource), sans la partie
"décalage du calendrier".

Cette implémentation n'est pas optimisée en espace mémoire : on devrait pouvoir supprimer les
éléments "parent", "tDeb", et "tFin" de chaque noeud, en utilisant une pile lors du parcours de
l'arbre (et, d'un point de vue théorique, on pourrait aussi fusionner "qf" et "qn").

*/

#include <time.h>


// arbre du calendrier
typedef struct xxxnoeud
{   struct xxxnoeud *fg, *fd,    // fils gauche et droit
                    *parent;
    time_t tDeb, tFin;            // début et fin de la période représentée par le noeud
    long qf,                    // max (q(fg),q(fd))
         qn;                    // quantités réservées pour ce noeud-chapeau
}
type_noeud;
static type_noeud *racine;
static time_t granularite;        // granularité du calendrier (période couverte par une feuille de l'arbre)


// variables pour le parcours de l'arbre
static type_noeud *ndParcours;        // dernier noeud parcouru
static long qnTotalParcours;        // total des qn depuis la racine jusqu'au noeud <ndParcours>
static time_t tDebResa, tFinResa;    // début/fin de la réservation
static char phaseParcours;            // 0=init ; 1=remontée gauche ; 2=remontée droite
                                    // 3=remontée finale (une fois tous les noeuds-chapeaux trouvés)


//===============================================================================================
//                                    PARCOURS DE L'ARBRE

/*
Il y a deux types de parcours :

1) Le parcours de noeuds-chapeaux (appelé parcours "C")
    Durant ce parcours, on calcule la quantité maximale réservée sur la période correspondant à
            chaque noeud-chapeau.
    Ce parcours est utilisé pour connaître la quantité de ressource déjà réservée

2) Le parcours de noeuds-chapeaux et des noeuds parents d'au moins un noeud-chapeau (appelé parcours "CP")
    Le parcours se fait de bas en haut (un noeud est toujours retourné AVANT son noeud parent)
    Ce parcours est utilisé pour ajouter ou supprimer une réservation
*/

//----- Initialise le parcours des noeuds-chapeaux
// Retourne FALSE ssi la période est en dehors du calendrier
static boolean InitParcours (time_t t0, time_t t1)
    // t0, t1 : début/fin de la période 
{
    if (t0 > racine->tFin || t1 < racine->tDeb)
        return FALSE;
    phaseParcours = 0;
    // pour simplifier le parcours, arrondit tDebResa et tFinResa à la granularité de l'arbre 
    if (t0 < racine->tDeb)
        tDebResa = racine->tDeb;
    else
        tDebResa = t0 - (t0-racine->tDeb)%granularite;
    if (t1 > racine->tFin)
        tFinResa = racine->tFin;
    else
        tFinResa = t1 - (t1-racine->tDeb)%granularite + granularite-1;
    return TRUE;
}


//----- Trouve le noeud-chapeau suivant (noeud-chapeau)
// Retourne FALSE quand il n'y a plus de noeud-chapeau
static boolean NoeudSuivantC (type_noeud **pNoeud, long *quantiteMax)
    // pNoeud : en retour, pointeur vers le noeud-chapeau suivant
    // quantiteMax : en retour, quantité maximale réservée sur la période correspondant au noeud-chapeau
{
    type_noeud *exNd;
    
    if (phaseParcours == 0)
    {   // trouve le noeud-chapeau le plus à gauche
        ndParcours = racine;
        qnTotalParcours = racine->qn;
        while (ndParcours->tDeb < tDebResa || ndParcours->tFin > tFinResa)
        {   if (ndParcours->fd)
                ndParcours = (ndParcours->fd->tDeb <= tDebResa) ? ndParcours->fd : ndParcours->fg;
            else
                ndParcours = ndParcours->fg;
            qnTotalParcours += ndParcours->qn;
        }
        phaseParcours = 1;
        *pNoeud = ndParcours;
        *quantiteMax = qnTotalParcours + ndParcours->qf;
        return TRUE;
    }
    
    if (phaseParcours == 1)
    {   // remontée gauche
        if (ndParcours == racine)
            return FALSE;
        exNd = ndParcours;
        do
        {   qnTotalParcours -= ndParcours->qn;
            ndParcours = ndParcours->parent;
        }
        while (ndParcours != NULL && ndParcours->tFin == exNd->tFin);
        if (ndParcours == NULL)
            return FALSE;
        ndParcours = ndParcours->fd;
        qnTotalParcours += ndParcours->qn;
        if (ndParcours->tFin > tFinResa)
        {   // remontée gauche terminée => trouve le noeud-chapeau le plus à droite
            if (ndParcours->tDeb > tFinResa)
                return FALSE;
            do
            {   ndParcours = (ndParcours->fg->tFin >= tFinResa) ? ndParcours->fg : ndParcours->fd;
                qnTotalParcours += ndParcours->qn;
            } while (ndParcours->tFin > tFinResa);
            phaseParcours = 2;
            *pNoeud = ndParcours;
            *quantiteMax = qnTotalParcours + ndParcours->qf;
            return TRUE;
        }
        *pNoeud = ndParcours;
        *quantiteMax = qnTotalParcours + ndParcours->qf;
        return TRUE;
    }
    
    // phaseParcours == 2
    // remontée droite
    exNd = ndParcours;
    do
    {   qnTotalParcours -= ndParcours->qn;
        ndParcours = ndParcours->parent;
    }
    while (ndParcours != NULL && ndParcours->tDeb == exNd->tDeb);
    if (ndParcours == NULL)
        return FALSE;
    ndParcours = ndParcours->fg;
    qnTotalParcours += ndParcours->qn;
    if (ndParcours->tDeb <= tDebResa) // remontée droite terminée
        return FALSE;
    *pNoeud = ndParcours;
    *quantiteMax = qnTotalParcours + ndParcours->qf;
    return TRUE;
}


//----- Trouve le noeud suivant (noeud-chapeau, ou parent d'un noeud-chapeau)
// Continue le parcours de l'arbre, en retournant
//        soit un noeud-chapeau
//        soit un parent d'un noeud-chapeau
// Retourne FALSE en fin de parcours
static boolean NoeudSuivantCP (type_noeud **pNoeud, boolean *pChapeau)
    // pNoeud : en retour, pointeur vers le noeud suivant
    // pChapeau : en retour, TRUE ssi c'est un noeud-chapeau
{
    type_noeud *exNd;
    
    if (phaseParcours == 0)
    {   // trouve le noeud-chapeau le plus à gauche
        ndParcours = racine;
        while (ndParcours->tDeb < tDebResa || ndParcours->tFin > tFinResa)
        {   if (ndParcours->fd)
                ndParcours = (ndParcours->fd->tDeb <= tDebResa) ? ndParcours->fd : ndParcours->fg;
            else
                ndParcours = ndParcours->fg;
        }
        phaseParcours = 1;
        *pNoeud = ndParcours;
        *pChapeau = TRUE;
        return TRUE;
    }
    
    if (phaseParcours == 1)
    {   // remontée gauche
        if (ndParcours == racine)
            return FALSE;
        exNd = ndParcours;
        ndParcours = ndParcours->parent;
        if (ndParcours->tFin == exNd->tFin)
        {   *pNoeud = ndParcours;
            *pChapeau = FALSE;
            return TRUE;
        }
        ndParcours = ndParcours->fd;
        if (ndParcours->tFin > tFinResa)
        {   // remontée gauche terminée => trouve le noeud-chapeau le plus à droite
            if (ndParcours->tDeb > tFinResa)
            {   ndParcours = ndParcours->parent;
                *pChapeau = FALSE;
                phaseParcours = 3;
            }
            else
            {    do
                {   ndParcours = (ndParcours->fg->tFin >= tFinResa) ? ndParcours->fg : ndParcours->fd;
                    qnTotalParcours += ndParcours->qn;
                } while (ndParcours->tFin > tFinResa);
                *pChapeau = TRUE;
                phaseParcours = 2;
            }
        }
        else
            *pChapeau = TRUE;
        *pNoeud = ndParcours;
        return TRUE;
    }
    
    if (phaseParcours == 2)
    {   // remontée droite
        exNd = ndParcours;
        ndParcours = ndParcours->parent;
        if (ndParcours->tDeb == exNd->tDeb)
        {   *pNoeud = ndParcours;
            *pChapeau = FALSE;
            return TRUE;
        }
        ndParcours = ndParcours->fg;
        if (ndParcours->tDeb <= tDebResa) // remontée droite terminée
        {   ndParcours = ndParcours->parent;
            *pChapeau = FALSE;
            phaseParcours = 3;
        }
        else
            *pChapeau = TRUE;
        *pNoeud = ndParcours;
        return TRUE;
    }
    
    // phaseParcours == 3
    // remontée finale, jusqu'à la racine
    if (ndParcours == racine)
        return FALSE;
    ndParcours = ndParcours->parent;
    *pNoeud = ndParcours;
    *pChapeau = FALSE;
    return TRUE;
}


//===============================================================================================
//                                        OPERATIONS DE BASE

//----- Crée un sous-arbre
// ATTENTION : il faudrait tester le retour du calloc()
static type_noeud *CreeSousArbre (time_t tDeb, time_t tFin, time_t deltaT, int hauteur, type_noeud *parent)
{
    type_noeud *nouveauNd;
    time_t tDebFDroit;        // début de la période couverte par le fils droit
    
    nouveauNd = calloc(sizeof(type_noeud),1);
    nouveauNd->tDeb = tDeb;
    nouveauNd->tFin = tFin;
    nouveauNd->parent = parent;
    if (hauteur > 1)
    {
        tDebFDroit = tDeb + (deltaT << (hauteur-2));
        if (tDebFDroit > tFin)
            nouveauNd->fg = CreeSousArbre (tDeb, tFin, deltaT, hauteur-1, nouveauNd);
        else
        {   nouveauNd->fg = CreeSousArbre (tDeb, tDebFDroit-1, deltaT, hauteur-1, nouveauNd);
            nouveauNd->fd = CreeSousArbre (tDebFDroit, tFin, deltaT, hauteur-1, nouveauNd);
        }
    }
    return nouveauNd;
}

//----- Crée un arbre de réservation
// Il faudrait ajouter le contrôle de l'allocation mémoire
void CreeRayrole (time_t tDeb, time_t tFin, time_t deltaT)
{
    int nbFeuilles1,    // nombre de feuilles - 1
        hauteur;
    
    nbFeuilles1 = (tFin-tDeb)/deltaT;
    hauteur = 1;
    while (nbFeuilles1 > 0)
    {   hauteur++;
        nbFeuilles1 >>= 1;
    }
    racine = CreeSousArbre(tDeb,tFin,deltaT,hauteur,NULL);
    granularite = deltaT;
}    


//----- Ajoute une réservation
boolean AjouteResa (time_t t0, time_t t1, long quantite)
{
    type_noeud *nd;
    boolean chapeau;

    if (!InitParcours(t0,t1))
        return FALSE;
    while (NoeudSuivantCP(&nd,&chapeau))
        if (chapeau)
            nd->qn += quantite;
        else
            nd->qf = max (nd->fg->qn+nd->fg->qf , nd->fd->qn+nd->fd->qf);
    return TRUE;
}

//----- Supprime une réservation
boolean SupprimeResa (time_t t0, time_t t1, long quantite)
{
    return AjouteResa(t0,t1,-quantite);
}


//----- Trouve la quantité réservée max sur une période
long MaxReserve (time_t t0, time_t t1)
{
    type_noeud *nd;
    long qMax, resultat;
    
    if (!InitParcours(t0,t1))
        return -1;
    resultat = 0;
    while (NoeudSuivantC(&nd,&qMax))
        resultat = max(resultat,qMax);
    return resultat;
}