← Back to branch summary

~ubuntu-branches/ubuntu/lucid/graphviz/lucid-security

« back to all changes in this revision

Viewing changes to grid/erbase.c

  • Committer: Bazaar Package Importer
  • Author(s): Stephen M Moraco
  • Date: 2002-02-05 18:52:12 UTC
  • Revision ID: james.westby@ubuntu.com-20020205185212-8i04c70te00rc40y
Tags: upstream-1.7.16
Import upstream version 1.7.16

Show diffs side-by-side

added added

removed removed

Lines of Context:
grid/erbase.c
 
1
#include <grid.h>
 
2
 
 
3
#ifdef DMALLOC
 
4
#include "dmalloc.h"
 
5
#endif
 
6
 
 
7
ERnode_t *er_nd(Agnode_t *n) {return (ERnode_t*)(AGDATA(n));}
 
8
ERedge_t *er_ed(Agedge_t *e) {return (ERedge_t*)(AGDATA(e));}
 
9
Agraph_t *ergraph(ERview_t *D) {return BASE(D)->model.main;}
 
10
 
 
11
        /* generic sets */
 
12
Set_t *ERmake_set(ERview_t *D)
 
13
{
 
14
        Set_t   *rv;
 
15
        rv = agalloc(ergraph(D),sizeof(Set_t));
 
16
        rv->extent = 20;
 
17
        rv->list = agalloc(ergraph(D),rv->extent * sizeof(void*));
 
18
        return rv;
 
19
}
 
20
 
 
21
void ERfree_set(ERview_t *D, Set_t *set)
 
22
{
 
23
        if (set) {agfree(ergraph(D),set->list); agfree(ergraph(D),set);}
 
24
}
 
25
 
 
26
void ERset_append(ERview_t *D, Set_t *set, void *obj)
 
27
{
 
28
        assert(set->extent > 0);
 
29
        if (set->size >= set->extent - 1) {
 
30
                set->list = agrealloc(ergraph(D),set->list,
 
31
                        set->extent*sizeof(void*),set->extent * 2 * sizeof(void*));
 
32
                set->extent = set->extent * 2;
 
33
        }
 
34
        set->list[set->size++] = obj;
 
35
}
 
36
 
 
37
void ERset_delete(Set_t *set, void *obj)
 
38
{
 
39
        int             i;
 
40
        void    *obj0;
 
41
 
 
42
        for (i = 0; (obj0 = set->list[i]); i++) {
 
43
                if (obj0 == obj) {
 
44
                        if (i < set->size - 1)
 
45
                                set->list[i] = set->list[set->size - 1];
 
46
                        set->size--;
 
47
                        set->list[set->size] = NIL(void*);
 
48
                        break;
 
49
                }
 
50
        }
 
51
        assert(obj == obj0);
 
52
}
 
53
 
 
54
        /* tile sets */
 
55
Tileset_t *ERmake_tileset(ERview_t *D)
 
56
        { return (Tileset_t*)  ERmake_set(D); }
 
57
void ERfree_tileset(ERview_t *D, Tileset_t *set)
 
58
        { ERfree_set(D,(Set_t*)set);}
 
59
void ERtileset_append(ERview_t *D, Tileset_t *set, Tile_t *b)
 
60
        { ERset_append(D,(Set_t*)set,b); }
 
61
void ERtileset_delete(Tileset_t *set, Tile_t *b)
 
62
        { ERset_delete((Set_t*)set,b); }
 
63
 
 
64
        /* segment sets */
 
65
Seglist_t *ERmake_seglist(ERview_t *D)
 
66
        {return (Seglist_t*) ERmake_set(D); }
 
67
void ERfree_seglist(ERview_t *D, Seglist_t *set) {ERfree_set(D,(Set_t*)set);}
 
68
void ERseglist_append(ERview_t *D, Seglist_t *set, Seg_t *s)
 
69
        { ERset_append(D,(Set_t*)set,s); }
 
70
void ERseglist_delete(Seglist_t *set, Seg_t *seg)
 
71
        { ERset_delete((Set_t*)set,seg); }
 
72
 
 
73
        /* points */
 
74
Pt_t ERmkpoint(double x, double y) {Pt_t rv; rv.c[0] = x; rv.c[1] = y; return rv;}
 
