summaryrefslogtreecommitdiff
path: root/src/gtkext/graph/ranks.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/gtkext/graph/ranks.c')
-rw-r--r--src/gtkext/graph/ranks.c463
1 files changed, 446 insertions, 17 deletions
diff --git a/src/gtkext/graph/ranks.c b/src/gtkext/graph/ranks.c
index 6121907..65e40fd 100644
--- a/src/gtkext/graph/ranks.c
+++ b/src/gtkext/graph/ranks.c
@@ -32,16 +32,68 @@
+/* ---------------------- MANIPULATION DES PORTES HORIZONTALES ---------------------- */
+
+
+/* Etendue horizontale d'un lien */
+typedef struct _reserved_hspan
+{
+ gint x1; /* Départ d'une ligne */
+ gint x2; /* Arrivée de cette même ligne */
+
+} reserved_hspan;
+
+/* Lignes de liens d'un même niveau */
+typedef struct _links_spans
+{
+ reserved_hspan *hspans; /* Lignes sans chevauchement */
+ size_t count; /* Nombre de ces lignes */
+
+} links_spans;
+
+
+/* Initialise les futures portées d'un même niveau. */
+static void init_links_spans(links_spans *);
+
+/* Regarde si des portées horizontales se chevauchent ou non. */
+static bool is_intersection_with_spans(const links_spans *, const reserved_hspan *);
+
+/* Ajoute une réservation à un ensemble de portées horizontales. */
+static void extend_links_spans(links_spans *, const reserved_hspan *);
+
+
+
+/* ------------------------ GESTION D'UN ETAGE DE CLASSEMENT ------------------------ */
+
+
/* Information relatives à un rang de classement */
typedef struct _rank_props
{
- gint top_margin; /* Espace supérieur pour liens */
- gint height; /* Hauteur minimale */
+ links_spans *top_spans; /* Niveaux de lignes supérieurs*/
+ hspan_slot_t top_count; /* Nbre des niveaux de lignes */
+ links_spans *bottom_spans; /* Niveaux de lignes inférieurs*/
+ hspan_slot_t bottom_count; /* Nbre des niveaux de lignes */
- gint final_y; /* Ordonnée finale */
+ gint height; /* Hauteur minimale */
+ gint y; /* Ordonnée finale */
} rank_props;
+
+/* Réserve une portion de hauteur pour un lien. */
+static hspan_slot_t reserve_span_in_rank_props(rank_props *, gint, gint, bool);
+
+/* Calcule la position verticale du rang de classement. */
+static gint compute_rank_props_y_pos(rank_props *, gint *, gint);
+
+/* Fournit la position verticale obtenue par réservation. */
+static gint get_y_for_rank_props_hspan_slot(const rank_props *, hspan_slot_t, bool);
+
+
+
+/* ------------------------- CLASSEMENT VERTICAL DES NOEUDS ------------------------- */
+
+
/* Calcul de l'ordonnée des différents classements (instance) */
struct _GGraphRanks
{
@@ -50,6 +102,8 @@ struct _GGraphRanks
rank_props *props; /* Propriétés des rangs */
unsigned int count; /* Nombre de rangs présents */
+ gint height; /* Hauteur totale du graphique */
+
};
/* Calcul de l'ordonnée des différents classements (classe) */
@@ -74,6 +128,296 @@ static void g_graph_ranks_finalize(GGraphRanks *);
+/* ---------------------------------------------------------------------------------- */
+/* MANIPULATION DES PORTES HORIZONTALES */
+/* ---------------------------------------------------------------------------------- */
+
+
+/******************************************************************************
+* *
+* Paramètres : spans = liste à initialiser. *
+* *
+* Description : Initialise les futures portées d'un même niveau. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void init_links_spans(links_spans *spans)
+{
+ spans->hspans = NULL;
+ spans->count = 0;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : spans = liste de portées déjà en place. *
+* hspan = nouvelle portée à insérer quelque part. *
+* *
+* Description : Regarde si des portées horizontales se chevauchent ou non. *
+* *
+* Retour : true si les portées peuvent cohabiter, false sinon. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static bool is_intersection_with_spans(const links_spans *spans, const reserved_hspan *hspan)
+{
+ bool result; /* Bilan d'analyse à retourner */
+ size_t i; /* Boucle de parcours */
+
+ result = false;
+
+ for (i = 0; i < spans->count && !result; i++)
+ {
+ if (hspan->x1 < spans->hspans[i].x1)
+ result = hspan->x2 >= spans->hspans[i].x1;
+
+ else if (hspan->x1 > spans->hspans[i].x2)
+ result = hspan->x2 <= spans->hspans[i].x2;
+
+ else
+ {
+ result = spans->hspans[i].x1 < hspan->x1 && hspan->x1 < spans->hspans[i].x2;
+ result |= spans->hspans[i].x1 < hspan->x2 && hspan->x2 < spans->hspans[i].x2;
+ }
+
+ }
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : spans = liste de portées déjà en place. *
+* hspan = nouvelle portée à insérer quelque part. *
+* *
+* Description : Ajoute une réservation à un ensemble de portées horizontales.*
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void extend_links_spans(links_spans *spans, const reserved_hspan *new)
+{
+ spans->hspans = (reserved_hspan *)realloc(spans->hspans,
+ ++spans->count * sizeof(reserved_hspan));
+
+ if (new->x1 <= new->x2)
+ spans->hspans[spans->count - 1] = *new;
+ else
+ {
+ spans->hspans[spans->count - 1].x1 = new->x2;
+ spans->hspans[spans->count - 1].x2 = new->x1;
+ }
+
+}
+
+
+
+/* ---------------------------------------------------------------------------------- */
+/* GESTION D'UN ETAGE DE CLASSEMENT */
+/* ---------------------------------------------------------------------------------- */
+
+
+/******************************************************************************
+* *
+* Paramètres : props = propriétés de rang à mettre à jour. *
+* *
+* Description : Supprime les portions de hauteur pour un lien. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void reset_spans_in_rank_props(rank_props *props)
+{
+ hspan_slot_t i; /* Boucle de parcours */
+
+ for (i = 0; i < props->top_count; i++)
+ if (props->top_spans[i].hspans != NULL)
+ free(props->top_spans[i].hspans);
+
+ if (props->top_spans != NULL)
+ {
+ free(props->top_spans);
+ props->top_spans = NULL;
+ props->top_count = 0;
+ }
+
+ for (i = 0; i < props->bottom_count; i++)
+ if (props->bottom_spans[i].hspans != NULL)
+ free(props->bottom_spans[i].hspans);
+
+ if (props->bottom_spans != NULL)
+ {
+ free(props->bottom_spans);
+ props->bottom_spans = NULL;
+ props->bottom_count = 0;
+ }
+
+ props->y = 0;
+ props->height = 0;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : props = propriétés de rang à mettre à jour. *
+* x1 = début de la portée à réserver. *
+* x2 = fin de la portée à réserver. *
+* top = désignation de la zone à traiter. *
+* *
+* Description : Réserve une portion de hauteur pour un lien. *
+* *
+* Retour : Indice de la hauteur adaptée et réservée. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static hspan_slot_t reserve_span_in_rank_props(rank_props *props, gint x1, gint x2, bool top)
+{
+ hspan_slot_t result; /* Indice à retourner */
+ reserved_hspan hspan; /* Portée à constituer */
+ links_spans **list; /* Liste à parcourir */
+ hspan_slot_t *count; /* Taille de cette liste */
+
+ hspan.x1 = x1;
+ hspan.x2 = x2;
+
+ if (top)
+ {
+ list = &props->top_spans;
+ count = &props->top_count;
+ }
+ else
+ {
+ list = &props->bottom_spans;
+ count = &props->bottom_count;
+ }
+
+ for (result = 0; result < *count; result++)
+ if (!is_intersection_with_spans(&(*list)[result], &hspan))
+ break;
+
+ if (result == *count)
+ {
+ *list = (links_spans *)realloc(*list, ++(*count) * sizeof(links_spans));
+ init_links_spans(&(*list)[result]);
+ }
+
+ extend_links_spans(&(*list)[result], &hspan);
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : props = propriétés de rang à mettre à jour. *
+* y = ordonnée courante à faire évoluer. *
+* last_bottom = espace inférieur requis du niveau précédent. *
+* *
+* Description : Calcule la position verticale du rang de classement. *
+* *
+* Retour : Espace inférieur nécessaire au niveau de classement. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static gint compute_rank_props_y_pos(rank_props *props, gint *y, gint last_bottom)
+{
+ gint result; /* Espace Sud à retourner */
+ gint top_margin; /* Espace Nord nécessaire */
+
+ /* Espace supérieur pour les liens */
+
+ top_margin = last_bottom;
+
+ if (props->top_count > 0)
+ {
+ top_margin += props->top_count * EDGE_VERTICAL_MIN_SEP;
+ top_margin += EDGE_SLOT_VERT_MARGIN;
+ }
+
+ /**
+ * L'espace vertical entre les noeuds n'a lieu d'être qu'en présence de noeuds !
+ */
+ top_margin = MAX(top_margin, (*y > 0 && props->height > 0 ? NODE_VERTICAL_MARGIN : 0));
+
+ /* Position des noeuds */
+
+ props->y = *y + top_margin;
+ *y = props->y + props->height;
+
+ /* Espace inférieur pour les liens */
+
+ /**
+ * Fournit une marge minimum : si des liens autres que boucles partent de ce rang,
+ * il ne sont pas enregistrés à ce niveau, mais ont besoin d'espace quand même.
+ * On prend néanmoins garde aux rangs terminaux, potentiellement vides.
+ */
+ result = (props->height > 0 ? EDGE_SLOT_VERT_MARGIN : 0);
+
+ if (props->bottom_count > 0)
+ result += props->bottom_count * EDGE_VERTICAL_MIN_SEP;
+
+ return result;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : props = propriétés de rang à consulter. *
+* slot = numérod de la réservation. *
+* top = désignation de la zone à traiter. *
+* *
+* Description : Fournit la position verticale obtenue par réservation. *
+* *
+* Retour : Ordonnée à utiliser. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static gint get_y_for_rank_props_hspan_slot(const rank_props *props, hspan_slot_t slot, bool top)
+{
+ gint result; /* Ordonnée à retourner */
+
+ result = EDGE_SLOT_VERT_MARGIN + slot * EDGE_VERTICAL_MIN_SEP;
+
+ if (top)
+ result = props->y - result;
+ else
+ result += props->y + props->height;
+
+ return result;
+
+}
+
+
+
+/* ---------------------------------------------------------------------------------- */
+/* CLASSEMENT VERTICAL DES NOEUDS */
+/* ---------------------------------------------------------------------------------- */
+
+
/* Indique le type définit par la GLib pour le calcul de l'ordonnée des classements. */
G_DEFINE_TYPE(GGraphRanks, g_graph_ranks, G_TYPE_OBJECT);
@@ -176,19 +520,12 @@ static void g_graph_ranks_finalize(GGraphRanks *ranks)
GGraphRanks *g_graph_ranks_new(unsigned int count)
{
GGraphRanks *result; /* Structure à retourner */
- size_t i; /* Boucle de parcours */
result = g_object_new(G_TYPE_GRAPH_RANKS, NULL);
result->count = count;
result->props = (rank_props *)calloc(count, sizeof(rank_props));
- for (i = 0; i < count; i++)
- if (i == 0)
- result->props[i].top_margin = GRAPH_TOP_MARGIN;
- else
- result->props[i].top_margin = NODE_TOP_MARGIN;
-
return result;
}
@@ -219,6 +556,72 @@ void g_graph_ranks_set_min_height(GGraphRanks *ranks, unsigned int index, gint h
/******************************************************************************
* *
+* Paramètres : ranks = ensemble des rangs de classement à consulter. *
+* *
+* Description : Fournit la hauteur requise pour l'affichage des rangs. *
+* *
+* Retour : Hauteur nécessaire en pixel. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+gint g_graph_ranks_get_height(const GGraphRanks *ranks)
+{
+ return ranks->height;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : ranks = ensemble des rangs à mettre à jour. *
+* *
+* Description : Supprime toutes les réservations faites pour les liens. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void g_graph_ranks_reset_reservations(GGraphRanks *ranks)
+{
+ unsigned int i; /* Boucle de parcours */
+
+ for (i = 0; i < ranks->count; i++)
+ reset_spans_in_rank_props(&ranks->props[i]);
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : ranks = ensemble des rangs à mettre à jour. *
+* index = indice du rang visé. *
+* x1 = début de la portée à réserver. *
+* x2 = fin de la portée à réserver. *
+* top = désignation de la zone à traiter. *
+* *
+* Description : Réserve une portion de hauteur pour un lien. *
+* *
+* Retour : Indice de la hauteur adaptée et réservée. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+hspan_slot_t g_graph_ranks_reserve_span(GGraphRanks *ranks, unsigned int index, gint x1, gint x2, bool top)
+{
+ /*BUG_ON(index >= ranks->count) */
+
+ return reserve_span_in_rank_props(&ranks->props[index], x1, x2, top);
+
+}
+
+
+/******************************************************************************
+* *
* Paramètres : ranks = ensemble des rangs de classement à manipuler. *
* *
* Description : Calcule l'ordonnée finale de chaque rang du classement. *
@@ -231,16 +634,18 @@ void g_graph_ranks_set_min_height(GGraphRanks *ranks, unsigned int index, gint h
void g_graph_ranks_compute_y_line(GGraphRanks *ranks)
{
+ gint last_bottom; /* Espace minimal à transmettre*/
+ gint y; /* Ordonnée courante à proposer*/
size_t i; /* Boucle de parcours */
- for (i = 0; i < ranks->count; i++)
- {
- ranks->props[i].final_y = ranks->props[i].top_margin;
+ last_bottom = GRAPH_VERTICAL_MARGIN;
+ y = 0;
- if (i > 0)
- ranks->props[i].final_y += ranks->props[i - 1].final_y + ranks->props[i - 1].height;
- }
+ for (i = 0; i < ranks->count; i++)
+ last_bottom = compute_rank_props_y_pos(&ranks->props[i], &y, last_bottom);
+
+ ranks->height = y + last_bottom + GRAPH_VERTICAL_MARGIN;
}
@@ -262,6 +667,30 @@ gint g_graph_ranks_get_y_for_rank(const GGraphRanks *ranks, unsigned int index)
{
/*BUG_ON(index >= ranks->count) */
- return ranks->props[index].final_y;
+ return ranks->props[index].y;
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : ranks = ensemble des rangs de classement à consulter. *
+* index = indice du rang visé. *
+* slot = numérod de la réservation. *
+* top = désignation de la zone à traiter. *
+* *
+* Description : Fournit la position verticale obtenue par réservation. *
+* *
+* Retour : Ordonnée à utiliser. *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+gint g_graph_ranks_get_y_for_hspan_slot(const GGraphRanks *ranks, unsigned int index, hspan_slot_t slot, bool top)
+{
+ /*BUG_ON(index >= ranks->count) */
+
+ return get_y_for_rank_props_hspan_slot(&ranks->props[index], slot, top);
}
generated by cgit v0.11.2-87-g4458 at 2025-01-13 13:49:57 (GMT)