123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961 |
- /*************************************/
- /* Auteur : Rémi Synave */
- /* Date de création : 01/03/07 */
- /* Date de modification : 15/03/15 */
- /* Version : 0.4 */
- /*************************************/
- /***************************************************************************/
- /* This file is part of a2ri. */
- /* */
- /* a2ri is free software: you can redistribute it and/or modify it */
- /* under the terms of the GNU Lesser General Public License as published */
- /* by the Free Software Foundation, either version 3 of the License, or */
- /* (at your option) any later version. */
- /* */
- /* a2ri is distributed in the hope that it will be useful, */
- /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
- /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
- /* GNU Lesser General Public License for more details. */
- /* */
- /* You should have received a copy of the GNU Lesser General Public */
- /* License along with a2ri. */
- /* If not, see <http://www.gnu.org/licenses/>. */
- /***************************************************************************/
- #include "util.h"
- /********** INTERMEDIATE TYPES AND FUNCTIONS **********/
- /* Les fonctions intermédiaires sont préfixées de IF */
- /* et les types intermédiaires de IT */
- int
- IFlist_int_etape_tri_rapide (
- int *t,
- int min,
- int max,
- int type)
- {
- int temp = t[max];
-
- while (max > min)
- {
- if (type == ASC)
- {
- while (max > min && t[min] <= temp)
- min++;
- }
- else
- {
- while (max > min && t[min] > temp)
- min++;
- }
- if (max > min)
- {
- t[max] = t[min];
- max--;
- if (type == ASC)
- {
- while (max > min && t[max] >= temp)
- max--;
- }
- else
- {
- while (max > min && t[max] < temp)
- max--;
- }
- if (max > min)
- {
- t[min] = t[max];
- min++;
- }
- }
- }
- t[max] = temp;
- return (max);
- }
- void
- IFlist_int_tri_rapide (
- int *t,
- int deb,
- int fin,
- int type)
- {
- int mil;
-
- if (deb < fin)
- {
- mil = IFlist_int_etape_tri_rapide (t, deb, fin, type);
- if (mil - deb > fin - mil)
- {
- IFlist_int_tri_rapide (t, mil + 1, fin, type);
- IFlist_int_tri_rapide (t, deb, mil - 1, type);
- }
- else
- {
- IFlist_int_tri_rapide (t, deb, mil - 1, type);
- IFlist_int_tri_rapide (t, mil + 1, fin, type);
- }
- }
- }
- int
- IFlist_double_etape_tri_rapide (
- double *t,
- int min,
- int max,
- int type)
- {
- double temp = t[max];
-
- while (max > min)
- {
- if (type == ASC)
- {
- while (max > min && t[min] <= temp)
- min++;
- }
- else
- {
- while (max > min && t[min] > temp)
- min++;
- }
- if (max > min)
- {
- t[max] = t[min];
- max--;
- if (type == ASC)
- {
- while (max > min && t[max] >= temp)
- max--;
- }
- else
- {
- while (max > min && t[max] < temp)
- max--;
- }
- if (max > min)
- {
- t[min] = t[max];
- min++;
- }
- }
- }
- t[max] = temp;
- return (max);
- }
- void
- IFlist_double_tri_rapide (
- double *t,
- int deb,
- int fin,
- int type)
- {
- int mil;
-
- if (deb < fin)
- {
- mil = IFlist_double_etape_tri_rapide (t, deb, fin, type);
- if (mil - deb > fin - mil)
- {
- IFlist_double_tri_rapide (t, mil + 1, fin, type);
- IFlist_double_tri_rapide (t, deb, mil - 1, type);
- }
- else
- {
- IFlist_double_tri_rapide (t, deb, mil - 1, type);
- IFlist_double_tri_rapide (t, mil + 1, fin, type);
- }
- }
- }
- /********** MAIN FUNCTIONS **********/
- /**
- Affiche un message d'erreur et stoppe le programme si la condition n'est pas satisfaite
- @param cond condition à satisfaire
- @param str message d'erreur à afficher dans le cas contraire
- @return aucun
- **/
- void
- a2ri_erreur_critique_si (
- int cond,
- const char * const str)
- {
- if (cond)
- {
- a2ri_printf_debug ("%s\n", str);
- exit (EXIT_FAILURE);
- }
- }
- /**
- Renvoie un entier compris entre min et max
- @param min valeur minimale
- @param max valeur maximale
- @return un entier
- **/
- int
- rand_int (
- int min,
- int max)
- {
- return ((((int) rand ()) % (max - min + 1)) + min);
- }
- /**
- Retourne la position de la valeur tosearch, -1 sinon
- @param list tableau d'entier
- @param size taille du tableau
- @param tosearch entier à chercher
- @return position de la première occurence, -1 s'il n'apparait pas dans le tableau
- */
- int
- list_int_contains (
- const int * const list,
- int size,
- int tosearch)
- {
- int i;
- for (i = 0; i < size; i++)
- if (list[i] == tosearch)
- return i;
- return -1;
- }
- /**
- Retourne la position de la valeur tosearch, -1 sinon
- @param list tableau de réels
- @param size taille du tableau
- @param tosearch réel à chercher
- @return position de la première occurence, -1 s'il n'apparait pas dans le tableau
- */
- int
- list_double_contains (
- const double * const list,
- int size,
- double tosearch)
- {
- int i;
- for (i = 0; i < size; i++)
- if (list[i] == tosearch)
- return i;
- return -1;
- }
- /**
- Clone la liste
- @param list la liste à cloner
- @param size taille de la liste
- @param list_clone liste clonée
- @return 1 si la liste est bien clonée, 0 sinon
- **/
- int
- list_int_clone (
- const int * const list,
- int size,
- int **list_clone)
- {
- (*list_clone) = (int *) malloc (size * sizeof (int));
- a2ri_erreur_critique_si (*list_clone == NULL,
- "erreur allocation memoire pour list_clone\nlist_int_clone");
- if ((*list_clone) == NULL)
- return 0;
- for (int i = 0; i < size; i++)
- (*list_clone)[i] = list[i];
- return 1;
- }
- /**
- Clone la liste
- @param list la liste à cloner
- @param size taille de la liste
- @param list_clone liste clonée
- @return 1 si la liste est bien clonée, 0 sinon
- **/
- int
- list_double_clone (
- const double * const list,
- int size,
- double **list_clone)
- {
- (*list_clone) = (double *) malloc (size * sizeof (double));
- a2ri_erreur_critique_si (*list_clone == NULL,
- "erreur allocation memoire pour list_clone\nlist_double_clone");
- if ((*list_clone) == NULL)
- return 0;
- for (int i = 0; i < size; i++)
- (*list_clone)[i] = list[i];
- return 1;
- }
- /**
- calcul de l'intersection de deux liste d'entier
- @param list1 premiere liste d'entier
- @param size1 taille de la premiere liste
- @param list2 seconde liste d'entier
- @param size2 taille de la seconde liste
- @param list_inter liste d'entier représentatnt l'intersection de list1 et list2
- @param size_list_inter taille de la liste d'intersection
- @return aucun
- */
- void
- list_int_intersection (
- const int * const list1,
- int size1,
- const int * const list2,
- int size2,
- int **list_inter,
- int *size_list_inter)
- {
- *list_inter = NULL;
- *size_list_inter = 0;
- for (int i = 0; i < size1; i++)
- {
- if (list_int_contains (list2, size2, list1[i]) != -1)
- list_int_add (list_inter,
- size_list_inter,
- list1[i],
- WITHOUT_REDUNDANCE);
- }
- }
- /**
- Ajoute l'entier toadd en fin de liste
- @param list pointeur sur le premier élément du tableau
- @param size pointeur sur la taille du tableau
- @param toadd entier à ajouter
- @param add_type WITH_REDUNDANCE ou WITHOUT_REDUNDANCE <BR> avec redondance : ajout simple <BR> sans redondance : ajout si la valeur n'apparait pas dans la liste
- @return 1 si succès, 0 sinon
- */
- int
- list_int_add (
- int **list,
- int *size,
- int toadd,
- int add_type)
- {
- if (add_type == WITHOUT_REDUNDANCE)
- if (list_int_contains (*list, *size, toadd) != -1)
- return 0;
-
- int *newlist = (int *) malloc (((*size) + 1) * sizeof (int));
- a2ri_erreur_critique_si (newlist == NULL,
- "erreur allocation memoire pour newlist\nlist_int_add");
-
- int i;
- for (i = 0; i < *size; i++)
- newlist[i] = (*list)[i];
- newlist[*size] = toadd;
- free (*list);
- (*list) = newlist;
- *size = (*size) + 1;
-
- return 1;
- }
- /**
- Ajoute le réel toadd en fin de liste
- @param list pointeur sur le premier élément du tableau
- @param size pointeur sur la taille du tableau
- @param toadd réel à ajouter
- @param add_type WITH_REDUNDANCE ou WITHOUT_REDUNDANCE <BR> avec redondance : ajout simple <BR> sans redondance : ajout si la valeur n'apparait pas dans la liste
- @return 1 si succès, 0 sinon
- */
- int
- list_double_add (
- double **list,
- int *size,
- double toadd,
- int add_type)
- {
- if (add_type == WITHOUT_REDUNDANCE)
- if (list_double_contains (*list, *size, toadd) != -1)
- return 0;
-
- double *newlist = (double *) malloc (((*size) + 1) * sizeof (double));
- a2ri_erreur_critique_si (newlist == NULL,
- "erreur allocation memoire pour newlist\nlist_double_add");
- int i;
- for (i = 0; i < *size; i++)
- newlist[i] = (*list)[i];
- newlist[*size] = toadd;
- free (*list);
- (*list) = newlist;
- *size = (*size) + 1;
-
- return 1;
- }
- /**
- Enlève la valeur à la position index
- @param list pointeur sur le premier élément du tableau
- @param size pointeur sur la taille du tableau
- @param index position de l'entier à supprimer
- @return 1 si succès, 0 sinon (cas où index>=size)
- */
- int
- list_int_remove (
- int **list,
- int *size,
- int index)
- {
- int *temp;
- if (index >= *size)
- return 0;
- if(*size==1)
- {
- free(*list);
- *size=0;
- *list=NULL;
- return 1;
- }
- for (int i = index; i < (*size) - 1; i++)
- (*list)[i] = (*list)[i + 1];
- temp = (int *) realloc (*list, ((*size) - 1) * sizeof (int));
- a2ri_erreur_critique_si (temp == NULL && *size != 0,
- "erreur allocation memoire pour temp\nlist_int_remove");
- *list=temp;
- *size = (*size) - 1;
- a2ri_erreur_critique_si (*list == NULL && *size != 0,
- "erreur allocation memoire pour list\nlist_int_remove");
- return 1;
- }
- /**
- Enlève la valeur à la position index
- @param list pointeur sur le premier élément du tableau
- @param size pointeur sur la taille du tableau
- @param index position du réel à supprimer
- @return 1 si succès, 0 sinon (cas où index>=size)
- */
- int
- list_double_remove (
- double **list,
- int *size,
- int index)
- {
- double *temp;
- if (index >= *size)
- return 0;
- if(*size==1)
- {
- free(*list);
- *size=0;
- *list=NULL;
- return 1;
- }
- for (int i = index; i < (*size) - 1; i++)
- (*list)[i] = (*list)[i + 1];
- temp = (double *) realloc (*list, ((*size) - 1) * sizeof (double));
- a2ri_erreur_critique_si (temp == NULL && *size != 0,
- "erreur allocation memoire pour temp\nlist_double_remove");
- *list=temp;
- *size = (*size) - 1;
- a2ri_erreur_critique_si (*list == NULL && *size != 0,
- "erreur allocation memoire pour list\nlist_double_remove");
- return 1;
- }
- /**
- Mélange la liste d'entier
- @param list tableau d'entier
- @param size taille du tableau
- @return aucun
- */
- void
- list_int_mix (
- int *list,
- int size)
- {
- int *list_clone = NULL,
- size_clone;
- list_int_clone (list, size, &list_clone);
- size_clone = size;
- for (int i = 0; i < size; i++)
- {
- int index = rand_int (0, size_clone - 1);
- list[i] = list_clone[index];
- list_int_remove (&list_clone, &size_clone, index);
- }
- }
- /**
- Mélange la liste de réel
- @param list tableau de réel
- @param size taille du tableau
- @return aucun
- */
- void
- list_double_mix (
- double *list,
- int size)
- {
- double *list_clone = NULL;
- int size_clone;
- list_double_clone (list, size, &list_clone);
- size_clone = size;
- for (int i = 0; i < size; i++)
- {
- int index = rand_int (0, size_clone - 1);
- list[i] = list_clone[index];
- list_double_remove (&list_clone, &size_clone, index);
- }
- }
- /**
- Affichage de la liste d'entier
- @param list tableau d'entier
- @param size taille du tableau
- @return aucun
- */
- void
- list_int_display (
- const int * const list,
- int size)
- {
- int i;
- if (size == 0)
- return;
- printf ("liste :\n%d", list[0]);
- for (i = 1; i < size; i++)
- printf (" - %d", list[i]);
- printf ("\n");
- }
- /**
- Affichage de la liste de réel
- @param list tableau de réel
- @param size taille du tableau
- @return aucun
- */
- void
- list_double_display (
- const double * const list,
- int size)
- {
- int i;
- if (size == 0)
- return;
- printf ("liste :\n%lf", list[0]);
- for (i = 1; i < size; i++)
- printf (" - %lf", list[i]);
- printf ("\n");
- }
- /**
- Inverse la liste d'entier
- @param list tableau d'entier
- @param size taille du tableau
- @return aucun
- */
- void
- list_int_reverse (
- int *list,
- int size)
- {
- int *listechang = (int *) malloc (size * sizeof (int));
- a2ri_erreur_critique_si (listechang == NULL,
- "erreur allocation memoire pour list\nlist_int_reverse");
- int i;
- for (i = 0; i < size; i++)
- listechang[i] = list[i];
- for (i = 0; i < size; i++)
- list[i] = listechang[size - 1 - i];
- free (listechang);
- }
- /**
- Inverse la liste de réel
- @param list tableau de réel
- @param size taille du tableau
- @return aucun
- */
- void
- list_double_reverse (
- double *list,
- int size)
- {
- double *listechang = (double *) malloc (size * sizeof (double));
- a2ri_erreur_critique_si (listechang == NULL,
- "erreur allocation memoire pour list\nlist_double_reverse");
- int i;
- for (i = 0; i < size; i++)
- listechang[i] = list[i];
- for (i = 0; i < size; i++)
- list[i] = listechang[size - 1 - i];
- free (listechang);
- }
- /**
- Décale la liste d'entier à droite de "shift" position(s)
- @param list tableau d'entier
- @param size taille du tableau
- @param shift nombre de décalage à droite
- @return aucun
- */
- void
- list_int_shift_right (
- int *list,
- int size,
- int shift)
- {
- int *listechang = (int *) malloc (size * sizeof (int));
- a2ri_erreur_critique_si (listechang == NULL,
- "erreur allocation memoire pour list\nlist_int_shift_right");
- int i;
- for (i = 0; i < size; i++)
- listechang[i] = list[i];
- for (i = 0; i < size; i++)
- list[i] = listechang[(i - shift + size) % size];
- free (listechang);
- }
- /**
- Décale la liste d'entier à gauche de "shift" position(s)
- @param list tableau d'entier
- @param size taille du tableau
- @param shift nombre de décalage à gauche
- @return aucun
- */
- void
- list_int_shift_left (
- int *list,
- int size,
- int shift)
- {
- int *listechang = (int *) malloc (size * sizeof (int));
- a2ri_erreur_critique_si (listechang == NULL,
- "erreur allocation memoire pour list\nlist_int_shift_left");
- int i;
- for (i = 0; i < size; i++)
- listechang[i] = list[i];
- for (i = 0; i < size; i++)
- list[i] = listechang[(i + shift) % size];
- free (listechang);
- }
- /**
- Décale la liste de réel à droite de "shift" position(s)
- @param list tableau de réel
- @param size taille du tableau
- @param shift nombre de décalage à droite
- @return aucun
- */
- void
- list_double_shift_right (
- double *list,
- int size,
- int shift)
- {
- double *listechang = (double *) malloc (size * sizeof (double));
- a2ri_erreur_critique_si (listechang == NULL,
- "erreur allocation memoire pour list\nlist_double_shift_right");
- int i;
- for (i = 0; i < size; i++)
- listechang[i] = list[i];
- for (i = 0; i < size; i++)
- list[i] = listechang[(i - shift + size) % size];
- free (listechang);
- }
- /**
- Décale la liste de réel à gauche de "shift" position(s)
- @param list tableau de réel
- @param size taille du tableau
- @param shift nombre de décalage à gauche
- @return aucun
- */
- void
- list_double_shift_left (
- double *list,
- int size,
- int shift)
- {
- double *listechang = (double *) malloc (size * sizeof (double));
- a2ri_erreur_critique_si (listechang == NULL,
- "erreur allocation memoire pour list\nlist_double_shift_left");
- int i;
- for (i = 0; i < size; i++)
- listechang[i] = list[i];
- for (i = 0; i < size; i++)
- list[i] = listechang[(i + shift) % size];
- free (listechang);
- }
- /**
- Trouve le plus petit entier de la liste
- @param list tableau d'entier
- @param size taille du tableau
- @return le plus petit entier
- */
- int
- list_int_min (
- const int * const list,
- int size)
- {
- int min = list[0];
- for (int i = 1; i < size; i++)
- if (list[i] < min)
- min = list[i];
- return min;
- }
- /**
- Trouve le plus grand entier de la liste
- @param list tableau d'entier
- @param size taille du tableau
- @return le plus grand entier
- */
- int
- list_int_max (
- const int * const list,
- int size)
- {
- int max = list[0];
- for (int i = 1; i < size; i++)
- if (list[i] > max)
- max = list[i];
- return max;
- }
- /**
- Trouve le plus petit réel de la liste
- @param list tableau de réel
- @param size taille du tableau
- @return le plus petit réel
- */
- double
- list_double_min (
- const double * const list,
- int size)
- {
- double min = list[0];
- for (int i = 1; i < size; i++)
- if (list[i] < min)
- min = list[i];
- return min;
- }
- /**
- Trouve le plus grand réel de la liste
- @param list tableau de réel
- @param size taille du tableau
- @return le plus grand réel
- */
- double
- list_double_max (
- const double * const list,
- int size)
- {
- double max = list[0];
- for (int i = 1; i < size; i++)
- if (list[i] > max)
- max = list[i];
- return max;
- }
- /**
- Calcul de la moyenne d'une liste d'entier
- @param list tableau d'entier
- @param size taille du tableau
- @return moyenne de la liste
- */
- double
- list_int_average (
- const int * const list,
- int size)
- {
- int somme = 0;
- for (int i = 0; i < size; i++)
- somme += list[i];
- return (somme * 1.0) / (size * 1.0);
- }
- /**
- Calcul de la variance d'une liste d'entier
- @param list tableau d'entier
- @param size taille du tableau
- @return variance de la liste
- */
- double
- list_int_variance (
- const int * const list,
- int size)
- {
- double moyenne = list_int_average (list, size),
- somme = 0;
- for (int i = 0; i < size; i++)
- somme += (list[i] - moyenne) * (list[i] - moyenne);
- return somme / (size * 1.0);
- }
- /**
- Calcul de la moyenne d'une liste de réel
- @param list tableau de réel
- @param size taille du tableau
- @return moyenne de la liste
- */
- double
- list_double_average (
- const double * const list,
- int size)
- {
- double somme = 0;
- for (int i = 0; i < size; i++)
- somme += list[i];
- return somme / (size * 1.0);
- }
- /**
- Calcul de la variance d'une liste de réel
- @param list tableau de réel
- @param size taille du tableau
- @return variance de la liste
- */
- double
- list_double_variance (
- const double * const list,
- int size)
- {
- double moyenne = list_double_average (list, size);
- double somme = 0;
- for (int i = 0; i < size; i++)
- somme += (list[i] - moyenne) * (list[i] - moyenne);
- return somme / (size * 1.0);
- }
- /**
- Tri de la liste d'entier
- @param list tableau d'entier
- @param size taille du tableau
- @param type ASC ou DESC : ordre croissant ou décroissant
- @return aucun
- */
- void
- list_int_sort (
- int *list,
- int size,
- int type)
- {
- IFlist_int_tri_rapide (list, 0, size - 1, type);
- }
- /**
- Tri de la liste de réel
- @param list tableau de réel
- @param size taille du tableau
- @param type ASC ou DESC : ordre croissant ou décroissant
- @return aucun
- */
- void
- list_double_sort (
- double *list,
- int size,
- int type)
- {
- IFlist_double_tri_rapide (list, 0, size - 1, type);
- }
- /**
- Initialisation à zéro d'un temps
- @param t pointeur vers un objet temps
- @return aucun
- */
- void
- a2ri_time_init (
- a2ri_time * t)
- {
- t->tv_sec = 0;
- t->tv_usec = 0;
- }
- /**
- Acquisition de l'heure actuelle
- @param t pointeur vers un objet temps
- @return aucun
- */
- a2ri_time
- a2ri_get_time (
- )
- {
- a2ri_time retour;
- gettimeofday (&retour, NULL);
- return retour;
- }
- /**
- Conversion d'un temps en double
- @param deb le temps inférieur
- @param fin le temps supérieur
- @return la conversion en double
- */
- double
- a2ri_time_interval_to_double (
- a2ri_time deb,
- a2ri_time fin)
- {
- return ((fin.tv_sec - deb.tv_sec) * 1.0) +
- ((fin.tv_usec - deb.tv_usec) / 1000000.0);
- }
- /**
- Affichage du temps séparant les deux variables en secondes
- @param debut borne de début
- @param fin borne de fin
- @return aucun
- */
- void
- a2ri_display_interval_time (
- const char * const str,
- a2ri_time deb,
- a2ri_time fin)
- {
- printf ("%s%lf\n",
- str,
- ((fin.tv_sec - deb.tv_sec) * 1.0) +
- ((fin.tv_usec - deb.tv_usec) / 1000000.0));
- }
|