From f65f83fd222d14934b527152899359327813128e Mon Sep 17 00:00:00 2001 From: Cyrille Bagard Date: Fri, 15 Mar 2019 11:55:03 +0100 Subject: Tracked vertical links beyond their cluster. --- src/gtkext/graph/cluster-int.h | 27 +- src/gtkext/graph/cluster.c | 811 ++++++++++++++++++++++++++++------------- src/gtkext/graph/leaving.c | 95 ++--- src/gtkext/graph/leaving.h | 14 +- src/gtkext/graph/rank.c | 84 ++--- src/gtkext/graph/rank.h | 12 +- 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 *); -- cgit v0.11.2-87-g4458