Graphviz  2.41.20170921.2350
pointset.c
Go to the documentation of this file.
1 /* $Id$ $Revision$ */
2 /* vim:set shiftwidth=4 ts=8: */
3 
4 /*************************************************************************
5  * Copyright (c) 2011 AT&T Intellectual Property
6  * All rights reserved. This program and the accompanying materials
7  * are made available under the terms of the Eclipse Public License v1.0
8  * which accompanies this distribution, and is available at
9  * http://www.eclipse.org/legal/epl-v10.html
10  *
11  * Contributors: See CVS logs. Details at http://www.graphviz.org/
12  *************************************************************************/
13 
14 
15 #include "render.h"
16 #include "pointset.h"
17 
18 typedef struct {
21 } pair;
22 
23 static pair *mkPair(point p)
24 {
25  pair *pp;
26 
27  pp = NEW(pair);
28  pp->id = p;
29  return pp;
30 }
31 
32 static void freePair(Dt_t * d, pair* pp, Dtdisc_t * disc)
33 {
34  free (pp);
35 }
36 
37 static int cmppair(Dt_t * d, point * key1, point * key2, Dtdisc_t * disc)
38 {
39  if (key1->x > key2->x)
40  return 1;
41  else if (key1->x < key2->x)
42  return -1;
43  else if (key1->y > key2->y)
44  return 1;
45  else if (key1->y < key2->y)
46  return -1;
47  else
48  return 0;
49 }
50 
51 static Dtdisc_t intPairDisc = {
52  offsetof(pair, id),
53  sizeof(point),
54  offsetof(pair, link),
55  0,
56  (Dtfree_f) freePair,
57  (Dtcompar_f) cmppair,
58  0,
59  0,
60  0
61 };
62 
64 {
65  return (dtopen(&intPairDisc, Dtoset));
66 }
67 
68 void freePS(PointSet * ps)
69 {
70  dtclose(ps);
71 }
72 
73 void insertPS(PointSet * ps, point pt)
74 {
75  pair *pp;
76 
77  pp = mkPair(pt);
78  if (dtinsert(ps, pp) != pp)
79  free(pp);
80 }
81 
82 void addPS(PointSet * ps, int x, int y)
83 {
84  point pt;
85  pair *pp;
86 
87  pt.x = x;
88  pt.y = y;
89  pp = mkPair(pt);
90  if (dtinsert(ps, pp) != pp)
91  free(pp);
92 }
93 
94 int inPS(PointSet * ps, point pt)
95 {
96  pair p;
97  p.id = pt;
98  return ((dtsearch(ps, &p)) ? 1 : 0);
99 }
100 
101 int isInPS(PointSet * ps, int x, int y)
102 {
103  pair p;
104  p.id.x = x;
105  p.id.y = y;
106  return ((dtsearch(ps, &p)) ? 1 : 0);
107 }
108 
109 int sizeOf(PointSet * ps)
110 {
111  return dtsize(ps);
112 }
113 
115 {
116  int n = dtsize(ps);
117  point *pts = N_NEW(n, point);
118  pair *p;
119  point *pp = pts;
120 
121  for (p = (pair *) dtflatten(ps); p;
122  p = (pair *) dtlink(ps, (Dtlink_t *) p)) {
123  *pp++ = p->id;
124  }
125 
126  return pts;
127 }
128 
129 typedef struct {
132  int v;
133 } mpair;
134 
135 typedef struct {
138 } MPairDisc;
139 
140 static mpair *mkMPair(Dt_t * d, mpair * obj, MPairDisc * disc)
141 {
142  mpair *ap;
143 
144  if (disc->flist) {
145  ap = disc->flist;
146  disc->flist = (mpair *) (ap->link.right);
147  } else
148  ap = GNEW(mpair);
149  ap->id = obj->id;
150  ap->v = obj->v;
151  return ap;
152 }
153 
154 static void freeMPair(Dt_t * d, mpair * ap, MPairDisc * disc)
155 {
156  ap->link.right = (Dtlink_t *) (disc->flist);
157  disc->flist = ap;
158 }
159 
160 static Dtdisc_t intMPairDisc = {
161  offsetof(mpair, id),
162  sizeof(point),
163  offsetof(mpair, link),
164  (Dtmake_f) mkMPair,
165  (Dtfree_f) freeMPair,
166  (Dtcompar_f) cmppair,
167  0,
168  0,
169  0
170 };
171 
173 {
174  MPairDisc *dp = GNEW(MPairDisc);
175 
176  dp->disc = intMPairDisc;
177  dp->flist = 0;
178 
179  return (dtopen(&(dp->disc), Dtoset));
180 }
181 
182 void clearPM(PointMap * ps)
183 {
184  dtclear(ps);
185 }
186 
187 void freePM(PointMap * ps)
188 {
189  MPairDisc *dp = (MPairDisc *) (ps->disc);
190  mpair *p;
191  mpair *next;
192 
193  dtclose(ps);
194  for (p = dp->flist; p; p = next) {
195  next = (mpair *) (p->link.right);
196  free(p);
197  }
198  free(dp);
199 }
200 
201 int updatePM(PointMap * pm, int x, int y, int v)
202 {
203  mpair *p;
204  mpair dummy;
205  int old;
206 
207  dummy.id.x = x;
208  dummy.id.y = y;
209  dummy.v = v;
210  p = dtinsert(pm, &dummy);
211  old = p->v;
212  p->v = v;
213  return old;
214 }
215 
216 int insertPM(PointMap * pm, int x, int y, int v)
217 {
218  mpair *p;
219  mpair dummy;
220 
221  dummy.id.x = x;
222  dummy.id.y = y;
223  dummy.v = v;
224  p = dtinsert(pm, &dummy);
225  return p->v;
226 }
Dtdisc_t * disc
Definition: cdt.h:101
void freePS(PointSet *ps)
Definition: pointset.c:68
void insertPS(PointSet *ps, point pt)
Definition: pointset.c:73
int(* Dtcompar_f)(Dt_t *, void *, void *, Dtdisc_t *)
Definition: cdt.h:40
PointSet * newPS(void)
Definition: pointset.c:63
CDT_API int dtclose(Dt_t *)
#define N_NEW(n, t)
Definition: memory.h:36
void *(* Dtmake_f)(Dt_t *, void *, Dtdisc_t *)
Definition: cdt.h:38
point id
Definition: pointset.c:20
CDT_API Dtlink_t * dtflatten(Dt_t *)
Definition: dtflatten.c:9
CDT_API Dtmethod_t * Dtoset
Definition: cdt.h:166
int v
Definition: pointset.c:132
Definition: cdt.h:80
int insertPM(PointMap *pm, int x, int y, int v)
Definition: pointset.c:216
mpair * flist
Definition: pointset.c:137
int x
Definition: geom.h:26
CDT_API Dt_t * dtopen(Dtdisc_t *, Dtmethod_t *)
Definition: dtopen.c:9
#define dtsearch(d, o)
Definition: cdt.h:260
int updatePM(PointMap *pm, int x, int y, int v)
Definition: pointset.c:201
int sizeOf(PointSet *ps)
Definition: pointset.c:109
int isInPS(PointSet *ps, int x, int y)
Definition: pointset.c:101
point * pointsOf(PointSet *ps)
Definition: pointset.c:114
void clearPM(PointMap *ps)
Definition: pointset.c:182
CDT_API int dtsize(Dt_t *)
Definition: dtsize.c:12
#define dtinsert(d, o)
Definition: cdt.h:262
void addPS(PointSet *ps, int x, int y)
Definition: pointset.c:82
#define GNEW(t)
Definition: memory.h:37
Definition: geom.h:26
void freePM(PointMap *ps)
Definition: pointset.c:187
int inPS(PointSet *ps, point pt)
Definition: pointset.c:94
#define dtclear(d)
Definition: cdt.h:267
point id
Definition: pointset.c:131
Definition: pointset.c:18
Dtlink_t link
Definition: pointset.c:130
Dtlink_t link
Definition: pointset.c:19
void(* Dtfree_f)(Dt_t *, void *, Dtdisc_t *)
Definition: cdt.h:39
Definition: cdt.h:99
Dtdisc_t disc
Definition: pointset.c:136
int y
Definition: geom.h:26
#define dtlink(d, e)
Definition: cdt.h:250
Ppoint_t point
Definition: printvis.c:16
#define NEW(t)
Definition: memory.h:35
PointMap * newPM(void)
Definition: pointset.c:172