Projet Informatique Théorique 2016
Instructions et Documentation
ensemble.h
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 #ifndef __ENSEMBLE_H__
23 #define __ENSEMBLE_H__
24 
25 #include <stdint.h>
26 
27 #include "avl.h"
28 #include "table.h"
29 
30 /*
31  * Définit le type d'un ensemble.
32  */
33 struct Ensemble {
34  Table* table;
35  int (*comparer_element)( const intptr_t elem1, const intptr_t elem2 );
36  intptr_t (*copier_element)( const intptr_t elem );
37  void (*supprimer_element)(intptr_t elem );
38 };
39 
40 typedef struct Ensemble Ensemble;
41 
42 /*
43  * Définit le type d'un itérateur sur les éléments d'un ensemble.
44  */
45 typedef struct avl_traverser Ensemble_iterateur;
46 
47 /*
48  * Renvoie un nouvel ensemble vide.
49  *
50  * L'ensemble peut contenir des entiers, codés à l'aide du type intptr_t.
51  * Mais il peut aussi contenir des pointeurs vers des structures plus complexes.
52  * Dans ce cas, c'est l'ensmeble qui devient le responsable de la mémoire des
53  * éléments situé à l'interieur de l'ensemble.
54  * Pour pouvoir gérer cette mémoire, l'ensemble à besoin des fonctions :
55  * - int comparer_element( const intptr_t elem1, const intptr_t elem2 ),
56  * - intptr_t copier_element( const intptr_t elem ),
57  * - void supprimer_element( intptr_t elem ),
58  * qui permettent de comaprer, upprimer et copier des éléments de l'ensemble.
59  *
60  */
61 Ensemble * creer_ensemble(
62  int (*comparer_element)( const intptr_t elem1, const intptr_t elem2 ),
63  intptr_t (*copier_element)( const intptr_t elem ),
64  void (*supprimer_element)( intptr_t elem )
65 );
66 
67 /*
68  * Libère la mémoire d'un ensemble.
69  * La mémoire de tous les éléments de l'ensemble est aussi libérée.
70  */
71 void liberer_ensemble( Ensemble* ens );
72 
73 /*
74  * Ajoute un élement passé en paramètre à l'ensemble.
75  *
76  * L'élément ajouté est copié. La mémoire de la copie n'est pas à la charge
77  * de l'utilisateur. Par contre, l'élément copié (celui qui a été passé en
78  * paramètre) reste à la charge de l'utilisateur qui ne devra pas oublier de
79  * de le supprimer proprement.
80  */
81 void ajouter_element( Ensemble * ensemble, const intptr_t element );
82 
83 /*
84  * Ajoute tous les éléments d'un ensemble à un ensemble.
85  */
86 void ajouter_elements( Ensemble * ens1, const Ensemble * ens2 );
87 
88 /*
89  * Transfère tous les élément de l'ensemble source dans l'ensemble destination
90  * La mémoire de l'ensemble source n'est pas libérer.
91  */
92 void transferer_elements( Ensemble * destination, Ensemble * source );
93 
94 /*
95  * Transfère tous les élément de l'ensemble source dans l'ensemble destination
96  * La mémoire de l'ensemble source est ensuite libéré.
97  */
98 void transferer_elements_et_libere( Ensemble * destination, Ensemble * source );
99 
100 /*
101  * Retire un élément de l'ensemble
102  *
103  * Cette fonction cherche dans l'ensemble un élément idenitque (pour la fonction
104  * de comparaison des éléments) à celui passé en paramètre.
105  * Si la fonction trouve cet élément, elle retire l'élément de l'ensemble
106  * et libère son espace mémoire.
107  */
108 void retirer_element( Ensemble * ensemble, const intptr_t element );
109 
110 /*
111  * Retire tous les éléments d'un ensemble
112  */
113 void retirer_elements( Ensemble * ens1, const Ensemble * ens2 );
114 
115 /*
116  * Retire et supprime tous les éléments d'un ensemble.
117  */
118 void vider_ensemble( Ensemble * ensemble );
119 
120 /*
121  * Renvoie Vrai si il existe un élément dans l'ensmble égal (pour la donction
122  * de comparaion de l'ensemble) à l'élément passé en paramètre.
123  */
124 int est_dans_l_ensemble( const Ensemble * ensemble, const intptr_t element );
125 
126 /*
127  * Renvoie le nombre d'éléments qui se trouvent dans l'ensemble.
128  */
129 unsigned int taille_ensemble( const Ensemble* ensemble );
130 
131 /*
132  * Compare deux ensembles entre eux.
133  *
134  * Cette fonction renvoie 0 si les ensembles sont identiques.
135  *
136  * Soit t1 (resp. t2) le tuple contenant les éléments de l'ensemble 1
137  * (resp. l'ensemble 2) trié par ordre lexicographique, alors, la fonction
138  * renvoie -1 si t1 est plus petit lexicographiquement que
139  * t2, 0 si ils sont identiques et 1 sinon.
140  */
141 int comparer_ensemble( const Ensemble* ens1, const Ensemble* ens2 );
142 
143 /*
144  * Renvoie une copie de l'ensemble passé en paramètre
145  */
146 Ensemble* copier_ensemble( const Ensemble* ensemble );
147 
148 /*
149  * Crée un nouvel ensemble qui est la copie de deux ensembles passés en
150  * paramètre
151  */
152 Ensemble * creer_union_ensemble( const Ensemble* ens1, const Ensemble* ens2 );
153 
154 /*
155  * Créé un nouvel ensemble qui est la différence de deux ensembles passés en
156  * paramètre.
157  */
158 Ensemble * creer_difference_ensemble(
159  const Ensemble* ens1, const Ensemble* ens2
160 );
161 
162 /*
163  * Créé un nouvel ensemble qui est l'intersection de deux ensembles passés en
164  * paramètre.
165  */
166 Ensemble * creer_intersection_ensemble(
167  const Ensemble* ens1, const Ensemble* ens2
168 );
169 
170 /*
171  * Passe en revue tous les éléments d'un ensemble et execute un fonction
172  * passée en paramètre.
173  */
174 void pour_tout_element(
175  const Ensemble* ensemble,
176  void (* action )( const intptr_t element, void* data ),
177  void* data
178 );
179 
180 /*
181  * Affiche tous les éléments d'un ensemble.
182  */
183 void print_ensemble(
184  const Ensemble* ens, void (*print_element)( const intptr_t element )
185 );
186 
187 /*
188  * Échange le contenu de deux ensembles passés en paramètre.
189  */
190 void swap_ensemble( Ensemble* ens1, Ensemble* ens2 );
191 
192 /*
193  * Supprime le contenu de l'ensemble destination, déplace le contenu de
194  * l'ensemble source dans celui de destination et libère la mémoire
195  * de l'ensemble source.
196  */
197 void deplacer_ensemble( Ensemble* dest, Ensemble* source );
198 
199 /*
200  * Renvoie un itérateur positionné sur l'élément identique (pour la fonction
201  * de comparaison des éléments de la table) à l'élément passé en
202  * paramètre.
203  */
204 Ensemble_iterateur trouver_ensemble(
205  const Ensemble* ensemble, const intptr_t element
206 );
207 
208 /*
209  * Renvoie un itérateur positionné sur le premier élement de l'ensemble.
210  */
211 Ensemble_iterateur premier_iterateur_ensemble( const Ensemble* ensemble );
212 
213 /*
214  * Renvoie l'iterateur suivant.
215  *
216  * C'est à dire, l'iterateur renvoyé est positionné sur un nouvel élément
217  * qui est le plus petit des éléments parmi les élément plus grands que celui
218  * associé à l'iterateur passé en en paramètre.
219  *
220  * Deux éléments sont comparés en utilsant la fonction de
221  * comparaison des éléments de l'ensemble.
222  *
223  * S'il n'y a pas d'itérateur suivant (l'itérateur passé en paramètre est
224  * associé au plus grand élément), l'itérateur vide est renvoyé.
225  */
226 Ensemble_iterateur iterateur_suivant_ensemble( Ensemble_iterateur iterateur );
227 
228 /*
229  * Renvoie l'iterateur précédent.
230  *
231  * C'est à dire, l'iterateur renvoyé est positionné sur un nouvel élément
232  * qui est le plus grand élément parmi les éléments plus petit que celui
233  * associé à l'iterateur passé en en paramètre.
234  *
235  * Deux éléments sont comparés en utilisant la fonction de comparaison des
236  * élément de l'ensemble.
237  *
238  * S'il n'y a pas d'itérateur précédent (l'itérateur passé en paramètre est
239  * associé à la plus petite association), l'itérateur vide est renvoyé.
240  */
241 Ensemble_iterateur iterateur_precedent_ensemble( Ensemble_iterateur iterateur );
242 
243 /*
244  * Renvoie 1 si l'iterateur passé en paramètre est vide.
245  * Renvoie 0 sinon.
246  */
247 int iterateur_ensemble_est_vide( Ensemble_iterateur iterateur );
248 
249 /*
250  * Renvoie l'élément associé à l'itérateur passé en paramètre.
251  */
252 intptr_t get_element( Ensemble_iterateur it );
253 
254 #endif
Definition: table.c:39