diff options
Diffstat (limited to 'src/gtkext/graph')
-rw-r--r-- | src/gtkext/graph/edge.c | 178 | ||||
-rw-r--r-- | src/gtkext/graph/edge.h | 9 | ||||
-rw-r--r-- | src/gtkext/graph/layout.c | 132 | ||||
-rw-r--r-- | src/gtkext/graph/layout.h | 6 | ||||
-rw-r--r-- | src/gtkext/graph/node-int.h | 11 | ||||
-rw-r--r-- | src/gtkext/graph/node.c | 70 | ||||
-rw-r--r-- | src/gtkext/graph/node.h | 19 | ||||
-rw-r--r-- | src/gtkext/graph/nodes/flow.c | 41 | ||||
-rw-r--r-- | src/gtkext/graph/nodes/virtual.c | 410 | ||||
-rw-r--r-- | src/gtkext/graph/nodes/virtual.h | 12 | ||||
-rw-r--r-- | src/gtkext/graph/params.h | 46 | ||||
-rw-r--r-- | src/gtkext/graph/ranks.c | 463 | ||||
-rw-r--r-- | src/gtkext/graph/ranks.h | 19 |
13 files changed, 1311 insertions, 105 deletions
diff --git a/src/gtkext/graph/edge.c b/src/gtkext/graph/edge.c index 0eb0230..4aedbde 100644 --- a/src/gtkext/graph/edge.c +++ b/src/gtkext/graph/edge.c @@ -27,6 +27,9 @@ #include <math.h> +#include "nodes/virtual.h" + + /* Lien graphique entre deux noeuds graphiques (instance) */ struct _GGraphEdge @@ -38,6 +41,12 @@ struct _GGraphEdge GFlowNode *dest_node; /* Bloc d'arrivée du lien */ node_slot_t *dest_slot; /* Numéro d'ancrage final */ + hspan_slot_t top_step; /* Niveau sup. de destination */ + GVirtualNode *container; /* Conteneur pour les tours */ + bool is_left; /* Tour par la gauche ? */ + vspan_slot_t vert_step; /* Position de contournement */ + hspan_slot_t bottom_step; /* Niveau inf. de source */ + EdgeColor color; /* Couleur du rendu */ GdkPoint *points; /* Points de la ligne dessinée */ size_t count; /* Quantité de ces points */ @@ -52,12 +61,6 @@ struct _GGraphEdgeClass }; -#define SLOT_VERT_SEP 20 - -#define ARROW_LENGHT 10 -#define ARROW_DEGREES 10 - - /* Initialise la classe des liens graphiques entre deux noeuds. */ static void g_graph_edge_class_init(GGraphEdgeClass *); @@ -117,6 +120,8 @@ static void g_graph_edge_class_init(GGraphEdgeClass *klass) static void g_graph_edge_init(GGraphEdge *edge) { + edge->top_step = UNINITIALIZED_HSPAN_SLOT; + edge->bottom_step = UNINITIALIZED_HSPAN_SLOT; } @@ -138,6 +143,9 @@ static void g_graph_edge_dispose(GGraphEdge *edge) g_object_unref(G_OBJECT(edge->src_node)); g_object_unref(G_OBJECT(edge->dest_node)); + if (edge->container != NULL) + g_object_unref(G_OBJECT(edge->container)); + G_OBJECT_CLASS(g_graph_edge_parent_class)->dispose(G_OBJECT(edge)); } @@ -157,6 +165,9 @@ static void g_graph_edge_dispose(GGraphEdge *edge) static void g_graph_edge_finalize(GGraphEdge *edge) { + if (edge->points != NULL) + free(edge->points); + G_OBJECT_CLASS(g_graph_edge_parent_class)->finalize(G_OBJECT(edge)); } @@ -201,7 +212,101 @@ GGraphEdge *g_graph_edge_new(GFlowNode *src_node, node_slot_t *src_slot, GFlowNo /****************************************************************************** * * -* Paramètres : edge = ligne de rendu à mettre à jour. * +* Paramètres : edge = ligne de rendu à mettre à jour. * +* nodes = noeud au sommet de la hiérarchie. * +* ranks = classement global dans lequel s'intégrer. * +* * +* Description : Prend les dispositions nécessaires à l'insertion du lien. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void g_graph_edge_reserve_vertical_space(GGraphEdge *edge, GGraphNode *nodes, GGraphRanks *ranks) +{ + GGraphNode *container; /* Conteneur du lien de boucle */ + unsigned int r1; /* Classement de départ */ + unsigned int r2; /* Classement d'arrivée */ + + switch (edge->color) + { + case EGC_BLUE: + + container = g_graph_node_find_container(nodes, G_GRAPH_NODE(edge->dest_node)); + g_object_ref(G_OBJECT(container)); + edge->container = G_VIRTUAL_NODE(container); + + edge->is_left = false; /* TODO */ + + r1 = g_graph_node_get_rank(G_GRAPH_NODE(edge->src_node)); + r2 = g_graph_node_get_rank(G_GRAPH_NODE(edge->dest_node)); + + edge->vert_step = g_virtual_node_reserve_span(edge->container, r1, r2, edge->is_left); + + break; + + default: + break; + + } + +} + + +/****************************************************************************** +* * +* Paramètres : edge = ligne de rendu à mettre à jour. * +* ranks = classement global dans lequel s'intégrer. * +* * +* Description : Prend les dispositions nécessaires à l'insertion du lien. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void g_graph_edge_reserve_horizontal_space(GGraphEdge *edge, GGraphRanks *ranks) +{ + GdkPoint x_src; /* Abscisse au niveau du départ*/ + GdkPoint x_dest; /* Abscisse au niveau d'arrivée*/ + gint x_step; /* Transition verticale */ + unsigned int rank; /* Indice de classement */ + + x_src = g_flow_node_get_point_from_slot(edge->src_node, false, edge->src_slot); + x_dest = g_flow_node_get_point_from_slot(edge->dest_node, true, edge->dest_slot); + + switch (edge->color) + { + case EGC_BLUE: + + x_step = g_virtual_node_get_x_for_vspan_slot(edge->container, + edge->vert_step, edge->is_left); + + rank = g_graph_node_get_rank(G_GRAPH_NODE(edge->src_node)); + edge->bottom_step = g_graph_ranks_reserve_span(ranks, rank, x_src.x, x_step, false); + + rank = g_graph_node_get_rank(G_GRAPH_NODE(edge->dest_node)); + edge->top_step = g_graph_ranks_reserve_span(ranks, rank, x_dest.x, x_step, true); + + break; + + default: + rank = g_graph_node_get_rank(G_GRAPH_NODE(edge->dest_node)); + edge->top_step = g_graph_ranks_reserve_span(ranks, rank, x_src.x, x_dest.x, true); + break; + + } + +} + + +/****************************************************************************** +* * +* Paramètres : edge = ligne de rendu à mettre à jour. * +* ranks = classement global dans lequel s'intégrer. * * * * Description : Etablit le tracé du lien graphique entre deux noeuds. * * * @@ -211,19 +316,16 @@ GGraphEdge *g_graph_edge_new(GFlowNode *src_node, node_slot_t *src_slot, GFlowNo * * ******************************************************************************/ -void g_graph_edge_compute(GGraphEdge *edge) +void g_graph_edge_compute(GGraphEdge *edge, GGraphRanks *ranks) { GdkPoint start; /* Point de départ */ GdkPoint end; /* Point d'arrivée */ + gint x_step; /* Transition verticale */ + unsigned int rank; /* Indice de classement */ start = g_flow_node_get_point_from_slot(edge->src_node, false, edge->src_slot); end = g_flow_node_get_point_from_slot(edge->dest_node, true, edge->dest_slot); - printf(" -- (%d ; %d) - (%d ; %d)\n", - start.x, start.y, - end.x, end.y); - - /* Point de départ */ edge->count = 2; @@ -235,16 +337,64 @@ void g_graph_edge_compute(GGraphEdge *edge) /* Points de jonction */ + switch (edge->color) + { + case EGC_BLUE: + + edge->count += 4; + edge->points = (GdkPoint *)realloc(edge->points, edge->count * sizeof(GdkPoint)); + + x_step = g_virtual_node_get_x_for_vspan_slot(edge->container, + edge->vert_step, edge->is_left); + + rank = g_graph_node_get_rank(G_GRAPH_NODE(edge->src_node)); + edge->points[edge->count - 4].x = start.x; + edge->points[edge->count - 4].y = g_graph_ranks_get_y_for_hspan_slot(ranks, rank, + edge->bottom_step, + false); + + edge->points[edge->count - 3].x = x_step; + edge->points[edge->count - 3].y = edge->points[edge->count - 4].y; + + rank = g_graph_node_get_rank(G_GRAPH_NODE(edge->dest_node)); + + edge->points[edge->count - 2].x = x_step; + edge->points[edge->count - 2].y = g_graph_ranks_get_y_for_hspan_slot(ranks, rank, + edge->top_step, + true); + edge->points[edge->count - 1].x = end.x; + edge->points[edge->count - 1].y = edge->points[edge->count - 2].y; + + break; + + default: + + edge->count += 2; + edge->points = (GdkPoint *)realloc(edge->points, edge->count * sizeof(GdkPoint)); + + rank = g_graph_node_get_rank(G_GRAPH_NODE(edge->dest_node)); + + edge->points[edge->count - 2].x = start.x; + edge->points[edge->count - 2].y = g_graph_ranks_get_y_for_hspan_slot(ranks, rank, + edge->top_step, + true); + + edge->points[edge->count - 1].x = end.x; + edge->points[edge->count - 1].y = edge->points[edge->count - 2].y; + + break; + + } /* Point d'arrivée */ edge->count += 2; edge->points = (GdkPoint *)realloc(edge->points, edge->count * sizeof(GdkPoint)); - edge->points[edge->count - 1] = end; edge->points[edge->count - 2] = end; edge->points[edge->count - 2].y -= SLOT_VERT_SEP; + edge->points[edge->count - 1] = end; } diff --git a/src/gtkext/graph/edge.h b/src/gtkext/graph/edge.h index 31e4a97..12dcfdc 100644 --- a/src/gtkext/graph/edge.h +++ b/src/gtkext/graph/edge.h @@ -28,6 +28,7 @@ #include <glib-object.h> +#include "ranks.h" #include "nodes/flow.h" @@ -66,8 +67,14 @@ GType g_graph_edge_get_type(void); /* Etablit un lien graphique entre deux noeuds graphiques. */ GGraphEdge *g_graph_edge_new(GFlowNode *, node_slot_t *, GFlowNode *, node_slot_t *, EdgeColor); +/* Prend les dispositions nécessaires à l'insertion du lien. */ +void g_graph_edge_reserve_vertical_space(GGraphEdge *, GGraphNode *, GGraphRanks *); + +/* Prend les dispositions nécessaires à l'insertion du lien. */ +void g_graph_edge_reserve_horizontal_space(GGraphEdge *, GGraphRanks *); + /* Etablit le tracé du lien graphique entre deux noeuds. */ -void g_graph_edge_compute(GGraphEdge *); +void g_graph_edge_compute(GGraphEdge *, GGraphRanks *); /* Dessine les liens graphiques enregistrés dans le moteur. */ void g_graph_edge_draw(const GGraphEdge *, GdkDrawable *, GdkGC *); diff --git a/src/gtkext/graph/layout.c b/src/gtkext/graph/layout.c index 377ad52..0a14854 100644 --- a/src/gtkext/graph/layout.c +++ b/src/gtkext/graph/layout.c @@ -569,51 +569,27 @@ static void g_graph_layout_finalize(GGraphLayout *layout) GGraphLayout *g_graph_layout_new(GInstrBlock *blocks, GtkBufferView **views, size_t count) { GGraphLayout *result; /* Structure à retourner */ - size_t i; /* Boucle de parcours */ result = g_object_new(G_TYPE_GRAPH_LAYOUT, NULL); result->nodes = convert_blocks_into_nodes(blocks, views, count); - /* Traitement des positions horizontales */ - - g_graph_node_set_position(result->nodes, (gint []) { 0 }, NULL); - g_virtual_node_organize_x_line(G_VIRTUAL_NODE(result->nodes)); - - /* Traitement des positions verticales */ - result->ranks = g_graph_ranks_new(count); - bool _register_cb(GFlowNode *node, GGraphRanks *ranks) - { - g_flow_node_register_rank(node, ranks); - return true; - } - - g_graph_node_visit_flow_nodes(result->nodes, (graph_node_visitor_cb)_register_cb, result->ranks); + /* Situations verticales grossières */ - g_graph_ranks_compute_y_line(result->ranks); - - bool _apply_cb(GFlowNode *node, GGraphRanks *ranks) + bool _register_cb(GFlowNode *node, GNodeVisitState state, GGraphLayout *layout) { - g_flow_node_apply_rank(node, ranks); + if (state == GVS_NODE) + g_flow_node_link(node, layout, layout->nodes); return true; } - g_graph_node_visit_flow_nodes(result->nodes, (graph_node_visitor_cb)_apply_cb, result->ranks); - - /* Mise en place des liens */ - - bool _do_links_cb(GFlowNode *node, GGraphLayout *layout) - { - g_flow_node_link(node, layout, layout->nodes); - return true; - } + g_graph_node_visit_nodes(result->nodes, (graph_node_visitor_cb)_register_cb, result); - g_graph_node_visit_flow_nodes(result->nodes, (graph_node_visitor_cb)_do_links_cb, result); + /* Actualisation... */ - for (i = 0; i < result->edges_count; i++) - g_graph_edge_compute(result->edges[i]); + g_graph_layout_refresh(result); return result; @@ -645,6 +621,68 @@ void g_graph_layout_add_edge(GGraphLayout *layout, GGraphEdge *edge) /****************************************************************************** * * +* Paramètres : layout = graphique à mettre à jour. * +* * +* Description : Met à jour les positions des différents noeuds. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void g_graph_layout_refresh(GGraphLayout *layout) +{ + size_t i; /* Boucle de parcours */ + + g_graph_ranks_reset_reservations(layout->ranks); + + bool _reset_cb(GGraphNode *node, GNodeVisitState state, void *unused) + { + g_graph_node_reset_position(node); + if (state == GVS_NODE) + g_flow_node_register_rank(G_FLOW_NODE(node), layout->ranks); + return true; + } + + g_graph_node_visit_nodes(layout->nodes, (graph_node_visitor_cb)_reset_cb, NULL); + + /* Traitement des positions horizontales */ + + for (i = 0; i < layout->edges_count; i++) + g_graph_edge_reserve_vertical_space(layout->edges[i], layout->nodes, layout->ranks); + + /* Traitement des positions horizontales */ + + g_graph_node_set_position(layout->nodes, (gint []) { 0 }, NULL); + g_virtual_node_organize_x_line(G_VIRTUAL_NODE(layout->nodes)); + + for (i = 0; i < layout->edges_count; i++) + g_graph_edge_reserve_horizontal_space(layout->edges[i], layout->ranks); + + /* Traitement des positions verticales */ + + g_graph_ranks_compute_y_line(layout->ranks); + + bool _apply_cb(GFlowNode *node, GNodeVisitState state, GGraphRanks *ranks) + { + if (state == GVS_NODE) + g_flow_node_apply_rank(node, ranks); + return true; + } + + g_graph_node_visit_nodes(layout->nodes, (graph_node_visitor_cb)_apply_cb, layout->ranks); + + /* Mise en place des liens */ + + for (i = 0; i < layout->edges_count; i++) + g_graph_edge_compute(layout->edges[i], layout->ranks); + +} + + +/****************************************************************************** +* * * Paramètres : layout = disposition en graphique prête. * * view = support de destination finale. * * * @@ -658,13 +696,39 @@ void g_graph_layout_add_edge(GGraphLayout *layout, GGraphEdge *edge) void g_graph_layout_place(GGraphLayout *layout, GtkGraphView *view) { - bool _place_cb(GFlowNode *node, GtkGraphView *view) + bool _place_cb(GFlowNode *node, GNodeVisitState state, GtkGraphView *view) { - g_flow_node_place(node, view); + if (state == GVS_NODE) + g_flow_node_place(node, view); return true; } - g_graph_node_visit_flow_nodes(layout->nodes, (graph_node_visitor_cb)_place_cb, view); + g_graph_node_visit_nodes(layout->nodes, (graph_node_visitor_cb)_place_cb, view); + +} + + +/****************************************************************************** +* * +* Paramètres : layout = graphique constitué à consulter. * +* requisition = dimensions souhaitées. [OUT] * +* * +* Description : Fournit la taille requise pour un plein rendu du graphique. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void g_graph_layout_size_request(const GGraphLayout *layout, GtkRequisition *requisition) +{ + GtkAllocation alloc; /* Largeur totale requise */ + + alloc = g_graph_node_get_allocation(layout->nodes); + requisition->width = alloc.width + 2 * GRAPH_HORIZONTAL_MARGIN; + + requisition->height = g_graph_ranks_get_height(layout->ranks); } diff --git a/src/gtkext/graph/layout.h b/src/gtkext/graph/layout.h index 6295cac..8aade99 100644 --- a/src/gtkext/graph/layout.h +++ b/src/gtkext/graph/layout.h @@ -69,9 +69,15 @@ GGraphLayout *g_graph_layout_new(GInstrBlock *, GtkBufferView **, size_t); /* Ajoute un lien entre deux noeuds au graphique. */ void g_graph_layout_add_edge(GGraphLayout *, GGraphEdge *); +/* Met à jour les positions des différents noeuds. */ +void g_graph_layout_refresh(GGraphLayout *); + /* Dispose chaque noeud sur la surface de destination donnée. */ void g_graph_layout_place(GGraphLayout *, GtkGraphView *); +/* Fournit la taille requise pour un plein rendu du graphique. */ +void g_graph_layout_size_request(const GGraphLayout *, GtkRequisition *); + /* Dessine les liens graphiques enregistrés dans le moteur. */ void g_graph_layout_draw(const GGraphLayout *, GdkDrawable *, GdkGC *); diff --git a/src/gtkext/graph/node-int.h b/src/gtkext/graph/node-int.h index 9ecb072..6d1086f 100644 --- a/src/gtkext/graph/node-int.h +++ b/src/gtkext/graph/node-int.h @@ -32,6 +32,12 @@ /* Fournit le rang du noeud dans le graphique. */ typedef unsigned int (* get_node_rank_fc) (const GGraphNode *); +/* Réinitialise la position d'un noeud d'encapsulation. */ +typedef void (* node_set_pos_fc) (GGraphNode *, gint *, gint *); + +/* Réinitialise la position d'un noeud d'encapsulation. */ +typedef void (* node_reset_pos_fc) (GGraphNode *); + /* Altère la position du noeud d'encapsulation. */ typedef void (* node_set_pos_fc) (GGraphNode *, gint *, gint *); @@ -44,6 +50,9 @@ typedef GtkAllocation (* node_get_alloc_fc) (const GGraphNode *); /* Parcourt tous les noeuds graphiques dans un ordre donné. */ typedef bool (* visit_flow_nodes_fc) (GGraphNode *, graph_node_visitor_cb, void *); +/* Recherche le noeud contenant un autre noeud. */ +typedef GGraphNode * (* find_container_fc) (GGraphNode *, GGraphNode *); + /* Intermédiaire entre le noeud dot et la bribe de code (instance) */ struct _GGraphNode @@ -51,10 +60,12 @@ struct _GGraphNode GObject parent; /* A laisser en premier */ get_node_rank_fc get_rank; /* Premier rang d'appartenance */ + node_reset_pos_fc reset_pos; /* Réinitialise l'emplacement */ node_set_pos_fc set_pos; /* Définit l'emplacement */ node_get_pos_fc get_pos; /* Fournit l'emplacement */ node_get_alloc_fc get_alloc; /* Fournit l'espace nécessaire */ visit_flow_nodes_fc visit; /* Visite des noeuds d'exécut° */ + find_container_fc contain; /* Retrouve un conteneur */ GtkWidget *view; /* Morceau de code représenté */ char name[NODE_NAME_LEN]; /* Adresse sous forme humaine */ diff --git a/src/gtkext/graph/node.c b/src/gtkext/graph/node.c index bb8403f..7b1d2b3 100644 --- a/src/gtkext/graph/node.c +++ b/src/gtkext/graph/node.c @@ -242,6 +242,25 @@ unsigned int g_graph_node_get_rank(const GGraphNode *node) /****************************************************************************** * * * Paramètres : node = noeud graphique à manipuler. * +* * +* Description : Réinitialise la position d'un noeud de graphique. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void g_graph_node_reset_position(GGraphNode *node) +{ + node->reset_pos(node); + +} + + +/****************************************************************************** +* * +* Paramètres : node = noeud graphique à manipuler. * * x = éventuelle abscisse à intégrer ou NULL. * * y = éventuelle ordonnée à intégrer ou NULL. * * * @@ -314,13 +333,39 @@ GtkAllocation g_graph_node_get_allocation(const GGraphNode *node) * * ******************************************************************************/ -bool g_graph_node_visit_flow_nodes(GGraphNode *node, graph_node_visitor_cb callback, void *data) +bool g_graph_node_visit_nodes(GGraphNode *node, graph_node_visitor_cb callback, void *data) { return node->visit(node, callback, data); } +/****************************************************************************** +* * +* Paramètres : nodes = noeud au sommet de la hiérarchie. * +* target = élément à retrouver dans l'ensemble de noeuds. * +* * +* Description : Recherche le noeud contenant un autre noeud. * +* * +* Retour : Noeud trouvé ou NULL si aucun. * +* * +* Remarques : - * +* * +******************************************************************************/ + +GGraphNode *g_graph_node_find_container(GGraphNode *nodes, GGraphNode *target) +{ + GGraphNode *result; /* Trouvaille à retourner */ + + result = NULL; + + if (nodes->contain != NULL) + result = nodes->contain(nodes, target); + + return result; + +} + @@ -625,14 +670,23 @@ GGraphNode *find_node_for_instruction(GGraphNode *nodes, GArchInstruction *instr params.instr = instr; params.found = NULL; - bool _find_node_cb(GFlowNode *node, struct visit_params *params) + bool _find_node_cb(GFlowNode *node, GNodeVisitState state, struct visit_params *params) { - if (g_flow_node_start_with(node, params->instr)) - params->found = G_GRAPH_NODE(node); - return (params->found == NULL); + bool result; + + if (state == GVS_NODE) + { + if (g_flow_node_start_with(node, params->instr)) + params->found = G_GRAPH_NODE(node); + result = (params->found == NULL); + } + else result = true; + + return result; + } - g_graph_node_visit_flow_nodes(nodes, (graph_node_visitor_cb)_find_node_cb, ¶ms); + g_graph_node_visit_nodes(nodes, (graph_node_visitor_cb)_find_node_cb, ¶ms); result = params.found; @@ -641,6 +695,10 @@ GGraphNode *find_node_for_instruction(GGraphNode *nodes, GArchInstruction *instr } + + + + /****************************************************************************** * * * Paramètres : nodes = liste de noeuds à parcourir. * diff --git a/src/gtkext/graph/node.h b/src/gtkext/graph/node.h index ffe0a0d..53232d9 100644 --- a/src/gtkext/graph/node.h +++ b/src/gtkext/graph/node.h @@ -59,8 +59,17 @@ typedef struct _GGraphNode GGraphNode; typedef struct _GGraphNodeClass GGraphNodeClass; +/* Détail sur une visite */ +typedef enum _GNodeVisitState +{ + GVS_ENTER, /* Entrée dans un groupe */ + GVS_NODE, /* Traitement d'une feuille */ + GVS_EXIT /* Sortie d'un groupe */ + +} GNodeVisitState; + /* Rappel à chaque noeud visité */ -typedef bool (* graph_node_visitor_cb) (GGraphNode *, void *); +typedef bool (* graph_node_visitor_cb) (GGraphNode *, GNodeVisitState, void *); /* Indique le type définit par la GLib pour le noeud. */ @@ -74,6 +83,9 @@ GGraphNode *g_graph_node_new(GtkWidget *); /* Fournit le rang du noeud dans le graphique. */ unsigned int g_graph_node_get_rank(const GGraphNode *); +/* Réinitialise la position d'un noeud de graphique. */ +void g_graph_node_reset_position(GGraphNode *); + /* Altère la position du noeud d'encapsulation. */ void g_graph_node_set_position(GGraphNode *, gint *, gint *); @@ -91,7 +103,10 @@ void g_graph_node_get_position(const GGraphNode *, gint *, gint *); GtkAllocation g_graph_node_get_allocation(const GGraphNode *); /* Parcourt tous les noeuds graphiques dans un ordre donné. */ -bool g_graph_node_visit_flow_nodes(GGraphNode *, graph_node_visitor_cb, void *); +bool g_graph_node_visit_nodes(GGraphNode *, graph_node_visitor_cb, void *); + +/* Recherche le noeud contenant un autre noeud. */ +GGraphNode *g_graph_node_find_container(GGraphNode *, GGraphNode *); diff --git a/src/gtkext/graph/nodes/flow.c b/src/gtkext/graph/nodes/flow.c index d4506ea..1848048 100644 --- a/src/gtkext/graph/nodes/flow.c +++ b/src/gtkext/graph/nodes/flow.c @@ -84,6 +84,9 @@ static void g_flow_node_finalize(GFlowNode *); /* Fournit le rang du noeud dans le graphique. */ static unsigned int g_flow_node_get_rank(const GFlowNode *); +/* Réinitialise la position d'un noeud d'encapsulation. */ +static void g_flow_node_reset_position(GFlowNode *); + /* Altère la position du noeud d'encapsulation. */ static void g_flow_node_set_position(GFlowNode *, gint *, gint *); @@ -159,6 +162,7 @@ static void g_flow_node_init(GFlowNode *node) base = G_GRAPH_NODE(node); base->get_rank = (get_node_rank_fc)g_flow_node_get_rank; + base->reset_pos = (node_reset_pos_fc)g_flow_node_reset_position; base->set_pos = (node_set_pos_fc)g_flow_node_set_position; base->get_pos = (node_get_pos_fc)g_flow_node_get_position; base->get_alloc = (node_get_alloc_fc)g_flow_node_get_allocation; @@ -286,6 +290,32 @@ static unsigned int g_flow_node_get_rank(const GFlowNode *node) /****************************************************************************** * * * Paramètres : node = noeud graphique à manipuler. * +* * +* Description : Réinitialise la position d'un noeud d'encapsulation. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_flow_node_reset_position(GFlowNode *node) +{ + GtkRequisition requisition; /* Taille à l'écran actuelle */ + + node->alloc.x = UNINITIALIZED_NODE_POS; + node->alloc.y = UNINITIALIZED_NODE_POS; + + gtk_widget_size_request(GTK_WIDGET(node->view), &requisition); + + node->alloc.width = requisition.width; + node->alloc.height = requisition.height; + +} + +/****************************************************************************** +* * +* Paramètres : node = noeud graphique à manipuler. * * x = éventuelle abscisse à intégrer ou NULL. * * y = éventuelle ordonnée à intégrer ou NULL. * * * @@ -366,7 +396,7 @@ static GtkAllocation g_flow_node_get_allocation(const GFlowNode *node) static bool g_flow_node_visit_flow_nodes(GFlowNode *node, graph_node_visitor_cb callback, void *data) { - return callback(G_GRAPH_NODE(node), data); + return callback(G_GRAPH_NODE(node), GVS_NODE, data); } @@ -427,7 +457,7 @@ void g_flow_node_register_rank(const GFlowNode *node, GGraphRanks *ranks) { unsigned int index; /* Indice du rang associé */ - index = g_flow_block_get_next_rank(node->block); + index = g_flow_node_get_rank(node); g_graph_ranks_set_min_height(ranks, index, node->alloc.height); @@ -451,7 +481,7 @@ void g_flow_node_apply_rank(GFlowNode *node, GGraphRanks *ranks) { unsigned int index; /* Indice du rang associé */ - index = g_flow_block_get_next_rank(node->block); + index = g_flow_node_get_rank(node); node->alloc.y = g_graph_ranks_get_y_for_rank(ranks, index); @@ -534,11 +564,6 @@ void g_flow_node_link(GFlowNode *node, GGraphLayout *layout, GGraphNode *nodes) void g_flow_node_place(const GFlowNode *node, GtkGraphView *view) { - printf("alloc %p :: (%d ; %d) - (%d ; %d)\n", - node->view, - node->alloc.x, node->alloc.y, - node->alloc.width, node->alloc.height); - gtk_graph_view_put(view, GTK_WIDGET(node->view), &node->alloc); } diff --git a/src/gtkext/graph/nodes/virtual.c b/src/gtkext/graph/nodes/virtual.c index 2781644..e13dfc8 100644 --- a/src/gtkext/graph/nodes/virtual.c +++ b/src/gtkext/graph/nodes/virtual.c @@ -33,6 +33,40 @@ +/* ----------------------- MANIPULATION DES PORTES VERTICALES ----------------------- */ + + +/* Etendue verticale d'un lien */ +typedef struct _reserved_vspan +{ + unsigned int r1; /* Départ d'une ligne */ + unsigned int r2; /* Arrivée de cette même ligne */ + +} reserved_vspan; + +/* Lignes de liens verticales au sein d'un même groupe */ +typedef struct _vert_links +{ + reserved_vspan *vspans; /* Lignes sans chevauchement */ + size_t count; /* Nombre de ces lignes */ + +} vert_links; + + +/* Initialise les futures portées d'un même niveau. */ +static void init_vertical_links(vert_links *); + +/* Regarde si des portées verticales se chevauchent ou non. */ +static bool is_intersection_with_vertical_spans(const vert_links *, const reserved_vspan *); + +/* Ajoute une réservation à un ensemble de portées verticales. */ +static void extend_vertical_links_spans(vert_links *, const reserved_vspan *); + + + +/* ---------------------- REPRESENTATIONS DES GROUPES LOGIQUES ---------------------- */ + + /* Encapsulation graphique d'un bloc virtuel (instance) */ struct _GVirtualNode { @@ -46,6 +80,11 @@ struct _GVirtualNode GGraphNode **children; /* Noeuds englobés */ size_t count; /* Quantité de ces noeuds */ + vert_links *left_padding; /* Espace à gauche pour liens */ + vspan_slot_t left_count; /* Nombre de largeurs réservées*/ + vert_links *right_padding; /* Espace à droite pour liens */ + vspan_slot_t right_count; /* Nombre de largeurs réservées*/ + }; /* Encapsulation graphique d'un bloc virtuel (classe) */ @@ -71,6 +110,9 @@ static void g_virtual_node_finalize(GVirtualNode *); /* Fournit le rang du noeud dans le graphique. */ static unsigned int g_virtual_node_get_rank(const GVirtualNode *); +/* Réinitialise la position d'un noeud d'encapsulation. */ +static void g_virtual_node_reset_position(GVirtualNode *); + /* Altère la position du noeud d'encapsulation. */ static void g_virtual_node_set_position(GVirtualNode *, gint *, gint *); @@ -83,11 +125,120 @@ static GtkAllocation g_virtual_node_get_allocation(const GVirtualNode *); /* Parcourt tous les blocs d'instructions dans un ordre donné. */ static bool g_virtual_node_visit_flow_nodes(GVirtualNode *, graph_node_visitor_cb, void *); +/* Recherche le noeud contenant un autre noeud. */ +static GGraphNode *g_virtual_node_find_container(GVirtualNode *, GGraphNode *); + /* Définit les abscisses relatives du contenu d'un noeud. */ static void g_virtual_node_setup_x_line(GVirtualNode *); +/* ---------------------------------------------------------------------------------- */ +/* MANIPULATION DES PORTES VERTICALES */ +/* ---------------------------------------------------------------------------------- */ + + +/****************************************************************************** +* * +* Paramètres : links = liste à initialiser. * +* * +* Description : Initialise les futures portées d'un même niveau. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void init_vertical_links(vert_links *links) +{ + links->vspans = NULL; + links->count = 0; + +} + + +/****************************************************************************** +* * +* Paramètres : links = liste de portées déjà en place. * +* vspan = nouvelle portée à insérer quelque part. * +* * +* Description : Regarde si des portées verticales se chevauchent ou non. * +* * +* Retour : true si les portées peuvent cohabiter, false sinon. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static bool is_intersection_with_vertical_spans(const vert_links *links, const reserved_vspan *vspan) +{ + bool result; /* Bilan d'analyse à retourner */ + size_t i; /* Boucle de parcours */ + + result = false; + + for (i = 0; i < links->count && !result; i++) + { + if (vspan->r1 < links->vspans[i].r1) + result = vspan->r2 >= links->vspans[i].r1; + + else if (vspan->r1 > links->vspans[i].r2) + result = vspan->r2 <= links->vspans[i].r2; + + else + { + result = links->vspans[i].r1 < vspan->r1 && vspan->r1 < links->vspans[i].r2; + result |= links->vspans[i].r1 < vspan->r2 && vspan->r2 < links->vspans[i].r2; + } + + } + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : spans = liste de portées déjà en place. * +* vspan = nouvelle portée à insérer quelque part. * +* * +* Description : Ajoute une réservation à un ensemble de portées verticales. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void extend_vertical_links_spans(vert_links *links, const reserved_vspan *new) +{ + links->vspans = (reserved_vspan *)realloc(links->vspans, + ++links->count * sizeof(reserved_vspan)); + + if (new->r1 <= new->r2) + links->vspans[links->count - 1] = *new; + else + { + links->vspans[links->count - 1].r1 = new->r2; + links->vspans[links->count - 1].r2 = new->r1; + } + +} + + + + + + + + +/* ---------------------------------------------------------------------------------- */ +/* REPRESENTATIONS DES GROUPES LOGIQUES */ +/* ---------------------------------------------------------------------------------- */ + + /* Indique le type définit par la GLib pour l'encapsulation d'un bloc virtuel. */ G_DEFINE_TYPE(GVirtualNode, g_virtual_node, G_TYPE_GRAPH_NODE); @@ -135,10 +286,12 @@ static void g_virtual_node_init(GVirtualNode *node) base = G_GRAPH_NODE(node); base->get_rank = (get_node_rank_fc)g_virtual_node_get_rank; + base->reset_pos = (node_reset_pos_fc)g_virtual_node_reset_position; base->set_pos = (node_set_pos_fc)g_virtual_node_set_position; base->get_pos = (node_get_pos_fc)g_virtual_node_get_position; base->get_alloc = (node_get_alloc_fc)g_virtual_node_get_allocation; base->visit = (visit_flow_nodes_fc)g_virtual_node_visit_flow_nodes; + base->contain = (find_container_fc)g_virtual_node_find_container; node->x = UNINITIALIZED_NODE_POS; node->y = UNINITIALIZED_NODE_POS; @@ -246,6 +399,26 @@ static unsigned int g_virtual_node_get_rank(const GVirtualNode *node) /****************************************************************************** * * * Paramètres : node = noeud graphique à manipuler. * +* * +* Description : Réinitialise la position d'un noeud d'encapsulation. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_virtual_node_reset_position(GVirtualNode *node) +{ + node->x = UNINITIALIZED_NODE_POS; + node->y = UNINITIALIZED_NODE_POS; + +} + + +/****************************************************************************** +* * +* Paramètres : node = noeud graphique à manipuler. * * x = éventuelle abscisse à intégrer ou NULL. * * y = éventuelle ordonnée à intégrer ou NULL. * * * @@ -302,6 +475,12 @@ static void g_virtual_node_get_position(const GVirtualNode *node, gint *x, gint static GtkAllocation g_virtual_node_get_allocation(const GVirtualNode *node) { GtkAllocation result; /* Valeurs à retourner */ + gint margins; /* Bordures gauche et droite */ + unsigned int last_rank; /* Détection de saut de rangs */ + size_t horiz_count; /* Quantité à l'horizontale */ + size_t vert_count; /* Quantité à la verticale */ + gint rank_width; /* Largeur d'un rang donné */ + gint rank_height; /* Hauteur d'un rang donné */ size_t i; /* Boucle de parcours */ GtkAllocation alloc; /* Allocation d'un sous-noeud */ @@ -309,23 +488,72 @@ static GtkAllocation g_virtual_node_get_allocation(const GVirtualNode *node) result.y = node->y; result.width = 0; + margins = 0; + if (node->left_count > 0) + { + margins += EDGE_SLOT_HORIZ_MARGIN; + margins += (node->left_count - 1) * EDGE_HORIZONTAL_MIN_SEP; + } + if (node->right_count > 0) + { + margins += EDGE_SLOT_HORIZ_MARGIN; + margins += (node->right_count - 1) * EDGE_HORIZONTAL_MIN_SEP; + } result.height = 0; + last_rank = -1; + + horiz_count = 0; + vert_count = 0; + + rank_width = 0; + rank_height = 0; + for (i = 0; i < node->count; i++) { alloc = g_graph_node_get_allocation(node->children[i]); - result.width += alloc.width; - result.height += alloc.height; + if (last_rank != g_graph_node_get_rank(node->children[i])) + { + last_rank = g_graph_node_get_rank(node->children[i]); + + result.width = MAX(result.width, rank_width); - } + /* + if (horiz_count > 0) + result.width = MAX(result.width, rank_width + (horiz_count - 1) * NODE_LEFT_MARGIN); + */ + + result.height += rank_height; + + rank_width = 0; + rank_height = 0; + + horiz_count = 0; + vert_count++; + + } + + //rank_width += alloc.width; + if (rank_width > 0) rank_width += NODE_LEFT_MARGIN; + rank_width += alloc.width; + rank_height = MAX(rank_height, alloc.height); + + horiz_count++; - if (node->count > 1) - { - result.width += (node->count - 1) * NODE_TOP_MARGIN; - result.height += (node->count - 1) * NODE_TOP_MARGIN; } + result.width = MAX(result.width, rank_width); + /* + if (horiz_count > 0) + result.width = MAX(result.width, rank_width + (horiz_count - 1) * NODE_LEFT_MARGIN); + */ + + result.width += margins; + + if (vert_count > 1) + result.height += (vert_count - 1) * NODE_TOP_MARGIN; + return result; } @@ -350,10 +578,46 @@ static bool g_virtual_node_visit_flow_nodes(GVirtualNode *node, graph_node_visit bool result; /* Bilan à retourner */ size_t i; /* Boucle de parcours */ - result = true; + result = callback(G_GRAPH_NODE(node), GVS_ENTER, data); for (i = 0; i < node->count && result; i++) - result = g_graph_node_visit_flow_nodes(node->children[i], callback, data); + result = g_graph_node_visit_nodes(node->children[i], callback, data); + + if (result) + result = callback(G_GRAPH_NODE(node), GVS_EXIT, data); + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : nodes = noeud à consulter. * +* target = élément à retrouver dans l'ensemble de noeuds. * +* * +* Description : Recherche le noeud contenant un autre noeud. * +* * +* Retour : Noeud trouvé ou NULL si aucun. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static GGraphNode *g_virtual_node_find_container(GVirtualNode *node, GGraphNode *target) +{ + GGraphNode *result; /* Trouvaille à retourner */ + size_t i; /* Boucle de parcours */ + + result = NULL; + + for (i = 0; i < node->count && result == NULL; i++) + { + if (node->children[i] == target) + result = G_GRAPH_NODE(node); + else + result = g_graph_node_find_container(node->children[i], target); + } return result; @@ -430,6 +694,59 @@ GGraphNode *g_virtual_node_get_child(const GVirtualNode *node, size_t index) /****************************************************************************** * * +* Paramètres : node = groupe de noeuds à mettre à jour. * +* r1 = début de la portée à réserver. * +* r2 = fin de la portée à réserver. * +* left = désignation de la zone à traiter. * +* * +* Description : Réserve une portion de largeur pour un lien. * +* * +* Retour : Indice de la largeur adaptée et réservée. * +* * +* Remarques : - * +* * +******************************************************************************/ + +vspan_slot_t g_virtual_node_reserve_span(GVirtualNode *node, unsigned int r1, unsigned int r2, bool left) +{ + vspan_slot_t result; /* Identifiant à retourner */ + reserved_vspan vspan; /* Portée à constituer */ + vert_links **list; /* Liste à parcourir */ + vspan_slot_t *count; /* Taille de cette liste */ + + vspan.r1 = r1; + vspan.r2 = r2; + + if (left) + { + list = &node->left_padding; + count = &node->left_count; + } + else + { + list = &node->right_padding; + count = &node->right_count; + } + + for (result = 0; result < *count; result++) + if (!is_intersection_with_vertical_spans(&(*list)[result], &vspan)) + break; + + if (result == *count) + { + *list = (vert_links *)realloc(*list, ++(*count) * sizeof(vert_links)); + init_vertical_links(&(*list)[result]); + } + + extend_vertical_links_spans(&(*list)[result], &vspan); + + return result; + +} + + +/****************************************************************************** +* * * Paramètres : node = noeud d'encapsulation à traiter. * * * * Description : Organise le contenu du noeud selon l'axe des abscisses. * @@ -456,9 +773,8 @@ void g_virtual_node_organize_x_line(GVirtualNode *node) min = MIN(min, x); } - printf("min =%d\n", min); - - min = -min + GRAPH_LEFT_MARGIN; + node->x += GRAPH_HORIZONTAL_MARGIN; + min = -min + GRAPH_HORIZONTAL_MARGIN; g_virtual_node_offset_x_line(node, min); @@ -494,7 +810,7 @@ static void g_virtual_node_setup_x_line(GVirtualNode *node) if (rank_0 == rank_1) { - g_graph_node_set_position(node->children[0], (gint []) { -(alloc.width / 2) }, NULL); + g_graph_node_set_position(node->children[0], (gint []) { 0/*-(alloc.width / 2)*/ }, NULL); for (i = 1; i < node->count; i++) { @@ -530,9 +846,6 @@ static void g_virtual_node_setup_x_line(GVirtualNode *node) if (!g_graph_node_has_x_position(child)) { alloc = g_graph_node_get_allocation(child); - - printf("alloc ? %d\n", alloc.width); - g_graph_node_set_position(child, (gint []) { -(alloc.width / 2) }, NULL); } @@ -571,23 +884,80 @@ static void g_virtual_node_setup_x_line(GVirtualNode *node) void g_virtual_node_offset_x_line(GVirtualNode *node, gint xoffset) { + gint padding; /* Décallage supplémentaire */ size_t i; /* Boucle de parcours */ gint x; /* Position d'un sous-noeud */ GGraphNode *child; /* Raccourci confortable */ + /* Espace pour les liens remontants */ + + if (node->left_count > 0) + padding = EDGE_SLOT_HORIZ_MARGIN + EDGE_HORIZONTAL_MIN_SEP * (node->left_count - 1); + else + padding = 0; + + /* Traitement de sous-noeuds */ + for (i = 0; i < node->count; i++) { child = node->children[i]; g_graph_node_get_position(child, &x, NULL); - printf("[%p] old=%d... ", child, x); - - x += xoffset; + x += xoffset + padding; g_graph_node_set_position(child, &x, NULL); - printf("next=%d...\n", x); + } + +} + + +/****************************************************************************** +* * +* Paramètres : node = conteneur de noeuds à consulter. * +* slot = numérod de la réservation. * +* left = désignation de la zone à traiter. * +* * +* Description : Fournit la position horizontale obtenue par réservation. * +* * +* Retour : Abscisse à utiliser. * +* * +* Remarques : - * +* * +******************************************************************************/ + +gint g_virtual_node_get_x_for_vspan_slot(const GVirtualNode *node, vspan_slot_t slot, bool left) +{ + gint result; /* Position à retourner */ + GtkAllocation alloc; /* Taille totale requise */ + + alloc = g_virtual_node_get_allocation(node); + + if (left) + { + /*BUG_ON(slot >= node->left_count) */ + + result = (node->left_count - 1) * EDGE_HORIZONTAL_MIN_SEP/* + EDGE_SLOT_HORIZ_MARGIN*/; + result -= (slot * EDGE_HORIZONTAL_MIN_SEP/* + EDGE_SLOT_HORIZ_MARGIN*/); + + result += alloc.x; } + else + { + /*BUG_ON(slot >= node->right_count) */ + + result = /*EDGE_SLOT_HORIZ_MARGIN + */slot * EDGE_HORIZONTAL_MIN_SEP; + + result += alloc.x + alloc.width/* - EDGE_SLOT_HORIZ_MARGIN*/; + if (node->right_count > 0) + result -= (node->right_count - 1) * EDGE_HORIZONTAL_MIN_SEP; + + /* On pense à la largeur du trait... */ + result -= 2; + + } + + return result; } diff --git a/src/gtkext/graph/nodes/virtual.h b/src/gtkext/graph/nodes/virtual.h index 440c675..20106b6 100644 --- a/src/gtkext/graph/nodes/virtual.h +++ b/src/gtkext/graph/nodes/virtual.h @@ -29,6 +29,12 @@ #include "../../../analysis/blocks/virtual.h" +/* Indice d'une hauteur au sein des rangs */ +typedef size_t vspan_slot_t; + +/* Indice non initilisé */ +#define UNINITIALIZED_VSPAN_SLOT (~((vspan_slot_t)0)) + #define G_TYPE_VIRTUAL_NODE g_virtual_node_get_type() #define G_VIRTUAL_NODE(obj) (G_TYPE_CHECK_INSTANCE_CAST((obj), g_virtual_node_get_type(), GVirtualNode)) @@ -59,12 +65,18 @@ size_t g_virtual_node_count_children(const GVirtualNode *); /* Renvoie un des noeuds contenus dans le groupe courant. */ GGraphNode *g_virtual_node_get_child(const GVirtualNode *, size_t); +/* Réserve une portion de largeur pour un lien. */ +vspan_slot_t g_virtual_node_reserve_span(GVirtualNode *, unsigned int, unsigned int, bool); + /* Organise le contenu du noeud selon l'axe des abscisses. */ void g_virtual_node_organize_x_line(GVirtualNode *); /* Procède à un décallage du contenu sur l'axe des abscisses. */ void g_virtual_node_offset_x_line(GVirtualNode *, gint); +/* Fournit la position horizontale obtenue par réservation. */ +gint g_virtual_node_get_x_for_vspan_slot(const GVirtualNode *, vspan_slot_t, bool); + #endif /* _GTKEXT_GRAPH_NODES_VIRTUAL_H */ diff --git a/src/gtkext/graph/params.h b/src/gtkext/graph/params.h index 63960b8..d4fea24 100644 --- a/src/gtkext/graph/params.h +++ b/src/gtkext/graph/params.h @@ -31,12 +31,52 @@ #define UNINITIALIZED_NODE_POS G_MININT +/** + * Paramètres à l'échelle du graphique. + */ + +/* Bordures supérieure et inférieure des graphiques */ +#define GRAPH_VERTICAL_MARGIN 15 + +/* Bordures gauche et droite des graphiques */ +#define GRAPH_HORIZONTAL_MARGIN 15 + + +/** + * Paramètres à l'échelle du noeud. + */ + + + -#define GRAPH_LEFT_MARGIN 15 -#define GRAPH_TOP_MARGIN 15 #define NODE_LEFT_MARGIN 25 -#define NODE_TOP_MARGIN 55 +#define NODE_TOP_MARGIN 55 /* TODO : supprimer */ + + + +/* Séparation verticale minimale entre deux noeuds */ +#define NODE_VERTICAL_MARGIN 35 + + + + +/* Séparations minimales entre deux liens */ +#define EDGE_HORIZONTAL_MIN_SEP 10 +#define EDGE_VERTICAL_MIN_SEP 10 + +/* Séparations minimales entre un lien et un noeud */ +#define EDGE_SLOT_HORIZ_MARGIN 20 +#define EDGE_SLOT_VERT_MARGIN 20 + + + + + +#define SLOT_VERT_SEP EDGE_SLOT_VERT_MARGIN /* TODO : remplacer */ + +#define ARROW_LENGHT 10 +#define ARROW_DEGREES 10 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); } diff --git a/src/gtkext/graph/ranks.h b/src/gtkext/graph/ranks.h index 627269f..618db79 100644 --- a/src/gtkext/graph/ranks.h +++ b/src/gtkext/graph/ranks.h @@ -26,8 +26,15 @@ #include <glib-object.h> +#include <stdbool.h> +/* Indice d'une hauteur au sein des rangs */ +typedef size_t hspan_slot_t; + +/* Indice non initilisé */ +#define UNINITIALIZED_HSPAN_SLOT (~((hspan_slot_t)0)) + #define G_TYPE_GRAPH_RANKS g_graph_ranks_get_type() #define G_GRAPH_RANKS(obj) (G_TYPE_CHECK_INSTANCE_CAST((obj), g_graph_ranks_get_type(), GGraphRanks)) @@ -52,12 +59,24 @@ GGraphRanks *g_graph_ranks_new(unsigned int); /* Note une hauteur minimale requise pour un rang du classement. */ void g_graph_ranks_set_min_height(GGraphRanks *, unsigned int, gint); +/* Fournit la hauteur requise pour l'affichage des rangs. */ +gint g_graph_ranks_get_height(const GGraphRanks *); + +/* Supprime toutes les réservations faites pour les liens. */ +void g_graph_ranks_reset_reservations(GGraphRanks *); + +/* Réserve une portion de hauteur pour un lien. */ +hspan_slot_t g_graph_ranks_reserve_span(GGraphRanks *, unsigned int, gint, gint, bool); + /* Calcule l'ordonnée finale de chaque rang du classement. */ void g_graph_ranks_compute_y_line(GGraphRanks *); /* Fournit la position verticale correspondant à un rang donné. */ gint g_graph_ranks_get_y_for_rank(const GGraphRanks *, unsigned int); +/* Fournit la position verticale obtenue par réservation. */ +gint g_graph_ranks_get_y_for_hspan_slot(const GGraphRanks *, unsigned int, hspan_slot_t, bool); + #endif /* _GTKEXT_GRAPH_RANKS_H */ |