/**
 * \file SortedList.cpp
 * Implante une structure de stockage d'une liste (liste chainee ordonnee arbitrairement longue) d'enregistrements tries.
 * 
 * @author Nicolas Janey
 * @author nicolas.janey@univ-fcomte.fr
 * @version 1.0, 01/01/10
 */

#include <stdio.h>
#include <stdlib.h>

#include "SortedList.h"

static void freeListe(int taille,struct SortedList::liste *racine);

int SortedList::cpt = 0;

/**
 * Constructeur pour un nouveau SortedList vide.
 *
 * @author Nicolas Janey
 * @author nicolas.janey@univ-fcomte.fr
 * @version 1.0, 01/01/10
 */
SortedList::SortedList(int (*critere)(void *,void *)) {
  taille = 0;
  racine = NULL;
  fin = NULL;
  this->critere = critere;
  cpt++;
}

/**
 * Destructeur pour un SortedList (sans desallocation les enregistrements qu'il contient).
 *
 * @author Nicolas Janey
 * @author nicolas.janey@univ-fcomte.fr
 * @version 1.0, 01/01/10
 */
SortedList::~SortedList(void) {
  freeListe(taille,racine);
  cpt--;
}

/**
 * Ajout d'un enregistrement en queue d'un SortedList.
 *
 * @param p L'enregistrement a ajouter en queue.
 * @author Nicolas Janey
 * @author nicolas.janey@univ-fcomte.fr
 * @version 1.0, 01/01/10
 */
void SortedList::add(void *p) {
  int indice = 0;
  struct liste *l = this->racine;
  while ( ( l != NULL ) && ( critere(p,l->p) >= 0 ) ) {
    indice++;
    l = l->suiv; }
  add(indice,p);
}

/**
 * Test de l'existence d'un enregistrement dans un SortedList.
 *
 * @param p L'enregistrement a rechercher.
 * @return 1 si l'enregistrement a ete trouve, 0 sinon.
 * @author Nicolas Janey
 * @author nicolas.janey@univ-fcomte.fr
 * @version 1.0, 01/01/10
 */
int SortedList::contains(void *p) {
  struct liste *l = racine;
  while ( ( l != NULL ) && ( l->p != p ) ) {
    l = l->suiv; }
  if ( l == NULL )
    return(0);
  return(1);
}

/**
 * Recherche d'un enregistrement dans un SortedList.
 *
 * @param index L'indice de l'enregistrement a rechercher.
 * @return Le pointeur sur l'enregistrement trouve, NULL si l'index n'existe pas.
 * @author Nicolas Janey
 * @author nicolas.janey@univ-fcomte.fr
 * @version 1.0, 01/01/10
 */
void *SortedList::elementAt(int index) {
  if ( ( index < 0 ) || ( index >= taille ) )
    return(NULL);
  if ( racine == NULL )
    return(NULL);
  struct liste *l = racine;
  int i = 0;
  while ( i < index ) {
    l = l->suiv;
    i++; }
  return(l->p);
}

/**
 * Recherche de l'indice d'un enregistrement present dans un SortedList.
 *
 * @param p L'enregistrement rechercher.
 * @return L'indice trouve, -1 si l'enregistrement n'existe pas.
 * @author Nicolas Janey
 * @author nicolas.janey@univ-fcomte.fr
 * @version 1.0, 01/01/10
 */
int SortedList::indexOf(void *p) {
  struct liste *l = racine;
  int i = 0; 
  while ( ( l != NULL ) && ( l->p != p ) ) {
    i++;
    l = l->suiv; }
  if ( l == NULL )
    return(i);
  return(-1);
}

/**
 * Retrait d'un enregistrement d'un SortedList.
 *
 * @param index l'indice de l'enregistrement retire
 * @return l'enregistrement retire, NULL si elle n'existe pas
 * @author Nicolas Janey
 * @author nicolas.janey@univ-fcomte.fr
 * @version 1.0, 01/01/10
 */
void *SortedList::remove(int index) {
  if ( ( index < 0 ) || ( index >= taille ) )
    return(NULL);
  if ( racine == NULL )
    return(NULL);
  if ( index == 0 ) {
    struct liste *l = racine;
    taille--;
    racine = racine->suiv;
    if ( taille == 0 )
      fin = NULL;
    void *p = l->p;
    free(l);
    return(p); }
  struct liste *l = racine->suiv;
  struct liste *a = racine;
  int i = 1;
  while ( i < index ) {
    a = l;
    l = l->suiv;
    i++; }
  void *p = l->p;
  if ( l == fin )
    fin = a;
  a->suiv = l->suiv;
  taille--;
  free(l);
  return(p);
}

