From 856dfb72dec63f566c5525df42a8b292987a14d6 Mon Sep 17 00:00:00 2001
From: Cyrille Bagard <nocbos@gmail.com>
Date: Fri, 8 Mar 2019 14:22:14 +0100
Subject: Reordered blocks in graph view to avoid edge crossing.
---
src/gtkext/graph/cluster-int.h | 24 ++-
src/gtkext/graph/cluster.c | 402 +++++++++++++++++++++++++++++++----------
src/gtkext/graph/leaving.c | 124 +++++++++++++
src/gtkext/graph/leaving.h | 15 ++
src/gtkext/graph/rank.c | 149 ++++++++++-----
src/gtkext/graph/rank.h | 18 +-
6 files changed, 576 insertions(+), 156 deletions(-)
diff --git a/src/gtkext/graph/cluster-int.h b/src/gtkext/graph/cluster-int.h
index 881a60a..3121d64 100644
--- a/src/gtkext/graph/cluster-int.h
+++ b/src/gtkext/graph/cluster-int.h
@@ -49,21 +49,27 @@ void g_graph_cluster_setup_links(GGraphCluster *);
/* Organise la disposition d'un ensemble de blocs basiques. */
void g_graph_cluster_dispatch_x(GGraphCluster *);
+/* Détermine une direction préférée pour la suite du bloc. */
+bool g_graph_cluster_get_exit_direction(const GGraphCluster *, const GGraphCluster *, LeavingLinkDir *);
+
+/* Réorganise au besoin les liens sortants d'un bloc. */
+void g_graph_cluster_sort_leaving_links(GGraphCluster *);
+
+/* Calcule les ordonnées extrèmes atteintes via liens sortants. */
+bool g_graph_cluster_compute_min_max_bottom(const GGraphCluster *cluster, gint [2]);
+
+/* Retrouve s'il existe un lien entrant vers un bloc d'origine. */
+const leaving_link_t *g_graph_cluster_has_origin(const GGraphCluster *, const GGraphCluster *);
+
+/* Compare deux clusters selon un de leurs liens d'origine. */
+int g_graph_cluster_compare_by_origin(const GGraphCluster **, const GGraphCluster **, const GGraphCluster *);
+
/* Réorganise au besoin les liens entrants d'un bloc. */
void g_graph_cluster_sort_incoming_links(GGraphCluster *);
/* Retrouve l'indice d'un lien entrant donné pour un bloc. */
size_t g_graph_cluster_find_incoming_link(const GGraphCluster *, const leaving_link_t *);
-/* Détermine si un cluster possède un lien sortant. */
-bool g_graph_cluster_has_exit_link(GGraphCluster *, bool *);
-
-/* Compare deux clusters avec lien sortant. */
-int g_graph_cluster_compare_by_exit(const GGraphCluster **, const GGraphCluster **, const bool *);
-
-/* Réordonne les blocs sortant du cluster au mieux. */
-void g_graph_cluster_reorder_exit_blocks(GGraphCluster *);
-
/* Réordonne les blocs de départ de boucle au mieux. */
void g_graph_cluster_reorder_loop_blocks(GGraphCluster *);
diff --git a/src/gtkext/graph/cluster.c b/src/gtkext/graph/cluster.c
index 5785251..801929e 100644
--- a/src/gtkext/graph/cluster.c
+++ b/src/gtkext/graph/cluster.c
@@ -701,7 +701,6 @@ void g_graph_cluster_setup_links(GGraphCluster *cluster)
{
leaving->straight = true;
leaving->straight_level = target_level;
- continue;
}
/* Est-ce une sortie de cluster ? */
@@ -715,10 +714,7 @@ void g_graph_cluster_setup_links(GGraphCluster *cluster)
break;
if (k == container->ranks_count)
- {
leaving->cluster_exit = true;
- continue;
- }
}
@@ -741,7 +737,6 @@ void g_graph_cluster_setup_links(GGraphCluster *cluster)
{
leaving->forced_straight = true;
leaving->straight_level = target_level;
- continue;
}
}
@@ -911,102 +906,267 @@ void g_graph_cluster_dispatch_x(GGraphCluster *cluster)
/******************************************************************************
* *
-* Paramètres : cluster = graphique de blocs à manipuler. *
+* Paramètres : cluster = graphique de blocs à analyser. *
+* root = élément à ne jamais croiser dans la paternité. *
+* dir = préférence à actualiser si possible. [OUT] *
* *
-* Description : Réorganise au besoin les liens entrants d'un bloc. *
+* Description : Détermine une direction préférée pour la suite du bloc. *
* *
-* Retour : - *
+* Retour : false si une incapacité de détermination a été rencontrée. *
* *
* Remarques : - *
* *
******************************************************************************/
-void g_graph_cluster_sort_incoming_links(GGraphCluster *cluster)
+bool g_graph_cluster_get_exit_direction(const GGraphCluster *cluster, const GGraphCluster *root, LeavingLinkDir *dir)
{
- size_t i; /* Boucle de parcours */
+ bool result; /* Bilan à renvoyer */
+ size_t i; /* Boucle de parcours #1 */
+ const leaving_link_t *leaving; /* Lien sortant à traiter */
+ GGraphCluster *iter; /* Boucle de parcours #2 */
+ LeavingLinkDir pref; /* Préférence du lien courant */
- qsort(cluster->top_anchors, cluster->ta_count, sizeof(incoming_link_t *), (__compar_fn_t)cmp_incoming_links);
+ result = true;
- for (i = 0; i < cluster->ranks_count; i++)
- sort_graph_rank_incoming_links(&cluster->ranks[i]);
+ for (i = 0; i < cluster->ba_count && result; i++)
+ {
+ leaving = cluster->bottom_anchors[i];
- sort_incoming_links_for_vspace_manager(&cluster->self);
+ if (!leaving->cluster_exit)
+ continue;
+
+ /* Validation d'une sortie du cluster d'origine */
+
+ for (iter = leaving->other->owner; iter != NULL; iter = iter->owner)
+ if (iter == root)
+ break;
+
+ if (iter != NULL)
+ continue;
+
+ pref = get_leaving_link_direction(leaving);
+
+ /* Si la direction est claire... */
+ if (*dir == LLD_NO_PREF)
+ *dir = pref;
+
+ /* Multiples directions, on ne sait pas trancher ! */
+ else if (*dir != pref)
+ result = false;
+
+ }
+
+ for (i = 0; i < cluster->ranks_count && result; i++)
+ result = get_graph_rank_exit_direction(&cluster->ranks[i], root, dir);
+
+ return result;
}
/******************************************************************************
* *
-* Paramètres : cluster = graphique de blocs à consulter. *
-* incoming = adresse de l'autre bout du lien concerné. *
+* Paramètres : cluster = graphique de blocs à manipuler. *
* *
-* Description : Retrouve l'indice d'un lien entrant donné pour un bloc. *
+* Description : Réorganise au besoin les liens sortants d'un bloc. *
* *
-* Retour : Indice à priori toujours valide. *
+* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
-size_t g_graph_cluster_find_incoming_link(const GGraphCluster *cluster, const leaving_link_t *leaving)
+void g_graph_cluster_sort_leaving_links(GGraphCluster *cluster)
{
- size_t result; /* Indice à retourner */
+ size_t i; /* Boucle de parcours */
+ leaving_link_t **left; /* Liens à placer à gauche */
+ leaving_link_t **center; /* Liens à placer au milieu */
+ leaving_link_t **right; /* Liens à placer à droite */
+ size_t left_count; /* Quantité de liens à gauche */
+ size_t center_count; /* Quantité de liens au milieu */
+ size_t right_count; /* Quantité de liens à droite */
+ leaving_link_t *leaving; /* Lien sortant à traiter */
+ LeavingLinkDir pref; /* Préférence du lien courant */
- for (result = 0; result < cluster->ta_count; result++)
- if (cluster->top_anchors[result]->other == leaving)
- break;
+ /**
+ * On n'intervient que s'il y a lieu de le faire, notamment si les sorties
+ * du groupe de blocs ont une direction claire.
+ */
- assert(cluster->ta_count);
+ pref = LLD_NO_PREF;
- return result;
+ if (!g_graph_cluster_get_exit_direction(cluster, cluster, &pref))
+ goto done;
+
+ if (cluster->ba_count < 2 || pref == LLD_NO_PREF)
+ goto done;
+
+ left = NULL;
+ center = NULL;
+ right = NULL;
+
+ left_count = 0;
+ center_count = 0;
+ right_count = 0;
+
+ /* Réorganisation des liens */
+
+ for (i = 0; i < cluster->ba_count; i++)
+ {
+ leaving = cluster->bottom_anchors[i];
+
+ if (SHOULD_BE_VERTICAL(leaving))
+ {
+ if (leaving->cluster_exit)
+ pref = get_leaving_link_direction(leaving);
+
+ else
+ pref = LLD_NO_PREF;
+
+ }
+ else
+ {
+ pref = LLD_NO_PREF;
+
+ if (!g_graph_cluster_get_exit_direction(leaving->other->owner, leaving->other->owner, &pref))
+ pref = LLD_NO_PREF;
+
+ }
+
+ switch (pref)
+ {
+ case LLD_TO_LEFT:
+ left = realloc(left, ++left_count * sizeof(leaving_link_t *));
+ left[left_count - 1] = leaving;
+ break;
+
+ case LLD_NO_PREF:
+ center = realloc(center, ++center_count * sizeof(leaving_link_t *));
+ center[center_count - 1] = leaving;
+ break;
+
+ case LLD_TO_RIGHT:
+ right = realloc(right, ++right_count * sizeof(leaving_link_t *));
+ right[right_count - 1] = leaving;
+ break;
+
+ }
+
+ }
+
+ /* Sauvegarde du nouvel arrangement */
+
+ assert((left_count + center_count + right_count) == cluster->ba_count);
+
+ cluster->ba_count = 0;
+
+ if (left != NULL)
+ {
+ qsort_r(left, left_count, sizeof(leaving_link_t *),
+ (__compar_d_fn_t)cmp_leaving_links,
+ (LeavingLinkDir []) { LLD_TO_LEFT });
+
+ for (i = 0; i < left_count; i++)
+ cluster->bottom_anchors[cluster->ba_count++] = left[i];
+
+ free(left);
+
+ }
+
+ if (center != NULL)
+ {
+ for (i = 0; i < center_count; i++)
+ cluster->bottom_anchors[cluster->ba_count++] = center[i];
+
+ free(center);
+
+ }
+
+ if (right != NULL)
+ {
+ qsort_r(right, right_count, sizeof(leaving_link_t *),
+ (__compar_d_fn_t)cmp_leaving_links,
+ (LeavingLinkDir []) { LLD_TO_RIGHT });
+
+ for (i = 0; i < right_count; i++)
+ cluster->bottom_anchors[cluster->ba_count++] = right[i];
+
+ free(right);
+
+ }
+
+ assert((left_count + center_count + right_count) == cluster->ba_count);
+
+ for (i = 0; i < cluster->ba_count; i++)
+ cluster->bottom_anchors[i]->index = i;
+
+ /* Application de la nouvelle disposition */
+
+ for (i = 0; i < cluster->ranks_count; i++)
+ reorder_graph_rank_clusters(&cluster->ranks[i], cluster);
+
+ for (i = 0; i < cluster->ranks_count; i++)
+ reset_graph_rank_allocation(&cluster->ranks[i]);
+
+ for (i = 0; i < cluster->ranks_count; i++)
+ offset_x_graph_rank(&cluster->ranks[i], cluster->alloc.x);
+
+ g_graph_cluster_dispatch_x(cluster);
+
+ g_graph_cluster_set_y(cluster, cluster->alloc.y);
+
+ done:
+
+ for (i = 0; i < cluster->ranks_count; i++)
+ visit_graph_rank(&cluster->ranks[i], g_graph_cluster_sort_leaving_links);
}
/******************************************************************************
* *
-* Paramètres : cluster = graphique de blocs à analyser. *
-* l2r = indique si le lien trouvé part vers à droite. [OUT]*
+* Paramètres : cluster = graphique de blocs à consulter. *
+* pos = ordonnées minimale et maximale en bout. [OUT] *
* *
-* Description : Détermine si un cluster possède un lien sortant. *
+* Description : Calcule les ordonnées extrèmes atteintes via liens sortants. *
* *
-* Retour : true si le chef de file à un lien qui sort de l'ensemble. *
+* Retour : true si un lien sortant a été trouvé, false sinon. *
* *
* Remarques : - *
* *
******************************************************************************/
-bool g_graph_cluster_has_exit_link(GGraphCluster *cluster, bool *l2r)
+bool g_graph_cluster_compute_min_max_bottom(const GGraphCluster *cluster, gint pos[2])
{
bool result; /* Bilan à retourner */
size_t i; /* Boucle de parcours */
- leaving_link_t *leaving; /* Lien manipulé */
- gint x1; /* Abscisse de départ de lien */
- size_t idx; /* Indice du lien entrant */
- gint x2; /* Abscisse d'arrivée de lien */
+ const leaving_link_t *leaving; /* Lien sortant à traiter */
+ gint y; /* Ordonnée rencontrée */
result = false;
- for (i = 0; i < cluster->ba_count && !result; i++)
+ for (i = 0; i < cluster->ba_count; i++)
{
leaving = cluster->bottom_anchors[i];
- if (leaving->cluster_exit)
- {
- result = true;
-
- x1 = compute_leaving_link_position(leaving);
+ if (!leaving->cluster_exit)
+ continue;
- idx = g_graph_cluster_find_incoming_link(leaving->other->owner, leaving);
+ result = true;
- x2 = g_graph_cluster_compute_incoming_link_position(leaving->other->owner, idx);
+ y = leaving->other->owner->alloc.y;
- *l2r = (x1 < x2);
+ if (y < pos[0])
+ pos[0] = y;
- }
+ if (pos[1] < y)
+ pos[1] = y;
}
+ for (i = 0; i < cluster->ranks_count; i++)
+ result |= compute_graph_rank_min_max_bottom(&cluster->ranks[i], pos);
+
return result;
}
@@ -1014,69 +1174,75 @@ bool g_graph_cluster_has_exit_link(GGraphCluster *cluster, bool *l2r)
/******************************************************************************
* *
-* Paramètres : cluster = premier graphique de blocs à analyser. *
-* other = second graphique de blocs à analyser. *
-* l2r = indique si le lien trouvé part vers à droite. *
+* Paramètres : cluster = graphique de blocs à analyser. *
+* origin = cluster d'origine à considérer. *
* *
-* Description : Compare deux clusters avec lien sortant. *
+* Description : Retrouve s'il existe un lien entrant vers un bloc d'origine. *
* *
-* Retour : Bilan de la comparaison. *
+* Retour : Lien vers le bloc d'origine trouvé ou NULL. *
* *
* Remarques : - *
* *
******************************************************************************/
-int g_graph_cluster_compare_by_exit(const GGraphCluster **cluster, const GGraphCluster **other, const bool *l2r)
+const leaving_link_t *g_graph_cluster_has_origin(const GGraphCluster *cluster, const GGraphCluster *origin)
{
- int result; /* Bilan à renvoyer */
+ const leaving_link_t *result; /* Lien trouvé à renvoyer */
size_t i; /* Boucle de parcours */
- gint cluster_y; /* Position de la sortie #0 */
- gint other_y; /* Position de la sortie #1 */
- leaving_link_t *leaving; /* Lien manipulé */
- cluster_y = 0;
- other_y = 0;
+ result = NULL;
- for (i = 0; i < (*cluster)->ba_count; i++)
- {
- leaving = (*cluster)->bottom_anchors[i];
+ for (i = 0; i < cluster->ta_count && result == NULL; i++)
+ if (cluster->top_anchors[i]->other->owner == origin)
+ result = cluster->top_anchors[i]->other;
- if (leaving->cluster_exit)
- {
- cluster_y = leaving->other->owner->alloc.y;
- break;
- }
+ return result;
- }
+}
- assert(i < (*cluster)->ba_count);
- for (i = 0; i < (*other)->ba_count; i++)
- {
- leaving = (*other)->bottom_anchors[i];
+/******************************************************************************
+* *
+* Paramètres : cluster = premier graphique de blocs à analyser. *
+* other = second graphique de blocs à analyser. *
+* origin = cluster d'origine à considérer. *
+* *
+* Description : Compare deux clusters selon un de leurs liens d'origine. *
+* *
+* Retour : Bilan de la comparaison. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
- if (leaving->cluster_exit)
- {
- other_y = leaving->other->owner->alloc.y;
- break;
- }
+int g_graph_cluster_compare_by_origin(const GGraphCluster **cluster, const GGraphCluster **other, const GGraphCluster *origin)
+{
+ int result; /* Bilan à renvoyer */
+ const leaving_link_t *leaving; /* Accès au lien manipulé */
+ gint x0; /* Première abscisse à traiter */
+ gint x1; /* Seconde abscisse à traiter */
- }
+ leaving = g_graph_cluster_has_origin(*cluster, origin);
+
+ assert(leaving != NULL);
+
+ x0 = compute_leaving_link_position(leaving);
+
+ leaving = g_graph_cluster_has_origin(*other, origin);
+
+ assert(leaving != NULL);
- assert(i < (*other)->ba_count);
+ x1 = compute_leaving_link_position(leaving);
- if (cluster_y < other_y)
+ if (x0 < x1)
result = -1;
- else if (cluster_y > other_y)
+ else if (x0 > x1)
result = 1;
else
result = 0;
- if (*l2r)
- result *= -1;
-
return result;
}
@@ -1084,9 +1250,9 @@ int g_graph_cluster_compare_by_exit(const GGraphCluster **cluster, const GGraphC
/******************************************************************************
* *
-* Paramètres : cluster = graphique de blocs à actualiser. *
+* Paramètres : cluster = graphique de blocs à manipuler. *
* *
-* Description : Réordonne les blocs sortant du cluster au mieux. *
+* Description : Réorganise au besoin les liens entrants d'un bloc. *
* *
* Retour : - *
* *
@@ -1094,12 +1260,44 @@ int g_graph_cluster_compare_by_exit(const GGraphCluster **cluster, const GGraphC
* *
******************************************************************************/
-void g_graph_cluster_reorder_exit_blocks(GGraphCluster *cluster)
+void g_graph_cluster_sort_incoming_links(GGraphCluster *cluster)
{
size_t i; /* Boucle de parcours */
+ qsort(cluster->top_anchors, cluster->ta_count, sizeof(incoming_link_t *), (__compar_fn_t)cmp_incoming_links);
+
for (i = 0; i < cluster->ranks_count; i++)
- reorder_graph_rank_exit_blocks(&cluster->ranks[i]);
+ sort_graph_rank_incoming_links(&cluster->ranks[i]);
+
+ sort_incoming_links_for_vspace_manager(&cluster->self);
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : cluster = graphique de blocs à consulter. *
+* incoming = adresse de l'autre bout du lien concerné. *
+* *
+* Description : Retrouve l'indice d'un lien entrant donné pour un bloc. *
+* *
+* Retour : Indice à priori toujours valide. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+size_t g_graph_cluster_find_incoming_link(const GGraphCluster *cluster, const leaving_link_t *leaving)
+{
+ size_t result; /* Indice à retourner */
+
+ for (result = 0; result < cluster->ta_count; result++)
+ if (cluster->top_anchors[result]->other == leaving)
+ break;
+
+ assert(result < cluster->ta_count);
+
+ return result;
}
@@ -2256,6 +2454,25 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList *
g_graph_cluster_dispatch_x(result);
/**
+ * Une première passe d'organisation horizontale est réalisée.
+ *
+ * A ce point, en proposant des emplacements verticaux en complément,
+ * on est en mesure de déterminer si les liens qui sortent de leur
+ * conteneur vont en croiser d'autres.
+ *
+ * On réorganise ainsi au besoin les différents blocs pour éviter ce cas
+ * de figure. Les blocs sont replacés à une nouvelle position horizontale
+ * au besoin.
+ *
+ * Une illustration concrête de la nécessité de cette opération est la
+ * fonction test_ite_2() de la suite de tests.
+ */
+
+ g_graph_cluster_set_y(result, 0);
+
+ g_graph_cluster_sort_leaving_links(result);
+
+ /**
* A ce point, tous les blocs sont placés.
* On est donc en mesure de réorganiser les points d'arrivée
* des liens afin d'éviter les croisements : un lien qui vient
@@ -2272,21 +2489,6 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList *
g_graph_cluster_sort_incoming_links(result);
/**
- * Comme des profondeurs de rang identiques peuvent renvoyer à des
- * positions verticales différentes selon les chemins présents,
- * on lance ici une réorganisation des blocs qui ont une sortie fuyante
- * de leur ensemble parent en plaçant, même de façon parcellaire, l'ensemble
- * des blocs.
- *
- * Une illustration concrête de cette nécessité est la fonction test_ite_2()
- * de la suite de tests.
- */
-
- g_graph_cluster_set_y(result, 0);
-
- g_graph_cluster_reorder_exit_blocks(result);
-
- /**
* Même s'ils ne sont pas encore entièrement tracés, les liens de boucle
* voient désormais leurs positions d'arrivée et de départ définies.
*
diff --git a/src/gtkext/graph/leaving.c b/src/gtkext/graph/leaving.c
index ad07f04..3147784 100644
--- a/src/gtkext/graph/leaving.c
+++ b/src/gtkext/graph/leaving.c
@@ -24,6 +24,7 @@
#include "leaving.h"
+#include <assert.h>
#include <malloc.h>
@@ -105,3 +106,126 @@ gint compute_leaving_link_position(const leaving_link_t *link)
return result;
}
+
+
+/******************************************************************************
+* *
+* Paramètres : link = information sur un lien à consulter. *
+* *
+* Description : Détermine une direction prise par un lien à son départ. *
+* *
+* Retour : Direction prise à l'écran. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+LeavingLinkDir get_leaving_link_direction(const leaving_link_t *link)
+{
+ LeavingLinkDir result; /* Préférence à retourner */
+ gint x1; /* Abscisse de départ de lien */
+ GGraphCluster *owner; /* Raccourci vers le proprio */
+ size_t idx; /* Indice du lien entrant */
+ gint x2; /* Abscisse d'arrivée de lien */
+
+ x1 = compute_leaving_link_position(link);
+
+ owner = link->other->owner;
+
+ idx = g_graph_cluster_find_incoming_link(owner, link);
+
+ x2 = g_graph_cluster_compute_incoming_link_position(owner, idx);
+
+ if (x1 < x2)
+ result = LLD_TO_RIGHT;
+
+ else if (x1 > x2)
+ result = LLD_TO_LEFT;
+
+ else
+ result = LLD_NO_PREF;
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : a = premier lien entrant à comparer. *
+* b = second lien entrant à comparer. *
+* dir = complément d'information quant à la direction traitée. *
+* *
+* Description : Compare deux liens sortants. *
+* *
+* Retour : Bilan de comparaison. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+int cmp_leaving_links(const leaving_link_t **a, const leaving_link_t **b, const LeavingLinkDir *dir)
+{
+ int result; /* Bilan à retourner */
+ GGraphCluster *owner; /* Raccourci vers le proprio */
+ gint pos_a[2]; /* Points de départ pour A */
+ GtkAllocation alloc; /* Emplacement de cluster */
+ gint pos_b[2]; /* Points de départ pour B */
+
+ /* Calcul des ordonnées des points de chute */
+
+ owner = (*a)->other->owner;
+
+ pos_a[0] = G_MAXINT;
+ pos_a[1] = 0;
+
+ if (!g_graph_cluster_compute_min_max_bottom(owner, pos_a))
+ {
+ g_graph_cluster_get_allocation(owner, &alloc);
+
+ pos_a[0] = alloc.y;
+ pos_a[1] = alloc.y;
+
+ }
+
+ owner = (*b)->other->owner;
+
+ pos_b[0] = G_MAXINT;
+ pos_b[1] = 0;
+
+ if (!g_graph_cluster_compute_min_max_bottom(owner, pos_b))
+ {
+ g_graph_cluster_get_allocation(owner, &alloc);
+
+ pos_b[0] = alloc.y;
+ pos_b[1] = alloc.y;
+
+ }
+
+ /* Comparaison */
+
+ if (pos_a[1] < pos_b[1])
+ result = -1;
+
+ else if (pos_a[1] > pos_b[1])
+ result = 1;
+
+ else
+ {
+ if (pos_a[0] < pos_b[0])
+ result = -1;
+
+ else if (pos_a[0] > pos_b[0])
+ result = 1;
+
+ else
+ result = 0;
+
+ }
+
+ if (*dir == LLD_TO_RIGHT)
+ result *= -1;
+
+ return result;
+
+}
diff --git a/src/gtkext/graph/leaving.h b/src/gtkext/graph/leaving.h
index c91f232..b81e1ca 100644
--- a/src/gtkext/graph/leaving.h
+++ b/src/gtkext/graph/leaving.h
@@ -61,6 +61,21 @@ void delete_leaving_link(leaving_link_t *);
/* Calcule l'abscisse d'un lien à son départ d'un bloc. */
gint compute_leaving_link_position(const leaving_link_t *);
+/* Direction prise par le lien */
+typedef enum _LeavingLinkDir
+{
+ LLD_NO_PREF, /* Direction variable */
+ LLD_TO_LEFT, /* Vers la gauche */
+ LLD_TO_RIGHT, /* Vers la droite */
+
+} LeavingLinkDir;
+
+/* Détermine une direction prise par un lien à son départ. */
+LeavingLinkDir get_leaving_link_direction(const leaving_link_t *);
+
+/* Compare deux liens sortants. */
+int cmp_leaving_links(const leaving_link_t **, const leaving_link_t **, const LeavingLinkDir *);
+
#endif /* _GTKEXT_GRAPH_LEAVING_H */
diff --git a/src/gtkext/graph/rank.c b/src/gtkext/graph/rank.c
index 0fadb27..bffefe9 100644
--- a/src/gtkext/graph/rank.c
+++ b/src/gtkext/graph/rank.c
@@ -104,6 +104,28 @@ void exit_graph_rank(graph_rank_t *grank)
* *
* Paramètres : grank = ensemble de même rang à consulter. *
* *
+* Description : Parcours l'ensemble des blocs du rang avec un visiteur. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void visit_graph_rank(const graph_rank_t *grank, graph_rank_cb cb)
+{
+ size_t i; /* Boucle de parcours */
+
+ for (i = 0; i < grank->count; i++)
+ cb(grank->clusters[i]);
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : grank = ensemble de même rang à consulter. *
+* *
* Description : Assigne à un ensemble de blocs un emplacement initial. *
* *
* Retour : - *
@@ -494,24 +516,29 @@ void dispatch_x_graph_rank(const graph_rank_t *grank)
/******************************************************************************
* *
-* Paramètres : grank = ensemble de blocs de même rang à actualiser. *
+* Paramètres : grank = ensemble de blocs de même rang à actualiser. *
+* root = élément à ne jamais croiser dans la paternité. *
+* dir = préférence à actualiser si possible. [OUT] *
* *
* Description : Réorganise au besoin les liens entrants un ensemble de blocs.*
* *
-* Retour : - *
+* Retour : false si une incapacité de détermination a été rencontrée. *
* *
* Remarques : - *
* *
******************************************************************************/
-void sort_graph_rank_incoming_links(graph_rank_t *grank)
+bool get_graph_rank_exit_direction(graph_rank_t *grank, const GGraphCluster *root, LeavingLinkDir *dir)
{
+ bool result; /* Bilan à renvoyer */
size_t i; /* Boucle de parcours */
- for (i = 0; i < grank->count; i++)
- g_graph_cluster_sort_incoming_links(grank->clusters[i]);
+ result = true;
- sort_incoming_links_for_vspace_manager(&grank->vspaces);
+ for (i = 0; i < grank->count && result; i++)
+ result = g_graph_cluster_get_exit_direction(grank->clusters[i], root, dir);
+
+ return result;
}
@@ -519,8 +546,37 @@ void sort_graph_rank_incoming_links(graph_rank_t *grank)
/******************************************************************************
* *
* Paramètres : grank = ensemble de blocs de même rang à actualiser. *
+* pos = ordonnées minimale et maximale en bout. [OUT] *
+* *
+* Description : Calcule les ordonnées extrèmes atteintes via liens sortants. *
* *
-* Description : Réordonne les blocs sortant d'un ensemble. *
+* Retour : true si un lien sortant a été trouvé, false sinon. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+bool compute_graph_rank_min_max_bottom(const graph_rank_t *grank, gint pos[2])
+{
+ bool result; /* Bilan à renvoyer */
+ size_t i; /* Boucle de parcours */
+
+ result = false;
+
+ for (i = 0; i < grank->count; i++)
+ result |= g_graph_cluster_compute_min_max_bottom(grank->clusters[i], pos);
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : grank = ensemble de blocs de même rang à actualiser. *
+* origin = cluster d'origine à considérer. *
+* *
+* Description : Réorganise au besoin les blocs selon les liens d'origine. *
* *
* Retour : - *
* *
@@ -528,64 +584,69 @@ void sort_graph_rank_incoming_links(graph_rank_t *grank)
* *
******************************************************************************/
-void reorder_graph_rank_exit_blocks(graph_rank_t *grank)
+void reorder_graph_rank_clusters(graph_rank_t *grank, const GGraphCluster *origin)
{
- GGraphCluster **exit_2_left; /* Liste avec sortie à gauche */
- GGraphCluster **exit_2_right; /* Liste avec sortie à droite */
- GGraphCluster **no_exit; /* Liste sans sortie */
- size_t count_2_left; /* Quantité de présents */
- size_t count_2_right; /* Quantité de présents */
- size_t count_no; /* Quantité de présents */
size_t i; /* Boucle de parcours */
- bool l2r; /* Détermination de catégorie */
+ GGraphCluster **filtered; /* Blocs à réorganiser */
+ size_t fcount; /* Nombre de ces blocs */
+ size_t next; /* Prochain indice à réinsérer */
if (grank->count > 1)
{
- exit_2_left = malloc(grank->count * sizeof(GGraphCluster *));
- exit_2_right = malloc(grank->count * sizeof(GGraphCluster *));
- no_exit = malloc(grank->count * sizeof(GGraphCluster *));
+ /**
+ * On prend garde de ne déplacer que les blocs avec un lien concernant
+ * un bloc d'origine, dont les liens au départ ont été réorganisés.
+ */
- count_2_left = 0;
- count_2_right = 0;
- count_no = 0;
+ filtered = malloc(grank->count * sizeof(GGraphCluster *));
+ fcount = 0;
for (i = 0; i < grank->count; i++)
- {
- if (g_graph_cluster_has_exit_link(grank->clusters[i], &l2r))
+ if (g_graph_cluster_has_origin(grank->clusters[i], origin) != NULL)
{
- if (l2r)
- exit_2_right[count_2_right++] = grank->clusters[i];
- else
- exit_2_left[count_2_left++] = grank->clusters[i];
+ filtered[fcount++] = grank->clusters[i];
+ grank->clusters[i] = NULL;
}
- else
- no_exit[count_no++] = grank->clusters[i];
- }
+ qsort_r(filtered, fcount, sizeof(GGraphCluster *),
+ (__compar_d_fn_t)g_graph_cluster_compare_by_origin, (void *)origin);
- assert((count_2_left + count_2_right + count_no) == grank->count);
+ next = 0;
- qsort_r(exit_2_left, count_2_left, sizeof(GGraphCluster *),
- (__compar_d_fn_t)g_graph_cluster_compare_by_exit, (bool []){ false });
+ for (i = 0; i < grank->count; i++)
+ if (grank->clusters[i] == NULL)
+ {
+ assert(next < fcount);
+ grank->clusters[i] = filtered[next++];
+ }
- qsort_r(exit_2_right, count_2_right, sizeof(GGraphCluster *),
- (__compar_d_fn_t)g_graph_cluster_compare_by_exit, (bool []){ true });
+ free(filtered);
- grank->count = 0;
+ }
- for (i = 0; i < count_2_left; i++)
- grank->clusters[grank->count++] = exit_2_left[i];
+}
- for (i = 0; i < count_no; i++)
- grank->clusters[grank->count++] = no_exit[i];
- for (i = 0; i < count_2_right; i++)
- grank->clusters[grank->count++] = exit_2_right[i];
+/******************************************************************************
+* *
+* Paramètres : grank = ensemble de blocs de même rang à actualiser. *
+* *
+* Description : Réorganise au besoin les liens entrants un ensemble de blocs.*
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
- }
+void sort_graph_rank_incoming_links(graph_rank_t *grank)
+{
+ size_t i; /* Boucle de parcours */
for (i = 0; i < grank->count; i++)
- g_graph_cluster_reorder_exit_blocks(grank->clusters[i]);
+ g_graph_cluster_sort_incoming_links(grank->clusters[i]);
+
+ sort_incoming_links_for_vspace_manager(&grank->vspaces);
}
diff --git a/src/gtkext/graph/rank.h b/src/gtkext/graph/rank.h
index 1a149fc..e28b1f0 100644
--- a/src/gtkext/graph/rank.h
+++ b/src/gtkext/graph/rank.h
@@ -55,6 +55,12 @@ void init_graph_rank(graph_rank_t *, GGraphCluster *);
/* Termine la gestion d'un ensemble de blocs de même rang. */
void exit_graph_rank(graph_rank_t *);
+/* Visiteur pour blocs */
+typedef void (* graph_rank_cb) (GGraphCluster *);
+
+/* Parcours l'ensemble des blocs du rang avec un visiteur. */
+void visit_graph_rank(const graph_rank_t *grank, graph_rank_cb);
+
/* Assigne à un ensemble de blocs un emplacement initial. */
void reset_graph_rank_allocation(const graph_rank_t *);
@@ -89,10 +95,16 @@ void _place_graph_rank_clusters(GGraphCluster **, size_t, gint, int);
void dispatch_x_graph_rank(const graph_rank_t *);
/* Réorganise au besoin les liens entrants un ensemble de blocs. */
-void sort_graph_rank_incoming_links(graph_rank_t *);
+bool get_graph_rank_exit_direction(graph_rank_t *, const GGraphCluster *, LeavingLinkDir *);
+
+/* Calcule les ordonnées extrèmes atteintes via liens sortants. */
+bool compute_graph_rank_min_max_bottom(const graph_rank_t *, gint [2]);
-/* Réordonne les blocs sortant d'un ensemble. */
-void reorder_graph_rank_exit_blocks(graph_rank_t *);
+/* Réorganise au besoin les blocs selon les liens d'origine. */
+void reorder_graph_rank_clusters(graph_rank_t *, const GGraphCluster *);
+
+/* Réorganise au besoin les liens entrants un ensemble de blocs. */
+void sort_graph_rank_incoming_links(graph_rank_t *);
/* Réordonne les blocs de départ de boucle d'un ensemble. */
void reorder_graph_rank_loop_blocks(graph_rank_t *);
--
cgit v0.11.2-87-g4458