summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorCyrille Bagard <nocbos@gmail.com>2019-03-15 10:55:03 (GMT)
committerCyrille Bagard <nocbos@gmail.com>2019-03-15 10:55:03 (GMT)
commitf65f83fd222d14934b527152899359327813128e (patch)
tree742e0f08a82ba941e386e5e3764a84b13e0c9ffe
parent0a190905f31d7c395e1b26efe3abe443687429e5 (diff)
Tracked vertical links beyond their cluster.
-rw-r--r--src/gtkext/graph/cluster-int.h27
-rw-r--r--src/gtkext/graph/cluster.c811
-rw-r--r--src/gtkext/graph/leaving.c95
-rw-r--r--src/gtkext/graph/leaving.h14
-rw-r--r--src/gtkext/graph/rank.c84
-rw-r--r--src/gtkext/graph/rank.h12
6 files changed, 677 insertions, 366 deletions
diff --git a/src/gtkext/graph/cluster-int.h b/src/gtkext/graph/cluster-int.h
index 9da1af2..7ffdb61 100644
--- a/src/gtkext/graph/cluster-int.h
+++ b/src/gtkext/graph/cluster-int.h
@@ -40,23 +40,38 @@
/* Assigne à un bloc et son ensemble un emplacement initial. */
void g_graph_cluster_reset_allocation(GGraphCluster *);
+/* Réinitialise les décalages pour les lignes verticales. */
+void g_graph_cluster_reset_extra_offsets(GGraphCluster *);
+
/* Met en place les embryons de liens nécessaires. */
void g_graph_cluster_define_links(GGraphCluster *, GHashTable *);
/* Repère les liens marquants à destination d'autres blocs. */
void g_graph_cluster_setup_links(GGraphCluster *);
+/* Détermine un éventuel lien entrant réellement vertical. */
+incoming_link_t *g_graph_cluster_find_real_straight_incoming(GGraphCluster *, size_t *);
+
/* Organise la disposition d'un ensemble de blocs basiques. */
void g_graph_cluster_dispatch_x(GGraphCluster *);
+/* Calcule les abscisses extrèmes atteintes via liens de sortie. */
+bool g_graph_cluster_compute_min_max_x_exit(const GGraphCluster *, const GGraphCluster *, gint [2]);
+
+/* Calcule les abscisses extrèmes atteintes horizontalement. */
+void g_graph_cluster_compute_min_max_horizontal(const GGraphCluster *, gint, gint [2]);
+
+/* Définit d'éventuels décalages pour les lignes verticales. */
+bool g_graph_cluster_dispatch_define_extra_offset(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 *);
+LeavingLinkDir g_graph_cluster_get_link_direction(const GGraphCluster *, gint, gint);
/* 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]);
+/* Calcule l'ordonnée la plus profonde via liens sortants. */
+bool g_graph_cluster_compute_min_y_target(const GGraphCluster *, const GGraphCluster *, gint *);
/* 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 *);
@@ -64,12 +79,6 @@ const leaving_link_t *g_graph_cluster_has_origin(const GGraphCluster *, const GG
/* Compare deux clusters selon un de leurs liens d'origine. */
int g_graph_cluster_compare_by_origin(const GGraphCluster **, const GGraphCluster **, const GGraphCluster *);
-/* Calcule les abscisses extrèmes atteintes horizontalement. */
-void g_graph_cluster_compute_min_max_horizontal(const GGraphCluster *, const GGraphCluster *, gint [2]);
-
-/* S'assure que les liens verticaux ne traversent pas de bloc. */
-void g_graph_cluster_ensure_space_for_straight(GGraphCluster *);
-
/* Réorganise au besoin les liens entrants d'un bloc. */
void g_graph_cluster_sort_incoming_links(GGraphCluster *);
diff --git a/src/gtkext/graph/cluster.c b/src/gtkext/graph/cluster.c
index e425d67..444bd22 100644
--- a/src/gtkext/graph/cluster.c
+++ b/src/gtkext/graph/cluster.c
@@ -309,7 +309,7 @@ GGraphCluster *g_graph_cluster_new(GCodeBlock *block, segcnt_list *highlighted,
/******************************************************************************
* *
-* Paramètres : cluster = graphique de blocs à compléter. *
+* Paramètres : cluster = graphique de blocs à traiter. *
* *
* Description : Assigne à un bloc et son ensemble un emplacement initial. *
* *
@@ -762,36 +762,25 @@ void g_graph_cluster_setup_links(GGraphCluster *cluster)
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à manipuler. *
+* idx = indice du lien éventuellement identifié. [OUT] *
* *
-* Description : Organise la disposition d'un ensemble de blocs basiques. *
+* Description : Détermine un éventuel lien entrant réellement vertical. *
* *
-* Retour : - *
+* Retour : Lien entrant véritablement vertical. *
* *
* Remarques : - *
* *
******************************************************************************/
-void g_graph_cluster_dispatch_x(GGraphCluster *cluster)
+incoming_link_t *g_graph_cluster_find_real_straight_incoming(GGraphCluster *cluster, size_t *idx)
{
- size_t i; /* Boucle de parcours #1 */
+ incoming_link_t *result; /* Lien entrant à retourner */
size_t straight_idx; /* Lien vertical le plus adapté*/
size_t forced_idx; /* Lien vertical forcé */
bool drop_forced; /* Invalidation de cet indice */
+ size_t i; /* Boucle de parcours #1 */
leaving_link_t *leaving; /* Départ de lien */
GCodeBlock *block[2]; /* Accès rapide aux blocs */
- gint start; /* Position initiale de départ */
- gint end; /* Position initiale d'arrivée */
- leaving_link_t *straight_leaving; /* Lien à présenter vertical */
- size_t straight_index; /* Indice du lien vertical */
- gint straight_start; /* Position initiale de départ */
- size_t straight_level; /* Rang atteint en ligne droite*/
- const graph_rank_t *rank; /* Accès confortable au rang */
- size_t j; /* Boucle de parcours #2 */
- GGraphCluster *target; /* Unique sous-bloc visé */
-
- /**
- * Traitement amont : alignement sur une éventuelle origine.
- */
straight_idx = cluster->ta_count;
forced_idx = cluster->ta_count;
@@ -837,30 +826,69 @@ void g_graph_cluster_dispatch_x(GGraphCluster *cluster)
}
- /* Recalage en fonction d'une éventuelle conduite forcée */
+ /* Détermination du résultat final */
if (drop_forced)
forced_idx = cluster->ta_count;
if (straight_idx < cluster->ta_count || forced_idx < cluster->ta_count)
{
- if (forced_idx < cluster->ta_count)
- {
- leaving = cluster->top_anchors[forced_idx]->other;
+ *idx = (forced_idx < cluster->ta_count ? forced_idx : straight_idx);
- end = g_graph_cluster_compute_incoming_link_position(cluster, forced_idx);
+ result = cluster->top_anchors[*idx];
- }
- else
- {
- leaving = cluster->top_anchors[straight_idx]->other;
+ }
- end = g_graph_cluster_compute_incoming_link_position(cluster, straight_idx);
+ else
+ result = NULL;
- }
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : cluster = graphique de blocs à manipuler. *
+* *
+* Description : Organise la disposition d'un ensemble de blocs basiques. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void g_graph_cluster_dispatch_x(GGraphCluster *cluster)
+{
+ size_t idx; /* Indice de lien d'arrivée */
+ incoming_link_t *incoming; /* Arrivée de lien */
+ leaving_link_t *leaving; /* Départ de lien */
+ gint start; /* Position initiale de départ */
+ gint end; /* Position initiale d'arrivée */
+ size_t i; /* Boucle de parcours #1 */
+ leaving_link_t *straight_leaving; /* Lien à présenter vertical */
+ size_t straight_index; /* Indice du lien vertical */
+ gint straight_start; /* Position initiale de départ */
+ size_t straight_level; /* Rang atteint en ligne droite*/
+ const graph_rank_t *rank; /* Accès confortable au rang */
+ size_t j; /* Boucle de parcours #2 */
+ GGraphCluster *target; /* Unique sous-bloc visé */
+
+ /**
+ * Traitement amont : alignement sur une éventuelle origine.
+ */
+
+ incoming = g_graph_cluster_find_real_straight_incoming(cluster, &idx);
+
+ if (incoming != NULL)
+ {
+ leaving = incoming->other;
start = g_graph_cluster_compute_leaving_link_position(leaving->owner, leaving->index);
+ end = g_graph_cluster_compute_incoming_link_position(cluster, idx);
+
g_graph_cluster_offset_x(cluster, start - end);
}
@@ -897,15 +925,13 @@ void g_graph_cluster_dispatch_x(GGraphCluster *cluster)
{
if (get_graph_rank(rank) < straight_level)
{
- start = straight_start;
-
/* Répartition à gauche du lien */
for (j = rank->count; j > 0; j--)
if (*rank->clusters[j - 1]->parent_index < straight_index)
break;
- start -= LINK_MARGIN;
+ start = straight_start - LINK_MARGIN;
_place_graph_rank_clusters(rank->clusters, j, start, -1);
@@ -915,7 +941,7 @@ void g_graph_cluster_dispatch_x(GGraphCluster *cluster)
if (*rank->clusters[j]->parent_index > straight_index)
break;
- start += 2 * LINK_MARGIN;
+ start = straight_start + LINK_MARGIN + cluster->right_offset;
_place_graph_rank_clusters(rank->clusters + j, rank->count - j, start, 1);
@@ -974,11 +1000,12 @@ void g_graph_cluster_dispatch_x(GGraphCluster *cluster)
/******************************************************************************
* *
-* Paramètres : cluster = graphique de blocs à analyser. *
-* root = élément à ne jamais croiser dans la paternité. *
-* dir = préférence à actualiser si possible. [OUT] *
+* Paramètres : cluster = graphique de blocs à consulter. *
+* root = ensemble dont s'extraire. *
+* max = ordonnée maximale de la zone de travail. *
+* pos = abscisses minimale et maximale en bout. [OUT] *
* *
-* Description : Détermine une direction préférée pour la suite du bloc. *
+* Description : Calcule les abscisses extrèmes atteintes via liens de sortie.*
* *
* Retour : false si une incapacité de détermination a été rencontrée. *
* *
@@ -986,46 +1013,421 @@ void g_graph_cluster_dispatch_x(GGraphCluster *cluster)
* *
******************************************************************************/
-bool g_graph_cluster_get_exit_direction(const GGraphCluster *cluster, const GGraphCluster *root, LeavingLinkDir *dir)
+bool g_graph_cluster_compute_min_max_x_exit(const GGraphCluster *cluster, const GGraphCluster *root, gint pos[2])
{
bool result; /* Bilan à renvoyer */
size_t i; /* Boucle de parcours #1 */
const leaving_link_t *leaving; /* Lien sortant à traiter */
+ bool stop; /* Prépare la fin de parcours */
GGraphCluster *iter; /* Boucle de parcours #2 */
- LeavingLinkDir pref; /* Préférence du lien courant */
+ gint x; /* Abscisse rencontrée */
- result = true;
+ 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)
+ if (leaving->other->type == ILT_LOOP)
continue;
+ stop = leaving->cluster_exit;
+
/* Validation d'une sortie du cluster d'origine */
- for (iter = leaving->other->owner; iter != NULL; iter = iter->owner)
- if (iter == root)
- break;
+ if (stop)
+ {
+ for (iter = leaving->other->owner; iter != NULL; iter = iter->owner)
+ if (iter == root)
+ break;
- if (iter != NULL)
- continue;
+ stop = (iter == NULL);
+
+ }
+
+ /* Poursuite du lien */
+
+ if (stop)
+ {
+ x = compute_leaving_link_position(leaving);
+
+ if (x < pos[0])
+ {
+ pos[0] = x;
+ result = true;
+ }
+
+ if (x > pos[1])
+ {
+ pos[1] = x;
+ result = true;
+ }
+
+ }
+
+ else
+ result |= g_graph_cluster_compute_min_max_x_exit(leaving->other->owner, root, pos);
+
+ }
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : cluster = graphique de blocs à consulter. *
+* max = profondeur maximale des traitements en ordonnée. *
+* pos = ordonnées minimale et maximale en bout. [OUT] *
+* *
+* Description : Calcule les abscisses extrèmes atteintes horizontalement. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void g_graph_cluster_compute_min_max_horizontal(const GGraphCluster *cluster, gint max, gint pos[2])
+{
+ size_t i; /* Boucle de parcours */
+ const leaving_link_t *leaving; /* Lien sortant du bloc */
+
+ if (cluster->alloc.y < max)
+ {
+ if (cluster->alloc.x < pos[0])
+ pos[0] = cluster->alloc.x;
+
+ if ((cluster->alloc.x + cluster->alloc.width) > pos[1])
+ pos[1] = cluster->alloc.x + cluster->alloc.width;
+
+ for (i = 0; i < cluster->ba_count; i++)
+ {
+ leaving = cluster->bottom_anchors[i];
+
+ if (leaving->other->type == ILT_LOOP)
+ continue;
+
+ g_graph_cluster_compute_min_max_horizontal(leaving->other->owner, max, pos);
+
+ }
+
+ }
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : cluster = graphique de blocs à manipuler. *
+* *
+* Description : Définit d'éventuels décalages pour les lignes verticales. *
+* *
+* Retour : true si un changement est survenu, false sinon. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+bool g_graph_cluster_dispatch_define_extra_offset(GGraphCluster *cluster)
+{
+ bool result; /* Evolution à retourner */
+ size_t i; /* Boucle de parcours #1 */
+ leaving_link_t *straight_leaving; /* Lien à présenter vertical */
+ size_t straight_index; /* Indice du lien vertical */
+ gint straight_start; /* Position initiale de départ */
+ size_t straight_level; /* Rang atteint en ligne droite*/
+ const graph_rank_t *rank; /* Accès confortable au rang */
+ size_t j; /* Boucle de parcours #2 */
+ gint straight_depth; /* Profondeur du lien vertical */
+ gint depth; /* Profondeur du lien voisin */
+ gint x_exit[2]; /* Bornes des liens de sortie */
+#ifndef NDEBUG
+ bool status; /* Validation des obtentions */
+#endif
+ gint x_used[2]; /* Bornes d'utilisations */
+ bool changed; /* Note un changement d'état */
+ gint offset; /* Décalage à appliquer */
+ GGraphCluster *parent; /* Racine pour les mises à jour*/
+ GGraphCluster *target; /* Unique sous-bloc visé */
+ leaving_link_t *leaving; /* Départ de lien */
+
+ result = false;
+
+ /**
+ * Le corps de cette fonction est calqué sur celui de g_graph_cluster_dispatch_x(),
+ * à partir du traitement amon.
+ *
+ * Toute modification dans ces parties doit donc être synchronisée.
+ */
+
+ /* Recherche d'une limite verticale */
+
+ straight_leaving = NULL;
+
+ for (i = 0; i < cluster->ba_count; i++)
+ if (SHOULD_BE_VERTICAL(cluster->bottom_anchors[i]))
+ {
+ straight_leaving = cluster->bottom_anchors[i];
+ straight_index = i;
+
+ straight_start = g_graph_cluster_compute_leaving_link_position(cluster, i);
+ straight_level = straight_leaving->straight_level;
+
+ break;
+
+ }
+
+ /* Il est désormais temps de placer tous les blocs de code inférieurs. */
+
+ for (i = 0; i < cluster->ranks_count; i++)
+ {
+ rank = &cluster->ranks[i];
+
+ /* Répartition autour d'une ligne verticale */
+ if (straight_leaving != NULL)
+ {
+ if (get_graph_rank(rank) < straight_level)
+ {
+ /* Répartition à gauche du lien */
+
+ for (j = rank->count; j > 0; j--)
+ if (*rank->clusters[j - 1]->parent_index < straight_index)
+ break;
+
+ /* Répartition à droite du lien */
+
+ for (j = 0; j < rank->count; j++)
+ if (*rank->clusters[j]->parent_index > straight_index)
+ break;
+
+ if (j < rank->count)
+ {
+ if (straight_leaving->cluster_exit)
+ {
+ straight_depth = straight_leaving->other->owner->alloc.y;
+
+ depth = G_MAXINT;
+
+ if (g_graph_cluster_compute_min_y_target(rank->clusters[j], cluster, &depth))
+ {
+ x_exit[0] = G_MAXINT;
+ x_exit[1] = G_MININT;
+
+#ifndef NDEBUG
+ status = g_graph_cluster_compute_min_max_x_exit(rank->clusters[j], cluster, x_exit);
+ assert(status);
+#else
+ g_graph_cluster_compute_min_max_x_exit(rank->clusters[j], cluster, x_exit);
+#endif
+
+ x_used[0] = G_MAXINT;
+ x_used[1] = G_MININT;
+
+ changed = false;
+
+ if (straight_depth > depth)
+ {
+ g_graph_cluster_compute_min_max_horizontal(rank->clusters[j],
+ straight_depth, x_used);
+
+ if (straight_start > x_used[0])
+ {
+ offset = straight_start - x_used[0] + LINK_MARGIN;
+
+ if (offset != 0)
+ {
+ cluster->right_offset += offset;
+ changed = true;
+ }
+
+ }
+
+ }
+
+ else
+ {
+ g_graph_cluster_compute_min_max_horizontal(straight_leaving->other->owner,
+ depth, x_used);
+
+ if (x_used[1] > x_exit[0])
+ {
+ offset = x_used[1] - x_exit[0] + LINK_MARGIN;
+
+ if (offset != 0)
+ {
+ cluster->right_offset += offset;
+ changed = true;
+ }
+
+ }
+
+ }
+
+ /* Réorganisation suite à changement ? */
+ if (changed)
+ {
+ result = true;
+
+ parent = cluster->owner;
+
+ if (parent != NULL)
+ {
+ g_graph_cluster_sort_leaving_links(parent);
+
+ for (i = 0; i < parent->ranks_count; i++)
+ reset_graph_rank_allocation(&parent->ranks[i]);
+
+ g_graph_cluster_dispatch_x(parent);
+
+ g_graph_cluster_set_y(parent, parent->alloc.y);
+
+ g_graph_cluster_sort_leaving_links(parent);
+
+ }
+
+ }
+
+ }
+
+ }
+
+ }
+
+ result |= visit_and_accumulate_graph_rank(rank, g_graph_cluster_dispatch_define_extra_offset);
+
+ }
+
+ else if (get_graph_rank(rank) == straight_level)
+ {
+ result |= visit_and_accumulate_graph_rank(rank, g_graph_cluster_dispatch_define_extra_offset);
+
+ straight_leaving = NULL;
+
+ goto look_for_forced;
+
+ }
+
+ else
+ assert(false);
+
+ }
+
+ /* Répartition homogène */
+ else
+ {
+ result |= visit_and_accumulate_graph_rank(rank, g_graph_cluster_dispatch_define_extra_offset);
+
+ look_for_forced:
+
+ /* Lien vertical interne ? */
- pref = get_leaving_link_direction(leaving);
+ if (rank->count != 1)
+ continue;
+
+ target = rank->clusters[0];
+
+ if (target->ba_count != 1)
+ continue;
+
+ leaving = target->bottom_anchors[0];
+
+ if (leaving->forced_straight)
+ {
+ straight_leaving = leaving;
+ straight_index = 0;
+
+ straight_start = g_graph_cluster_compute_leaving_link_position(target, 0);
+ straight_level = leaving->straight_level;
- /* 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 à analyser. *
+* x1 = abscisse de départ du lien d'origine. *
+* max = ordonnée la plus profonde à ne pas dépasser. *
+* *
+* Description : Détermine une direction préférée pour la suite du bloc. *
+* *
+* Retour : false si une incapacité de détermination a été rencontrée. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+LeavingLinkDir g_graph_cluster_get_link_direction(const GGraphCluster *cluster, gint x1, gint max)
+{
+ LeavingLinkDir result; /* Préférence à retourner */
+ size_t left_points; /* Nombre de voix à gauche */
+ size_t left_straight; /* Nombre de voix à gauche bis */
+ size_t right_points; /* Nombre de voix à droite */
+ size_t right_straight; /* Nombre de voix à droite bis */
+ size_t i; /* Boucle de parcours #1 */
+ const leaving_link_t *leaving; /* Lien sortant à traiter */
+ LeavingLinkDir pref; /* Préférence du lien courant */
+
+ /* Analyse des différents liens */
+
+ left_points = 0;
+ left_straight = 0;
+ right_points = 0;
+ right_straight = 0;
+
+ for (i = 0; i < cluster->ba_count; i++)
+ {
+ leaving = cluster->bottom_anchors[i];
+
+ if (leaving->other->type == ILT_LOOP)
+ continue;
+
+ pref = get_leaving_link_direction(leaving, x1, max);
+
+ if (pref == LLD_TO_LEFT)
+ {
+ left_points++;
+ if (SHOULD_BE_VERTICAL(leaving))
+ left_straight++;
+ }
+ else
+ {
+ right_points++;
+ if (SHOULD_BE_VERTICAL(leaving))
+ right_straight++;
+ }
+
+ }
+
+ /* Décompte des points et élection du gagnant ! */
+
+ if (left_points > right_points)
+ result = LLD_TO_LEFT;
+
+ else if (left_points < right_points)
+ result = LLD_TO_RIGHT;
+
+ else
+ {
+ if (left_straight > right_straight)
+ result = LLD_TO_LEFT;
+
+ else if (left_straight < right_straight)
+ result = LLD_TO_RIGHT;
+
+ else
+ result = LLD_NO_PREF;
+
+ }
return result;
@@ -1046,6 +1448,10 @@ bool g_graph_cluster_get_exit_direction(const GGraphCluster *cluster, const GGra
void g_graph_cluster_sort_leaving_links(GGraphCluster *cluster)
{
+ gint max; /* Borne pour la profondeur */
+ size_t lr_sep; /* Séparation gauche / droite */
+ leaving_link_t *leaving; /* Lien sortant à traiter */
+ incoming_link_t *straight; /* Lien entrant vertical ? */
size_t i; /* Boucle de parcours */
leaving_link_t **left; /* Liens à placer à gauche */
leaving_link_t **center; /* Liens à placer au milieu */
@@ -1053,21 +1459,53 @@ void g_graph_cluster_sort_leaving_links(GGraphCluster *cluster)
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 */
+ gint x1; /* Abscisse de départ de lien */
/**
- * On n'intervient que s'il y a lieu de le faire, notamment si les sorties
- * du groupe de blocs ont une direction claire.
+ * On n'intervient que s'il y a lieu de le faire...
*/
- pref = LLD_NO_PREF;
-
- if (!g_graph_cluster_get_exit_direction(cluster, cluster, &pref))
+ if (cluster->ba_count < 2)
goto done;
- if (cluster->ba_count < 2 || pref == LLD_NO_PREF)
- goto done;
+ /**
+ * Détermination de la profondeur maximale, à partir des liens verticaux.
+ *
+ * Ces liens seront centraux, donc inutile de déterminer la direction
+ * des autres liens passée une certaine profondeur verticale.
+ */
+
+ max = 0;
+ lr_sep = cluster->ba_count;
+
+ for (i = 0; i < cluster->ba_count; i++)
+ {
+ leaving = cluster->bottom_anchors[i];
+
+ straight = g_graph_cluster_find_real_straight_incoming(leaving->other->owner, (size_t []){ 0 });
+
+ if (straight == leaving->other)
+ {
+ /**
+ * Il ne peut y avoir à priori qu'un seul lien vertical au départ
+ * d'un bloc donné.
+ */
+ assert(max == 0);
+
+ max = leaving->other->owner->alloc.y;
+ lr_sep = i;
+
+ }
+
+ }
+
+ if (max == 0)
+ max = G_MAXINT;
+
+ /**
+ * Phase de réorganisation effective.
+ */
left = NULL;
center = NULL;
@@ -1083,21 +1521,15 @@ void g_graph_cluster_sort_leaving_links(GGraphCluster *cluster)
{
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;
+ if (i == lr_sep)
+ pref = LLD_NO_PREF;
- }
else
{
- pref = LLD_NO_PREF;
+ x1 = compute_leaving_link_position(leaving);
- if (!g_graph_cluster_get_exit_direction(leaving->other->owner, leaving->other->owner, &pref))
- pref = LLD_NO_PREF;
+ pref = get_leaving_link_direction(leaving, x1, max);
}
@@ -1132,7 +1564,7 @@ void g_graph_cluster_sort_leaving_links(GGraphCluster *cluster)
{
qsort_r(left, left_count, sizeof(leaving_link_t *),
(__compar_d_fn_t)cmp_leaving_links,
- (LeavingLinkDir []) { LLD_TO_LEFT });
+ (leaving_cmp_info_t []) { { .root = cluster, .dir = LLD_TO_LEFT } });
for (i = 0; i < left_count; i++)
cluster->bottom_anchors[cluster->ba_count++] = left[i];
@@ -1154,7 +1586,7 @@ void g_graph_cluster_sort_leaving_links(GGraphCluster *cluster)
{
qsort_r(right, right_count, sizeof(leaving_link_t *),
(__compar_d_fn_t)cmp_leaving_links,
- (LeavingLinkDir []) { LLD_TO_RIGHT });
+ (leaving_cmp_info_t []) { { .root = cluster, .dir = LLD_TO_RIGHT } });
for (i = 0; i < right_count; i++)
cluster->bottom_anchors[cluster->ba_count++] = right[i];
@@ -1194,21 +1626,24 @@ void g_graph_cluster_sort_leaving_links(GGraphCluster *cluster)
/******************************************************************************
* *
* Paramètres : cluster = graphique de blocs à consulter. *
-* pos = ordonnées minimale et maximale en bout. [OUT] *
+* root = ensemble dont s'extraire. *
+* pos = ordonnée minimale en bout. [OUT] *
* *
* Description : Calcule les ordonnées extrèmes atteintes via liens sortants. *
* *
-* Retour : true si un lien sortant a été trouvé, false sinon. *
+* Retour : false si une incapacité de détermination a été rencontrée. *
* *
* Remarques : - *
* *
******************************************************************************/
-bool g_graph_cluster_compute_min_max_bottom(const GGraphCluster *cluster, gint pos[2])
+bool g_graph_cluster_compute_min_y_target(const GGraphCluster *cluster, const GGraphCluster *root, gint *pos)
{
- bool result; /* Bilan à retourner */
- 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 */
+ bool stop; /* Prépare la fin de parcours */
+ GGraphCluster *iter; /* Boucle de parcours #2 */
gint y; /* Ordonnée rencontrée */
result = false;
@@ -1217,23 +1652,41 @@ bool g_graph_cluster_compute_min_max_bottom(const GGraphCluster *cluster, gint p
{
leaving = cluster->bottom_anchors[i];
- if (!leaving->cluster_exit)
+ if (leaving->other->type == ILT_LOOP)
continue;
- result = true;
+ stop = leaving->cluster_exit;
- y = leaving->other->owner->alloc.y;
+ /* Validation d'une sortie du cluster d'origine */
- if (y < pos[0])
- pos[0] = y;
+ if (stop)
+ {
+ for (iter = leaving->other->owner; iter != NULL; iter = iter->owner)
+ if (iter == root)
+ break;
- if (pos[1] < y)
- pos[1] = y;
+ stop = (iter == NULL);
- }
+ }
- for (i = 0; i < cluster->ranks_count; i++)
- result |= compute_graph_rank_min_max_bottom(&cluster->ranks[i], pos);
+ /* Poursuite du lien ? */
+
+ if (stop)
+ {
+ y = leaving->other->owner->alloc.y;
+
+ if (y < *pos)
+ {
+ *pos = y;
+ result = true;
+ }
+
+ }
+
+ else
+ result |= g_graph_cluster_compute_min_y_target(leaving->other->owner, root, pos);
+
+ }
return result;
@@ -1318,148 +1771,6 @@ int g_graph_cluster_compare_by_origin(const GGraphCluster **cluster, const GGrap
/******************************************************************************
* *
-* Paramètres : cluster = graphique de blocs à consulter. *
-* stop = chef de file marquant l'arrêt des consultations. *
-* pos = ordonnées minimale et maximale en bout. [OUT] *
-* *
-* Description : Calcule les abscisses extrèmes atteintes horizontalement. *
-* *
-* Retour : - *
-* *
-* Remarques : - *
-* *
-******************************************************************************/
-
-void g_graph_cluster_compute_min_max_horizontal(const GGraphCluster *cluster, const GGraphCluster *stop, gint pos[2])
-{
- size_t i; /* Boucle de parcours */
- const leaving_link_t *leaving; /* Lien sortant du bloc */
-
- if (cluster->alloc.y < stop->alloc.y)
- {
- if (cluster->alloc.x < pos[0])
- pos[0] = cluster->alloc.x;
-
- if ((cluster->alloc.x + cluster->alloc.width) > pos[1])
- pos[1] = cluster->alloc.x + cluster->alloc.width;
-
- for (i = 0; i < cluster->ba_count; i++)
- {
- leaving = cluster->bottom_anchors[i];
-
- if (leaving->other->type == ILT_LOOP)
- continue;
-
- g_graph_cluster_compute_min_max_horizontal(leaving->other->owner, stop, pos);
-
- }
-
- }
-
-}
-
-
-/******************************************************************************
-* *
-* Paramètres : cluster = graphique de blocs à manipuler. *
-* *
-* Description : S'assure que les liens verticaux ne traversent pas de bloc. *
-* *
-* Retour : - *
-* *
-* Remarques : - *
-* *
-******************************************************************************/
-
-void g_graph_cluster_ensure_space_for_straight(GGraphCluster *cluster)
-{
- size_t i; /* Boucle de parcours */
- size_t first; /* Premier lien vertical */
- size_t last; /* Dernier lien vertical */
- size_t straight_level; /* Rang atteint en ligne droite*/
- GGraphCluster *stop; /* Borne d'arrêt correspondante*/
- const leaving_link_t *leaving; /* Lien sortant du bloc */
- gint pos[2]; /* Bornes horizontales */
- gint max; /* Borne horizontale */
-
- for (i = 0; i < cluster->ranks_count; i++)
- visit_graph_rank(&cluster->ranks[i], g_graph_cluster_ensure_space_for_straight);
-
- first = cluster->ba_count;
- last = 0;
-
- straight_level = 0;
- stop = NULL;
-
- for (i = 0; i < cluster->ba_count; i++)
- {
- leaving = cluster->bottom_anchors[i];
-
- if (leaving->straight)
- {
- if (first == cluster->ba_count)
- first = i;
-
- last = i;
-
- if (straight_level < leaving->straight_level)
- {
- straight_level = leaving->straight_level;
- stop = leaving->other->owner;
- }
-
- }
-
- }
-
- if (stop != NULL)
- {
- if (first > 0)
- {
- pos[0] = G_MAXINT;
- pos[1] = 0;
-
- for (i = 0; i < first; i++)
- {
- leaving = cluster->bottom_anchors[i];
- g_graph_cluster_compute_min_max_horizontal(leaving->other->owner, stop, pos);
- }
-
- max = compute_leaving_link_position(cluster->bottom_anchors[first]);
-
- if ((pos[1] + LINK_MARGIN) > max)
- {
- cluster->right_offset = (pos[0] + LINK_MARGIN) - max;
- assert(false);
- }
-
- }
-
- if ((last + 1) < cluster->ba_count)
- {
- pos[0] = G_MAXINT;
- pos[1] = 0;
-
- for (i = last + 1; i < cluster->ba_count; i++)
- {
- leaving = cluster->bottom_anchors[i];
- g_graph_cluster_compute_min_max_horizontal(leaving->other->owner, stop, pos);
- }
-
- max = compute_leaving_link_position(cluster->bottom_anchors[last]);
-
- if ((max + LINK_MARGIN) > pos[0])
- cluster->right_offset = (max + LINK_MARGIN) - pos[0];
-
- }
-
- }
-
-}
-
-
-/******************************************************************************
-* *
* Paramètres : cluster = graphique de blocs à manipuler. *
* *
* Description : Réorganise au besoin les liens entrants d'un bloc. *
@@ -1604,7 +1915,6 @@ void g_graph_cluster_reorder_link_origins(GGraphCluster *cluster, bool left)
void g_graph_cluster_offset_x(GGraphCluster *cluster, gint offset)
{
size_t i; /* Boucle de parcours */
-
cluster->alloc.x += offset;
for (i = 0; i < cluster->ranks_count; i++)
@@ -1756,8 +2066,6 @@ void g_graph_cluster_compute_needed_alloc(const GGraphCluster *cluster, GtkAlloc
}
- alloc->width += cluster->right_offset;
-
}
@@ -2641,6 +2949,7 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList *
GHashTable *all; /* Collection des créations */
size_t count; /* Taille de la liste de blocs */
pending_blocks *pending; /* Suivi des blocs à traiter */
+ bool loop; /* Ordre de relance */
GtkAllocation needed; /* Taille requise */
/* Création des éléments */
@@ -2685,26 +2994,32 @@ GGraphCluster *bootstrap_graph_cluster(GLoadedBinary *binary, const GBlockList *
g_graph_cluster_sort_leaving_links(result);
/**
- * On vérifie maintenant que les liens bien verticaux ne rencontrent pas
- * de bloc de code.
+ * Un effet de bord de l'organisation en rangs de profondeur est que, dans
+ * une situation où les blocs sont placés de part et d'autre d'un lien vertical,
+ * ce lien vertical n'a d'influence que sur les blocs du même cluster.
+ *
+ * Les positions sont en effet déterminés via la fonction g_graph_cluster_dispatch_x().
*
- * Pour celà, il faut disposer d'une cartographie complète :
+ * Si un bloc d'un rang a des enfants qui ne sont pas dominés, la taille de
+ * ces enfants n'est pas prise en compte pour s'assurer du respect du lien
+ * vertical.
*
- * - sur l'axe des abscisses pour les positions à compenser.
- * - sur l'axe des ordonnées pour borner les suivis de liens en profondeur.
+ * On calcule ici un décalage de compensation. Et comme l'opération est de
+ * nature à réorganiser les blocs, on itère le nombre de fois nécessaires.
*/
- g_graph_cluster_reset_allocation(result);
-
- g_graph_cluster_dispatch_x(result);
+ do
+ {
+ g_graph_cluster_reset_allocation(result);
- g_graph_cluster_compute_needed_alloc(result, &needed);
+ g_graph_cluster_dispatch_x(result);
- g_graph_cluster_offset_x(result, -needed.x);
+ g_graph_cluster_set_y(result, 0);
- g_graph_cluster_set_y(result, 0);
+ loop = g_graph_cluster_dispatch_define_extra_offset(result);
- g_graph_cluster_ensure_space_for_straight(result);
+ }
+ while (loop);
/**
* A ce point, tous les blocs sont placés.
diff --git a/src/gtkext/graph/leaving.c b/src/gtkext/graph/leaving.c
index 3147784..70db5f3 100644
--- a/src/gtkext/graph/leaving.c
+++ b/src/gtkext/graph/leaving.c
@@ -111,6 +111,8 @@ gint compute_leaving_link_position(const leaving_link_t *link)
/******************************************************************************
* *
* Paramètres : link = information sur un lien à consulter. *
+* x1 = abscisse de départ du lien d'origine. *
+* max = ordonnée la plus profonde à ne pas dépasser. *
* *
* Description : Détermine une direction prise par un lien à son départ. *
* *
@@ -120,30 +122,51 @@ gint compute_leaving_link_position(const leaving_link_t *link)
* *
******************************************************************************/
-LeavingLinkDir get_leaving_link_direction(const leaving_link_t *link)
+LeavingLinkDir get_leaving_link_direction(const leaving_link_t *link, gint x1, gint max)
{
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 */
+ GtkAllocation alloc; /* Emplacement reservé */
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);
+ g_graph_cluster_get_allocation(owner, &alloc);
- x2 = g_graph_cluster_compute_incoming_link_position(owner, idx);
+ if (alloc.y > max)
+ result = LLD_NO_PREF;
- if (x1 < x2)
- result = LLD_TO_RIGHT;
+ else
+ {
+ result = g_graph_cluster_get_link_direction(owner, x1, max);
- else if (x1 > x2)
- result = LLD_TO_LEFT;
+ if (result == LLD_NO_PREF)
+ {
+ /**
+ * Les liens ne sont pas encore ordonnés avec leur indice final.
+ * Donc on choisit de faire au plus simple, et donc au plus rapide.
+ *
+ * Une alternative viable, mais tout aussi imprécise, serait d'appeler :
+ *
+ * idx = g_graph_cluster_find_incoming_link(owner, link);
+ *
+ * x2 = g_graph_cluster_compute_incoming_link_position(owner, idx);
+ */
- else
- result = LLD_NO_PREF;
+ x2 = alloc.x + alloc.width / 2;
+
+ if (x1 < x2)
+ result = LLD_TO_RIGHT;
+
+ else if (x1 > x2)
+ result = LLD_TO_LEFT;
+
+ else
+ result = LLD_NO_PREF;
+
+ }
+
+ }
return result;
@@ -152,9 +175,9 @@ LeavingLinkDir get_leaving_link_direction(const leaving_link_t *link)
/******************************************************************************
* *
-* Paramètres : a = premier lien entrant à comparer. *
-* b = second lien entrant à comparer. *
-* dir = complément d'information quant à la direction traitée. *
+* Paramètres : a = premier lien entrant à comparer. *
+* b = second lien entrant à comparer. *
+* info = compléments d'information pour l'opération. *
* *
* Description : Compare deux liens sortants. *
* *
@@ -164,66 +187,52 @@ LeavingLinkDir get_leaving_link_direction(const leaving_link_t *link)
* *
******************************************************************************/
-int cmp_leaving_links(const leaving_link_t **a, const leaving_link_t **b, const LeavingLinkDir *dir)
+int cmp_leaving_links(const leaving_link_t **a, const leaving_link_t **b, const const leaving_cmp_info_t *info)
{
int result; /* Bilan à retourner */
GGraphCluster *owner; /* Raccourci vers le proprio */
- gint pos_a[2]; /* Points de départ pour A */
+ gint pos_a; /* Point de départ pour A */
GtkAllocation alloc; /* Emplacement de cluster */
- gint pos_b[2]; /* Points de départ pour B */
+ gint pos_b; /* Point 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;
+ pos_a = G_MAXINT;
- if (!g_graph_cluster_compute_min_max_bottom(owner, pos_a))
+ if (!g_graph_cluster_compute_min_y_target((*a)->other->owner, info->root, &pos_a))
{
g_graph_cluster_get_allocation(owner, &alloc);
- pos_a[0] = alloc.y;
- pos_a[1] = alloc.y;
+ pos_a = alloc.y;
}
owner = (*b)->other->owner;
- pos_b[0] = G_MAXINT;
- pos_b[1] = 0;
+ pos_b = G_MAXINT;
- if (!g_graph_cluster_compute_min_max_bottom(owner, pos_b))
+ if (!g_graph_cluster_compute_min_y_target((*b)->other->owner, info->root, &pos_b))
{
g_graph_cluster_get_allocation(owner, &alloc);
- pos_b[0] = alloc.y;
- pos_b[1] = alloc.y;
+ pos_b = alloc.y;
}
/* Comparaison */
- if (pos_a[1] < pos_b[1])
+ if (pos_a < pos_b)
result = -1;
- else if (pos_a[1] > pos_b[1])
+ else if (pos_a > pos_b)
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;
-
- }
+ result = 0;
- if (*dir == LLD_TO_RIGHT)
+ if (info->dir == LLD_TO_RIGHT)
result *= -1;
return result;
diff --git a/src/gtkext/graph/leaving.h b/src/gtkext/graph/leaving.h
index b81e1ca..fc949db 100644
--- a/src/gtkext/graph/leaving.h
+++ b/src/gtkext/graph/leaving.h
@@ -71,10 +71,18 @@ typedef enum _LeavingLinkDir
} LeavingLinkDir;
/* Détermine une direction prise par un lien à son départ. */
-LeavingLinkDir get_leaving_link_direction(const leaving_link_t *);
+LeavingLinkDir get_leaving_link_direction(const leaving_link_t *, gint, gint);
-/* Compare deux liens sortants. */
-int cmp_leaving_links(const leaving_link_t **, const leaving_link_t **, const LeavingLinkDir *);
+/* Transmision d'éléments pour comparaisons */
+typedef struct _leaving_cmp_info_t
+{
+ GGraphCluster *root;
+ LeavingLinkDir dir;
+
+} leaving_cmp_info_t;
+
+/*Compare deux liens sortants. */
+int cmp_leaving_links(const leaving_link_t **a, const leaving_link_t **b, const leaving_cmp_info_t *);
diff --git a/src/gtkext/graph/rank.c b/src/gtkext/graph/rank.c
index bffefe9..54b5415 100644
--- a/src/gtkext/graph/rank.c
+++ b/src/gtkext/graph/rank.c
@@ -126,6 +126,33 @@ void visit_graph_rank(const graph_rank_t *grank, graph_rank_cb cb)
* *
* Paramètres : grank = ensemble de même rang à consulter. *
* *
+* Description : Parcours l'ensemble des blocs du rang avec un visiteur. *
+* *
+* Retour : Bilan à retourner. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+bool visit_and_accumulate_graph_rank(const graph_rank_t *grank, graph_rank_acc_cb cb)
+{
+ bool result; /* Bilan cumulé à renvoyer */
+ size_t i; /* Boucle de parcours */
+
+ result = false;
+
+ for (i = 0; i < grank->count; i++)
+ result |= cb(grank->clusters[i]);
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : grank = ensemble de même rang à consulter. *
+* *
* Description : Assigne à un ensemble de blocs un emplacement initial. *
* *
* Retour : - *
@@ -516,63 +543,6 @@ void dispatch_x_graph_rank(const graph_rank_t *grank)
/******************************************************************************
* *
-* 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 : false si une incapacité de détermination a été rencontrée. *
-* *
-* Remarques : - *
-* *
-******************************************************************************/
-
-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 */
-
- result = true;
-
- for (i = 0; i < grank->count && result; i++)
- result = g_graph_cluster_get_exit_direction(grank->clusters[i], root, dir);
-
- return result;
-
-}
-
-
-/******************************************************************************
-* *
-* 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. *
-* *
-* 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. *
* *
diff --git a/src/gtkext/graph/rank.h b/src/gtkext/graph/rank.h
index e28b1f0..6536378 100644
--- a/src/gtkext/graph/rank.h
+++ b/src/gtkext/graph/rank.h
@@ -61,6 +61,12 @@ 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);
+/* Visiteur pour blocs */
+typedef bool (* graph_rank_acc_cb) (GGraphCluster *);
+
+/* Parcours l'ensemble des blocs du rang avec un visiteur. */
+bool visit_and_accumulate_graph_rank(const graph_rank_t *, graph_rank_acc_cb);
+
/* Assigne à un ensemble de blocs un emplacement initial. */
void reset_graph_rank_allocation(const graph_rank_t *);
@@ -94,12 +100,6 @@ void _place_graph_rank_clusters(GGraphCluster **, size_t, gint, int);
/* Organise la disposition d'un ensemble de blocs basiques. */
void dispatch_x_graph_rank(const graph_rank_t *);
-/* Réorganise au besoin les liens entrants un ensemble de blocs. */
-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éorganise au besoin les blocs selon les liens d'origine. */
void reorder_graph_rank_clusters(graph_rank_t *, const GGraphCluster *);