/**
 * Retrait d'un enregistrement d'un SortedList.
 *
 * @param p l'enregistrement a retirer
 * @return 1 si l'enregistrement a ete trouve et retire, 0 sinon
 * @author Nicolas Janey
 * @author nicolas.janey@univ-fcomte.fr
 * @version 1.0, 01/01/10
 */
int SortedList::remove(void *p) {
  if ( racine == NULL )
    return(0);
  if ( racine->p == p ) {
    struct liste *l = racine;
    taille--;
    racine = racine->suiv;
    if ( taille == 0 )
      fin = NULL;
    free(l);
    return(1); }
  struct liste *l = racine->suiv;
  struct liste *a = racine;
  while ( ( l != NULL ) && ( l->p != p ) ) {
    a = l;
    l = l->suiv; }
  if ( l == NULL )
    return(0);
  if ( l == fin )
    fin = a;
  a->suiv = l->suiv;
  taille--;
  free(l);
  return(1);
}

///
/// Retour du dernier element du SortedList.
///
/// @return Le dernier element.
/// @author Nicolas Janey
/// @author nicolas.janey@univ-fcomte.fr
/// @version 1.0, 01/01/10
///
void *SortedList::lastElement(void) {
  if ( fin )
    return(fin->p);
  return(NULL);
}

/**
 * Retour du nombre d'enregistrements stockes dans un SortedList.
 *
 * @return le nombre d'enregistrements actuellement stockees
 * @author Nicolas Janey
 * @author nicolas.janey@univ-fcomte.fr
 * @version 1.0, 01/01/10
 */
int SortedList::size(void) {
  return(taille);
}

static void freeListe(int taille,struct SortedList::liste *racine) {
  if ( taille != 0 ) {
    void **t =(void **) calloc(taille,sizeof(void *));
    struct SortedList::liste *l = racine;
    for ( int i = 0 ; i < taille ; i++ ) {
      t[i] = l;
      l = l->suiv; }
    for ( int i = 0 ; i < taille ; i++ ) {
      free(t[i]); }
    free(t); }
}

/**
 * Vidage d'un SortedList sans desallocation de ses enregistrements.
 *
 * @author Nicolas Janey
 * @author nicolas.janey@univ-fcomte.fr
 * @version 1.0, 01/01/10
 */
void SortedList::removeAll(void) {
  freeListe(taille,racine);
  taille = 0;
  racine = NULL;
  fin = NULL;
}

/**
 * Retour d'un tableau de void * alloue dynamiquement et contenant l'ensemble des enregistrements d'un SortedList.
 *
 * @return le tableau des enregistrements actuellement stockes
 * @author Nicolas Janey
 * @author nicolas.janey@univ-fcomte.fr
 * @version 1.0, 01/01/10
 */
void **SortedList::getArray(void) {
  if ( taille == 0 )
    return(NULL);
  void **t =(void **) calloc(taille,sizeof(void *));
  struct liste *l = racine;
  for ( int i = 0 ; i < taille ; i++ ) {
    t[i] = l->p;
    l = l->suiv; }
  return(t);
}

/**
 * Retour de la quantite de memoire utilisee pour la gestion d'un SortedList.
 *
 * @return la quantite de memoire.
 * @author Nicolas Janey
 * @author nicolas.janey@univ-fcomte.fr
 * @version 1.0, 01/01/10
 */
size_t SortedList::getUsedMemory(void) {
  return(sizeof(SortedList)+taille*sizeof(struct liste));
}

/**
 * Retour du nombre de handles memoires utilises pour la gestion d'un SortedList.
 *
 * @return le nombre de handles memoires.
 * @author Nicolas Janey
 * @author nicolas.janey@univ-fcomte.fr
 * @version 1.0, 01/01/10
 */
long SortedList::getUsedHandles(void) {
  return(1+taille);
}

/**
 * Insertion d'un enregistrement dans un SortedList.
 *
 * @param index L'indice de la position d'insertion
 * @param p L'enregistrement a ajouter.
 * @author Nicolas Janey
 * @author nicolas.janey@univ-fcomte.fr
 * @version 1.0, 01/01/10
 */
void SortedList::add(int index,void *p) {
  if ( ( index < 0 ) || ( index > taille ) )
    return;
  taille++;
  struct liste *l =(struct liste *) calloc(1,sizeof(struct liste));
  l->p = p;
  if ( racine == NULL ) {
    racine = l;
    fin = l;
    return; }
  if ( index == taille-1 ) {
    fin->suiv = l;
    fin = l;
    return; }
  if ( index == 0 ) {
    l->suiv = racine;
    racine = l;
    return; }
  struct liste *a = racine;
  int i = 1;
  while ( i < index ) {
    a = a->suiv;
    i++; }
  l->suiv = a->suiv;
  a->suiv = l;
}
