commit 89f766078f2bdd81453d8ed3d75c0982a4272a12
parent 36a02dfb17c55c9412724807b6e47237adc89e9d
Auteur: Loïc Daignault-Pichette <loic@asteride.xyz>
Date: Fri, 10 Apr 2026 00:26:46 -0400
Trier les états
Diffstat:
| M | tfm.c | | | 90 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | tfm.h | | | 4 | ++++ |
2 fichiers modifiés, 94 insertions(+), 0 suppressions(-)
diff --git a/tfm.c b/tfm.c
@@ -24,6 +24,10 @@
* pas. */
static ssize_t tfm_symb_chercher(char *te, char *symb, size_t lngr);
+/* Trier les transitions d’un état.
+ * Renvoie 0, ou -1 en cas d’erreur. */
+static void trier_etat(struct tfm *tfm, size_t ietat);
+
struct tfm *
tfm_init(void)
{
@@ -209,6 +213,92 @@ tfm_tfinal(struct tfm *tfm, size_t ietat)
return tfm->etats[ietat].final;
}
+int
+tfm_trier(struct tfm *tfm)
+{
+ size_t ietat;
+
+ TFM_COHERENT(tfm);
+
+ if (tfm->trie)
+ return 0;
+
+ for (ietat = 0; tampex_dedans(tfm->etats, ietat); ietat++) {
+ if (!tfm->etats[ietat].trie && tfm->etats[ietat].existe) {
+ trier_etat(tfm, ietat);
+ tfm->etats[ietat].trie = 1;
+ }
+ }
+
+ return 0;
+}
+
+/* Inspiré du programme de Simon Tatham disponible au
+ * https://www.chiark.greenend.org.uk/~sgtatham/algorithms/listsort.c */
+static void
+trier_etat(struct tfm *tfm, size_t ietat)
+{
+ TFM_COHERENT(tfm);
+
+ ssize_t liste, dern; /* Liste et son dernier élément. */
+ size_t listel; /* Longueur de la liste. */
+ size_t ts; /* Taille des segments. */
+ ssize_t s1, s2; /* Deux segments de la liste. */
+ size_t ts1, ts2; /* Taille des deux segments. */
+ size_t trans;
+ size_t i;
+
+ liste = tfm->etats[ietat].trans;
+ listel = tfm->etats[ietat].ntrans;
+ ts = 1;
+
+ while (ts < listel) {
+ s1 = s2 = liste;
+ liste = dern = -1;
+
+ while (s1 != -1) {
+ ts1 = 0;
+ for (i = 0; i < ts; i++) {
+ ts1++;
+ if ((s2 = tfm->trans[s2].prch) == -1)
+ break;
+ }
+
+ ts2 = ts;
+
+ while ((ts1 > 0) || ((ts2 > 0) && (s2 != -1))) {
+ if (ts1 == 0) goto des2;
+ if (ts2 == 0 || s2 == -1) goto des1;
+ if (tfm->trans[s1].se <= tfm->trans[s2].se) {
+ des1:
+ trans = s1;
+ s1 = tfm->trans[s1].prch;
+ ts1--;
+ } else {
+ des2:
+ trans = s2;
+ s2 = tfm->trans[s2].prch;
+ ts2--;
+ }
+
+ if (dern != -1) {
+ tfm->trans[dern].prch = trans;
+ } else {
+ liste = trans;
+ }
+ dern = trans;
+ }
+ tfm->trans[dern].prch = -1;
+
+ s1 = s2;
+ }
+
+ ts *= 2;
+ }
+
+ tfm->etats[ietat].trans = liste;
+}
+
static ssize_t
tfm_symb_chercher(char *ti, char *symb, size_t lngr)
{
diff --git a/tfm.h b/tfm.h
@@ -100,4 +100,8 @@ int tfm_mfinal(struct tfm *tfm, size_t ietat);
* Renvoie un booléen, ou -1 en cas d’erreur. */
int tfm_tfinal(struct tfm *tfm, size_t ietat);
+/* Trier les transitions de tous les états du transducteur tfm.
+ * Renvoie 0, ou -1 en cas d’erreur. */
+int tfm_trier(struct tfm *tfm);
+
#endif
