/*
Suite de fonctions pour maintenir une liste chaînée triée selon l'ordre 
Ascendant du champ Value. La liste est circulaire; c'est-à-dire qu'un nœud 
factice est à la fois la tête et la queue de la liste.
Le nœud factice est une sentinelle, qui contient la plus grande valeur du
champ Value. Testé avec Borland C++ en mode C. */

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "llist.h"

/* Initialise une liste chaînée vide de structures LinkNode,
   composée d'un nœud tête/queue sentinelle, et retourne un 
   pointeur sur la liste. Retourne NULL en cas d'échec. */
struct LinkNode *InitLinkedList()
{
   struct LinkNode *Sentinel;

   if ((Sentinel = malloc(sizeof(struct LinkNode))) == NULL)
      return(NULL);

   Sentinel->NextNode = Sentinel;
   Sentinel->Value = SENTINEL;
   strcpy(Sentinel->Text, "*** sentinelle ***");
   return(Sentinel);
}

/* Trouve dans une liste chaînée triée le premier nœud dont le champ est 
supérieur ou égal à une valeur clé, et retourne un pointeur sur le nœud 
qui le précède(pour faciliter l'insertion ou la suppression), ou bien un
pointeur NULL si aucune valeur n'est trouvée. Suppose que la liste se termine 
par un nœud sentinelle qui contient la plus grande valeur possible */
struct LinkNode *FindNodeBeforeValue(struct LinkNode *HeadOfListNode,
   int SearchValue)
{
   struct LinkNode *NodePtr = HeadOfListNode;

   while (NodePtr->NextNode->Value < SearchValue)
      NodePtr = NodePtr->NextNode;

   if (NodePtr->NextNode->Value == SearchValue) {
      /*Nous avons trouvé la valeur recherchée; nous avons réussi sauf 
       si nous avons trouvé la sentinelle(seulement si SearchValue == SENTINEL) */
      if (NodePtr->NextNode == HeadOfListNode) {
      return(NULL);     /*nous avons échoué; nous avons trouvé la sentinelle */
      } else {
         return(NodePtr);  /*nous avons réussi; retourne un pointeur sur le nœud  
 qui précède celui qui est trouvé */
      }
   } else {
      /*Pas de correspondance; retourne le statut d'échec */
      return(NULL);
   }
}

/* Insère le nœud spécifié dans la liste chaînée triée, afin que
   l'ordre soit maintenu. Retourne un pointeur sur le nœud qui précède
   le nœud qui vient d'être inséré. */
struct LinkNode *InsertNodeSorted(struct LinkNode *HeadOfListNode,
   struct LinkNode *NodeToInsert)
{
   struct LinkNode *NodePtr = HeadOfListNode;
   int SearchValue = NodeToInsert->Value;

   while (NodePtr->NextNode->Value < SearchValue)
      NodePtr = NodePtr->NextNode;

   NodeToInsert->NextNode = NodePtr->NextNode;
   NodePtr->NextNode = NodeToInsert;
   return(NodePtr);
}