/***************************************************************************
                          stringList.h  -  description
                             -------------------
    debut                : Fri Nov 19 2004
    copyright            : (C) 2004 by Yan Morin
    courriel                : yansanmo@iquebec.com
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   This program 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 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 ***************************************************************************/

/**
 * Liste de chaine de caracteres
 * Provient du code source listString.h (laboratoire 1, yan morin)
 * Utilisation
 * StringList mylist;
 * StringList_init(&mylist);
 * StringList_add(&mylist, "bla bla");
 * StringList_free(&mylist);
 *
 * Deboggage:
 *  StringList_print(&mylist);
 * 
 */

#include <string.h>
#ifndef ___STRINGLIST_H
#define ___STRINGLIST_H


typedef struct StringElement StringElement; // element de chaine de caractere
struct StringElement {
  char *string;            // chaine
  StringElement *previous; // element precedent (NULL si c'est le premier)
  StringElement *next;     // element suivant   (NULL si c'est la fin fin)
};

typedef struct StringList {
   StringElement *root; // racine
   StringElement *end;  // dernier element
} StringList;

StringList* StringList_init(StringList *lst); // permet d'initialiser la liste (pointeur NULL)
void StringList_free(StringList *lst); // permet de vider completement la liste (liberer les ressources)

StringElement* StringList_add(StringList *lst, char *str); // ajouter
StringElement* StringList_addUniqueSorted(StringList *lst, char *str); // ajout mais en ordre et unique

// methode utilitaire
void StringList_print(StringList *lst);
int StringList_length(StringList *lst);




/**
 * Initialise les pointeurs a NULL (debut et fin)
 */
StringList* StringList_init(StringList *lst) {
  lst->root = NULL;
  lst->end  = NULL;
  return lst;
}


/**
 * Ajoute un nouveau noeud a la liste
 * Si la racine est nulle, on ajoute a la racine
 *    end = racine = nouveau noeud
 * Sinon, on ajoute apres le dernier noeud (end)
 *    end = nouveau noeud
 */
StringElement* StringList_add(StringList *lst, char *str) {
  StringElement *newStr = (StringElement*)malloc(sizeof(StringElement));

  newStr->string = (char *)malloc(strlen(str)+1);
  strcpy(newStr->string, str);
  newStr->previous = NULL;
  newStr->next = NULL;

  if ( !lst->root ) {
    lst->root = newStr;
    lst->end  = newStr;
  } else {
    StringElement *last = lst->end;
    if ( last ) { // si la fin est null et la racine est null.. on a un sacre probleme!
      last->next = newStr;
      newStr->previous = last;
      lst->end = newStr;
    }
  }
  return newStr;
}

StringElement* StringList_addUniqueSorted(StringList *lst, char *str) {
  if ( !lst->root ) {
    StringElement *newStr = (StringElement*)malloc(sizeof(StringElement));
    newStr->string = (char *)malloc(strlen(str)+1);
    strcpy(newStr->string, str);
    newStr->previous = NULL;
    newStr->next = NULL;

    lst->root = newStr;
    lst->end = newStr;
    return newStr;
  } else {
    // on regarde chaque chaine et on insere lorsque str < next->string;
    // si str == next->string, on ne fait rien
    StringElement *next = lst->root;
    int diff;
    while ( next ) {
      diff = strcmp(str, next->string);
      if ( diff > 0 ) { // on doit continuer puisque la chaine est plus grande
        if ( next->next ) { // il y a un suivant?
          next = next->next;
        } else { // non, alors c'est le noeud de la fin
          StringElement *newStr = (StringElement*)malloc(sizeof(StringElement));
          newStr->string = (char *)malloc(strlen(str)+1);
          strcpy(newStr->string, str);

          lst->end = newStr;
          next->next = newStr;

          newStr->previous = next;
          newStr->next = NULL;
          return newStr;
        }

      } else if (diff < 0 ) { // on doit l'inserer avant

        StringElement *newStr = (StringElement*)malloc(sizeof(StringElement));
        newStr->string = (char *)malloc(strlen(str)+1);
        strcpy(newStr->string, str);

        if ( next->previous == NULL ) { // on insere a la racine (avant le premier noeud)
          lst->root = newStr;
          newStr->previous = NULL;
          newStr->next = next;
          next->previous = newStr;

        } else { // on est au milieu...  donc on change les pointeurs (next / previous)

          next->previous->next = newStr; // gauche
          newStr->previous = next->previous;

          next->previous = newStr; // droite
          newStr->next = next;     // droite
        }
        return newStr;

      } else if ( diff == 0 ) {
        return NULL; // on est tombe sur la meme chaine...
      }
    }

  }
  return NULL;
}
/*
 b
 a --> a b (lst.root = a,
            a.previous=b.previous,
            a.next = b,
            b.previous = a)
 ab --> a ab b ( a.next.previous = ab,
                 ab.next = a.next;
                 ab.previous = a;
                 a.next = ab;
 c --> a ab b c ( c.next = b.next, b.next = c, c.previous = b )
*/

void StringList_free(StringList *lst) {
  StringElement *next = lst->root;
  StringElement *previous;

  while ( next ) {
    free(next->string);
    previous = next;
    next = next->next;
    free(previous);
  };

  lst->root = NULL;
  lst->end  = NULL;
}

/**
 * Affiche la liste des strings (#n. ... "\n")
 * @param *lst pointeur vers la liste.
 */
void StringList_print(StringList *lst) {
  if ( lst->root ) {
    StringElement *next = lst->root;
    int iElement = 0;
    while ( next ) {
      printf("%03d. %s\n",iElement++, next->string);
      next = next->next;
    }
  }
}

/**
 * Nombre d'element dans la liste
 * @param *lst pointeur vers la liste.
 * @return Le nombre d'element
 */
int StringList_length(StringList *lst) {
   int l = 0;
   if ( lst->root ) {
     StringElement *next = lst->root;
     while (next) {
       l++;
       next = next->next;
     }
   }
   return l;
}
#endif