/* Fonctions relatives aux listes d'objets. */
#include <stdio.h>
#include "polygon.h"

/*Configure la liste vide d'objets, avec des sentinelles aux deux extrémités pour
  indiquer la fin des recherches */
void InitializeObjectList()
{
   ObjectListStart.NextObject = &ObjectListEnd;
   ObjectListStart.PreviousObject = NULL;
   ObjectListStart.CenterInView.Z = INT_TO_FIXED(-32768);
   ObjectListEnd.NextObject = NULL;
   ObjectListEnd.PreviousObject = &ObjectListStart;
   ObjectListEnd.CenterInView.Z = 0x7FFFFFFFL;
   NumObjects = 0;
}

/* Ajoute un objet dans la liste d'objets, triée selon la coordonnée Z. */
void AddObject(Object *ObjectPtr)
{
   Object *ObjectListPtr = ObjectListStart.NextObject;

   /* Trouve le point d'insertion. Sûr de terminer en raison de la sentinelle de fin */
   while (ObjectPtr->CenterInView.Z > ObjectListPtr->CenterInView.Z) {
      ObjectListPtr = ObjectListPtr->NextObject;
   }

   /* Réalise un lien avec le nouvel objet */
   ObjectListPtr->PreviousObject->NextObject = ObjectPtr;
   ObjectPtr->NextObject = ObjectListPtr;
   ObjectPtr->PreviousObject = ObjectListPtr->PreviousObject;
   ObjectListPtr->PreviousObject = ObjectPtr;
   NumObjects++;
}

/* Trie de nouveau les objets selon l'ordre ascendant des coordonnées Z dans 
   l'espace de visualisation, en déplaçant chaque objet l'un après l'autre à la bonne   
   position dans la liste des objets. 
*/
void SortObjects()
{
   int i;
   Object *ObjectPtr, *ObjectCmpPtr, *NextObjectPtr;

   /* Commence à vérifier le deuxième objet */
   ObjectCmpPtr = ObjectListStart.NextObject;
   ObjectPtr = ObjectCmpPtr->NextObject;
   for (i=1; i<NumObjects; i++) {
      /* Vérifie si nous devons remonter la liste */
      if (ObjectPtr->CenterInView.Z < ObjectCmpPtr->CenterInView.Z) {
         /* Mémorise là où reprendre le tri au prochain objet */
         NextObjectPtr = ObjectPtr->NextObject;
         /*Oui, remontons jusqu'à ce que nous trouvons le point d'insertion.  Fin  
           garantie en raison de la sentinelle de départ */
         do {
            ObjectCmpPtr = ObjectCmpPtr->PreviousObject;
         } while (ObjectPtr->CenterInView.Z <
               ObjectCmpPtr->CenterInView.Z);

         /* Déplace maintenant l'objet à son nouvel emplacement */
         /* Ne réalise pas un lien entre l'objet et son ancien emplacement */
         ObjectPtr->PreviousObject->NextObject =
               ObjectPtr->NextObject;
         ObjectPtr->NextObject->PreviousObject =
               ObjectPtr->PreviousObject;

         /* Réalise un lien entre l'objet et son nouvel emplacement */
         ObjectCmpPtr->NextObject->PreviousObject = ObjectPtr;
         ObjectPtr->PreviousObject = ObjectCmpPtr;
         ObjectPtr->NextObject = ObjectCmpPtr->NextObject;
         ObjectCmpPtr->NextObject = ObjectPtr;

         /* Passe au prochain objet à trier */
         ObjectCmpPtr = NextObjectPtr->PreviousObject;
         ObjectPtr = NextObjectPtr;
      } else {
         /* Passe au prochain objet à trier */
         ObjectCmpPtr = ObjectPtr;
         ObjectPtr = ObjectPtr->NextObject;
      }
   }
}