75
Pt_t ERaddpoint(Pt_t p0, Pt_t p1) {return ERmkpoint( x(p0) + x(p1),  y(p0) + y(p1)); }
 
76
Pt_t ERavgpt(Pt_t p0, Pt_t p1) {return ERmkpoint((x(p0)+x(p1))/2.,(y(p0)+y(p1))/2.);}
 
77
 
 
78
Pt_t ERcombine(Pt_t p, Pt_t q, ilbool px)
 
79
{
 
80
        double  x,y;
 
81
        if (px) {x = x(p); y = y(q);}
 
82
        else  {x = x(q); y = y(p);}
 
83
        return ERmkpoint(x,y);
 
84
}
 
85
 
 
86
 
 
87
        /* points of compass & orientation */
 
88
 
 
89
#ifdef NOTDEF
 
90
char *name_of_dir(Dir_t arg)
 
91
{
 
92
        static char *n[] = {"west","north","east","south","nosuchdir"};
 
93
        return n[arg];
 
94
}
 
95
#endif
 
96
 
 
97
        /* returns true if horizontal, false if vertical */
 
98
ilbool ERhorizontal(Seg_t *seg)
 
99
{
 
100
        if (y(seg->p[0]) == y(seg->p[1])) return TRUE;
 
101
        assert(x(seg->p[0]) == x(seg->p[1]));
 
102
        return FALSE;
 
103
}
 
104
 
 
105
        /* tiles */
 
106
/* construct a tile from two points.
 
107
 *  seglists are initially empty.
 
108
 *      the tile is not entered into the global configuration.
 
109
 */
 
110
Tile_t  *ERmake_tile(ERview_t *D, Pt_t p0, Pt_t p1)
 
111
{
 
112
        int                     i,d;
 
113
        Tile_t          *rv;
 
114
        Seglist_t       *segs;
 
115
        static int      next_id = 0;
 
116
 
 
117
        assert (x(p0) != x(p1));
 
118
        assert (y(p0) != y(p1));
 
119
 
 
120
        rv = agalloc(ergraph(D),sizeof(Tile_t));
 
121
        for (d = 0; d < 2; d++) {
 
122
                rv->LL.c[d] = MIN(p0.c[d],p1.c[d]);
 
123
                rv->UR.c[d] = MAX(p0.c[d],p1.c[d]);
 
124
        }
 
125
        for (i = 0; i < NSIDES; i++) {
 
126
                segs = rv->segs[i] = ERmake_seglist(D);
 
127
        }
 
128
        rv->id = next_id++;
 
129
        return rv;
 
130
}
 
131
 
 
132
void ERfree_tile(ERview_t *D, Tile_t *b) {
 
133
        Dir_t   side;
 
134
        for (side = 0; side < NSIDES; side++) ERfree_seglist(D,b->segs[side]);
 
135
        agfree(ergraph(D),b);
 
136
}
 
137
 
 
138
Pt_t ERtile_LL(Tile_t *b) {return b->LL;}
 
139
Pt_t ERtile_LR(Tile_t *b) {return ERmkpoint(x(b->UR),y(b->LL));}
 
140
Pt_t ERtile_UR(Tile_t *b) {return b->UR;}
 
141
Pt_t ERtile_UL(Tile_t *b) {return ERmkpoint(x(b->LL),y(b->UR));}
 
142
 
 
143
void ERcorners(Tile_t *b, Pt_t *p)
 
144
{
 
145
        p[0] = ERtile_LL(b);
 
146
        p[1] = ERtile_UL(b);
 
147
        p[2] = ERtile_UR(b);
 
148
        p[3] = ERtile_LR(b);
 
149
}
 
150
 
 
151
        /* note, must return points in ascending order. */
 
152
void ERget_tile_side(Tile_t *b, Dir_t side, Pt_t *p)
 
153
{
 
154
        switch (side) {
 
155
        case north:     p[0] = ERtile_UL(b); p[1] = ERtile_UR(b); break;
 
156
        case east:      p[0] = ERtile_LR(b); p[1] = ERtile_UR(b); break;
 
157
        case south:     p[0] = ERtile_LL(b); p[1] = ERtile_LR(b); break;
 
158
        case west:      p[0] = ERtile_LL(b); p[1] = ERtile_UL(b); break;
 
159
        default: abort();
 
160
        }
 
161
}
 
