1 files changed, 88 insertions, 0 deletions
diff --git a/semestre 3/structures des données/tme/tme6-11/Hachage.c b/semestre 3/structures des données/tme/tme6-11/Hachage.c
new file mode 100644
index 0000000..11046cf
--- /dev/null
+++ b/semestre 3/structures des données/tme/tme6-11/Hachage.c
@@ -0,0 +1,88 @@
+#include "Hachage.h"
+#include "Reseau.h"
+#include <math.h>
+#include <stdlib.h>
+
+int cle(double x, double y){
+    return y + (x+y)*(x+y+1)/2;
+}
+
+int hachage(int M, double k){
+    float A = (sqrt(5)-1)/2;
+    return floor(M*(k*A-floor(k*A)));
+}
+
+TableHachage* initHachage(int M){
+    TableHachage* hash = malloc(sizeof(TableHachage));
+    hash->len = M;
+    hash->values = malloc(M*sizeof(CellNoeud));
+    for (int i = 0; i < M; i++) hash->values[i] = NULL;
+    return hash;
+}
+
+/*void freeHachage(TableHachage* hash){
+    for (int i = 0; i < hash->len; i++) freeCellHash(hash->values[i]);
+    free(hash->values);
+    free(hash);
+}*/
+
+void insertHachage(TableHachage* H, CellNoeud* cell){
+    int key = hachage(H->len, cle(cell->nd->x, cell->nd->y));
+    cell->suiv = H->values[key];
+    H->values[key] = cell;
+}
+
+Noeud* rechercheCreeNoeudHachage(Reseau* R, TableHachage* H, double x, double y){
+    int key = cle(x, y);
+    CellNoeud* val = H->values[hachage(H->len, key)];
+    // je suppose que les clés sont uniques
+    while (val && (val->nd->x != x || val->nd->y != y)) val = val->suiv;
+    if (val) return val->nd;
+    // on a besoin de créer le nœud
+    Noeud* node = rechercheCreeNoeudListe(R, x, y);
+    CellNoeud* cell = malloc(sizeof(CellNoeud));
+    cell->nd = node;
+    insertHachage(H, cell);
+    return node;
+}
+
+Reseau* reconstitueReseauHachage(Chaines *C, int M){
+    TableHachage* hash = initHachage(M);
+    Reseau* R = (Reseau*) malloc(sizeof(Reseau));
+    CellChaine* chain = C->chaines;
+    while (chain){
+        CellPoint* points = chain->points;
+        CellNoeud* before;
+        CellNoeud* beforeTwice;
+        CellCommodite* com = malloc(sizeof(CellCommodite));
+        com->extrA = NULL;
+        while (points){
+            Noeud* node = rechercheCreeNoeudHachage(R, hash, points->x, points->y);
+            if (!com->extrA) com->extrA = node;
+            // represents voisins of node
+            CellNoeud* cellNode = (CellNoeud*) malloc(sizeof(CellNoeud));
+            cellNode->nd = node;
+            cellNode->suiv = NULL;
+
+            if (beforeTwice){
+                CellNoeud* cell = (CellNoeud*) malloc(sizeof(CellNoeud));
+                cell->nd = node;
+                cell->suiv = NULL;
+                beforeTwice->suiv = cell; // link beforeTwice to current
+                before->nd->voisins = beforeTwice; // set before voisins
+            }
+
+            beforeTwice = before;
+            before = cellNode;
+            if (!points->suiv) com->extrB = node;
+            points = points->suiv;
+        }
+        if (beforeTwice && before){
+            before->nd->voisins = beforeTwice; // set before voisins
+        }
+        com->suiv = R->commodites;
+        R->commodites = com;
+        chain = chain->suiv;
+    }
+    return R;
+}