/********************************/
/********************************/
/* Prototypes des fonctions TP1 */
/********************************/
/********************************/

/***************************/
/***************************/
/*  Exercice préliminaire  */
/***************************/
/***************************/

// Doublement des majuscules dans une chaîne
char *double_upper(char *s);

/******************************/
/******************************/
/*  Liste doublement chaînées */
/******************************/
/******************************/

// Type utilisé pour représenter une cellule d'une liste doublement chaînée
struct dlist {
  int value;
  struct dlist *next, *prev;
};

// On définit dlist comme un synonyme de struct dlist.
typedef struct dlist dlist;

/**********************/
/* Fonctions basiques */
/**********************/

// Création d'une liste vide
dlist *create_empty_dlist();

// Ajout d'une nouvelle valeur (à droite ou à gauche de la cellule prise en
// entrée)
dlist *add_left_to_dlist(dlist *list, int value);
dlist *add_right_to_dlist(dlist *list, int value);

// Suppression d'une cellule (attention à mettre à jour les pointeurs des
// cellules adjacentes)
void del_cell_dlist(dlist *list);

// Libération d'une dlist entière
void free_dlist(dlist *list);

/*********************/
/* Fonctions de test */
/*********************/

// Génération d'une dlist contenant les n premiers entiers dans l'ordre:
// 0 1 2 3 4 5 6 7 ...n-1.
dlist *iota_dlist(int n);

// Affichage des valeurs de toutes les cellules d'une liste, dans l'ordre.
// Pensez à tester vos fonctions précédentes avec print_dlist !
void print_dlist(dlist *list);

// Génération d'une dlist aléatoire (on prend en argument la longueur voulue et
// la valeur maximale).
//
// Utiliser la fonction random() pour générer des valeurs entières (la
// documentation est accessible par man 3 random), et utiliser l'opérateur
// modulo % pour ne pas dépasser la valeur maximale demandée.
//
// Par exemple, create_random_dlist(5, 10) renvoie une liste contenant 5 valeurs
// inférieures à 10. Elle peut donc renvoyer, par exemple la liste 3 7 2 5 8.
dlist *create_random_dlist(int length, int max);

/**********************************/
/* Fonctions utilisant des listes */
/**********************************/

// Crée une copie d'une dlist et renvoie cette copie.
dlist *copy_dlist(dlist *list);

// Inversion d'une dlist: retourne une nouvelle dlist obtenue en inversant
// l'ordre des valeurs dans celle prise en argument.
dlist *reverse_dlist(dlist *list);

// Fusion alternée: retourne une nouvelle dlist obtenue en insérant de façon
// alternée les valeurs des deux listes prises en argument. Si une des deux
// listes est plus longue, les valeurs restantes sont ajoutées à la fin de la
// liste renvoyée.
dlist *mix_dlist(dlist *list1, dlist *list2);

// Place les cellules de valeur paire avant celles de numéro pair.
// Par exemple, si la liste contient la séquence 1 2 3 4 5 6 7 8, elle doit être
// modifiée pour contenir 2 4 6 8 1 3 5 7
void evenodd_dlist(dlist *list);

/****************/
/* Tri à bulles */
/****************/

// Tri à bulles d'une dlist
void bubblesort_dlist(dlist *list);

/**************/
/* Tri fusion */
/**************/

// Retire la première moitié des éléments de la liste prise en argument.
// Retourne ces éléments dans une nouvelle liste.
dlist *split_dlist(dlist *list);

// Les deux listes prises en arguments de la fonction merge_dlist sont supposées
// triées. Fusionne ces deux listes dans la première pour obtenir une unique
// liste triée.
void merge_dlist(dlist *list1, dlist *list2);

// Tri fusion d'une liste, en utilisant les fonctions auxiliaires précédentes.
void mergesort_dlist(dlist *list);

/**************/
/* Tri rapide */
/**************/

// Retire tous les éléments strictement plus petits que l'entier pivot dans la
// liste prise en argument, et retourne ces éléments dans une nouvelle liste.
dlist *pivot_dlist(int pivot, dlist *list);

// Tri rapide d'une liste, en utilisant la fonction auxiliaire précédente.
void quicksort_dlist(dlist *list);