Projet Informatique Théorique 2016
Instructions et Documentation
ensemble.c
1 /*
2  * Ce fichier fait partie d'un projet de programmation donné en Licence 3
3  * à l'Université de Bordeaux
4  *
5  * Copyright (C) 2014 Adrien Boussicault
6  *
7  * This Library is free software: you can redistribute it and/or modify
8  * it under the terms of the GNU General Public License as published by
9  * the Free Software Foundation, either version 2 of the License, or
10  * (at your option) any later version.
11  *
12  * This Library is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this Library. If not, see <http://www.gnu.org/licenses/>.
19  */
20 
21 
22 #define _GNU_SOURCE
23 
24 #include "ensemble.h"
25 #include "outils.h"
26 #include "table.h"
27 
28 #include <stdlib.h>
29 #include <stdio.h>
30 
31 
32 int* allouer_element( int val ){
33  int* result = (int*) xmalloc( sizeof(int) );
34  (*result) = val;
35  return result;
36 }
37 
38 void supprimer_element( int* element ){
39  xfree( element );
40 }
41 
42 void next_iterators( Table_iterateur * it1, Table_iterateur * it2 ){
43  *it1 = iterateur_suivant_table(*it1);
44  *it2 = iterateur_suivant_table(*it2);
45 }
46 
47 int comparer_ensemble( const Ensemble* ens1, const Ensemble* ens2 ){
48  Table_iterateur it1, it2;
49 
50  it1 = premier_iterateur_table( ens1->table );
51  it2 = premier_iterateur_table( ens2->table );
52  for(
53  ;
54  ( ! iterateur_est_vide(it1) ) && ( ! iterateur_est_vide(it2) );
55  next_iterators( &it1, &it2 )
56  ){
57  int cmp;
58  if( ens1->comparer_element ){
59  cmp = ens1->comparer_element( get_cle( it1 ), get_cle( it2 ) );
60  }else{
61  cmp = get_cle( it1 ) - get_cle( it2 );
62  }
63  if( cmp > 0 ) return 1;
64  if( cmp < 0 ) return -1;
65  }
66  if( iterateur_est_vide(it1) && iterateur_est_vide(it2) )
67  return 0;
68  if( iterateur_est_vide(it1) )
69  return -1;
70  return 1;
71 }
72 
73 
74 Ensemble * creer_ensemble(
75  int (*comparer_element)( const intptr_t elem1, const intptr_t elem2 ),
76  intptr_t (*copier_element)( const intptr_t elem ),
77  void (*supprimer_element)(intptr_t elem )
78 ){
79  Ensemble * result = (Ensemble*) xmalloc( sizeof(Ensemble) );
80  result->table = creer_table(
81  comparer_element, copier_element, supprimer_element
82  );
83  result->comparer_element = comparer_element;
84  result->copier_element = copier_element;
85  result->supprimer_element = supprimer_element;
86  return result;
87 }
88 
89 void liberer_ensemble( Ensemble * ens ){
90  if(ens){
91  liberer_table( ens->table );
92  xfree( ens );
93  }
94 }
95 
96 void ajouter_element( Ensemble * ensemble, const intptr_t element ){
97  add_table( ensemble->table, element, (intptr_t) NULL );
98 }
99 
100 
101 void action_ajouter_element( const intptr_t element, void* ens ){
102  ajouter_element( (Ensemble*) ens, element );
103 }
104 
105 void ajouter_elements( Ensemble * ens1, const Ensemble * ens2 ){
106  pour_tout_element( ens2, action_ajouter_element, ens1 );
107 }
108 
109 void transferer_elements_et_libere(
110  Ensemble * destination, Ensemble * source
111 ){
112  ajouter_elements( destination, source );
113  liberer_ensemble( source );
114 }
115 
116 void transferer_elements(
117  Ensemble * destination, Ensemble * source
118 ){
119  ajouter_elements( destination, source );
120  vider_ensemble( source );
121 }
122 
123 void retirer_element( Ensemble * ensemble, const intptr_t element ){
124  delete_table( ensemble->table, element );
125 }
126 
127 void action_retirer_elements( const intptr_t element, void* ens ){
128  retirer_element( (Ensemble*) ens, element );
129 }
130 
131 void retirer_elements( Ensemble * ens1, const Ensemble * ens2 ){
132  pour_tout_element( ens2, action_retirer_elements, ens1 );
133 }
134 
135 void vider_ensemble( Ensemble * ensemble ){
136  vider_table( ensemble->table );
137 }
138 
139 int est_dans_l_ensemble( const Ensemble * ensemble, intptr_t element ){
140  Table_iterateur it = trouver_table( ensemble->table, element );
141  return ! avl_t_is_null( &it );
142 }
143 
144 void action_taille_ensemble( const intptr_t element, void* taille ){
145  (*(int*) taille)+=1;
146 }
147 
148 unsigned int taille_ensemble( const Ensemble* ensemble ){
149  int taille = 0;
150  pour_tout_element( ensemble, action_taille_ensemble, &taille );
151  return taille;
152 }
153 
154 typedef struct {
155  void (*print_element)( const intptr_t cle );
157 
158 void action_print_ensemble( const intptr_t element, void* data ){
159  data_print_ensemble* info = ( data_print_ensemble* ) data;
160  if( info->print_element ){
161  info->print_element( element );
162  }else{
163  printf( "%ld", element );
164  }
165  printf( ", " );
166 }
167 
168 void print_ensemble(
169  const Ensemble* ens,
170  void (*print_element)( const intptr_t cle )
171 ){
172  data_print_ensemble data;
173  data.print_element = print_element;
174 
175  printf( "{" );
176  pour_tout_element( ens, action_print_ensemble, &data );
177  printf( "}" );
178 }
179 
180 
181 typedef struct {
182  void (* action )( const intptr_t element, void* data );
183  void* data;
185 
186 void action_pour_tout_element_ensemble( const intptr_t cle, intptr_t valeur, void* data ){
188  info->action( cle, info->data );
189 }
190 
191 void pour_tout_element(
192  const Ensemble* ensemble,
193  void (* action )( const intptr_t element, void* data ),
194  void* data
195 ){
197  data1.action = action;
198  data1.data = data;
200  ensemble->table, action_pour_tout_element_ensemble, &data1
201  );
202 }
203 
204 void swap_ensemble( Ensemble* ens1, Ensemble* ens2 ){
205  void* tmp = ens1->table;
206  ens1->table = ens2->table;
207  ens2->table = tmp;
208 }
209 void deplacer_ensemble( Ensemble* ens1, Ensemble* ens2 ){
210  swap_ensemble( ens1, ens2 );
211  liberer_ensemble( ens2 );
212 }
213 
214 Ensemble* copier_ensemble( const Ensemble* ensemble ){
215  Ensemble* res = creer_ensemble(
216  ensemble->comparer_element, ensemble->copier_element,
217  ensemble->supprimer_element
218  );
219  ajouter_elements( res, ensemble );
220  return res;
221 }
222 
223 Ensemble * creer_union_ensemble( const Ensemble* ens1, const Ensemble* ens2 ){
224  Ensemble * res = copier_ensemble( ens1 );
225  ajouter_elements( res, ens2 );
226  return res;
227 }
228 
229 Ensemble * creer_difference_ensemble(
230  const Ensemble* ens1, const Ensemble* ens2
231 ){
232  Ensemble * res = copier_ensemble( ens1 );
233  retirer_elements( res, ens2 );
234  return res;
235 }
236 
237 Ensemble * creer_intersection_ensemble(
238  const Ensemble* ens1, const Ensemble* ens2
239 ){
240  Ensemble *tmp, *res;
241  tmp = creer_difference_ensemble( ens1, ens2 );
242  res = creer_difference_ensemble( ens1, tmp );
243  liberer_ensemble( tmp );
244  return res;
245 }
246 
247 Ensemble_iterateur trouver_ensemble(
248  const Ensemble* ensemble, const intptr_t element
249 ){
250  return trouver_table( ensemble->table, element );
251 }
252 
253 Ensemble_iterateur premier_iterateur_ensemble( const Ensemble* ensemble ){
254  return premier_iterateur_table( ensemble->table );
255 }
256 
257 Ensemble_iterateur iterateur_suivant_ensemble(
258  const Ensemble_iterateur iterateur
259 ){
260  return iterateur_suivant_table( iterateur );
261 }
262 
263 Ensemble_iterateur iterateur_precedent_ensemble( Ensemble_iterateur iterateur ){
264  return iterateur_precedent_table( iterateur );
265 }
266 
267 int iterateur_ensemble_est_vide( Ensemble_iterateur iterateur ){
268  return iterateur_est_vide( iterateur );
269 }
270 
271 intptr_t get_element( Ensemble_iterateur it ){
272  return get_cle( it );
273 }
void vider_table(Table *table)
Supprime toutes les clés de la table.
Definition: table.c:201
Table_iterateur premier_iterateur_table(const Table *table)
Renvoie un itérateur positionné sur la première association de la table.
Definition: table.c:251
intptr_t get_cle(Table_iterateur it)
Renvoie la clé de l'association pointée par l'itérateur passé en paramètre.
Definition: table.c:47
void pour_toute_cle_valeur_table(const Table *table, void(*action)(const intptr_t cle, intptr_t valeur, void *data), void *data)
La fonction passe en revue toutes les associaitons (clé, valeur) de la table, et apelle la fonction p...
Definition: table.c:169
void liberer_table(Table *table)
Cette fonction détruit une table. La mémoire qui a été allouée par la table pour stocker les clés son...
Definition: table.c:131
intptr_t delete_table(Table *table, const intptr_t cle)
Supprime une clé de la table. La mémoire de la clé est libérée et la valeur associée à la clé est per...
Definition: table.c:150
Table_iterateur iterateur_suivant_table(Table_iterateur iterator)
Renvoie l'itérateur suivant.
Definition: table.c:269
Table_iterateur iterateur_precedent_table(Table_iterateur iterator)
Renvoie l'itérateur précédent.
Definition: table.c:274
int iterateur_est_vide(Table_iterateur iterator)
Renvoie 1 si l'itérateur passé en paramètre est vide. Renvoie 0 sinon.
Definition: table.c:265
Table_iterateur trouver_table(const Table *table, const intptr_t cle)
Renvoie un itérateur positionné sur l'association dont la clé est identique (pour la fonction de comp...
Definition: table.c:241
Table * creer_table(int(*comparer_cle)(const intptr_t cle1, const intptr_t cle2), intptr_t(*copier_cle)(const intptr_t cle), void(*supprimer_cle)(intptr_t cle))
Renvoie une nouvelle table.
Definition: table.c:117
void add_table(Table *table, const intptr_t cle, const intptr_t valeur)
La fonction add_table() ajoute une association entre une clé et une valeur. Pour cela, add_table(), crée une copie de la clé passée en paramètre, l'enregistre dans la table et l'associe à la valeur passée en paramètre. La mémoire de la copie de la clé est gérée par la table. La mémoire de la clé passée en paramètre reste à la charge de l'utilisateur.
Definition: table.c:137