162
 
 
163
Dir_t ERtile_side_of(Tile_t *b, Pt_t p, Pt_t q)
 
164
{
 
165
        Dir_t side = nosuchdir;
 
166
 
 
167
        if (x(p) == x(q)) {
 
168
                if (NONDECREASING(y(b->LL),y(p),y(b->UR))
 
169
                        && NONDECREASING(y(b->LL),y(q),y(b->UR))) {
 
170
                        if (x(p) == x(b->LL)) side = west;
 
171
                        else if (x(p) == x(b->UR)) side = east;
 
172
                }
 
173
        }
 
174
        else {
 
175
                assert (y(p) == y(q));
 
176
                if (NONDECREASING(x(b->LL),x(p),x(b->UR))
 
177
                        && NONDECREASING(x(b->LL),x(q),x(b->UR))) {
 
178
                        if (y(p) == y(b->LL)) side = south;
 
179
                        else if (y(p) == y(b->UR)) side = north;
 
180
                }
 
181
        }
 
182
        return side;
 
183
}
 
184
 
 
185
static ilbool on_side(Tile_t *b, Pt_t p, Pt_t q)
 
186
{
 
187
        return (ERtile_side_of(b,p,q) != nosuchdir);
 
188
}
 
189
 
 
190
static ilbool pt_in_tile(Pt_t p, Tile_t *b) {
 
191
        return (NONDECREASING(x(b->LL),x(p),x(b->UR)) &&
 
192
                NONDECREASING(y(b->LL),y(p),y(b->UR)));
 
193
}
 
194
 
 
195
ilbool ERpt_strictly_in_tile(Pt_t p, Tile_t *b) {
 
196
        return (INCREASING(x(b->LL),x(p),x(b->UR)) &&
 
197
                INCREASING(y(b->LL),y(p),y(b->UR)));
 
198
}
 
199
 
 
200
ilbool ERtiles_nontrivially_intersect(Tile_t *b0, Tile_t *b1) {
 
201
        if ((x(b0->UR) <= x(b1->LL))    /* b0 is left */
 
202
        ||  (x(b0->LL) >= x(b1->UR))    /* b0 is right */
 
203
        ||  (y(b0->UR) <= y(b1->LL))    /* b0 is below */
 
204
        ||  (y(b0->LL) >= y(b1->UR)))   /* b0 is above */
 
205
                return FALSE; 
 
206
        return TRUE;
 
207
}
 
208
 
 
209
ilbool ERtile_covers_tile(Tile_t *outer, Tile_t *inner)
 
210
{
 
211
        if ((x(outer->LL) > x(inner->LL))
 
212
        ||  (x(outer->UR) < x(inner->UR))
 
213
        ||  (y(outer->LL) > x(inner->LL))
 
214
        ||  (y(outer->UR) < x(inner->UR))) return FALSE;
 
215
        return TRUE;
 
216
}
 
217
 
 
218
        /* segments */
 
219
 
 
220
Seg_t *ERmkseg(ERview_t *D, Pt_t p, Pt_t q, Tile_t *b0, Tile_t *b1, Segkind_t kind) {
 
221
        Pt_t    t;
 
222
        Seg_t   *rv;
 
223
 
 
224
        if ( (x(p) == x(q)) + (y(p) == y(q)) != 1) abort();
 
225
        if NOT(on_side(b0,p,q)) abort();
 
226
        if NOT(on_side(b1,p,q)) abort();
 
227
 
 
228
        if ( ((y(p) == y(q)) && (x(p) > x(q))) ||
 
229
             ((x(p) == x(q)) && (y(p) > y(q))))
 
230
                 { t = p; p = q; q = t; }               /* pts always in ascending order */
 
231
        rv = agalloc(ergraph(D),sizeof(Seg_t));
 
232
        rv->p[0] = p; rv->p[1] = q;
 
233
        rv->b[0] = b0; rv->b[1] = b1;
 
234
        rv->kind = kind;
 
235
        return rv;
 
236
}
 
237
 
 
238
void ERfree_seg(ERview_t *D, Seg_t *s) {agfree(ergraph(D),s);}
 
