1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
|
#ifdef HAVE_CONFIG_H
#include "gvconfig.h"
#endif
#include <assert.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#ifdef HAVE_VALUES_H
#include <values.h>
#else
#include <limits.h>
#ifndef MAXINT
#define MAXINT INT_MAX
#endif
#include <float.h>
#ifndef MAXDOUBLE
#define MAXDOUBLE DBL_MAX
#endif
#ifndef MAXFLOAT
#define MAXFLOAT FLT_MAX
#endif
#endif
#include <engine.h>
#ifndef FALSE
#define FALSE (0)
#endif
#ifndef TRUE
#define TRUE (!FALSE)
#endif
#ifndef NOT
#define NOT(x) (!(x))
#endif
#ifndef NIL
#define NIL(type) ((type)0)
#endif
#define BASE(obj) (&((obj)->base))
#define HORZ TRUE
#define VERT FALSE
#define K_DIST (1.0)
#define K_BEND (5.0)
#define K_CROSSING (10.0)
#define K_NARROW_PENALTY (200.0)
#define NSIDES 4 /* of a rectangle */
#define opposite(side) (((side) + 2) % NSIDES)
#define MIN(a,b) ((a)<(b)?(a):(b))
#define MAX(a,b) ((a)>(b)?(a):(b))
#define NONDECREASING(a,b,c) (((a)<=(b)) && ((b)<=(c)))
#define INCREASING(a,b,c) (((a)<(b)) && ((b)<(c)))
/* diagram segment types */
typedef enum segkind_e { s_plain, s_edge, s_node, s_forbidden } Segkind_t;
typedef enum dir_e { west = 0, north = 1, east = 2, south = 3, nosuchdir = 5 } Dir_t;
/* the ways an edge can pass through a rectangular tile */
typedef enum trans_e { t_none, t_straight, t_bend, t_jog, t_uturn } Trans_t;
typedef struct Label_s Label_t;
typedef struct Seg_s Seg_t;
typedef struct Seglist_s Seglist_t;
typedef struct Tile_s Tile_t;
typedef struct Tileset_s Tileset_t;
#define XCOORD 0
#define YCOORD 1
#define x(point) (point.c[XCOORD])
#define y(point) (point.c[YCOORD])
#define pt_eq(p,q) ((x(p)==x(q))&&(y(p)==y(q)))
typedef struct Set_s { /* prototype of all sets */
void **list;
int size,extent;
} Set_t;
typedef struct Pt_s { double c[2]; } Pt_t;
struct Label_s { /* shortest path label */
Tile_t *tile;
double cost; /* cost to get here */
Pt_t win[2]; /* boundaries of the segment window */
Pt_t loc; /* tentative route point to estimate distance */
Trans_t trans;
Seg_t *prev_seg;
ilbool finalized;
ilbool is_terminal;
} ;
struct Seg_s {
Pt_t p[2]; /* endpoints */
Tile_t *b[2]; /* adjacent tiles */
Label_t sp; /* shortest path label */
Segkind_t kind;
short refcnt;
} ;
struct Seglist_s {
Seg_t **list;
int size,extent;
} ;
struct Tile_s {
Pt_t LL,UR; /* tile's corners */
Seglist_t *segs[NSIDES]; /* boundary segments */
int id; /* for debugging */
} ;
struct Tileset_s {
Tile_t **list;
int size,extent;
} ;
typedef struct ERview_s {
engview_t base; /* must be first */
Tileset_t *config; /* primtive tiles of the layout */
Tileset_t *nodes; /* logical tiles only of nodes */
} ERview_t ;
typedef struct ERnode_s {
engnode_t base; /* must be first */
Tile_t *tile; /* in view->config set */
} ERnode_t ;
typedef struct ERedge_s {
engedge_t base;
ilshape_t *route; /* how it is drawn */
} ERedge_t ;
ERnode_t *er_nd(Agnode_t*);
ERedge_t *er_ed(Agedge_t*);
Set_t *ERmake_set(ERview_t *);
void ERfree_set(ERview_t *, Set_t *);
void ERset_append(ERview_t *, Set_t *, void *);
void ERset_delete(Set_t *, void *);
Tileset_t *ERmake_tileset(ERview_t *);
void ERfree_tileset(ERview_t *, Tileset_t *);
void ERtileset_append(ERview_t *, Tileset_t *, Tile_t *);
void ERtileset_delete(Tileset_t *, Tile_t *);
Seglist_t *ERmake_seglist(ERview_t *);
void ERfree_seglist(ERview_t *,Seglist_t *);
void ERseglist_append(ERview_t *, Seglist_t *, Seg_t *);
void ERseglist_delete(Seglist_t *, Seg_t *);
Pt_t ERpt(ilcoord_t p);
Pt_t ERmkpoint(double, double);
Pt_t ERaddpoint(Pt_t, Pt_t);
Pt_t ERavgpt(Pt_t, Pt_t);
Pt_t ERcombine(Pt_t, Pt_t, ilbool);
ilbool ERhorizontal(Seg_t *);
Tile_t *ERnodetile(ERview_t *, Pt_t, Pt_t);
Tile_t *ERtile(ERview_t *, Pt_t, Pt_t);
void ERfree_tile(ERview_t *, Tile_t *);
Pt_t ERtileLL(Tile_t *);
Pt_t ERtileLR(Tile_t *);
Pt_t ERtileUR(Tile_t *);
Pt_t ERtileUL(Tile_t *);
void ERcorners(Tile_t *, Pt_t *);
void ERside(Tile_t *, Dir_t, Pt_t *);
Dir_t ERtile_side_of(Tile_t *, Pt_t, Pt_t);
ilbool ERpt_in_tile(Pt_t, Tile_t *);
ilbool ERpt_strictly_in_tile(Pt_t, Tile_t *);
ilbool ERtiles_nontrivially_intersect(Tile_t *, Tile_t *);
ilbool ERtile_covers_tile(Tile_t *, Tile_t *);
Seg_t *ERmkseg(ERview_t *, Pt_t, Pt_t, Tile_t *, Tile_t *, Segkind_t);
void ERfree_seg(ERview_t *, Seg_t *);
void ERinstall_new_seg(ERview_t *, Pt_t, Pt_t, Segkind_t, Tile_t *, Dir_t, Tile_t *);
void ERmark_segs(ERview_t *D, Pt_t p, Pt_t q, Segkind_t kind);
void ERmark_container_segs(ERview_t *d, Tile_t *b, Segkind_t kind);
Tile_t *ERneighbor(Tile_t *, Pt_t);
Tile_t *ERlocate(ERview_t *, Pt_t);
void ERlocate_endpoint(ERview_t *D, Tile_t *user_node, Pt_t pt, Tile_t **pb, Seg_t **pseg);
void ERsplit_config(ERview_t *D, Pt_t p, Pt_t q);
void ERcut_tile(ERview_t *D, Tile_t *b, ilbool horizontal, Pt_t p);
void ERuser_route(ERview_t *D, ilshape_t *req);
ilshape_t *ERauto_route(ERview_t *D, Tile_t *arg_start, Pt_t sp, Tile_t *arg_end, Pt_t ep);
void ERnode_remove(ERview_t *D, Tile_t *);
void ERroute_remove(ERview_t *D, ilshape_t *route);
void ERprint(FILE*, ERview_t *D, ilbool alltiles);
Agraph_t *ergraph(ERview_t *D);
|
