1 /*
2 * vim: ts=4 sw=4 et tw=0 wm=0
3 *
4 * libavoid - Fast, Incremental, Object-avoiding Line Router
5 * Copyright (C) 2004-2005 Michael Wybrow <mjwybrow@users.sourceforge.net>
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2.1 of the License, or (at your option) any later version.
11 *
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 *
21 */
23 #include "libavoid/graph.h"
24 #include "libavoid/makepath.h"
25 #include "libavoid/visibility.h"
26 #include "libavoid/debug.h"
29 namespace Avoid {
32 ConnRefList connRefs;
35 ConnRef::ConnRef(const unsigned int id)
36 : _id(id)
37 , _needs_reroute_flag(true)
38 , _false_path(false)
39 , _active(false)
40 , _route_dist(0)
41 , _srcVert(NULL)
42 , _dstVert(NULL)
43 , _initialised(false)
44 , _callback(NULL)
45 , _connector(NULL)
46 {
47 // TODO: Store endpoints and details.
48 _route.pn = 0;
49 _route.ps = NULL;
50 }
53 ConnRef::ConnRef(const unsigned int id, const Point& src, const Point& dst)
54 : _id(id)
55 , _needs_reroute_flag(true)
56 , _false_path(false)
57 , _active(false)
58 , _route_dist(0)
59 , _srcVert(NULL)
60 , _dstVert(NULL)
61 , _initialised(false)
62 , _callback(NULL)
63 , _connector(NULL)
64 {
65 _route.pn = 0;
66 _route.ps = NULL;
68 if (IncludeEndpoints)
69 {
70 bool isShape = false;
71 _srcVert = new VertInf(VertID(id, isShape, 1), src);
72 _dstVert = new VertInf(VertID(id, isShape, 2), dst);
73 vertices.addVertex(_srcVert);
74 vertices.addVertex(_dstVert);
75 makeActive();
76 _initialised = true;
77 }
78 }
81 ConnRef::~ConnRef()
82 {
83 freeRoute();
85 if (_srcVert)
86 {
87 vertices.removeVertex(_srcVert);
88 delete _srcVert;
89 _srcVert = NULL;
90 }
92 if (_dstVert)
93 {
94 vertices.removeVertex(_dstVert);
95 delete _dstVert;
96 _dstVert = NULL;
97 }
99 if (_active)
100 {
101 makeInactive();
102 }
103 }
105 void ConnRef::updateEndPoint(const unsigned int type, const Point& point)
106 {
107 assert((type == (unsigned int) VertID::src) ||
108 (type == (unsigned int) VertID::tar));
109 //assert(IncludeEndpoints);
111 if (!_initialised)
112 {
113 makeActive();
114 _initialised = true;
115 }
117 VertInf *altered = NULL;
118 VertInf *partner = NULL;
119 bool isShape = false;
121 if (type == (unsigned int) VertID::src)
122 {
123 if (_srcVert)
124 {
125 _srcVert->Reset(point);
126 }
127 else
128 {
129 _srcVert = new VertInf(VertID(_id, isShape, type), point);
130 vertices.addVertex(_srcVert);
131 }
133 altered = _srcVert;
134 partner = _dstVert;
135 }
136 else // if (type == (unsigned int) VertID::dst)
137 {
138 if (_dstVert)
139 {
140 _dstVert->Reset(point);
141 }
142 else
143 {
144 _dstVert = new VertInf(VertID(_id, isShape, type), point);
145 vertices.addVertex(_dstVert);
146 }
148 altered = _dstVert;
149 partner = _srcVert;
150 }
152 bool knownNew = false;
153 vertexVisibility(altered, partner, knownNew, true);
154 }
157 void ConnRef::makeActive(void)
158 {
159 assert(!_active);
161 // Add to connRefs list.
162 _pos = connRefs.insert(connRefs.begin(), this);
163 _active = true;
164 }
167 void ConnRef::makeInactive(void)
168 {
169 assert(_active);
171 // Remove from connRefs list.
172 connRefs.erase(_pos);
173 _active = false;
174 }
177 void ConnRef::freeRoute(void)
178 {
179 if (_route.ps)
180 {
181 _route.pn = 0;
182 std::free(_route.ps);
183 _route.ps = NULL;
184 }
185 }
188 PolyLine& ConnRef::route(void)
189 {
190 return _route;
191 }
194 void ConnRef::calcRouteDist(void)
195 {
196 _route_dist = 0;
197 for (int i = 1; i < _route.pn; i++)
198 {
199 _route_dist += dist(_route.ps[i], _route.ps[i - 1]);
200 }
201 }
204 bool ConnRef::needsReroute(void)
205 {
206 return (_false_path || _needs_reroute_flag);
207 }
210 void ConnRef::moveRoute(const int& diff_x, const int& diff_y)
211 {
212 for (int i = 0; i < _route.pn; i++)
213 {
214 _route.ps[i].x += diff_x;
215 _route.ps[i].y += diff_y;
216 }
217 }
220 void ConnRef::lateSetup(const Point& src, const Point& dst)
221 {
222 assert(!_initialised);
224 bool isShape = false;
225 _srcVert = new VertInf(VertID(_id, isShape, 1), src);
226 _dstVert = new VertInf(VertID(_id, isShape, 2), dst);
227 vertices.addVertex(_srcVert);
228 vertices.addVertex(_dstVert);
229 makeActive();
230 _initialised = true;
231 }
234 VertInf *ConnRef::src(void)
235 {
236 return _srcVert;
237 }
240 VertInf *ConnRef::dst(void)
241 {
242 return _dstVert;
243 }
246 bool ConnRef::isInitialised(void)
247 {
248 return _initialised;
249 }
252 void ConnRef::unInitialise(void)
253 {
254 vertices.removeVertex(_srcVert);
255 vertices.removeVertex(_dstVert);
256 makeInactive();
257 _initialised = false;
258 }
261 void ConnRef::removeFromGraph(void)
262 {
263 for (VertInf *iter = _srcVert; iter != NULL; )
264 {
265 VertInf *tmp = iter;
266 iter = (iter == _srcVert) ? _dstVert : NULL;
268 // For each vertex.
269 EdgeInfList& visList = tmp->visList;
270 EdgeInfList::iterator finish = visList.end();
271 EdgeInfList::iterator edge;
272 while ((edge = visList.begin()) != finish)
273 {
274 // Remove each visibility edge
275 delete (*edge);
276 }
278 EdgeInfList& invisList = tmp->invisList;
279 finish = invisList.end();
280 while ((edge = invisList.begin()) != finish)
281 {
282 // Remove each invisibility edge
283 delete (*edge);
284 }
285 }
286 }
289 void ConnRef::setCallback(void (*cb)(void *), void *ptr)
290 {
291 _callback = cb;
292 _connector = ptr;
293 }
296 void ConnRef::handleInvalid(void)
297 {
298 if (_false_path || _needs_reroute_flag) {
299 if (_callback) {
300 _callback(_connector);
301 }
302 }
303 }
306 void ConnRef::makePathInvalid(void)
307 {
308 _needs_reroute_flag = true;
309 }
312 int ConnRef::generatePath(Point p0, Point p1)
313 {
314 if (!_false_path && !_needs_reroute_flag) {
315 // This connector is up to date.
316 return (int) false;
317 }
319 _false_path = false;
320 _needs_reroute_flag = false;
322 VertInf *src = _srcVert;
323 VertInf *tar = _dstVert;
325 if (!IncludeEndpoints)
326 {
327 lateSetup(p0, p1);
329 // Update as they have just been set by lateSetup.
330 src = _srcVert;
331 tar = _dstVert;
333 bool knownNew = true;
334 vertexVisibility(src, tar, knownNew);
335 vertexVisibility(tar, src, knownNew);
336 }
338 bool *flag = &(_needs_reroute_flag);
340 makePath(this, flag);
342 bool result = true;
344 int pathlen = 1;
345 for (VertInf *i = tar; i != src; i = i->pathNext)
346 {
347 pathlen++;
348 if (i == NULL)
349 {
350 db_printf("Warning: Path not found...\n");
351 pathlen = 2;
352 tar->pathNext = src;
353 if (InvisibilityGrph)
354 {
355 // TODO: Could we know this edge already?
356 EdgeInf *edge = EdgeInf::existingEdge(src, tar);
357 assert(edge != NULL);
358 edge->addCycleBlocker();
359 }
360 result = false;
361 break;
362 }
363 if (pathlen > 100)
364 {
365 fprintf(stderr, "ERROR: Should never be here...\n");
366 exit(1);
367 }
368 }
369 Point *path = (Point *) malloc(pathlen * sizeof(Point));
371 int j = pathlen - 1;
372 for (VertInf *i = tar; i != src; i = i->pathNext)
373 {
374 if (InvisibilityGrph)
375 {
376 // TODO: Again, we could know this edge without searching.
377 EdgeInf *edge = EdgeInf::existingEdge(i, i->pathNext);
378 edge->addConn(flag);
379 }
380 else
381 {
382 _false_path = true;
383 }
384 path[j--] = i->point;
385 }
386 path[0] = src->point;
389 // Would clear visibility for endpoints here if required.
391 PolyLine& output_route = route();
392 output_route.pn = pathlen;
393 output_route.ps = path;
395 return (int) result;
396 }
399 //============================================================================
402 // It's intended this function is called after shape movement has
403 // happened to alert connectors that they need to be rerouted.
404 void callbackAllInvalidConnectors(void)
405 {
406 ConnRefList::iterator fin = connRefs.end();
407 for (ConnRefList::iterator i = connRefs.begin(); i != fin; ++i) {
408 (*i)->handleInvalid();
409 }
410 }
413 }