239
 
 
240
void ERinstall_new_seg(ERview_t *D, Pt_t p, Pt_t q, Segkind_t kind, Tile_t *b0, Dir_t side, Tile_t *b1)
 
241
{
 
242
        Seg_t   *newseg;
 
243
        newseg = ERmkseg(D,p,q,b0,b1,kind);
 
244
        ERseglist_append(D,b0->segs[side],newseg);
 
245
        ERseglist_append(D,b1->segs[opposite(side)],newseg);
 
246
}
 
247
 
 
248
 
 
249
static Dir_t ERside_toward(Tile_t *b, Pt_t p)
 
250
{
 
251
        Dir_t   side;
 
252
 
 
253
        if (y(p) > y(b->UR)) side = north;
 
254
        else if (y(p) < y(b->LL)) side = south;
 
255
        else if (x(p) > x(b->UR)) side = east;
 
256
        else if (x(p) < x(b->LL)) side = west;
 
257
        else side = nosuchdir;
 
258
        return side;
 
259
}
 
260
 
 
261
static int varying(Dir_t side)  /* depends on internal values of Dir_t enum */
 
262
{
 
263
        return (side + 1) % 2;
 
264
}
 
265
 
 
266
        /* walk one step from b toward p */
 
267
Tile_t *ERneighbor(Tile_t *b, Pt_t p)
 
268
{
 
269
        int             i, c;
 
270
        Seg_t   *seg;
 
271
        Tile_t  *rv;
 
272
        Dir_t   side;
 
273
 
 
274
        side = ERside_toward(b,p);
 
275
        if (side == nosuchdir) rv = b;
 
276
        else {
 
277
                c = varying(side);
 
278
                for (i = 0; (seg = b->segs[side]->list[i]); i++)
 
279
                        if (NONDECREASING(seg->p[0].c[c],p.c[c],seg->p[1].c[c])) break;
 
280
                if (b != seg->b[0]) rv = seg->b[0]; else rv = seg->b[1];
 
281
        }
 
282
        return rv;
 
283
}
 
284
 
 
285
static Seg_t *find_seg(Tile_t *b, Pt_t p)
 
286
{
 
287
        int             i,d0,d1;
 
288
        Pt_t    cp[2];
 
289
        Dir_t   side;
 
290
        Seglist_t *seglist;
 
291
        Seg_t   *seg;
 
292
 
 
293
        for (side = 0; side < NSIDES; side++) {
 
294
                ERget_tile_side(b,side,cp);
 
295
                d1 = side % 2; d0 = !d1;
 
296
                if (p.c[d1] == cp[0].c[d1]) {
 
297
                        if (NONDECREASING(cp[0].c[d0],p.c[d0],cp[1].c[d0])) {
 
298
                                seglist = b->segs[side];
 
299
                                for (i = 0; (seg = seglist->list[i]); i++) {
 
300
                                        if (NONDECREASING(seg->p[0].c[d0],p.c[d0],seg->p[1].c[d0]))
 
301
                                                return seg;
 
302
                                }
 
303
                        }
 
304
                        else break;
 
305
                }
 
306
        }
 
307
        return NIL(Seg_t*);
 
308
}
 
309
 
 
310
 
 
311
        /* locate the tile of a given point */
 
312
Tile_t *ERlocate(ERview_t *D, Pt_t p)
 
313
{
 
314
        Tile_t  *b;
 
315
        int             i;
 
316
 
 
317
        for (i = 0; (b = D->config->list[i]); i++)
 
318
                if (pt_in_tile(p,b)) break;
 
319
        return b;
 
320
}
 
321
 
 
322
void ERlocate_endpoint(ERview_t *D, Tile_t *user_node, Pt_t pt,
 
323
                        Tile_t **pb, Seg_t **pseg)
 
324
{
 
325
        Tile_t  *b;
 
326
        Seg_t   *seg;
 
327
 
 
328
        b = ERlocate(D,pt);
 
329
        seg = find_seg(b,pt);
 
330
        if (seg) {
 
331
                if (NOT(ERtiles_nontrivially_intersect(user_node,b)))
 
332
                        b = (b != seg->b[0]?  seg->b[0] : seg->b[1]);
 
333
        }
 
334
        else b = NIL(Tile_t*);
 
335
        *pb = b;
 
336
        *pseg = seg;
 
337
}
 
338
 
 
339
static Pt_t snap_to(Pt_t p, Tile_t *b)
 
340
{
 
341
        int             c;
 
342
 
 
343
        for (c = 0; c < 2; c++) {
 
344
                if (p.c[c] < b->LL.c[c])  p.c[c] = b->LL.c[c];
 
345
                else if (p.c[c] > b->UR.c[c]) p.c[c] = b->UR.c[c];
 
346
        }
 
347
        return p;
 
348
}
 
349
 
 
350
        /* split the configuration by a given line segment */
 
351
 
 
352
void ERmark_segs(ERview_t *D, Pt_t p, Pt_t q, Segkind_t kind)
 
353
{
 
354
        int             i,c,d;
 
355
        Tile_t  *b,*last_b;
 
356
        Pt_t    p0;
 
357
        Dir_t   side;
 
358
        Seg_t   *seg;
 
359
 
 
360
        if (y(p) == y(q)) {c = 0; d = 1;}
 
361
        else {c = 1; d = 0;}
 
362
        if (p.c[c] > q.c[c]) {Pt_t t; t = p; p = q; q = t;}
 
363
        b = ERlocate(D,p);
 
364
        do {
 
365
                p0 = snap_to(q,b);
 
366
                assert(p0.c[d] == p.c[d]);
 
367
                assert(p0.c[d] == q.c[d]);
 
368
                if (NOT(pt_eq(p,p0))) {
 
369
                        side = ERtile_side_of(b,p,p0);
 
370
                        for (i = 0; (seg = b->segs[side]->list[i]); i++) {
 
371
                                if ((seg->p[0].c[c] < q.c[c]) &&
 
372
                                        (seg->p[1].c[c] > p.c[c])) {
 
373
                                        seg->kind = kind;
 
374
                                }
 
375
                        }
 
376
                }
 
377
                p = p0;
 
378
                last_b = b;
 
379
                b = ERneighbor(b,q);
 
380
        } while (b != last_b);
 
381
}
 
382
 
 
383
void ERmark_container_segs(ERview_t *d, Tile_t *b, Segkind_t kind)
 
384
{
 
385
        int             i;
 
386
        Tile_t  *nb;
 
387
        Pt_t    corner[4];
 
388
        Dir_t   side;
 
389
 
 
390
        for (i = 0; (nb = d->nodes->list[i]); i++) {
 
391
                if (ERtile_covers_tile(nb,b)) {
 
392
                        ERcorners(b,corner);
 
393
                        for (side = 0; side < NSIDES; side++) {
 
394
                                ERmark_segs(d,corner[side],corner[(side+1)%4],kind);
 
395
                        }
 
396
                }
 
397
        }
 
398
}
 
399
 
 
400
Dir_t ERtiles_share_side(Tile_t *b, Tile_t *cb, Pt_t *res)
 
401
{
 
402
        int                     d0,d1;
 
403
        Dir_t           side, opp;
 
404
        Pt_t            bseg[2],cbseg[2];
 
405
 
 
406
        for (side = 0; side < NSIDES; side++) {
 
407
                d0 = (side % 2);
 
408
                d1 = (d0? 0 : 1);
 
409
                opp = opposite(side);
 
410
                ERget_tile_side(b,side,bseg);
 
411
                ERget_tile_side(cb,opp,cbseg);
 
412
                if (bseg[0].c[d0] != cbseg[0].c[d0]) continue;
 
413
                if (bseg[1].c[d1] <= cbseg[0].c[d1]) continue;
 
414
                if (bseg[0].c[d1] >= cbseg[1].c[d1]) continue;
 
415
                if (bseg[0].c[d1] < cbseg[0].c[d1]) res[0] = cbseg[0];
 
416
                else res[0] = bseg[0];
 
417
                if (bseg[1].c[d1] > cbseg[1].c[d1]) res[1] = cbseg[1];
 
418
                else res[1] = bseg[1];
 
419
if NOT(on_side(b,res[0],res[1])) abort();
 
420
if NOT(on_side(cb,res[0],res[1])) abort();
 
421
                return side;
 
422
        }
 
423
        return nosuchdir;
 
424
}